(7,4) cyclic code G(p) = p³ + p + 1 for 0101

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(p)$ of degree $n-k$ that divides $p^n+1$:

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

Given $(n,k)=(7,4)$, $G(p)=p^3+p+1$, $n-k=3$. Convention: leftmost message bit is the highest power. Message $0101$:

$$M(p)=0\cdot p^3+1\cdot p^2+0\cdot p+1=p^2+1$$

All additions are modulo 2.

Non-systematic form

$$\begin{aligned} X(p)&=M(p)\,G(p)=(p^2+1)(p^3+p+1)\\ &=p^5+p^3+p^2+p^3+p+1\\ &=p^5+p^2+p+1 \end{aligned}$$

Coefficients from $p^6$ down to $p^0$:

Non-systematic code vector: 0100111

Systematic form

1. Multiply by $p^{n-k}=p^3$: $p^3M(p)=p^5+p^3$.
2. Divide by $G(p)$:

              p^2
            -----------------
 p^3+p+1 )  p^5 +       p^3
            p^5 +       p^3 + p^2
            ---------------------
                              p^2   <- remainder

3. Remainder $C(p)=p^2$, so parity bits $(p^2,p^1,p^0)=100$.
4. $X(p)=p^3M(p)+C(p)=p^5+p^3+p^2$.

Check: $X(p)=p^2\,G(p)=p^5+p^3+p^2$, a multiple of $G(p)$.

Systematic code vector: 0101 100 (message bits, then check bits)