An iterative trellis search technique is described for the maximum-likelihood (ML) soft decision decoding of block codes. The proposed technique derives its motivation from the fact that a given block code may be a subcode for a parent code whose associated trellis has substantially fewer edges. Through the use of list-Viterbi (1967) decoding and an iterative algorithm, the proposed technique allows for the use of a trellis for the parent code in the ML decoding of the desired subcode. Complexity and performance analyses, as well as details of potential implementations, indicate a substantial reduction in decoding complexity for linear block codes of practical length while achieving ML or near-ML soft decision performance.

A methodology is presented for the design and development of efficient trellis-based soft decision decoders for extended Hamming and BCH codes. A new metric for noncoherent discriminator detection is proposed that substantially improves the performance of trellis-based decoders over additive white Gaussian noise (AWGN) channels. Minimal edge trellises are then presented for the class of extended Hamming codes and the (32, 21) extended BCH code. The latter is in extensive use in narrow-band wireless data systems. An automatic request (ARQ) protocol is described that allows the soft decision decoders to outperform their hard decision counterparts in both reliability and throughput.