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

I. INTRODUCTION

• QC-LDPC codes are used in industry standards for structural benefits that support low-complexity encoding and efficient decoder design.The cited examples are feedback shift-register encoding and memory-efficient partially parallel decoding.Source: §I · p. 1
• Commutativity in QC-LDPC constructions imposes upper bounds on minimum distance and Tanner-graph girth, properties relevant to iterative-decoding performance.Short cycles and related graph structures matter because decoding iterations introduce correlation and error floors.Source: §I · p. 1
• Higher-degree permutation polynomials are proposed for protograph-based codes to avoid the limits of commuting permutation matrices while retaining a compact representation.The stated goal is improved minimum-distance and girth properties with efficient implementation.Source: §I · p. 1
• The paper develops its construction and analysis across monomial and non-commuting binomial polynomials, then reports simulations against affine-polynomial constructions.The paper outline identifies large-girth construction and improved simulated performance as later topics.Source: §I · p. 1

A. Protograph-based Codes

• The construction replaces each protograph biadjacency-matrix entry with an N × N permutation matrix to form the scalar parity-check matrix H.This section focuses on an all-ones protograph, where each entry is 1, for space constraints.Source: A. Protograph-based Codes · pp. 1–2
• Interpreting H as a biadjacency matrix yields the Tanner graph representing the protograph-based code.Its vertices and edges correspond to the nodes and connections encoded by H.Source: A. Protograph-based Codes · p. 2
• A TBC walk is a closed walk with no immediate backtracking and no tail, while a cycle has distinct vertices and edges.The girth is the length of the shortest cycle.Source: A. Protograph-based Codes · p. 2

B. Permutation Polynomials

• A permutation polynomial over R induces a permutation of R and corresponds to a permutation matrix used in the polynomial parity-check matrix.For the all-ones protograph, replacing each polynomial with its permutation matrix gives the scalar parity-check matrix.Source: B. Permutation Polynomials · p. 2
• QC-LDPC codes correspond to monic affine polynomials x + a, while APM-LDPC codes use linear polynomials ax + b.For APM-LDPC codes, ax + b is a permutation polynomial exactly when gcd(a, N) = 1.Source: B. Permutation Polynomials · p. 2

C. Girth of Protograph-based Codes

• A TBC walk of length 2l in the protograph yields a 2l-cycle in the Tanner graph if its alternating product of associated permutation matrices has a fixed point.The product uses each odd-indexed matrix followed by the transpose of the next even-indexed matrix.Source: C. Girth of Protograph-based Codes · p. 2
• To ensure target girth g, the fixed-point condition must be checked for every protograph TBC walk of length less than g.When the lifting factor N is large, evaluating the matrix products for all such walks becomes computationally prohibitive.Source: C. Girth of Protograph-based Codes · p. 2
• The matrix-product test can instead be expressed as a composition of the corresponding permutation polynomials, whose having a fixed point signals the cycle.The composition alternates inverse polynomials with the original polynomials along the walk.Source: C. Girth of Protograph-based Codes · p. 2

• Two composition- and inverse-closed permutation-polynomial families facilitate girth and cycle analysis.Source: §III · p. 2

A. Monomials and Girth and Minimum Distance Upper Bounds

• For the all-ones protograph, monomials x^lij over Fq are permutation polynomials when gcd(lij, q −1) = 1.Source: A. Monomials and Girth and Minimum… · p. 2
• 12-cycles are unavoidable for monomial parity-check matrices when nc ≥2 and nv ≥3.A 2×3 submatrix yields a TBC walk whose associated composition has fixed points.Source: A. Monomials and Girth and Minimum… · p. 3
• The minimum distance of a monomial-based code is upper bounded by (nc + 1)!, because its permutation matrices commute.Source: A. Monomials and Girth and Minimum… · p. 3
• Commutativity and typically multiple fixed points limit monomial constructions; avoiding the stated bounds requires a noncommuting matrix in each 2×3 submatrix.Source: A. Monomials and Girth and Minimum… · p. 3

B. Permutation Polynomials f(x) = ax(q+1)/2 + bx

