?? cyclic redundancy check.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0067)http://utopia.knoware.nl/users/eprebel/Communication/CRC/index.html -->
<HTML lang=en-US><HEAD><TITLE>Cyclic Redundancy Check</TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1"><LINK
href="Cyclic Redundancy Check.files/Styles.css" type=text/css rel=stylesheet>
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY>
<H1>Cyclic Redundancy Check</H1>
<H2>Introduction</H2>
<P>Different methods exist to calculate a check number for binary data, to be
able to see if the data is not altered, for example, after being sent through
some communication channel.<BR>Cyclic Redundancy Check (CRC) is a common method
for protecting binary data that way. Different CRCs exist, which in the past has
resulted in a naming scheme. This page discusses the standard ITU-TSS CRC, often
written as a formula:
G(x)=x<SUP>16</SUP>+x<SUP>12</SUP>+x<SUP>5</SUP>+1.<BR>Characteristic of this
CRC is its 16 bits size and its initial value $FFFF. Although, you can encounter
an initial value $0000 too. </P>
<H2>Hardware</H2>
<P>A CRC generator can be built as a piece of hardware. </P>
<P><IMG height=64 alt=[Image] src="Cyclic Redundancy Check.files/Hardware.gif"
width=424> </P>
<P>Each bit (b) of the binary data is shifted into the CRC register after being
XORed with the CRCs most significant bit. This part of the generator ensures the
cyclical aspect of CRC. The XOR result is inserted in CRC bit 5 and 12 too.
During the processing of bit b, all current CRC bits (modified or unmodified)
are shifted one position to the left.<BR>If a byte must be processed, all 8 bits
must be processed one after another. The most significant bit is processed
first. </P>
<P>Example: </P>
<TABLE>
<TBODY>
<TR>
<TD>Initial CRC value:</TD>
<TD><CODE>1111 1111 1111 1111</CODE></TD></TR>
<TR>
<TD>Byte to process:</TD>
<TD><CODE>0101 1010</CODE></TD></TR></TBODY></TABLE>
<P><IMG height=158 alt=[Image] src="Cyclic Redundancy Check.files/Example.gif"
width=450> </P>
<TABLE>
<TBODY>
<TR>
<TD>New CRC value:</TD>
<TD><CODE>0001 1010 0100 1111</CODE></TD></TR></TBODY></TABLE>
<H2>Formula</H2>
<P>Expressed as a set of formulas, processing a bit <CODE>b</CODE> means: </P>
<TABLE>
<TBODY>
<TR>
<TD><CODE>c<SUP>*</SUP><SUB>15</SUB>=c<SUB>14</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>14</SUB>=c<SUB>13</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>13</SUB>=c<SUB>12</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>12</SUB>=c<SUB>11</SUB><IMG height=9 alt=^
src="Cyclic Redundancy Check.files/XOR.gif"
width=11>c<SUB>15</SUB></CODE></TD></TR>
<TR>
<TD><CODE>c<SUP>*</SUP><SUB>11</SUB>=c<SUB>10</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>10</SUB>=c<SUB>9</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>9 </SUB>=c<SUB>8</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>8 </SUB>=c<SUB>7</SUB></CODE></TD></TR>
<TR>
<TD><CODE>c<SUP>*</SUP><SUB>7 </SUB>=c<SUB>6</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>6 </SUB>=c<SUB>5</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>5 </SUB>=c<SUB>4</SUB><IMG height=9 alt=^
src="Cyclic Redundancy Check.files/XOR.gif"
width=11>c<SUB>15</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>4 </SUB>=c<SUB>3</SUB></CODE></TD></TR>
<TR>
<TD><CODE>c<SUP>*</SUP><SUB>3 </SUB>=c<SUB>2</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>2 </SUB>=c<SUB>1</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>1 </SUB>=c<SUB>0</SUB></CODE></TD>
<TD><CODE>c<SUP>*</SUP><SUB>0 </SUB>=c<SUB>15</SUB><IMG height=9
alt=^ src="Cyclic Redundancy Check.files/XOR.gif"
width=11>b</CODE></TD></TR></TBODY></TABLE>
<H2>Software</H2>
<P>One can build a CRC generator in software, that is analoguous to the hardware
solution. The solution processes each bit separately. </P>
<P>Using the C programming language, the source code could be:
</P><CODE>unsigned short crc = 0xFFFF;<BR>unsigned short temp;<BR>unsigned char
byte = 0x5A; //just as an example<BR>unsigned short index;<BR><BR>for(index = 0;
index <= 7;
index++)<BR> {<BR> temp = (crc
>> 15) ^ (byte >> 7);<BR> crc <<=
1;<BR> if(temp)<BR> {<BR> crc
^=
0x1021;<BR> }<BR> byte
<<= 1;<BR> } </CODE>
<P>First, b XOR c<SUB>15</SUB> (the cyclical value) is calculated. Then the CRC
bits are shifted to the left (c<SUB>0</SUB> becomes 0). The cyclical value has
to be processed in c<SUB>0</SUB>, c<SUB>5</SUB> and c<SUB>12</SUB>. If the
cyclical value equals 1, bits c<SUB>0</SUB>, c<SUB>5</SUB> and c<SUB>12</SUB>
are changed at the same moment by XORing the CRC with value
0000 0001 0100 0001 (0x1021). If the cyclical value equals 0, the
CRC should be XORed with value 0000 0000 0000 0000. XORing the
CRC with 0x0000 does not change the CRC, and therefore it is skipped. Finally
the next bit to be processed is prepared. </P>
<P>In the source code example, the initial CRC value and the byte to be
processed are already defined. The calculations sub results are: </P>
<TABLE>
<TBODY>
<TR align=middle>
<TD width=50><CODE>crc</CODE></TD>
<TD width=50><CODE>byte</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>F F F F</CODE></TD>
<TD width=50><CODE>5 A</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>E F D F</CODE></TD>
<TD width=50><CODE>B 4</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>D F B E</CODE></TD>
<TD width=50><CODE>6 8</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>A F 5 D</CODE></TD>
<TD width=50><CODE>D 0</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>5 E B A</CODE></TD>
<TD width=50><CODE>A 0</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>A D 5 5</CODE></TD>
<TD width=50><CODE>4 0</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>4 A 8 B</CODE></TD>
<TD width=50><CODE>8 0</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>8 5 3 7</CODE></TD>
<TD width=50><CODE>0 0</CODE></TD></TR>
<TR align=middle>
<TD width=50><CODE>1 A 4 F</CODE></TD></TR></TBODY></TABLE>
<H2>Simplification</H2>
<P>When processing a byte, the eight most significant bits of the 'old' CRC
value, will be shifted out of the CRC. Somewhere in the process, these bits will
be XORed with the byte to be processed. This XOR can be done at once and as a
first step. A temporary variable is not needed too.<BR>The simpified source code
could be: </P><CODE>unsigned short crc = 0xFFFF;<BR>unsigned char byte =
0x5A;<BR>unsigned short index;<BR><BR>crc ^= byte << 8;<BR>for(index = 0;
index <= 7;
index++)<BR> {<BR> crc = crc &
0x8000 ? (crc << 1) ^ 0x1021 : crc <<
1;<BR> } </CODE>
<P>In the source code example too, the initial CRC value and the byte to be
processed are already defined. The calculations sub results are: </P>
<TABLE>
<TBODY>
<TR align=middle>
<TD><CODE>crc</CODE></TD></TR>
<TR align=middle>
<TD><CODE>A 5 F F</CODE></TD></TR>
<TR align=middle>
<TD><CODE>5 B D F</CODE></TD></TR>
<TR align=middle>
<TD><CODE>B 7 B E</CODE></TD></TR>
<TR align=middle>
<TD><CODE>7 F 5 D</CODE></TD></TR>
<TR align=middle>
<TD><CODE>F E B A</CODE></TD></TR>
<TR align=middle>
<TD><CODE>E D 5 5</CODE></TD></TR>
<TR align=middle>
<TD><CODE>C A 8 B</CODE></TD></TR>
<TR align=middle>
<TD><CODE>8 5 3 7</CODE></TD></TR>
<TR align=middle>
<TD><CODE>1 A 4 F</CODE></TD></TR></TBODY></TABLE>
<H2>Acceleration</H2>
<P>To be able to accelerate the software CRC generator, we first take a look at
the formulas that express the processing of 8 bits
<TABLE>
<TBODY>
<TR>
<TD><CODE>t<SUB>7..0</SUB></CODE></TD>
<TD><CODE>=</CODE></TD>
<TD><CODE>c<SUB>15..8</SUB></CODE></TD>
<TD><CODE><IMG height=9 alt=^ src="Cyclic Redundancy Check.files/XOR.gif"
width=11></CODE></TD>
<TD><CODE>b<SUB>7..0</SUB></CODE></TD></TR>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -