Cyclic Codes
Cyclic Codes
A
bstract:-
As we can see the telecommunication is waidly spread in our life but the main
enemy of the telecommunication is the noise, which means more error and less
BRE. The channel coding was the thrown of this problem and that was done by
adding more data to protect the information, at this project we are going to study
one of the most important techniques in this filed. it is the CYCLIC CODES we
have define the CYCLIC CODES, show how CYCLIC CODE is
genarated(Encoding),and how to detect and correct errors. we have comperd
between the deferant CYCLIC technequs and mention some applications.
Background:-
1
CYCLIC codes are subclass of group codes which don't posses the all
zero code word.
GROUP(Linear)
Golay BCH
It is called CYCLIC since when rotating any code word of the words the
resulted word is a valid code word such that if :
∁=(I 1 , I 2 , I 3 , I 4 ,… . , I n )
then :
∁' =(I n , I 1 , I 2 , I 3 , I 4 , … . , I n−1 )
2
If a massage of length k bits (mk−1 , mk−2 , … . ,m1 , m0 ) is to be transmitted over
a channel then for coding process it may represented by the polynomial :
M ( x )=m k−1 X k−1 , m k−2 X k−2 , … . , m1 X , m 0
And it is modified by using the generator polynomial P(x) to became the
coded massage to be transmitted. This can be accomplish by polynomials
multiplication or by:
1- bit shift of the massage M(x) by the order of P(x) .
2- Dividing the result by P(x). (mod-2)
3- Then add the result in step 2 to the result in step 1. (mod-2)
1010000
1101
0111000
1101
001100
1101
0001
Then the remainder is 001
- Now add 001 to 1010000 to have the codeword
1010001
Which is the coded data to be transmitted.
1010001
3
1101
0111001
1101
001101
1101
0000
The resultant value is called the syndrome and it is used to detetarmen the
location of the error from the syndrome table.
As we can see from the figure above that the data word is treated
(Encoded) using a generator polynomial (divisor) by the way we have
shown previously. This process generates the reminder which we sent it
with the data over unreliable transition media (there is a probability of
error) to the receiver. At the transmitter said the same generator
polynomial (divisor) will be used to generate the syndrome s(x) and using
a syndrome table it detect the error and correct it.
4
As we have previously said that CYCLIC codes can be implemented
using shift registers and exclusive or gates for example if we consider the
generator polynomial P(x) = X 3 + X 2+ 1 then the encoder used to encod the
data is as follows :
switch
T T T
the following figure shows the decoder for the same generator the switch is down
for 4 bits
polynomial
Gate
reserved data
T T T
Correct data
3 2
Fig 4: the Decoder for a (7,4) cyclic code P(x) = X + X + 1
At the last figer the shift regestors and the X-OR's calculate the syndrome and
the syndrome table determen the location of error.
5
Interleaving :
Input data … … . , I 12 , I 10 , I 9 , I 8 , I 7 , I 6 , I 5 , I 4 , I 3 , I 2 , I 1
I1 I5 I9 I 13
I2 I6 I 10 I 14
I3 I7 I 11 I 15
I4 I8 I 12 I 16
Interleaving memory
… … . , I 11 , I 7 , I 3 , I 14 , I 10 , I 6 , I 2 , I 13 , I 9 , I 5 , I 1
I 13 , I 9 , I 5 , I 1 Block1
I 14 , I 10 , I 6 , I 2 Block2
I 15 , I 11 , I 7 , I 3 Block3
I 16 , I 12 , I 8 , I 4 Block4
This way when a codeword burst (all the block is damaged)then only one
bit is lost which makes easier to correct errors. This technique is used in
reed Solomon coding in CD's and HD.
6
The cyclic redundancy check (CRC):
Not that the CRC length can be changed according to the generator
polynomial (divisor) in our case r = n – k = 7 – 4 = 3 which is the order
of the generator polynomial
7
It is the polynomial we divide the data word by (the divisor) to generate
the codeword[that is why it is called the generator polynomial].
r ( x )=C ( x)+e ( x)
r ( x)
s ( x )=
p(x)
C(x) e(x)
¿ +
p(x) p(x)
e(x)
¿ 0+
P (x )
So if e(x) is dividable over p(x) then the result will be zero , which means
that there is no error or the error can't be detected.
8
1- If p(x) consists more than one coefficient and the coefficient of
X 0 is 1then all single errors can be detected.
References:
- Digital communications 2nd edition Ian A. Glover
- www.Wiki.com
- IEEE 802.3 Cyclic Redundancy Check [Initial Xilinx Release v.1
- http://blacknite.eu/tutorials/crc.htm
- Cyclic redundancy code generator [Patent Application Publication
US 2003/0159101A1]