Search code examples
algorithmchecksumcrc

Very basic understanding on CRC algorithm. Length? Divisor?

Thank you for clicking my question.
I want to understand the CRC algorithm from the scratch.
I tried to read basic articles from Wikipedia and etc... but failed in some detailed points.

So, let me show one practical example case.
When we have to transfer the string "HELLO WORLD!\0" (let me call it as [sz2]) through the network,
also have to verify with CRC...
The [sz2]'s binary value should be like below: (and let me call it as [ar3].)
[01001000010001010100110001001100010011110010000001010111010011110101001001001100010001000010000100000000]

Then, gotta perform a loop code to traverse [ar3].
The first character is 'H' and binary is [01001000]

Question1 : Shall i append [000] at the end of [01001000] and perform "XOR loop", then repeat the same job to the rest 12characters * 8bits chopped [ar3] to make different 13 CRC checksums?
Or, append [000..] at the end of [sz2] and perform the long traversing loop?

Question2 : How to choose good divisor? what is adjacent polynomial for this case [sz2]?
Is there "commonly used polynomial" in general? Or, do we have to calculate through [sz2] to acquire good one?

Question3 : Many explanation contents gives target binary starting with [1...].
But as you can see "HELLO"'s "H" is starting with [0100....].
then, if the divisor is [1011], result of XOR becomes [1111]. What should be the next calculation?

Please teach me master hands; Thank you in advance.

Solution
    1. You append the three zeros once at the end of the entire message.
    2. 1011 has been in common use for a degree-four CRC, e.g. in ITU-T G.704. You can find an analysis for different message lengths on Koopman's site.
    3. No, if the high bit is zero, there is no exclusive-or. The result of the first step is 01001000010.... At the next step there is 1, after which the result is 00010000010....