Home

Federica EU

1/26

Luigi Paura » 13.Cyclic Codes

Cyclic Codes

The cyclic codes are linear block codes with the further property that if c $\in$ C than any cyclic permutation $\in$ C.

Example:

c ≡ (101110) $\in$ C ⇒

(010111) $\in$ C

(101011) $\in$ C

(110101) $\in$ C

(111010) $\in$ C

(011101) $\in$ C

Cyclic Codes

The study of the cyclic codes can be carried out easily thanks to their polynomial representation:

100111 ↔ p⁵ + p ² + p + 1

c ↔ c(p) word polynomial

Any binary block of length n corresponds to a polynomial of degree < n-1 called “code word polynomial”

Cyclic Codes

Proprieties of cyclic codes

A cyclic code C(n,k) is characterized by a generator polynomial g(p) of degree n-k.

Any code word polynomial c(x) is a multiple of g(p) namely:

c(p) = g(p)x(p)

where x (p) polynomial information of degree ≤ k-1

Cyclic Codes

The cyclic shift of one position of the code word:

c=(c₁,c₂,…..c_n) is c⁽¹⁾ =

(c₂,c₃,…..c_n,c₁).

Cyclic Codes

c⁽¹⁾(p) = pc(p) mod (pⁿ+1)

c^(k)(p) = p^kc(p) mod (pⁿ+1)… ∀ k

c⁽ⁿ⁾(p) = pnc(p) mod (pⁿ+1) =

=(pⁿc(p)+c(p) + c(p)) mod (pⁿ+1)=

= [c(p)(pⁿ+1)+c(p)] mod (pⁿ+1) =

Cyclic Codes

=c(p)(pⁿ+1) mod (pⁿ+1)+c(p) mod (pⁿ+1)=

= c(p) mod (pⁿ+1) = c(p)

With n cyclic shifts the code word c is again obtained.
In any cyclic code (n,k) any code word polynomial is a multiple of a polynomial g(x) of degree n-k called the generator polynomial:

g(p) = p^n-k + g₂p^n-k-1 + g₃p^n-k-2 + … g_n-k-1 p+1 multiplo di pⁿ+1

Cyclic Codes

Let us call x(p) the polynomial corresponding to the information sequence:

x(p) = x₁p^K-1 + x₂p^K-2 + … + x_K

c(p) = x(p) g (p)

Cyclic Codes

Example:
To generate a cyclic code (7,4) we need a generator polynomial of degree 7-4=3:

p⁷ + 1 = (p + 1) (p³ + p² + 1) (p³ + p +1)

The possible generator polynomials are then:

p³ + p² + 1, … p³ + p + 1

Cyclic Codes

We choose:

p³ + p² + 1

and multiply for all possible polynomials x(p) (they are 16 =24) thus obtaining so the 16 codewords

Cyclic Codes

The code defined by the relation:

c(p) = x(p) g (p)

is not systematic since the first k binary symbols are not the k information symbols.

Cyclic Codes

The code word polynomials are then multiples of g(p).

Cyclic Codes

The Generator Matrix of cyclic code

Let us derive the Generator Matrix of a cyclic systematic code.

Any row is a multiple of g(p) since is a code word.

The k-th row will be a polynomial of degree n-k since there are k-1 zeros followed by 1⇒ p^n-kis present.

Moreover, also the last term ( the known term) must be present otherwise if it were zero with one shift the first k symbol all null with at least one parity symbol non null: this is not possible for linear codes.

Therefore the k-th row is a polynomial p^n-k +….+1that is a code word polynomial that coincides with the generator polynomial ⇒

c(p) = g(p) · x(p) = g(p) · 1

Cyclic Codes

Example:

Cyclic code (7,4) with g(p)= p³+p²+1

The third row is obtained by: p⁴mod (p³+p²+1)=p²+p+1 ↔ 0010111
The second row is obtained by: p⁵ mod (p³+p²+1)=p+1 ↔ 0100011
The first row is obtained by: p⁶ mod (p³+p²+1)= p²+p ↔ 1000110