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 International Symposium on Information Theory (ISIT)

Burst-Correction Decoding of Cyclic LDPC Codes

Shumei Song, Shu Lin, Khaled Abdel-Ghaffar

Published Jul 1, 2006• 4 citations
Publisher

Abstract

LDPC codes have excellent performance when iteratively decoded based on sparse parity-check matrices over both the AWGN channel and the erasure channel. In this paper, we propose a simple burst-correction decoding scheme for cyclic LDPC codes based on the same sparse circulant parity-check matrices used to perform iterative decoding. Although the proposed scheme may not achieve the full burst-correcting capability of the codes, it is rather simple and fast. We also show that the full burst-correcting capabilities of some codes constructed from Euclidean and projective geometries are very close to the Reiger upper bound

DOI
10.1109/isit.2006.261648

Related papers

Optimizing burst erasure correction of LDPC codes by interleaving

Gokul Sridharan, Abishek Kumarasubramanian, Andrew Thangaraj +1 more

The performance of iterative decoding of low density parity check (LDPC) codes over binary erasure channels can be completely characterized by the study of stopping sets. Therefore, the burst erasure correction capability of a given LDPC code can be readily quantified by searching for stopping sets within consecutive bit nodes. In this work we study the optimal permutation of the bit nodes that will result in the maximum possible burst erasure correction capability for a given LDPC code. Noting that this is essentially a combinatorial optimization problem that is highly likely to be NP-hard, we adopt a simulated annealing based approach for finding the optimal permutation. We present bounds based on stopping sets that limit the burst erasure correction capability. As part of our results, we provide interleavers that greatly improve the burst erasure correction capability of protograph quasi-cyclic LDPC codes used in the WiMax standard.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•8 citations

Enhancing Iterative Decoding of Cyclic LDPC Codes Using Their Automorphism Groups

Chao Chen, Baoming Bai, Xinquan Yang +2 more

For cyclic LDPC codes, we propose to use their automorphism groups to improve the iterative decoding performance. The basic idea is to construct nonequivalent parity-check matrices via column permutations. Three types of iterative decoders are devised to take advantage of the code's automorphism group. In this paper we focus on cyclic LDPC codes defined by a circulant parity-check matrix and consider two known subgroups of the automorphism group of a cyclic code. For the large class of idempotent-based cyclic LDPC codes in the literature, we show that the two subgroups only provide equivalent parity-check matrices and thus cannot be harnessed for iterative decoding. Towards exploiting the automorphism group of a code, we propose a new class of cyclic LDPC codes based on pseudo-cyclic MDS codes with two information symbols, for which nonequivalent parity-check matrices are obtained. Simulation results show that for our constructed codes of short lengths, the automorphism group can significantly enhance the iterative decoding performance.

IEEE Transactions on Communications•Apr 4, 2013•9 citations

NEW CONSTRUCTIONS OF LDPC CODES BASED ON CIRCULANT PERMUTATION MATRICES FOR AWGN CHANNEL

Song, Zixi, Zhang +1 more

Two new design approaches for constructing Low-Density Parity-Check(LDPC) codes are proposed.One is used to design regular Quasi-Cyclic LDPC(QC-LDPC) codes with girth at least 8.The other is used to design irregular LDPC codes.Both of their parity-check matrices are composed of Circulant Permutation Matrices(CPMs).When iteratively decoded with the Sum-Product Algorithm(SPA),these proposed codes exhibit good performances over the AWGN channel.

Journal of Electronics (China)•Jan 1, 2014•2 citations

Erasure-Burst and Error-Burst Decoding of Linear Codes

Shumei Song, Shu Lin, Khaled Abdel-Ghaffar +1 more

Iterative algorithms for decoding over erasure-burst channels have attracted much interest lately due to their simplicity. Although the performance of these techniques is typically good, it may not be optimal if the underlying matrix used for decoding is not properly chosen. In this paper, we construct matrices that lead to optimal performance when used with iterative decoding over erasure-burst channels. We also develop a simple decoding technique that makes use of these same matrices to decode any linear code over error-burst channels. For cyclic codes, this algorithm is optimal.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•6 citations

