(7,4) cyclic code g(x) = 1 + x + x³ for 1011

A cyclic code is a linear block code in which every cyclic shift of a codeword is also a codeword. An $(n,k)$ cyclic code is generated by a polynomial $g(x)$ of degree $n-k$ that divides $x^n+1$:

• Non-systematic encoding: $c(x)=m(x)\,g(x)$; message bits are not visible directly in the codeword.
• Systematic encoding: $c(x)=x^{n-k}m(x)+\text{rem}\left[\dfrac{x^{n-k}m(x)}{g(x)}\right]$; the message appears unchanged and the remainder gives the $n-k$ parity bits.

Given $(n,k)=(7,4)$, $g(x)=1+x+x^3$, $n-k=3$. Convention (Haykin): message $(m_0m_1m_2m_3)=1011$ in ascending powers of $x$:

$$m(x)=1+x^2+x^3$$

All arithmetic is modulo 2.

Non-systematic form

$$\begin{aligned} c(x)&=m(x)g(x)=(1+x^2+x^3)(1+x+x^3)\\ &=(1+x+x^3)+(x^2+x^3+x^5)+(x^3+x^4+x^6)\\ &=1+x+x^2+x^3+x^4+x^5+x^6 \end{aligned}$$

($x^3$ appears three times, leaving $x^3$.)

Non-systematic code vector $(c_0\dots c_6)$ = 1111111

Systematic form

1. $x^{n-k}m(x)=x^3+x^5+x^6$
2. Divide by $g(x)=x^3+x+1$:

              x^3 + x^2 + x + 1
          ---------------------------
x^3+x+1 ) x^6 + x^5 +       x^3
          x^6 +       x^4 + x^3
          -------------------------
                x^5 + x^4
                x^5 +       x^3 + x^2
                -----------------------
                      x^4 + x^3 + x^2
                      x^4 +       x^2 + x
                      -------------------
                            x^3 +       x
                            x^3 +       x + 1
                            -----------------
                                          1

3. Remainder $b(x)=1$, parity bits $(b_0b_1b_2)=100$.
4. $c(x)=b(x)+x^3m(x)=1+x^3+x^5+x^6$.

Check: quotient $\times\,g(x)=(1+x+x^2+x^3)(1+x+x^3)=1+x^3+x^5+x^6$. Valid.

Systematic code vector $(b_0b_1b_2\,m_0m_1m_2m_3)$ = 100 1011