Reed-Muller codes

Reed-Muller shall be abbreviated RM.

The $[8, 4, 4]$ RM code over $GF(2)$ having generator matrix

$$\left( \begin{array}{cccccccc} 1& 0& 0& 1& 0& 1& 1& 0\\ 0& ... ... 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 1 \end{array}\right)$$

is obtained by typing

C:=ReedMullerCode(1,3);
C:
G:=GeneratorMatrix(C);
G;

Encoding a message $w$ using $G$ , is simply the map $w\longmapsto wG$ . Type

W:=InformationSpace(C);
W;
Cwords:=<w*G : w in W>;
Cwords;
#Cwords;

From this, you see all the codewords of C and how many there are.

To get the parity check matrix, type H:=ParityCheckMatrix(C); To see if a vector in $\mathbb{F}^8$ is a codeword, simply compute $Hv$ and check if it is zero or not. Here's a MAGMA example:

V:=AmbientSpace(C);
v:=V![1,0,0,0,0,0,0,0];
v*Transpose(H);

Since this last vector is non-zero, $v$ is not a codeword. If it was a vector received in transmission (with at least one error) then to decode it, hence to find the most likely codeword sent, type

Decode(C,v);

Exercise 3.15.4 (a)   For the parity check matrix $H$ of the RM code of length $8$ , verify $Hc=0$ for three or four codewords c. Decode $(1,1,0,0,0,0,0,0)$ .

(b) Find a parity check matrix of the RM code of length $16$ . Verify $Hc=0$ for three or four codewords $c$ . Decode $(1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0)$ .

To get the dimension of the code, type Dimension(C); To get its minimum distance, type MinimumDistance(C);

Exercise 3.15.5   Find the dimension and minimum distance of the RM code of length $16$ .