📄 crc-ccitt -- 16-bit.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0052)http://www.joegeluso.com/software/articles/ccitt.htm -->
<HTML><HEAD><TITLE>CRC-CCITT -- 16-bit</TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="Joe Geluso" name=Author>
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY><A href="http://www.joegeluso.com/">http://www.joegeluso.com/</A> <BR>
<HR width="100%">
<H2>CRC16-CCITT</H2>
<UL>
<LI><A
href="http://www.joegeluso.com/software/articles/ccitt.htm#overview">Overview</A>
<LI><A
href="http://www.joegeluso.com/software/articles/ccitt.htm#general">General</A>
<LI><A
href="http://www.joegeluso.com/software/articles/ccitt.htm#results">Results
from the C-language Implementations</A>
<LI><A
href="http://www.joegeluso.com/software/articles/ccitt.htm#long-hand">Long-hand
Calculation for a One-byte Message</A>
<LI><A
href="http://www.joegeluso.com/software/articles/ccitt.htm#source">Source Code
for the C-language Implementations</A>
<LI><A
href="http://www.joegeluso.com/software/articles/ccitt.htm#refs">References</A>
-- updated April 4, 2003
<LI><A href="http://www.joegeluso.com/software/articles/ccitt.htm#style">Style
Notes</A>
<LI><A
href="http://www.joegeluso.com/software/articles/ccitt.htm#addendum">Addendum</A>
-- added April 4, 2003 (perhaps a little less confrontational than other
sections) </LI></UL>
<P><BR>
<HR width="100%">
<H3><A name=overview></A>Overview</H3>This page presents accurate
implementations (long-hand and programmed) of the 16-bit CRC-CCITT
specification, which is:
<UL>
<LI>Width = 16 bits
<LI>Truncated polynomial = 0x1021
<LI>Initial value = 0xFFFF
<LI>Input date is NOT reflected
<LI>Output CRC is NOT reflected
<LI>No XOR is performed on the output CRC </LI></UL>A C-language program is
included which produces CRC values which conform to this specification.
The program also includes a routine which demonstrates how an incorrect "<A
href="http://www.joegeluso.com/software/articles/ccitt.htm#results">check
value</A>" which has been found on the web may be generated. <BR>
<P>
<HR width="100%">
<H3><A name=general></A>General</H3>Why yet another document on calculating
CRCs? Because this one:
<UL>
<LI>Indicates that some common implementations of the 16-bit CRC-CCITT may
produce incorrect values.
<LI>Provides source code for the 16-bit CRC-CCITT without using tables or
reversed polynomials. The program <A
href="http://www.joegeluso.com/software/articles/ccitt.htm#source">below</A>
implements the concepts presented in the first 8 sections of "<A
href="http://www.ross.net/crc/crcpaper.html">A Painless Guide to CRC Error
Detection Algorithms</A>" by Ross Williams. Things become significantly
more complex in progressing beyond section 8 of that document. If a
table-driven implementation of the 16-bit CRC-CCITT is to be developed, a
solid reference is needed to ensure that it is working correctly. The
source code in this document may fill that role. </LI></UL>Important features of
a standard CRC are that it:
<BLOCKQUOTE>
<LI>Can be used to validate data
<LI>Is reproducible by others </LI></BLOCKQUOTE>The first feature above is easy
to realize in a closed system if corruption of data is infrequent (but
substantial when it occurs). The term "closed system" refers to a
situation where the CRC need not be communicated to others. A correct
implementation of a 16-bit CRC will detect a change in a single bit in a message
of over 8000 bytes. An erroneous CRC implementation may not be able to
detect such subtle errors. If errors are usually both rare and large
(affecting several bits), then a faulty 16-bit CRC implementation may still be
adequate in a closed system.
<P>The second feature above -- that the CRC is reproducible by others -- is
crucial in an open system; that is, when the CRC must be communicated to
others. If the integrity of data passed between two applications is to be
verified using a CRC defined by a particular standard, then the implementation
of that standard must produce the same result in both applications -- otherwise,
valid data will be reported as corrupt.
<P>Reproducibility may be satisfied by even a botched implementation of a
standard CRC in most cases -- if everyone uses the same erroneous implementation
of the standard. But this approach:
<UL>
<LI>Modifies the standard in ways that are both unofficial and undocumented.
<LI>Creates confusion when communicating with others who have not adopted the
botched implementation as the implied standard. </LI></UL>It appears that some
CRC implementations available on the web produce incorrect values for the 16-bit
CRC-CCITT. How to tell if a CRC16-CCITT implementation was botched?
By calculating the CRC for a reference string.
<P>The CRC value for the 9-byte reference string, "123456789" is
<B>0xE5CC</B>. Some web pages report that the value for reference string
should be <I>0x29B1</I> -- but this value is returned by an implementation which
does NOT conform to the specification above. CRC values for other
reference strings are listed <A
href="http://www.joegeluso.com/software/articles/ccitt.htm#results">elsewhere</A>
in this document.
<P>The <B>bolding</B> and <I>italics</I> above are used to emphasize the correct
value and distort the incorrect value in the hope that it will discourage
propagation of the incorrect value.
<P>Why focus on the 16-bit CRC-CCITT (polynomial 0x1021) and not CRC16
(polynomial 0x8005), which appears to have wider use? Because the 16-bit
CRC-CCITT:
<UL>
<LI>Is a straightforward 16-bit CRC implementation in that it doesn't involve:
<UL>
<LI>reflection of data
<LI>reflection of the final CRC value </LI></UL>
<LI>Starts with a non-zero initial value -- leading zero bits can't affect the
CRC16 used by LHA, ARC, etc., because its initial value is zero.
<LI>It requires no additional XOR operation after everything else is
done. The CRC32 implementation used by Ethernet, Pkzip, etc., requires
this operation; less common 16-bit CRCs may require it as well. </LI></UL>Why
use a 16-bit CRC instead of a 32-bit CRC? Because it:
<UL>
<LI>Can be calculated faster than a 32-bit CRC.
<LI>Requires less space than a 32-bit CRC for storage, display or printing.
<LI>Is usually long enough if the data being safeguarded is fewer than several
thousand bytes in length, e.g., individual records in a database. </LI></UL>
<P><BR>
<HR width="100%">
<H3><A name=results></A>Results from the C-language Implementations</H3>The
following CRC values were produced by the program whose source code is listed <A
href="http://www.joegeluso.com/software/articles/ccitt.htm#source">elsewhere</A>
in this document. The "Good_CRC" values are in accordance with the
CRC-CCITT specification as defined at the <A
href="http://www.joegeluso.com/software/articles/ccitt.htm#overview">top of this
document</A>. The "Bad_CRC" values are produced by an implementation which
reports the incorrect check value that is reported on some web pages for the
reference string "123456789". The validity of the "Good_CRC" values below
is demonstrated <A
href="http://www.joegeluso.com/software/articles/ccitt.htm#long-hand">elsewhere</A>
in this document. <BR> <BR>
<TABLE border=1>
<TBODY>
<TR>
<TD>
<CENTER>
<H4>Message</H4></CENTER></TD>
<TD>
<H4>Good_CRC</H4></TD>
<TD>
<H4>Bad_CRC</H4></TD>
<TD>
<H4>Message Length (bytes)</H4></TD></TR>
<TR>
<TD>
<CENTER><I>-None-</I></CENTER></TD>
<TD>
<CENTER>0x1D0F</CENTER></TD>
<TD>
<CENTER>0xFFFF</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD></TR>
<TR>
<TD>
<CENTER>A</CENTER></TD>
<TD>
<CENTER>0x9479</CENTER></TD>
<TD>
<CENTER>0xB915</CENTER></TD>
<TD>
<CENTER>1</CENTER></TD></TR>
<TR>
<TD>
<CENTER>123456789</CENTER></TD>
<TD>
<CENTER>0xE5CC</CENTER></TD>
<TD>
<CENTER>0x29B1</CENTER></TD>
<TD>
<CENTER>9</CENTER></TD></TR>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -