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

Binary cyclic code

A binary cyclic code is a linear block code in which every cyclic shift of a codeword is also a codeword. If $(c_0,c_1,\dots,c_{n-1})$ is a codeword, so is $(c_{n-1},c_0,\dots,c_{n-2})$.

Code vectors are treated as polynomials $c(x)=c_0+c_1x+\dots+c_{n-1}x^{n-1}$. An $(n,k)$ cyclic code is defined by a generator polynomial $g(x)$ of degree $n-k$ that divides $x^n+1$. Every codeword is a multiple of $g(x)$. Cyclic codes are easy to encode and decode with shift registers (used in CRC).

Given

$(n,k)=(7,4)$, $n-k=3$, $g(x)=x^3+x^2+1$. It is a valid generator since $x^7+1=(x+1)(x^3+x+1)(x^3+x^2+1)$.

Convention: the leftmost data bit is the highest power. Data $1011$:

$$d(x)=x^3+x+1$$

All arithmetic is modulo 2 ($1+1=0$).

(a) Non-systematic codeword

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

(three $x^3$ terms leave one $x^3$.)

Non-systematic code vector: 1 1 1 1 1 1 1

(b) Systematic codeword

Steps: multiply by $x^{n-k}=x^3$, divide by $g(x)$, append the remainder as parity bits.

$$x^3d(x)=x^6+x^4+x^3$$

Long division by $g(x)=x^3+x^2+1$:

              x^3 + x^2            <- quotient
          ---------------------------
x^3+x^2+1 ) x^6 +     x^4 + x^3
            x^6 + x^5 +       x^3
            -----------------------
                  x^5 + x^4
                  x^5 + x^4 +       x^2
                  -------------------
                                    x^2   <- remainder

Remainder $p(x)=x^2$, i.e. parity bits $(x^2,x^1,x^0)=1\,0\,0$.

$$c(x)=x^3d(x)+p(x)=x^6+x^4+x^3+x^2$$

Check: $c(x)=(x^3+x^2)\,g(x)$, a multiple of $g(x)$, so it is a valid codeword.

Systematic code vector: 1 0 1 1 | 1 0 0 (data bits followed by parity bits).

Shift-register encoder check

The remainder can be produced by a 3-stage feedback shift register (taps at the non-zero coefficients of $g(x)=1+x^2+x^3$). With feedback $f=\text{input}\oplus r_2$, the update is $r_0\leftarrow f$, $r_1\leftarrow r_0$, $r_2\leftarrow r_1\oplus f$.

After 4 shifts the register holds $(r_0,r_1,r_2)=(0,0,1)$, i.e. remainder $x^2$; read out $r_2r_1r_0=100$, the same parity bits as the long division. The 4 data bits are sent first, then the gate opens and the 3 parity bits follow.