CRC Messages with Noise and Error Detection

Question

Two Messages M(x), 10bit length
Generator G(x) = X^5 + X^4 + x + 1
Generated Messages: T1(x) , T2(x)
Noise: For 1st message E1(x) =100000010000001 
Noise: For 2nd message E2(x) =100000001110011 

Can we detect the errors for both of messages?

Basically I don't know how to approach this because I don't even know the original messages M(x). If I knew at least the final the messages T1 and T2 , I would divide them with G(x) and if it was 0 then everything is alright, else there is a problem. Now, here what am I supposed to do? Is there some part of my theory that I am missing?

Btw, it is not an assignment/schoolwork or something... I just found this question on the internet and it is bugging A LOT me to be honest.

Thanks in advance!

~Stv

Answer 1

You don't need to know the messages to verify if the errors can be detected. You know that T1(x) and T2(x) are divisible by G(x) with reminder zero (because they were constructed to be like that!).

The errors can't be detected if E1(x) divided by G(x) gives reminder zero! Same for E2(x)!

Note: sorry for the formatting! I'm mobile...

Answer 2

Error detection with CRC is just that. You check whether the received polynomial is divisible by the generator. If it is, then you accept it, and assume that no errors happened. If it is not divisible, then some errors have happened, but you have no idea how many.

I do these by using tricks (typically one would use long division). Your generator is $$ G(x)=x^5+x^4+x+1=(x+1)(x^4+1)=(x+1)^5. $$ The first message is $$ E_1(x)=x^{14}+x^7+1 $$ Because $E_1(1)=1\neq0$, the polynomial $E_1(x)$ is not divisible by $x+1$ let alone its fifth power. Therefore we can conclude that $E_1(x)$ is in error.

The second message takes a bit more work $$ E_2(x)=x^{14}+x^6+x^5+x^4+x+1=x^{14}+x^6+G(x). $$ Here we encounter the reason why $G(x)$ is a very bad CRC-polynomial that should be taken behind the sauna. The remaining terms factor like $$ x^{14}+x^6=x^6(x^8+1)=x^6(x+1)^8. $$ We see that $x^{14}+x^6$ and hence all of $E_2(x)$ actually is divisible by $G(x)$, so given the scheme, we would acceept $E_2(x)$. There is no reason not to!

---

Rant: My guess is that this $G(x)$ was used here for purely pedagogical reasons. This would be a bad choice in practice, because we just saw that all polynomial of the form $x^{n+8}+x^n$ are divisible by $G(x)$. What this means is that it only takes two errorneous bits, eight positions apart, to allow an incorrect message to pass undetected. I could go on quite a while, but let's not. Let me just emphasize that A) this always happens - no matter what the CRC-polynomial is, it will be a factor of some binary polynomial with only two non-zero terms. The problem here is that those two terms only need to be eight positions apart. One of the design criteria of CRC-polynomials is to push that number up as much as possible (how high you can go depends on the degree of the CRC-polynomial). The tables of standard CRC-polynomials give an upper bound for the length of the data block that you can protect with it.