A most famous relation in
coding theory
is a discrete avatar of the
Fourier transform
which relates the weight enumerator
of a
linear code
and the weight enumerator of its dual
with respect to the standard scalar product, namely
(Cf.
MacWilliams identities.)
A simple example of a dual pair of codes is the
Hamming code
,
a (big)
code whose dual is the (small) first-order
Reed–Muller code
.
The matrix
where
and
is a root of
,
is both a
generator matrix
for
and a
parity check matrix
for
.
The small code
has the simple weight distribution
The MacWilliams formula now gives an explicit expression for
which would be cumbersome to obtain directly.
There is no Fourier transform without Abelian groups and therefore there is no MacWilliams
formula for non-linear codes. The discovery first of the
Nordstrom–Robinson code
in
1967,
non-linear and still formally self-dual for the MacWilliams relation,
followed in
1968
and
1972
[a8]
by the
discovery of two infinite families of non-linear codes, the Preparata and
Kerdock codes, respectively, whose weight enumerators are MacWilliams dual of each
other, were until
[a4]
an unexplained phenomenon. The unsuccessful
efforts of many distinguished researchers on this notoriously difficult problem
[a8]
led one of them to declare
[a5]
that it was
"merely a coincidence" .
A well-known trick in modulation theory to address the
-PSK constellation
consists of using a (very simple) case of the
Gray mapping.
This is a mapping from
to
defined by
and extended to a mapping from
to
in the natural way. The key property is that the mapping
from
equipped with the
Lee distance
to
equipped with the
Hamming distance
is an
isometric mapping
of metric spaces. The trace parametrization of quaternary
-sequences
can be used to show that the Kerdock code as defined in
[a8],
p. 1107,
is essentially the cyclic code associated to construction
of
[a1],
p. 458,
and the construction of
[a9].
In particular, if
denotes a primitive root of
in a suitable
Galois ring,
[a7],
then the matrix
(
,
with
odd) is both a generator matrix for the Kerdock code and a parity check matrix for
the
"Preparata"
code. One sees that the Kerdock and Preparata codes are quaternary analogues of the
first-order Reed–Muller code and of the extended Hamming code, respectively.
The
Goethals
and
Delsarte–Goethals codes,
which are also a quaternary dual pair, are related in a less simple manner to three
error-correcting
BCH codes.
Besides
MacWilliams duality,
the
structure also bears influence on the decoding (cf.
[a4],
Fig. 2)
and on the coset structure of the Preparata code, which gives rise to a new distance-regular
graph of diameter
[a4].
The article
[a4],
which solves a twenty-year-old riddle, was awarded
the 1995 IEEE Information Theory award for best paper. Geometrical repercussions
can be found in
[a3],
[a6].