Minimal tail-biting trellises: The Golay code and more

Tail-biting trellis representations of block codes are investigated. We dev elop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trell is for the (24, 12, 8) binary Golay code. This tail-biting trellis represen tation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventi onal 12-section trellis for the Golay code, which has 256 states at its mid point, or with the best quasi-cyclic representation of this code, which lea ds to a 64-state tail-biting trellis, Unwrapping this tail-biting trellis p roduces a periodically time-varying 16-state rate-1/2 "convolutional Golay code" with d = 8, which has attractive performance/complexity properties. W e furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-s tate group tail-biting trellis, even though it has no such linear trellis o ver F-4. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F-4, and the Z(4)-linear (8, 4, 4) octacode.