Homework 2: Error Detection and Correction

Question 1: CRC

A cyclic redundancy check(CRC) is an error detecting code that is commonly used in links. In CRC, given a data block of n bits you generate k check bits such that the n+k bits are evenly divisible by a generating polynomial C. The error detecting capability depends upon the generating polynomial. One such polynomial is CRC 32

Standard CRC-32 is X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1

Show the following for CRC 32
1. Hamming distance is 4.
2. It can detect upto triple bit errors.
3. It cannot detect all odd number of errors.

Question 2: Hamming Code

Hamming codes are linear error-correcting codes invented by Richard Hamming. It uses a code with message length n = 2^r-r-1 for every r>=2. Show that the code has a hamming distance of 3