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