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

EURASIP Journal on Wireless Communications and Networking

Structured LDPC Codes over Integer Residue Rings

Elisa Mo, M.A. Armand

Published Jun 12, 2008• 1 citation
Publisher

Abstract

This paper presents a new class of low-density parity-check (LDPC) codes over represented by regular, structured Tanner graphs. These graphs are constructed using Latin squares defined over a multiplicative group of a Galois ring, rather than a finite field. Our approach yields codes for a wide range of code rates and more importantly, codes whose minimum pseudocodeword weights equal their minimum Hamming distances. Simulation studies show that these structured codes, when transmitted using matched signal sets over an additive-white-Gaussian-noise channel, can outperform their random counterparts of similar length and rate.

DOI
10.1155/2008/598401

Related papers

Structured LDPC codes from permutation matrices free of small trapping sets

Dung Viet Nguyen, Bane V. Vasic, Michael W. Marcellin +1 more

This paper introduces a class of structured low-density parity-check (LDPC) codes whose parity check matrices are arrays of permutation matrices. The permutation matrices are obtained from Latin squares and form a finite field under some matrix operations. They are chosen so that the Tanner graphs do not contain subgraphs harmful to iterative decoding algorithms. The construction of column-weight-three codes is presented. Although the codes are optimized for the Gallager A/B algorithm over the binary symmetric channel (BSC), their error performance is very good on the additive white Gaussian noise channel (AWGNC) as well.

arXiv:1004.1198•IEEE Information Theory Workshop (ITW)•Aug 1, 2010•25 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

Analysis of the cycle-structure of LDPC codes based on Latin squares

Olgica Milenković, Stefan Laendner

In this paper, we introduce a family of structured low-density parity-check (LDPC) codes based on a class of idempotent, symmetric Latin and modified Latin squares. The parity-check matrices of the codes have a block structure with permutation blocks which insures that both their corresponding girth and minimum distance are at least equal to six. The storage requirement for codes from this class is reduced to only one parameter. We also propose a structured method for shortening the codes by removing columns that break a large number of cycles of length six. The storage requirements for the codes obtained using the described procedure consist in memorizing only two integers, while their performance under iterative decoding matches that of random-like codes of comparable length.

International Conference on Communications•Jan 1, 2004•9 citations

Tree-Based Construction of LDPC Codes Having Good Pseudocodeword Weights

Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal

We present a tree-based construction of low-density parity-check (LDPC) codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a$d$-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degrees$d=p^s$and$d = p^s+1$, for$p$a prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes; the other codes presented are new. We also present some bounds on pseudocodeword weight for$p$-ary LDPC codes. Treating these codes as$p$-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite-geometry LDPC codes where$p > 2$.

IEEE Transactions on Information Theory•Apr 1, 2007•18 citations

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

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
This paper presents a new class of low-density parity-check (LDPC) codes over represented by regular, structured Tanner graphs. These graphs are constructed using Latin squares defined over a multiplicative group of a Galois ring, rather than a finite field. Our approach yields codes for a wide range of code rates and more importantly, codes whose minimum pseudocodeword weights equal their minimum Hamming distances. Simulation studies show that these structured codes, when transmitted using matched signal sets over an additive-white-Gaussian-noise channel, can outperform their random counterparts of similar length and rate.
This paper introduces a class of structured low-density parity-check (LDPC) codes whose parity check matrices are arrays of permutation matrices. The permutation matrices are obtained from Latin squares and form a finite field under some matrix operations. They are chosen so that the Tanner graphs do not contain subgraphs harmful to iterative decoding algorithms. The construction of column-weight-three codes is presented. Although the codes are optimized for the Gallager A/B algorithm over the binary symmetric channel (BSC), their error performance is very good on the additive white Gaussian noise channel (AWGNC) as well.
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.
In this paper, we introduce a family of structured low-density parity-check (LDPC) codes based on a class of idempotent, symmetric Latin and modified Latin squares. The parity-check matrices of the codes have a block structure with permutation blocks which insures that both their corresponding girth and minimum distance are at least equal to six. The storage requirement for codes from this class is reduced to only one parameter. We also propose a structured method for shortening the codes by removing columns that break a large number of cycles of length six. The storage requirements for the codes obtained using the described procedure consist in memorizing only two integers, while their performance under iterative decoding matches that of random-like codes of comparable length.
We present a tree-based construction of low-density parity-check (LDPC) codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating addd-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degreesd=psd=p^sd=psandd=ps+1d = p^s+1d=ps+1, forpppa prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes; the other codes presented are new. We also present some bounds on pseudocodeword weight forppp-ary LDPC codes. Treating these codes asppp-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite-geometry LDPC codes wherep>2p > 2p>2.
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.
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.