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

Globecom

A low-weight trellis based decoding algorithm for binary linear block codes with application to generalized irregular low-density codes

Telex M. N. Ngatched, Fambirai Takawira

Published Feb 22, 2005• 0 citations
Publisher

Abstract

In this paper, reduced-complexity trellis-based soft-input soft-output (SISO) decoding of linear block codes is considered. A new low-weight subtrellis based SISO decoding algorithm for linear block code to achieve near optimal error performance with a significant reduction in decoding complexity is presented. The proposed scheme is suitable for iterative decoding of linear block codes when used as component codes in compound or concatenated coding schemes. It has the following important features. An initial candidate codeword is first generated by a simple decoding method that guarantees a successful decoding. A low-weight subtrellis diagram centered around the candidate codeword is constructed. The maximum a posteriori probability (MAP) algorithm is then applied to the subtrellis. The generated extrinsic information is then used as a priori information to improve the generation of a candidate codeword for the next stage of iteration. Simulation results in the case of the newly introduced generalized irregular low-density (GILD) codes indicate that the proposed algorithm achieves practically optimal performance with a significant reduction in decoding complexity.

DOI
10.1109/glocom.2004.1378001

Related papers

A low-weight trellis-based iterative soft-decision decoding algorithm for binary linear block codes

Takuya Koumoto, T. Takata, Tadao Kasami +1 more

This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.

IEEE Transactions on Information Theory•Mar 1, 1999•13 citations

An Iterative Soft-Decision Decoding Algorithm

Shu Wen Lin, Takuya Koumoto, Toyoo Takata +1 more

This paper presents a new minimum-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. Simulation results for the RM(64,22), EBCH(64,24), RM(64,42) and EBCH(64,45) codes show that the proposed decoding algorithm achieves practically (or near) optimal error performance with significant reduction in decoding computational complexity. The average number of search iterations is also small even for low signal-to-noise ratio.

•Jul 10, 1996•7 citations

Efficient decoding of generalized low-density parity-check codes based on long component codes

Telex M. N. Ngatched, Fambirai Takawira

A class of pseudo-random compound error-correcting codes, called generalized low density (GLD) parity-check codes, has been proposed recently. As a generalization of Gallager's low-density parity check (LPDC) codes, GLD codes are also asymptotically good in the sense of minimum distance criterion and can be effectively decoded based on iterative soft-input soft-output (SISO) decoding of individual constituent codes. The code performance and decoding complexity of GLD codes are heavily dependent on the employed SISO decoding algorithm. In this paper, we present an efficient SISO decoding algorithm for GLD codes. The proposed algorithm utilizes Kaneko's decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decision using reliability calculations. The algorithm proposed here presents a major advantage over existing decoding algorithms for GLD codes by being applicable even when long and powerful component codes are used. The complexity of the proposed algorithm is less than that of trellis-based decoding algorithms with a performance degradation of only 0.3 dB.

IEEE Wireless Communications and Networking Conference•Jan 24, 2004•6 citations

Compound codes based on irregular graphs and their iterative decoding.

Telex Magloire Ngatched. Nkouatchah

Low-density parity-check (LDPC) codes form a Shannon limit approaching class of linear block codes. With iterative decoding based on their Tanner graphs, they can achieve outstanding performance. Since their rediscovery in late 1990's, the design, construction, and decoding of LDPC codes as well as their generalization have become one of the focal research points. This thesis takes a few more steps in these directions. The first significant contribution of this thesis is the introduction of a new class of codes called Generalized Irregular Low-Density (GILD) parity-check codes, which are adapted from the previously known class of Generalized Low-Density (GLD) codes. GILD codes are generalization of irregular LDPC codes, and are shown to outperform GLD codes. In addition, GILD codes have a significant advantage over GLD codes in terms of encoding and decoding complexity. They are also able to match and even beat LDPC codes for small block lengths. The second significant contribution of this thesis is the proposition of several decoding algorithms. Two new decoding algolithms for LDPC codes are introduced. In principle and complexity these algorithms can be grouped with bit flipping algorithms. Two soft-input soft-output (SISO) decoding algorithms for linear block codes are also proposed. The first algorithm is based on Maximum a Posteriori Probability (MAP) decoding of low-weight subtrellis centered around a generated candidate codeword. The second algorithm modifies and utilizes the improved Kaneko's decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decisions using reliability calculations. Simulation results indicate that the proposed algorithms provide a significant improvement in error performance over Chase-based algorithm and achieve practically optimal performance with a significant reduction in decoding complexity. An analytical expression for the union bound on the bit error probability of linear codes on the Gilbert-Elliott (GE) channel model is also derived. This analytical result is shown to be accurate in establishing the decoder performance in the range where obtaining sufficient data from simulation is impractical.

•Jan 1, 2004•0 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

New implementation for the scalable LDPC-decoders

Yanping Li, Moon Ho Lee, Gi-Yean Hwang +1 more

