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 Transactions on Information Theory

Conditionally Cycle-Free Graphical Models for Coset Codes

Thomas R. Halford, K.M. Chugg, Marcus T. Urie

Published Jan 1, 2012• 0 citations
Publisher

Abstract

Conditionally cycle-free graphical models (i.e., cyclic graphical models which become cycle-free after conditioning on a subset of the hidden variables) are constructed for coset codes. Following the description of a general construction procedure, examples of a number of families of codes-including first-order Reed-Muller (RM) and the Delsarte-Goethals codes - are provided for which the proposed procedure yields optimal soft-in soft-out (SISO) decoding algorithms that are less complex than the best known trellis-based algorithms. In the case of the first-order RM codes, which have a recursive coset construction, the optimal SISO decoding algorithm that results when the proposed construction is applied repeatedly is denoted recursive coset representation (RCR) decoding. Connections are made between RCR decoding and existing algorithms that exploit fast Hadamard transforms. Finally, the utility of the proposed decoding algorithms are supported by a practically motivated application: the construction of serially concatenated codes that have high rates and low error floors. Extended Hamming codes are proposed as outer codes in such constructions with efficient decoding employing the SISO algorithms developed herein.

DOI
10.1109/tit.2011.2169540

Related papers

Conditionally Cycle-Free Generalized Tanner Graphs: Theory and Application to High-Rate Serially Concatenated Codes

Thomas R. Halford, K.M. Chugg

Generalized Tanner graphs have been implicitly studied by a number of authors under the rubric of generalized parity-check matrices. This work considers the conditioning of binary hidden variables in such models in order to break all cycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tanner graphs are shown to imply optimal SISO decoding algorithms for the first order Reed-Muller codes and their duals - the extended Hamming codes - which are substantially less complex than conventional bit-level trellis decoding. The study of low-complexity optimal SISO decoding algorithms for the family of extended Hamming codes is practically motivated. Specifically, it is shown that exended Hamming codes offer an attractive alternative to high- rate convolutional codes in terms of both performance and complexity for use in very high-rate, very low-floor, serially concatenated coding schemes.

arXiv:cs/0611097•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•3 citations

Conditionally Cycle-FreeGeneralizedTanner Graphs:Theory and Application toHigh-Rate SeriallyConcatenated Codes

M. Chugg

Generalized Tannergraphshavebeenimplicitly studied byanumberofauthors undertherubric ofgeneralized parity-check matrices. Thisworkconsiders theconditioning of binary hiddenvariables insuchmodelsinordertobreakall cycles andthusderive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tannergraphs areshowntoimply optimal SISOdecoding algorithms forthefirst order Reed-Muller codes andtheir duals -theextended Hamming codes-whicharesubstantially lesscomplex thanconventional bit-level trellis decoding. Thestudyoflow-complexity optimal SISOdecoding algorithms forthefamily ofextended Hamming codesispractically motivated. Specifically, itisshownthat exended Hammingcodesoffer anattractive alternative tohigh- rateconvolutional codesintermsofbothperformance and complexity foruseinveryhigh-rate, verylow-floor, serially concatenated coding schemes.

•Jan 1, 2007•0 citations

Soft Decision Decoding of Recursive Plotkin Constructions Based on Hidden Code Words

Martin Bossert

The Plotkin construction combines two codes to a code of doubled length. It can be applied recursively. The class of Reed-Muller (RM) codes is a particular example. Exploiting a property of the code words constructed by the recursive Plotkin construction, we present novel soft-decision decoders. These are based on the decoding of hidden code words which are inherent contained in the constructed code words and can be uncovered by adding particular parts of the overall code word. The main idea is to use more than one decoding variant where each variant starts with the decoding of a different hidden code word. Given the decision of this first hidden code word allows error cancellation for the remaining decoding. The final decoding decision selects the best of the decisions of the used variants. The more variants are used the closer the performance gets to the maximum-likelihood (ML) decoding performance. This is verified by an ML-bound for the cases where the ML performance is not known. The decoding algorithms use only additions, comparisons, and sign operations. Further, due to the recursive structure, only relatively short codes have to be decoded, thus, the decoding complexity is very low. We also present a new decoder for first-order RM codes with low complexity. In addition, we introduce two novel classes of half-rate codes based on recursive Plotkin constructions with RM codes. We show that the novel soft decision decoders can also be applied to recursive Plotkin constructions with BCH codes and to particular classes of generalized concatenated codes (GCC).

arXiv:2408.12946•IEEE Transactions on Information Theory•Apr 1, 2025•1 citation

Constrained designs for maximum likelihood soft decoding of RM(2,m) and the extended Golay codes

Moshe Ran, Jakov Snyders

We present algorithms for maximum likelihood soft decoding of the second order Reed-Muller codes RM(2,m) and the extended (24,12,8) Golay code. The decoding procedures are based on a concise representation of appropriately selected cosets of a subcode of the code considered. Such representation enables application of certain elimination rules. A structure, called constrained design, is established to support the elimination procedures. Remarkably efficient algorithms are obtainable by this approach. The method of elimination is applicable also in combination with existing coset decoding schemes.>

IEEE Transactions on Communications•Feb 1, 1995•16 citations

The Tradeoff Between Cyclic Topology and Complexity in Graphical Models of Linear Codes

Thomas R. Halford, K.M. Chugg

It is now well-known that together with a suitable message passing schedule, a graphical model for a code implies a soft-in soft-out (SISO) decoding algorithm which is optimal for cycle-free models and suboptimal, yet often substantially less complex, for cyclic models.The Cut-Set Bound (CSB) indicates that the introduction of cycles to graphical models can lead to dramatic reductions in complexity and in the case of tailbiting trellises (i.e.single-cycle models), the CSB can be used to establish the square-root bound, thus quantifying this potential reduction precisely.The aim of this work is to provide such a precise characterization of the tradeoff between cyclic topology and complexity (i.e.maximum hidden variable size and local constraint complexity) in graphical models with more than one cycle.To this end, a new bound is introduced -the tree-inducing cut-set bound -which can be viewed as a generalization of the square-root bound to graphical models with arbitrary cyclic topologies.

