Math @ Duke

Publications [#236067] of Robert Calderbank
Papers Published
 Calderbank, AR; Jr, GDF; Vardy, A, Minimal tailbiting trellises: the Golay code and more,
IEEE Transactions on Information Theory, vol. 45 no. 5
(1999),
pp. 14351455, ISSN 00189448 [doi]
(last updated on 2018/07/21)
Abstract: Tailbiting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16state 12section structurally invariant tailbiting trellis for the (24, 12, 8) binary Golay code. This tailbiting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasicyclic representation of this code, which leads to a 64state tailbiting trellis. Unwrapping this tailbiting trellis produces a periodically timevarying 16state rate 1/2 'convolutional Golay code' with d = 8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quarternary hexacode has a minimal 8state group tailbiting trellis, even though it has no such linear trellis over F 4. Minimal tailbiting 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 4linear (8, 4, 4) octacode.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

