Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

A Compact Construction for LDPC Codes using Permutation Polynomials

O.Y. Takeshita

Published Jul 1, 2006• 12 citations
Publisher

Abstract

A construction is proposed for low density parity check codes using quadratic permutation polynomials over finite integer rings. Graph isomorphisms and automorphisms are identified and used in an efficient search for good codes. Graphs with girth as large as 12 were found. Upper bounds on the minimum Hamming distance are found algorithmically. The bounds indicate that the minimum distance grows with block length. One of the new codes has a similar error performance as the best known PEG LDPC code. Finally, the new codes are quasi-cyclic

DOI
10.1109/isit.2006.261678

Related papers

A New Construction for LDPC Codes using Permutation Polynomials over Integer Rings

O.Y. Takeshita

A new construction is proposed for low density parity check (LDPC) codes using quadratic permutation polynomials over finite integer rings. The associated graphs for the new codes have both algebraic and pseudo-random nature, and the new codes are quasi-cyclic. Graph isomorphisms and automorphisms are identified and used in an efficient search for good codes. Graphs with girth as large as 12 were found. Upper bounds on the minimum Hamming distance are found both analytically and algorithmically. The bounds indicate that the minimum distance grows with block length. Near-codewords are one of the causes for error floors in LDPC codes; the new construction provides a good framework for studying near-codewords in LDPC codes. Nine example codes are given, and computer simulation results show the excellent error performance of these codes. Finally, connections are made between this new LDPC construction and turbo codes using interleavers generated by quadratic permutation polynomials.

arXiv:cs/0506091•Jun 24, 2005•11 citations

Low-Density Parity-Check Codes of High Girth from Permutation Polynomials

Tasawwar Hussain, Anthony Gómez-Fonseca, Tefjol Pllaha

Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely used in modern communication standards due to their simple structure and efficient encoder and decoder implementations. However, the commutativity of the circulant permutation matrices used in their construction significantly limits their girth and minimum distance, affecting iterative decoding performance. In this paper, we investigate protograph-based codes constructed using permutation polynomials of higher degree, focusing on a closed family of non-commuting binomial permutation polynomials that enables these constructions to exceed both of these girth and minimum distance upper bounds while maintaining a simple representation. Simulation results demonstrate improved decoding performance compared to constructions based on affine permutation polynomials, which include QC-LDPC codes.

arXiv:2610.03341•Oct 2, 2026•0 citations

Construction of quasi-cyclic low-density parity-check codes using Hamming codewords

Haijing Zhong, Shancheng Zhao, Li Chen +1 more

In this paper, we propose a new approach to construct quasi-cyclic low-density parity-check (QC-LDPC) codes using Hamming codewords of weight three, namely the HM-QC-LDPC codes. Thanks to the distance property of Hamming codes, length four cycles are avoided from the Tanner graph of the constructed codes, resulting in codes of girth six. This approach can be further extended to construct QC-LDPC codes of girth eight. Our numerical results show that the proposal has a better cycle profile than the progressive-edge-growth (PEG) constructed codes, and consequently prevails in performance. Moreover, the constructed QC-LDPC code prevails the LDPC code of the IEEE802.22 standard by 0.2 dB at the bit error rate (BER) of 10-8when the codeword length is within hundreds of bits, making it a promising candidate for scenarios where strict decoding latency is imposed.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 1, 2016•1 citation

Permutation-block LDPC codes: influence of Tanner-graph structure on minimum hamming distance

Benjamin Michael Thorn

Only since the mid-1990s, with the increase in computational power, has the\nimportance been realized regarding low-density parity-check (LDPC) codes as leading error\ncorrecting codes. The work in this thesis primarily studies LDPC codes that are de???ned by a\nparity-check matrix comprised of r _ r permutation matrix blocks, that is, permutation-block\nLDPC codes. More specifically, we study their minimum Hamming distance, as this is a\nparameter that affects the performance of linear codes, and thus LDPC codes.\nIt has been proven that there are upper bounds on the minimum Hamming distance of\nquasi-cyclic codes, de???ned by a parity-check matrix comprised of r _ r circulant matrix\nblocks, regardless of how large we allow r. However, we show that if general permutation\nmatrices are used instead of circulant matrices, we are able to exceed the bounds allowed by\nquasi-cyclic codes. Graphical representations of the codes, called Tanner-graphs, are used in\nproving many useful results regarding permutation-block LDPC codes and their minimum\nHamming distance. We show a characterization of the minimum Hamming distance of these\ncodes and we produce an algorithm for constructing permutation-block LDPC codes with\nlarge minimum Hamming distance.

•Jun 28, 2011•0 citations

Construction of block-LDPC codes based on quadratic permutation polynomials

Guan Wu, Liping Liang

A new block low-density parity-check (Block-LDPC) code based on quadratic permutation polynomials (QPPs) is proposed. The parity-check matrix of the Block-LDPC code is composed of a group of permutation submatrices that correspond to QPPs. The scheme provides a large range of implementable LDPC codes. Indeed, the most popular quasi-cyclic LDPC (QC-LDPC) codes are just a subset of this scheme. Simulation results indicate that the proposed scheme can offer similar error performance and implementation complexity as the popular QC-LDPC codes.

Journal of Communications and Networks•Apr 1, 2015•7 citations

A Compact Construction for Nonbinary LDPC Codes Using Permutation Polynomials

Tao Xiong, Hongyu Zhao

