BIDIRECTIONAL BREADTH-1ST ALGORITHMS FOR THE DECODING OF CONVOLUTIONAL-CODES

New bidirectional multiple-path tree searching algorithms for the deco ding of convolutional codes are presented. These suboptimal decoding a lgorithms use a multiple-path breadth-first bidirectional tree explora tion procedure and long-memory (nu > 20) convolutional codes. Compared to the usual M-algorithm, we show that the bidirectional exploration considerably reduces the bit error propagation due to correct path los s. Computer simulations using rate 1/2 codes over binary symmetric cha nnels have been used to analyze the effect of the number of path exten sions, code memory, and frame length on the bit error probability. The se results show that at P(B) = 10(-5), coding gains on the order of 2 dB can be achieved over the M-algorithm and 1 dB over a Viterbi decode r of equivalent complexity.