Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Minimal tail-biting trellises: the Golay code and more

A.B. Calderbank, G. David Forney, Alexander Vardy

Published Nov 27, 2002• 12 citations
Publisher

Abstract

A 16-state tail-biting trellis for the binary (24,12,8) Golay code C/sub 24/ is exhibited. This tail-biting trellis is minimal. It has many other nice properties, and may be simpler to decode than the minimal conventional trellis for C/sub 24/. Unwrapping this tail-biting trellis produces a periodically-time-varying 16-state rate- 1/2 convolutional code. This "Golay convolutional code" is the first known example of a self-dual doubly-even binary linear convolutional code. It has greater minimum distance than any 16-state time-invariant convolutional code of rate 1/2 . Demonstrably minimal tail-biting trellises are given for several other binary and nonbinary self-dual codes. For some nonbinary codes, tail-biting trellises based on code generators over a group are simpler than any tail-biting trellis based on linear generators over a field.

DOI
10.1109/isit.1998.708860

Related papers

Low Complexity Tail-Biting Trellises for Some Extremal Self-Dual Codes

Grégory Olocco, Ayoub Otmani

We obtain low complexity tail-biting trellises for some extremal self-dual codes for various lengths and fields such as the [12,6,6] ternary Golay code and a [24,12,8] Hermitian self-dual code over GF(4). These codes are obtained from a particular family of cyclic Tanner graphs called necklace factor graphs.

•Sep 8, 2002•0 citations

A Multivariate Weight Enumerator for Tail-biting Trellis Pseudocodewords

Nigel Boston

Tail-biting-trellis representations of codes allow for iterative decoding algorithms, which are limited in effectiveness by the presence of pseudocodewords. We introduce a multivariate weight enumerator that keeps track of these pseudocodewords. This enumerator is invariant under many linear transformations, often enabling us to compute it exactly. The extended binary Golay code has a particularly nice tail-biting-trellis and a famous unsolved question is to determine its minimal AWGN pseudodistance. The new enumerator provides an inroad to this problem.

Journal of Generalized Lie Theory and Applications•Jan 1, 2015•7 citations

Convolutional and Tail-Biting Quantum Error-Correcting Codes

G. David Forney, Markus Grassl, Saikat Guha

Rate-(n-2)/n unrestricted and CSS-type quantum convolutional codes with up to 4096 states and minimum distances up to 10 are constructed as stabilizer codes from classical self-orthogonal rate-1/n F4-linear and binary linear convolutional codes, respectively. These codes generally have higher rate and less decoding complexity than comparable quantum block codes or previous quantum convolutional codes. Rate-(n-2)/n block stabilizer codes with the same rate and error-correction capability and essentially the same decoding complexity are derived from these convolutional codes via tail-biting

arXiv:quant-ph/0511016•IEEE Transactions on Information Theory•Mar 1, 2007•103 citations

Low Complexity Tail-Biting Trellises of Self-dual codes of Length 24, 32 and 40 over GF(2) and Z4 of Large Minimum Distance

Emmanuel Cadic, Jean-Claude Carlach, Grégory Olocco +2 more

Lecture notes in computer science•Jan 1, 2001•3 citations

The Improvement of TB-MASSEY Trellis Algorithm for Linear Codes

Zhiliang Zhu, Songtao Liang

The well-known Forney algorithm, Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm and product construction for minimal linear conventional trellises have all successfully extended to tail-biting trellises. As first author of this paper, one of my paper, in a way, popularized Massey construction of minimal linear conventional trellises to tail-biting trellises, just referred as TB-Massey trellises. In this paper, we make some necessary and important optimization and improvement of TB-Massey trellises, mainly via elaborately constricting vertexes of the trellis graph as far as possible. Then display performance of all kinds of the extended tail-biting trellises by comparison. Though having not found the thorough generalized tail-biting Massey trellises, we get some positive progress and results

International Conference on Wireless Communications, Networking and Mobile Computing•Sep 1, 2011•0 citations

Characteristic Generators and Dualization for Tail-Biting Trellises

Heide Gluesing-Luerssen, Elizabeth A. Weaver

