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