PaperlayerView exact revision on arXiv

Source-linked AI summary

Weight Distributions of Single Parity-Check Product Codes via Character Sums

Makson Miller Alves Ribeiro, Sara D. Cardell

arXiv:2608.26457v1cs.ITmath.CO

TL;DR

Binary single parity-check product codes have constrained row and column parities, making complete weight enumeration nontrivial. The paper combines generalized-weight analysis with dual-code characterization, Walsh–Hadamard MacWilliams identities, and Krawtchouk recurrences to derive exact formulas and efficient computation. It also determines square-code maximum weights and the parity condition for enumerator symmetry.

  • Problem

    Complete weight enumeration requires counting binary matrices with prescribed weight and simultaneous even row and column sums, while direct enumeration becomes impractical as dimensions grow.

  • Method

    The paper characterizes the dual code, applies the MacWilliams identity in Walsh–Hadamard form, groups auxiliary vectors by weight, and evaluates coefficients with Krawtchouk-polynomial recurrences.

  • Results

    The paper obtains exact closed-form formulas for the weight enumerator and its coefficients, determines generalized Hamming weights, and shows that C_n has maximum weight n^2 for even n and n^2−n for odd n.

  • Takeaways & Limitations

    The full weight distribution can be computed without enumerating all codewords, using at most O(N^2) arithmetic operations and O(N) auxiliary memory for N = mn.

  • Takeaways & Limitations

    All equalities in the Walsh–Hadamard weight-enumerator derivation are taken in F_2.

Abstract

from arXiv · show

We investigate structural and enumerative properties of binary single parity-check product codes. For each $n\geq 2$, $\operatorname{SPC}(n)$ denotes the binary single parity-check code of length $n$, consisting of all binary vectors of length $n$ having even Hamming weight. We determine the generalized Hamming weight hierarchy of the product code $\mathcal{C}_{m,n}=\operatorname{SPC}(m)\otimes\operatorname{SPC}(n)$, whose codewords can be represented as $m\times n$ binary matrices in which every row and every column has even Hamming weight. For the square product $\mathcal{C}_n =\operatorname{SPC}(n)\otimes\operatorname{SPC}(n)$, we also determine the maximum codeword weight and prove that its homogeneous weight enumerator is symmetric if and only if $n$ is even. After characterizing the dual code, we apply the MacWilliams identity in its Walsh--Hadamard formulation to derive an exact closed-form expression for the weight enumerator. By grouping the auxiliary binary vectors according to their Hamming weights, we obtain an explicit formula for each coefficient in terms of binomial coefficients and alternating convolutions. Finally, using Krawtchouk polynomials, we present an exact procedure for computing the full weight distribution without exhaustively enumerating all codewords. Numerical examples illustrate the formulas and verify the resulting computations.

1 Introduction

The paper studies structural and enumerative properties of binary single parity-check product codes, focusing on generalized Hamming weights, maximum weights, symmetry, and exact weight distributions. It combines dual-code analysis, Walsh–Hadamard methods, character sums, and Krawtchouk-polynomial computation to avoid exhaustive enumeration.

  • Motivation: Weight distributions count codewords by Hamming weight, determine minimum distance, and support studies of duality, decoding, and combinatorial identities.Direct computation can require examining all 2^K codewords of a binary linear code of dimension K.
  • Code family: The product code C_m,n = SPC(m) ⊗ SPC(n) has parameters [mn, (m−1)(n−1), 4]_2, with even row and column sums.SPC(n) consists of binary length-n vectors of even Hamming weight.
  • Enumeration problem: Counting weight-A_w codewords is equivalent to enumerating m × n binary matrices with exactly w ones and simultaneous even row and column sums.The parity equations contain one global linear dependency, while direct enumeration considers 2^((m−1)(n−1)) codewords.
  • Structural results: The paper determines the generalized Hamming weight hierarchy of C_m,n and, for C_n, the maximum weight and symmetry criterion.The maximum weight is n^2 for even n and n^2−n for odd n; the homogeneous enumerator is symmetric exactly when n is even.
  • Enumerative formula: The exact weight enumerator follows by characterizing the dual code, applying the Walsh–Hadamard MacWilliams identity, and grouping auxiliary vectors by their weights.This yields formulas for homogeneous and one-variable enumerators and coefficients A_w using binomial coefficients and alternating convolutions.
  • Computation: A Krawtchouk-polynomial recurrence computes the full distribution in at most O(N^2) arithmetic operations and O(N) auxiliary memory for N = mn.The procedure groups equal contributions and avoids enumerating the 2^((m−1)(n−1)) codewords; numerical examples provide consistency checks.

2 Preliminaries

