Cyclic redundancy check (CRC) codes
Active In SP
Joined: Sep 2010
30-12-2010, 02:55 PM
Cyclic redundancy ppt 2010.ppt (Size: 437.5 KB / Downloads: 86)
What is CRC?
A systematic error detecting code
a group of error control bits (which is the remainder --a polynomial division of a message polynomial by generator polynomial) is appended to the end of the message block
with considerable burst-error detection capability
The receiver generally has the ability to send
retransmission requests back to the data source through a feedback channel.
Following are the steps that are involved in sending our message with CRC so that receiver can check for the reliability of the message sent.
Representing n+1 bits using n degree polynomial. And we call it M(x).
CRC bit can be choosen from the following table
Which is polynomial of degree ‘k’ and it is
based on our application .we call it C(x):
Making P(x)[which is n+1 bit message bit + k bit
crc] exactly divisible by C(x).
The polynomial for the received code word P(X) is
divided by the generator polynomial C(X).
If the remainder is not zero:
An indication that an error has occurred in
transmission and the received codeword is not a
valid code word.
1.On dividing B(x) by C(x),B(x) must be of
Higher degree polynomial than C(x).
2.If Degree of both B(x) and C(x) are same then Quotient=1
3.To get remainder subtract C(x) from B(x).
4.For Subtracting use XOR gate.
To make P(x) exactly divisible by C(x) follow the
following three steps:
1.Add k (Degree of CRC choosen) zeros at the end of message M(x) and call the resulting polynomial T(x).
2.Divide T(x) by C(x) and find the remainder.
3.Subtract the remainder from T(x).
Resulting bit is the message that we have to