BREADTH-1ST TRELLIS DECODING WITH ADAPTIVE EFFORT

A new breadth-first trellis decoding algorithm is introduced for application to sequence estimation in digital data transmission. The high degree of inherent parallelism makes a parallel-processing (possibly VLSI) implementation attractive. The proposed algorithm is shown to exhibit an error-rate versus average-computational-complexity behavior that is much superior to the well-known Viterbi algorithm, and which also improves on the popular M-algorithm. The decoding algorithm maintains a variable number of paths as its computation adapts to the channel noise actually encountered. Buffering of received samples is required to support this. Bounds which are evaluated by trellis search are produced for the error event rate and average number of survivors. Performance is evaluated with conventional binary convolutional codes over both BSC and AWGN channels. Performance is also found for multilevel AM and PSK codes and simple intersymbol interference responses over an AWGN channel. At lower SNR, Monte-Cario simulations are employed to improve on the bounds and to investigate decoder dynamics. © 1990 IEEE