Main | Browse | Search | Author Links | Manage ETD List | Review ETDs | Catalog ETDs | Help

Title page for ETD etd-05202008-063919

Type of Document Dissertation
Author Sikora, Marcin
URN etd-05202008-063919
Title Reduced-Complexity Algorithms for Decoding and Equalization
Degree Doctor of Philosophy
Department Electrical Engineering
Advisory Committee
Advisor Name Title
Daniel J. Costello, Jr. Committee Chair
  • decoding
  • equalization
  • tree search
Date of Defense 2008-04-07
Availability unrestricted
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 guide the search procedure, reducing the average number of visited incorrect nodes. For soft-output decoding and equalization, a new approach to the generation of soft output within the M-algorithm-based search is presented. Both techniques, when applied simultaneously, yield a particularly efficient soft output decoder for large-memory convolutional codes. Finally, a short block code is presented, which repeated and concatenated with strong outer convolutional code yields 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.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  SikoraM052008.pdf 1.23 Mb 00:05:41 00:02:55 00:02:33 00:01:16 00:00:06

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact the Graduate School.