Homework 2: Error Detection and Correction
Out: Friday October 18
Due: Friday October 25 (midnight)
Turnin: Online
Teams Do it individually
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
- Hamming distance is 4.
- It can detect upto triple bit errors.
- 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
|