The problem of maximum likelihood decoding in the context of
correction of transmission errors is known to be NP-complete
in the general case . In fact, it cannot even be approximated
(within a constant factor) in polynomial time  and is
fixed-parameter hard . Because of this obvious bottleneck,
a variety of decoding schemes have been proposed to deal
with specific families of codes.
Conclusions and Future Directions
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.