Recursive Reed-Muller matrix generation?

Question

I have an assigment where I need to recursively find the generator matrix for a Reed-Muller code, in particular the $RM(r,m)=R(1,3)$ code, where $r$ is the order and $m$ is the message length in bits. Now, a generator matrix can be found using the following (according to my assignment):

$$ G(r,m)= \begin{pmatrix} G(r,m-1)&G(r,m-1) \\0&G(r-1,m-1)\end{pmatrix}$$

Where, to start the induction, $G(0,m)$ is defined as a row vector of $2^m$ ones, $G(m,m)$ is defined as the unit matrix of size $2^m$, and the $0$ represents the all-zero matrix with the same size of $G(r-1,m-1)$.

Here's how I have proceded to find $G(1,3)$:

1. I have wrote down an expression for it: $$ G(1,3)=\begin{pmatrix} G(1,2)&G(1,2) \\0&G(0,2)\end{pmatrix}$$ where $G(0,2)=(1111)$ and $0=(0000)$.
2. I have done the same for $G(1,2)$ which should be: $$G(1,2)=\begin{pmatrix} G(1,1)&G(1,1) \\0&G(0,1)\end{pmatrix}$$ where $G(0,1)=(11)$ and $0=(00)$. Now, if my understanding is correct, $G(1,1)$ should be the unit matrix of size 2, that is the identity matrix of size 2 (if unit matrix = identity matrix, which I'm not actually sure of...). If this is true, then: $$G(1,1)=\begin{pmatrix} 1&0 \\0&1\end{pmatrix}$$
3. At this point, I plug $G(1,1)$ into the matrix for $G(1,2)$ and then I plug that one into $G(1,3)$, which gives me: $$G(1,2)=\begin{pmatrix} 10&&10 \\01&&01\\\\00&&11\end{pmatrix}=\begin{pmatrix} 1010 \\0101\\0011\end{pmatrix}\implies G(1,3)=\begin{pmatrix} 1010&&1010 \\0101&&0101\\0011&&0011\\\\0000&&1111\end{pmatrix}=\begin{pmatrix} 10101010 \\01010101\\00110011\\00001111\end{pmatrix}$$ where I drew the matrices a little "separated" to show where the different parts come from...
   
   This all seems okay with me (unless maybe I totally missed the point), however a quick search on Wikipedia shows me that the generator matrix for a RM(1,3) code is actually: $$G(1,3)=\begin{pmatrix} 11111111 \\10101010\\11001100\\11110000\end{pmatrix}$$ Now, if bit flipping is not a problem, 3 rows of my matrix match the ones from the Wikipedia page, however I do not get the row with all ones, but a bit flipped version of one of the other rows I have (the one with the alternating 0 and 1). What am I doing wrong? Thank you so much!

Answer 1

A generator matrix $G$ of a linear code $C \subset \mathbb{F}_q^n$ (for a prime power $q$ and $n \in \mathbb{N}$) is a matrix whose rows form a basis of $C$ (as $\mathbb{F}_q$-linear subspace of $\mathbb{F}_q^n$). In other words: $C$ is the rowspace of $G$.

In particular, that means that there are lots of different generator matrices for one code because you can conduct $\mathbb{F}_q$-linear row operations without changing the rowspace of the matrix.

In your case: You can obtain the rows of Wikipedia's from your solution as follows where I indicate the rows of your matrix with roman numbers (I-IV):

• first row: I + II
• second row: I
• third row: I + II + III
• fourth row: I + II + IV

Both matrices hence generate the same code.