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.
| Identifer | oai:union.ndltd.org:uky.edu/oai:uknowledge.uky.edu:math_etds-1000 |
| Date | 01 January 2012 |
| Creators | Weaver, Elizabeth A. |
| Publisher | UKnowledge |
| Source Sets | University of Kentucky |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations--Mathematics |
Page generated in 0.0013 seconds