PaperlayerView exact revision on arXiv

Source-linked AI summary

Quasi-Cyclic LDPC Codes: Influence of Proto- and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds

Roxana Smarandache, Pascal O. Vontobel

arXiv:0901.4129v2cs.ITcs.DM

TL;DR

The paper asks how QC LDPC minimum-distance upper bounds depend on code and graph structure. It derives polynomial-matrix and weight-matrix bounds, transfers related statements through QC-to-convolutional unwrapping, and gives constructions achieving or approaching several bounds.

  • Problem

    The paper examines how QC LDPC minimum Hamming distance upper bounds depend on parity-check matrices, weight matrices, proto-graphs, Tanner-graph parameters, and girth.

  • Method

    It derives two QC/convolutional upper-bound families and uses QC unwrapping, graph structure, and explicit constructions to study and approach them.

  • Results

    The paper presents bounds based on polynomial parity-check matrices and weight matrices, strengthens them using graph information, and constructs codes that achieve or come close to several bounds.

  • Takeaways & Limitations

    Minimum-distance behavior can be analyzed through both algebraic parity-check descriptions and the structure of associated proto-graphs and Tanner graphs.

Abstract

from arXiv · show

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by "unwrapping" the QC code.

I. INTRODUCTION

The paper studies QC LDPC codes through polynomial parity-check and weight matrices, relating their distance bounds to proto-graph and Tanner-graph structure. It also develops analogous convolutional-code results and outlines constructions for codes approaching the bounds.

  • For monomial parity-check matrices, the minimum Hamming distance is always upper bounded by (J +1)! .
  • The paper generalizes beyond monomial parity-check matrices to weight-matrix entries 0, 1, 2, and 3, studying how distance bounds depend on matrix and graph structure.The corresponding polynomial entries are zero polynomials, monomials, binomials, and trinomials.
  • Weight matrices represent proto-graphs, whose incidence entries count parallel edges; QC constructions are proto-graph covers restricted to cyclic edge permutations.
  • QC LDPC codes are attractive because their descriptions support efficient encoding and decoding while minimum Hamming distance characterizes undetectable errors.
  • The paper presents polynomial-matrix and weight-matrix distance bounds, then studies type-1, type-2, type-3 codes, cycles, and constructions based on covers.

D. Convolutional Codes

QC codes can be represented as graph covers of proto-graphs and algebraically unwrapped into convolutional codes. This connection enables field-based linear-algebra arguments and transfers distance statements between the two code families.

  • D. Convolutional Codes: Unwrapping replaces x and its powers in a QC parity-check matrix H(x) by y and its powers to form Hconv(y), preserving the weight matrix.
  • D. Convolutional Codes: Tanner’s theorem relates a QC code’s minimum Hamming distance to the free Hamming distance of its unwrapped convolutional code.
  • D. Convolutional Codes: Convolutional parity-check matrices over the field F2((y)) support rank and determinant arguments that are unavailable in general over the QC polynomial ring with zero divisors.
  • E. Graphs: The example’s Tanner graph is (3, 4)-regular, with variable-node degree 3 and check-node degree 4.
  • E. Graphs: A QC Tanner graph is an r-cover of its proto-graph, and restricting edge permutations to cyclic permutations makes the resulting proto-graph-based code quasicyclic.

F. Determinants and Permanents

The paper constructs codewords from subsets of columns and uses determinants or permanents to derive two QC and convolutional distance upper bounds. The weight-matrix bound is easier to compute but generally weaker, while graph information can strengthen the bounds.

  • The bounds can be strengthened using Tanner-graph structure such as cycles, and several constructed code classes achieve or approach the resulting upper bounds.
  • For a size-(J+1) column subset, the construction forms a codeword from submatrix determinants; characteristic two makes determinants equal permanents.
  • Theorem 7 gives QC and convolutional distance upper bounds as functions of the polynomial parity-check matrices H(x) and Hconv(y), respectively.
  • The min∗ operator excludes constructed all-zero codewords, whose zero Hamming weight would otherwise produce an irrelevant bound.
  • Theorem 8 gives a generally weaker but easier-to-compute bound based only on the weight matrix, independent of the circulant size r.

