Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
Il Corso Le lezioni del Corso La Cattedra
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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.


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,… is c(1) =


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

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

Cyclic Codes

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).

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

Cyclic Codes

Cyclic Codes

Cyclic Codes

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


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.

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

Cyclic Codes

Cyclic Codes


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

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
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