2
$\begingroup$

I think I may be under a misconception. When calculating the CRC code, how many bits do you append to the original message? Is it the degree of the generator polynomial (e.g. x^3+1 you append three 0s) or is it the number of digits used to represent the generator polynomial (e.g. x^3+1 gives 1001 which gives four 0s)?

For example if you had the generator G(x)=x^4+x+2 and the message 10 000 101 would the numerator be 100 001 010 000 or 1 000 010 100 000?

1 Answers 1

1

Calculating the CRC does not itself append any bits to the message. It gives you some output bits that you can afterwards chose to do with as you want.

(Sometimes what you want to do with the output is to use it to compute some bits to append to the message such that the CRC of the augmented message happens to be all zeroes. Or equivalently, you can append sufficiently many zero bits to the message before calculating the CRC, and then subtract the remainder from the padded message, such that the result of that correction will have all-zero CRC).

The number of bits in the CRC is the degree of the generator polynomial. That is, for a generator polynomial of $x^3+1$ you get a 3-bit CRC. This is because the remainder in polynomail division always has lower degree than the divisor, so you only need to represent those terms with lower exponent than the leading term in the generator.

  • 0
    OK. So, yes 5 zeroes are appended there in order to make space for subtracting out the remainder later, such that the final result will have an all-zero remainder, _without_ disturbing any of the original payload bits. There are 5 zeroes, because the initial remainder that you need to subtract can be up to 5 bits long, because the generator polynomial has degree 5.2012-10-04