1

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

Pratham
  • 13
  • 3
  • Something similar was brought up and answered in [this question](https://stackoverflow.com/questions/63312309/cyclic-redundancy-check-single-and-double-bit-error) . – rcgldr Jan 08 '22 at 11:05
  • @rcgldr sir, my doubt is in the paragraph quoted above the author said-- for detecting 2-bit isolated error (x^i + x^j) => x^j[x^(i-j) + 1] , let (i-j) = t --> our polynomial generator should not divide (x^t + 1) where, t is from 2 to n-1. t=0 is meaningless (I understand) but why excluding t=1? 2 consecutive error must also be detected right? – Pratham Jan 08 '22 at 12:36
  • If you could update your question to include the later part of the book where it explains why "t = 1 is needed", that would help. Seems it would be better stated that g(x) must not divide (x^i + x^j), where i ≠ j, and i+j < n. – rcgldr Jan 09 '22 at 07:55
  • @rcgldr yes, I have referred Tanenbaum and there also they are not saying something about the lower bound of t. I don't know why they have excluded t=1 in forouzan book. I have added the screenshots you can check them. – Pratham Jan 09 '22 at 11:37

1 Answers1

2

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.

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • Thank You, sir, I can't agree with you more :) – Pratham Jan 09 '22 at 13:38
  • Hello, I am a beginner in CRC. Things are not that intuitive to me. So sorry, if I am asking anything too trivial or silly.. Please can you explain `this reduces the maximum length that the CRC is guaranteed to detect 2 bit errors from n-1 to (n/2)-1`, the mathematics I mean, a little bit? – Abhishek Ghosh Jan 09 '22 at 14:31
  • For odd bit errors, we need `(x+1)` to be a factor of `G(X)`, i.e. `G(X)=(x+1).F(X)`. `F(x)!=1`. And for two bit errors, `G(X)` should not divide `(x^t+1)` and hence `(x+1)`, for `t==1`. Now if `G(x)` has `(X+1)` as factor, then also `G(X)` shall not divide `(x+1)`. Because based on our assumption, `(X+1)/G(x)=1/F(X)` and this does not have remainder `0`... So why not have t==1 condition as well... This is my thought process... – Abhishek Ghosh Jan 09 '22 at 14:33
  • Or it is so that based on this: `Now if G(x) has (X+1) as factor, then also G(X) shall not divide (x+1). Because based on our assumption, (X+1)/G(x)=1/F(X) and this does not have remainder 0... So why not have t==1 condition as well...` `t==1` need not be satisfied explicitly? (I mean implicitly is it being satisfied?) so they are removing `t=1` condition ... [as other options make sure that G(x) does not divide (x+1) as I thought in the above comment] Please can you help me... @rcgldr – Abhishek Ghosh Jan 09 '22 at 14:37
  • 1
    @AbhishekGhosh - I updated my answer. The "t = 1 is needed" is clarified later by stating g(x) = x+1 cannot detect adjacent errors, and then in another statement, doesn't special case t = 0 or t=1, just stating "t between 0 and n-1", except the t = 0 case is zero errors, since (x^0 + 1) = (1 + 1) = 0. – rcgldr Jan 09 '22 at 16:19
  • Ok, @rcgldr, I think I have got the point now. The problem I guess arose because of the language of the text... The text special case `t=1` and "it is needed" is used in the sense that `t=1 is indeed needed to be considered as a possible value of t so that our g(x) works fine` – Abhishek Ghosh Jan 09 '22 at 19:45
  • If my last comment is correct, @rcgldr please can you explain me, why in the summary [Third picture third point] the authors are considering, `t=2 to n-1` along with the other three points? It is so because that the so called good `g(x)` as per points 1,2,4 mentioned, cannot divide `(x^1+1)` so they are not including it? [Not considering t=0 is fine as it is non sense] – Abhishek Ghosh Jan 09 '22 at 19:53
  • 1
    @AbhishekGhosh - I consider to be a mistake or at least confusing. It would be simpler to state `t = 1 to n-1`. (As noted above, t = 0 is a zero bit error case). – rcgldr Jan 10 '22 at 01:55