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

Asilomar Conference on Signals, Systems and Computers (ACSSC)

Multiple rate low-density parity-check codes with constant blocklength

Andres I. Vila Casado, Wen-Yen Weng, Richard D. Wesel

Published Mar 31, 2005• 23 citations
Publisher

Abstract

This paper presents a new method to design low-density parity-check codes for a variety of different rates that all share the same fundamental decoder architecture. Combining rows of the parity-check matrix for the lowest rate code produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. These LDPC codes also share the same variable degree distribution. The proposed design method maintains good graphical properties and hence low error floors for all rates. Furthermore, an imposed matrix structure facilitates a low complexity encoding and decoding of the codes.

DOI
10.1109/acssc.2004.1399517

Related papers

Multiple-rate low-density parity-check codes with constant blocklength

Andres I. Vila Casado, Wen-Yen Weng, Stefano Valle +1 more

This paper describes and analyzes low-density parity-check code families that support variety of different rates while maintaining the same fundamental decoder architecture. Such families facilitate the decoding hardware design and implementation for applications that require communication at different rates, for example to adapt to changing channel conditions. Combining rows of the lowest-rate parity-check matrix produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. This approach is compatible with well known techniques that allow low-complexity encoding and parallel decoding of these LDPC codes. This technique also allows the design of programmable analog LDPC decoders. The proposed design method maintains good graphical properties and hence low error floors for all rates.

IEEE Transactions on Communications•Jan 1, 2009•43 citations

Low-density parity-check codes: properties and constructions

Sarah J. Johnson

Introduction The construction of binary low-density parity-check (LDPC) codes simply involves replacing a small number of the values in an all-zeros matrix by 1s in such a way that the rows and columns have the required degree distribution. In many cases, randomly allocating the entries in H will produce a reasonable LDPC code. However, the construction of H can affect the performance of the sum–product decoder, significantly so for some codes, and also the implementation complexity of the code. While there is no one recipe for a “good” LDPC code, there are a number of principles that inform the code designer. The first obvious decisions are which degree distribution to choose and how to construct the matrix with the chosen degrees, i.e. pseudo-randomly or with some sort of structure. Whichever construction is chosen, the features to consider include the girth of the Tanner graph and the minimum distance of the code. In this chapter we will discuss those properties of an LDPC code that affect its iterative decoding performance and then present the common construction methods used to produce codes with the preferred properties. Following common practice in the field we will call the selection of the degree distributions for an LDPC code code design and the methods to assign the locations in the parity-check matrix for the 1 entries code construction .

Cambridge University Press eBooks•Nov 19, 2009•0 citations

An Expurgating-Based Method for Constructing Multi-Rate Non-Binary Quasi-Cyclic LDPC Codes

Xijin Mu, Gang Chen, Baoming Bai

This letter presents a new method for constructing the multi-rate non-binary quasi-cyclic low-density parity-check codes by expurgating a high-rate mother code. A matrix-theoretic approach is applied to design the parity-check matrices of the proposed codes. The resulting codes possess a quasi-cyclic structure, which is desirable for hardware implementations of the encoder and decoder. The codes can also be encoded directly with parity-check matrices due to the block dual-diagonal structure. Simulation results show that the codes can achieve good performance within a wide range of code rates both in the waterfall region and in the error-floor region.

IEEE Communications Letters•May 15, 2017•4 citations

Construction of multiple-rate quasi-cyclic LDPC codes via the hyperplane decomposing

Xueqin Jiang, Yier Yan, Moon Ho Lee

This paper presents an approach to the construction of multiple-rate quasi-cyclic low-density parity-check (LDPC) codes. Parity-check matrices of the proposed codes consist of q X q square submatrices. The block rows and block columns of the parity-check matrix correspond to the hyperplanes (μ-flats) and points in Euclidean geometries, respectively. By decomposing the μ -flats, we obtain LDPC codes of different code rates and a constant code length. The code performance is investigated in term of the bit error rate and compared with those of LDPC codes given in IEEE standards. Simulation results show that our codes perform very well and have low error floors over the additive white Gaussian noise channel.

Journal of Communications and Networks•Jun 1, 2011•2 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

Architecture of the modified Block-Type Low-Density parity-check code decoding design

Kuang-Hao Lin, KyungHi Chang, Sheng-Dong Wu

