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

Suzhou Daxue xuebao. Faxue ban

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

Wang Yi-ming

Published Jan 1, 2006• 0 citations
OpenAlex

Abstract

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.

Related papers

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

A novel algorithm of constructing LDPC codes with graph theory

Yan Cui, Xinhui Si, Yanan Shen

There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.

IEEE Conference on Cybernetics and Intelligent Systems•Sep 1, 2008•2 citations

Construction of LDPC Code with Big Girth and Linear-encoding Complexity

Xiaoming Liu

Based on cycle search algorithm and Progressive Edge Growth(PEG) algorithm,this paper proposes a method to construct quasi-cyclic Low-density Parity Check(LDPC) codes with big girth and linear-encoding complexity.A parity-check matrix with a form of approximate lower triangle structure is designed to achieve iterative encoding with linear-encoding complexity.PEG algorithm is used to construct the base matrix and the cycle search algorithm is used to optimize the cycle distribution.And a fast encoding method is proposed.Experimental results show that the LDPC codes constructed with the proposed method can avoid error floor and achieve better BER performance than Tanner-QC-LDPC codes and equivalent BER performance to the ones of random codes.

Jisuanji gongcheng•Jan 1, 2011•0 citations

Low-Density Parity-Check Codes: Construction and Implementation

Gabofetswe Malema

Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. \nThis thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. \nRow-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. \nQuasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. \nDecoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing \nthe starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. \nTechniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques.

•Jan 1, 2007•24 citations

A random construction of LDPC codes using a sub-optimal search algorithm

Seif Shebl, Nawal Ahmed El-Fishawy, Atef Abou Elazm +1 more

In this paper, a method for constructing Low-Density Parity-Check (LDPC) codes of good performance in terms of Bit Error Rate (BER) using a computer search algorithm is presented. First, LDPC codes and encoding along with its Tanner graph representation is described. Then, a detailed description of the proposed construction algorithm is given. A Modified Shortest-Path (MSP) Algorithm of lower complexity is applied to obtain a code graph of the desired structure. The proposed algorithm works directly on the parity-check matrix of the LDPC code. The parity-check matrix of the code is constructed column by column subject to the bit-degree and girth constraints. Using the proposed algorithm, both regular and irregular LDPC codes have been constructed. Furthermore, not only have the girth been improved but also the rate of LDPC codes. Finally, by simulation results the constructed codes were shown to perform well over an additive white Gaussian noise (AWGN) channel.

National Radio Science Conference•Jan 1, 2009•1 citation

Efficient Construction for QC-LDPC Convolutional Codes with Periodic Bit-Filling

Ming Zhao, Zhipeng Liu, Ling Zhao

QC-LDPC-C (Quasi-Cyclic Low Density Parity-Check Convolutional) codes are with low encoding and decoding complexity and can achieve decoding performance approaching the Shannon limit. However, the construction of the parity check matrices need to be free of the length-4 cycles, and the computational complexity of direct construction will increase exponentially without considering the characteristics of the matrices. The construction for QC-LDPC-C codes with periodic bit-filling method is proposed. With the periodicity of the base check matrix, the proposed method firstly fills the deterministic submatrices to realize fast encoding; then it avoids all possible length-4 cycles by periodic filling in the construction of random submatrices. Thus the base check matrix without cycles of length-4 can be obtained, and the girth of expanded check matrix is at least 6. LDPC-C codes with different parameters are used to compare with the constructed QC-LDPC codes. Experimental results show that the codes constructed with proposed method can achieve better performance and lower encoding and decoding complexity.

IEEE International Conference on Computer and Communication Engineering Technology (CCET)•Aug 1, 2018•1 citation
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.
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.
There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.
Based on cycle search algorithm and Progressive Edge Growth(PEG) algorithm,this paper proposes a method to construct quasi-cyclic Low-density Parity Check(LDPC) codes with big girth and linear-encoding complexity.A parity-check matrix with a form of approximate lower triangle structure is designed to achieve iterative encoding with linear-encoding complexity.PEG algorithm is used to construct the base matrix and the cycle search algorithm is used to optimize the cycle distribution.And a fast encoding method is proposed.Experimental results show that the LDPC codes constructed with the proposed method can avoid error floor and achieve better BER performance than Tanner-QC-LDPC codes and equivalent BER performance to the ones of random codes.
Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. \nThis thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. \nRow-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. \nQuasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. \nDecoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing \nthe starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. \nTechniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques.
In this paper, a method for constructing Low-Density Parity-Check (LDPC) codes of good performance in terms of Bit Error Rate (BER) using a computer search algorithm is presented. First, LDPC codes and encoding along with its Tanner graph representation is described. Then, a detailed description of the proposed construction algorithm is given. A Modified Shortest-Path (MSP) Algorithm of lower complexity is applied to obtain a code graph of the desired structure. The proposed algorithm works directly on the parity-check matrix of the LDPC code. The parity-check matrix of the code is constructed column by column subject to the bit-degree and girth constraints. Using the proposed algorithm, both regular and irregular LDPC codes have been constructed. Furthermore, not only have the girth been improved but also the rate of LDPC codes. Finally, by simulation results the constructed codes were shown to perform well over an additive white Gaussian noise (AWGN) channel.
QC-LDPC-C (Quasi-Cyclic Low Density Parity-Check Convolutional) codes are with low encoding and decoding complexity and can achieve decoding performance approaching the Shannon limit. However, the construction of the parity check matrices need to be free of the length-4 cycles, and the computational complexity of direct construction will increase exponentially without considering the characteristics of the matrices. The construction for QC-LDPC-C codes with periodic bit-filling method is proposed. With the periodicity of the base check matrix, the proposed method firstly fills the deterministic submatrices to realize fast encoding; then it avoids all possible length-4 cycles by periodic filling in the construction of random submatrices. Thus the base check matrix without cycles of length-4 can be obtained, and the girth of expanded check matrix is at least 6. LDPC-C codes with different parameters are used to compare with the constructed QC-LDPC codes. Experimental results show that the codes constructed with proposed method can achieve better performance and lower encoding and decoding complexity.