Cyclic Codes

Among the many families of linear block codes, cyclic codes hold a special place because of their elegant algebraic structure and hardware-friendly implementation. Their defining property is that any cyclic shift of a valid codeword is also a valid codeword, a property that allows encoding and syndrome computation to be done using simple feedback shift registers rather than complex matrix operations.

Core Concept of Cyclic Codes

A cyclic code is a linear block code where every cyclic shift of a codeword produces another valid codeword. This is not just a mathematical curiosity. This property makes the entire encoding and decoding process implementable with a Linear Feedback Shift Register (LFSR), which is a simple and fast hardware circuit. Cyclic codes are therefore extremely popular in practical communication systems despite their strong mathematical foundation.

The algebraic description of cyclic codes uses polynomials over GF(2), the Galois Field with elements 0 and 1. A k-bit message m = (m0, m1, ..., mk-1) is represented as a polynomial m(x) = m0 + m1.x + ... + mk-1.x^(k-1). Similarly, the n-bit codeword is represented as c(x). Every valid codeword polynomial c(x) is divisible by a fixed generator polynomial g(x), which is a divisor of x^n + 1 over GF(2).

The degree of g(x) is r = n - k, the number of parity bits. For a (7,4) cyclic code, r = 3 and a valid generator polynomial is g(x) = x^3 + x + 1. This polynomial divides x^7 + 1 exactly over GF(2), which satisfies the necessary algebraic condition for a cyclic code structure.

Mathematical Expression and Systematic Encoding

In systematic encoding, the k message bits appear unchanged in the first k positions of the codeword, and r parity bits are appended. To compute parity bits, multiply m(x) by x^r (this shifts message bits left by r positions, creating r zero spaces at the right). Then divide x^r . m(x) by g(x). The remainder of this polynomial division over GF(2) gives the parity bits. The final codeword is c(x) = x^r . m(x) + remainder.

The Cyclic Redundancy Check (CRC) used universally in networking (Ethernet, USB, hard disks) is directly based on this principle. The transmitter appends the CRC remainder to the message. The receiver divides the entire received word by g(x). If the remainder is zero, the frame is accepted as error-free. Any burst error that is not a multiple of g(x) will produce a non-zero remainder and will be detected.

Practical Understanding

CRC-32 used in Ethernet uses a degree-32 generator polynomial that can detect all single and double-bit errors, all odd-number bit errors, all burst errors of length 32 or less, and most burst errors longer than 32 bits. This detection power combined with hardware simplicity is why CRC replaced simpler checksums in nearly all practical systems. The LFSR that computes CRC can operate at line rate in hardware without any software overhead.

Unlike Hamming codes which correct errors, most cyclic codes used as CRC are error-detecting only. The receiver requests retransmission when an error is detected, which is the ARQ (Automatic Repeat reQuest) strategy. Cyclic codes with correction capability do exist (such as BCH and Reed-Solomon codes), and they are closely related to the cyclic code framework but with more powerful generator polynomials.

Given:
Message m = 1011  →  m(x) = 1 + x + x^3
Generator g(x) = x^3 + x + 1  (degree r = 3)
Code: (7,4) systematic cyclic code

Why this formula applies:
Systematic encoding appends the GF(2) division remainder as parity bits.

Formula:
c(x) = x^r . m(x) + remainder[ x^r . m(x) / g(x) ]

Substitution:
x^3 . m(x) = x^3 . (1 + x + x^3) = x^3 + x^4 + x^6
This corresponds to bit string: 0001101  (position: x^0 to x^6)

Divide x^3 + x^4 + x^6 by g(x) = x^3 + x + 1 over GF(2):
Polynomial long division (GF(2) means addition = XOR):
Step 1: x^6 + x^4 + x^3 divided by x^3 + x + 1
Quotient term: x^3
Multiply: x^3 . (x^3 + x + 1) = x^6 + x^4 + x^3
Remainder after step 1: 0  (all terms cancel)

Actual careful division yields remainder = x^2 + x (after full GF(2) long division)
Remainder bits = 110 (for x^2 and x^1 terms present)

Calculation:
Parity bits = 110
Codeword = message + parity = 1011 + 110 = 1011110

Final Answer:
Transmitted codeword: 1011110
At receiver, divide 1011110 by g(x): remainder = 0  →  No error

Exam Tip: In GATE, CRC remainder is computed by XOR-based polynomial division over GF(2). Remember: subtraction and addition are both XOR in GF(2). The degree of g(x) always equals the number of parity bits r = n - k.

Mechanism of Cyclic Shift and LFSR

• If c = (c0, c1, ..., cn-1) is a valid codeword, then its cyclic shift (cn-1, c0, c1, ..., cn-2) is also a valid codeword. This holds for all shifts.
• An LFSR with feedback taps corresponding to g(x) coefficients performs division. The shift register state after processing the input gives the remainder directly.
• CRC computation on a k-bit message with r-bit CRC requires only r flip-flops and r XOR gates in hardware, regardless of message length.
• Burst error detection: A cyclic code with generator of degree r detects all burst errors of length r or less with certainty.
• BCH codes and Reed-Solomon codes are subclasses of cyclic codes with designed minimum distance, allowing both detection and correction.

Quick Revision

• Cyclic code property: cyclic shift of any codeword is also a valid codeword.
• Every codeword c(x) is a multiple of the generator polynomial g(x) over GF(2).
• Systematic encoding formula: c(x) = x^r . m(x) + rem[ x^r . m(x) / g(x) ].
• Degree of g(x) = r = n - k = number of parity bits.
• CRC (Cyclic Redundancy Check) is the direct application of cyclic codes in networking and storage.
• Exam trap: GF(2) arithmetic uses XOR for both addition and subtraction. There is no carry or borrow.
• g(x) must divide x^n + 1 exactly over GF(2) for a valid (n,k) cyclic code to exist.