tag:blogger.com,1999:blog-53628746888483164362017-03-11T08:56:37.186-08:00Checksum and CRC CentralCyclic Redundancy Codes, Checksums, and related issues for computer system data integrity.Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-5362874688848316436.post-75263718099655384802017-03-11T08:56:00.002-08:002017-03-11T08:56:37.195-08:00Video on Hamming Codes & Hamming DistanceNice video that talks about Hamming Codes and gives a hypercube explanation that helps understand Hamming Distance<br /><br />Perfect Codes:<br /><br /><a href="https://youtu.be/WPoQfKQlOjg">https://youtu.be/WPoQfKQlOjg</a><br />on computerphile.Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-6943153477744449122017-01-22T11:53:00.001-08:002017-01-22T11:55:54.915-08:00On sabbaticalI noticed that my e-mail has some CRC queries. I'm on sabbatical through summer 2017, so there might be significant delays before I'm able to respond to e-mails. If you notice something that seems to be a problem please do let me know, but please bear with me until I have time to respond.<br /><br />(Contrary to what some might thinks "sabbatical" is usually the opposite of "vacation" for engineering faculty. It is a chance for us to concentrate on a large difficult problem that we can't do during normal semesters because of all the many demands made upon our time.)<br /><br />Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-78304431725603404362015-07-28T05:23:00.002-07:002015-07-28T05:25:50.656-07:00Significantly updated CRC dataOver the course of the summer I was able to get a little time to revise and update my CRC data web site. It is still work-in-progress, but you'll find a lot more data than was there previously.<br /><br />New summary tables: <a href="http://users.ece.cmu.edu/~koopman/crc/">http://users.ece.cmu.edu/~koopman/crc/</a><br /><br />Recommendations for "good" polynomials with various HD values are completed through 25 bit CRCs, and I'll let the scripts compute away for a few months until eventually the tables are completed through 32 bits. Past 32 bits my search algorithm starts taking a long time to execute so probably will only have samples above that, but we'll see how it goes.<br /><br />When you look at the data, yellow and blank mean things I'm working on (the color coding helps me keep straight what the scripts are currently working on). Green boxes and "under construction" mean preliminary results that should be OK but aren't double-checked yet. A significant addition is that I've added automatically generated examples of violations of the HD so you can confirm results for yourself. There is also <a href="http://users.ece.cmu.edu/~koopman/crc/hdlen.html">some do-it-yourself HD computation help here</a>.<br /><br />If you see a polynomial missing that is published somewhere let me know and I'll add it.<br /><br />I should mention that Prof. Berthold Gick from University of Applied Sciences, Koblenz, Germany has been independently working in this area and verified many of my results. More importantly, he's pointed out a few typos and other issues that I'm working to correct. I'd like to take this chance to thank him for his efforts. If anyone else notices problems please let me know.<br /><br />Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-20791784969070427682015-06-11T05:18:00.001-07:002015-06-11T05:18:23.868-07:00Is HD=1 Useful?<div class="moz-cite-prefix">I received an e-mail with a question as to why a HD=1 checksum would ever be useful (referred to on slide 89 of my Sept 2014 slide set on CRCs). The point is that HD=1 means you are not guaranteeing detection of any error, not even 1-bit errors. Here's my answer, which I am posting since it might have general interest:.</div><div class="moz-cite-prefix"><br /></div><div class="moz-cite-prefix">HD=1 (zero errors guaranteed to be detected) means that there is still a residual capability to randomly detect most errors (all errors except 1 in 2**k for k bits).</div><div class="moz-cite-prefix">If you only need an error detection ratio of a few orders of magnitude this is fine if you have a large CRC.<br /> <br />If you are using a 256 bit cryptographic checksum (which must be assumed to have HD=1) then undetected error probability is 1 in 2**256, which is pretty good. However, a high-HD CRC will usually get you better non-malicious error detection for less computational cost. <br /> </div><blockquote cite="mid:170783FC83F56540B5183F3CBA20401F86FA62C2@FMSMSX119.amr.corp.intel.com" type="cite"><div class="WordSection1"><div class="MsoNormal"><br /></div></div></blockquote>Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-86939314254965840292015-04-11T11:23:00.001-07:002015-04-11T11:23:10.202-07:00FAA CRC ReportAfter an extensive editing and approval process, the FAA has released the report that I did with Kevin Driscoll & Brendan Hall from Honeywell. You can see it here:<br /><br />Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity<br />DOT/FAA/TC-14/49<br /><a href="http://www.tc.faa.gov/its/worldpac/techrpt/tc14-49.pdf">http://www.tc.faa.gov/its/worldpac/techrpt/tc14-49.pdf</a><br /><br /><br /><br />Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-81893697798594708722014-09-27T14:22:00.000-07:002014-09-27T14:28:10.833-07:00Data Integrity Techniques: Aviation Best Practices for CRC & Checksum Error DetectionI just presented a session at an FAA sponsored conference on "Data Integrity Techniques: Aviation Best Practices for CRC & Checksum Error Detection" on Sept. 25. Here are the slides:<br /><br /><iframe src="//www.slideshare.net/slideshow/embed_code/39604136" width="476" height="400" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"></iframe><br /> (Acrobat download: <a href="http://users.ece.cmu.edu/~koopman/pubs/koopman14_crc_faa_conference_presentation.pdf">http://users.ece.cmu.edu/~koopman/pubs/koopman14_crc_faa_conference_presentation.pdf</a>)<br /><br /><hr /><br />A recording of an older variant of this presentation can be viewed below:<br /><br /><iframe allowfullscreen="" frameborder="0" height="400" msallowfullscreen="" src="https://app.box.com/embed_widget/s/nn5r9ogwpw100fqkp6g2?theme=blue" webkitallowfullscreen="" width="500"></iframe> <br /><br />Webinar download: <a href="https://cmu.box.com/s/nn5r9ogwpw100fqkp6g2">https://cmu.box.com/s/nn5r9ogwpw100fqkp6g2</a><br />Accompanying slides for that older webinar can be found: <a href="http://www.ece.cmu.edu/~koopman/pubs/01oct2013_koopman_faa_final_presentation.pdf">here</a><br /><div><br /></div>Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-63695590109995816482014-08-14T07:17:00.000-07:002014-08-14T07:17:22.738-07:00Significant update to on-line CRC performance data<br />I've managed to create a new set of pages with CRC performance data during my hobby time this summer.<br /><br />"Best" CRC Polynomials:<br /> <a href="http://users.ece.cmu.edu/~koopman/crc/index.html">http://users.ece.cmu.edu/~koopman/crc/index.html</a><br />This contains an extensive list of of good CRC polynomials for different CRC sizes and dataword lengths. I re-ran all the computations in light of some data that has become available since the initial publication a number of years back. The table is slightly different than the table I previously published. The old table is OK, but this one is marginally better than the old one for the data that was previously provided, so there is no pressing need to change systems based on the old version so long as you were running at shorter than 2Kbit dataword sizes. More importantly, this new table consideres unlimited dataword lengths and larger CRC sizes. (At this time the 32-bit computations are still running and they'll be updated as they are available.)<br /><br />CRC Polynomial Zoo with Hamming Weight Data<br /><div> <a href="http://users.ece.cmu.edu/~koopman/crc/hw_data.html">http://users.ece.cmu.edu/~koopman/crc/hw_data.html</a></div><div>Contains error detection performance data for a large variety of CRCs, including numerous "standard" and published CRCs. If you see one missing let me know with a citation and I'll add it.</div><div><br /></div>Please be sure to scroll down past the data to see the notes on how to interpret the summary page and the data files. The summary page is hand-created, and thus slightly prone to minor bugs, so please do double-check things there. The data files are 100% machine created and therefore less prone to bugs (and have no bugs as far as I know).<br /><br />I hope that this data is useful to others. Some of the large polynomials have incomplete or shortened data files, and will be updating those over time as the computations complete.<br /><div><br /></div>Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-58923146851698174842014-08-04T07:29:00.002-07:002015-12-05T03:38:25.562-08:00CRC publication errata<br />Thanks to Prof. Berthold Gick at University of Applied Sciences in Koblenz Germany for finding a few bugs in my published CRC values. (And also thanks for a very thorough second-check of results -- this is an essential part of scholarly publication that is not acknowledged as often as it should be!)<br /><br />I have updated presentations and papers that I can find with the following corrections:<br /><br />From my FAA presentation materials:<br />Polynomial HD=2 HD=3 HD=4<br />0x80000d | 16,777,212 | 5815 | 509 (length in bits at that HD)<br /><br /><br />From my 2002 paper:<br />Polynomial 0x992c1a4c has a maximal HD=6 payload of 32738 bits (originally published as 32737)<br /><br /><br />From many publications the table of 16-bit and smaller CRCs:<br />11-bit polynomial 0x5d7 has a maximal HD=5 payload of 26 bits (originally published as 25)<br /><br /><br />Some of the "best" polynomial recommendations have been updated. If you are unsure about a polynomial from a previous publication, you can look up its properties here:<br /> http://users.ece.cmu.edu/~koopman/crc/<br />and in the accompanying polynomial zoo (click on the polynomial size header in each column).<br /><br />If anyone else spots an error please do let me know. This work happens time-available, but I do strive to eventually fix any bugs I know about.<br /><br />Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-45306740488159138072012-05-12T08:18:00.000-07:002012-05-12T08:18:01.718-07:00CRC and Checksum Tutorial SlidesI recently presented an invitation-only webinar on the topic of CRC and Checksum good practices and error detection effectiveness. The talk was for an aviation audience, but it applies almost entirely to other applications as is. The recording didn't work out, but if there is enough demand I'll find time this summer to see if I can do an audio narration recording to go with the slides.<br /><br />Meanwhile, you can find the slides here:<br /><a href="http://www.ece.cmu.edu/%7Ekoopman/pubs/KoopmanCRCWebinar9May2012.pdf">http://www.ece.cmu.edu/~koopman/pubs/KoopmanCRCWebinar9May2012.pdf</a><br /><br />Contents:<br />- Introduction<br /> - Motivation -- why isn't this a solved problem?<br /> - Parity computations as an example<br /> - Error code construction and evaluation (without scary math)<br /> - Example using parity codes<br />- Checksums<br /> - What's a checksum?<br /> - Commonly used checksums and their performance<br />- Cyclic redundancy codes (CRCs)<br /> - What's a CRC<br /> - Commonly used CRC approaches and their performance<br />- Don't blindly trust what you hear on this topic<br /> - A good CRC is almost always much better than a good checksum<br /> - Many published (and popular) approaches are suboptimal or just plain wrong<br /> - There are some topics to be careful of for which we don't know the answers yet<br /><br />We are also collecting information about how CRCs and checksums are used in real applications (which is not necessarily the same as what researchers study!) If you have anecdotes, examples, or other information about what you do or what you'd like to do, we'd love to hear about it. If you are in the aviation community the FAA is running a much more specific survey just for you; let me know and I'll get you in touch with the appropriate FAA contact.<br /><br />(We can't necessarily provide immediate answers to specific questions such as "which polynomial should I use for this specific situation." But popular topics and questions that we think are broadly applicable will be put into the research bin and published here or in a report when results are available.) <br /><br /><br />Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-34923873816613908482012-01-15T07:00:00.000-08:002014-07-20T21:45:47.856-07:00Consolidated Wikipedia Pointers for Checksums and CRCsHere are some starting points within Wikipedia if you are interested in checksum and CRC background. (These articles also point to other places of interest.) Over time I hope to distill the practical application of all this in my blog, but for now these are reasonable starting points.<br /><ul><li>List of checksum and CRC algorithms: <a href="http://en.wikipedia.org/wiki/List_of_checksum_algorithms">http://en.wikipedia.org/wiki/List_of_checksum_algorithms </a></li></ul><ul><li>Longitudinal Redundancy Check (XOR checksum): <a href="http://en.wikipedia.org/wiki/Longitudinal_redundancy_check">http://en.wikipedia.org/wiki/Longitudinal_redundancy_check</a> </li></ul><ul><li>Overview of Checksums: <a href="http://en.wikipedia.org/wiki/Checksum">http://en.wikipedia.org/wiki/Checksum</a> <br /></li><li>Fletcher Checksum: <a href="http://en.wikipedia.org/wiki/Fletcher%27s_checksum">http://en.wikipedia.org/wiki/Fletcher%27s_checksum</a></li><li>Adler Checksum: <a href="http://en.wikipedia.org/wiki/Adler-32">http://en.wikipedia.org/wiki/Adler-32</a></li></ul><ul><li>Overview of CRC: <a href="http://en.wikipedia.org/wiki/Cyclic_redundancy_check">http://en.wikipedia.org/wiki/Cyclic_redundancy_check</a></li><li>More detailed example of CRC computation: <a href="http://en.wikipedia.org/wiki/Computation_of_CRC">http://en.wikipedia.org/wiki/Computation_of_CRC</a> </li><li>Mathematics of CRCs: <a href="http://en.wikipedia.org/wiki/Mathematics_of_CRC">http://en.wikipedia.org/wiki/Mathematics_of_CRC</a></li></ul> Related pages:<br /><ul><li>Overview of error detection and correction codes: <a href="http://en.wikipedia.org/wiki/Redundancy_check">http://en.wikipedia.org/wiki/Redundancy_check</a></li><li>Discussion of parity: <a href="http://en.wikipedia.org/wiki/Parity_bit">http://en.wikipedia.org/wiki/Parity_bit</a></li><li>Check digits (it's like parity for numbers handled by people): <a href="http://en.wikipedia.org/wiki/Check_digit">http://en.wikipedia.org/wiki/Check_digit</a></li></ul>It is important to realize that Wikipedia is not necessarily an authoritative source. For this area it seems there is enough critical mass of authors, editors and reviewers to get the pages into reasonable shape.Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-47402377730764736462012-01-01T07:00:00.000-08:002012-01-01T07:00:07.637-08:00CRC for Protecting A Single ValueSome critical applications need to protect a single byte or word of data in memory against corruption. (For example, if you want to be extra-sure about <a href="http://betterembsw.blogspot.com/2011/11/avoiding-eeprom-corruption-problems.html">protecting EEPROM values against corruption</a>.) A <a href="http://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html">previous post</a> gives good CRC polynomials for a wide range of circumstances, but it is always nice to know if you can do better for a special case. Below are optimal CRC polynomials for a few special cases involving small data words that might be stored in memory (RAM, EEPROM, or otherwise).<br /><br /><u>Protecting an 8-bit data word:</u><br />8-bit CRC: HD=5; 0x9C = x^8 + x^5 + x^4 + x^3 + 1 <br />16-bit CRC: HD=8; 0xE92F = x^16 + x^15 + x^14 + x^12 + x^9 + x^6 + x^4 + x^3 + x^2 + x + 1<br />32-bit CRC: HD=16; 0xC563942F = x^32 +x^31 +x^27 +x^25 +x^23 +x^22 +x^18 +x^17 +x^16 +x^13 +x^11 +x^6 +x^4 +x^3 +x^2 +x +1 <br /><br /><u>Protecting a 16-bit data word:</u><br />8-bit CRC: HD=4; 0x93 = x^8 + x^5 + x^2 + x + 1 <br />16-bit CRC: HD=7; 0x978A = x^16 + x^13 + x^11 + x^10 + x^9 + x^8 + x^4 + x^2 + 1<br />32-bit CRC: HD=14; 0xB396786D = x^32 +x^30 +x^29 +x^26 +x^25 +x^24 +x^21 +x^19 +x^18 +x^15 +x^14 +x^13 +x^12 +x^7 +x^6 +x^4 +x^3 +x +1<br /><br /><u>Protecting a 32-bit data word:</u><br />8-bit CRC: HD=4; 0x92 = x^8 + x^5 + x^2 + 1 <br />16-bit CRC: HD=6; 0x8BFC = x^16 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1<br />32-bit CRC: HD=12; 0xB527A43B = x^32 +x^30 +x^29 +x^27 +x^25 +x^22 +x^19 +x^18 +x^17 +x^16 +x^14 +x^11 +x^6 +x^5 +x^4 +x^2 +x +1<br /><br />The hex number has an implicit +1. "HD" means Hamming Distance. Other information about this topic can be found at my <a href="http://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html">previous post on good CRCs</a>.<br /><br />Note that for this sort of use it is a good idea to "seed" the CRC computation with a value of that is not zero. That avoids a data word value of zero giving a CRC computed value of zero -- which will result in an undetected error if memory is wiped to all zeros for some reason.Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com2tag:blogger.com,1999:blog-5362874688848316436.post-52748434167254838402011-12-28T07:00:00.000-08:002012-01-03T04:42:10.193-08:00Pointers to other CRC discussionsOver time I'll add links to postings on CRCs that I find interesting or entertaining:<br /><br />Nigel Jones has an essay on how we don't always stop to think about whether what we're doing is actually good enough, even if it is what we've always done. In this case he's talking about CRC selection.<br />(<a href="http://embeddedgurus.com/stack-overflow/2009/06/thoughts-on-bccs-lrcs-crcs-and-being-experienced/">link: Thoughts on BCC's, LRC's, CRC's and being experienced</a>)<br /><br /> Lammert Bies has a Q&A forum about practical implementations of standard CRC functions.<br />(<a href="http://www.lammertbies.nl/forum/viewforum.php?f=11%20">link: Error Correction and Detection Forum</a> )Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-11946534601654354172011-12-26T07:00:00.000-08:002013-07-15T06:11:23.757-07:00What is the best CRC up to 16 bits in size?<br />Please see the posting at this link for this article:<br /><a href="http://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html">http://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html</a><br /><br /><div style="text-align: center;"><br /></div>Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0tag:blogger.com,1999:blog-5362874688848316436.post-38683152087573649202011-12-19T07:00:00.000-08:002013-07-15T06:14:50.801-07:00Should you use a CRC or Checksum?<br />Please use this link to see this blog posting:<br /><a href="http://betterembsw.blogspot.com/2010/05/which-error-detection-code-should-you.html">http://betterembsw.blogspot.com/2010/05/which-error-detection-code-should-you.html</a><br /><br /><br /><ul></ul>Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com4tag:blogger.com,1999:blog-5362874688848316436.post-58716761009610150002011-12-17T13:30:00.000-08:002012-01-03T04:42:39.995-08:00WelcomeWelcome to my blog on Checksums and CRCs!<br /><br />Over time I'll be posting articles related to checksums, cyclic redundancy codes, parity strategies, and their effectiveness. If you have a particular topic you'd like me to post on please let me know and I'll put it in the idea bin.<br /><br />If you are looking for more general embedded system topics, please have a look at my <a href="http://betterembsw.blogspot.com/">Better Embedded Software Blog</a>.Phil Koopmanhttp://www.blogger.com/profile/11849599272360094243noreply@blogger.com0