REED-MULLER CODES
An important class of codes which includes the extended Hamming
codes are
Reed-Muller codes. These codes are linear codes defined
recursively. The r-th
order (0<= r <=m) Reed-Muller code of length n=2^m are denoted
by RM(r,m).
We shall define these codes by using Kronecker (Tensor) product of
Matrices.
J = ones(1,2); Z = [0 1];
G00 = [1]
G00 =
1
Z1=Z;
G01 = [ kron(J,G00)], G11 =
[G01; Z1 ]
G01 =
1 1
G11 =
1 1
0 1
Z2 = [ kron(Z,Z1) ];
G02 = [ kron(J,G01) ], G12
= [ kron(J,G11); kron(Z,G01) ] , G22 = [G12 ; Z2]
G02 =
1 1
1 1
G12 =
1 1
1 1
0 1
0 1
0 0
1 1
G22 =
1 1
1 1
0 1
0 1
0
0 1 1
0 0
0 1
Z3 = [ kron(Z,Z2) ];
G03 = [ kron( J , G02 )],
G13 = [ kron( J , G12 ); kron( Z , G02 )],
G03 =
1 1
1 1 1
1 1 1
G13 =
1 1
1 1 1
1 1 1
0 1
0 1 0
1 0 1
0 0
1 1 0
0 1 1
0 0
0 0 1
1 1 1
G23 = [ k[ron(J,G22); kron(Z,G12)], G33 = [G23 ; Z3]
G23 =
1 1
1 1 1
1 1 1
0
1 0 1
0 1 0
1
0 0
1 1 0
0 1 1
0 0
0 1 0
0 0 1
0 0
0 0 1
1 1 1
0 0
0 0 0
1 0 1
0 0 0
0 0 0
1 1
G33 =
1 1
1 1 1
1 1 1
0 1
0 1 0
1 0 1
0 0
1 1 0
0 1 1
0 0
0 1 0
0 0 1
0 0 0
0 1 1
1 1
0 0
0 0 0
1 0 1
0 0
0 0 0
0 1 1
0 0
0 0 0
0 0 1
Note that the matrix
G13 =
1 1
1 1 1
1 1 1
0 1
0 1 0
1 0 1
0 0
1 1 0
0 1 1
0 0
0 0 1
1 1 1
is an extended Hammmig
code.
Fast Decoding for RM(1,m)
We use the matrix
H = [1 1; 1 -1]
H =
1 1
1 -1
To define H(m,i) = kron( kron(eye(2^(m-i)),H), eye(2^(i-1) ).
For R(1,3), we have:
H21 = kron( eye(2),H ), H22 = kron( H,eye(2) ),
H21 =
1 1
0 0
1 -1
0 0
0 0
1 1
0
0 1 -1
H22 =
1 0
1 0
0 1
0 1
1 0
-1 0
0 1
0 -1
H31=kron( eye(4),H )
H31 =
1 1
0 0 0
0 0 0
1 -1
0 0 0
0 0 0
0 0
1 1 0
0 0 0
0 0
1 -1 0
0 0 0
0 0
0 0 1
1 0 0
0 0
0 0 1
-1 0 0
0 0
0 0 0
0 1 1
0 0
0 0 0
0 1 -1
H32=kron( kron( eye(2),H),eye(2) )
H32 =
1 0
1 0 0
0 0 0
0 1
0 1 0
0 0 0
1 0
-1 0 0
0 0 0
0 1
0 -1 0
0 0 0
0 0
0 0 1
0 1 0
0 0
0 0 0
1 0 1
0 0
0 0 1
0 -1 0
0 0
0 0 0
1 0 -1
H33=kron( H,eye(4) )
H33 =
1
0 0 0
1 0 0
0
0 1
0 0 0
1 0 0
0 0
1 0 0
0 1 0
0 0
0 1 0
0 0 1
1 0
0 0 -1
0 0 0
0 1 0
0 0 -1
0 0
0 0
1 0 0
0 -1 0
0 0
0 1 0
0 0 -1
ALGORITHM
We explain the algorithm for the RM(1,3) code by giving two
examples.
Example
a. Suppose the
received word is:
wa = [1 0 1 0 1 0 1 1]
wa =
1 0
1 0 1
0 1 1
STEP 1. Replace
all the zero components of wa by -1.
xa=wa-ones(1,8) ; wxa=wa+xa
wxa =
1 -1
1 -1 1
-1 1 1
STEP 2.
Now we evaluate
wxa1=wxa*H31, wxa2=wxa1*H32, wxa3=wxa2*H33
wxa1 =
0 2
0 2 0
2 2 0
wxa2 =
0 4
0 0 2
2 -2 2
wxa3 =
2 6
-2 2 -2
2 2 -2
STEP3. The
larges component of wxa3 (in absolute value) is 6 occuring in
position 1. The binary position of 6 is 100.
va1 = [1 0 0]
va1 =
1 0
0
Since 6 is positive, the presumed message is
va = [1 1 0 0]
va =
1 1
0 0
The first position is position zero, so the binary position of 2
is 000.
Example
b. Suppose the
received word is:
wb = [1 0 0 0 1 1 1 1]
wb =
1 0
0 0 1
1 1 1
STEP 1. Replace
all the zero components of wa by -1.
xb=wb-ones(1,8) ; wxb=wb+xb
wxb =
1
-1 -1 -1
1 1 1
1
STEP 2. Now
we valuate
wxb1=wxb*H31 , wxb2=wxb1*H32 , wxb3=wxb2*H33
wxb1 =
0 2
-2 0 2
0 2 0
wxb2 =
-2 2
2 2 4
0 0 0
wxb3 =
2 2
2 2
-6 2 2
2
STEP3. The
larges component of wxb3 (in absolute value) is 6
occurring in position 4.
The binary position of 6 is 100.
vb4 = [0 0 1]
vb4 =
0 0
1
Since -6 is negative, the presumed message is
vb = [0 0 0 1]
vb =
0 0
0 1