The cyclic codes are linear block codes with the further property that if c C than any cyclic permutation C.
c ≡ (101110) C ⇒
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”
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=(c1,c2,…..cn) is c(1) =
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) =
=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
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)
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
p3 + p2 + 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⇒ 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 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
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 = 2m – 1
n – k ≤ mt
dmin = 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.
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
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
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
13. Cyclic Codes