Self-Synchronizing Sequential Coding with Low Redundancy

In several previous papers, the author has pursued two apparently separate paths of development. The first path involves classes of slightly sulx>ptimal variable-length prefix codes1-2 whose self-synchronizing abilities are vastly superior to the optimal (Huffman) codes which minimize redundancy. T h e second path involves self-synchronizing sequential codes using information-lossless sequential machines as encoders and decoders.*- 4 In this paper, these two paths of development are joined. The result produces highly efficient sequential codes (with low redundancy· which have good self-synchronizing abilities and surprisingly low decoding complexity. These codes are applicable in situations in which the message source is highly correlated. 951 952 THH DELL SYSTEM TECHNICAL JOURNAL, MARCH 1971 I.i Difference Codes Given an environment in which successive source signals are likely to be similar (or at least strongly correlated), considerable compression can be obtained by encoding the level difference between successive quantized signal levels (temporally or spatially). Such is the situation in a video picture environment, for example, with respect to adjacent points horizontally or vertically, or even to the same point in successive frames. By encoding differences, however, any error in quantizing, encoding, transmitting, decoding or reconstructing the image tends to persist. That is, once an error has occurred in a signal level, subsequent levels will continue to be in error by the same offset, unless terminated by boundary effects or by compensating errors.