•Sep 27, 2006•0 citations

Recursive Decoding of Reed-Muller Codes Starting With the Higher-Rate Constituent Code

Mikhail Kamenev

Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length$(\leq 256)$RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length$2^{m}$and order$m-3$with reasonable complexity.

arXiv:2101.11328•IEEE Transactions on Information Theory•Jul 29, 2022•5 citations
Conditionally cycle-free graphical models (i.e., cyclic graphical models which become cycle-free after conditioning on a subset of the hidden variables) are constructed for coset codes. Following the description of a general construction procedure, examples of a number of families of codes-including first-order Reed-Muller (RM) and the Delsarte-Goethals codes - are provided for which the proposed procedure yields optimal soft-in soft-out (SISO) decoding algorithms that are less complex than the best known trellis-based algorithms. In the case of the first-order RM codes, which have a recursive coset construction, the optimal SISO decoding algorithm that results when the proposed construction is applied repeatedly is denoted recursive coset representation (RCR) decoding. Connections are made between RCR decoding and existing algorithms that exploit fast Hadamard transforms. Finally, the utility of the proposed decoding algorithms are supported by a practically motivated application: the construction of serially concatenated codes that have high rates and low error floors. Extended Hamming codes are proposed as outer codes in such constructions with efficient decoding employing the SISO algorithms developed herein.
Generalized Tanner graphs have been implicitly studied by a number of authors under the rubric of generalized parity-check matrices. This work considers the conditioning of binary hidden variables in such models in order to break all cycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tanner graphs are shown to imply optimal SISO decoding algorithms for the first order Reed-Muller codes and their duals - the extended Hamming codes - which are substantially less complex than conventional bit-level trellis decoding. The study of low-complexity optimal SISO decoding algorithms for the family of extended Hamming codes is practically motivated. Specifically, it is shown that exended Hamming codes offer an attractive alternative to high- rate convolutional codes in terms of both performance and complexity for use in very high-rate, very low-floor, serially concatenated coding schemes.
Generalized Tannergraphshavebeenimplicitly studied byanumberofauthors undertherubric ofgeneralized parity-check matrices. Thisworkconsiders theconditioning of binary hiddenvariables insuchmodelsinordertobreakall cycles andthusderive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tannergraphs areshowntoimply optimal SISOdecoding algorithms forthefirst order Reed-Muller codes andtheir duals -theextended Hamming codes-whicharesubstantially lesscomplex thanconventional bit-level trellis decoding. Thestudyoflow-complexity optimal SISOdecoding algorithms forthefamily ofextended Hamming codesispractically motivated. Specifically, itisshownthat exended Hammingcodesoffer anattractive alternative tohigh- rateconvolutional codesintermsofbothperformance and complexity foruseinveryhigh-rate, verylow-floor, serially concatenated coding schemes.
The Plotkin construction combines two codes to a code of doubled length. It can be applied recursively. The class of Reed-Muller (RM) codes is a particular example. Exploiting a property of the code words constructed by the recursive Plotkin construction, we present novel soft-decision decoders. These are based on the decoding of hidden code words which are inherent contained in the constructed code words and can be uncovered by adding particular parts of the overall code word. The main idea is to use more than one decoding variant where each variant starts with the decoding of a different hidden code word. Given the decision of this first hidden code word allows error cancellation for the remaining decoding. The final decoding decision selects the best of the decisions of the used variants. The more variants are used the closer the performance gets to the maximum-likelihood (ML) decoding performance. This is verified by an ML-bound for the cases where the ML performance is not known. The decoding algorithms use only additions, comparisons, and sign operations. Further, due to the recursive structure, only relatively short codes have to be decoded, thus, the decoding complexity is very low. We also present a new decoder for first-order RM codes with low complexity. In addition, we introduce two novel classes of half-rate codes based on recursive Plotkin constructions with RM codes. We show that the novel soft decision decoders can also be applied to recursive Plotkin constructions with BCH codes and to particular classes of generalized concatenated codes (GCC).
We present algorithms for maximum likelihood soft decoding of the second order Reed-Muller codes RM(2,m) and the extended (24,12,8) Golay code. The decoding procedures are based on a concise representation of appropriately selected cosets of a subcode of the code considered. Such representation enables application of certain elimination rules. A structure, called constrained design, is established to support the elimination procedures. Remarkably efficient algorithms are obtainable by this approach. The method of elimination is applicable also in combination with existing coset decoding schemes.>
It is now well-known that together with a suitable message passing schedule, a graphical model for a code implies a soft-in soft-out (SISO) decoding algorithm which is optimal for cycle-free models and suboptimal, yet often substantially less complex, for cyclic models.The Cut-Set Bound (CSB) indicates that the introduction of cycles to graphical models can lead to dramatic reductions in complexity and in the case of tailbiting trellises (i.e.single-cycle models), the CSB can be used to establish the square-root bound, thus quantifying this potential reduction precisely.The aim of this work is to provide such a precise characterization of the tradeoff between cyclic topology and complexity (i.e.maximum hidden variable size and local constraint complexity) in graphical models with more than one cycle.To this end, a new bound is introduced -the tree-inducing cut-set bound -which can be viewed as a generalization of the square-root bound to graphical models with arbitrary cyclic topologies.
Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length(≤256)(\leq 256)(≤256)RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length2m2^{m}2mand orderm−3m-3m−3with reasonable complexity.