In this paper, a combined Low-Density Parity-Check (LDPC) code decoding design method, called modified Block-Type LDPC (B-LDPC), for realistic LDPC coding system architectures is presented. The B-LDPC code, which is a special class of quasi-cyclic LDPC (QC-LDPC), has an efficient encoding algorithm owing to the simple structure of their parity-check matrices. A proposed distribution of irregular parity-check matrix for the modified B-LDPC is developed so that we can obtain an area-efficient decoder design, good error correction performance, and achievable architecture implementation. The modified B-LDPC code decoding utilizes the iterative min-sum algorithm (MSA) and its decoding architecture design employs the non-overlapping operations of bit node unit (BNU) and check node unit (CNU). Different block matrix sizes for parity-check matrix can be adopted so that the modified B-LDPC code decoding improves the throughput without obvious performance degradation.

International Conference on Information, Communications & Signal Processing (ICICS)•Jan 1, 2007•1 citation
This paper presents a new method to design low-density parity-check codes for a variety of different rates that all share the same fundamental decoder architecture. Combining rows of the parity-check matrix for the lowest rate code produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. These LDPC codes also share the same variable degree distribution. The proposed design method maintains good graphical properties and hence low error floors for all rates. Furthermore, an imposed matrix structure facilitates a low complexity encoding and decoding of the codes.
This paper describes and analyzes low-density parity-check code families that support variety of different rates while maintaining the same fundamental decoder architecture. Such families facilitate the decoding hardware design and implementation for applications that require communication at different rates, for example to adapt to changing channel conditions. Combining rows of the lowest-rate parity-check matrix produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. This approach is compatible with well known techniques that allow low-complexity encoding and parallel decoding of these LDPC codes. This technique also allows the design of programmable analog LDPC decoders. The proposed design method maintains good graphical properties and hence low error floors for all rates.
Introduction The construction of binary low-density parity-check (LDPC) codes simply involves replacing a small number of the values in an all-zeros matrix by 1s in such a way that the rows and columns have the required degree distribution. In many cases, randomly allocating the entries in H will produce a reasonable LDPC code. However, the construction of H can affect the performance of the sum–product decoder, significantly so for some codes, and also the implementation complexity of the code. While there is no one recipe for a “good” LDPC code, there are a number of principles that inform the code designer. The first obvious decisions are which degree distribution to choose and how to construct the matrix with the chosen degrees, i.e. pseudo-randomly or with some sort of structure. Whichever construction is chosen, the features to consider include the girth of the Tanner graph and the minimum distance of the code. In this chapter we will discuss those properties of an LDPC code that affect its iterative decoding performance and then present the common construction methods used to produce codes with the preferred properties. Following common practice in the field we will call the selection of the degree distributions for an LDPC code code design and the methods to assign the locations in the parity-check matrix for the 1 entries code construction .
This letter presents a new method for constructing the multi-rate non-binary quasi-cyclic low-density parity-check codes by expurgating a high-rate mother code. A matrix-theoretic approach is applied to design the parity-check matrices of the proposed codes. The resulting codes possess a quasi-cyclic structure, which is desirable for hardware implementations of the encoder and decoder. The codes can also be encoded directly with parity-check matrices due to the block dual-diagonal structure. Simulation results show that the codes can achieve good performance within a wide range of code rates both in the waterfall region and in the error-floor region.
This paper presents an approach to the construction of multiple-rate quasi-cyclic low-density parity-check (LDPC) codes. Parity-check matrices of the proposed codes consist of q X q square submatrices. The block rows and block columns of the parity-check matrix correspond to the hyperplanes (μ-flats) and points in Euclidean geometries, respectively. By decomposing the μ -flats, we obtain LDPC codes of different code rates and a constant code length. The code performance is investigated in term of the bit error rate and compared with those of LDPC codes given in IEEE standards. Simulation results show that our codes perform very well and have low error floors over the additive white Gaussian noise channel.
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 combined Low-Density Parity-Check (LDPC) code decoding design method, called modified Block-Type LDPC (B-LDPC), for realistic LDPC coding system architectures is presented. The B-LDPC code, which is a special class of quasi-cyclic LDPC (QC-LDPC), has an efficient encoding algorithm owing to the simple structure of their parity-check matrices. A proposed distribution of irregular parity-check matrix for the modified B-LDPC is developed so that we can obtain an area-efficient decoder design, good error correction performance, and achievable architecture implementation. The modified B-LDPC code decoding utilizes the iterative min-sum algorithm (MSA) and its decoding architecture design employs the non-overlapping operations of bit node unit (BNU) and check node unit (CNU). Different block matrix sizes for parity-check matrix can be adopted so that the modified B-LDPC code decoding improves the throughput without obvious performance degradation.