Heuristic survivor selection for reduced complexity BCJR-type algorithms

The invention of turbo coding demonstrated that interleaved concatenation of weak codes can achieve excellent performance in the waterfall region of the bit error rate curve when decoded iteratively. The performance curve of turbo codes, however, typically exhibits an error floor due to poor minimum distance. The minimum distance can be increased by introducing a stronger component code into the concatenation, but this can lead to unacceptably large decoding effort if full BCJR decoding is used. In this paper we consider reduced complexity soft input soft output decoding of convolutional codes with long constraint lengths. In particular, we consider the M*-BCJR algorithm, which uses the M-algorithm principle to preserve only the M most promising trellis states at each step of the forward recursion. We demonstrate that the forward state metrics, typically used in M-type algorithms, are insufficient to reliably identify the best M states. In contrast, very small M suffices to achieve very good decoding performance if the state selection is based on both the forward metric and an estimate of the backward metric. We present how a heuristic based on a supercode, a higher rate code containing all the codewords of the original code but having a simpler trellis representation, can serve as an efficient estimate for the backward state metrics, enabling practical decoding of turbo codes with a strong component code.