发信人: micheal (平凡的世界), 信区: ECE
标  题: A Painless Guide to CRC [9]
发信站: 大红花的国度 (Fri Jun  2 09:55:52 2000), 转信

20. Summary
-----------
This document has provided a detailed explanation of CRC algorithms
explaining their theory and stepping through increasingly
sophisticated implementations ranging from simple bit shifting through
to byte-at-a-time table-driven implementations. The various
implementations of different CRC algorithms that make them confusing
to deal with have been explained. A parameterized model algorithm has
been described that can be used to precisely define a particular CRC
algorithm, and a reference implementation provided. Finally, a program
to generate CRC tables has been provided.
21. Corrections
---------------
If you think that any part of this document is unclear or incorrect,
or have any other information, or suggestions on how this document
could be improved, please context the author. In particular, I would
like to hear from anyone who can provide Rocksoft^tm Model CRC
Algorithm parameters for standard algorithms out there.
A. Glossary
-----------
CHECKSUM - A number that has been calculated as a function of some
message. The literal interpretation of this word "Check-Sum" indicates
that the function should involve simply adding up the bytes in the
message. Perhaps this was what early checksums were. Today, however,
although more sophisticated formulae are used, the term "checksum" is
still used.
CRC - This stands for "Cyclic Redundancy Code". Whereas the term
"checksum" seems to be used to refer to any non-cryptographic checking
information unit, the term "CRC" seems to be reserved only for
algorithms that are based on the "polynomial" division idea.
G - This symbol is used in this document to represent the Poly.
MESSAGE - The input data being checksummed. This is usually structured
as a sequence of bytes. Whether the top bit or the bottom bit of each
byte is treated as the most significant or least significant is a
parameter of CRC algorithms.
POLY - This is my friendly term for the polynomial of a CRC.
POLYNOMIAL - The "polynomial" of a CRC algorithm is simply the divisor
in the division implementing the CRC algorithm.
REFLECT - A binary number is reflected by swapping all of its bits
around the central point. For example, 1101 is the reflection of 1011.
ROCKSOFT^TM MODEL CRC ALGORITHM - A parameterized algorithm whose
purpose is to act as a solid reference for describing CRC algorithms.
Typically CRC algorithms are specified by quoting a polynomial.
However, in order to construct a precise implementation, one also
needs to know initialization values and so on.
WIDTH - The width of a CRC algorithm is the width of its polynomical
minus one. For example, if the polynomial is 11010, the width would be
4 bits. The width is usually set to be a multiple of 8 bits.
B. References
-------------
[Griffiths87] Griffiths, G., Carlyle Stones, G., "The Tea-Leaf Reader
Algorithm: An Efficient Implementation of CRC-16 and CRC-32",
Communications of the ACM, 30(7), pp.617-620. Comment: This paper
describes a high-speed table-driven implementation of CRC algorithms.
The technique seems to be a touch messy, and is superceded by the
Sarwete algorithm.
[Knuth81] Knuth, D.E., "The Art of Computer Programming", Volume 2:
Seminumerical Algorithms, Section 4.6.
[Nelson 91] Nelson, M., "The Data Compression Book", M&T Books, (501
Galveston Drive, Redwood City, CA 94063), 1991, ISBN: 1-55851-214-4.
Comment: If you want to see a real implementation of a real 32-bit
checksum algorithm, look on pages 440, and 446-448.
[Sarwate88] Sarwate, D.V., "Computation of Cyclic Redundancy Checks
via Table Look-Up", Communications of the ACM, 31(8), pp.1008-1013.
Comment: This paper describes a high-speed table-driven implementation
for CRC algorithms that is superior to the tea-leaf algorithm.
Although this paper describes the technique used by most modern CRC
implementations, I found the appendix of this paper (where all the
good stuff is) difficult to understand.
[Tanenbaum81] Tanenbaum, A.S., "Computer Networks", Prentice Hall,
1981, ISBN: 0-13-164699-0. Comment: Section 3.5.3 on pages 128 to 132
provides a very clear description of CRC codes. However, it does not
describe table-driven implementation techniques.
C. References I Have Detected But Haven't Yet Sighted
-----------------------------------------------------
Boudreau, Steen, "Cyclic Redundancy Checking by Program," AFIPS
Proceedings, Vol. 39, 1971.
Davies, Barber, "Computer Networks and Their Protocols," J. Wiley &
Sons, 1979.
Higginson, Kirstein, "On the Computation of Cyclic Redundancy Checks
by Program," The Computer Journal (British), Vol. 16, No. 1, Feb 1973.

McNamara, J. E., "Technical Aspects of Data Communication," 2nd
Edition, Digital Press, Bedford, Massachusetts, 1982.
Marton and Frambs, "A Cyclic Redundancy Checking (CRC) Algorithm,"
Honeywell Computer Journal, Vol. 5, No. 3, 1971.
Nelson M., "File verification using CRC", Dr Dobbs Journal, May 1992,
pp.64-67.
Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE
Micro, Aug 1988.
Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal,
pp.118-133.
Ward R.K, Tabandeh M., "Error Correction and Detection, A Geometric
Approach" The Computer Journal, Vol. 27, No. 3, 1984, pp.246-253.
Wecker, S., "A Table-Lookup Algorithm for Software Computation of
Cyclic Redundancy Check (CRC)," Digital Equipment Corporation
memorandum, 1974.
***** The END ******

--
┌───────────────────────────────────┐
│　Ｃ = Ｗ·㏒﹝1﹢ＳＮＲ﹞　　　　　　▁▄▇█▇▄▁　　　　　　　　　│
│　﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋﹋      　　▅███████▅　　　　　　　　│
│　噪声不是我的错　:)　　　　　　▃███████████▃　　　　　　│
│　﹌﹌﹌﹌﹌﹌﹌﹌﹌  　　　▂▇█████████████▇▂　　　　│
│▁▁▁▁▁▁▁▂▂▂▃▃▅▇█████████████████▇▄▃▂│

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: sillystone.bbs@smth.]