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

D. J. Coggins*, B. S. Vucetic, D. J. Skellern

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review


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 2r 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.

Original languageEnglish
Title of host publicationIEEE 1988 International Symposium on Information Theory - Abstracts of papers
Place of PublicationNew York
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages1
Volume25 n 13
Publication statusPublished - 1988
Externally publishedYes


Dive into the research topics of 'Trellis partitioning scheme based on state relabelling for Viterbi decoding in VLSI'. Together they form a unique fingerprint.

Cite this