Linear Block Code Base Mesh Theory And Minimize The Construction Method

The theory of trellis is originated in the study of finite-state automata, in 1967 motivated by Viterbi algorithm Forney invented trellis, which then started the trellis theory research. Given a block code, there are more than one trellises to represent it, but how to find the code's best trellis is a very much important and still not thoroughly settled topic of the trellis network theory.This paper just focuses on this problem. To find the best trellis can be divided into three problems of different aspects, firstly let the time axis is fixed, in this situation two more kinds can be got:the root and toor must only consist of a single vertex respectly, just the problem of finding the minimal conventional trellis; if the vertex of root and toor can both exceed one, the problem is to find the minimal tail-biting trellis. Due to the concept of equivalent code, different trellis of the same code have quite different efficiency, then whether to find the best trellis under permutation condition is NPC becomes another famous open problem. The abstract algebra and linear algebra theory is of great use in the study of trellis.The construction theory of minimal conventional trellis is already very developed, there exists at least more than four noted construction algorithm:BCJR construction, Forney construction, Massey construction and Kschischang-Sorokine construction. But when it comes to tail-biting trellis, it becomes much more complex, in the paper how to get high-performance or effective construction of tail-biting trellis is a central question, for this generalizing the BCJR construction and Forney construction to tail-biting trellis is of great progress to trellis theory, and TB-Massey algorithm including its optimization lemma is also a not thoroughly settled fruit. Besides, the NPC theory of permutation trellis is not well figured out so far, there are still not lots of results.