Abstract:

Most known decoding procedures for error-correcting codes have been based either on algebraically calculating the error pattern or on some sort of tree or trellis search. With the advent of turbo coding (Berrou et al., 1993), a third decoding principle is introduced: iterative decoding. With respect to Viterbi decoding, a code is most naturally described via a trellis diagram. In this paper, and with respect to iterative decoding, the code is described via a Tanner graph (Tanner, 1991), which is viewed as a generalized trellis. In particular, it is the 'time axis' of a trellis that is generalized to a Tanner graph. It is shown that the trellises yield Tanner graphs that have no cycles. The complexity reduction in turbo codes is shown to come from allowing Tanner graphs with cycles.