Robust Data Compression: Consistency Checking in the Synchronization of Variable Length Codes

Many data compression techniques are essentially variable length codes. Such codes suffer from a vulnerability to error propagation. This occurs when an error causes the correspondence between the data stream and the stream of encoded symbols to be lost and continues until synchronization between the two is re-established. This paper compares a number of strategies for synchronization in which redundant synchronizing words are used with a mechanism for labelling or counting them. In each case the strategy is investigated for the prevention of error propagation, ensuring the re-establishment of the correspondence with the correct point in the data stream. Three classes of potential synchronization error are explored: the false recognition of spurious words, the loss of synchronizing words and synchronization misinterpretation, when one synchronizing word is confused with another. The probabilities of synchronization error are analysed. It is shown that the strategies are successful against random errors when they incorporate some mechanism for consistency checking. The relative merits of different schemes are demonstrated. The schemes are also compared with the technique known as bitstuffing. This is considered on its own and in combination with the other schemes.