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

Polygon Semi Regular Low Density Parity Check Codes

khalil shah

Published Jun 10, 2010• 0 citations
OpenAlex

Abstract

I proposed a new algorithm for the allocation of g- values to the binary vectors. An infinite family of simple graphs in generated by placing copies of polygons in parallel such that degree of each vertex is three. We call them polygon graphs. Since polygon graphs are bipartite therefore they can be used as Tanner graphs to generate low density parity check codes. An incidence structure defined on these polygon graphs in named as polygon semi design. Rows of incidence matrix are reduced by deleting rows from the bottom one by one. These matrices serve as parity check matrices to define low density parity check codes for various dimensions. Size of the stopping sets in the associated Tanner graphs of LDPC codes determine the performance of codes over binary erasure channel. The generated polygon semi regular LDPC codes are simulated and their performance is presented by BER. plots. There exists polygon semi regular LDPC codes e.g. (25,4,17), (49,6,19) etc. The LDPC codes of girth 6 presented by Vera Pless has parameters (25,4,10), (49,6,14). This shows a significant improvement in terms of minimum distance.

Related papers

LDPC Codes From Generalized Polygons

Zhouding Liu, Dimitris A. Pados

We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight, all codewords have even Hamming weight. When the generalized polygon has in addition an equal number of points and lines, we see that the nonregular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum-distance bound is presented for codes from nonregular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity-check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate (BER) performance when decoding is carried out via low-complexity variants of belief propagation.

IEEE Transactions on Information Theory•Oct 24, 2005•41 citations

Generalized quad, hex, and octagon LDPC codes

Zhenyu Liu, Dimitris A. Pados

We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight all codewords have even Hamming weight. When the generalized polygon has in addition equal number of points and lines, we see that the non-regular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum distance bound is presented for codes from non-regular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate performance when decoding is carried out via low complexity variants of belief propagation.

Globecom•Jan 1, 2005•2 citations

Coset graphs for low-density parity check codes: performance on the binary erasure channel

Josef Lauri, Cen Jung Tjhai

The authors show that a popular way of constructing quasi-cyclic low-density parity check (LDPC) codes is a special case of a construction which is common in graph theory and group theory. It is shown that a generalisation of this construction as coset graphs produces (dv, dc)-regular LDPC codes that have an advantage in terms of the minimum stopping set size compared to quasi-cyclic LDPC codes. A (dv, dc)-regular quasi-cyclic LDPC code cannot have minimum stopping set size larger than (dv+1)!. However, by using coset graphs, a (3, 5)-regular LDPC code with minimum stopping set size of 28 and a (3, 4)-regular LDPC code with minimum stopping set size larger than 32 have been obtained. In addition, the idea of coset graphs also provides a compact algebraic way of describing bipartite graph and the associated parity-check matrix of an LDPC code. Simulation results of iterative decoding of the coset graphs LDPC codes over the binary erasure channel show that some of the codes converge well and based on the truncated stopping set distributions of the codes, which are exhaustively and efficiently enumerated, the error-floor of the codes at low probability of erasure is estimated.

IET Communications•Mar 25, 2011•0 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

Regular and irregular progressive edge-growth tanner graphs

Xiao-Yu Hu, Evangelos S. Eleftheriou, Donald M. Arnold

We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2005•1,489 citations

The Design of Structured Low-Density Parity-Check Codes With Large Girth

Jing Long

This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.

Chinese Journal of Computers•Jan 1, 2007•1 citation
I proposed a new algorithm for the allocation of g- values to the binary vectors. An infinite family of simple graphs in generated by placing copies of polygons in parallel such that degree of each vertex is three. We call them polygon graphs. Since polygon graphs are bipartite therefore they can be used as Tanner graphs to generate low density parity check codes. An incidence structure defined on these polygon graphs in named as polygon semi design. Rows of incidence matrix are reduced by deleting rows from the bottom one by one. These matrices serve as parity check matrices to define low density parity check codes for various dimensions. Size of the stopping sets in the associated Tanner graphs of LDPC codes determine the performance of codes over binary erasure channel. The generated polygon semi regular LDPC codes are simulated and their performance is presented by BER. plots. There exists polygon semi regular LDPC codes e.g. (25,4,17), (49,6,19) etc. The LDPC codes of girth 6 presented by Vera Pless has parameters (25,4,10), (49,6,14). This shows a significant improvement in terms of minimum distance.
We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight, all codewords have even Hamming weight. When the generalized polygon has in addition an equal number of points and lines, we see that the nonregular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum-distance bound is presented for codes from nonregular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity-check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate (BER) performance when decoding is carried out via low-complexity variants of belief propagation.
We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight all codewords have even Hamming weight. When the generalized polygon has in addition equal number of points and lines, we see that the non-regular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum distance bound is presented for codes from non-regular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate performance when decoding is carried out via low complexity variants of belief propagation.
The authors show that a popular way of constructing quasi-cyclic low-density parity check (LDPC) codes is a special case of a construction which is common in graph theory and group theory. It is shown that a generalisation of this construction as coset graphs produces (dv, dc)-regular LDPC codes that have an advantage in terms of the minimum stopping set size compared to quasi-cyclic LDPC codes. A (dv, dc)-regular quasi-cyclic LDPC code cannot have minimum stopping set size larger than (dv+1)!. However, by using coset graphs, a (3, 5)-regular LDPC code with minimum stopping set size of 28 and a (3, 4)-regular LDPC code with minimum stopping set size larger than 32 have been obtained. In addition, the idea of coset graphs also provides a compact algebraic way of describing bipartite graph and the associated parity-check matrix of an LDPC code. Simulation results of iterative decoding of the coset graphs LDPC codes over the binary erasure channel show that some of the codes converge well and based on the truncated stopping set distributions of the codes, which are exhaustively and efficiently enumerated, the error-floor of the codes at low probability of erasure is estimated.
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 .
We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.
This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.