Traditionally, the algebraic decoding algorithm is used as the decoding algorithm for linear block codes, and the Viterbi algorithm (VA) is used as the maximum likelihood decoding algorithm for convolutional codes. Theoretically, by representing linear block codes in trellis form, the VA can also be used to decode linear block codes. A major advantage of the VA above traditional block decoders is the existence of efficient soft decision algorithms employing channel measurement information. However, the computational complexity of the VA exists a strong dependence on code constraint length. In most applications, this makes the decoder implementation practically unfeasible. In this paper, the VA for hard-decision and soft-decision decoding of linear block codes is studied from a computational complexity viewpoint. We introduce a concept of distance threshold which establishes a trade-off between error rate performance and decoding complexity. Using this concept, a reduced-complexity Viterbi algorithm (RCVA) is developed. The RCVA explores a drastically reduced trellis and requires either few or no metric comparisons at all. A computer simulation using the (23, 12) Golay code over an AWGN channel illustrates that the error rate performance achieved by the RCVA is essentially the same as that of a maximum likelihood decoder.
