VLSI Architecture for the M Algorithm Suited for Detection and Source Coding Applications

Trellis source coders consists of a trellis search algorithm as the encoder and a finite state machine as the decoder. The search algorithm finds the best sequence of codewords in the trellis representing the source sequence. The optimum trellis search is the Viterbi algorithm (VA). However, for source coding applications, it becomes prohibitively complex. Hence, suboptimum search algorithms must be considered. The M algorithm is a suboptimum search whose performance is close to the optimum system. This algorithm retains the best M paths at every instant. Conventional architectures of this algorithm are impractical when the number of retained paths is large. In this paper, new hardware architectures based on VA implementations are presented. Dividing the M algorithm into path metric updating and trace-back based survivor memory management procedures, efficient architectures can be achieved contributing to a significant reduction in the hardware complexity, which allows quantization systems with larger reproduction codebooks.