Bidirectional breadth-first algorithms for the decoding ofconvolutional codes

Bidirectional multiple-path tree searching algorithms for the decoding of convolutional codes are presented. These suboptimal coding algorithms use a multiple-path breadth-first bidirectional tree exploration procedure and long-memory convolution codes. It is shown that, compared to the usual M-algorithm, the bidirectional exploration considerably reduces the bit error propagation due to correct path loss. Computer simulations using rate-1/2 codes over binary symmetric channels are used to analyze the effect of the number of path extensions, code memory, and frame length on the bit error probability. The results show that with a bit error probability of 10^-5, coding gains on the order of 2 dB over the M-algorithm and 1 dB over a Viterbi decoder of equivalent complexity can be achieved