How to puncture a Reed-Muller code to obtain a cyclic code?

Question

I am reading the book Algebraic Codes for Data Transmission by Richard E. Blahut. In that book, the author says a binary Reed-Muller code of block length $2^m$ can be punctured to get a cyclic Reed-Muller code of block length $2^m - 1$. But the author doesn't tell us which bit of the code vectors must be deleted to get the cyclic code. My intuition says that we must delete the first or last bit of all code vectors to get a cyclic reed-muller code. Could you please help me determine the puncturing pattern of a binary Reed-Muller code to get a cyclic Reed-Muller code?

Answer 1

The Reed-Muller codes have transitive automorphism groups. This implies that it is immaterial which position you puncture – the resulting codes will all be equivalent.

The catch is that to make a punctured Reed-Muller code cyclic, you need to carefully rearrange the bit positions. For example, if you start with the Reed-Muller $R(3,1)$ that is also an extended Hamming code of length $8$, you typically have a generator matrix like the following $$ G=\left(\begin{array}{l}01010101\\ 00110011 \\ 00001111 \\ 11111111 \end{array}\right). $$ Let's say that we puncture the leftmost bit (call it column $0$). To see that we get a cyclic code we need to reorder columns $1$ to $7$ for example(there are many orderings that will work) in the order $1,2,4,3,6,7,5$, when we arrive at $$ \tilde{G}=\left(\begin{array}{l} 1001011\\ 0101110\\ 0010111\\ 1111111 \end{array}\right). $$ Here you will see that the third row can be gotten from the second by cyclically shifting it by one position. Similarly, the cyclic shift of the third row is the first row, and the cyclic shift of the first row is the sum of the two top rows.

In general it goes much the same way. The explanation requires a bit more algebra, most notably the fact that the multiplicative group of a finite field is always cyclic. If you want an algorithm doing this, you can use a maximum length linear feedback shift register. Observe that the top three rows of the matrix $G$ above have all the patterns of three bits as (sub)columns. I tossed out the all zeros column, and cycled the rest of them according to an LFSR of 3 bits with maximal period $2^3-1=7$. Ask, if you want more information.

Answer 2

Consider polynomials of degree $r$ or less in $m$ binary variables $x_0, x_{1}, \cdots, x_{m-1}$. Since $x_i^j = x_i$ for all $j\geq 2$, each variable occurs at most once in any monomial (single term) in the polynomial. Thus, there are $\binom{m}{i}$ monomials of degree exactly $i$, and thus a total of $2^{\sum_{i=0}^r \binom mi}$ polynomials of degree $r$ or less. The images of these polynomials constitute $\operatorname{RM}(m,r)$, the $r$-th order binary Reed-Muller code of length $2^m$ and minimum distance $2^{m-r}$. By image we mean that if $f(x_{m-1}, x_{m-2}, \cdots, x_0)$ is a polynomial of degree $\leq r$, then the corresponding codeword is $$C = \big[f(0,\ldots,0, 0),f(0,\ldots,0, 1),f(0,\ldots,1, 0), f(0,\ldots,1, 1), \cdots, f(1,\ldots,1, 1)\big]$$ that is, we are evaluating $f$ at the $2^m$ positions arranged in natural binary counting order. Note that

• If $f(x_{m-1}, x_{m-2}, \cdots, x_0) = x_0$, then the corresponding codeword is $[0101\cdots 0101]$
• If $f(x_{m-1}, x_{m-2}, \cdots, x_0) = x_1$, then the corresponding codeword is $[0011\cdots 0011]$

and so on till we get to

• $f(x_{m-1}, x_{m-2}, \cdots, x_0) = x_{m-1}$, when the corresponding codeword is $[00\cdots 0011\cdots 11]$

Example: The polynomial pre-images of the codewords of $\operatorname{RM}(4,1)$ are of the form $a_{0}+a_{1,0}x_0 + a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3$ and so the generator matrix of $\operatorname{RM}(4,1)$ is $$G=\left(\begin{array}{l}1111111111111111 \\ 0101010101010101\\ 0011001100110011 \\ 0000111100001111 \\ 0000000011111111 \end{array}\right) \tag{1}$$ where the $5$ rows of $G$ are the codewords corresponding to the mononomials $1,~ x_0,~ x_1,~ x_2,~ x_3$. This is a $[16,5,8]$ nonsystematic code and we get the codeword that encodes the $5$-bit information vector $[a_{0}, a_{1,0}, a_{1,1},a_{1,2}, a_{1,3}]$ by multiplying it by $G$. Note that the first row of $G$ is the generator matrix of $\operatorname{RM}(4,0)$ which is the $[16,1,16]$ repetition code.

The generator matrix of the $\operatorname{RM}(4,2)$ code needs to include $6$ more rows corresponding to the monomials $x_0x_1,~ x_0x_2,~ x_0x_3,~x_1x_2, ~x_1x_3, ~x_2x_3$ which are $0001000100010001,~$ $0000010100000101,~$ $0000000001010101,~$ $0000001100000011,~$ $0000000000110011,~$ and $0000000000001111~$ respectively, giving a $[16,11,4]$ (Hamming!) code.

