Trellis Decoding: From Algorithm to Flexible Architectures
(2007) In Series of licentiate and doctoral theses- Abstract
- Trellis decoding is a popular method to recover encoded information corrupted during transmission over a noisy channel. Prominent members of this class of decoding algorithms are the Viterbi algorithm, which provides maximum likelihood estimates, and the BCJR algorithm, which is a maximum a posteriori estimator commonly used in iterative decoding. In this thesis, the Viterbi algorithm is chosen since it provides a good trade-off between achievable coding gain and implementation complexity. This is the basis for considerations on simplified, hybrid, and, most importantly, flexible VLSI architectures.
Algorithm simplifications are necessary to reduce the computational burden laid
on an implementation... (More) - Trellis decoding is a popular method to recover encoded information corrupted during transmission over a noisy channel. Prominent members of this class of decoding algorithms are the Viterbi algorithm, which provides maximum likelihood estimates, and the BCJR algorithm, which is a maximum a posteriori estimator commonly used in iterative decoding. In this thesis, the Viterbi algorithm is chosen since it provides a good trade-off between achievable coding gain and implementation complexity. This is the basis for considerations on simplified, hybrid, and, most importantly, flexible VLSI architectures.
Algorithm simplifications are necessary to reduce the computational burden laid
on an implementation platform. In our work on trellis decoding blocks, a simplification that lowers the number of arithmetic operations is derived and evaluated. By using a complementary code property, the arithmetic complexity of the main part on the Viterbi algorithm is reduced by 17%. Synthesized blocks show varying savings for cell area and estimated power consumption. A comparison to a competing simplification shows the advantage in a hardware implementation of our work for the important class of rate 1/2 convolutional codes.
Hybrid architectures try to combine benefits of several approaches to lower the drawbacks of the individual contributors. For survivor path processing in Viterbi decoders, a new hybrid approach is proposed. A low-latency algorithm, whose implementation complexity quickly increases with the number of trellis states, is combined with a scalable RAM-based method. As a result, the developed hybrid architecture exhibits a better latency-complexity behavior compared to other hybrid approaches.
Flexible VLSI architectures to cover several communication standards become increasingly important as fabrication costs for microchips rise rapidly with every new process generation. In the context of flexible trellis decoding, earlier work mostly concentrated on varying encoder memory and thus the number of trellis states. This work studies the effects on hardware size and throughput introduced by flexibility if the code rate is varied. The investigation of a decoder for bandwidth-efficient codes, which was fabricated in a 0.13 um digital CMOS process and verified for functionality, distinguishes between task- and rate-flexibility. A comparison is carried out between flexible designs, which decode both convolutional and TCM codes and provide two or three transmission rates. It is concluded that the larger number of rates is more beneficial from a cost--flexibility viewpoint. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/26758
- author
- Kamuf, Matthias LU
- supervisor
-
- Viktor Öwall LU
- opponent
-
- Professor Fettweis, Gerhard, Technische Universität Dresden, Dresden, Tyskland
- organization
- publishing date
- 2007
- type
- Thesis
- publication status
- published
- subject
- keywords
- Electronics, Signalbehandling, Signal processing, VLSI, Viterbi algorithm, trellis decoding, TCM, survivor path, flexibility, convolutional codes, ACS, ASIC, Elektronik, Telecommunication engineering, Telekommunikationsteknik
- in
- Series of licentiate and doctoral theses
- pages
- 146 pages
- publisher
- Department of Electroscience, Lund University
- defense location
- E:1406, E-huset, Ole Römers väg 3, Lunds Tekniska Högskola, Lund
- defense date
- 2007-03-23 10:15:00
- ISSN
- 1402-8662
- language
- English
- LU publication?
- yes
- id
- 426d164b-edf8-44c7-b919-9b4c0ab585bb (old id 26758)
- date added to LUP
- 2016-04-01 16:16:00
- date last changed
- 2019-05-24 08:01:47
@phdthesis{426d164b-edf8-44c7-b919-9b4c0ab585bb,
abstract = {{Trellis decoding is a popular method to recover encoded information corrupted during transmission over a noisy channel. Prominent members of this class of decoding algorithms are the Viterbi algorithm, which provides maximum likelihood estimates, and the BCJR algorithm, which is a maximum a posteriori estimator commonly used in iterative decoding. In this thesis, the Viterbi algorithm is chosen since it provides a good trade-off between achievable coding gain and implementation complexity. This is the basis for considerations on simplified, hybrid, and, most importantly, flexible VLSI architectures.<br/><br>
<br/><br>
Algorithm simplifications are necessary to reduce the computational burden laid<br/><br>
<br/><br>
on an implementation platform. In our work on trellis decoding blocks, a simplification that lowers the number of arithmetic operations is derived and evaluated. By using a complementary code property, the arithmetic complexity of the main part on the Viterbi algorithm is reduced by 17%. Synthesized blocks show varying savings for cell area and estimated power consumption. A comparison to a competing simplification shows the advantage in a hardware implementation of our work for the important class of rate 1/2 convolutional codes.<br/><br>
<br/><br>
Hybrid architectures try to combine benefits of several approaches to lower the drawbacks of the individual contributors. For survivor path processing in Viterbi decoders, a new hybrid approach is proposed. A low-latency algorithm, whose implementation complexity quickly increases with the number of trellis states, is combined with a scalable RAM-based method. As a result, the developed hybrid architecture exhibits a better latency-complexity behavior compared to other hybrid approaches.<br/><br>
<br/><br>
Flexible VLSI architectures to cover several communication standards become increasingly important as fabrication costs for microchips rise rapidly with every new process generation. In the context of flexible trellis decoding, earlier work mostly concentrated on varying encoder memory and thus the number of trellis states. This work studies the effects on hardware size and throughput introduced by flexibility if the code rate is varied. The investigation of a decoder for bandwidth-efficient codes, which was fabricated in a 0.13 um digital CMOS process and verified for functionality, distinguishes between task- and rate-flexibility. A comparison is carried out between flexible designs, which decode both convolutional and TCM codes and provide two or three transmission rates. It is concluded that the larger number of rates is more beneficial from a cost--flexibility viewpoint.}},
author = {{Kamuf, Matthias}},
issn = {{1402-8662}},
keywords = {{Electronics; Signalbehandling; Signal processing; VLSI; Viterbi algorithm; trellis decoding; TCM; survivor path; flexibility; convolutional codes; ACS; ASIC; Elektronik; Telecommunication engineering; Telekommunikationsteknik}},
language = {{eng}},
publisher = {{Department of Electroscience, Lund University}},
school = {{Lund University}},
series = {{Series of licentiate and doctoral theses}},
title = {{Trellis Decoding: From Algorithm to Flexible Architectures}},
year = {{2007}},
}