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

Some new Algebraic constructions of Codes from Graphs which are good Expanders

Christine A. Kelley, Joachim Rosenthal, Deepak Sridhara

Published Jan 1, 2003• 3 citations
OpenAlex

Abstract

The design of LDPC codes based on a class of expander graphs is investigated. Graph products, such as the zig-zag product [9], of smaller expander graphs have been shown to yield larger expanders. LDPC codes are designed based on the zigzag product graph of two component Cayley graphs. The results for specific cases simulated reveal that the resulting LDPC codes compare well with other random LDPC codes at short block lengths – suggesting that product graphs form yet another avenue to pursue in the design of codes over graphs. 1

Related papers

Pseudocodewords, Expander Graphs, and the Algebraic Construction of Low-density Parity-check Codes

Christine A. Kelley

In 1948, Claude Shannon provided a sound mathematical foundation for communication, and proved the existence of good codes. Low-density parity-check (LDPC) codes are a family of error-correcting codes that achieve reliable performance (i.e., arbitrarily low probability of decoding error) near the Shannon-limit when decoded iteratively via very efficient graph-based message-passing decoders, the complexity of which grows only linearly in the block-length. Despite their tremendous success, LDPC codes lack a strong theoretical foundation and few explicit constructions of them are known that outperform their random counterparts. The first part of this thesis investigates how the structure of a graph representing an LDPC code affects the decoding performance. In particular, lower bounds on the minimum pseudocodeword weight, a key parameter in predicting iterative decoding performance, are obtained which link the performance of the code to the structural properties of its graph. One bound is a tree bound and is extended to generalized and p-ary LDPC codes. To this end, a suitable definition of pseudocodeword weight is derived for the p-ary symmetric channel. Moreover, the relationship between pseudocodeword weight distributions and different graph representations is examined. Bounds on the minimum pseudocodeword weight are also presented for several classes of expander codes based on the eigenvalues of the adjacency matrix of the Tanner graph. The second part of this thesis constructs LDPC codes having desirable properties. The first construction is combinatorial and uses permutations and mutually orthogonal Latin squares. One type results in the well-known projective-geometrybased LDPC codes. Another type yields a new family of codes having comparable parameters and pseudocodeword weights suitable for iterative decoding. The resulting performance of these codes is superior in comparison with that of comparable random LDPC codes, a feature attributed to the lack of low-weight bad pseudocodewords. For the second construction, unbalanced expander graphs are obtained by modifying the original zig-zag graph product to take bi-regular expander graphs as components, with suitable constraints on the degrees. Graphs resulting from the zig-zag and replacement product graphs are then used in the design of generalized LDPC codes having compact representation and pseudocodeword weights lower-bounded by the eigenvalue bounds.

•Jan 1, 2006•0 citations

LDPC Codes Based on Combinatorial Designs, Graphs, and Superposition

W.E. Ryan, Shu Hwa Lin

Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs, were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding.

Cambridge University Press eBooks•Sep 17, 2009•1 citation

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

Conclusion and Remarks

Juane Li, Shu Lin, Khaled Abdel-Ghaffar +2 more

In this book, we unified several major types of LDPC code constructions using a single framework, namely, the SP-construction. Under this framework, the constructions of all these types of LDPC codes can be viewed as basically algebraic. In general, algebraically constructed LDPC codes have good overall performance in terms of both waterfall and error-floor performance, as well as a fast rate of decoding convergence. The unification of all these constructions may lead to better designs, and construction of high performing and more easily implementable codes for applications in next generations of communication and data storage systems. This book consists of seven parts. In the first part (Chapter 4), we gave an algebraic interpretation of the protograph-based (PTG-based) construction of LDPC codes and presented a simple and novel algebraic method for constructing PTG-LDPC codes. The proposed algebraic method is equivalent to the graphical copy-and-permute operation and uses a simple matrix decomposition-and-replacement process to construct PTG-LDPC codes. The algebraic method is based on decomposition of a small base matrix and is very flexible in code construction. The constructed codes perform well as supported by examples and simulation results. However, how to design decomposition base matrices so that the resultant PTG-LDPC codes can perform close to their decoding thresholds is still an unresolved problem which needs further investigation. In the second part of the book (Chapters 5 and 6), we re-interpreted the SP-construction of LDPC codes, one of the earliest methods for algebraic construction of LDPC codes, in a broader context, from both algebraic and graph-theoretic perspectives. We showed that the PTG-LDPC code construction is a special case of SP-construction. New constructions of RC-constrained base matrices and PW-RC-constrained replacement sets of matrices for the SP-construction of LDPC codes were presented. In Chapter 5, we showed that two major ensembles of SP-LDPC codes for a given rate can be formed. One ensemble is equivalent to the ensemble of PTG-LDPC codes. In forming this ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are regular. Since this ensemble is equivalent to the ensemble of PTG-LDPC codes, the SP-LDPC codes in this ensemble have good asymptotic performance and structural properties. For the other ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are not regular.

