Reduced-Complexity Algorithms for Decoding and Equalization

ETD
Add to Collection

Abstract

Finite state machines (FSMs) and detection problems involving them are frequently encountered in digital communication systems for noisy channels. One type of FSM arises naturally in transmission over band-limited frequency-selective channels, when bits are modulated onto complex symbols using memoryless mapper and passed through a finite impulse response (FIR) filter. Another type of FSMs, mapping sequences of information bits into longer sequences of coded bits, are the convolutional codes. The detection problem for FSMs, termed decoding in the context of convolutional codes and equalization for frequency-selective channels, involve either finding the most likely input sequence given noisy observations of the output sequence (hard-output decoding), or determining a posteriori probabilty of individual information bits (soft-output decoding). These problems are commonly solved either running a search algorithm on the tree representation of all FSM sequences or by means of dynamic programming on the trellis representation of the FSM.

This work presents novel approaches to decoding and equalization based on tree search.For decoding of convolutional codes, two novel supercode heuristics are proposed to guidethe search procedure, reducing the average number of visited incorrect nodes.For soft-output decoding and equalization, a new approach to the generation of soft outputwithin the M-algorithm-based search is presented.Both techniques, when applied simultaneously, yield a particularly efficient soft output decoderfor large-memory convolutional codes.Finally, a short block code is presented, which repeated and concatenated with strong outer convolutional codeyields an iteratively-decodable coding scheme with excellent convergence and minimum distance properties.With the help of the proposed soft output decoder for the outer convolutional code,this concatenation has also low decoding complexity.

Attributes

Attribute NameValues
URN
  • etd-05202008-063919

Author Marcin Sikora
Advisor Daniel J. Costello, Jr.
Contributor Daniel J. Costello, Jr., Committee Chair
Degree Level 2
Degree Discipline Electrical Engineering
Degree Name Doctor of Philosophy
Defense Date
  • 2008-04-07

Submission Date 2008-05-20
Country
  • United States of America

Subject
  • decoding

  • equalization

  • tree search

Publisher
  • University of Notre Dame

Language
  • English

Access Rights Open Access
Content License
  • All rights reserved

Files