The preliminaries define linear-code invariants, single parity-check codes, product codes, character transforms, and the Walsh–Hadamard formulation of MacWilliams duality. These tools establish the code constraints and provide the framework for later weight-enumerator calculations.

  • 2.1 Linear Codes: A linear code is a vector subspace over a finite field, with dimension and minimum distance recorded in [n, k, d]_q parameters.Generator and parity-check matrices describe the code and its parity constraints, with G H^T = 0.
  • 2.1 Linear Codes: Hamming weight is the cardinality of a vector’s support, while Hamming distance counts coordinates where two vectors differ.For linear codes, distance from the zero vector equals weight, and minimum distance is determined by nonzero codewords.
  • 2.1 Linear Codes: Generalized Hamming weights measure the smallest support of a subcode of each prescribed dimension and form a strictly increasing weight hierarchy.The first generalized Hamming weight equals the minimum Hamming distance.
  • 2.2 Single Parity-Check Codes: SPC(n) is the binary length-n code of vectors with even Hamming weight, with parameters [n, n−1, 2]_2.Its weight enumerator counts even-weight words, including binomially many words of weight 2i.
  • 2.3 SPC product codes: The product of binary linear codes with parameters [n_1,k_1,d_1]_2 and [n_2,k_2,d_2]_2 has parameters [n_1n_2,k_1k_2,d_1d_2]_2.Its codewords can be arranged as matrices whose rows and columns satisfy the component-code constraints.
  • 2.3 SPC product codes: For SPC products, codeword matrices have even row and column sums, represented by a possibly redundant parity-check matrix with one linear dependency.Removing any one row produces a full-rank parity-check matrix.
  • 2.4 Characters and the Walsh–Hadamard Transform: Characters of a finite additive abelian group form a dual group, and over F_2^n they take values in {1, −1} via the standard inner product.Character orthogonality underlies the Walsh–Hadamard transform and its inversion formula.
  • 2.4 Characters and the Walsh–Hadamard Transform: The Walsh–Hadamard transform is the unnormalized Fourier transform on F_2^n, and for a binary linear code its indicator transform is supported on the dual code.This gives a Fourier-analytic formulation of the MacWilliams identity relating a code’s weight enumerator to its dual’s.

3 Weight Properties of SPC Product Codes

The section derives generalized Hamming weight hierarchies for SPC product codes and establishes maximum-weight and symmetry properties for square products.

  • The product C_m,n has parameters [mn, (m−1)(n−1), 4]_2 and consists of binary matrices with even row and column sums.
  • The hierarchy follows from the chain condition and the product formula applied to the component SPC codes.SPC(ℓ) attains its hierarchy through nested subcodes supported on the first i + 1 coordinates.
  • 3.3 Maximum weight and symmetry of the weight enumerator: For C_n, the maximum codeword weight is n^2 when n is even and n^2 − n when n is odd.For even n, the all-one matrix is a codeword; for odd n, each row has weight at most n−1.

4 The Weight Enumerator of the SPC Product Code via the Walsh–Hadamard Transform

The section characterizes the dual of the SPC product code and uses the Walsh–Hadamard form of the MacWilliams identity to obtain exact weight-enumerator formulas.

  • Every dual codeword is represented by a matrix Y(a,b) whose entries are a_i + b_j over F_2, with exactly two representations.The equivalent representations are (a,b) and (a + 1_m, b + 1_n).
  • If wt(a)=r and wt(b)=t, equal and unequal coordinate pairs occur in numbers Z(r,t)=rt+(m−r)(n−t) and O(r,t)=r(n−t)+(m−r)t.
  • Theorem 10 gives an exact closed-form homogeneous weight enumerator by summing MacWilliams terms over the weights of the auxiliary vectors.The one-variable enumerator follows by setting x=1 and y=z.
  • Example: For C_3, the resulting one-variable enumerator is W_C3(z)=1+9z^4+6z^6.
  • Grouping auxiliary vectors by their weights reduces enumeration over 2^((m−1)(n−1)) codewords to a sum indexed by possible auxiliary-vector weights.

5 Computational Evaluation of the Weight Enumerator

The section converts the coefficient formulas into an exact Krawtchouk-polynomial procedure, with polynomial-time arithmetic complexity and numerical verification.

  • The coefficient formula groups pairs producing the same O(r,t) before evaluating alternating convolutions.This avoids repeated calculations for distinct pairs with identical unequal-pair counts.
  • Binary Krawtchouk polynomials and their recurrence compute all coefficients without separately evaluating every alternating binomial sum.
  • The algorithm uses O(N) auxiliary memory, O(N^2) additional arithmetic operations, and requires arbitrary-precision integers.Multiplicity computation uses O(mn)=O(N) arithmetic operations.
  • 5.1 Computational examples: For C_3, the computed coefficients are A_0=1, A_4=9, and A_6=6, summing to 16=2^4.
  • 5.1 Computational examples: For C_4, the weight enumerator is 1+36z^4+96z^6+246z^8+96z^10+36z^12+z^16, whose coefficients sum to 512=2^9.
  • 5.1 Computational examples: For SPC(10)⊗SPC(10), the code has parameters [100,81,4]_2, and selected coefficients are reported in Table 1.The distribution is symmetric under A_w=A_100−w because n is even.

6 Conclusion

The paper establishes structural results for binary single parity-check product codes and develops an exact, computable framework for their finite-length weight distributions. It also identifies extensions to higher-dimensional products and other component codes as future directions.

  • The generalized Hamming weight hierarchy of C_m,n is explicitly described using the product formula for codes satisfying the chain condition.
  • For the square product C_n, the maximum codeword weight is determined, and its homogeneous weight enumerator is symmetric if and only if n is even.
  • An exact closed-form weight enumerator for C_m,n is derived by characterizing the dual code and applying the MacWilliams identity in Walsh–Hadamard form.
  • Grouping auxiliary vectors by Hamming weight produces explicit formulas for the weight enumerator and each coefficient.
  • Krawtchouk-polynomial formulas provide an exact procedure for computing the full weight distribution without exhaustive enumeration of the 2^(m−1)(n−1) codewords.Numerical examples and consistency checks verify the resulting distributions for several component lengths.
  • The Walsh–Hadamard approach gives a unified framework for finite-length weight distributions of two-dimensional SPC product codes, with extensions proposed for higher dimensions and other components.
Loading 2608.26457v1…