Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Right but when your calculating the CRC code a step involved is to append 0s to the original message. For example here youtube.com/watch?v=0apqZ4jsGmI at 4:20 why did he five 0s to the end of the data? –  Celeritas Oct 4 '12 at 23:05
    
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. –  Henning Makholm Oct 4 '12 at 23:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.