On the Construction and MAP Decoding of Optimal Variable-Length Error-Correcting Codes

Abstract

In this paper, we present a novel algorithm that guarantees of finding a variable-length error-correcting code (VLEC) with minimal average codeword length for a fixed free distance d(free). We also propose a low complexity maximum a posterior (MAP) decoding algorithm for our codes under the premise that the receiver knows the number of codewords being transmitted. The resulting VLEC provides significant gains over other codes from the literature. When compared with separate source-channel tandem codes with identical d(free), such as a tandem code consisting of a Huffman source code concatenated with a (2, 1, 4) tail-biting convolutional channel code, our system has only a 0.3 dB performance loss at a bit error rate of 10(-5) while requiring significantly less decoding complexity.