Skip to main content

Cyclic codes

Short answer

A cyclic code is a linear block code where every cyclic shift of a codeword is also a codeword. A linear code becomes cyclic if it is generated by a polynomial g(x) that divides x^n+1. For example, the (7,4) code with g(x)=x^3+x+1 gives codeword 1001110; its shifts like 0011101 are also codewords.

Define cyclic codes. Under what conditions does a linear code become a cyclic code? Explain with example.

Definition

A cyclic code is a linear block code with the extra property that a cyclic (end-around) shift of any codeword gives another codeword of the same code. If (c₀ c₁ … c_{n−1}) is a codeword, then (c_{n−1} c₀ … c_{n−2}) is also a codeword.

Conditions for a linear code to be cyclic

  1. The code is linear: the sum (modulo 2) of any two codewords is also a codeword (and the all-zero word is a codeword).
  2. It is closed under cyclic shift.

In polynomial form, a code of length n with codeword polynomial c(x) is cyclic if it is generated by a generator polynomial g(x) of degree n − k that is a factor of xⁿ + 1. Every codeword is c(x) = m(x)·g(x), where m(x) is the message polynomial.

Example: (7,4) cyclic code

xⁿ + 1 = x⁷ + 1 = (x + 1)(x³ + x + 1)(x³ + x² + 1). Choose g(x) = x³ + x + 1 (1011).

Systematic encoding of m = 1001: m(x) = x³ + 1.

  • x³·m(x) = x⁶ + x³ → 1001000
  • Divide 1001000 by 1011: remainder = 110
  • Codeword = 1001110

Cyclic shifts of 1001110: 0011101, 0111010, 1110100, 1101001, 1010011, 0100111. Each of them is again a codeword of this code (for example 0011101 = (x + 1)·g(x)), which shows the cyclic property.

Cyclic codes are easily implemented with shift registers and XOR gates, and CRC and BCH codes belong to this family.

✓ Answer checked by Claude Sonnet 5.5

Related questions

All Data Communication chapter 8 questions →