Search code examples
crccrc32crc16error-correctioncrc64

Cyclic Redundancy check : Single and double bit error


Found this in the book by Forouzan (Data Communications and Networking 5E). But, not able to understand the logic behind this.

This is in the context of topic two isolated single-bit errors

In other words, g(x) must not divide x^t + 1, where t is between 0 and n − 1. However, t = 0 is meaningless and t = 1 is needed as we will see later. This means t should be between 2 and n – 1

why t=1 is excluded here? (x^1 + 1) is two consecutive errors, it must also be detected right using our g(x).

2 isolated 1 bit error

enter image description here

enter image description here


Solution

  • The third image states that (x+1) should be a factor of g(x), but this reduces the maximum length that the CRC is guaranteed to detect 2 bit errors from n-1 to (n/2)-1, but it provides the advantage of being able to detect any odd number of bit errors such as (x^k + x^j + x^i) where k+j+i <= (n/2)-1.

    Not mentioned in the book, is that some generators can detect more than 3 errors, but sacrifice the maximum length of a message in order to do this.

    If a CRC can detect e errors, then it can also correct floor(e/2) errors, but I'm not aware of an efficient algorithm to do this, other than a huge table lookup (if there is enough space). For example there is a 32 bit CRC (in hex: 1f1922815 = 787·557·465·3·3) that can detect 7 bit errors or correct 3 bit errors for a message size up to 1024 bits, but fast correction requires a 1.4 giga-byte lookup table.

    As for the "t = 1 is needed", the book later clarifies this by noting that g(x) = (x+1) cannot detect adjacent bit errors. In the other statement, the book does not special case t = 0 or t = 1, it states, "If a generator cannot divide (x^t + 1), t between 0 and n-1, then all isolated double bit errors can be detected", except that if t = 0, (x^0 + 1) = (1 + 1) = 0, which would be a zero bit error case.