Introductıon to telecommunıcatıon - cse040 | Lab Project Report | Cyclic Redundancy Check | | 0701020045 Berat Özbay | 25/4/2012 |

Contents 1. Introduction: The Need for Error Detection 3 1.1 Error detection process 3 1.2 Types of errors 4 1.2.1 Single bit error 4 1.2.2 Burst error 4 2. Cyclic Redundancy Check 4 2.1 Background 4 2.2 Idea behind the CRC 5 2.3 CRC Algorithm 5 2.3.1 Modulo 2 Arithmetic 6 2.3.2 Polynomial representation 8 2.3.3 Digital Logic 9 2.4 Why CRC works 10 3. The Generator Polynomial and Error Detection Capabilities 10 3.1 Kinds of error CRC detects 10 4. References 11

1. Introduction: The Need for Error Detection
In communication systems, data transmitted over a channel will be exposed to transmission impairments. The most significant impairments are attenuation, delay distortion and noise. These impairments cause the received signal to be different than the transmitted signal which is not a desired situation. An error detection technique allows the receiver to determine if the received data is corrupted or not.
1.1 Error detection process
To enable detection of errors, an error detection technique appends (n - k) extra bits to k data bits to be transmitted, creating an n bit frame. Appended bits are called redundant bits because they do not change the data bits and discarded by the receiver as soon as the integrity of the data bits is determined. Redundant bits (also called the checksum) are computed as a function of data bits to be sent. Receiver applies the same function used by the transmitter to data bits and compares the result to redundant bits. If they match there is no error, if they do not match an error is detected.

1.2 Types of errors
There are two general types of errors which an error detection technique must consider.
1.2.1 Single bit error
A single bit error means only 1 bit of a given message is flipped. Single bit errors are least likely to happen in serial transmission systems. For example, an impulse noise event that last 0.5 microseconds on a cable at a data rate of 100Mbps would cause 0.5/0.01 = 50 consecutive erroneous bits. To have a single bit error at 100Mbps duration of the noise event must be 0.01 microseconds, which is very hard to happen.
1.2.2 Burst error
Burst error is defined as a group of two corrupted bits that are separated by k bits. Intermediate bits do not have to be erroneous. In the above example an impulse noise event that last 0.5 microseconds on a cable at a data rate of 100Mbps caused 0.5/0.01 = 50 consecutive erroneous bits. That is a burst error of size 50. Higher data rates cause the effects of burst errors to be greater.
2. Cyclic Redundancy Check
Cyclic redundancy check (CRC) is a very common and powerful error detecting technique for digital data. CRC follows the common error detection process. It generates (n - k) redundant bits (called frame check sequence) to a given k bit message, resulting in an n bit frame that is exactly divisible by some predetermined number.
2.1 Background
The simplest error detection technique, parity checking, makes the total number of ‘1’s in a bit sequence even or odd. If a message sent with even parity, number of ‘1’s including the parity bit is even. If a message sent with odd parity, number of ‘1’s including the parity bit is odd. The parity bit can be generated easily with XOR gates.
An example of a transmission sent using even parity is as follows: * Suppose station A wants to transmit the bit sequence 0100 to station B. * A computes the parity bit:

* A appends the parity bit to the message and sends 01001.
Notice that the sent message has even number of ‘1’s. * B receives corrupted bit sequence 11001. Corrupted message has odd number of ‘1’s!

* B computes parity of the received message and determines that the received data has odd number of ‘1’s instead of even number of ‘1’s.

* B request retransmission of the message.
Parity check can detect all odd number of single bit errors but fails if even number of errors occurs. It can be seen that parity checking is not a good method for detecting burst errors which happens more often at high data rates. These disadvantages of parity check method leads to necessity of a more capable error detection method. Cyclic redundancy code is developed to satisfy that necessity.
2.2 Idea behind the CRC
The idea behind the cyclic redundancy check is actually a very simple one. Assume the message to be transmitted is a binary number. Divide that number by a predetermined divisor. Remainder of the division operation is the frame check sequence (FCS). Receiver divides whole frame by the same predetermined binary number. If it the remainder is zero there are no errors. If it is not zero an error (or more than one error) has occurred. Because CRC is an error detection algorithm, it only adds just enough redundant bits to determine whether an error occurred or not, location of the erroneous bits are irrelevant.
2.3 CRC Algorithm
Before starting some definitions must be made: * T = n-bit frame to be transmitted * D = k-bit block of message to be sent, the first k bits of T * F = (n – k)-bit FCS, the last (n - k) bits of T * P = pattern of n – k + 1 bits; this is the predetermined divisor. Also called the generator. First and last bits must be 1.

