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

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

M. Chugg

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

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.

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-Free Graphical Models for Coset Codes

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

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.

IEEE Transactions on Information Theory•Jan 1, 2012•0 citations

Bit-optimal decoding of codes whose Tanner graphs are trees

Emina Soljanin, Elke Offer

Discrete Applied Mathematics•May 1, 2003•0 citations

Soft-decision decoding of Reed-Muller codes as generalized multiple concatenated codes

G. Schnabl, Martin Bossert

Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long codes.>

IEEE Transactions on Information Theory•Jan 1, 1995•90 citations

Pseudocodeword-free criterion for codes with cycle-free Tanner graph

Wittawat Kositwattanarerk

Designs Codes and Cryptography•Mar 23, 2018•0 citations

On Iterative Decoding of Cycle Codes of Graphs

Gilles Zémor

The IMA volumes in mathematics and its applications•Jan 1, 2001•4 citations
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.
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.
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.
Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long codes.>