• The family f(x) = ax^(q+1)/2 + bx is noncommuting and closed under composition and inverses, and is used to construct protograph-based codes.Source: B. Permutation Polynomials f(x) =… · p. 3
• f(x) = ax^(q+1)/2 + bx permutes Fq exactly when b² − a² ∈ S, and it is piecewise affine.Its form can be written as (aψ(x) + b)x, with ψ taking 0, 1, or −1 according to the input.Source: B. Permutation Polynomials f(x) =… · p. 3
• The polynomial has 0 as its only fixed point if and only if b ± a ≠ 1.Source: B. Permutation Polynomials f(x) =… · p. 3
• The composition analysis considers cases where the coefficients’ b_i ± a_i values lie in S or in N; the general mixed case is omitted for space.Source: B. Permutation Polynomials f(x) =… · p. 3

C. Girth Upper Bounds

• Type S polynomials preserve squares and non-squares, whereas type N polynomials exchange them, yielding two categories for the cycle analysis.The type distinction is defined by whether b ± a are squares or non-squares.Source: C. Girth Upper Bounds · p. 4
• Girth is at most 20 for a 2×3 all-ones submatrix, 16 for a 2×4 submatrix, and 12 for a 2×L submatrix when L ≥5.Theorem 11 gives these bounds for codes using f(x) = ax^(q+1)/2 + bx.Source: C. Girth Upper Bounds · p. 4
• A length-12 TBC walk produces a Tanner-graph 12-cycle when the three columns are all in Category 1 or all in Category 2.The paper gives one composition witness for each category and says the other three-column combinations within each category are similar.Source: C. Girth Upper Bounds · p. 4
• When a 2×3 submatrix mixes the two categories, a length-20 TBC walk produces a Tanner-graph 20-cycle.The analysis of other combinations with two columns in one category and one in the other is described as similar.Source: C. Girth Upper Bounds · p. 4
• The QC-LDPC minimum-distance upper bound does not apply to these polynomials because their compositions do not commute; investigating that bound is left for future work.Source: C. Girth Upper Bounds · p. 5

IV. SIMULATIONS

• PM-LDPC codes yield a slight decoding gain over APM-LDPC codes in the simulated comparison.The comparison uses belief propagation and includes a QC-LDPC baseline.Source: §IV · p. 5
• At lift size 100, F2×3 and G2×3 have girth 20, while H2×3 has girth 12; their code parameters are [300, 101, 10] and [300, 101, 6], respectively.F2×3 and G2×3 have 200 and 350 20-cycles; H2×3 has 100 12-cycles.Source: §IV · p. 5
• At lift size 100, F2×4 and G2×4 have girth 16, while H2×4 has girth 12; their code parameters are [400, 201, 8] and [400, 201, 6], respectively.F2×4 and G2×4 have 800 and 1350 16-cycles; H2×4 has 400 12-cycles.Source: §IV · p. 5
• The same decoding gain is reported as achievable with smaller lift sizes, although those results are not detailed.The constructions are defined using polynomial parity-check matrices and the matrices listed in Tables I and II.Source: §IV · p. 5

V. CONCLUDING REMARKS

• Figure 1 compares simulated decoding performance for PM, APM, and CPM constructions from Tables I and II.The paper identifies CPMs with circulant permutation matrices and PMs with binomial permutation polynomials.Source: Figure 1 · p. 5, §V · p. 5
• Simulations suggest binomial-permutation protograph-based LDPC codes have a lower error rate than APM-LDPC codes.The same parameters are reported achievable at lift size 18 for girth 20 using permutation binomials over F19, versus lift size 20 for affine permutations.Source: §V · p. 5
• Permutation monomials commute and typically have several fixed points, whereas the studied permutation binomials do not commute and are piecewise affine.Both families are closed under composition and inverses, enabling algebraic and efficient girth analysis.Source: §V · p. 5
• The authors identify exploring more sophisticated permutation-polynomial families, including Dickson polynomials, as future work.They express cautious optimism that such families may yield meaningful coding gains.Source: §V · p. 5
• Exploring quantum LDPC codes using general permutation polynomials is another proposed future direction.The passage notes prior work on affine-permutation high-girth quantum LDPC codes and a linear-cost decoding algorithm.Source: §V · p. 5