The MacWilliams identity #
For a linear code C of length n over a finite field F with q elements, the MacWilliams
identity expresses the homogeneous weight enumerator of the Euclidean dual through that of C:
#C · W_{C⊥}(X, Y) = W_C(X + (q - 1) Y, X - Y).
It is stated here in this division-free form, as an identity in ℤ[X, Y].
The proof is the classical character-sum argument. Fix a primitive additive character ψ of
the alphabet with values in a domain of characteristic zero. The finite Fourier transform of
the weight monomial X^(n - wt y) Y^(wt y) factors over the coordinates, and each factor is
X + (q - 1) Y or X - Y according as the coordinate vanishes, so the transform is
(X + (q - 1) Y)^(n - wt x) (X - Y)^(wt x). Summing over C and applying the Poisson
summation formula Submodule.sum_sum_addChar_dotProduct_smul gives the identity with
coefficients in the target of ψ, which descends to ℤ.
The argument only uses the primitive character, so the identity is proved for linear codes over
any finite commutative ring carrying a primitive additive character with values in a
characteristic zero domain, such as ZMod m; the finite-field statement is the specialization
to AddChar.FiniteField.primitiveChar.
Over a field of characteristic zero the identity can be divided by #C, giving the normalized
form W_{C⊥}(X, Y) = (#C)⁻¹ W_C(X + (q - 1) Y, X - Y). For a self-dual code of length n,
#C = q^(n/2), so the MacWilliams substitution multiplies W_C by q^(n/2). Since W_C is
homogeneous of degree n, this says that W_C is invariant under the normalized transform
(X, Y) ↦ ((X + (q - 1) Y) / √q, (X - Y) / √q).
Main statements #
Submodule.sum_addChar_dotProduct_smul_weightMonomial: the Fourier transform of the weight monomial.Submodule.natCard_mul_weightEnumerator_euclideanDual_of_isPrimitive: the MacWilliams identity over a finite commutative ring with a primitive additive character.Submodule.natCard_mul_weightEnumerator_euclideanDual: the MacWilliams identity over a finite field.TauCeti.aeval_macWilliams_identity: evaluation of a division-free MacWilliams identity in any commutative ring.Submodule.natCard_mul_weightEnumerator_of_isSelfDual: the division-free MacWilliams identity for a self-dual code.Submodule.map_weightEnumerator_euclideanDual: the normalized MacWilliams identity, with coefficients in a field of characteristic zero.Submodule.aeval_weightEnumerator_of_isSelfDual: the integral MacWilliams symmetryW_C(X + (q - 1) Y, X - Y) = q^(n/2) W_C(X, Y)of a self-dual code.
The normalized forms of both identities live in
TauCeti.InformationTheory.Coding.MacWilliams.Normalized, which states them over an arbitrary
commutative ring and is the canonical home for them.
References #
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland (1977), Chapter 5, §2, Theorem 1; W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press (2003), §7.2, Theorem 7.2.3.
The finite Fourier transform of the weight monomial X^(n - wt y) Y^(wt y) with respect to
a primitive additive character ψ is (X + (q - 1) Y)^(n - wt x) (X - Y)^(wt x), where q is
the size of the alphabet.
The MacWilliams identity over a finite commutative ring R with q elements which
carries a primitive additive character with values in a domain of characteristic zero: for a
linear code C, #C · W_{C⊥}(X, Y) = W_C(X + (q - 1) Y, X - Y) in ℤ[X, Y].
The MacWilliams identity: for a linear code C over a finite field F with q
elements, #C · W_{C⊥}(X, Y) = W_C(X + (q - 1) Y, X - Y) in ℤ[X, Y].
The normalized MacWilliams identity: for a linear code C over a finite field with q
elements, W_{C⊥}(X, Y) = (#C)⁻¹ W_C(X + (q - 1) Y, X - Y), with coefficients in any field K of
characteristic zero.
The weight enumerator of a Euclidean self-dual code over a field with q elements is fixed by
the MacWilliams substitution up to the factor q^(n/2), where n is the length:
W_C(X + (q - 1) Y, X - Y) = q^(n/2) W_C(X, Y) in ℤ[X, Y].
Evaluating an integral MacWilliams identity in any commutative ring preserves its
cardinality factor and the substitution (X, Y) ↦ (X + (q - 1) Y, X - Y).
A self-dual code over a finite commutative ring carrying a primitive additive character
satisfies the division-free MacWilliams identity in ℤ[X, Y].
A self-dual code over a finite field satisfies the division-free MacWilliams identity
in ℤ[X, Y].