Skip to main content

Minimal tail-biting trellises: the Golay code and more

Publication ,  Journal Article
Calderbank, AR; Forney, GD; Vardy, A
Published in: IEEE Transactions on Information Theory
January 1, 1999

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.

Duke Scholars

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

January 1, 1999

Volume

45

Issue

5

Start / End Page

1435 / 1455

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Calderbank, A. R., Forney, G. D., & Vardy, A. (1999). Minimal tail-biting trellises: the Golay code and more. IEEE Transactions on Information Theory, 45(5), 1435–1455. https://doi.org/10.1109/18.771145
Calderbank, A. R., G. D. Forney, and A. Vardy. “Minimal tail-biting trellises: the Golay code and more.” IEEE Transactions on Information Theory 45, no. 5 (January 1, 1999): 1435–55. https://doi.org/10.1109/18.771145.
Calderbank AR, Forney GD, Vardy A. Minimal tail-biting trellises: the Golay code and more. IEEE Transactions on Information Theory. 1999 Jan 1;45(5):1435–55.
Calderbank, A. R., et al. “Minimal tail-biting trellises: the Golay code and more.” IEEE Transactions on Information Theory, vol. 45, no. 5, Jan. 1999, pp. 1435–55. Scopus, doi:10.1109/18.771145.
Calderbank AR, Forney GD, Vardy A. Minimal tail-biting trellises: the Golay code and more. IEEE Transactions on Information Theory. 1999 Jan 1;45(5):1435–1455.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

January 1, 1999

Volume

45

Issue

5

Start / End Page

1435 / 1455

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing