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 Communications

Transactions Letters - Random Redundant Iterative Soft-in Soft-out Decoding

Thomas R. Halford, K.M. Chugg

Published Apr 1, 2008• 25 citations
Publisher

Abstract

This letter presents an iterative soft-in soft-out (SISO) decoding algorithm based on redundant Tanner graphs that is applicable to arbitrary linear block codes. The proposed algorithm utilizes the permutation group of a code in order to efficiently and randomly generate redundant parity-checks.
DOI
10.1109/tcomm.2008.060105

Related papers

Random Redundant Soft-In Soft-Out Decoding of Linear Block Codes

Thomas R. Halford, K.M. Chugg

A number of authors have recently considered iterative soft-in soft-out (SISO) decoding algorithms for classical linear block codes that utilize redundant Tanner graphs. Jiang and Narayanan presented a practically realizable algorithm that applies only to cyclic codes while Kothiyal et al. presented an algorithm that, while applicable to arbitrary linear block codes, does not imply a low-complexity implementation. This work first presents the aforementioned algorithms in a common framework and then presents a related algorithm - random redundant iterative decoding - that is both practically realizable and applicable to arbitrary linear block codes. Simulation results illustrate the successful application of the random redundant iterative decoding algorithm to the extended binary Golay code. Additionally, the proposed algorithm is shown to outperform Jiang and Narayanan's algorithm for a number of Bose-Chaudhuri-Hocquenghem (BCH) codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•46 citations

On iterative decoding of HDPC codes using weight-bounding graph operations

Joakim Grahl Knudsen, Constanza Riera, Lars Eirik Danielsen +2 more

Abstract—In this paper, we extend our work on iterative softinput soft-output (SISO) decoding of high density parity check (HDPC) codes. Edge-local complementation (ELC) is a graph operationwhichcanbeusedtogivestructuralredundancyduring decoding with the sum-product algorithm (SPA). We describe the specific subgraphs required for ELC to not increase the weight of the Tanner graph beyond a specified upper bound. We call this controlled operation weight-bounding ELC (WB-ELC). A generalized iterative SISO HDPC decoder is described, which can be configured to employ different operations; most importantly, ‘flooding ’ SPA, and iterative ‘permutation decoding. ’ The latter is a state-of-the-art decoding algorithm for HDPC codes, using permutations from the automorphism group of the code. We observe performance improvements when the SISO HDPC decoder is configured to use WB-ELC, as compared to using ELC, or even permutation decoding. I.

•Jan 1, 2010•3 citations

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

Iterative soft decoding of binary linear codes using a generalized Tanner graph

Eirik Rosnes

In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner graph. A generalized Tanner graph is constructed from the code's Tanner graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.

IEEE Information Theory Workshop (ITW)•Oct 1, 2011•0 citations

Stochastic Decoding of Linear Block Codes With High-Density Parity-Check Matrices

Saeed Sharifi Tehrani, Christophe Jégo, Bo Zhu +1 more

This correspondence extends the application of the recently proposed stochastic decoding approach to decode linear block codes with high-density parity-check matrices and discusses its hardware complexity. Results demonstrate decoding performance close to floating-point iterative soft-input soft-output (SISO) decoding while offering nodes with considerably lower complexity compared to fixed-point SISO decoding.

IEEE Transactions on Signal Processing•Aug 18, 2008•22 citations

Iterative Decoding of Linear Block Codes: A Parity-Check Orthogonalization Approach

S. Sankaranarayanan, Bane V. Vasic

It is widely accepted that short cycles in Tanner graphs deteriorate the performance of message-passing algorithms. This discourages the use of these algorithms on Tanner graphs (TGs) of well-known algebraic codes such as Hamming codes, Bose-Chaudhuri-Hocquenghem codes, and Reed-Solomon codes. Yedidia et al. presented a method to generate code representations suitable for message-passing algorithms. This method does not guarantee a representation free of four-cycles. In this correspondence, we present an algorithm to convert an arbitrary linear block into a code with orthogonal parity-check equations. A combinatorial argument is used to prove that the algorithm guarantees a four-cycle free representation for any linear code. The effects of removing four-cycles on the performance of a belief propagation decoder for the binary erasure channel are studied in detail by analyzing the structures in different representations. Finally, we present bit-error rate (BER) and block-error rate (BLER) performance curves of linear block codes under belief propagation algorithms for the binary erasure channel and the additive white Gaussian noise (AWGN) channel in order to demonstrate the improvement in performance achieved with the help of the proposed algorithm.

IEEE Transactions on Information Theory•Aug 24, 2005•57 citations
A number of authors have recently considered iterative soft-in soft-out (SISO) decoding algorithms for classical linear block codes that utilize redundant Tanner graphs. Jiang and Narayanan presented a practically realizable algorithm that applies only to cyclic codes while Kothiyal et al. presented an algorithm that, while applicable to arbitrary linear block codes, does not imply a low-complexity implementation. This work first presents the aforementioned algorithms in a common framework and then presents a related algorithm - random redundant iterative decoding - that is both practically realizable and applicable to arbitrary linear block codes. Simulation results illustrate the successful application of the random redundant iterative decoding algorithm to the extended binary Golay code. Additionally, the proposed algorithm is shown to outperform Jiang and Narayanan's algorithm for a number of Bose-Chaudhuri-Hocquenghem (BCH) codes
Abstract—In this paper, we extend our work on iterative softinput soft-output (SISO) decoding of high density parity check (HDPC) codes. Edge-local complementation (ELC) is a graph operationwhichcanbeusedtogivestructuralredundancyduring decoding with the sum-product algorithm (SPA). We describe the specific subgraphs required for ELC to not increase the weight of the Tanner graph beyond a specified upper bound. We call this controlled operation weight-bounding ELC (WB-ELC). A generalized iterative SISO HDPC decoder is described, which can be configured to employ different operations; most importantly, ‘flooding ’ SPA, and iterative ‘permutation decoding. ’ The latter is a state-of-the-art decoding algorithm for HDPC codes, using permutations from the automorphism group of the code. We observe performance improvements when the SISO HDPC decoder is configured to use WB-ELC, as compared to using ELC, or even permutation decoding. I.
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.
In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner graph. A generalized Tanner graph is constructed from the code's Tanner graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.
It is widely accepted that short cycles in Tanner graphs deteriorate the performance of message-passing algorithms. This discourages the use of these algorithms on Tanner graphs (TGs) of well-known algebraic codes such as Hamming codes, Bose-Chaudhuri-Hocquenghem codes, and Reed-Solomon codes. Yedidia et al. presented a method to generate code representations suitable for message-passing algorithms. This method does not guarantee a representation free of four-cycles. In this correspondence, we present an algorithm to convert an arbitrary linear block into a code with orthogonal parity-check equations. A combinatorial argument is used to prove that the algorithm guarantees a four-cycle free representation for any linear code. The effects of removing four-cycles on the performance of a belief propagation decoder for the binary erasure channel are studied in detail by analyzing the structures in different representations. Finally, we present bit-error rate (BER) and block-error rate (BLER) performance curves of linear block codes under belief propagation algorithms for the binary erasure channel and the additive white Gaussian noise (AWGN) channel in order to demonstrate the improvement in performance achieved with the help of the proposed algorithm.