Talk:Computation of cyclic redundancy checks

About the animated graphical illustration

In the second animated diagram only 7 bits of the checksum are fed to the register engine. However, as far as I know, generally, all eight bits shall be fed for 8-bit CRC.

In both the first and second animated drawing, the XOR taps are not correct.

If we are thinking about this as result = [8:1]

poly = x^8 + x^2 + x + 1

tap = bit 8 XOR serial_data_in

bit 1 = tap (correctly shown)

bit 2 = tap XOR bit 1 (incorrectly shown)

bit 3 = tap XOR bit 2 (incorrectly shown)

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)

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 x⁰ is symbolic (since x⁰ = 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)

Confusion over 2nd Code Fragment

Ok at bit confused. Why isn't the 2nd code fragment's if statment like this?

remainderPolynomial := remainderPolynomial xor bitString[i]
if coefficient of xn-1 of remainderPolynomial = 1 {

I know Im missing something. >.> I get the first code fragment and the first optimization but the 2nd really has me confused. Anyone care to elaborate? If it means what I think, then why do we ever have the bitString inside of the remainderPolynomial in the first place? --71.127.111.133 (talk) 06:55, 7 June 2009 (UTC)Buttink

I have swapped the xor operands in the if clause so that it reads

         if (bitString[i] xor coefficient of xn-1 of remainderPolynomial) = 1 {

This may clear it up. If not then consider that your version would insert bitstring[i] at the bottom whereas it is meant to be xored with the topmost bit — we're avoiding pushing the bitstring through the register before it is tested, so that we don't have to push zeroes to flush it out at the end, at extra expense. — Regregex (talk) 21:16, 12 June 2009 (UTC)

Oh ok wait a sec, do we never actually do the XOR with the bit we test because our Key always will have a 1 as its highest order bit. That way we can skip over it and just XOR with the remainder. I think I get this :). Hope I actually get it to work. --71.127.111.133 (talk) 06:17, 14 June 2009 (UTC) Buttink

The xor shown above is executed on every cycle. Actually there is a problem with this fragment in that the top coefficient is not cancelled, allowing the remainder to grow very large. The bitstream should be xored in before testing, as you suggest, but at the top. I shall just fix that now.

Note that the xⁿ in fragment 1 is changed to x^n-1 in fragment 2 as the remainder is now shifted (multiplied by x) after the test, not before. — Regregex (talk) 10:40, 16 June 2009 (UTC)

JavaScript used to create the bit-wise equations

Some HTML/ECMAScript code to display tables as shown in computation of CRC can be found on K5002 talk.

K5002 (talk) 21:08, 30 July 2009 (UTC)

Fast computation using carryless multiplication

A fast parallel CRC algorithm has been published by David Feldmeier (David C. Feldmeier, Fast Software Implementation of Error Detection Codes. IEEE TRANSACTIONS ON NETWORKING, VOL. 3, NO. 6, DECEMBER 1995). This algorithm can be efficiently implemented by using the carryless multiplication. The algorithm could be added to the article under parallel computations.Lauri.pirttiaho (talk) 11:25, 5 February 2011 (UTC)

Thanks for the reference, looks promising. I'd add it myself if I had $30 for the paywall: Ten.eleven oh nine, end of the line. – Regregex (talk) 13:07, 7 February 2011 (UTC)

7.2 Post-invert -- statement correction justification

The statement "To be precise, the result is the non-inverted CRC of the inversion pattern." appears incorrect.

Background: my test using CRC-32, lsb-first table-driven algorithm, on message: buf[13] = "123456789":

1. Generate message (length = 9) CRC using -1 preset and post-invert (with 0xffffffff), result = 0xcbf43926 (message-specific). Append this, least-significant byte first, to message (i.e. starting at buf[9]).

2. To check the "transmitted" message, generate buf (length = 13) CRC using -1 preset and post-invert, result = 0x2144df1c (constant for any message with appended CRC-32 as just described).

This is enough to verify any complete message transmission, as section 7.2 states.

An alternative to step 2 would be to skip the post-invert when checking the "transmitted" message, since it simply complements the result. The alternative result would therefore be 0xdebb20e3 (constant).

Now for the statement in question. There are two reasonable interpretations for "non-inverted CRC of the inversion pattern":

(a) CRC of { 0xff, 0xff, 0xff, 0xff }, with no -1 preset (rem = 0) and no post-invert, which yields 0xdebb20e3, or

(b) CRC of { 0xff, 0xff, 0xff, 0xff }, with -1 preset and no post-invert, which yields 0.

It's obvious that case (a) is the correct interpretation, since it is the only non-zero result. But the value *doesn't* match the result for my original step 2 above. However, it *does* match the result for my alternative step 2.

Thus, either the existing statement assumes that no post-invert is done on a one-pass check, or the statement is incorrect. The unstated assumption seems a stretch, and would be kludgy because the CRC function would differ for generation and checking. So here's my suggested wording for a new statement:

"To be precise, the result is the CRC (without -1 preset, but with post-invert) of the inversion pattern."

I tested this with the common 0xffffffff inversion pattern, yielding 0x2144df1c, as well as an arbitrary pattern of 0xff3f8850, yielding 0xaec8087b. In each case, the result matched the constant result produced using the CRC algorithm (with -1 preset and post-invert) on the "transmitted" message.

Blott5822 (talk) 08:50, 31 October 2014 (UTC)

CRC Calculation Parameter Table

A comprehensive table showing the calculation parameters for each CRC type would be a great addition to this article. I have not been able to find a reference that clearly displays the differences between CRCs of the same bit size.

Some key parameters are: Polynomial, Initial Bit Reflection (Y/N), Output Bit Reflection (Y/N), XOR-Input Value (in hex), XOR-Output Value (hex), and the return CRC for the ASCII string "123456789" as a check. — Preceding unsigned comment added by Cwagner16 (talk • contribs) 15:14, 7 October 2016 (UTC)

Problems in Code Fragment 3

It seems that the line:

remainderPolynomial := remainderPolynomial xor polynomialForm(string[i]) * xn−8

is erroneous. First, in the previous code fragments it is written bitstring[i], not string[i]. Second, and more important, although AFAIU it should load 8 new bits, it loads only one. In any case, I don't understand how after loading one new bit, there are 8 conditional generatorPolynomial xoring. That just doesn't seem right. — Preceding unsigned comment added by 192.114.182.2 (talk) 13:34, 25 January 2018 (UTC)

(Very late, but for anyone else) The entire point is that code fragment 3 is not loading one new bit, but rather 8 new bits. The variable string[] is a string of 8-bit bytes (which is why it's not called bitstring!), and the polynomialForm() function converts those 8 bits to a polynomial with 8 coefficients. 97.102.205.224 (talk) 13:43, 24 September 2024 (UTC)