Taming of the BEAST

Maja Loncar

Research output: ThesisDoctoral Thesis (monograph)

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 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.
Original languageEnglish
QualificationDoctor
Awarding Institution
  • Department of Electrical and Information Technology
Supervisors/Advisors
  • Johannesson, Rolf, Supervisor
Award date2007 Oct 12
Publisher
ISBN (Print)91-7167-045-9
Publication statusPublished - 2007

Bibliographical note

Defence details

Date: 2007-10-12
Time: 10:15
Place: Room E:1406, E-building, Ole Römers väg 3, Lund University Faculty of Engineering

External reviewer(s)

Name: Costello, Daniel
Title: Professor
Affiliation: University of Notre Dame, USA

---

Subject classification (UKÄ)

  • Electrical Engineering, Electronic Engineering, Information Engineering

Free 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

Fingerprint

Dive into the research topics of 'Taming of the BEAST'. Together they form a unique fingerprint.

Cite this