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

arXiv:2103.01560

Efficient Encoding Algorithm of Binary and Non-Binary LDPC Codes Using Block Triangulation

Yuta Iketo, T. Nozaki

Published Mar 2, 2021• 1 citation
arXivHTMLPDF

Abstract

We propose an efficient encoding algorithm for the binary and non-binary low-density parity-check codes. This algorithm transforms the parity part of the parity-check matrix into a block triangular matrix with low weight diagonal submatrices by row and column permutations in the preprocessing stage. This algorithm determines the parity part of a codeword by block back-substitution to reduce the encoding complexity in the encoding stage. Numerical experiments show that this algorithm has a lower encoding complexity than existing encoding algorithms. Moreover, we show that this algorithm encodes the non-binary cycle codes in linear time.

DOI
10.48550/arxiv.2103.01560

Related papers

Encoding Algorithm of Binary and Non-binary Irregular LDPC Codes via Block Triangular Matrices with Low Weight Diagonal Submatrices

Yuta Iketo, T. Nozaki

In this paper, we propose a low complexity encoding algorithm for the binary and non-binary irregular LDPC codes. This algorithm transforms the parity part of the parity-check matrix into a block triangular matrix by row and column permutations. By lowering the weight of diagonal submatrices, we reduce the encoding complexity.

International Symposium on Information Theory and its Applications•Oct 24, 2020•0 citations

Quasi-cyclic LDPC codes for fast encoding

Seho Myung, Kyeongcheol Yang, Jaeyoel Kim

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.

IEEE Transactions on Information Theory•Jul 19, 2005•278 citations

Structure of non-binary regular ldpc cycle codes

Jie Huang, Shengli Zhou, Peter Willett

In this paper, we study non-binary regular LDPC cycle codes whose parity check matrix has fixed column weight 2 and fixed row weight d. We prove that the parity check matrix of any regular cycle code can be put into a concatenation form of row-permuted block-diagonal matrices after row and column permutations if d is even, or, if d is odd and the code's associated graph contains at least one spanning subgraph that consists of disjoint edges. Utilizing this structure enables parallel processing in linear-time encoding, and parallel processing in sequential belief-propagation decoding, which increases the throughput without compromising performance or complexity. Numerical results are presented to compare the code performance and the decoding complexity.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 1, 2008•4 citations

Approximately Lower Triangular Ensembles of LDPC Codes With Linear Encoding Complexity

Shay Freundlich, David Burshtein, Simon N. Litsyn

The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

IEEE Transactions on Information Theory•Apr 1, 2007•18 citations

Approximately Lower Triangular Ensembles of LPDC Codes with Linear Encoding Complexity

Shay Freundlich, David Burshtein, Simon N. Litsyn

The complexity of brute force encoding of LDPC codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

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

Linear Time Encoding of LDPC Codes

Jin Lu, José M. F. Moura

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ¿label-and-decide.¿ We prove that the ¿label-and-decide¿ method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ¿label-decide-recompute.¿ Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than4 ·M·((k¿- 1), whereMis the number of independent rows in the parity-check matrix andk¿represents the mean row weight of the parity-check matrix.

arXiv:0810.2781•IEEE Transactions on Information Theory•Jan 1, 2010•19 citations
We propose an efficient encoding algorithm for the binary and non-binary low-density parity-check codes. This algorithm transforms the parity part of the parity-check matrix into a block triangular matrix with low weight diagonal submatrices by row and column permutations in the preprocessing stage. This algorithm determines the parity part of a codeword by block back-substitution to reduce the encoding complexity in the encoding stage. Numerical experiments show that this algorithm has a lower encoding complexity than existing encoding algorithms. Moreover, we show that this algorithm encodes the non-binary cycle codes in linear time.
In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.
In this paper, we study non-binary regular LDPC cycle codes whose parity check matrix has fixed column weight 2 and fixed row weight d. We prove that the parity check matrix of any regular cycle code can be put into a concatenation form of row-permuted block-diagonal matrices after row and column permutations if d is even, or, if d is odd and the code's associated graph contains at least one spanning subgraph that consists of disjoint edges. Utilizing this structure enables parallel processing in linear-time encoding, and parallel processing in sequential belief-propagation decoding, which increases the throughput without compromising performance or complexity. Numerical results are presented to compare the code performance and the decoding complexity.
The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes
The complexity of brute force encoding of LDPC codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes
In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ¿label-and-decide.¿ We prove that the ¿label-and-decide¿ method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ¿label-decide-recompute.¿ Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than4 ·M·((k¿- 1), whereMis the number of independent rows in the parity-check matrix andk¿represents the mean row weight of the parity-check matrix.