Talk:Computation of CRC

From Wikipedia, the free encyclopedia

[edit] Misimplimentation

Discussion moved from Talk:Mathematics of CRC#Misimplimentation by Regregex (talk) on 13:53, 23 January 2008 (UTC)

The algorithm for bytewise xoring (the common software implementation) seems to have some errors: the coefficient to be checked should be x^n, and the multiplication by x should be done after xoring with the generator polynomial if the tested bit is a 1 (tried examples by hand). Currently, the example seems to ignore the first bit of each byte. Anyone else concur? 128.252.37.8 22:20, 31 July 2007 (UTC)

The algorithm (2nd box) is correct as I understand it. The changes would not break it, but would make it harder to implement. The current shift register lies in bits 0 to n-1, whereas in your case it would lie from bit 1 (as multiplication by x is the last step, so bit 0 = 0) to n (where the top bit is tested.) This would overflow machine registers of size n. -- Regregex (talk) 13:53, 23 January 2008 (UTC)

[edit] Unfamiliar

I am not familiar with the algorithm, and so make the following suggestion as a novice. The use of the multiplication of the remainder term by 'x' as in the following line:

remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x0

is not clear (at least to me). The variable 'x' was not defined, and if multiplication is simply bit shifting, it would be helpful to put in a couple of lines mentioning why. Per Bj. Bro (talk) 19:33, 3 February 2008 (UTC)

The first algorithm is a transition between the mathematics of polynomial division and computerised shift register implementations. Here it shows how to manipulate the polynomials in an algorithmic way, using a contrived composite data type for polynomials (which could be mentioned in the text for clarity). So the multiplication by x0 is symbolic (since x0 = 1) to show we are adding a new term to the polynomial.
As to x not being known, that's the whole point. Otherwise the polynomial expressions collapse to a single integer, additions carry and subtractions borrow, which we don't want as exclusive OR is simpler.
Section Bit ordering (Endianness) uses left- and right-shifts in the algorithms. The link between multiplication and bit shifts does deserve an explanation though. -- Regregex (talk) 16:25, 6 February 2008 (UTC)