Low-latency low-complexity architectures for viterbi decoders

Renfei Liu; Keshab K. Parhi

doi:10.1109/TCSI.2008.2012217

Low-latency low-complexity architectures for viterbi decoders

Renfei Liu, Keshab K. Parhi

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

Look-ahead techniques are applied in the nonlinear add-compare-select unit for achieving high throughput in Viterbi decoders. Multiple steps of the binary trellis are combined into an equivalent one-step complex trellis in time sequence, which is referred to as the branch metric precomputation (BMP). As the look-ahead level increases, the BMP dominates the complexity and delay of the overall system architecture. This paper systematically proposes an optimal branch metric computation scheme with the minimal complexity and latency. The proof of its optimality is also given. This highly efficient scheme leads to a novel overall optimal BMP architecture for any look-ahead level. Furthermore, an alternative technique other than the look-ahead is proposed for reducing the latency at very low complexity cost. This alternative technique can be either applied in combination with the proposed architecture to achieve the lowest latency at a slight increase in complexity or used on its own for low complexity compared with other look-ahead-based architectures. Results show that the three proposed architectures can either reduce complexity by up to 84% or reduce the latency by up to 72.50%.

Original language	English (US)
Article number	4738418
Pages (from-to)	2315-2324
Number of pages	10
Journal	IEEE Transactions on Circuits and Systems I: Regular Papers
Volume	56
Issue number	10
DOIs	https://doi.org/10.1109/TCSI.2008.2012217
State	Published - 2009

Bibliographical note

Funding Information:
Dr. Parhi was the recipient of numerous awards including the 2004 F. E. Terman Award by the American Society of Engineering Education, the 2003 IEEE Kiyo Tomiyasu Technical Field Award, the 2001 IEEE W. R. G. Baker Prize Paper Award, and a Golden Jubilee Award from the IEEE Circuits and Systems Society in 1999. He has served on the Editorial Boards of the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS and the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—II: EXPRESS BRIEFS, the IEEE TRANSACTIONS ON VERY LARGE-SCALE INTEGRATED (VLSI) SYSTEMS, the IEEE TRANSACTIONS ON SIGNAL PROCESSING, the IEEE SIGNAL PROCESSING LETTERS, and IEEE Signal Processing Magazine. He has served as the Editor-in-Chief of the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS from 2004 to 2005. He has served as Technical Program Cochair of the 1995 IEEE VLSI Signal Processing Workshop and the 1996 Application-Specific Systems, Architectures and Processors (ASAP) Conference and as the General Chair of the 2002 IEEE Workshop on Signal Processing Systems. He was a Distinguished Lecturer for the IEEE Circuits and Systems Society during 1996–1998.

Keywords

Balanced binary grouping (bbg)
Look-ahead technique
Low latency
Precomputation
Trellis
Viterbi decoder

Publisher link

10.1109/TCSI.2008.2012217

Find It

Find It at U of M Libraries

Cite this

@article{0db4ec1e608f4a9eb7c6abc0ebcb7e36,

title = "Low-latency low-complexity architectures for viterbi decoders",

abstract = "Look-ahead techniques are applied in the nonlinear add-compare-select unit for achieving high throughput in Viterbi decoders. Multiple steps of the binary trellis are combined into an equivalent one-step complex trellis in time sequence, which is referred to as the branch metric precomputation (BMP). As the look-ahead level increases, the BMP dominates the complexity and delay of the overall system architecture. This paper systematically proposes an optimal branch metric computation scheme with the minimal complexity and latency. The proof of its optimality is also given. This highly efficient scheme leads to a novel overall optimal BMP architecture for any look-ahead level. Furthermore, an alternative technique other than the look-ahead is proposed for reducing the latency at very low complexity cost. This alternative technique can be either applied in combination with the proposed architecture to achieve the lowest latency at a slight increase in complexity or used on its own for low complexity compared with other look-ahead-based architectures. Results show that the three proposed architectures can either reduce complexity by up to 84% or reduce the latency by up to 72.50%.",

keywords = "Balanced binary grouping (bbg), Look-ahead technique, Low latency, Precomputation, Trellis, Viterbi decoder",

author = "Renfei Liu and Parhi, {Keshab K.}",

note = "Funding Information: Dr. Parhi was the recipient of numerous awards including the 2004 F. E. Terman Award by the American Society of Engineering Education, the 2003 IEEE Kiyo Tomiyasu Technical Field Award, the 2001 IEEE W. R. G. Baker Prize Paper Award, and a Golden Jubilee Award from the IEEE Circuits and Systems Society in 1999. He has served on the Editorial Boards of the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS and the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—II: EXPRESS BRIEFS, the IEEE TRANSACTIONS ON VERY LARGE-SCALE INTEGRATED (VLSI) SYSTEMS, the IEEE TRANSACTIONS ON SIGNAL PROCESSING, the IEEE SIGNAL PROCESSING LETTERS, and IEEE Signal Processing Magazine. He has served as the Editor-in-Chief of the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS from 2004 to 2005. He has served as Technical Program Cochair of the 1995 IEEE VLSI Signal Processing Workshop and the 1996 Application-Specific Systems, Architectures and Processors (ASAP) Conference and as the General Chair of the 2002 IEEE Workshop on Signal Processing Systems. He was a Distinguished Lecturer for the IEEE Circuits and Systems Society during 1996–1998.",

year = "2009",

doi = "10.1109/TCSI.2008.2012217",

language = "English (US)",

volume = "56",

pages = "2315--2324",

journal = "IEEE Transactions on Circuits and Systems I: Regular Papers",

issn = "1549-8328",

number = "10",

}

TY - JOUR

T1 - Low-latency low-complexity architectures for viterbi decoders

AU - Liu, Renfei

AU - Parhi, Keshab K.

N1 - Funding Information: Dr. Parhi was the recipient of numerous awards including the 2004 F. E. Terman Award by the American Society of Engineering Education, the 2003 IEEE Kiyo Tomiyasu Technical Field Award, the 2001 IEEE W. R. G. Baker Prize Paper Award, and a Golden Jubilee Award from the IEEE Circuits and Systems Society in 1999. He has served on the Editorial Boards of the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS and the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—II: EXPRESS BRIEFS, the IEEE TRANSACTIONS ON VERY LARGE-SCALE INTEGRATED (VLSI) SYSTEMS, the IEEE TRANSACTIONS ON SIGNAL PROCESSING, the IEEE SIGNAL PROCESSING LETTERS, and IEEE Signal Processing Magazine. He has served as the Editor-in-Chief of the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS from 2004 to 2005. He has served as Technical Program Cochair of the 1995 IEEE VLSI Signal Processing Workshop and the 1996 Application-Specific Systems, Architectures and Processors (ASAP) Conference and as the General Chair of the 2002 IEEE Workshop on Signal Processing Systems. He was a Distinguished Lecturer for the IEEE Circuits and Systems Society during 1996–1998.

PY - 2009

Y1 - 2009

N2 - Look-ahead techniques are applied in the nonlinear add-compare-select unit for achieving high throughput in Viterbi decoders. Multiple steps of the binary trellis are combined into an equivalent one-step complex trellis in time sequence, which is referred to as the branch metric precomputation (BMP). As the look-ahead level increases, the BMP dominates the complexity and delay of the overall system architecture. This paper systematically proposes an optimal branch metric computation scheme with the minimal complexity and latency. The proof of its optimality is also given. This highly efficient scheme leads to a novel overall optimal BMP architecture for any look-ahead level. Furthermore, an alternative technique other than the look-ahead is proposed for reducing the latency at very low complexity cost. This alternative technique can be either applied in combination with the proposed architecture to achieve the lowest latency at a slight increase in complexity or used on its own for low complexity compared with other look-ahead-based architectures. Results show that the three proposed architectures can either reduce complexity by up to 84% or reduce the latency by up to 72.50%.

AB - Look-ahead techniques are applied in the nonlinear add-compare-select unit for achieving high throughput in Viterbi decoders. Multiple steps of the binary trellis are combined into an equivalent one-step complex trellis in time sequence, which is referred to as the branch metric precomputation (BMP). As the look-ahead level increases, the BMP dominates the complexity and delay of the overall system architecture. This paper systematically proposes an optimal branch metric computation scheme with the minimal complexity and latency. The proof of its optimality is also given. This highly efficient scheme leads to a novel overall optimal BMP architecture for any look-ahead level. Furthermore, an alternative technique other than the look-ahead is proposed for reducing the latency at very low complexity cost. This alternative technique can be either applied in combination with the proposed architecture to achieve the lowest latency at a slight increase in complexity or used on its own for low complexity compared with other look-ahead-based architectures. Results show that the three proposed architectures can either reduce complexity by up to 84% or reduce the latency by up to 72.50%.

KW - Balanced binary grouping (bbg)

KW - Look-ahead technique

KW - Low latency

KW - Precomputation

KW - Trellis

KW - Viterbi decoder

UR - http://www.scopus.com/inward/record.url?scp=75149142177&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=75149142177&partnerID=8YFLogxK

U2 - 10.1109/TCSI.2008.2012217

DO - 10.1109/TCSI.2008.2012217

M3 - Article

AN - SCOPUS:75149142177

SN - 1549-8328

VL - 56

SP - 2315

EP - 2324

JO - IEEE Transactions on Circuits and Systems I: Regular Papers

JF - IEEE Transactions on Circuits and Systems I: Regular Papers

IS - 10

M1 - 4738418

ER -

Low-latency low-complexity architectures for viterbi decoders

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this