Question
P7. In this problem, we explore some of the properties of the CRC. For the generator G (=1001) given in Section 5.2.3, answer the following questions.
a. Why can it detect any single bit error in data D?
b. Can the above G detect any odd number of bit errors? Why?
Answer
By dividing the Data bits(appended with 4 zeros) by G, then R= 0100.
Discussions
xyz
a) Without loss of generality, suppose ith bit is flipped, where 0<= i <= d+r-1 and assume that the least significant bit is 0th bit.
A single bit error means that the received data is K=D*2r XOR R + 2i. It is clear that if we divide K by G, then the reminder is not zero. In general, if G contains at least two 1’s, then a single bit error can always be detected.
b) The key insight here is that G can be divided by 11 (binary number), but any number
of odd-number of 1’s cannot be divided by 11. Thus, a sequence (not necessarily
contiguous) of odd-number bit errors cannot be divided by 11, thus it cannot be
divided by G.
Post the discussion to improve the above solution.