Reed-Muller Codes

Let ; ; and bijective.
View as the Indicator Ring over (with operations and )
and furthermore define for:

with .
Reed-Muller Linear Code of order and length
is the vector subspace of spanned by and wedge products of at most of the .

Example

,

	000	001	010	011	100	101	110	111
	1	1	1	1	1	1	1	1
	1	1	1	1	0	0	0	0
	1	1	0	0	1	1	0	0
	1	0	1	0	1	0	1	0
	1	1	0	0	0	0	0	0
	1	0	0	0	1	0	0	0
	1	0	1	0	0	0	0	0
	1	0	0	0	0	0	0	0

is spanned by . It is the repetition code of length 8

is spanned by .
Deleting the first component of each codeword gives Hamming’s Original Code

is spanned by all the previous plus , and .

Lemma

The vector for and are a basis for

Proof

We have a set of vectors
So it suffices to show they span , equivalently
Let
Let

and

Expanding using distributive law, gives that
But these clearly span .

Corollary

has rank

Lemma

The Bar Product

Proof

We order such that
(where we take ones and zeros)
and for .
Let .
It is a sum of wedge products of
so
Where and are sums of wedge products of …
We have and
So

Corollary

has weight .

Proof

is the repetition code of length , has weight
has weight
If we use induction on with The Bar Product