Conclusions and Future Directions

The problem of maximum likelihood decoding in the context of correction of transmission errors is known to be NP-complete in the general case [5]. In fact, it cannot even be approximated (within a constant factor) in polynomial time [54] and is fixed-parameter hard [16]. Because of this obvious bottleneck, a variety of decoding schemes have been proposed to deal with specific families of codes.

We have considered two popular decoding paradigms in this work: Viterbi decoding on time-indexed trellises and iterative decoding on factor graphs. In the former case we have presented a method for designing families of good error-correcting codes that satisfy specific decoding constraints, and in the latter case we have shown that current theoretical knowledge about the convergence of iterative decoding does not apply directly to asymptotically good codes.