IV. TYPE-I QC/CONVOLUTIONAL CODES

This section specializes the paper’s distance-bound results to type-1 QC codes and evaluates them through explicit examples. It compares polynomial-matrix and weight-matrix bounds, including constructions that attain the bounds and cautions about the proposed search strategy.

  • The paper extends the type-1 discussion to analogous convolutional-code results and uses computational programs to evaluate minimum and free distances.
  • A 2×4 monomial parity-check matrix can yield a QC code with minimum Hamming distance at most 6, while unsuitable polynomial entries make the polynomial-matrix bound strictly smaller.
  • For a (3,4)-regular type-1 QC LDPC code, the minimum Hamming distance is upper bounded by 24, and suitable choices attain this bound at r = 31 with parameters [124, 33, 24].
  • The weight-matrix bound is easier to compute and applies to every QC code sharing the same weight matrix, hence the same proto-graph, although it can be looser than the polynomial-matrix bound.
  • Type-1 QC codes with design rate 4/7 can achieve the corollary’s minimum-distance upper bound, with an example attaining dmin = 24.

V. TYPE-II AND TYPE-III QC/CONVOLUTIONAL CODES

The section classifies type-2 and type-3 regular QC/convolutional codes by weight-matrix structure and derives corresponding minimum/free Hamming-distance upper bounds. Explicit constructions attain optimal bounds in several cases, including a [184, 47, 32] type-2 QC code and a [184, 46, 34] type-3 QC code.

  • Type-2 codes: A type-2 (3, 4)-regular weight-matrix classification yields five matrix types, with the largest upper bound {dmin, dfree} ⩽32.The bound 32 occurs for the first or second matrix type, up to row and column permutations.
  • Type-2 codes: dmin = 32 is achieved by the [184, 47, 32] type-2 QC code, attaining the best possible bound for this class.The code has girth 8 and diameter 8.
  • Type-3 codes: Type-3 (3, 4)-regular weight matrices add three configurations to the five type-2 configurations, with the largest upper bound {dmin, dfree} ⩽54.The bound 54 corresponds to the last listed matrix type, up to row and column permutations.
  • Type-3 codes: A type-3 construction produces a [124, 31, 28] code for r = 31 and a [184, 46, 34] code for r = 46, while larger r may reach dmin = 54.The reported rates are 0.25 and 0.2554, respectively.
  • Girth: Type-2 and type-3 codes with trinomial entries cannot have Tanner-graph girth larger than 6.This restriction follows from the presence of at least one trinomial entry.
  • Open problem: The paper leaves relevant simple general upper bounds for type-2 and type-3 codes with arbitrary regular dimensions as an open problem.Straightforward generalizations exist but are described as usually not useful.

VI. THE EFFECT OF SMALL CYCLES ON THE MINIMUM HAMMING DISTANCE AND THE FREE HAMMING DISTANCE

This section relates short Tanner-graph cycles to stronger minimum and free Hamming-distance upper bounds. For type-1 codes, 4- and 6-cycles prevent attainment of the maximal bound (J+1)! associated with the cycle-free case.

  • 4-cycles: The paper derives stronger distance upper bounds when Tanner graphs contain 4-cycles, using polynomial-matrix conditions that characterize such cycles.The same framework applies to corresponding convolutional codes.
  • Effect of girth: The paper observes that smaller Tanner-graph girth gives smaller minimum/free Hamming-distance upper bounds and is also generally associated with poorer iterative-decoding performance.The decoding-performance statement is presented as empirical evidence and related prior analysis.
  • 4-cycles: A 4-cycle is detected through a 2 × 2 polynomial sub-matrix satisfying the corresponding permanent condition.For type-1 QC codes, the condition is equivalent to a monomial 2 × 2 sub-matrix whose permanent relation holds.

B. Type-I QC/Convolutional Codes with 6-Cycles

