# 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 ↔ p5 + p 2 + 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=(c1,c2,…..cn) is c(1) =

(c2,c3,…..cn,c1).

### Cyclic Codes

c(1)(p) = pc(p) mod (pn+1)

c(k)(p) = pkc(p) mod (pn+1) ∀ k

c(n)(p) = pnc(p) mod (pn+1) =

=(pnc(p)+c(p) + c(p)) mod (pn+1)=

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

### Cyclic Codes

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

= c(p) mod (pn+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) = pn-k + g2pn-k-1 + g3pn-k-2 + … gn-k-1 p+1 multiplo di pn+1

### Cyclic Codes

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

x(p) = x1pK-1 + x2pK-2 + … + xK

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:

p7 + 1 = (p + 1) (p3 + p2 + 1) (p3 + p +1)

The possible generator polynomials are then:

p3 + p2 + 1, p3 + p + 1

### Cyclic Codes

We choose:

p3 + p2 + 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⇒ pn-k is 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 pn-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)= p3+p2+1

The third row is obtained by: p4 mod (p3+p2+1)=p2+p+1 ↔ 0010111
The second row is obtained by: p5 mod (p3+p2+1)=p+1 ↔ 0100011
The first row is obtained by: p6 mod (p3+p2+1)= p2+p ↔ 1000110

### Cyclic Codes

The Hamming codes are cyclic codes

The coder is a multiplier circuit in binary logic.

FIR circuit in binary maths.

The decoder divides the received code word polynomial for g(p) and rest of division is utilized to perform the correction.

### Cyclic Codes

The BCH codes are a subset of the cyclic codes.

They are able to correct t errors.

There exists a very simple algorithm to decode BCH codes : the algorithm of Berlekamp-Massey

For any t and m there exists a BCH code with parameter:

n = 2m – 1

n – k ≤ mt

dmin = 2t + 1

### Cyclic Codes

Since t and m are arbitrary the designer possesses a great selection capability in the BCH code family.

There exist tables in which the coefficients of the polynomials g(p) are reported in octal form.
Example:

The g(p) of the BCH code (15,5) expressed in octal form as 2467 namely:

10, 100, 110, 111 ↔ p10+p8+p5+p4+p2+p+1

### Cyclic Codes

Reed-Solomon Codes

They are a subset of the BCH codes

They are non binary codes : the components of each codeword belong to an alphabet of cardinality q with q=2k.

C(N, K9: bloks of K q-ary symbols are mapped to bloks of N q-ary symbols:

N= q-1 = 2k – 1

K = 1, 2, 3, … , N – 2

Dmin = N – K + 1

$R_c= \frac K N$

### Cyclic Codes

Example:

Determine a polinomial generator, if there exists, for a cyclic code C(7,3) and its minimum distance.

The degree of g(p) must be n-k=4

p7 + 1 = (p + 1)(p3 + p2 + 1)(p3 + p + 1)

…… = (p4 + p2 + p + 1)(p3 + p + 1)

…… = (p3 + p2 + 1)(p4 + p3 +p2 + 1)

g1(p) = p4 + p2 + p + 1

g2(p) = p4 + p3 + p + 1

### Cyclic Codes

Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion