Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#236067] of Robert Calderbank

Papers Published

  1. Calderbank, AR; Jr, GDF; Vardy, A, Minimal tail-biting trellises: the Golay code and more, Ieee Transactions on Information Theory, vol. 45 no. 5 (1999), pp. 1435-1455, ISSN 0018-9448 [doi]
    (last updated on 2018/10/22)

    Tail-biting 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 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state 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 8-state group tail-biting trellis, even though it has no such linear trellis over 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320