The section characterizes 6-cycles and longer 2R-cycles through sub-matrix and permutation conditions, then extends cycle-detection ideas to type-2 QC codes. It shows that longer cycles have more varied matrix representations and that type-2 4-cycle freedom can be tested algebraically.

  • 6-cycles: A 6-cycle is characterized by a 3 × 3 polynomial sub-matrix whose permanent expansion contains terms that cancel to zero.The characterization applies to type-1 QC codes and has an analogous convolutional-code statement.
  • 6-cycles: Type-1 QC/convolutional codes with 6-cycles receive stricter minimum/free Hamming-distance upper bounds than the cycle-free maximum.The theorem is part of the paper’s systematic analysis of cycle effects.
  • 2R-cycles: A cycle of length 2R follows when two distinct bijections satisfy the specified polynomial-product relation and their composition is a cyclic permutation of order R.The products on both sides of the relation must be nonzero.
  • 2R-cycles: Unlike 4- and 6-cycles, longer cycles are not confined to one square sub-matrix size: 8-cycles may occur in 4 × 4, 2 × 4, or 3 × 4 sub-matrices.The paper states that analogous variation occurs for longer cycles.
  • Type-2 codes: For type-2 QC codes, 4-cycle freedom is equivalent to algebraic conditions on relevant polynomial sub-matrices and can be checked through finite set-sum exclusions.The paper illustrates these exclusions for a specific type-2 construction.

VII. TYPE-I QC CODES BASED ON DOUBLE COVERS OF TYPE-II QC CODES

The section constructs larger type-1 QC LDPC codes from type-2 codes through double-cover transformations and noncommuting block modifications. A worked example shows that the modified code raises minimum distance from 32 to 56 while retaining nearly identical decoding performance in the simulated range.

  • Construction: The construction replaces each entry of a type-2 polynomial parity-check matrix with a 2×2 block, producing a type-1 matrix twice as large while preserving regularity.The resulting matrix has dimensions (2J) × (2I) and the same (J′, I′)-regularity as the original code.
  • Construction: The initial double cover preserves the Tanner- and proto-graph covering relationship, but its minimum-distance bounds can remain limited by commuting polynomial blocks.For r = 46, the constructed code has bounds 80 and 108 from two general results, but the double-cover and commuting-matrix arguments reduce the bound to 32.
  • Example: The two QC codes have nearly identical simulated sum-product decoding curves, while the randomly generated four-cycle-free comparison code shows a word-error-rate floor near 4.5 dB.Only the [368, 93, 32] curve is shown because the two QC curves are nearly coincident; the authors expect the distance-56 code to perform better at higher signal-to-noise ratios.
  • Example: Changing selected polynomial blocks so they no longer all commute removes the 32-distance bound and yields a [368, 93, 56] code, compared with the base [368, 93, 32] code.The modified code remains a 2r-cover of the original proto-graph, although its Tanner graph is not a double cover of the intermediate code.
  • Extensions: The paper presents iterative extensions of the construction using M-covers whose noncommuting blocks can avoid the original minimum-distance bound, but further code construction and analysis remain future work.The conclusion summarizes bounds based on polynomial and weight matrices, graph parameters such as girth, and constructions that achieve or approach those bounds.

APPENDIX A PROOF OF THEOREM 8

Appendix A proves the weight-matrix-based upper bound on free Hamming distance for convolutional codes, including degenerate cases where the standard codeword construction gives the zero vector. The QC result then follows by unwrapping the QC code and applying Tanner’s inequality.

  • QC connection: The QC-code statement follows by applying the convolutional result to H(y) = H(x)|x=y and combining it with Tanner’s inequality.The appendix proves the convolutional part first because the convolutional parity-check matrix is defined over a field.
  • Proof strategy: The proof bounds the permanent-based expression using the weight function’s triangle and product inequalities, establishing it as an upper bound on free Hamming distance.When the constructed vector is nonzero, it is a valid convolutional-code codeword; rank-deficient cases are handled by reducing to a smaller submatrix.
  • Degenerate cases: The min* operator excludes zero codewords while retaining nonzero terms that can still be shown to upper-bound free distance.This prevents constructed all-zero vectors from producing an invalid zero upper bound.
  • Full-rank case: If the selected submatrix has full rank, the codeword-generating procedure produces a nonzero codeword whose weight supplies the required free-distance upper bound.The argument explicitly treats the full-rank case before addressing rank deficiency.
  • Rank-deficient case: When the selected submatrix is rank-deficient, a suitable reduced submatrix produces a nonzero codeword in the original convolutional code and preserves the upper-bound argument.The proof selects an index using a nonzero permanent term, removes that coordinate, and recursively handles any remaining rank deficiency.

