The trellis complexity of block and convolutional codes

Citation

Lin, Wei (1997) The trellis complexity of block and convolutional codes. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/5130-4858. https://resolver.caltech.edu/CaltechETD:etd-01142008-075936

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 maximum-likelihood (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 NP-complete. 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 "divide-and-conquer" 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 trellis-canonical 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 well-defined. This allowed one to make a direct performance-complexity comparison between block codes and convolutional codes. The ratio of performance (measured by the asymptotic coding gain-ACG) and complexity (measured by the logarithm trellis edge complexity-LTC) 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 maximum-likelihood 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.

Thesis Files