Quasi-Cyclic LDPC Codes on Cyclic Subgroups of Finite Fields

Li Guo Zhang, Shu Lin, Khaled Abdel-Ghaffar +2 more

A new class of quasi-cyclic LDPC codes whose parity-check matrices are arrays of circulant permutation matrices constructed based on cyclic subgroups of finite fields is presented. This class of codes contains several known classes of algebraic quasi-cyclic LDPC codes as subclasses. Experimental results show that the codes constructed perform very well over the AWGN channel when decoded with iterative decoding based on belief propagation. This class of new QC-LDPC codes contains a subclass of codes which have large minimum distances. Combinatorial expressions for the ranks of the parity-check matrices of a subclass of codes constructed based on fields of characteristic two are given.

IEEE Transactions on Communications•Jun 28, 2011•34 citations

LDPC Block and Convolutional Codes Based on Circulant Matrices

R. Michael Tanner, Deepak Sridhara, Arvind Sridharan +2 more

A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.

IEEE Transactions on Information Theory•Nov 30, 2004•591 citations
LDPC codes have excellent performance when iteratively decoded based on sparse parity-check matrices over both the AWGN channel and the erasure channel. In this paper, we propose a simple burst-correction decoding scheme for cyclic LDPC codes based on the same sparse circulant parity-check matrices used to perform iterative decoding. Although the proposed scheme may not achieve the full burst-correcting capability of the codes, it is rather simple and fast. We also show that the full burst-correcting capabilities of some codes constructed from Euclidean and projective geometries are very close to the Reiger upper bound
The performance of iterative decoding of low density parity check (LDPC) codes over binary erasure channels can be completely characterized by the study of stopping sets. Therefore, the burst erasure correction capability of a given LDPC code can be readily quantified by searching for stopping sets within consecutive bit nodes. In this work we study the optimal permutation of the bit nodes that will result in the maximum possible burst erasure correction capability for a given LDPC code. Noting that this is essentially a combinatorial optimization problem that is highly likely to be NP-hard, we adopt a simulated annealing based approach for finding the optimal permutation. We present bounds based on stopping sets that limit the burst erasure correction capability. As part of our results, we provide interleavers that greatly improve the burst erasure correction capability of protograph quasi-cyclic LDPC codes used in the WiMax standard.
For cyclic LDPC codes, we propose to use their automorphism groups to improve the iterative decoding performance. The basic idea is to construct nonequivalent parity-check matrices via column permutations. Three types of iterative decoders are devised to take advantage of the code's automorphism group. In this paper we focus on cyclic LDPC codes defined by a circulant parity-check matrix and consider two known subgroups of the automorphism group of a cyclic code. For the large class of idempotent-based cyclic LDPC codes in the literature, we show that the two subgroups only provide equivalent parity-check matrices and thus cannot be harnessed for iterative decoding. Towards exploiting the automorphism group of a code, we propose a new class of cyclic LDPC codes based on pseudo-cyclic MDS codes with two information symbols, for which nonequivalent parity-check matrices are obtained. Simulation results show that for our constructed codes of short lengths, the automorphism group can significantly enhance the iterative decoding performance.
Iterative algorithms for decoding over erasure-burst channels have attracted much interest lately due to their simplicity. Although the performance of these techniques is typically good, it may not be optimal if the underlying matrix used for decoding is not properly chosen. In this paper, we construct matrices that lead to optimal performance when used with iterative decoding over erasure-burst channels. We also develop a simple decoding technique that makes use of these same matrices to decode any linear code over error-burst channels. For cyclic codes, this algorithm is optimal.
A new class of quasi-cyclic LDPC codes whose parity-check matrices are arrays of circulant permutation matrices constructed based on cyclic subgroups of finite fields is presented. This class of codes contains several known classes of algebraic quasi-cyclic LDPC codes as subclasses. Experimental results show that the codes constructed perform very well over the AWGN channel when decoded with iterative decoding based on belief propagation. This class of new QC-LDPC codes contains a subclass of codes which have large minimum distances. Combinatorial expressions for the ranks of the parity-check matrices of a subclass of codes constructed based on fields of characteristic two are given.
A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.