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

Journal of Generalized Lie Theory and Applications

A Multivariate Weight Enumerator for Tail-biting Trellis Pseudocodewords

Nigel Boston

Published Jan 1, 2015• 7 citations
Publisher

Abstract

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.

DOI
10.4172/1736-4337.s1-004

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

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

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

Iterative decoding and graphical code representations

Meina Xu

Since the invention of turbo codes, there has been an explosion of interest in iterative decoding and graphical representation of codes. This thesis examines the iterative decoding of codes defined on graphs with cycles, which appears to be an efficient means of achieving the Shannon limit. Much of this analysis is on the iterative min-sum decoding of tail-biting codes and cycle codes. We have identified the pseudocodeword as the cause of the suboptimal performance of the iterative decoder, and we have obtained a union bound for the performance of the iterative decoder on both AWGN and BSC channels. Using the union bound argument, for cycle codes, we have shown that the performance of the iterative decoder is asymptotically as good as that of the ML decoder. As for tail-biting codes, the same thing is true if the lowest weight pseudocodeword is at least the minimum weight of the code. Unfortunately, the analysis of tail-biting codes and cycle codes does not extend to turbo codes and low density parity check codes in general. Our next approach is to determine the average behavior of message passing algorithms by studying the evolution of their "message" densities. For the class of "repeat and accumulate" serially concatenated turbo-like codes, we have devised an algorithm for determining their "threshold" values. When the signal-to-noise ratio is larger than the threshold value, the error probabilities of message passing algorithms approach zero, whereas if the signal-to-noise ratio is less than the threshold value, the error probability stays bounded away from zero. Some message passing algorithms and graphical representation of codes are efficient means of devising ML or MAP decoding algorithms. We have proposed a junction tree representation for linear block codes, and we have shown that the minimum junction tree can be less complex than the minimal trellis.

•Mar 11, 2008•1 citation

Iterative decoding and pseudo-codewords

Gavin Bernard Horn

In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance. Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.

•Jan 1, 1999•17 citations

Tail-Biting Code/Error-Trellis Construction for Linear Block Codes

Masato Tajima, Koji Okino, Tatsuto Murayama

IEICE Technical Report; IEICE Tech. Rep.•Jul 10, 2014•2 citations
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.
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.
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
Since the invention of turbo codes, there has been an explosion of interest in iterative decoding and graphical representation of codes. This thesis examines the iterative decoding of codes defined on graphs with cycles, which appears to be an efficient means of achieving the Shannon limit. Much of this analysis is on the iterative min-sum decoding of tail-biting codes and cycle codes. We have identified the pseudocodeword as the cause of the suboptimal performance of the iterative decoder, and we have obtained a union bound for the performance of the iterative decoder on both AWGN and BSC channels. Using the union bound argument, for cycle codes, we have shown that the performance of the iterative decoder is asymptotically as good as that of the ML decoder. As for tail-biting codes, the same thing is true if the lowest weight pseudocodeword is at least the minimum weight of the code. Unfortunately, the analysis of tail-biting codes and cycle codes does not extend to turbo codes and low density parity check codes in general. Our next approach is to determine the average behavior of message passing algorithms by studying the evolution of their "message" densities. For the class of "repeat and accumulate" serially concatenated turbo-like codes, we have devised an algorithm for determining their "threshold" values. When the signal-to-noise ratio is larger than the threshold value, the error probabilities of message passing algorithms approach zero, whereas if the signal-to-noise ratio is less than the threshold value, the error probability stays bounded away from zero. Some message passing algorithms and graphical representation of codes are efficient means of devising ML or MAP decoding algorithms. We have proposed a junction tree representation for linear block codes, and we have shown that the minimum junction tree can be less complex than the minimal trellis.
In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance. Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.