zbMATH — the first resource for mathematics

On the theory of linear trellises. (English) Zbl 1073.94522
Blaum, Mario (ed.) et al., Information, coding and mathematics. Proceedings of workshop honoring Professor Bob McEliece on his 60th birthday, Pasadena, CA, USA, May 24–25, 2002. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7079-9/hbk). The Kluwer International Series in Engineering and Computer Science 687, 323-354 (2002).
Summary: Trellis linearity, first considered by McEliece in 1996, turns out to be crucial in the study of tail-biting trellises. In this chapter, basic structural properties of linear trellises are investigated. A rigorous definition of linearity is given for both conventional and tail-biting trellises. An algorithm that determines in polynomial time whether a given trellis is linear is then derived. The relationship between linear trellises and the trellis product construction is discussed. The key result of this chapter is that a trellis we prove that a trellis – either tail-biting or conventional – is linear if and only if it may be obtained by the product construction. Thus every linear trellis factors into a product of elementary trellises over a field, and every abelian-group trellis factors into elementary trellises over a group.
For the entire collection see [Zbl 1054.94001].

94B12 Combined modulation schemes (including trellis codes) in coding theory
94B05 Linear codes, general