Trellis partitioning scheme based on state relabelling for Viterbi decoding in VLSI

Summary form only given, as follows. The concept of trellis partitioning and state relabelling which allows efficient implementation of Viterbi decoding algorithm of convolutional codes in VLSI technology is presented. In VLSI implementation the complexity is measured by the product of the chip area and the computation time. For the Viterbi algorithm the area devoted to interprocessor and interregister wiring dominates the area occupied by processors and memories. The trellis partitioning scheme is an interconnect method that reduces the interprocessor wiring. In this algorithm the original trellis of the code is partitioned into 2 ^μ-r trellises with 2^r states each. The movement of path metrics and corresponding surviving paths is confined to a particular region during r decoding cycles. State relabelling is applied every r-th decode cycle to move the paths and metrics to appropriate regions. The method is applied to rate 1/n and k/n convolutional codes as well as to trellis codes. Using the complexity measure defined as the product of area and computation time, it has been shown that significant improvement compared to the standard algorithm can be achieved.