Mumbai University > Information Technology > Sem 4 > CN

Marks: 5M

Year: May 2016

Cyclic Redundancy Check

• Stronger kind of error-detecting code is in widespread use at the link layer: the CRC (Cyclic Redundancy Check), also known as a polynomial code.

• Polynomial codes are based upon treating bit strings as representations of polynomials with coefficients of 0 and 1 only. A k-bit frame is regarded as the coefficient list for a polynomial with k terms, ranging from xk−1 to x0xk−1 to x0.

• For example, 110001 has 6 bits and thus represents a six-term polynomial with coefficients 1, 1, 0, 0, 0, and 1: 1x5+1x4+0x3+0x2+0x1+1x01x5+1x4+0x3+0x2+0x1+1x0.

  • When the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, G(x), in advance. Both the high- and low order bits of the generator must be 1.

  • To compute the CRC for some frame with m bits corresponding to the polynomial M(x), the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by G(x).

  • When the receiver gets the checksummed frame, it tries dividing it by G(x). If there is a remainder, there has been a transmission error.

• The algorithm for computing the CRC is as follows:

  -Let r be the degree of G(x). Append r zero bits to the low-order end of the frame so it now contains m + r bits and corresponds to the polynomial xr M(x).

  -Divide the bit string corresponding to G(x) into the bit string corresponding to xr M(x), using modulo 2 divisions.

  -Subtract the remainder (which is always r or fewer bits) from the bit string corresponding to xr M(x) using modulo 2 subtraction. The result is the check summed frame to be transmitted. Call its polynomial T(x).

• Figure below illustrates the calculation for a frame 1101011111 using the generator : G(x) = x4x4 + x + 1.

Checksum:

• The second kind of error-detecting code, the checksum, is closely related to groups of parity bits. The word ‘‘checksum’’ is often used to mean a group of check bits associated with a message, regardless of how are calculated. A group of parity bits is one example of a checksum.
• However, there are other, stronger checksums based on a running sum of the data bits of the message. The checksum is usually placed at the end of the message, as the complement of the sum function.
• This way, errors may be detected by summing the entire received codeword, both data bits and checksum. If the result comes out to be zero, no error has been detected.
• One example of a checksum is the 16-bit Internet checksum used on all Internet packets as part of the IP protocol. This checksum is a sum of the message bits divided into 16-bit words. Because this method operates on words rather than on bits, as in parity, errors that leave the parity unchanged can still alter the sum and be detected.
• For example, if the lowest order bit in two different words is flipped from a 0 to a 1, a parity check across these bits would fail to detect an error. However, two 1s will be added to the 16-bit checksum to produce a different result. The error can then be detected.
• The Internet checksum is computed in one’s complement arithmetic instead of as the modulo 2^16 sum.