APPENDIX B PROOF OF COROLLARY 9

Appendix B proves the type-1 specialization of the free-distance bound, including a degenerate rank-deficient case. It also derives the QC statement through the convolutional-code result and Tanner’s inequality.

  • QC connection: The appendix establishes the convolutional result first and obtains the QC result by applying it to H(y) = H(x)|x=y and using Tanner’s inequality.This is the same unwrapping-based connection used elsewhere in the paper.
  • Nondegenerate case: For a type-1 weight matrix with a nonzero qualifying permanent term, the proof obtains the factorial free-distance upper bound stated by the corollary.The argument uses that type-1 matrices contain only zeros and ones.
  • Degenerate case: In the degenerate case, all qualifying permanent terms vanish, implying that the parity-check matrix lacks full row rank and can be reduced recursively.For J > 1, recursion gives dfree(Cconv) ⩽ J!, which is no larger than (J+1)!; for J = 1, the bound is 2.
  • Cycle implications: The accompanying cycle analysis exhibits submatrices that force 6-, 8-, 10-, and 12-cycles in the Tanner graph under the stated weight configurations.These explicit paths translate polynomial conditions into upper bounds on graph girth.

APPENDIX D PROOF OF LEMMA 20

Appendix D proves a girth-sensitive bound for type-1 polynomial parity-check matrices containing a four-cycle. It separates full-rank and rank-deficient cases, then transfers the convolutional result to QC codes.

  • Cycle characterization: A type-1 2×2 submatrix can induce a four-cycle exactly when its polynomial exponents satisfy the corresponding equality condition.The appendix also notes that certain weight configurations cannot induce four-cycles because their weight inequalities are impossible.
  • Proof strategy: The proof exploits the presence of a four-cycle to refine the free-distance upper bound for type-1 convolutional codes.The argument partitions qualifying column sets according to whether they contain the two columns associated with the four-cycle.
  • Full-rank case: For submatrices with full row rank, the proof bounds the relevant permanent terms by separating permutations that preserve or exchange the four-cycle columns.The combinatorial counts distinguish the two-cycle-column mappings from the remaining permutations.
  • Rank-deficient case: When all relevant submatrices are rank-deficient, the proof reduces to a smaller parity-check matrix and applies the earlier type-1 bound recursively.The rank condition is expressed through vanishing permanents and equivalent failure of full row rank.
  • QC transfer: Combining the two subcases establishes the convolutional part of the theorem, and Tanner’s inequality yields the corresponding QC-code bound.Row and column transformations put the QC parity-check matrix into a form compatible with the convolutional argument without changing the code’s minimum distance.

APPENDIX F PROOF OF LEMMA 24

