4.5.8 Cyclic Codes

Cyclic codes are a subclass of linear block codes that possess a particularly convenient algebraic structure, making them highly practical for implementation using simple shift-register circuits. Most widely used block codes—such as Hamming, CRC, Bose–Chaudhuri–Hocquenghem (BCH), Golay, and Reed–Solomon (R–S) codes—are cyclic in nature.

A binary code is said to be cyclic if:

The sum of any two codewords is also a codeword (linearity property).
Any cyclic shift of a codeword produces another codeword (cyclic property).

In cyclic codes we use describe encoding operations using a generator polynomial, rather than a generator matrix. The generator polynomial g(X) for a (n,k) cyclic code is:

g (X) = g_{0} + g_{1} X + g_{2} X^{2} + \dots + g_{n - k} X^{n - k}

(4.23)

The coefficients of the polynomial, g_i, are 1 or 0 for binary codes: g₀ and g_n_–_k must be 1. A polynomial g(X) uniquely defines an (n,k) cyclic code if it is of degree n–k and is a factor of X ⁿ+1.

The original k-bit data word is also represented as a polynomial, where the binary data bits serve as coefficients:

d (X) = d_{0} + d_{1} X + d_{2} X^{2} + \dots + d_{k - 1} X^{k - 1}

(4.24)

Similarly, a cyclic-code codeword can be expressed as:

c (X) = c_{0} + c_{1} X + c_{2} X^{2} + \dots + c_{n - 1} X^{n - 1}

(4.25)

A codeword is valid codeword if, and only if, g(X) divides c(X) without remainder.

4.5.8.1 Non-Systematic Codewords

A non-systematic cyclic codeword is generated by multiplying the generator polynomial by the appropriate data polynomial:

c (X) = d (X) g (X)

(4.26)

For example, the generator polynomial g(X)=1+X+X ³ can be used to generate a (7,4) cyclic code. For data word d=0011, corresponding to a data polynomial of d(X)=X ²+X ³, the codeword polynomial is:

c (X) = d (X) g (X) = (X^{2} + X^{3}) (1 + X + X^{3})

= X^{2} + X^{3} + X^{5} + X^{3} + X^{4} + X^{6}

= X^{2} + X^{4} + X^{5} + X^{6} (4.27

(recall that in modulo-2 arithmetic X³+X³=0). The non-systematic codeword polynomial is therefore:

c (X) = 0 \cdot 1 + 0 \cdot X + 1 \cdot X^{2} + 0 \cdot X^{3} + 1 \cdot X^{4} + 1 \cdot X^{5} + 1 \cdot X^{6}

(4.28)

so that the equivalent binary codeword is c=0010111. Note this is non-systematic because the original data word d=0011 is not visible within the codeword.

4.5.8.2 Systematic Codewords

Cyclic codes have the useful property that any cyclic shift of a valid codeword yields another valid codeword. Since each power of X in the codeword polynomial c(X) represents a one-bit shift in time, multiplying by X represents a one-bit shift to the right. In general, for m cyclic shifts, if c(X) is a valid code polynomial, then:

c_{m} (X) = X^{m} c (X) \mod (X^{n} + 1)

(4.29)

is also a valid code polynomial. Modulo-(Xⁿ+1) arithmetic ensures that the cyclic property is maintained, since every valid codeword is a factor of (Xⁿ+1)

A systematic codeword is formed in cyclic codes with the structure:

c = (r_{0}, r_{1}, r_{2}, \dots r_{n - k - 1}, d_{0}, d_{1}, d_{2}, \dots d_{k - 1})

(4.30)

where there are (n–k) parity-check bits, and k original data bits. The polynomial r(X) is called the parity-check polynomial:

r (X) = r_{0} + r_{1} X + r_{2} X^{2} + \dots + r_{n - k - 1} X^{n - k - 1}

(4.31)

To form the codeword, we first right-shift the data polynomial by (n–k) positions by multiplying by Xⁿ^–^k , and then divide by the generator polynomial to obtain a quotient q(X) and the remainder r(X):

X^{n - k} d (X) = q (X) g (X) + r (X)

(4.32)

Adding (in a modulo-2 sense) r(X) to both sides gives:

r (X) + X^{n - k} d (X) = q (X) g (X) = c (X)

(4.33)

Thus, a valid systematic codeword is formed by adding the remainder polynomial to the shifted data polynomial.

By way of example, let us generate a systematic codeword for our data word d=0011 using the generator polynomial g(X)=1+X+X³ to generate a (7,4) cyclic code. First, we obtain the parity-check bits (r₁,r₂,r₃):

\frac{X^{n - k} d (X)}{g (X)} = q (X) + r (X)

(4.34)

That is, we need to divide X³(X ³ + X²) by (1+ X + X³) (all operations modulo-2). The quotient polynomial is q(X)= X³ +X² +X and remainder polynomial is r(X)=X, so the remainder word is r=010. The final codeword is therefore c=0100011.