This paper focuses on dualizing tail-biting trellises, particularly KV trellises. These trellises are based on characteristic generators, as introduced by Koetter-Vardy (2003), and may be regarded as a natural generalization of minimal conventional trellises, even though they are not necessarily minimal. Two dualization techniques will be investigated: the local dualization, introduced by Forney (2001) for general normal graphs, and a linear-algebra-based dualization tailored to the specific class of tail-biting Bahl-Cocke-Jelinek-Raviv (BCJR) trellises, introduced by Nori-Shankar (2006). It turns out that, in general, the BCJR dual is a subtrellis of the local dual, while for KV trellises these two coincide. Furthermore, making use of both the BCJR construction and the local dualization, it will be shown that for each complete set of characteristic generators of a code there exists a complete set of characteristic generators of the dual code such that their resulting KV trellises are dual to each other if paired suitably. This proves a stronger version of a conjecture formulated by Koetter-Vardy.

IEEE Transactions on Information Theory•Aug 3, 2011•17 citations
A 16-state tail-biting trellis for the binary (24,12,8) Golay code C/sub 24/ is exhibited. This tail-biting trellis is minimal. It has many other nice properties, and may be simpler to decode than the minimal conventional trellis for C/sub 24/. Unwrapping this tail-biting trellis produces a periodically-time-varying 16-state rate- 1/2 convolutional code. This "Golay convolutional code" is the first known example of a self-dual doubly-even binary linear convolutional code. It has greater minimum distance than any 16-state time-invariant convolutional code of rate 1/2 . Demonstrably minimal tail-biting trellises are given for several other binary and nonbinary self-dual codes. For some nonbinary codes, tail-biting trellises based on code generators over a group are simpler than any tail-biting trellis based on linear generators over a field.
Tail-biting-trellis representations of codes allow for iterative decoding algorithms, which are limited in effectiveness by the presence of pseudocodewords. We introduce a multivariate weight enumerator that keeps track of these pseudocodewords. This enumerator is invariant under many linear transformations, often enabling us to compute it exactly. The extended binary Golay code has a particularly nice tail-biting-trellis and a famous unsolved question is to determine its minimal AWGN pseudodistance. The new enumerator provides an inroad to this problem.
Rate-(n-2)/n unrestricted and CSS-type quantum convolutional codes with up to 4096 states and minimum distances up to 10 are constructed as stabilizer codes from classical self-orthogonal rate-1/n F4-linear and binary linear convolutional codes, respectively. These codes generally have higher rate and less decoding complexity than comparable quantum block codes or previous quantum convolutional codes. Rate-(n-2)/n block stabilizer codes with the same rate and error-correction capability and essentially the same decoding complexity are derived from these convolutional codes via tail-biting
The well-known Forney algorithm, Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm and product construction for minimal linear conventional trellises have all successfully extended to tail-biting trellises. As first author of this paper, one of my paper, in a way, popularized Massey construction of minimal linear conventional trellises to tail-biting trellises, just referred as TB-Massey trellises. In this paper, we make some necessary and important optimization and improvement of TB-Massey trellises, mainly via elaborately constricting vertexes of the trellis graph as far as possible. Then display performance of all kinds of the extended tail-biting trellises by comparison. Though having not found the thorough generalized tail-biting Massey trellises, we get some positive progress and results
This paper focuses on dualizing tail-biting trellises, particularly KV trellises. These trellises are based on characteristic generators, as introduced by Koetter-Vardy (2003), and may be regarded as a natural generalization of minimal conventional trellises, even though they are not necessarily minimal. Two dualization techniques will be investigated: the local dualization, introduced by Forney (2001) for general normal graphs, and a linear-algebra-based dualization tailored to the specific class of tail-biting Bahl-Cocke-Jelinek-Raviv (BCJR) trellises, introduced by Nori-Shankar (2006). It turns out that, in general, the BCJR dual is a subtrellis of the local dual, while for KV trellises these two coincide. Furthermore, making use of both the BCJR construction and the local dualization, it will be shown that for each complete set of characteristic generators of a code there exists a complete set of characteristic generators of the dual code such that their resulting KV trellises are dual to each other if paired suitably. This proves a stronger version of a conjecture formulated by Koetter-Vardy.