MAP decoding of variable length codes with self-synchronization strings

Maximum a posteriori probability (MAP) decoding of Huffman-equivalent variable-length codes (VLCs) has two undesired features. One is the high decoding complexity, and the other is the discrepancy between the objective of MAP decoding and the Levenshtein distance which is commonly used as the performance metric. In this correspondence, improvement over these two issues is targeted through extracting self-synchronization information in VLC coded sequence and incorporating it into MAP decoding. It will be shown that self-synchronization strings (SSSs) are concatenation of Huffman codewords and can be readily found. Occurrence probabilities of SSSs are then analyzed. By using this self-synchronization information, MAP decoding is split into multiple decoding of short data segments so that both decoding performance improvement and complexity reduction are obtained. Simulation results demonstrate the effectiveness of the proposed method.