My professor for my graduate course has given us a task of calculating the hamming distance of the CRC method that he demonstrated in the slide
He showed us how the CRC protocol can catch all single, double, odd number of bit errors, burst errors 2 <= k <= n, burst errors of n+1 where the remainder being a 0 and the message is incorrectly accectped as 1/2^(n-1) since the first and last bits are always fixed to 1, and finally error bursts of greater than n+1 with probability of the remainder being 0 with 1/2^n
Here is my answer so far to his 2 part questions:
a) Consider the parity bit protocol with the p's, q's, and the additional r bit. What is the hamming distance of this protocol? Briefly explain why
We know that the Hamm(code) >= x + 1. Using the parity bit protocol with the p's q's and r's give us 3 bit error detection power. Hence x = 3. This means that the hamming distance of this protocol is >= x + 1 = 3 + 1 = 4.
b) Assume we have a CRC protocol that satisfies all the desirable properties that we described in the slides. What is the hamming distance of this protocol? Briefly explain why.
Like stated above, the hamming distance of a code is x + 1 where x is the x bit error detection power. If we have a CRC protocol that satisfies all of the desirable properties that we discussed in the slide, which were: 1) All single bit errors 2) All double bit errors 3) All odd number of bits errors 4) Error bursts of k bits, 2 <= k <= n
if we use these factors, we can see that the CRC protocol satisfies all error bursts up to an including 2 <= k <= n bursts. This means that the Hamm(Code) >= x+1 = (n-2) + 1 = n-1.
c) For both a) and b), can these protocols be used for error correction, and if so, how many bits can they correct? (i.e., can they perform x-bit correction, and if so, what is x?) Explain how you reached this value.
for a) since we know that the parity bit protocol discussed can detect all 3 or less bit errors, x = 3. We also know that in order to perform x-bit correction: Hamm(code) >= 2x + 1 = 2(3) + 1 = 7,
. I am not sure if this is correct
But for part b) I am confused on the error correction of the CRC protocol. My answer for Hamming Correction is Hamm(code) >= 2x+1 <= 2(n-1)+1 = 2n - 2 + 1 = 2n - 1 I am not even sure if this is right at all or how I could determine the number of bits it can correct.
I actually ended up seeing where I was lacking knowledge for the most part but am still unsure if I am correct with my answers to a) and b). Could someone tell me if I am on the right track? I am not looking for "this is the answer". If I am correct, it would be nice to hear a yes but if not a simple guidance would be very, very appreciated.
for a) since we know that the parity bit protocol discussed can detect all 3 or less bit errors, x = 3 since Hamm(code) >= 4. We also know that in order to perform x-bit correction: Hamm(code) >= 2x + 1. Therefore we can only detect single bit errors because 2(1) + 1 = 3. Anything more would be greater than 4.
for b) we know that the CRC protocol has Hamm(code) >= n+2 where x = n+1. In order for Hamm(code) >= 2x+1, x <= floor(n/2). This protocol could then use error correction.