COMPUTER NETWORKS
Dr. Veena S
Department of Computer Applications
COMPUTER NETWORKS
Data Link Layer – Error
Detection – CRC
Dr. Veena S
Department of Computer Applications
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
▪ Reduce the number of extra bits and maximize protection
▪ Use polynomial arithmetic
▪ Given a bit string 110001 we can associate a polynomial on a
single variable x for it
▪ 1.x5+1.x4+0.x3+0.x2+0.x1+1.x0 = x5+x4+1 and the degree is 5
▪ a k+1 bit frame has a maximum degree of k
▪ Let M(x) be a message polynomial and C(x) be a generator
polynomial
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
▪ Let M(x)/C(x) leave a remainder of 0
[C(X) is selected in such way]
▪ Receiver receives M’(x)
▪ The receiver computes M’(x)/C(x) and if the remainder is
nonzero, then an error has occurred
▪ The only thing the sender and the receiver should know is
C(x)(Generator)
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
▪ Polynomial Arithmetic Modulo 2:
▪ Any polynomial B(x) can be divided by a divisor polynomial
C(x) if B(x) is of higher degree than C(x)
▪ Any polynomial B(x) can be divided once by a divisor
polynomial C(x) if B(x) is of the same degree as C(x)
▪ The remainder obtained when B(x) is divided by C(x) is
obtained by subtracting C(x) from B(x)
▪To subtract C(x) from B(x), we simply perform the exclusive-
OR (XOR) operation on each pair of matching coefficients
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
▪ Let M(x) be a frame with m bits and let the generator
polynomial be C(x)
▪ Let k be the degree of C(x)
▪ Multiply M(x) by 2k (Append k zero bits to the low-order end
of the message. We call this T(x) zero extended message)
– (Left shift the bit pattern by k places)
▪ Divide T(x) by C(x) using modulo 2 division and find the
remainder
▪ Subtract the remainder from T(x) using modulo 2 subtraction
▪ Resultant polynomial is completely divisible by C(x)
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
▪ Let the message to be communicated is x7 + x4 + x3 + x
CRC Calculation using Polynomial Long Division
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
▪ Six generator polynomials that have become international
standards are:
▪ CRC-8 = x8+x2+x+1
▪ CRC-10 = x10+x9+x5+x4+x+1
▪ CRC-12 = x12+x11+x3+x2+x+1
▪ CRC-16 = x16+x15+x2+1
▪ CRC-CCITT = x16+x12+x5+1
▪ CRC-32 =
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 =
100000100110000010001110110110111
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
Suppose we want to transmit the message 11001001 and
protect it from errors using the divisor polynomial x3+1
i) Use polynomial long division to determine the message that
should be transmitted.
ii) Suppose the leftmost bit of the message is inverted due to
noise on the transmission link. What is the result of the receiver’s
CRC calculation? How does the receiver know that an error has
occurred?
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
Message - 11001001
c(x) - 1001 k =3 (degree of generator polynomial)
Zero Extended Polynomial - 11001001000,
1001) 1 1 0 0 1 0 0 1 0 0 0 ( 11010011
1001
-------------
1011 polynomial long division
1001
----------
1000
1001
--------- Remainder - 11
1100
1001
------------ Message to be communicated by sender - 11001001011
1010
1001
----------------
11
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
Message - 11001001
c(x) - 1001 k =3 (degree of generator polynomial)
Zero Extended Polynomial - 11001001000,
1001) 0 1 0 0 1 0 0 1 0 1 1 ( 11010011
1001
-------------
001011 polynomial long division
10 01
----------
10
COMPUTER NETWORKS
Cyclic Redundancy Check (CRC)
▪ More powerful error-detection coding
▪ View data bits, D, as a binary number
▪ Choose generator, G
▪ Goal: choose CRC bits, R, such that
▪ <D,R> exactly divisible by G (modulo 2)
▪ receiver knows G, divides <D,R> by G. If non-zero
remainder: error detected!
▪ can detect all burst errors less than r+1 bits
▪widely used in practice (Ethernet, 802.11 WiFi, ATM)
THANK YOU
Dr. Veena S, Chairperson
Department of Computer Applications
[email protected]+91 80 26721983 Extn 829