Cambridge University Press eBooks•Dec 1, 2016•0 citations

Low-rate non-binary hybrid LDPC codes

Lucile Sassatelli, David Declercq, Charly Poulliat

In this paper, we use the class of non-binary hybrid LDPC codes to design very efficient low rate codes. To this end, we consider both asymptotic and finite length designs. First, we present an asymptotic analysis to design hybrid LDPC codes distributions and we explicit the cases when it is useful to use it. Then, by optimizing the algebraic properties of some topologies related to the Tanner graph, we design finite length codes. These codes show significant performance improvements both in the waterfall and in the error floor regions, in comparison with existing state-of-the-art low rate coding schemes, like turbo Hadamard or parallel concatenated Zigzag Hadamard codes, and with no increase of complexity. In particular, the minimum distance of low rate hybrid LDPC codes is by far greater than the ones of previously mentioned codes.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•2 citations

Short Protograph-Based LDPC Codes

D. Divsalar, Sam Dolinar, Christopher Jones

In this paper we design protograph-based LDPC codes with short block sizes. Mainly we consider rate 1/2 codes with input block sizes 64, 128, and 256 bits. To simplify the encoder and decoder implementations for high data rate transmission, the structure of the codes is based on protographs and circulants. These codes are designed for short block sizes based on maximizing the minimum distance and stopping set size subject to a constraint on the maximum variable node degree. In particular, we consider codes with variable node degrees between 3 and 5. Increasing the node degree leads to larger minimum distances, at the expense of smaller girth. Therefore, there is a trade-off between undetected error rate performance (improved by increasing minimum distance) and the degree of sub-optimality of the iterative decoders typically used (which are adversely affected by graph loops). Various LDPC codes are compared and simulation results are provided.

