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)

Approximately Lower Triangular Ensembles of LPDC Codes with Linear Encoding Complexity

Shay Freundlich, David Burshtein, Simon N. Litsyn

Published Jul 1, 2006• 6 citations
Publisher

Abstract

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

DOI
10.1109/isit.2006.261728

Related papers

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

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

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

Yuta Iketo, T. Nozaki

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.

arXiv:2103.01560•Mar 2, 2021•1 citation

Modified approximate lower triangular encoding of LDPC codes

Arijit Dutta, Ankita Pramanik

LDPC codes have become the most popular error control code in various fields like telecommunication, magnetic recording etc. due to their high error correcting capability. The Approximate Lower Triangular (ALT) encoding is the most commonly used encoding technique of LDPC codes. This technique though elegant suffers from the shortcoming that when a particular sub matrix of the H matrix obtained after ALT encoding is singular, the technique fails. In this paper a new algorithm is proposed to handle this shortcoming. In this work a new algorithm is proposed to bring any rectangular sparse LDPC matrix into a rectangular part and a square upper triangular part. This algorithm is implemented to encode a general H matrix. This algorithm is further appended to the ALT format of LDPC encoding and another efficient encoding technique is proposed for LDPC code. Both the proposed techniques have a pre-processing step followed by the actual encoding step. Scatter plots of the H matrices (after preprocessing) are shown. BER performance of the new Modified ALT technique is compared with the existing Systematic Approximate Lower Triangular method. The proposed algorithm gives better BER performance.

International Conference on Advances in Computer Engineering and Applications•Mar 1, 2015•5 citations

Nonbinary Quasi-Cyclic LDPC Codes with Efficient Richardson-Urbanke Encoding Algorithm

Xinmei Wang

In order to implement efficient encoding,a class of nonbinary quasi-cyclic low-density parity-check(QC-LDPC) codes is proposed,which can be encoded with Richardson-Urbanke algorithm.The right part of the parity-check matrix has weight-2 columns,which allows the construction of both regular and irregular codes.Constraints on the parity-check matrix ensure a linear encoding complexity. Simulation results show that the proposed codes,when combined with higher order modulation,perform favorably with the codes constructed by the progressive-edge-growth(PEG) constructed code and close to the Shannon limits.

Beijing Youdian Xueyuan xuebao•Jan 1, 2009•0 citations

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
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
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
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.
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.
LDPC codes have become the most popular error control code in various fields like telecommunication, magnetic recording etc. due to their high error correcting capability. The Approximate Lower Triangular (ALT) encoding is the most commonly used encoding technique of LDPC codes. This technique though elegant suffers from the shortcoming that when a particular sub matrix of the H matrix obtained after ALT encoding is singular, the technique fails. In this paper a new algorithm is proposed to handle this shortcoming. In this work a new algorithm is proposed to bring any rectangular sparse LDPC matrix into a rectangular part and a square upper triangular part. This algorithm is implemented to encode a general H matrix. This algorithm is further appended to the ALT format of LDPC encoding and another efficient encoding technique is proposed for LDPC code. Both the proposed techniques have a pre-processing step followed by the actual encoding step. Scatter plots of the H matrices (after preprocessing) are shown. BER performance of the new Modified ALT technique is compared with the existing Systematic Approximate Lower Triangular method. The proposed algorithm gives better BER performance.
In order to implement efficient encoding,a class of nonbinary quasi-cyclic low-density parity-check(QC-LDPC) codes is proposed,which can be encoded with Richardson-Urbanke algorithm.The right part of the parity-check matrix has weight-2 columns,which allows the construction of both regular and irregular codes.Constraints on the parity-check matrix ensure a linear encoding complexity. Simulation results show that the proposed codes,when combined with higher order modulation,perform favorably with the codes constructed by the progressive-edge-growth(PEG) constructed code and close to the Shannon limits.