Cyclic Redundancy Check

3.    A bit stream 10011101 is transmitted using the standard CRC method.  The generator polynomial is x3+1.  Show the actual bit string transmitted.  Suppose the third bit from the left is inverted during

transmission.  Show that this error is detected at the receiver’s end.

Solution:

Message M (x) = 10011101 = x7+x4+ x3+ x2+ 1
CRC Polynomial C (x) = x3+ 1 = 1001

Multiply the message with x3 since the divisor polynomial is of degree 3.

    ? T (x) = x3 (x7+x4+ x3+ x2+ 1) = x10+x7+ x6+ x5+x3  ? 10011101000

Divide 10011101000 by 1001 i.e., divide T (x) by C (x)


                1000110
      ---------------------------------------------
  1001    | 10011101000 ? Message
              | 1001
        -----------------
                  1101
                  1001
                  ---------
                    1000
            1001
            -----------
                  100 ? Remainder
            -----------

Since T (x) minus the remainder would be exactly divisible by C (x), we subtract the remainder from T (x) as shown below:

Note: The minus operation in polynomial arithmetic is the logical XOR operation.

    T (x):    10011101000
Remainder:            100
        -------------------
        10011101100     ? This turns out to be the original message with
        -------------------      the remainder appended to it.


If the third bit form the left is inverted during transmission, the bit stream would be: 10111101100. Dividing this by 1001 we get:

        10101
      ---------------------------------------------
  1001    | 10111101100 ? Message
              | 1001
        -----------------
              1011
              1001
              ---------
                  1001
                  1001
                ------------
                0100 ? Remainder
                ------------
Since the remainder is 100, which is different form 0, the receiver detects the error and can ask for retransmission.



http://www.cis.temple.edu/~latecki/Courses/CIS617-04/Solutions/archana_guptaHW1.pdf

• Cyclic Redundancy Check 

Goal
Maximize protection, Minimize extra bits
Idea
Add k bits of redundant data to an n-bit message
N-bit message is represented as a n-degree polynomial with each bit in the message being the corresponding coefficient in the polynomial
Example
Message = 10011010
Polynomial
= 1 ?x7 ? 0 ?x6 ? 0 ?x5 ? 1 ?x4 ? 1 ?x3 ? 0 ?x2 ? 1 ?x ? 0
= x7 ? x4 ? x3 ? x

• Cyclic Redundancy Check  

Error Detection
Checked at many layers
? Physical (e.g. modulation)
? Datalink (e.g. cyclic redundancy check)
? Network/Transport (e.g. IP Checksum)
? Application (e.g. MD5 hash)

Today: simple parity, redundancy w/voting, 2
dimensional parity, IP checksum, CRCs


(CRC)
Polynomial code
? Treat packet bits a coefficients of n-bit polynomial
» Message = 10011010
» Polynomial
=1 ?x7 ?0 ?x6 ?0 ?x5 ?1 ?x4 ?1 ?x3 ?0 ?x2 ?1 ?x ?0= 1 ?x7 ?0 ?x6 ?0 ?x5 ?1 ?x4 ?1 ?x3 ?0 ?x2 ?1 ?x ?0
= x7 ?x4 ?x3 ?x


http://cseweb.ucsd.edu/classes/fa09/cse123/123f09_Lec4.pdf

• Computer Networks 2-9: Error Detection

https://www.youtube.com/watch?v=BxCmS7NIDR4