IEEE Military Communications Conference (MILCOM)•Oct 1, 2007•23 citations
The design of LDPC codes based on a class of expander graphs is investigated. Graph products, such as the zig-zag product [9], of smaller expander graphs have been shown to yield larger expanders. LDPC codes are designed based on the zigzag product graph of two component Cayley graphs. The results for specific cases simulated reveal that the resulting LDPC codes compare well with other random LDPC codes at short block lengths – suggesting that product graphs form yet another avenue to pursue in the design of codes over graphs. 1
In 1948, Claude Shannon provided a sound mathematical foundation for communication, and proved the existence of good codes. Low-density parity-check (LDPC) codes are a family of error-correcting codes that achieve reliable performance (i.e., arbitrarily low probability of decoding error) near the Shannon-limit when decoded iteratively via very efficient graph-based message-passing decoders, the complexity of which grows only linearly in the block-length. Despite their tremendous success, LDPC codes lack a strong theoretical foundation and few explicit constructions of them are known that outperform their random counterparts. The first part of this thesis investigates how the structure of a graph representing an LDPC code affects the decoding performance. In particular, lower bounds on the minimum pseudocodeword weight, a key parameter in predicting iterative decoding performance, are obtained which link the performance of the code to the structural properties of its graph. One bound is a tree bound and is extended to generalized and p-ary LDPC codes. To this end, a suitable definition of pseudocodeword weight is derived for the p-ary symmetric channel. Moreover, the relationship between pseudocodeword weight distributions and different graph representations is examined. Bounds on the minimum pseudocodeword weight are also presented for several classes of expander codes based on the eigenvalues of the adjacency matrix of the Tanner graph. The second part of this thesis constructs LDPC codes having desirable properties. The first construction is combinatorial and uses permutations and mutually orthogonal Latin squares. One type results in the well-known projective-geometrybased LDPC codes. Another type yields a new family of codes having comparable parameters and pseudocodeword weights suitable for iterative decoding. The resulting performance of these codes is superior in comparison with that of comparable random LDPC codes, a feature attributed to the lack of low-weight bad pseudocodewords. For the second construction, unbalanced expander graphs are obtained by modifying the original zig-zag graph product to take bi-regular expander graphs as components, with suitable constraints on the degrees. Graphs resulting from the zig-zag and replacement product graphs are then used in the design of generalized LDPC codes having compact representation and pseudocodeword weights lower-bounded by the eigenvalue bounds.
Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs, were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding.
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 book, we unified several major types of LDPC code constructions using a single framework, namely, the SP-construction. Under this framework, the constructions of all these types of LDPC codes can be viewed as basically algebraic. In general, algebraically constructed LDPC codes have good overall performance in terms of both waterfall and error-floor performance, as well as a fast rate of decoding convergence. The unification of all these constructions may lead to better designs, and construction of high performing and more easily implementable codes for applications in next generations of communication and data storage systems. This book consists of seven parts. In the first part (Chapter 4), we gave an algebraic interpretation of the protograph-based (PTG-based) construction of LDPC codes and presented a simple and novel algebraic method for constructing PTG-LDPC codes. The proposed algebraic method is equivalent to the graphical copy-and-permute operation and uses a simple matrix decomposition-and-replacement process to construct PTG-LDPC codes. The algebraic method is based on decomposition of a small base matrix and is very flexible in code construction. The constructed codes perform well as supported by examples and simulation results. However, how to design decomposition base matrices so that the resultant PTG-LDPC codes can perform close to their decoding thresholds is still an unresolved problem which needs further investigation. In the second part of the book (Chapters 5 and 6), we re-interpreted the SP-construction of LDPC codes, one of the earliest methods for algebraic construction of LDPC codes, in a broader context, from both algebraic and graph-theoretic perspectives. We showed that the PTG-LDPC code construction is a special case of SP-construction. New constructions of RC-constrained base matrices and PW-RC-constrained replacement sets of matrices for the SP-construction of LDPC codes were presented. In Chapter 5, we showed that two major ensembles of SP-LDPC codes for a given rate can be formed. One ensemble is equivalent to the ensemble of PTG-LDPC codes. In forming this ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are regular. Since this ensemble is equivalent to the ensemble of PTG-LDPC codes, the SP-LDPC codes in this ensemble have good asymptotic performance and structural properties. For the other ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are not regular.
In this paper, we use the class of non-binary hybrid LDPC codes to design very efficient low rate codes. To this end, we consider both asymptotic and finite length designs. First, we present an asymptotic analysis to design hybrid LDPC codes distributions and we explicit the cases when it is useful to use it. Then, by optimizing the algebraic properties of some topologies related to the Tanner graph, we design finite length codes. These codes show significant performance improvements both in the waterfall and in the error floor regions, in comparison with existing state-of-the-art low rate coding schemes, like turbo Hadamard or parallel concatenated Zigzag Hadamard codes, and with no increase of complexity. In particular, the minimum distance of low rate hybrid LDPC codes is by far greater than the ones of previously mentioned codes.
In this paper we design protograph-based LDPC codes with short block sizes. Mainly we consider rate 1/2 codes with input block sizes 64, 128, and 256 bits. To simplify the encoder and decoder implementations for high data rate transmission, the structure of the codes is based on protographs and circulants. These codes are designed for short block sizes based on maximizing the minimum distance and stopping set size subject to a constraint on the maximum variable node degree. In particular, we consider codes with variable node degrees between 3 and 5. Increasing the node degree leads to larger minimum distances, at the expense of smaller girth. Therefore, there is a trade-off between undetected error rate performance (improved by increasing minimum distance) and the degree of sub-optimality of the iterative decoders typically used (which are adversely affected by graph loops). Various LDPC codes are compared and simulation results are provided.