Motivation
Minimum distance tells us the smallest nonzero weight in a linear code, but it discards the rest of the distribution. For error analysis and structural questions we often need to know how many codewords have each weight. Surprisingly, the full weight distribution of a linear code determines that of its orthogonal dual. A large code can therefore be studied by enumerating a much smaller dual and applying a polynomial substitution.
The mechanism is a finite Fourier calculation. Summing a nontrivial character over a group gives cancellation; summing the trivial character gives the group's size. We will construct the required character explicitly and prove why its annihilator is the usual field-valued dual. That last point depends on linearity over the whole field, not merely closure under addition.
Definitions
Definition 1.4.1
(Dual code and weight enumerator)
Let be an -linear code. Its Euclidean dual is
Let count codewords of Hamming weight . The homogeneous weight enumerator is
Thus , every is a nonnegative integer and . Denote the dual counts by . The weight enumerator records no coordinate positions; it is less information than the actual code or a complete list of supports.
Definition 1.4.2
(An additive character of )
Write . Using a supplied polynomial basis , let take the coefficient of one. Define the complex-valued additive character
Here is represented by its integer residue. Additivity makes , and . Complex numbers are a proof device; the final coefficient formulas are exact integer computations.
Theorem/proposition
Theorem 1.4.3
(MacWilliams identity)
For every -linear code,
In particular . Applying the transform again recovers .
Theorem 1.4.4
(Exact coefficient constraints)
With binomial coefficients outside their usual range interpreted as zero, define
Then . Every proposed linear-code weight distribution must make all these values nonnegative integers. These conditions are necessary; this chapter does not establish that they suffice for a code to exist.
Concept lensAlgebraic
The transform is an involution up to scale
Write . Then , so on homogeneous polynomials of degree substitution by twice multiplies by . In coefficients, sends to , and the matrix satisfies . Since , applying the normalized transform twice returns : passing to the dual code is matched by one fixed linear map on weight distributions, which is its own inverse up to the factor .
Theorem 1.4.5
(First and second weight moments)
If contains no word of weight one, then
If it contains no nonzero word of weight one or two, then also
The second assertion is a statement about pairwise coordinate distributions, not a claim that every coordinate of a random codeword is jointly independent.
Proof sketch or proof idea
Establish finite orthogonality
Proof
(Character sums detect the dual)
For , the sum is . For , multiplication by permutes the field, so it is . Translation by one also permutes the field and gives . Since , this forces .
Now fix and sum over . If , the result is . Otherwise choose with . Because is field-linear, , and its dot product with is one. Translation of the sum by this codeword multiplies it by , so the sum is zero. We have proved the indicator identity
This proof explains why simply finding a nonzero dot product was not enough by itself: a nontrivial character can still take value one on some nonzero extension-field elements. Scaling that product to one uses the full linear-code hypothesis.
Factor the global sum coordinate by coordinate
Proof
(Coordinatewise factorization of the transform)
Multiply the indicator identity by the weight monomial of and sum over all . Interchanging the finite sums is exact. For fixed , the coordinate sums are independent products. At coordinate , the contribution is
If , this equals . If , orthogonality gives , so it equals . Multiplying over coordinates and then summing over proves the weight transform.
Proof X-ray
Cancellation performs the dual membership test
The outer sum ranges over every ambient word, but the character average is exactly zero outside the dual and one inside it. Coordinate factorization then needs only whether each coordinate of a codeword is zero. That is why a polynomial retaining only weights still contains enough information to determine the dual weights, despite forgetting all support positions.
Set in the identity. Only the zero codeword contributes to , so the answer is . For the inverse transform, the linear substitution satisfies . Homogeneity supplies a factor on applying it twice, which cancels the product . This also agrees with the elementary vector-space fact .
Extract the coefficients and moments
Proof
(Coefficients by expansion, moments by projections)
In , obtain by choosing copies from the second factor and from the first. The binomial theorem gives exactly . This proves the coefficient formula without numerical character evaluation. For , it reads . Setting immediately gives the first moment.
There is a useful structural proof of the moment formulas as well. If one coordinate projection of were zero, a dual word supported there would exist. Otherwise that projection is an onto linear map to , with equal-sized fibers. A uniformly chosen codeword is consequently nonzero at that coordinate with probability . Summing these indicator expectations yields the first moment.
If projection onto a pair of distinct coordinates were a proper subspace of , a nonzero linear functional on would annihilate it. Its two coefficients would supply a nonzero dual word supported on that pair. Absence of dual weights one and two therefore makes every pair projection onto, again with equal-sized fibers. The probability that both coordinates are nonzero is . Since counts ordered distinct nonzero-coordinate pairs, summing gives the second moment. No triple or higher projection was used.
Know what the computation does and does not save
If the input already contains the integer counts , all transformed counts can be calculated by finite binomial sums in polynomial time in and . The counts have at most bits, as do the relevant binomial and power contributions up to comparable polynomial factors. Straight exact integer addition, multiplication and division suffice. A negative or nonintegral answer disproves the proposed spectrum.
This is not a general polynomial-time method to discover from a generator matrix. Enumerating a dimension- code still takes codewords by the direct method. The benefit is that one may enumerate the dual instead when its dimension is much smaller, then transform its distribution. Nor does the weight enumerator reconstruct the code's coordinate arrangement, give an efficient decoder or certify that every numerically feasible spectrum is realizable.
Retain the phases for a nonzero syndrome class
For a supplied vector , replace the dual indicator at by the indicator at . The same proof gives the coset formula
The phase depends on the individual codeword and the vector , rather than only on the weight of . We therefore cannot normally replace this expression by the ordinary enumerator substitution. This difference matters for syndrome decoding: a nonzero syndrome describes an affine class of possible error vectors rather than the linear zero-syndrome class. The character calculation still works, but it needs those extra coordinate-dependent phases. Taking removes them and recovers MacWilliams duality. Computing all of them by enumerating retains the enumeration cost; a closed algebraic expression does not by itself supply a fast maximum-likelihood decoder.
Common mistake
(Dropping the phases for a nonzero coset)
The coset enumerator is not the ordinary substitution applied to . Take the binary repetition code , so is the even-weight code, and . The coset consists of the odd-weight words , with enumerator . The formula gives this, because contributes the phase : . Ignoring the phase would return , the enumerator of itself.
For a concrete probabilistic use, suppose an additive error changes each coordinate independently, choosing zero with probability and each nonzero field value with probability , where . A transmitted codeword plus error remains in exactly when the error belongs to . Consequently the probability of a nonzero undetected error is
The subtraction removes the zero error, which passes every parity check but is not an error event. This formula uses the independent symmetric error law explicitly. For a correlated channel or unequal symbol-error probabilities, weights alone need not determine the error probability; the supports and actual nonzero symbols can matter.
Worked examples
Worked example 1.4.6
(Repetition and even parity)
For the binary length-three repetition code, and . The transform gives . This is the even-parity dual: the zero word and three weight-two words. Its first moment is six, agreeing with . Its dual is the repetition code, whose nonzero weight is three, so the pairwise formula also gives second factorial moment .
Worked example 1.4.7
(Recover a Hamming distribution from its small dual)
The binary simplex dual of the length-seven Hamming code has enumerator : every nonzero word of the simplex code has weight four. Transforming this eight-word code gives
Thus the sixteen-word Hamming code has seven words of weight three, seven of weight four and one of weight seven besides zero. The smallest nonzero weight is three, and the first weight sum is .
Worked example 1.4.8
(A nonbinary check with the sign convention visible)
For , the dual is . Both have enumerator . Indeed
The cross terms cancel. This computation uses Euclidean duality and works in characteristic two as well, where the two coordinate descriptions happen to coincide.
For example, under that symmetric binary error law, the length-three repetition code has nonzero undetected-error probability , whereas its even-parity dual has probability . This illustrates why knowing the entire spectrum supports a more detailed error calculation than knowing only the minimum distance.
Counterexamples and misconceptions
Counterexample mode
An additive subgroup is not enough
Let with , and take the length-one additive subgroup . It is not -linear. Its field-valued Euclidean annihilator is only zero. But for the constant-coefficient character above, , so averaging over at gives one rather than zero. The indicator proof fails exactly because scaling a codeword by need not stay in . General additive-code dualities require the corresponding character pairing and cannot silently use the present field-linear theorem.
Common mistake
(Nonnegative integer counts are not enough)
A plausible integer spectrum can fail the transform. For a supposed binary length-six dimension-three code, try and all other counts zero. These are nonnegative integers summing to eight, and there are enough ambient weight-two words. Nevertheless the predicted dual weight-one count is , impossible. Basic cardinality and weight-range checks did not detect this contradiction.
Practice
Quick check
(Compute the transform of the zero code and of the whole space .)
Solution · Answer
The zero code has , whose transform is , the whole-space enumerator. The whole space has size and this latter enumerator; its transformed linear expression is , giving as required.
Quick check
(Derive directly from the coefficient formula and recover the first moment when .)
Solution · Answer
The term is and the term is , summing to . Since , the equation rearranges to the stated first moment.
Quick check
(Show that a self-dual field-linear code must have even length and dimension . State the resulting enumerator identity.)
Solution · Answer
The size identity gives . Writing yields . The enumerator must satisfy . This is necessary and does not classify self-dual codes or prove their existence for every even length and field.
Quick check
(For the binary length-three even-parity code, show explicitly that pairwise independent coordinates need not be jointly independent.)
Solution · Answer
The four words are . Each chosen coordinate pair takes all four binary values once, so it is uniform. But the third coordinate is the sum of the first two, and has probability zero rather than . Pairwise uniformity therefore does not imply full independent uniform coordinates.
Quick check
(Check why the hypothetical length-six spectrum fails the first-moment interpretation, independently of expanding the full transform.)
Solution · Answer
A nonzero coordinate projection of a binary linear code is onto and contributes to the total weight over all codewords. A zero coordinate contributes zero. Thus that total must be four times the number of active coordinates. The proposed total is , not divisible by four. It cannot arise from a binary linear code.