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

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

Grégory Olocco, Ayoub Otmani

Published Sep 8, 2002• 0 citations
OpenAlex

Abstract

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.

Related papers

Minimal tail-biting trellises: the Golay code and more

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

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.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•12 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

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 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.

arXiv:1101.3929•Jan 20, 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

On the classification of Hermitian self-dual additive codes over GF(9)

Lars Eirik Danielsen

Additive codes over GF(9) that are self-dual with respect to the Hermitian trace inner product have a natural application in quantum information theory, where they correspond to ternary quantum error-correcting codes. However, these codes have so far received far less interest from coding theorists than self-dual additive codes over GF(4), which correspond to binary quantum codes. Self-dual additive codes over GF(9) have been classified up to length 8, and in this paper we extend the complete classification to codes of length 9 and 10. The classification is obtained by using a new algorithm that combines two graph representations of self-dual additive codes. The search space is first reduced by the fact that every code can be mapped to a weighted graph, and a different graph is then introduced that transforms the problem of code equivalence into a problem of graph isomorphism. By an extension technique, we are able to classify all optimal codes of length 11 and 12. There are 56,005,876 (11,3^11,5) codes and 6493 (12,3^12,6) codes. We also find the smallest codes with trivial automorphism group.

arXiv:1106.2428•Jun 13, 2011•0 citations

Some new Results for Additive Self-Dual Codes over GF(4)

Zlatko Varbanov

Additive code C over GF(4) of length n is an additive subgroup of GF(4)n. It is well known [4] that the problem of finding stabilizer quantum error-correcting codes is transformed into problem of finding additive self-orthogonal codes over the Galois field GF(4) under a trace inner product. Our purpose is to construct good additive self-dual codes of length 13 ≤ n ≤ 21. In this paper we classify all extremal (optimal) codes of lengths 13 and 14, and we construct many extremal codes of lengths 15 and 16. Also, we construct some new extremal codes of lengths 17,18,19, and 21. We give the current status of known extremal (optimal) additive self-dual codes of lengths 13 to 21.

Serdica Journal of Computing•Jul 4, 2007•11 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.
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 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.
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.
Additive codes over GF(9) that are self-dual with respect to the Hermitian trace inner product have a natural application in quantum information theory, where they correspond to ternary quantum error-correcting codes. However, these codes have so far received far less interest from coding theorists than self-dual additive codes over GF(4), which correspond to binary quantum codes. Self-dual additive codes over GF(9) have been classified up to length 8, and in this paper we extend the complete classification to codes of length 9 and 10. The classification is obtained by using a new algorithm that combines two graph representations of self-dual additive codes. The search space is first reduced by the fact that every code can be mapped to a weighted graph, and a different graph is then introduced that transforms the problem of code equivalence into a problem of graph isomorphism. By an extension technique, we are able to classify all optimal codes of length 11 and 12. There are 56,005,876 (11,3^11,5) codes and 6493 (12,3^12,6) codes. We also find the smallest codes with trivial automorphism group.
Additive code C over GF(4) of length n is an additive subgroup of GF(4)n. It is well known [4] that the problem of finding stabilizer quantum error-correcting codes is transformed into problem of finding additive self-orthogonal codes over the Galois field GF(4) under a trace inner product. Our purpose is to construct good additive self-dual codes of length 13 ≤ n ≤ 21. In this paper we classify all extremal (optimal) codes of lengths 13 and 14, and we construct many extremal codes of lengths 15 and 16. Also, we construct some new extremal codes of lengths 17,18,19, and 21. We give the current status of known extremal (optimal) additive self-dual codes of lengths 13 to 21.