Sorting-based VLSI architectures for the M-algorithm and T-algorithm trellis decoders

The well-known M-algorithm and the newer T-algorithm are two closely related reduced-complexity trellis-search algorithms that can be used for data sequence estimation in digital communication systems. VLSI implementations of these algorithms are attractive due to the parallelism and simplicity of their operation. While a small number of VLSI structures have been proposed previously, this paper describes new sorting-based architectures that can be used to realize these algorithms. Specifically, schemes based on odd-even transposition, insertion, and weavesorting techniques are presented. Structures are evaluated on the basis of area, time, and power measures. Actual VLSI implementations have been used to verify timing models.<>