A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
"Everything you wanted to know about CRC algorithms, but were afraid
to ask for fear that errors in your understanding might be detected."
Version : 3.
Date : 19 August 1993.
Author : Ross N. Williams.
Net : firstname.lastname@example.org.
FTP : ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
Company : Rocksoft^tm Pty Ltd.
Snail : 16 Lerwick Avenue, Hazelwood Park 5066, Australia.
Fax : +61 8 373-4911 (c/- Internode Systems Pty Ltd).
Phone : +61 8 379-9217 (10am to 10pm Adelaide Australia time).
Note : "Rocksoft" is a trademark of Rocksoft Pty Ltd, Australia.
Status : Copyright (C) Ross Williams, 1993. However, permission is
granted to make and distribute verbatim copies of this
document provided that this information block and copyright
notice is included. Also, the C code modules included
in this document are fully public domain.
Thanks : Thanks to Jean-loup Gailly (email@example.com) and Mark Adler
(firstname.lastname@example.org) who both proof read this document
and picked out lots of nits as well as some big fat bugs.
Table of Contents
1. Introduction: Error Detection
2. The Need For Complexity
3. The Basic Idea Behind CRC Algorithms
4. Polynomical Arithmetic
5. Binary Arithmetic with No Carries
6. A Fully Worked Example
7. Choosing A Poly
8. A Straightforward CRC Implementation
9. A Table-Driven Implementation
10. A Slightly Mangled Table-Driven Implementation
11. "Reflected" Table-Driven Implementations
12. "Reversed" Polys
13. Initial and Final Values
14. Defining Algorithms Absolutely
15. A Parameterized Model For CRC Algorithms
16. A Catalog of Parameter Sets for Standards
17. An Implementation of the Model Algorithm
18. Roll Your Own Table-Driven Implementation
19. Generating A Lookup Table
C. References I Have Detected But Haven't Yet Sighted
This document explains CRCs (Cyclic Redundancy Codes) and their
table-driven implementations in full, precise detail. Much of the
literature on CRCs, and in particular on their table-driven
implementations, is a little obscure (or at least seems so to me).
This document is an attempt to provide a clear and simple no-nonsense
explanation of CRCs and to absolutely nail down every detail of the
operation of their high-speed implementations. In addition to this,
this document presents a parameterized model CRC algorithm called the
"Rocksoft^tm Model CRC Algorithm". The model algorithm can be
parameterized to behave like most of the CRC implementations around,
and so acts as a good reference for describing particular algorithms.
A low-speed implementation of the model CRC algorithm is provided in
the C programming language. Lastly there is a section giving two forms
of high-speed table driven implementations, and providing a program
that generates CRC lookup tables.
(*** download for full text ***)