An Implementation of the M-algorithm using a Partially Sorting Algorithm

The M-Algorithm (MA) is a sequential sub optimum tree search algorithm with a breadth-first strategy, following M paths in the tree. It is applied in the equalization of signals disturbed by noise and inter symbol interference (ISI) and in the decoding of convolutional codes. Different to the Viterbi Algorithm, the MA requires an expensive sorting device. This pays off in systems having wide trellises and hence needing large M, e. g. multi carrier systems. An implementation of the MA for high data rates converts the algorithm's inherent parallelity into speed, which strongly increases cost. This paper presents a scalable architecture using a new sorting scheme called Extended Systolic Priority Queue (ESPQ). It is a partially sorting algorithm exploiting pre-sortedness. Its implementation is much less complex than that of completely sorting algorithms.