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

International Conference on Communications

Systematic Modification of Parity-Check Matrices for Efficient Encoding of LDPC Codes

Mohammad Obaidah Shaqfeh, Norbert Goertz

Published Jun 1, 2007• 3 citations
Publisher

Abstract

An algorithm for efficient encoding of LDPC codes is presented that does not impose any restrictions on the construction of the parity-check matrices. The algorithm modifies the parity check matrix, without changing the subspace spanned by its rows, by removing linear dependent rows and adding a small number of new rows such that the graph-based message-passing encoder will not get stuck in a stopping set. The added rows are designed by a new algorithm which is based on the notion of the "key set". The encoder exploits the sparseness of the parity-check matrix, and the encoding complexity grows almost linear with the blocksize, because the number of added rows, which may not be sparse, is relatively small.

DOI
10.1109/icc.2007.160

Related papers

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•31 citations

Quick and Direct Encoding of Low-Density Parity-Check Codes

Wang Yi-ming

LDPC code is a good error correct code which interests telecommunication field recently.However,the performance of LDPC code depends on the girth of its bipartite graph,that is it depends on its sparse parity-check matrices H,especially the complexity of encoding with H.This paper is mainly on how to construct a good matrix H.Based on the extended bit filling algorithm,the paper proposes a new method to construct matrix H which can be encoded directly and quickly.In different length of code,the simulation results show that this quick encoding has good random distribution and it doesn't need to compute the inverse of H and admits linear time encoding.So it can contribute to the LDPC code's application.

Suzhou Daxue xuebao. Faxue ban•Jan 1, 2006•0 citations

Joint encoding-decoding construction of LDPC codes with reduced complexity

Ming Shan

LDPC codes are now one of intensely studied areas in coding due to their near Shannon limit performance and parallel decoding architecture. Because the LDPC codes parity-check matrices are defined in terms of sparse random graphs, the implementation of the decoding and encoding is of high complexity. A new design methodology of LDPC codes, which are constructed by the cyclic shift matrices, is proposed in order to reduce the decoding complexity under the Sum-Product algorithm. Meanwhile,the encoding problem of LDPC codes is also considered, then a simplified encoding structure is given. A new procedure of removing the short loops from the bipartite graph is demonstrated according to the construction scheme of our LDPC codes. Performance comparisons between our codes and random constructed LDPC codes on BER, loop distributions and minimum distance estimation are given by extensive simulations and numerical analysis.

Journal of China Institute of Communications•Jan 1, 2005•1 citation

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•2 citations

The low-density parity-check codes based on The n-queen problem

Li Peng, Guangxi Zhu, Xiao Liu

This paper presents a new family of low-density parity-check (LDPC) code, the sparse parity-check matrix of which is constructed by self-defining non-diagonal identity sub-matrix that is a solution of the "n-queen problem". So this sub-matrix is called the Q-matrix and these LDPC codes are called the Q-matrixes LDPC codes. The Q-matrixes LDPC codes are good or very good codes with iterative decoding and their Tanner graphs are free of 4-lines cycle. Furthermore, they can be created in cycle form. Their encoding can be achieved in linear time. Especially, their code length and code rate can be flexible and quickly adjusted according to the practical situation, and the performance of high rate is also very good. The other unique excellence is that the large sparse parity-check matrixes of long Q-matrixes LDPC codes require very small storage space. The result of this paper is very significant not only for designing low complexity encoder, improving performance and reducing the complexity of the sum-product iterative decoding algorithm, but also for building practice system of encodable and decodable LDPC code.

•Oct 15, 2004•6 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•282 citations
An algorithm for efficient encoding of LDPC codes is presented that does not impose any restrictions on the construction of the parity-check matrices. The algorithm modifies the parity check matrix, without changing the subspace spanned by its rows, by removing linear dependent rows and adding a small number of new rows such that the graph-based message-passing encoder will not get stuck in a stopping set. The added rows are designed by a new algorithm which is based on the notion of the "key set". The encoder exploits the sparseness of the parity-check matrix, and the encoding complexity grows almost linear with the blocksize, because the number of added rows, which may not be sparse, is relatively small.
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.
LDPC code is a good error correct code which interests telecommunication field recently.However,the performance of LDPC code depends on the girth of its bipartite graph,that is it depends on its sparse parity-check matrices H,especially the complexity of encoding with H.This paper is mainly on how to construct a good matrix H.Based on the extended bit filling algorithm,the paper proposes a new method to construct matrix H which can be encoded directly and quickly.In different length of code,the simulation results show that this quick encoding has good random distribution and it doesn't need to compute the inverse of H and admits linear time encoding.So it can contribute to the LDPC code's application.
LDPC codes are now one of intensely studied areas in coding due to their near Shannon limit performance and parallel decoding architecture. Because the LDPC codes parity-check matrices are defined in terms of sparse random graphs, the implementation of the decoding and encoding is of high complexity. A new design methodology of LDPC codes, which are constructed by the cyclic shift matrices, is proposed in order to reduce the decoding complexity under the Sum-Product algorithm. Meanwhile,the encoding problem of LDPC codes is also considered, then a simplified encoding structure is given. A new procedure of removing the short loops from the bipartite graph is demonstrated according to the construction scheme of our LDPC codes. Performance comparisons between our codes and random constructed LDPC codes on BER, loop distributions and minimum distance estimation are given by extensive simulations and numerical analysis.
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.
This paper presents a new family of low-density parity-check (LDPC) code, the sparse parity-check matrix of which is constructed by self-defining non-diagonal identity sub-matrix that is a solution of the "n-queen problem". So this sub-matrix is called the Q-matrix and these LDPC codes are called the Q-matrixes LDPC codes. The Q-matrixes LDPC codes are good or very good codes with iterative decoding and their Tanner graphs are free of 4-lines cycle. Furthermore, they can be created in cycle form. Their encoding can be achieved in linear time. Especially, their code length and code rate can be flexible and quickly adjusted according to the practical situation, and the performance of high rate is also very good. The other unique excellence is that the large sparse parity-check matrixes of long Q-matrixes LDPC codes require very small storage space. The result of this paper is very significant not only for designing low complexity encoder, improving performance and reducing the complexity of the sum-product iterative decoding algorithm, but also for building practice system of encodable and decodable LDPC code.
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.