A new bidirectional algorithm for decoding trellis codes

A new parallel procedure for decoding trellis codes with a large constraint length is simulated and compared to the bidirectional stack algorithm. The systolic organization of processing units arranged in two mutually connected arrays enables the decoding effort to be unaffected by single correctable bursts of errors whose branch length is not greater than some /spl tau/, where /spl tau/ is not greater than the code memory length. During the course of decoding, the algorithm produces a set of tentative decisions of increasing reliability, until it reaches the final decision. Every tentative decision is composed of a portion of a forward and backward path, connected via a tunnel of length /spl tau/. After each new tentative decision is made, a new set of discarding criteria is produced. According to these criteria, a vast number of partially explored paths is discarded from all the stacks, speeding up the decoding procedure. The results show a significant reduction in decoding effort (measured by the number of extended paths in parallel) compared to known sequential procedures.