Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Taming of the BEAST

Loncar, Maja LU (2007)
Abstract
Modern communication systems are designed to enable reliable and fast information transfer. Therefore, efficient channel coding and decoding strategies are needed, which guarantee sufficiently low probability of erroneous reception with affordable receiver complexity. For many channel codes, optimal decoding with traditional methods is prohibitively complex. The challenge therefore lies in designing reduced-complexity decoding algorithms that achieve optimal or near-optimal performance. This thesis is devoted to one such algorithm - Bidirectional Efficient Algorithm for Searching code Trees.



The taming of the BEAST is laid out in several steps. After an introduction to coding, trellis and tree representations of codes... (More)
Modern communication systems are designed to enable reliable and fast information transfer. Therefore, efficient channel coding and decoding strategies are needed, which guarantee sufficiently low probability of erroneous reception with affordable receiver complexity. For many channel codes, optimal decoding with traditional methods is prohibitively complex. The challenge therefore lies in designing reduced-complexity decoding algorithms that achieve optimal or near-optimal performance. This thesis is devoted to one such algorithm - Bidirectional Efficient Algorithm for Searching code Trees.



The taming of the BEAST is laid out in several steps. After an introduction to coding, trellis and tree representations of codes are reviewed as prerequisites for understanding the BEAST. Maximum-likelihood decoding using BEAST, and its generalization to list decoding are presented first. An investigation of geometrical aspects of list decoding has resulted in new bounds on the list error probability. It is shown that the performance of a list decoder is determined by the worst-case list configuration, which yields the minimum list distance of a code.



A commonly used approach for achieving a good performance/complexity tradeoff is to use concatenated codes with iterative decoding, where decoders of constituent codes, employed as separate entities, iteratively exchange information on decoded symbols. In such a setup, the decoders provide soft symbol reliabilities in the form of a posteriori probabilities (APPs). It is shown that accurate APP approximations can be obtained from a short list of the most probable codewords found by BEAST. This decoding method is referred to as BEAST-APP decoding. Product codes belong to the class of iteratively decodable codes and the BEAST-APP decoder is used for decoding of constituent codes, yielding good performance with low complexity. Finally, BEAST is applied as soft-input soft-output detector for transmission over intersymbol interference channels. Its advantages and limitations in comparison to existing decoding methods are discussed. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Costello, Daniel, University of Notre Dame, USA
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Technological sciences, tree search, product codes, list distance, list decoding, list-based SISO decoding, ML decoding, MAP decoding, iterative decoding, ISI equalization, BEAST, block codes, Teknik, Signal processing, Signalbehandling
pages
219 pages
publisher
Electro and information technology
defense location
Room E:1406, E-building, Ole Römers väg 3, Lund University Faculty of Engineering
defense date
2007-10-12 10:15:00
external identifiers
  • other:LUTEDX/TEIT-07/1041-SE
ISBN
91-7167-045-9
language
English
LU publication?
yes
id
d67e60cc-7d84-4e35-b0e0-543236bdd8a0 (old id 598933)
date added to LUP
2016-04-04 11:15:08
date last changed
2018-11-21 21:03:38
@phdthesis{d67e60cc-7d84-4e35-b0e0-543236bdd8a0,
  abstract     = {{Modern communication systems are designed to enable reliable and fast information transfer. Therefore, efficient channel coding and decoding strategies are needed, which guarantee sufficiently low probability of erroneous reception with affordable receiver complexity. For many channel codes, optimal decoding with traditional methods is prohibitively complex. The challenge therefore lies in designing reduced-complexity decoding algorithms that achieve optimal or near-optimal performance. This thesis is devoted to one such algorithm - Bidirectional Efficient Algorithm for Searching code Trees.<br/><br>
<br/><br>
The taming of the BEAST is laid out in several steps. After an introduction to coding, trellis and tree representations of codes are reviewed as prerequisites for understanding the BEAST. Maximum-likelihood decoding using BEAST, and its generalization to list decoding are presented first. An investigation of geometrical aspects of list decoding has resulted in new bounds on the list error probability. It is shown that the performance of a list decoder is determined by the worst-case list configuration, which yields the minimum list distance of a code.<br/><br>
<br/><br>
A commonly used approach for achieving a good performance/complexity tradeoff is to use concatenated codes with iterative decoding, where decoders of constituent codes, employed as separate entities, iteratively exchange information on decoded symbols. In such a setup, the decoders provide soft symbol reliabilities in the form of a posteriori probabilities (APPs). It is shown that accurate APP approximations can be obtained from a short list of the most probable codewords found by BEAST. This decoding method is referred to as BEAST-APP decoding. Product codes belong to the class of iteratively decodable codes and the BEAST-APP decoder is used for decoding of constituent codes, yielding good performance with low complexity. Finally, BEAST is applied as soft-input soft-output detector for transmission over intersymbol interference channels. Its advantages and limitations in comparison to existing decoding methods are discussed.}},
  author       = {{Loncar, Maja}},
  isbn         = {{91-7167-045-9}},
  keywords     = {{Technological sciences; tree search; product codes; list distance; list decoding; list-based SISO decoding; ML decoding; MAP decoding; iterative decoding; ISI equalization; BEAST; block codes; Teknik; Signal processing; Signalbehandling}},
  language     = {{eng}},
  publisher    = {{Electro and information technology}},
  school       = {{Lund University}},
  title        = {{Taming of the BEAST}},
  year         = {{2007}},
}