The appendix proves the QC-code portion of Lemma 24 by translating equal monomials in a permanent expansion into short cycles in the Tanner graph.

  • APPENDIX F PROOF OF LEMMA 24: The convolutional-code part of the lemma is stated to follow by a similar argument.Only the QC-code portion is proved explicitly in this appendix.
  • APPENDIX F PROOF OF LEMMA 24: The proof assumes that all entries of B(x) are monomials; cases containing zero-polynomial entries are analogous.The monomial entries are parameterized by exponents in Z/rZ before expanding the permanent.
  • APPENDIX F PROOF OF LEMMA 24: The QC-code proof reduces the relevant permanent condition to the existence of repeated monomials in F⟨r⟩[x].The argument identifies two possible equality patterns among the six monomials in the expansion.
  • APPENDIX F PROOF OF LEMMA 24: When exactly one exponent variable is shared, equality yields the modular condition a + e + i = a + f + h and corresponds to a 4-cycle.The shared variable is a, and the equality is interpreted in Z/rZ.
  • APPENDIX F PROOF OF LEMMA 24: Equal monomials with all exponent variables distinct correspond to a 6-cycle in the Tanner graph.The proof concludes that such a cycle must occur within a 3 × 3 sub-matrix of a type-1 polynomial parity-check matrix.

APPENDIX G PROOF OF THEOREM 25

The appendix proves the QC-code part of Theorem 25 by converting polynomial identities into permutation conditions and then identifying those conditions with Tanner-graph cycle criteria.

  • APPENDIX G PROOF OF THEOREM 25: The proof follows earlier arguments while adapting the set conditions from {0,1} to {0,1,2}.The modified observations apply to sets containing or excluding the three distinguished indices.
  • APPENDIX G PROOF OF THEOREM 25: The argument assumes J ≥ 3 because a type-1 polynomial parity-check matrix cannot contain a six-cycle otherwise.It then upper-bounds the preceding result under this assumption.
  • APPENDIX G PROOF OF THEOREM 25: Row and column relabeling, together with invertible row and monomial column multiplications, permits a convenient equivalent form of H(x).These operations preserve the code or produce an equivalent code.
  • APPENDIX G PROOF OF THEOREM 25: Only the QC-code portions are proved directly; the convolutional-code arguments are described as similar or omitted when they parallel earlier proofs.The appendix explicitly omits one first-part proof because it follows Theorem 22 and Theorem 25 arguments.
  • APPENDIX G PROOF OF THEOREM 25: Nonzero products permit exponent representations p_j,σ(j) and p_j,τ(j), which rewrite condition (9) into a permutation-based equality.The proof then studies the orbit of a starting index under π.
  • APPENDIX G PROOF OF THEOREM 25: The proof defines π = σ^-1 ◦ τ and uses its cyclic order R to equate the algebraic condition with the existence of a 2R-cycle.The cycle criterion is identified with Tanner’s condition.

APPENDIX I GRAPH COVERS

This appendix constructs a polynomial-matrix code transformation whose minimum distance is related to that of the original QC code, and identifies the resulting Tanner graph as a double cover.

  • APPENDIX I GRAPH COVERS: The construction decomposes the parity-check matrix and defines ˜C through a new polynomial parity-check matrix.The proof starts from a QC code C with parity-check matrix H(x).
  • APPENDIX I GRAPH COVERS: Lemma 31 establishes inequalities relating the minimum Hamming distances of C and the constructed code ˜C.The two directions are proved by mapping codewords between the two codes.
  • APPENDIX I GRAPH COVERS: The first distance inequality follows by summing the two component codewords of a codeword in ˜C to obtain a codeword in C.The proof handles the zero-sum case separately and concludes the inequality in (26).
  • APPENDIX I GRAPH COVERS: The second distance inequality follows by showing that a transformed nonzero codeword satisfies the parity-check equations of ˜C.The required equations combine H^(2)(x)c(x)^T and H^(1)(x)c(x)^T.
  • APPENDIX I GRAPH COVERS: When no terms cancel in H^(1)(x) + H^(2)(x), the Tanner graph of ˜H(x) is a double cover of the Tanner graph of H(x).Thus Lemma 31 relates the minimum distance of a Tanner graph to that of a particular double cover.
  • APPENDIX I GRAPH COVERS: An alternative matrix construction produces the same double cover up to row, column, and coordinate relabeling.The resulting Tanner graphs are isomorphic and define the same cover.
  • APPENDIX I GRAPH COVERS: The construction extends to general M-covers when M is a power of 2 by iterating the argument.Related work also considers higher-degree covers, including powers of 2.
Loading 0901.4129v2…