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

Example:

*c* ≡ (101110) *C *⇒

(010111) *C*

(101011) *C*

(110101) *C*

(111010) *C*

(011101) *C*

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

100111 ↔ p^{5} + 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**”

**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

The cyclic shift of one position of the code word:

**c**=(c_{1},c_{2},…..c_{n}) is **c**^{(1)} =

(c_{2},c_{3},…..c_{n},c_{1}).

*c*^{(1)}*(p) = pc(p) *mod* (p ^{n}+1)*

*c ^{(k)}(p) = p^{k}c(p) *mod

*c ^{(n)}(p) = pnc(p) *mod

*=(p ^{n}c(p)+c(p) + c(p)) *mod

*= [c(p)(p ^{n}+1)+c(p)] *mod

*=c(p)(p ^{n}+1) *mod

*= c(p) *mod* (p ^{n}+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_{2}p^{n-k-1} + g_{3}p^{n-k-2} + … g_{n-k-1} p+1 *multiplo di

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

*x(p) = x _{1}p^{K-1} + x_{2}p^{K-2} + … + x_{K}*

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

Example:

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

*p ^{7} + 1 = (p + 1) (p^{3} + p^{2} + 1) (p^{3} + p +1)*

The possible generator polynomials are then:

*p ^{3} + p^{2} + 1, *

We choose:

*p ^{3} + p^{2} + 1*

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

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.

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-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 p^{n-k} +….+1that is a code word polynomial that coincides with the generator polynomial ⇒

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

Example:

**Cyclic code (7,4) with g(p)= p ^{3}+p^{2}+1**

The third row is obtained by: p^{4 }mod (p^{3}+p^{2}+1)=p^{2}+p+1 ↔ 0010111

The second row is obtained by: p^{5} mod (p^{3}+p^{2}+1)=p+1 ↔ 0100011

The first row is obtained by: p^{6} mod (p^{3}+p^{2}+1)= p^{2}+p ↔ 1000110

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

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 = 2 ^{m} – 1*

*n – k ≤ mt*

*d _{min} = 2t + 1*

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 ↔ p^{10}+p^{8}+p^{5}+p^{4}+p^{2}+p+1

**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=2^{k}.

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

N= q-1 = 2^{k} – 1

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

D_{min} = N – K + 1

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

p^{7} + 1 = (p + 1)(p^{3} + p^{2} + 1)(p3 + p + 1)

…… = (p^{4} + p^{2} + p + 1)(p^{3} + p + 1)

…… = (p^{3} + p^{2} + 1)(p^{4} + p^{3} +p^{2} + 1)

g_{1}(p) = p^{4} + p^{2} + p + 1

g_{2}(p) = p^{4} + p^{3} + p + 1

*5*. Digital Transmission over AWGN chanel

*6*. Evaluation of P(e) for optimum RX in AWGN

*7*. Error probability for M-PSK

*8*. Noncoherent ML Demodulation of FSK signals in AWGN

*9*. Transmission through bandlimited AWGN channels

*13*. 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