Trellis decoding of regular and irregular low-density parity-check (LDPC) codes and the corresponding decoder architectures are considered. Moreover, we propose a new approach for computing reliability metrics based on the BCJR algorithm that reduces the message switching activity in the decoder compared to existing approaches. The trellis decoding schedule is employed to decode LDPC codes using constituent soft-input soft-output (SISO) decoders that communicate through interleavers. The proposed tunable schedule exhibits a faster convergence behavior (up to 50% fewer iterations), and hence lower decoding latency, than the commonly employed two-phase schedule, and the corresponding decoder architecture has a significantly reduced memory requirement. Improvement in decoding gain (up to an order of magnitude for moderate-to-high SNR and small number of iterations) is achieved and structural regularity features in the form of permutation matrices further reduce interconnect complexity and improve decoding throughput.

IEEE Vehicular Technology Conference•Feb 22, 2005•1 citation
In this paper, reduced-complexity trellis-based soft-input soft-output (SISO) decoding of linear block codes is considered. A new low-weight subtrellis based SISO decoding algorithm for linear block code to achieve near optimal error performance with a significant reduction in decoding complexity is presented. The proposed scheme is suitable for iterative decoding of linear block codes when used as component codes in compound or concatenated coding schemes. It has the following important features. An initial candidate codeword is first generated by a simple decoding method that guarantees a successful decoding. A low-weight subtrellis diagram centered around the candidate codeword is constructed. The maximum a posteriori probability (MAP) algorithm is then applied to the subtrellis. The generated extrinsic information is then used as a priori information to improve the generation of a candidate codeword for the next stage of iteration. Simulation results in the case of the newly introduced generalized irregular low-density (GILD) codes indicate that the proposed algorithm achieves practically optimal performance with a significant reduction in decoding complexity.
This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.
A class of pseudo-random compound error-correcting codes, called generalized low density (GLD) parity-check codes, has been proposed recently. As a generalization of Gallager's low-density parity check (LPDC) codes, GLD codes are also asymptotically good in the sense of minimum distance criterion and can be effectively decoded based on iterative soft-input soft-output (SISO) decoding of individual constituent codes. The code performance and decoding complexity of GLD codes are heavily dependent on the employed SISO decoding algorithm. In this paper, we present an efficient SISO decoding algorithm for GLD codes. The proposed algorithm utilizes Kaneko's decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decision using reliability calculations. The algorithm proposed here presents a major advantage over existing decoding algorithms for GLD codes by being applicable even when long and powerful component codes are used. The complexity of the proposed algorithm is less than that of trellis-based decoding algorithms with a performance degradation of only 0.3 dB.
Low-density parity-check (LDPC) codes form a Shannon limit approaching class of linear block codes. With iterative decoding based on their Tanner graphs, they can achieve outstanding performance. Since their rediscovery in late 1990's, the design, construction, and decoding of LDPC codes as well as their generalization have become one of the focal research points. This thesis takes a few more steps in these directions. The first significant contribution of this thesis is the introduction of a new class of codes called Generalized Irregular Low-Density (GILD) parity-check codes, which are adapted from the previously known class of Generalized Low-Density (GLD) codes. GILD codes are generalization of irregular LDPC codes, and are shown to outperform GLD codes. In addition, GILD codes have a significant advantage over GLD codes in terms of encoding and decoding complexity. They are also able to match and even beat LDPC codes for small block lengths. The second significant contribution of this thesis is the proposition of several decoding algorithms. Two new decoding algolithms for LDPC codes are introduced. In principle and complexity these algorithms can be grouped with bit flipping algorithms. Two soft-input soft-output (SISO) decoding algorithms for linear block codes are also proposed. The first algorithm is based on Maximum a Posteriori Probability (MAP) decoding of low-weight subtrellis centered around a generated candidate codeword. The second algorithm modifies and utilizes the improved Kaneko's decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decisions using reliability calculations. Simulation results indicate that the proposed algorithms provide a significant improvement in error performance over Chase-based algorithm and achieve practically optimal performance with a significant reduction in decoding complexity. An analytical expression for the union bound on the bit error probability of linear codes on the Gilbert-Elliott (GE) channel model is also derived. This analytical result is shown to be accurate in establishing the decoder performance in the range where obtaining sufficient data from simulation is impractical.
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.
Trellis decoding of regular and irregular low-density parity-check (LDPC) codes and the corresponding decoder architectures are considered. Moreover, we propose a new approach for computing reliability metrics based on the BCJR algorithm that reduces the message switching activity in the decoder compared to existing approaches. The trellis decoding schedule is employed to decode LDPC codes using constituent soft-input soft-output (SISO) decoders that communicate through interleavers. The proposed tunable schedule exhibits a faster convergence behavior (up to 50% fewer iterations), and hence lower decoding latency, than the commonly employed two-phase schedule, and the corresponding decoder architecture has a significantly reduced memory requirement. Improvement in decoding gain (up to an order of magnitude for moderate-to-high SNR and small number of iterations) is achieved and structural regularity features in the form of permutation matrices further reduce interconnect complexity and improve decoding throughput.