1. Multiply D by2(n-k). This will ensure that every bit of D will be processed.
This is equivalent to padding D with (n - k) zeros. 2. Divide 2(n-k)D by P using modulo 2 arithmetic.
Remainder of the division operation is the F. 3. Replace the last (n - k) bits of 2(n-k)D with F
Resulting binary sequence is the T. 4. Send T to receiver.
T = 2(n-k)D+F 5. Receiver divides T by P. If the remainder is zero there is no error. If it is not an error is detected.
The reason modulo 2 arithmetic used is because it always gives a remainder of length less than the generator polynomial. It is also easy to implement in digital logic.
CRC process can be expressed in 3 equivalent ways: Modulo 2 arithmetic, polynomials, and digital logic.
2.3.1 Modulo 2 Arithmetic
Modulo 2 arithmetic uses binary arithmetic with no carries. Without carries, there are only four cases for addition and subtraction operations. This is equivalent to XOR operation.
0 + 0 = 0 0 – 0 = 0
0 + 1 = 1 0 – 1 = 1
1 + 0 = 1 1 – 0 = 1
1 + 1 = 0 1 – 1 = 0
It can be seen that both addition and subtraction operation yields the same result. With these properties, even it is clear that (11100)2 is greater than(100)2, it is not possible to say (11100)2 is greater than(11010)2 in modulo 2 arithmetic. Because both (11100)2-(110)2 =(11010)2 and (11100)2+(110)2=(11010)2 give the same result. This is characteristic of modulo 2 arithmetic be defined as: For a number to be same or greater than another number, its highest bit position which holds a ‘1’ must be the same or greater than the other number’s highest bit position which holds a ‘1’.

2.3.1.1 Example CRC computation

D = 100011011 (k = 9 bits)
P = 11001 (n – k + 1 = 5 bits)
F = to be calculated (n - k = 4 bits)
T = to be calculated (n = 13 bits)

Transmitter: 1. 24D=1000110110000

Quotient is not important _ _ _ _ _ _ _ _ _ 2. 11001 | 1000110110000 11001 | | | | | | | | 10001 | | | | | | | 11001 | | | | | | | 10000 | | | | | | 11001 | | | | | | 10011 | | | | | 11001 | | | | | 10101 | | | | 11001 | | | | 11000 | | | 11001 | | | 10 | | 00 | | 100 | 000 | 1000 <- F

3. T = 1000110111000

Receiver divides the frame by P:
Quotient is not important

_ _ _ _ _ _ _ _ _
11001 | 1000110111000 11001 | | | | | | | | 10001 | | | | | | | 11001 | | | | | | | 10000 | | | | | | 11001 | | | | | | 10011 | | | | | 11001 | | | | | 10101 | | | | 11001 | | | | 11001 | | | 11001 | | | 00 | | 00 | | 000 | 000 | 0000 <- F

Because T divided by P resulted in 0, frame is not corrupted.
2.3.2 Polynomial representation
Another way of representing the CRC process is to use polynomials with binary coefficients. The coefficients of the polynomials are the bits, and the power of the variable shows the position of the bit in the message D. If we redefine the variables for polynomial representation * T(X) = n-bit frame to be transmitted becomes degree of n-1 polynomial.
T(X) = Xn-kDX+F(X) * D(X) = k-bit block of message to be sent, the first k bits of T becomes degree of k-1 polynomial. * F(X) = (n – k)-bit FCS, degree of less than (n - k) polynomial. * P(X) = pattern of n – k + 1 bits becomes degree of (n – k) polynomial, it is called the generator polynomial. Must have non-zero constant term.

2.3.2.1 Example CRC computation
D(X) = 110111 = X5+X4+0X3+X2+X+1 (degree of 5)
P(X) = 11101 = X4+X3+X2+0X+1 (degree of 4)
F(X) = to be calculated (degree of less than 4) (in modulo 2 arithmetic F is 0010 so F(x) should be X1+0X0 = X)
T(X) = to be calculated (degree of 9)

1. X4DX= X9+X8+0X7+X6+X5+X4

X5+X3+X 2. X4+X3+X2+0X+1 ) X9+X8+0X7+X6+X5+X4 X9+X8+X7+0X6+X5 X7+X6+0X5+ X4 X7+X6+ X5+ 0X4+X3 X5+X4+X3 X5+X4+X3+0X2+X X <- F(x)

3. T(x) = X9+X8+X6+X5+X4+X = 1101110010
Extra zeros are added on the left to make the FCS field have length (n - k) bit

