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

arXiv:1101.3929

Characteristic Generators and Dualization for Tail-Biting Trellises

Heide Gluesing-Luerssen, Elizabeth A. Weaver

Published Jan 20, 2011• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1101.3929

Related papers

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

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

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

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

Weight Enumerators of Convolutional Codes, Tail-biting Codes and Their Duals

JØrn Justesen

The weight enumerators of convolutional codes and their tail-biting version may be derived from the finite state description.We present a generating function for the sequence of weight enumerators of these codes, and show that generating functions of dual codes satisfy a MacWilliams identity.The weights of the finite state description of the dual codes may be found by a transform.

•Oct 3, 2001•0 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
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.
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
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.