A maximum likelihood decoding algorithm for turbo codes

A maximum likelihood (ML) decoding algorithm is presented for decoding turbo codes. The basic algorithm, called the pair list algorithm (PLA) is a stack algorithm that examines pairs of constituent code trellis paths in order of decreasing metric sum. The PLA controls two per trellis list Viterbi algorithms (LVA) for finding the n highest metric paths in a trellis diagram. For practical implementation the ML search must be terminated. This search truncation may limit the utility of this algorithm to epsilon(b)/N-0 for which the cutoff rate R-0 exceed the code rate. However, the terminated ML search can be used to generate FER statistics, or for a FEC/ARQ turbo code scheme without using an additional error detecting outer code.