[go: up one dir, main page]

0% found this document useful (0 votes)
154 views9 pages

Cyclic Codes

The document discusses cyclic codes, which are a type of error correcting code used in digital communications. Cyclic codes can detect and correct errors by adding redundant bits to transmitted data. They are generated using polynomial operations on the data and a generator polynomial. At the receiver, the generator polynomial is used to calculate a syndrome value for error detection and correction. Examples of cyclic code encoding and decoding are provided to illustrate the process. Interleaving is also discussed as a technique to improve immunity to burst errors.

Uploaded by

Mostafa Atrash
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
154 views9 pages

Cyclic Codes

The document discusses cyclic codes, which are a type of error correcting code used in digital communications. Cyclic codes can detect and correct errors by adding redundant bits to transmitted data. They are generated using polynomial operations on the data and a generator polynomial. At the receiver, the generator polynomial is used to calculate a syndrome value for error detection and correction. Examples of cyclic code encoding and decoding are provided to illustrate the process. Interleaving is also discussed as a technique to improve immunity to burst errors.

Uploaded by

Mostafa Atrash
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 9

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

 Coding is used for :


- error detection and/or error correction (channel coding).
- ciphering (security).
- compression (source coding).
 In coding extra bits are added(channel coding) or removed in
data transmission(source coding).
 Channel coding can be realized by two approaches
 FECC (forward error coding)
- block coding, often realized by cyclic coding
- convolutional coding
 ARQ (automatic repeat request)
- stop-and-wait
- go-back-N
- selective repeat … etc.
 Note: ARQ applies FEC for error detection

About CYCLIC CODES

1
CYCLIC codes are subclass of group codes which don't posses the all
zero code word.

GROUP(Linear)

Others CYCLIC (Polynomial generated)

Golay BCH

Reed-Solomon Binary BCH

Hamming (e=1) e >1


(Fig1)

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 )

Is a valid code word.

Some features of the CYCLIC codes:

1- It allow us to detect and correct high order of errors.


n−k
t= . t : is the number of bits that can be corrected.
2
n : the block size.
k : the original data size.
The can easily implemented using shift registers and expulsive
ors.
2- All code words are a shifts of each others.
3- They can represented as and derived using polynomials.
Polynomial codeword generation :

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)

Systematic and non systematic cyclic codes:


- The systematic code is the code that the information bites are part of
the codeword and this is done her by :
C=X n−k∗M ( x ) mod P ( x ) + X n−k∗M ( x )
- The non systematic code is the code that the information bits are not
apart of the codeword, and it is don here by:
∁=P( x )∗M ( x )

Example : let M(x) = 1010 and P(x) = X 3 + X 2+ ¿1 . generate the polynomial


codeword corresponding to this massage?
Sol:
- X 3∗M ( x )=1010000
- Divide by 1101

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.

And it can be cheked at the recebent by divaiding it by P(x) again

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.

Fig2: the coding –decoding mechanism.

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.

Hard ware implementation :

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

Fig 3: Corresponding coder for a(7,4) cyclic code


Generated by P(x) = X 3 + X 2+ 1

the data sequence

the following figure shows the decoder for the same generator the switch is down
for 4 bits
polynomial

Gate

reserved data
T T T

Syndrome table lookup for error pattern determination

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 :

Interleaviing means that we marge the Encoded codewords before


Transmiting them so that the data block is separated over many blocks.
This increases the immunity aganste burst errors. See the next figre:

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

Out put interleaving to the Encoder

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

It is designed to detect errors in the received data. Practically it is the


reminder when dividing the massage polynomial M(x) by the generator
polynomial P(x) mod-2 division[[the syndrome s(x)]]. This value is sent
with the data. The receiver do the same process on the data and compeer
the result with that value, if it is not the same that means there is an error.
it sends an ARQ to the transmitter asking for retransmitting the data or it
corrects the data if possible. This technique is wildly used in digital
networks .

Example at CRC of a C(7,4)

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

Common used CRC polynomials (IEEE 802.3):


- 9 bits (CRC-8)
- 17 bits (CRC-16)
- 33 bits (CRC-32)
- 45 bits (CRC-64)

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

As we mention previously we use the generator to calculate the syndrome,


if the syndrome:

- S(x) ≠ 0 ; then there is an error.

- S(x) = 0 ; then either


there is no error
or
the error can't be detected.

When can't we detect the error?


Let r(x) be the received data, C(x) is the transmitted codeword, p(x)
is the generator polynomial, and e(x) be the error (from the channel).
Then :

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.

So it is clare that chosing the generator polynomial is a snsetive step in the


coding process.

How to choose the generator polynomial ?

8
1- If p(x) consists more than one coefficient and the coefficient of
X 0 is 1then all single errors can be detected.

2- If X+1 is a factor of the generator polynomial then it can detect all


odd number of errors.

3- If it doesn't divide X t +1 then, it can detect every two isolated


errors.

4- It should have at least two coefficients.

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]

You might also like