Until recently, most known decoding procedures for error-correcting codes were based either on algebraically calculating the error pattern or on some sort of tree or trellis search. With the advent of turbo coding, a third decoding principle has finally had its breakthrough: iterative decoding. With respect to Viterbi decoding, a code is most naturally described by means of a trellis diagram. The main thesis of the present paper is that, with respect to iterative decoding, the natural way of describing a code is by means of a Tanner graph, which may be viewed as a generalized trellis. More precisely, it is the "time axis" of a trellis that is generalized to a Tanner graph.
Abstract A general framework, based on ideas of Tanner, for the description of codes and iterative decoding (“turbo coding”) is developed. Just like trellis‐based code descriptions are naturally matched to Viterbi decoding, code descriptions based on Tanner graphs (which may be viewed as generalized trellises) are naturally matched to iterative decoding. Two basic iterative decoding algorithms (which are versions of the algorithms of Berrou et al. and of Hagenauer, respectively) are shown to be natural generalizations of the forward‐backward algorithm (Bahl et al.) and the Viterbi algorithm, respectively, to arbitrary Tanner graphs. The careful derivation of these algorithms clarifies, in particular, which a priori probabilities are admissible and how they are properly dealt with. For cycle codes (a class of binary linear block codes), a complete characterization is given of the error patterns that are corrected by the generalized Viterbi algorithm after infinitely many iterations.
This work demonstrates that a quantum trellis-coded modulation (QTCM) scheme can outperform a probabilistically equivalent classical channel (PCC) under depolarization. Simulations show that QTCM reduces the bit error rate (BER) by
15%−40% compared to PCC and degrades more slowly as the error probability p increases, with statistically significant differences and small-to-moderate effect sizes. We also estimate decoding complexity and throughput, finding that Viterbi decoding for QTCM remains comparable to classical TCM/PCC (about
1.1−1.2× runtime overhead at
L≤48 in Python prototypes). The quantum advantage is most visible in intermediate noise regimes, where entanglement and memory preserve correlations useful for decoding, and it is maintained over a broad operating range before converging to the fully mixed limit. These findings support a practical quantum advantage in communications with memory. We outline a path to NISQ validation with error mitigation and approximate decoding, and extensions to channels with realistic memory.