Trellis Nature Of The Linear Code

This thesis generally discusses the property of trellises for linear codes. Minimal trellises for two classes of linear codes, i.e., cyclic codes and quasi-cyclic codes are discussed. Furthermore, the relationships between some trellises of linear codes are also investigated.Trellis of codes often provides an efficient way for decoding in communication systems. It also plays an important role in coding and information theory. The Viterbi algorithm is widely used for efficient trellis-based decoding. Because the complexity of Viterbi algorithm is affected by the complexity of trellis graph, the basic problem of trellis theory is how to construct the simplest trellis, i.e., minimal trellis.There are two kinds of trellises, i.e., conventional trellises and tail-biting trellises. Minimal conventional trellises for linear codes can be constructed from their generation matrices or parity check matrices. Although constructing minimal conventional trellises for linear codes has already been settled well, much less is known about tail-biting trellises. Therefore, how to construct minimal tail-biting trellises becomes the major problem in trellis theory. Recently, Kotter and Vardy discussed the general theory on tail-biting trellises and provide a method to construct minimal tail-biting trellises using product codes. In this thesis, constructing minimal tail-biting trellises for two classes of linear codes, i.e., cyclic codes and quasi-cyclic codes is discussed.In coding theory, a new code can be constructed from some original codes. It is found that a close relationship exists between a new code and the original codes. Similarly, the trellis of a new code is also closely related to the trellises of the original codes. The properties of the relationship between these trellises are also discussed. Overall, some breakthroughs have been made in past few years, however, there are still many problems unsettled, which will be left for future work.