1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Introduction</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../crc.html" title="Chapter 12. Boost.CRC 1.5"> 10<link rel="prev" href="../crc.html" title="Chapter 12. Boost.CRC 1.5"> 11<link rel="next" href="crc_basic.html" title="Theoretical CRC Computer"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="../crc.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../crc.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="crc_basic.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="crc.introduction"></a><a class="link" href="introduction.html" title="Introduction">Introduction</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"><dt><span class="section"><a href="introduction.html#crc.introduction.intro_crcs">CRCs</a></span></dt></dl></div> 31<div class="note"><table border="0" summary="Note"> 32<tr> 33<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 34<th align="left">Note</th> 35</tr> 36<tr><td align="left" valign="top"><p> 37 Some of the introductory material is based on <a href="http://www.ross.net/crc/download/crc_v3.txt" target="_top"><span class="emphasis"><em>A 38 Painless Guide to CRC Error Detection Algorithms</em></span></a> by Ross 39 N. Williams at his <a href="http://www.ross.net/crc/" target="_top"><span class="bold"><strong>The 40 CRC Pitstop</strong></span></a> site. 41 </p></td></tr> 42</table></div> 43<p> 44 When binary data is transmitted, usually electronically, there is a chance 45 that the data gets corrupted. One method to pick up said corruption is to generate 46 some value that is coded from the original data, send said value to the receiver, 47 then confirm that the received data generates the same value when it's coded 48 at the destination. 49 </p> 50<p> 51 There are several possibilities after the receiver's check: 52 </p> 53<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 54<li class="listitem"> 55 The check value matches at both places and the data was transmitted intact. 56 </li> 57<li class="listitem"> 58 The data got corrupted and the check values do not match. 59 </li> 60<li class="listitem"> 61 The data is intact, but the check value got corrupted. This can't the distinguished 62 from the previous case, but is a (relatively) safe false positive. 63 </li> 64<li class="listitem"> 65 Either the data and/or check value gets corrupted, but such that the results 66 of the check-coding are still consistent. This is a dangerous false negative! 67 </li> 68</ul></div> 69<p> 70 The way to minimize false negatives is to choose coding algorithms that cause 71 a lot of churn per input, especially a variable amount. 72 </p> 73<p> 74 The check values are known as <span class="bold"><strong>checksum</strong></span>s because 75 they are used to <span class="emphasis"><em>check</em></span> for data consistency and the first 76 coding algorithms were addition- (i.e. <span class="emphasis"><em>sum</em></span>ming-) based. 77 </p> 78<div class="section"> 79<div class="titlepage"><div><div><h3 class="title"> 80<a name="crc.introduction.intro_crcs"></a><a class="link" href="introduction.html#crc.introduction.intro_crcs" title="CRCs">CRCs</a> 81</h3></div></div></div> 82<div class="toc"><dl class="toc"> 83<dt><span class="section"><a href="introduction.html#crc.introduction.intro_crcs.intro_crcs_impl">CRC Implementation</a></span></dt> 84<dt><span class="section"><a href="introduction.html#crc.introduction.intro_crcs.intro_crcs_augment">Message 85 Augmentation</a></span></dt> 86<dt><span class="section"><a href="introduction.html#crc.introduction.intro_crcs.intro_crcs_param">Other 87 CRC Parameters</a></span></dt> 88<dt><span class="section"><a href="introduction.html#crc.introduction.intro_crcs.intro_crcs_rmca">Compact 89 CRC Parameter Specification</a></span></dt> 90</dl></div> 91<p> 92 <span class="bold"><strong>Cyclic Redundancy Codes</strong></span> are a type of consistency 93 check that treats the message data as a (long) dividend of a modulo-2 polynomial 94 division. Modulo-2 arithmetic doesn't use carries/borrows when combining 95 numbers. A specific CRC defines a set number of bits to work on at a time, 96 where said number is also the degree of a fixed polynomial (with modulo-2 97 coefficients) used as a divisor. 98 </p> 99<p> 100 Since ordering doesn't apply to modulo arithmetic, the check between the 101 current high part of the dividend and the trial partial product (of the divisor 102 and the trial new quotient coefficient) is done by seeing if the highest-degree 103 coefficient of the dividend is one. (The highest-degree coefficient of the 104 divisor must be one by definition, since it's the only non-zero choice.) 105 The remainder after the division is finished is used as the basis of the 106 CRC checksum. 107 </p> 108<div class="section"> 109<div class="titlepage"><div><div><h4 class="title"> 110<a name="crc.introduction.intro_crcs.intro_crcs_impl"></a><a class="link" href="introduction.html#crc.introduction.intro_crcs.intro_crcs_impl" title="CRC Implementation">CRC Implementation</a> 111</h4></div></div></div> 112<p> 113 For a given degree <span class="emphasis"><em>x</em></span> for the modulo-2 polynomial divisor, 114 the remainder will have at most <span class="emphasis"><em>x</em></span> terms (from degree 115 <span class="emphasis"><em>x</em></span> - 1 down to the constant term). The coefficients 116 are modulo-2, which means that they can be represented by 0's and 1's. 117 So a remainder can be modeled by an (unsigned) integer of at least <span class="emphasis"><em>x</em></span> 118 bits in <span class="bold"><strong>width</strong></span>. 119 </p> 120<p> 121 The divisor must have its <span class="emphasis"><em>x</em></span> degree term be one, which 122 means it is always known and can be implied instead of having to explicitly 123 include in representations. Its lower <span class="emphasis"><em>x</em></span> terms must 124 be specified, so a divisor can be modeled the same way as remainders. With 125 such a modeling, the divisor representation could be said to be truncated 126 since the uppermost term's value is implied and not stored. 127 </p> 128<p> 129 The remainder and <span class="bold"><strong>(truncated) divisor polynomial</strong></span>s 130 are stored as basic computer integers. This is in contrast to the dividend, 131 which is modeled from the input stream of data bits, where each new incoming 132 bit is the next lower term of the dividend polynomial. Long division can 133 be processed in piecemeal, reading new upper terms as needed. This maps 134 to reading the data a byte (or bit) at a time, generating updated remainders 135 just-in-time, without needing to read (and/or store(!)) the entire data 136 message at once. 137 </p> 138<p> 139 Long division involves appending new dividend terms after the previous 140 terms have been processed into the (interim) remainder. So the remainder 141 it the only thing that has to change during each division step; a new input 142 byte (or bit) is combined with the remainder to make the interim dividend, 143 and then combined with the partial product (based on the divisor and top 144 dividend bit(s)) to become a remainder again. 145 </p> 146</div> 147<div class="section"> 148<div class="titlepage"><div><div><h4 class="title"> 149<a name="crc.introduction.intro_crcs.intro_crcs_augment"></a><a class="link" href="introduction.html#crc.introduction.intro_crcs.intro_crcs_augment" title="Message Augmentation">Message 150 Augmentation</a> 151</h4></div></div></div> 152<p> 153 When all of the input data has been read during division, the last <span class="emphasis"><em>x</em></span> 154 bits are still stuck in the interim remainder. They have not been pushed 155 through the division steps; to do so, <span class="emphasis"><em>x</em></span> zero-valued 156 extra bits must be passed into the system. This ensures all of the message's 157 data bits get processed. The post-processed remainder is the checksum. 158 The system requires the message to be <span class="bold"><strong>augmented</strong></span> 159 with <span class="emphasis"><em>x</em></span> extra bits to get results. 160 </p> 161<p> 162 Alternatively, if the post-division augmentation bits are the expected 163 checksum instead, then the remainder will "subtract" the checksum 164 with itself, giving zero as the final remainder. The remainder will end 165 up non-zero if bit errors exist in either the data or checksum or both. 166 This option requires the checksum to be fed from highest-order bit first 167 on down (i.e. big endian). 168 </p> 169<p> 170 Exploiting the properties of how the division is carried out, the steps 171 can be rearranged such that the post-processing zero-valued bits are not 172 needed; their effect is merged into the start of the process. Such systems 173 read <span class="bold"><strong>unaugmented</strong></span> messages and expose the 174 checksum directly from the interim remainder afterwards. (You can't use 175 the "augment-message-with-checksum-and-zero-check" technique 176 with this, of course.) 177 </p> 178</div> 179<div class="section"> 180<div class="titlepage"><div><div><h4 class="title"> 181<a name="crc.introduction.intro_crcs.intro_crcs_param"></a><a class="link" href="introduction.html#crc.introduction.intro_crcs.intro_crcs_param" title="Other CRC Parameters">Other 182 CRC Parameters</a> 183</h4></div></div></div> 184<p> 185 Since long division proceeds from the uppermost terms on down, it's easiest 186 to treat an incoming byte as the uppermost unprocessed terms, and to read 187 the bits within that byte as the highest-order bit is the uppermost unprocessed 188 term and go down. However, some hardware implementations have an easier 189 time reading each byte from the lowest-order bit and go up. To simulate 190 those systems in software, the program needs to be flagged that <span class="bold"><strong>input reflection</strong></span> needs to be applied. Reflecting 191 a built-in integer reverses the order of its bits, such that the lowest- 192 and highest-order bits swap states, the next-lowest- and next-highest-order 193 bits swap, etc. The input reflection can be done by reflecting each byte 194 as it comes in or keeping the bytes unchanged but reflect the other internal 195 functioning. The latter sounds harder, but what it usually done in the 196 real world, since it's a one-time cost, unlike reflecting the bytes. 197 </p> 198<p> 199 Similarly, the final remainder is processed by some hardware in reverse 200 order, which means software that simulate such systems need to flag that 201 <span class="bold"><strong>output reflection</strong></span> is in effect. 202 </p> 203<p> 204 Some CRCs don't return the remainder directly (reflected or not), but add 205 an extra step complementing the output bits. Complementing turns 1 values 206 into 0 values and vice versa. This can simulated by using a XOR (exclusive-or) 207 bit mask of all 1-values (of the same bit length as the remainder). Some 208 systems use a <span class="bold"><strong>final XOR mask</strong></span> that isn't 209 all 1-values, for variety. (This mask takes place <span class="emphasis"><em>after</em></span> 210 any output reflection.) 211 </p> 212<p> 213 At the other end, the built-in-integer register normally starts at zero 214 as the first bytes are read. Instead of just doing nothing but load input 215 bits for <span class="emphasis"><em>x</em></span> steps, some CRC systems use a non-zero 216 <span class="bold"><strong>initial remainder</strong></span> to add extra processing. 217 This initial value has to be different for the augmented versus un-augmented 218 versions of the same system, due to possible incorporation with the zero-valued 219 augment bits. 220 </p> 221</div> 222<div class="section"> 223<div class="titlepage"><div><div><h4 class="title"> 224<a name="crc.introduction.intro_crcs.intro_crcs_rmca"></a><a class="link" href="introduction.html#crc.introduction.intro_crcs.intro_crcs_rmca" title="Compact CRC Parameter Specification">Compact 225 CRC Parameter Specification</a> 226</h4></div></div></div> 227<p> 228 The Rocksoft™ Model CRC Algorithm, or RMCA for short, was designed 229 by Ross Williams to describe all the specification points of a given CRC 230 system (quoted): 231 </p> 232<div class="variablelist"> 233<p class="title"><b>RMCA Parameters</b></p> 234<dl class="variablelist"> 235<dt><span class="term">WIDTH</span></dt> 236<dd><p> 237 This is the width of the algorithm expressed in bits. This is one 238 less than the width of the Poly. 239 </p></dd> 240<dt><span class="term">POLY</span></dt> 241<dd><p> 242 This parameter is the poly. This is a binary value that should be 243 specified as a hexadecimal number. The top bit of the poly should 244 be omitted. For example, if the poly is 10110, you should specify 245 06. An important aspect of this parameter is that it represents the 246 unreflected poly; the bottom bit of this parameter is always the 247 LSB of the divisor during the division regardless of whether the 248 algorithm being modelled is reflected. 249 </p></dd> 250<dt><span class="term">INIT</span></dt> 251<dd><p> 252 This parameter specifies the initial value of the register when the 253 algorithm starts. This is the value that is to be assigned to the 254 register in the direct table algorithm. In the table algorithm, we 255 may think of the register always commencing with the value zero, 256 and this value being XORed into the register after the N'th bit iteration. 257 This parameter should be specified as a hexadecimal number. 258 </p></dd> 259<dt><span class="term">REFIN</span></dt> 260<dd><p> 261 This is a boolean parameter. If it is FALSE, input bytes are processed 262 with bit 7 being treated as the most significant bit (MSB) and bit 263 0 being treated as the least significant bit. If this parameter is 264 FALSE, each byte is reflected before being processed. 265 </p></dd> 266<dt><span class="term">REFOUT</span></dt> 267<dd><p> 268 This is a boolean parameter. If it is set to FALSE, the final value 269 in the register is fed into the XOROUT stage directly, otherwise, 270 if this parameter is TRUE, the final register value is reflected 271 first. 272 </p></dd> 273<dt><span class="term">XOROUT</span></dt> 274<dd><p> 275 This is an W-bit value that should be specified as a hexadecimal 276 number. It is XORed to the final register value (after the REFOUT) 277 stage before the value is returned as the official checksum. 278 </p></dd> 279</dl> 280</div> 281<p> 282 His description assumes an octet-sized byte. The <span class="emphasis"><em>POLY</em></span> 283 is the (truncated) divisor. The <span class="emphasis"><em>INIT</em></span> is the initial 284 remainder, assuming the unaugmented version of CRC processing is used. 285 (If you're using an augmented-style CRC, you have to undo the effect of 286 the built-in zero-augment before initialization.) 287 </p> 288</div> 289<p> 290 The two function templates and two class templates in this library provide 291 ways to carry out CRC computations. You give the various Rocksoft™ 292 Model CRC Algorithm parameters as template parameters and/or constructor 293 parameters. You then submit all the message data bytes at once (for the functions) 294 or piecemeal (for the class objects). 295 </p> 296</div> 297<p> 298 Note that some error-detection techniques merge their checksum results within 299 the message data, while CRC checksums are either at the end (when augmented, 300 without either kind of reflection, with a bit-width that's a multiple of byte 301 size, and no XOR mask) or out-of-band. 302 </p> 303</div> 304<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 305<td align="left"></td> 306<td align="right"><div class="copyright-footer">Copyright © 2001, 2003, 2012 Daryle Walker<p> 307 Distributed under the Boost Software License, Version 1.0. (See the accompanying 308 file LICENSE_1_0.txt or a copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 309 </p> 310</div></td> 311</tr></table> 312<hr> 313<div class="spirit-nav"> 314<a accesskey="p" href="../crc.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../crc.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="crc_basic.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 315</div> 316</body> 317</html> 318