The above description of the Reed-Muller codes corresponds to the form most commonly seen in textbooks.

---

We puncture this Reed-Muller code by discarding the first coordinate $(0,…,0,0)$ to leave codewords $$C^\prime = \big[f(0,\ldots,0, 1),f(0,\ldots,1, 0), f(0,\ldots,1, 1), \cdots, f(1,\ldots,1, 1)\big]$$ where we are evaluating $f$ at all the nonzero binary $m$-tuples.

We need to evaluate $f$ only at the $N = 2^m-1$ nonzero binary $m$-tuple. Now, recall that the $N$ nonzero elements of $\mathbb F_{2^m}$ all can be represented as powers $\alpha^i, 0\leq i \leq N-1$ of a primitive element $\alpha$ of the field. Note that $\alpha$ has multiplicative order $N$, that is, $N$ is the smallest positive integer such that $\alpha^{N}=1$. Recall also that another representation of the elements of $\mathbb F_{2^m}$ is as binary polynomials of degree $m-1$ or less in $\alpha$. Now, let's permute (and re-number) the code symbol locations so that after the permutation and renumbering, the locations are numbered from $0$ to $N-1$, and the symbol in the $i$-th location, $0 \leq i \leq N-1$, corresponds to $\alpha^i$. More specifically, suppose that $$\alpha^i = \sum_{k=0}^{m-1}\gamma_k^{(i)}\alpha^k \tag{2}$$ (where the $\gamma_k^{(i)}$s all are in $\mathbb F_2$) is the representation of $\alpha^i$ as a binary polynomial of degree $m-1$ or less in $\alpha$. Then the value of the code symbol in location $i, 0 \leq i \leq N-1$, is $f(\gamma_0^{(i)} \gamma_{m-1}^{(i)}, \gamma_{m-2}^{(i)}, \cdots, \gamma_0^{(i)})$.

We apply this formulation to the codeword corresponding to the monomial $x_k$, and see that this codeword is $$[\gamma_k^{(0)},~\gamma_k^{(1)},~\gamma_k^{(2)},~ \cdots,~ \gamma_k^{(N-1)} ]\tag{3}$$ Let $\{\beta_0, \beta_1, \cdots, \beta_{m-1}\}$ denote the dual basis of $\{\alpha^0, \alpha^1, \cdots, \alpha^{m-1}\}$. Then, for $0 \leq k, \ell \leq m-1$, we have that $$\operatorname{Tr}(\beta_k\alpha^\ell) = \begin{cases}1, &k = \ell, \\0, & k \neq \ell, \end{cases}$$ where $\operatorname{Tr}(z) = z^{2^0} + z^{2^1} + z^{2^2} + \cdots +z^{2^{m-1}}$ is the trace function from $\mathbb F_{2^m}$ to $\mathbb f_2$. It is a linear function: $\operatorname{Tr}(a+b) = \operatorname{Tr}(a) +\operatorname{Tr}(b).$ Thus, we have that $(2)$ can be expressed as $$\alpha^i = \sum_{k=0}^{m-1}\gamma_k^{(i)}\alpha^k = \sum_{k=0}^{m-1}\operatorname{Tr}(\beta_k\alpha^i)\alpha^k$$ while the codeword corresponding to the monomial $x_k$ can be expressed as $$[\operatorname{Tr}(\beta_k),~\operatorname{Tr}(\beta_k\alpha),~\operatorname{Tr}(\beta_k\alpha^2),~ \cdots,~ \operatorname{Tr}(\beta_k\alpha^{N-1})].\tag{4}$$ Note that this codeword is just a "cyclic shift to the left" by $\log_\alpha(\beta_k)$ places of the sequence $$[\operatorname{Tr}(1), \operatorname{Tr}(\alpha), ~ \operatorname{Tr}(\alpha^2), ~\cdots, \operatorname{Tr}(\alpha^{N-1})]\tag{5}$$ which is sometimes called the characteristic phase of the sequence.

