The structure of tail-biting trellises: minimality and basic principles

Basic structural properties of tail-biting trellises are investigated. We start with rigorous definitions of various types of minimality for tail-biting trellises. We then show that biproper and/or nonmergeable tail-biting trellises are not necessarily minimal, even though every minimal tail-biting trellis is biproper. Next, we introduce the notion of linear (or group) trellises and prove, by example, that a minimal tail-biting trellis for a binary linear code need not have any linearity properties whatsoever. We observe that a trellis - either tail-biting or conventional - is linear if and only if it factors into a product of elementary trellises. Using this result, we show how to construct, for any given linear code C, a tail-biting trellis that minimizes the product of state-space sizes among all possible linear tail-biting trellises. We also prove that every minimal linear tail-biting trellis for C arises from a certain n×n characteristic matrix, and show how to compute this matrix in time O(n²) from any basis for C. Furthermore, we devise a linear-programming algorithm that starts with the characteristic matrix and produces a linear tail-biting trellis for C; which minimizes the maximum state-space size. Finally, we consider a generalized product construction for tail-biting trellises, and use it to prove that a linear code C and its dual C^⊥C^⊥C^⊥C^⊥ have the same state-complexity profiles.