Lin, Wei (1997) The trellis complexity of block and convolutional codes. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd01142008075936
Abstract
NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document.
This thesis concerns the computational complexity of high performance decoding algorithms. The primary objective is to design the most efficient maximumlikelihood (ML) decoders for both block codes and convolutional codes. By efficient, we mean an implementation of ML decoding algorithms on trellises that minimize the computational complexity (the total number of additions and comparisons). Trellises are graph representations of codes. Since decoding complexity is completely determined by the particular trellis employed, the problem is equivalent to constructing the minimal trellis (one that has the minimum number of edges, vertices and bifurcations) for a given code.
There are four parts to this research. The first problem we attacked was to construct the minimal trellises for block codes over the coordinate permutations. The related problem of finding a coordinate permutation that minimizes the number of vertices at a given depth in the minimal trellis for a binary linear block code [36] has been proven to be NPcomplete. Our approach was based on the concept of span of the generator matrices, which connects the code parameters and the trellis complexity. New bounds on measures of trellis complexity such as [E] (the total number of edges) and [V] (the total number of vertices) were obtained from the analysis of the span distribution. Aiming to minimize the total span in a generator matrix, an efficient, effective "divideandconquer" algorithm and variants were proposed to search for the optimal or a good trellis structure for any block code. For example, it took about 12 minutes on a Sun Sparc Station 20 to find one optimal permutation for the [48,24,12] QR code from 48! candidates.
By introducing the concept of trelliscanonical generator matrices and a simple algorithm to compute one, we developed a general theory of minimal trellises for convolutional codes. In this theory, punctured convolutional codes no longer have to be treated as special cases. By then, the minimal trellises for block and convolutional codes were both welldefined. This allowed one to make a direct performancecomplexity comparison between block codes and convolutional codes.
The ratio of performance (measured by the asymptotic coding gainACG) and complexity (measured by the logarithm trellis edge complexityLTC) defines the coding efficiency. By means of the span analysis, we also proved a universal lower bound on the complexity to performance ratio. It implies that [...] can never be smaller than 1 for any code, block or convolutional. In some cases, the bound is optimal or asymptotically optimal. The study suggests that optimal codes in terms of minimum distance or free distance do not necessarily offer the best coding efficiency.
The last problem addressed in this dissertation is the implementation of maximumlikelihood decoding and the computational complexity for convolutional codes. By combining the optimal sectionalization technique [45] with minimal trellis theory, a low complexity hybrid decoding algorithm was developed. For some partial unit memory convolutional codes, its decoding complexity is significantly superior to other known algorithms. There are two components of the computational complexity. One is the edge metric computation cost [...]. We proved a lower bound on [...] which is independent of the computation mechanism (sequential or parallel). This bound is optimal in some cases. The other is the cost of the state metric updating which is inferable from the trellis structure. This sets a lower bound on the computational complexity for any implementation.
Finally we give a general review of research activities on this subject and present a list of open problems.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Degree Grantor:  California Institute of Technology 
Major Option:  Electrical Engineering 
Thesis Committee: 

Defense Date:  26 February 1997 
Record Number:  etd01142008075936 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd01142008075936 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  171 
Collection:  CaltechTHESES 
Deposited By:  Imported from ETDdb 
Deposited On:  28 Jan 2008 
Last Modified:  25 Dec 2012 14:57 
Thesis Files
PDF (Lin_w_1997.pdf)
Restricted to Caltech community only See Usage Policy. 4Mb 
Repository Staff Only: item control page