Date Available

5-16-2012

Year of Publication

2012

Degree Name

Doctor of Philosophy (PhD)

Document Type

Doctoral Dissertation

College

Arts and Sciences

Department/School/Program

Mathematics

First Advisor

Dr. Heide Gluesing-Luerssen

Abstract

Codes can be represented by edge-labeled directed graphs called trellises, which are used in decoding with the Viterbi algorithm. We will first examine the well-known product construction for trellises and present an algorithm for recovering the factors of a given trellis. To maximize efficiency, trellises that are minimal in a certain sense are desired. It was shown by Koetter and Vardy that one can produce all minimal tail-biting trellises for a code by looking at a special set of generators for a code. These generators along with a set of spans comprise what is called a characteristic pair, and we will discuss how to determine the number of these pairs for a given code. Finally, we will look at trellis dualization, in which a trellis for a code is used to produce a trellis representing the dual code. The first method we discuss comes naturally with the known BCJR construction. The second, introduced by Forney, is a very general procedure that works for many different types of graphs and is based on dualizing the edge set in a natural way. We call this construction the local dual, and we show the necessary conditions needed for these two different procedures to result in the same dual trellis.

Download

Included in

Mathematics Commons

Share

COinS