Next, consider the $[N,m]$ code whose generator matrix has $m$ rows that are the codewords corresponding to $x_0,~ x_1,~ x_2,~ \cdots, ~x_{m-1}$. Each of the $2^m-1$ nonzero codewords in this code can be expressed as $$\sum_{k=0}^{m-1}a_k\left[\operatorname{Tr}(\beta_k),~\operatorname{Tr}(\beta_k\alpha),~ \cdots,~ \operatorname{Tr}(\beta_k\alpha^{N-1})\right] = \left[\sum_{k=0}^{m-1}a_k\operatorname{Tr}(\beta_k),~\sum_{k=0}^{m-1} a_k\operatorname{Tr}(\beta_k\alpha),,~ \cdots,~ \sum_{k=0}^{m-1} a_k\operatorname{Tr}(\beta_k\alpha^{N-1})\right] = \left[\operatorname{Tr}\left(\sum_{k=0}^{m-1}a_k\beta_k\right),~\operatorname{Tr}\left(\left\{\sum_{k=0}^{m-1}a_k\beta_k\right\}\alpha\right),~ \cdots,~ \operatorname{Tr}\left(\left\{\sum_{k=0}^{m-1}a_k\beta_k\right\}\alpha^{N-1}\right)\right]$$ where $[a_0, a_1, \cdots, a_{m-1}]$ is some nonzero binary vector. But, since $\{\beta_0, \beta_1, \cdots, \beta_{m-1}\}$ is a basis for $\mathbb F_{2^m}$ over $\mathbb F_2$, $\sum_{k=0}^{m-1}a_k\beta_k$ takes on each nonzero value in $\mathbb F_2$ exactly once as $[a_0, a_1, \cdots, a_{m-1}]$ ranges over the nonzero binary $m$-tuples. That is, _all_the nonzero codewords in this code are cyclic shifts of each other: they form a cycle with $N$ elements. Since the code generated by the all-ones vector is also cyclic, we conclude that

The punctured $\operatorname{RM}(m,1)$ code with coordinates permuted as described above is a cyclic $[N,m+1,2^{m-1}-1]$ code.

Turning to higher-order punctured and re-arranged RM codes, note that the codeword $C$ corresponding to, say, the monomial $x_1x_3$ is just the bit-by-bit multiplication of the codewords $C^{(1)}$ and $C^{(3)}$ corresponding to $x_1$ and $x_3$ respectively. Let $T_\ell$ denote tne operator that cyclically shifts a codeword leftward by $\ell$ places. Then, $T_\ell(C)$ is just the bit-by-bit product of $T_\ell(C^{(1)})$ and $T_\ell(C^{(3)})$. The polynomial pre-images of $T_\ell(C^{(1)})$ and $T_\ell(C^{(3)})$ are degree-1 polynomials, and so the polynomial pre-image of $T_\ell(C)$ is a degree-2 polynomial. Similarly for higher degree terms: cyclic shifting does not change the degree of the pre-image. Thus we have that

The punctured $\operatorname{RM}(m,r)$ code with coordinates permuted as described above is a cyclic $[N,\sum_{k=0}^r \binom{m}{k},2^{m-r}-1]$ code.

Example (continued): Discarding the first symbol in the $G$ in $(1)$, we get the following generator matrix for the punctured $[16,5,7]$ $\operatorname{RM}(4,1)$ code: $$G^\prime =\left(\begin{array}{l}111111111111111 \\ 101010101010101\\ 011001100110011 \\ 000111100001111 \\ 000000011111111 \end{array}\right)\tag{6}$$ where, as noted previously, the $5$ rows of $G$ are the codewords corresponding to the mononomials $1,~ x_0,~ x_1,~ x_2,~ x_3$. Re-arranging the columns as described above has no effect on the first row, but the other four rows change to give the following generator matrix:

$$\tilde{G^\prime} =\left(\begin{array}{l}111111111111111\\ 100010011010111\\ 010011010111100\\ 001001101011110\\ 000100110101111 \end{array}\right).\tag{7}$$

In constructing this matrix, I have assumed that the minimal polynomial of $\alpha$ over $\mathbb F_2$ is $M_\alpha(z) = 1 + z + z^4$,so that we have $M_\alpha(\alpha)= 1 +\alpha + \alpha^4 = 0$ and so $\alpha^4 = 1 + \alpha$. Note that if we look at the columns of the $4\times 15$ submatrix consisting of the second through the fifth rows of $\tilde{G^\prime}$, the $0$th column is the field element $1 = \alpha^0$, the $1$st column is the field element $\alpha = \alpha^1$, the $2$nd column is the field element $\alpha^2$,the $3$rd column is the field element $\alpha^3$, the $4$th column is the field element $\alpha^4 = 1 + \alpha^1$,the $5$th column is the field element $\alpha^5 = \alpha(\alpha^4) = \alpha(1 + \alpha) = \alpha+\alpha^2$, the $6$th column is the field element $\alpha^6 =\alpha^2+\alpha^3$, and so on and so forth till the $14$th column is the field element $\alpha^{14} = 1+\alpha^3$. Using the more general notation developed, the $i$th column is just $\left[\begin{array}{1} \gamma_0^{(i)}\\ \gamma_1^{(i)}\\ \gamma_{2}^{(i)}\\ \gamma_{3}^{(i)}\end{array}\right]$.

Tbe dual basis of $\{1,\alpha, \alpha^2, \alpha^3\}$ is $\{\alpha^{14}, \alpha^2, \alpha, 1\}$ and it can be verified that the fifth row of $\tilde{G^\prime}$ is of the form $(5)$, the fourth and third rows are the fifth row shifted left cyclically by one place and two places respectively, while the second row is the 5th row shifted left cyclically by 14 places or equivalently, cyclically by one place rightwards.