Spring'09 Internet Crc

Spring 2009 Internet Prof. URANO, Yoshiyori

Aiesa bin Saad, 4902A126-2 Email: [email protected]

Assignment: Error Control in HDLC 1. Express the data: the last 3 digits in your student ID with 10 bit string. And show its corresponding polynomial. The last 3 digit of my ID is: 126 2x

0 0 29 28

0 27

1 1 1 1 1 1 0 26 25 24 23 22 21 20 64 + 32 + 16 + 8 + 4 + 2 = 126

Therefore, the 10 bit string is 0001111110 Its corresponding polynomial: D(x) = 0 ∙ x9 + 0 ∙ x8 + 0 ∙ x7 + 1 ∙ x6 + 1 ∙ x5 + 1 ∙ x4 + 1 ∙ x3 + 1 ∙ x2 + 1 ∙ x1 + 0 ∙ x0 = x6 + x5 + x4 + x3 + x2 + x1 2. Show its CRC codes in case of G(x)= x6 + x4 + x2 +1 D’(x) = D(x) ∙ xr = (x6 + x5 + x4 + x3 + x2 + x1) ∙ x6 = x12 + x11 + x10 + x9 + x8 + x7 R(x)

= D’(x) / G(x) = x12 + x11 + x10 + x9 + x8 + x7 / x6 + x4 + x2 +1 = x5+x4+x2 +1

CRC codes is x5+x4+x2+1 = 110101

x6+x5 +1 x6+x4+x2+1)x12+x11+x10+x9+x8+x7 x12+ +x10+ +x8+ +x6 x11+ x9+ x7 +x6 x11+ x9+ x7 + +x5 x6+x5 x6+ +x4+x2+1 x5+x4+x2+1

3. Show its polynomial corresponding to the string. The polynomial for 110101 = x5 +x4+x2+1 4. Show the result expected at the receiver in case of error-free data transfer. S(x)

= D’(x) + R(x) = (x12 + x11 + x10 + x9 + x8 + x7) ∙ (x5+x4+x2+1) = x12 + x11 + x10 + x9 + x8 + x7+x5+x4+x2+1

The result expected at the receiver in case of error-free transfer is 0001111110110101

5. Show the result expected at the receiver in case of data transfer with an error of the mth bit where m is the last digit in your student ID. In the case there is an error of the mth bit the result would be 0001111111110101 6. Show that any single bit error can be detected. To check for error, the string received, T(x) divided by the Generating Function, G(x) should have no reminder. As such: R’(x) = T(x) / G(x) = x12 + x11 + x10 + x9 + x8 + x7+ x5 +x4 +x2 +1 / x6 + x4 + x2 +1 x6+x5+1 x6+x4+x2+1)x12+x11+x10+x9+x8+x7+ x5+x4+x2+1 x12+ +x10+ +x8 +x6 x11+ x9+ x7+x6+x5+x4+x2+1 x11+ x9+ x7+ x5 x6+ x4+x2+1 x6+ x4+x2+1 no remainder!

In case of an error, for example in the last bit. (the error is on the CRC bit itself) The bit received is 0001111110110100 R’(x) = T(x) / G(x) = x12 + x11 + x10 + x9 + x8 + x7+ x5 +x4 +x2 / x6 + x4 + x2 +1 x6+x5+1 x6+x4+x2+1)x12+x11+x10+x9+x8+x7+ x5+x4+x2 x12+ +x10+ +x8 +x6 x11+ x9+ x7+x6+x5+x4+x2 x11+ x9+ x7+ x5 x6+ x4+x2 x6+ x4+x2+1 1 (remainder)

There is a remainder, so an error has occurred.