Talk:Cyclic redundancy check
![]() | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
Initial Value
[edit]It would be nice if the official IV, if any, was listed for each of these polynomials. I think most just start with all-1s, but there may be exceptions. 75.145.68.90 (talk) 00:05, 25 May 2018 (UTC)
Merger Discussion
[edit]Merge
These articles overlap with the contents of this article, some information is duplicated some elements are better presented in the linked articles. — Preceding unsigned comment added by 142.58.211.180 (talk) 23:15, 22 March 2016 (UTC)
- Agreed, dividing the pages only adds confusion, at the very least the mathematics and computation articles should be merged, and the resulting article added as a reference to the main CRC article.68.36.129.21 (talk) 07:13, 4 January 2017 (UTC)
- Merge: The Mathematics and Computation sections already make up most of this article's text. Also: I notice that the other two articles were never tagged with {{merge to}} templates; that may be why there has been little discussion here. I have added the tags. —Theodore Kloba (☎) 16:03, 20 October 2017 (UTC)
- Oppose merge: my feeling is that the distinct mathematics and computation pages are highly technical, and the current structure of a summary on the Cyclic redundancy check page links appropriately with a template:main (as it currently is) is a good structure that is better not tampered with. Klbrain (talk) 14:23, 21 March 2018 (UTC)
- Oppose merge: I agree with Klbrain. The reference information specific to CRC here is a lot of the article. 75.145.68.90 (talk) 00:05, 25 May 2018 (UTC)
SSE4
[edit]The page for SSE4 describes another CRC32 poly: 0x1EDC6F41. I would guess that means it is in common use and should be added to the table? Does it have a name? Spitzak (talk) 00:03, 19 February 2009 (UTC)
- This is the Castagnoli CRC [polynomial] used in iSCSI, and is already listed. — Regregex (talk) 21:29, 19 February 2009 (UTC)
- [...]and SCTP; This polynomial offers an improved Hamming distance which retains protection for Jumbo Frames not provided by the IEEE CRC. See RFC3385 for details. Intel now offers 1 Gb/s and 10 Gb/s Ethernet adapters that off-load SCTP. In addition, Ethernet CRC protection goes from NIC to NIC, whereas SCTP provides protection end-to-end. The checksum used in TCP and UDP fails to detect bus driver related bit specific errors as often as 2% of the events, due to these errors tendency to self cancel with checksums. —Preceding unsigned comment added by 64.142.13.68 (talk • contribs) 00:49, 17 August 2009
External links.
[edit]There's been some back-and-forth recently about how extensive the external links ought to be. I was thinking we could discuss it here rather than, say, edit-warring. I would start by suggesting that there are a large number of relevant links out there because CRCs are ubiquitous. It costs us little to link to them, but it costs readers more when they are unable to find what they're looking for here and have to resort to Googling. What do you think? 208.80.104.2 (talk) 22:31, 14 September 2009 (UTC)
- Dear IP,
- in great User:Oli Filth was right deleting the links, the page was/is missused as a linkfarm and product showcase. Especially the latter is unencyclopedic, read WP:NOT for a deeper understanding of Wikipedia's goals. We could of course talk about single links, which could be worth keeping.
- your announcement to start an edit war if someone re-deletes the links is - soft spoken - somewhat strange. There was no "back-and-forth recently about how extensive the external links ought to be". Oli decided to cut unnecessary links and you reverted him. Why didn't you discuss first and then see if a revert is acceptable?
- Summa: if you do not come up with better arguments for keeping those links, I'll revert your revert. Greetings --Kgfleischmann (talk) 08:09, 16 September 2009 (UTC)
- I deleted :
- Advertising (missusing the article for adv. for disk utilities and other types of vandalism)
- Most of the code examples, if notability is proven some may come back
- Dead links.
- Greetings --Kgfleischmann (talk) 18:53, 21 September 2009 (UTC)
- Thank you for your edits, for a major subject I'm surprised how little edit traffic this page gets, and so it tends to get cluttered. – Regregex (talk) 18:04, 28 September 2009 (UTC)
- --Kgfleischmann: It would be nice if there were some simple CRC32 source code in C or C++ <seems the links were removed>. I understand the BOOST libraries but they are very messy and confusing - seems a bad choice for example source code. - FourtySix&Two (talk) 19:29, 29 December 2009 (UTC)
Page too wide
[edit]I think the table should be made slimmer, as it is not very nice to have a wikipage with a scrollbar in the bottom of the screen (unlike [most?] other wikipages). Just my two dimes.
// Ilyushin
- Agree It's probably non-breaking spaces in the <math> elements; any suggestions? – Regregex (talk) 17:45, 28 September 2009 (UTC)
Merge Mathematics of CRC and Designing CRC polynomials
[edit]Please consider merging the two sections Mathematics of CRC and Designing CRC polynomials. The first one really gives no information, even not introductory. The second one could be improved by explaining the benefits of choosing irreducible or primitive polynomials over reducible ones. Last but not least, please consider generalizing the text to fields that are not of order 2 (this also applies to Mathematics of CRC)—even when in practice CRCs are based on the GF(2). Nageh (talk) 13:47, 25 January 2010 (UTC)
Oh, I just saw that there is some rationale for the use of primitive polynomials. However, it is not clear what is meant by blocklength: Is it the input length, or the CRC output length? If it refers to the latter, it probably means the size of the set of possible output tags. This needs to be clarified. Edit: Ok, that was a stupid question, as of course modular division can reveal all possible output lengths, so blocklength refers to the input length. Still, this should be clarified, as it is not obvious from terms like "maximal total blocklength". Nageh (talk) 12:39, 26 January 2010 (UTC)
This topic is in need of attention from an expert on the subject. The section or sections that need attention may be noted in a message below. |
- I'd already merged the sections before seeing this message, but the above is pretty much why I applied the {{Expert-subject}} template. In particular the following issues need attention:
- The first paragraph, which is abysmal (Nageh); the quality of the rest could also be better;
- Clarify the advantage of a 'maximal total block length' (Nageh);
- Check that 'irreducible' and 'primitive' have not been mixed up;
- Adjustment of Designing CRC polynomials to reflect the state of the art, such as the additional classes of polynomial found by Koopman [1] and the "propriety" property discussed by Thaler [2]
- More citations are needed.
- I also have a feeling of the section lacking something. Thanks for any assistance.
- Nageh, I have found a GF(32) Reed-Solomon code here (section A.2.1.4, p.34), which I think also constitutes a CRC. HTH. -- Regregex (talk) 14:38, 28 August 2010 (UTC)
- Thanks. Your recent reorganization was a good step forward. Regarding CRC vs. RS, both are cyclic codes, so for both codewords can be created using a generator polynomial, and syndrome checking by polynomial division. But, CRCs are single-burst error-detecting codes, while RS codes are MDS codes and random-error correcting over non-binary symbols. Because of non-binary symbol sizes for RS, they also constitute multi-burst error-detecting/correcting codes. You may compare RS with non-binary CRCs: in that case the generator polynomials would have different characteristics. Nageh (talk) 15:18, 28 August 2010 (UTC)
- Also, Reed-Solomon codes are intended for input blocks of fixed length (such as individual sectors on a CD), whereas CRC's are intended for stream data of arbitrary length. Selinger (talk) 15:54, 28 September 2010 (UTC)
Correct wording?
[edit]Not my area but the phrase "the number of the highest nonzero coefficient" makes no sense to me. Could it have meant "the highest exponent with nonzero coefficient" ?--Billymac00 (talk) 04:15, 10 March 2010 (UTC)
Any clues on history?
[edit]I've tried searching for it but cannot locate any sources that describe the development of CRC from a historical context. I'd like to know things like who first developed or deployed the generic CRC algorithm and how various implementors came to modify and define their own standards. If anyone knows of usable sources please advise. Ham Pastrami (talk) 10:38, 26 March 2010 (UTC)
- Wesley Peterson developed and studied the concept of CRCs, first published in 1961 (this is in the article!), and based on the theory of cyclic codes over polynomial rings. Cyclic codes were first studied by Prange in 1957. The rationale for using different CRC generator polynomials comes from the different requirements in terms of burst vs. random error detection. Additional hacks, like inverting input or outcome, intend to detect asymmetric errors, e.g., resulting in all-zero-bit messages. HTH for a start. Nageh (talk) 15:11, 26 March 2010 (UTC)
- If you mean as computer algorithms, Ross Williams's Usenet article in the 1980s (in the references) systematized descriptions and byte at a time lookup table implementations – which fall out from the math. Bit by bit algorithms probably simulate the tapped shift register hardware implementations – described in the refs of that era. In the archived talk page my comment notes that closed form CRC-16 table based implementations were used in the assembler MS-DOS Kermit and HP-150 ROMs - so ~1983. RDBrown (talk) 15:36, 26 March 2010 (UTC)
- Thanks for the replies. Please note that I am not asking for evidence of the first CRC, I am asking for a source that verifies the evidence as being the earliest example (e.g. the 1961 paper being the first). Right now the claim in the article, while perfectly believable, is a product of synthesis, namely: "this paper published in 1961 is the first documentation of CRC because nothing was published earlier". I am looking for a reliable source that confirms that. The same applies to the messages posted to Usenet, etc. Ham Pastrami (talk) 01:07, 27 March 2010 (UTC)
- Try the references in A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS from the CRC Pitstop refs link - Ross Williams' paper from his site (1993). The earliest refs he'd heard of (but hadn't seen) are
- Boudreau, Steen (1971). "Cyclic Redundancy Checking by Program". AFIPS Proceedings. 39. doi:10.1145/1479064.1479067.
- Higginson PL, Kirstein PT (February 1973). "On the Computation of Cyclic Redundancy Checks by Program". The Computer Journal. 16 (1): 19–22. doi:10.1093/comjnl/16.1.19.
- Marton, Frambs (1971). "A Cyclic Redundancy Checking (CRC) Algorithm". Honeywell Computer Journal. 5 (3).
- Wecker, S (1974). "A Table-Lookup Algorithm for Software Computation of Cyclic Redundancy Check (CRC)". Digital Equipment Corporation memorandum.
- A quick look at Google scholar found refs to these mostly in Ross's paper, but Google books and Worldcat may do better — Since hardware implementations are also significant to this, looking at bitsavers would be worthwhile if you wish to seriously research this RDBrown (talk) 02:00, 27 March 2010 (UTC)
- This is from Peterson, W.W.; Weldon, E.J. (1972). Error-correcting codes (2 ed.). MIT Press. ISBN 978-0262160391.:
- The first cyclic burst-error-correcting code found was Abramson's single-error, double-adjacent error-correcting code (1959), which initiated the further development of single-burst-correcting cyclic codes, which was led by Fire (1959), Melas (1960), Reiger (1960), Kasami (1962), Elspas and Short (1962), Melas and Gorog (1963), and Burton (1969). Methods for correcting bursts up to a predefined length is due to Peterson (1961) while pointing out that is basically a refinement of Abramson's (1961) and Meggitt's (1960) methods. Stone (1963) developed a multi-burst-correcting code, which is closely related to Reed-Solomon codes.
- Nageh (talk) 06:12, 27 March 2010 (UTC)
Demonstrated CRC
[edit]I did it out by hand and using a program I wrote. I'm not positive, but I think it comes out to 101 not 111. —Preceding unsigned comment added by 128.113.196.22 (talk) 05:35, 18 October 2010 (UTC)
- You're quite right, I believe the result is 101. Here is my working just to check:
11010011101100 1011 ↓↓↓ ↓↓ XOR ----- 01100 1011 ----- 01110 1011 ----- 01011 1011 -------- 00001101 1011 ----- 01101 1011 ----- 01100 1011 ----- 01110 1011 ---- 00000000000101
- I shall update the page accordingly. – Regregex (talk) 22:30, 18 October 2010 (UTC)
I had the same question -- and it appears the example still (2013) has not been updated. Is user "regregex" still around or can someone else fix the example so it completes the shift-divide sequence? The last two are "no op" since the lead digit is zero, but it'd be nice to show. Cellocgw (talk) 11:08, 8 April 2013 (UTC)
- I did update it the same day but Camitz (talk) pointed out in this later edit that the division shown above does not include the zero padding or augmentation carried out by almost all implementations, and so the correct result is now 100. IMHO I doubt that inserting the null steps would add clarity to the calculation. re/greg/ex;{mbox|history} 03:41, 9 April 2013 (UTC)
Thanks for the comment. I'm fine with that point of view Cellocgw (talk) 11:27, 18 April 2013 (UTC)
- Yes, current example is wrong
- b11010011101100 000 / b1011 = b10011001111 101, totally not b01100011101100 000 46.98.99.93 (talk) 16:59, 11 May 2023 (UTC)
In over my head
[edit]Till editing this article, I had no idea "CRC" had any cryptological significance. It's an encoding system but since everyone must agree on the exact method used, it offers no protection from interception or spoofing by Carol. I thought CRCs were only useful in fighting channel noise. So, I don't think the "insecurity" of a CRC function is something to dwell on in the lead since no-one expects it to provide security in the first place. --Wtshymanski (talk) 14:07, 10 November 2010 (UTC)
- The problem is that people think they can use it for purposes that actually demand cryptographically secure functions. What means for a function to be secure depends on the context. If you want good protection against random channel errors a cryptographic hash function is actually more "secure" than a CRC. But neither CRCs nor unkeyed hash functions can protect against malicious modification of data. So yes, CRCs are only useful for fighting channel noise, and saying that it is a "insecure" function in the lead would be quite misleading in this regard. Nageh (talk) 14:42, 10 November 2010 (UTC)
- Fair enough. – Regregex (talk) 20:23, 10 November 2010 (UTC)
- Cryptographic hashes are not more secure against random noise than CRCs, because they do not guarantee a minimum distance between code words for adjacent data words. The best known 32-bit CRC codes are proven to detect up to five individual bit errors and bursts of up to 32 bits in code words of up to 5,275 bits (Castagnoli, 1993). DES (talk) 06:39, 15 February 2011 (UTC)
Representations: normal / reversed / reverse of reciprocal ?
[edit]I'm sorry, but I'm kind of lost with these terms. Why couldn't we say for example that for the value : we could use the representation 0x13 (0010 0011) instead of those cryptic 0x3 / 0xC / 0x9 ?
Or at least explain what is the meaning of those values. —Preceding unsigned comment added by Glatapoui (talk • contribs) 10:11, 23 November 2010 (UTC)
- I've added a paragraph to the section Specification of CRC in the article to explain the triplets. The high-order bit is left off for reasons explained in that section; there's a hatnote on the table as a reminder. HTH. – Regregex (talk) 17:04, 23 November 2010 (UTC)
Mislabeled table. The reciprocal and reverse definitions are the same! The heading "reversed reciprocal" is actually Koopman which is taking the full polynomial then right shift, dropping the LSb as evident in the linked example. — Preceding unsigned comment added by 23.233.29.183 (talk) 05:51, 10 April 2017 (UTC)
Lede
[edit]The lede is not only poorly worded and at times ungrammatical, but also contains numerous factual errors:
- "CRC" should not be used as a noun; the proper term is "CRC code". This error pervades the entire article, not just the lede.
- I have never seen the term "polynomial code checksum" used outside of this article. CRC codes are both polynomial and cyclic but are far from the only codes in either category.
- A CRC code is not a hash or a checksum, but a code: a transformation of a data word (the information you want to transmit) into a code word (the bit stream that gets sent over the wire). It is designed so that data words that are close together (i.e. with a short Hamming distance) are transformed into code words that aren't. The basic principle is fairly well explained in the Hamming code article, although CRC codes are not Hamming codes.
- The additional bits generated by the CRC algorithm (technically, the low-order bits in the code word) are properly called check bits or check digits. While it may be common to refer to them as "the CRC code" or "the CRC checksum" or "the CRC" in informal discussion, these terms are incorrect. This confusion probably arises because the high-order bits in the code word are identical to the bits in the data word, so people tend to forget (or not understand) that the code word is an indivisible whole.
The lede was most likely written by editors who do not understand CRC codes and consider them some sort of black magic. In fact, the entire algorithm can be summarized in a few sentences:
- You need to reliably transmit a string of k symbols chosen from an alphabet of q symbols.
- Consider that string as a k-digit number in base q.
- Choose a number r, which is the order (or "width") of your code, and a number g such that qr < g < qr+1.
- Multiply the data word by qr. This is equivalent to appending r zeroes.
- Round the product up to the nearest multiple of g.
- The result is a n-digit code word, where n = k + r.
- To verify that the code word has not been corrupted in transit, the recipient divides it by g. The result should be zero.
Of course, the devil is in the details, i.e. the selection of r (the order) and g (the generator).
The only element of black magic is that all operations (addition, multiplication etc.) are done in modular arithmetic. In simple terms, this means that you never carry when adding; digits just wrap around. However, you don't need to know (or understand) this unless you intend to implement the full algorithm instead of using precomputed tables, or unless you're trying to understand the proofs in Peterson's paper. Likewise, the fact that Peterson considers the data word, code word and generator as polynomials rather than numbers is of no importance unless you're trying to understand his proofs.
DES (talk) 18:27, 14 February 2011 (UTC)
- Go for it! WP:BOLD and all that. --Wtshymanski (talk) 19:07, 14 February 2011 (UTC)
- In my copious free time (there should really be a Wikipedia article for that, and for round tuits). Anyway, I didn't want to embark on a major rewrite without discussing it here first. DES (talk) 09:00, 15 February 2011 (UTC)
- Mostly agree, and I encourage you to rewrite the Lead as well as other sections (e.g., "Computation of CRC"). At the same time a little bit more background on the mathematics behind it (selection of a polynomial ring, suitable generator polynomial, etc.) is desirable, too. (There is generally lot to improve in the article.) And just a minor note: A CRC code is a hash function by definition, i.e., a mapping of variable-length strings to fixed-length tags. It's probably a bit unfortunate to call it like that but it is not wrong. Nageh (talk) 22:35, 14 February 2011 (UTC)
- No, it is a mapping of a k-bit string to a k+r-bit string. If you read the original paper, the check bits were never intended to be considered separately from the data bits. Storing or transmitting them separately or in a different encoding may weaken the code. DES (talk) 07:04, 15 February 2011 (UTC)
- You are technically right. Still, you may use any systematic error-detecting code as a hash function. As I said it's probably a bit unfortunate to call it like that... maybe folks have a better picture when they think of a hash function? Nageh (talk) 09:09, 15 February 2011 (UTC)
- I believe that the purpose of Wikipedia is to be strictly correct, so Wikipedia articles should avoid using a term incorrectly, even if such usage is common, and they should mention that this common usage is incorrect. The following quote from the lede of the hash function article is an excellent example:
“Hash functions are related to (and often confused with) checksums, check digits, fingerprints, randomization functions, error correcting codes, and cryptographic hash functions. Although these concepts overlap to some extent, each has its own uses and requirements and is designed and optimised differently.”
- I think we're in violent agreement over this, but I just wanted to spell it out clearly.
- DES (talk) 11:50, 15 February 2011 (UTC)
- That's fine for me. Just wanna remark that the quoted statement in hash function is not entirely correct. At least checksum (functions) and cryptographic hash functions are subsets of the general class of hash functions. Moreover, that article is overly confusing in that it mixes functions with function outputs. And the last sentence in that paragraph is totally wrong since the tag of a cryptographic hash function is a digital fingerprint by definition as well as a hash (value) by definition of a hash function. Nageh (talk) 12:24, 15 February 2011 (UTC)
- I agree with you on a lot of points, but I don't think polynomials can be done away with completely: they're all over the literature, the ITU-T Recommendations in particular define their CRC codes algebraically. If there is a pure modular-arithmetic treatment of CRCs in publication then it certainly merits inclusion, otherwise writing a new one may be OR. But for Wikipedia to eliminate the polynomial treatment in its favour would be gauche or even a case of dumbing down. Here's another Foldoc entry: You are not expected to understand this
- Whatever the rights and wrongs of the term 'hash function', the article should at least admit that CRCs are used as hash functions (albeit sometimes with sparse polynomials making them dismally weak). Regregex (talk) 12:11, 15 February 2011 (UTC)
- Modular arithmetic does not generalise to polynomials over larger fields e.g. GF(32). Polynomials may be reducible, primitive or neither; integers can only be prime or composite. Regregex (talk) 13:07, 15 February 2011 (UTC)
- Firstly, I skipped polynomials in my description because you don't need them to understand or implement the algorithm; only to understand why CRC codes work and how generator polynomials are selected. That doesn't mean the article shouldn't mention them, just that a quick "how CRC codes work in seven bullet points" shouldn't.
- Secondly, your edits improved the lede in some areas but introduced a new error: the use of "CRC code" in the sense of "check digits". To simplify: the term "CRC code" is appropriate when the sentence would still be meaningful (albeit incorrect or inexact) if you wrote "hash function" instead, and the term "check digits" is appropriate when the sentence would still be meaningful (albeit incorrect or inexact) if you wrote "hash key" instead. The "code" in "CRC code" is exactly the same as in "Morse code" or "Caesar code", not as in "EAN code".
- Thirdly, I think the Computation of CRC and Mathematics of CRC sections should switch places, and the latter should be rewritten to actually describe the mathematics of CRC, not just polynomial selection. I'm willing to give it a shot, but it's a lot of work...
- DES (talk) 13:41, 15 February 2011 (UTC)
@Regregex: Just looking at your recent edits. I'm wondering where the statement that the output is sometimes (erroneously) called a "CRC code" comes from. In fact, CRC code is the more explicit naming for the function, whereas CRC may refer to both the function (i.e., the code) and the value (as it had been in the article before). Nageh (talk) 19:40, 16 February 2011 (UTC)
BTW, I also doubt that the output may be referred to as a "check character". A "character" refers to the basic symbols over which a code operates, which in the case of standard CRCs refers to bits. Referring to the result as a "check value" would be correct. Nageh (talk) 19:44, 16 February 2011 (UTC)
- Actually, all the terms that have been bandied about so far are unreferenced. I shall survey all the sources in my catalogue and see what they call it as DES has blown apart the terminology I took for granted (rightly, as far as WP editing goes.) Whatever I find will be inserted with references. Regregex (talk) 18:35, 18 February 2011 (UTC)
To name the 'check bits':
RFC 3095 uses "CRC" (and for the function and the code).
RFC 4880 uses "checksum"
RFC 1171 and V.42 use "frame check sequence"
EN 300 175-3 uses "check bits", "checksum", "error control bits", "redundancy bits", "CRC bits" and "CRC field".
EN 300 751 uses "CRC", "CRC bits", "CRC word" and "checksum".
EPC C1G2 uses "CRC code" and "CRC".
JESD84-A441 uses "CRC", "CRC bits" and "CRC checksum".
The Modbus Protocol Reference Guide uses "error check value", "CRC field" and "CRC check field".
Ecma-182 uses "CRC character" and "check character".
Block check character (BCC) does appear, e.g. [3] [4] [5] and ISO/IEC 1155:1978 according to [6], but not nearly as often as I thought and usually referring to a longitudinal parity check.
Regregex (talk) 21:06, 18 February 2011 (UTC)
I think you were not understanding me correctly. I was pointing out that the terminology "CRC code" for the output of a CRC function was incorrect, and was doubting that BCC was appropriate terminology.
Let me clarify. The function may be referred to as a "CRC", a "CRC code", or a "CRC function". The output may equally be called a "CRC", just as we had it in the article previously. Other names you are putting up are standard terminology in coding theory... I'm not sure we need to specifically point out or cite them (check bits, parity bits, error control bits, bits<->value, etc.).
Regarding your recently introduced term "block check character" (BCC): Based on your research, only TIA mentions a CRC when using this term, and it describes a BCC as a character (singular!) added to a message, so for a CRC we have multiple BCCs added to a message.
In conclusion, we should restore the text we had before. If our coverage of coding theory were only a bit better, I would suggest something like "A CRC-enabled device calculates a short, fixed-length sequence of parity bits, usually simply referred to as CRC, for each block of data...", such that a reader can look up the general meaning of "parity bit" (or check bit) rather than the specific, which the article describes, only.
Well, anyway, thanks for your research. Nageh (talk) 21:15, 18 February 2011 (UTC)
- Well, I have changed all references to the output-of-a-CRC-function to 'check value', as you suggested above. If you'd prefer an earlier version of this text, a revert is available via the page history. I am not going to stress myself any more with the particular terminology to be used or with this thread. Regregex (talk) 21:40, 18 February 2011 (UTC)
- Don't get me wrong, I appreciate your efforts. Thanks!!! Nageh (talk) 21:46, 18 February 2011 (UTC)
Regregex, interesting that you checked pretty much everything except the actual scientific literature about CRC codes referenced by the article, such as Peterson, Castagnoli or Koopman. Peterson uses “check digits”, but is is clear from context that these digits are actually bits (“We will be concerned with coding a message of k binary digits by appending n-k binary digits as a check and transmitting the k information digits and then the n-k check digits.”). Koopman uses “CRC bits”, but it is unclear whether he's referring to the check digits or to the polynomial. Castagnoli uses “parity bits” even though that is technically incorrect. Holzmann (Design and Validation of Computer Protocols, Prentice Hall 1990, not referenced in this article but one of my favorites for its clarity and simplicity) uses “check bits”. DES (talk) 11:04, 19 February 2011 (UTC)
Too complicated for wikipedia level
[edit]This article was mixed with math and it is too complicated. The animated gifs are too speedy to follow. Much interest was granted to text and explanation but the example is very poor and it is not ilustrated. —Preceding unsigned comment added by 212.77.163.101 (talk) 12:51, 4 March 2011 (UTC)
utility
[edit]there should be a link to a utility to calculate crc32 hash of files — Preceding unsigned comment added by 82.139.86.184 (talk) 13:48, 5 June 2011 (UTC)
Possible typo in the CRC32C polynomial
[edit]I think there may be a typo in the CRC32C polynomial in the table, I think one of the columns disagrees with one of the other columns, but my polynomial math is too rusty to be sure, so I have not edited it. Would someone more experienced please check and update the article if necessary? 90.184.113.110 (talk) 15:37, 7 May 2012 (UTC)
- I don't see any error. The first hex representation is as it appears in RFC 3720 (less the leading 1 as described above the table) and the Koopman notation is as printed in the citation. I've just checked that the algebraic form corresponds to the hex constant in the RFC. re/greg/ex;{mbox|history} 17:05, 8 May 2012 (UTC)
fixed-width text alignment not preserved in PediaPress book
[edit]I printed this article with others in a PediaPress paper book on 7th December. Although no edits have been made to the example in Computation of CRC, and although the alignment is correct in the wiki source, the printed book has an alignment problem where rows appear shifted left or right by one or more characters.
It makes the example needlessly difficult to follow, as you'd expect, but I have no idea why the printed version doesn't preserve the alignment.
Ecashin (talk) 03:25, 24 December 2012 (UTC)
Missing CRCs
[edit]THIS table is currently missing CRC13 [7] used by the BBC Longwave transmitter on 198khz. [8] [9] Eyreland (talk) 03:35, 27 September 2013 (UTC)
Actual Meaning of CRC
[edit]This article is not necessarily true. All CRCs are not calculated values (let alone polynomials). For example, some old file systems has CRCs that were simply known values that served as simple checks that the disk was being correctly read. Common values were 0xA5 and 0x55 (looking at the bit patterns will tell you why). CRCs are simply known, repeatable values. How/if they are calculated is irrelevant. — Preceding unsigned comment added by 74.67.119.190 (talk) 14:32, 15 August 2014 (UTC)
- Is there a source that describes this type and usage of CRC? ~KvnG 13:36, 3 September 2014 (UTC)
- None I can think of that Wikipedia would accept as a source, but one that comes to mind are the various disk formats used on old microcomputers, such as the TRS-80. The format used for TRS-80 floppy disks had two constants values, called CRCs, that could have checked for consistency. I don't remember if they were per track, sector, et. al. FAT does something similar, but I don't think MS called them CRCs. — Preceding unsigned comment added by 74.67.119.190 (talk) 15:08, 2 November 2014 (UTC)
- All Cyclic Redundancy Checks *are* calculated values using polynomials. Your statement accusing this article of not being necessarily true is "All CRCs are not calculated values (let alone polynomials)." However, the article is titled "Cyclic redundancy check", not "CRC". The TLA "CRC" has many uses as can be seen in the disambiguation page CRC; perhaps what you are referring to is yet another thing called a "CRC". Vincent J. Lipsio (talk) 18:56, 2 November 2014 (UTC)
- This seems to indicate that the TRS-80 used calculated CRC values. ~KvnG 15:26, 7 November 2014 (UTC)
Links to sections that no longer exist
[edit]In an effort to do some copyediting of this article, I found that all of the links targeting sections within the article point to sections that no longer exist. Specifically, these links:
[[#Computation of CRC|Computation]] [[#Specification of CRC|integer encodings]] [[#Commonly used and standardized CRCs|table]]
The link to #Computation of CRC now obviously points to its own article, Computation of cyclic redundancy checks, so I explicitly edited this. However, the other links may need to be looked at by someone with expertise in this area, to establish exactly where they are meant to link to. - Alistairirvine (talk) 21:17, 27 August 2014 (UTC)
Done ~KvnG 14:43, 3 September 2014 (UTC)
Missing information
[edit]The article does not even mention Fletcher's checksum and Adler-32.Sure, those are not CRCs, but it is important to understand the relation and the differences. Please add information about that to the article. --rtc (talk) 20:14, 17 June 2017 (UTC)
The most widely used crc64 in the wild seems to be the "Jones" variant, introduced in this paper: http://www0.cs.ucl.ac.uk/staff/D.Jones/crcnote.pdf
And described/analyzed here:
https://matt.sh/redis-crcspeed — Preceding unsigned comment added by 172.58.140.154 (talk) 03:15, 5 February 2018 (UTC)
bad math
[edit]"and will detect a fraction 1/(1 − 2^−n) of all longer error bursts." -- This cannot be correct. For example, with a 3 bit crc, 2^-3 = 1/8. 1/(1-1/8) == 8/7. How do you detect 8/7 of all longer bursts? This value should never be greater than 1. 24.180.6.18 (talk) 16:45, 4 August 2017 (UTC)
Done – I see that this was corrected not long after this was posted. —Quondum 21:21, 18 August 2018 (UTC)
External links modified
[edit]Hello fellow Wikipedians,
I have just modified 2 external links on Cyclic redundancy check. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
- Added archive https://web.archive.org/web/20110719042902/http://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf to http://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf
- Added archive https://web.archive.org/web/20130822124728/http://www.bosch-semiconductors.de/media/pdf_1/canliteratur/can_fd_spec.pdf to http://www.bosch-semiconductors.de/media/pdf_1/canliteratur/can_fd_spec.pdf
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}}
(last update: 5 June 2024).
- If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
- If you found an error with any archives or the URLs themselves, you can fix them with this tool.
Cheers.—InternetArchiveBot (Report bug) 23:14, 15 August 2017 (UTC)
Python code not working with 1 padding
[edit]I tested the attached python code in the "CRC-32 algorithm" section and it seems only working with 0-padding.
When I test it with 1-padding, it returns False.
I´m not an expert on the topic, so I could easily be mistaken, but I think this deserves a check by an expert.
Cheers MachWaveRider (talk) 08:14, 8 July 2019 (UTC)
- Please give an example of input which generates a result you think is wrong, preferably with a reason for why it is wrong. If I had a test case I might get a chance to look at it. Johnuniq (talk) 09:50, 8 July 2019 (UTC)
- Just try to run the code using the same values as in the example, but with padding = 1. The reminder function returns 011, which is correct. But when we enter these numbers into the check function, it returns False.
- I found that the checksum result with 1-padding must be inverted before being passed to the check function, in order to have a positive check.
- Maybe I am just stating the obvious and this step is just given for granted by any knowledgeable person. MachWaveRider (talk) 10:07, 8 July 2019 (UTC)
Examples
[edit]There are nice examples in many programming languages at Rosetta Code — Preceding unsigned comment added by 148.163.178.15 (talk) 20:43, 21 August 2019 (UTC)
CRC-32 Algorithm
[edit]The algorithm presented is one that hides much of the actual computation by using a lookup table. The algorithm isn't presented as a practical implementation I assume, but rather as clarification of the steps in the computation. I think it would be better if the algorithm provided here was one calculating the CRC32 one bit at a time. This would help clarify the functionality of the CRC32. Memoization is a way of optimizing the speed of an implementation, one of many, and complicates the algorithm. If the purpose of this section is to illustrate speed up techniques, then the section should be described as such and expanded. I would be happy to replace this example or add to this example with a one bit at a time algorithm. Gnuarm (talk) 15:43, 5 December 2020 (UTC)
- Don't replace, two CRC-32 algorithm examples would be better. If you add an example, it should be similar to how the other one is shown. • Sbmeirow • Talk • 20:32, 5 December 2020 (UTC)
Start a discussion about improving the Cyclic redundancy check page
Talk pages are where people discuss how to make content on Wikipedia the best that it can be. You can use this page to start a discussion with others about how to improve the "Cyclic redundancy check" page.