A compact construction for nonbinary low-density parity-check (LDPC) codes over GF(q) (q>2) using permutation polynomials (PPs) is proposed in this paper. Following the previous compact construction for binary LDPC codes using quadratic permutation polynomials (QPPs) over integer rings, a QPP whose coefficients are chosen for maximizing the girth is used for determining all the positions of nonzero elements in the parity check matrix of a regular nonbinary LDPC code. Moreover, it is proposed to use a linear permutation polynomial (LPP) over GF(q) for determining the distribution of nonzero elements of GF(q) at the nonzero positions. Computer simulation results of LDPC codes over GF(8) have shown that the propose compact construction can attain similar error correction performance with Mackay's random construction for nonbinary LDPC codes.

International Conference on Wireless Communications, Networking and Mobile Computing•Sep 1, 2012•1 citation
A construction is proposed for low density parity check codes using quadratic permutation polynomials over finite integer rings. Graph isomorphisms and automorphisms are identified and used in an efficient search for good codes. Graphs with girth as large as 12 were found. Upper bounds on the minimum Hamming distance are found algorithmically. The bounds indicate that the minimum distance grows with block length. One of the new codes has a similar error performance as the best known PEG LDPC code. Finally, the new codes are quasi-cyclic
A new construction is proposed for low density parity check (LDPC) codes using quadratic permutation polynomials over finite integer rings. The associated graphs for the new codes have both algebraic and pseudo-random nature, and the new codes are quasi-cyclic. Graph isomorphisms and automorphisms are identified and used in an efficient search for good codes. Graphs with girth as large as 12 were found. Upper bounds on the minimum Hamming distance are found both analytically and algorithmically. The bounds indicate that the minimum distance grows with block length. Near-codewords are one of the causes for error floors in LDPC codes; the new construction provides a good framework for studying near-codewords in LDPC codes. Nine example codes are given, and computer simulation results show the excellent error performance of these codes. Finally, connections are made between this new LDPC construction and turbo codes using interleavers generated by quadratic permutation polynomials.
Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely used in modern communication standards due to their simple structure and efficient encoder and decoder implementations. However, the commutativity of the circulant permutation matrices used in their construction significantly limits their girth and minimum distance, affecting iterative decoding performance. In this paper, we investigate protograph-based codes constructed using permutation polynomials of higher degree, focusing on a closed family of non-commuting binomial permutation polynomials that enables these constructions to exceed both of these girth and minimum distance upper bounds while maintaining a simple representation. Simulation results demonstrate improved decoding performance compared to constructions based on affine permutation polynomials, which include QC-LDPC codes.
In this paper, we propose a new approach to construct quasi-cyclic low-density parity-check (QC-LDPC) codes using Hamming codewords of weight three, namely the HM-QC-LDPC codes. Thanks to the distance property of Hamming codes, length four cycles are avoided from the Tanner graph of the constructed codes, resulting in codes of girth six. This approach can be further extended to construct QC-LDPC codes of girth eight. Our numerical results show that the proposal has a better cycle profile than the progressive-edge-growth (PEG) constructed codes, and consequently prevails in performance. Moreover, the constructed QC-LDPC code prevails the LDPC code of the IEEE802.22 standard by 0.2 dB at the bit error rate (BER) of 10-8when the codeword length is within hundreds of bits, making it a promising candidate for scenarios where strict decoding latency is imposed.
Only since the mid-1990s, with the increase in computational power, has the\nimportance been realized regarding low-density parity-check (LDPC) codes as leading error\ncorrecting codes. The work in this thesis primarily studies LDPC codes that are de???ned by a\nparity-check matrix comprised of r _ r permutation matrix blocks, that is, permutation-block\nLDPC codes. More specifically, we study their minimum Hamming distance, as this is a\nparameter that affects the performance of linear codes, and thus LDPC codes.\nIt has been proven that there are upper bounds on the minimum Hamming distance of\nquasi-cyclic codes, de???ned by a parity-check matrix comprised of r _ r circulant matrix\nblocks, regardless of how large we allow r. However, we show that if general permutation\nmatrices are used instead of circulant matrices, we are able to exceed the bounds allowed by\nquasi-cyclic codes. Graphical representations of the codes, called Tanner-graphs, are used in\nproving many useful results regarding permutation-block LDPC codes and their minimum\nHamming distance. We show a characterization of the minimum Hamming distance of these\ncodes and we produce an algorithm for constructing permutation-block LDPC codes with\nlarge minimum Hamming distance.
A new block low-density parity-check (Block-LDPC) code based on quadratic permutation polynomials (QPPs) is proposed. The parity-check matrix of the Block-LDPC code is composed of a group of permutation submatrices that correspond to QPPs. The scheme provides a large range of implementable LDPC codes. Indeed, the most popular quasi-cyclic LDPC (QC-LDPC) codes are just a subset of this scheme. Simulation results indicate that the proposed scheme can offer similar error performance and implementation complexity as the popular QC-LDPC codes.
A compact construction for nonbinary low-density parity-check (LDPC) codes over GF(q) (q>2) using permutation polynomials (PPs) is proposed in this paper. Following the previous compact construction for binary LDPC codes using quadratic permutation polynomials (QPPs) over integer rings, a QPP whose coefficients are chosen for maximizing the girth is used for determining all the positions of nonzero elements in the parity check matrix of a regular nonbinary LDPC code. Moreover, it is proposed to use a linear permutation polynomial (LPP) over GF(q) for determining the distribution of nonzero elements of GF(q) at the nonzero positions. Computer simulation results of LDPC codes over GF(8) have shown that the propose compact construction can attain similar error correction performance with Mackay's random construction for nonbinary LDPC codes.