#### Year of Publication

2012

#### Degree Name

Doctor of Philosophy (PhD)

#### Document Type

Doctoral Dissertation

#### College

Arts and Sciences

#### Department

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.

#### Recommended Citation

Weaver, Elizabeth A., "MINIMALITY AND DUALITY OF TAIL-BITING TRELLISES FOR LINEAR CODES" (2012). *Theses and Dissertations--Mathematics*. 1.

https://uknowledge.uky.edu/math_etds/1