2.3.3 Digital Logic
If the division operation in the section “2.3.1.1 Example CRC computation” examined, it can be seen that we only XOR’ed (same thing as subtracting in modulo 2 arithmetic) various shifts of the generator polynomial with the message until the message is less than the generator polynomial (producing the remainder). This operation can be implemented with a circuit consisting of a shift register and XOR gates.(A group of flip-flop connected in a row forms a shift register)
A CRC circuit consists of: * A shift register of (n - k) bits (flip-flops), same as the degree of the generator polynomial, which is also the length of the FCS. * Excluding the terms Xn-k and 1, coefficients of the generator polynomial determines the numbers and locations of the XOR gates. The constant term 1 means the message will XOR’ed before feeding it to the register. Output of the register’s last bit(most significant bit) goes back into all XOR gates, this way the polynomial XOR’ed (subtracted in modulo 2) to the bits in the register when the value of the bits in register is greater or equal to the generator polynomial.

2.3.3.1 Example circuit design for CRC-8-CCITT
CRC-8-CCITT is used for the calculation of the header error control field (i.e. the FCS) in ATM cells.
CRC-8-CCITT: X8+X2+X+1
So, to implement a CRC circuit for the above polynomial we need an 8-bit shift register and XOR gates at the outputs of the first and second flip flop. And the constant term 1 requires an XOR gate at the input.
X2
X

2.4 Why CRC works
Message to be transmitted after the CRC computation is TX=Xn-kDX+F(X) and we want TX mod P(X)=0.
In the second step of the CRC algorithm Xn-kD(X) is divided by P(X). This operation gives a quotient of Q(X) and a remainder of F(X) so, we can say Xn-kD(X)=P(X)QX+ F(X) which gives us TX=PXQX+ FX+FX= PXQX+2FX. However, all operations in CRC computations use modulo 2 arithmetic so the last equations becomes: TX=PXQX+0FX=PXQ(X). If divide T(X) by P(X) we got,
T(X)P(X)=PXQ(X)P(X)=Q(X) and no remainder.
3. The Generator Polynomial and Error Detection Capabilities
The generator polynomial directly affects the error detection capabilities of the CRC method; to understand that we should see the relationship between errors and the generator polynomial.
An error in a bit cause that bit to flip, i.e. 1 becomes 0 and vice versa. This reversal of bits is equivalent to adding 1 to a bit in modulo 2 arithmetic. This way, it is possible to show errors as a separate polynomial E(X).
Assume that T(X) = X3+X2+1= 1101 and the receiver gets the message as X3+1 = 1001. In another way, received message is T(X) + E(X) =(X3+X2+1) + X2 = 1101 + 0100 = 1001. Receiver divides the received message T(X) + E(X) by the generator polynomial P(X). We know that TX mod P(X)=0 then TX+EX mod PX=EX mod PX. This shows us if E(X) is a multiple of P(X), the error will be undetected.
If we assume that P(X) =X = 1, in the example above, the error E(X) =X2=100 will be undetected.
The generator polynomial P(X) is selected in such a way, it multiples are dissimilar to the error polynomial E(X) created by the transmission impairments.
3.1 Kinds of error CRC detects
Any errors not divisible by the generator polynomial P(X) will be detected. * All single bit errors will be detected if P(X) has more than one non-zero term. * All double bit errors will be detected if P(X) has a factor with at least three terms * All odd bit errors will be detected if P(X) has the factor (x + 1) * Any burst error of length less than the length of the generator polynomial. * A fraction of error bursts of length equal to the length of the generator polynomial.
Fraction equals to 1-2-(n-k-1) * A fraction of error bursts of length greater than the length of the generator polynomial.
Fraction equals to 1-2-(n-k)
4. References

1. Stallings, William. Data and computer communications. Boston London: Pearson, 2011. 214-223.

2. Peterson, W.W.; Brown, D.T.; , "Cyclic Codes for Error Detection," Proceedings of the IRE , vol.49, no.1, pp.228-235, Jan. 1961
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4066263&isnumber=4066234

3. http://en.wikipedia.org/wiki/Cyclic_redundancy_check

4. http://www.cs.jhu.edu/~scheideler/courses/600.344_S02/CRC.html

5. http://ceng2.ktu.edu.tr/~cevhers/ders_materyal/bil311_bilgisayar_mimarisi/supplementary_docs/crc_algorithms.pdf

6. http://en.wikipedia.org/wiki/Computation_of_CRC

7. http://www.users.cloud9.net/~stark/ctappd.pdf

8. http://www.mathworks.com/matlabcentral/fileexchange/19565-polynomial-division-by-convolution-quotient-and-reminder

9. http://www.mathworks.com/help/toolbox/comm/ref/bsc.html

10. http://en.wikipedia.org/wiki/Binary_symmetric_channel