TRELLIS DATA COMPRESSION

Tree and trellis data compression systems have traditionally been designed by using a tree or trellis search algorithm to improve the performance of traditional coding systems such as adaptive delta modulation or predictive quantization. Recent work in the area of vector quantization has suggested the possibility of designing new tree and trellis codes which are well matched to particular sources. The main design procedure iterates on a long training sequence to improve the performance of an initial trellis decoder. An additional procedure, given a trellis decoder, can produce a decoder of longer constraint length which performs at least as well. Combined, these algorithms provide a complete design procedure for trellis encoding data compression systems.

For random sources, many existing data compression systems can be readily improved and performance close to the rate-distortion bound can be obtained. In the applications area of speech compression, tree and trellis codes designed with these algorithms permit the construction of low rate speech waveform coders, low rate residual excited linear predictive coders (RELP), and a new kind of hybrid tree coder which provides good quality speech at rates below 7000 bits per second.