Williams R.N. A Painless Guide to CRC Error Detection Algorithms

Подождите немного. Документ загружается.

CRC: A Paper On CRCs

This CRC web was created because of the popularity of a paper on CRC algorithms written by Ross

Williams and posted to some Internet newsgroups on 19 August 1993. This paper is available by FTP as a

pure text file. It can also be browsed directly on the web:

ftp://ftp.rocksoft.com/papers/crc_v3.txt.●

http://www.repairfaq.org/filipg/LINK/F_crc_v3.html.●

Here is the title and abstract of the paper:

A Painless Guide to CRC Error Detection Algorithms

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. 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.

Webmaster: ross@ross.net

Linktome: Click here to find out how to link your pages to this web.

CRC: A Paper On CRCs

http://www.ross.net/crc/crcpaper.html [07.06.2001 12:58:03]

A PAINLESS GUIDE TO CRC ERROR

DETECTION ALGORITHMS INDEX V3.00

(9/24/96)

Contents:

Table of Contents●

1. Preface●

1.1) About the Author & Copyright●

1.2) Abstract●

2. Introduction: Error Detection●

3. The Need For Complexity●

4. The Basic Idea Behind CRC Algorithms●

5. Polynomical Arithmetic●

Chapter 6) Binary Arithmetic with No Carries●

Chapter 7) A Fully Worked Example●

Chapter 8) Choosing A Poly●

Chapter 9) A Straightforward CRC Implementation●

Chapter 10) A Table-Driven Implementation●

Chapter 11) A Slightly Mangled Table-Driven Implementation●

Chapter 12) "Reflected" Table-Driven Implementations●

Chapter 13) "Reversed" Polys●

Chapter 14) Initial and Final Values●

Chapter 15) Defining Algorithms Absolutely●

Chapter 16) A Parameterized Model For CRC Algorithms●

Chapter 17) A Catalog of Parameter Sets for Standards●

Chapter 18) An Implementation of the Model Algorithm●

Chapter 19) Roll Your Own Table-Driven Implementation●

Chapter 20) Generating A Lookup Table●

Chapter 21) Summary●

Chapter 22) Corrections●

Chapter 23) Glossary●

Chapter 24) References●

Fil's FAQ-Link-In Corner: CRC algorithms

http://www.repairfaq.org/filipg/LINK/F_crc_v3.html (1 of 2) [07.06.2001 12:58:52]

Chapter 25) References I Have Detected But Haven't Yet Sighted●

Please check attribution section for Author of this document! This article was written by

filipg@repairfaq.org

[mailto]. The most recent version is available on the WWW

server http://www.repairfaq.org/filipg/ [Copyright] [Disclaimer]

Fil's FAQ-Link-In Corner: CRC algorithms

http://www.repairfaq.org/filipg/LINK/F_crc_v3.html (2 of 2) [07.06.2001 12:58:52]

[Feedback Form]

Fil's FAQ-Link-In Corner

When I need to reference some other FAQ, instead of plagerizing the section(s) I need, I just convert

those FAQs to HTML (I have lots of scripts that automate this), put them here, and inter-link freely.

NEW!: To see what changed since last release, please see the CHANGE-LOG V1.00 (5/2/97) (0KB)

Contents:

1. In general (and specific)●

2. Repair●

3. PC/Mac Hardware Interfacing/Info (and Projects)●

4. Protocols/Standards/Guides●

5. Embedded Matters (Processor & LCD FAQs)●

6. GIICM (TTL IC pinouts), NTE cross-reference, ChipDir●

7. References/FAQs●

8. Home Made (and Projects)●

9. Radio/Ham●

10. Decoding●

11. Interfacing (and Projects)●

12. Software (and Manuals)●

13. Geek Life Aids●

[Document Version: 3.09] [Last Updated: 10/21/97]

Unless otherwise marked, files are on local machine (Texas, USA)1.

Entries marked with "(R)" are on Remote sites.2.

1. In general (and specific)

Sci.Electronics FAQ (TLJVERERR) (May_28_1998!) (0KB)●

Digital Scope FAQ V1.00 (Dec_16_1995) (0KB)●

Fil's FAQ-Link-In Corner: Main Index

http://www.repairfaq.org/filipg/LINK/F_LINK_IN.html (1 of 7) [07.06.2001 13:00:06]

2. Repair

Appliance/Electronics Repair Notes & Guides (TLJVERERR) (May_28_1998!) (0KB)●

3. PC/Mac Hardware Interfacing/Info (and

Projects)

comp.sys.ibm.pc.hardware.* FAQ in HTML! (TLJVERERR) (Sub-ToC) | PC Hardware FAQ

(R-USA)

●

Aad Offerman's CHIPLIST in HTML (detailed info on PC CPUs V8.00 (R-Netherlands)●

PC/Mac [parallel/game/serial/keyboard] Port info V1.58 (10/20/97) (Sub-ToC)●

IDE (ATA) Specifications V1.00 (9/11/96) (0KB)●

http://thef-nym.sci.kun.nl/~pieterh/storage.html - Peter den Haan's storage page, you MUST see it!

(R)

●

http://theref.c3d.rl.af.mil/ - TheRef (tm) Drive and Controller Guide (R)●

Chris Dodge's 'PC IR Remote Control' (project) (R)●

Bjorn Gahm's General Remote Control Program (rem34bg) (R)●

David Lee Negro's IR Control Page (R)●

Cheap 8-bit ADC for IBM PC V1.00 (Dec_12_1991) (0KB)●

4. Protocols/Standards/Guides

DTMF FAQ V1.07 (9/16/96) (0KB)●

CallerID FAQ (21KB) V1.03 (10/7/97) (0KB)●

comp.periph.scsi (SCSI) FAQ V3.00 (May_15_1995) (Sub-ToC)●

PDF Sample SCSI specifications for UMAX scanners (0KB) or the PS.gz version (0KB) (both

from UMAX's BBS)

●

S.M.P.T.E. Code FAQ V1.00 (Oct_09_1995) (0KB)●

A Painless Guide to CRC Error Detection Algorithms V3.00 (9/24/96) (Sub-ToC)●

Examples of CRC algorithm for uPs V1.00 (1/2/97) (0KB)●

Fil's FAQ-Link-In Corner: Main Index

http://www.repairfaq.org/filipg/LINK/F_LINK_IN.html (2 of 7) [07.06.2001 13:00:06]

+ MIDI FAQ V1.00 (3/5/94) (0KB) A list of articles about MIDI projects MIDI Home Page, The

MIDI Farm Internet (must see!), MIDI links (20 pages of them!), and MIDI for the IBM PC V1.00

(Jan_1991) (0KB)

●

MNP Error-Correcting Modems (6KB)●

Info about Archivers/Compressors/Squeezers V2.00 (Mar_20_1994) (0KB)●

5. Embedded Matters (Processor & LCD

FAQs)

Your quest is not complete if you don't check the Comp.Robotics FAQ (R) (HUGE)●

Processor [68hc11/PIC/8051/ST6/COP8/CPM] FAQs V2.00 (1/24/97) (Sub-ToC)●

I2C FAQ V1.6 (06/08/95) (Sub-ToC)●

+ LCD [pinout/programming/theory/tech] FAQs V4.00 (9/23/97) (Sub-ToC)●

6. GIICM (TTL IC pinouts), NTE

cross-reference, ChipDir

SEARCH the GIICM●

NTE IC Cross-reference (Courtesy NTE)●

Frank Falstaff's version of the GIICM (re-organized) (R)●

Paul's IC Pinout Index (R)●

GIICM in raw form●

Please choose the ChipDir 'closest' to you:

Australia

Brisbane■

❍

Europe

Germany

Karlsruhe■

■

Italy

Napels■

Sardinie■

■

❍

●

Fil's FAQ-Link-In Corner: Main Index

http://www.repairfaq.org/filipg/LINK/F_LINK_IN.html (3 of 7) [07.06.2001 13:00:06]

Udine■

Netherlands, the

Amsterdam■

Twente■

■

Portugal

Lissabon (New)■

■

Romania

Timisoara (New)■

■

North America

California■

Pennsylvania (New)■

Seattle■

❍

South America

Brazil■

❍

7. References/FAQs

Electronics Mail Order List V2.18 (9/15/96) (Sub-ToC)●

Official rec.crafts.metalworking FAQ (R-USA) | The Metal Web News Page (R-USA)●

Robotics FAQ link (R-USA) | Robotics Internet Resources Pag (R-USA)●

Alan Triggs' Touch Screen FAQ V2.06 (3/19/97) (0KB)●

Uninterruptable Power Source (UPS) FAQ | latest version link (R-USA)●

How to Buy and Sell on the Internet FAQ (R-USA)●

Link to hotlist of anonymous FTP sites: (R-USA)●

CPM (of Z80 fame) FAQ V2.00 (4/14/95) (0KB)●

Link to other FAQs (100+) (R-USA)●

Fil's FAQ-Link-In Corner: Main Index

http://www.repairfaq.org/filipg/LINK/F_LINK_IN.html (4 of 7) [07.06.2001 13:00:06]

8. Home Made (and Projects)

alt.comp.hardware.homebuilt FAQ (22KB)●

Control of Stepping Motors, a Tutorial (R) | More Stepper Motor Links... (R)●

Jamie Heilman's Musical Electronics Microarchive MUST SEE! (R-USA)●

Home-made PAL/GAL Programmers FAQ V2.00 (May_6_1994) (0KB)●

Magnetic Card Reader Info V1.10 (3/26/94) (0KB)●

Quiz Show Lights (Jeopardy Game Show like Circuit) V1.00 (0KB)●

Project for LM3909 (0KB)●

9. Radio/Ham

Mycal's Micro Radio Page (Author of FM-10 FAQ) (R)●

Low Power FM Broadcasting Hobby (Some more do-it-yourself)●

FM-10 (stereo radio transmitter) FAQ V10.2 (0KB)●

Low Power FM Broadcasting (some low-power transmitter plans) (R)●

FC's Electronic Circuits - some nice add-ons for the FM-10 (R)●

FM-10 kits (additional info) V1.01 (0KB)●

100 Years of RADIO - Guglielmo Marconi's Home page! (R)●

FCC Part 15 Rules FAQ - Read the fine-print (and weep)... (0KB)●

YAGI-UDA antenna build one! (0KB)●

HUGE ham-radio FTP archive, lots of stuff (ex. "Newcomer to HAM?" 9KB)●

PostScript Smith Chart (RF) (0KB)●

Smith Chart Software (DOS) (0KB) (README)●

Fil's FAQ-Link-In Corner: Main Index

http://www.repairfaq.org/filipg/LINK/F_LINK_IN.html (5 of 7) [07.06.2001 13:00:06]

10. Decoding

VideoCrypt Info (R-GERMANY) and Archive (R-GERMANY)●

MacroVision FAQ (now with GIF schematics + MORE!) V1.2 (Sub-ToC)●

11. Interfacing (and Projects)

CasioBOSS Interface Kit (0KB) (About)●

PostScript CasioBOSS Interface Schematic (MAXIM233) (0KB)●

Info on CasioBOSS Mailing List (0KB)●

Victor Wiewiorowski's CasioBOSS Interfacing Page (R-CANADA)●

Gareth Blades Casio Interfacing Page (R-UK)●

How to convert PCjr color monitor to CGA V1.00 (0KB)●

Tons of stuff on marine, GPS, and NMEA topics by Peter Bennett (R-CANADA)●

12. Software (and Manuals)

PADS PCB Manual V2.xx (0KB)●

PADS-LOGIC Version 2.X enhancements and advisories V2.xx (0KB)●

13. Geek Life Aids

How to meet women (15KB)●

What women say and what they REALLY mean V1.04 (0KB)●

Wimp vs Sensitive Guy Test (0KB)●

Dating article for shy men (by Brad Isaac) V1.00 (0KB)●

REC.RUNNING FAQ (Sub-ToC) V2.00 | The Running Page (R-USA) |●

If you're actually having fun on this page, you'll like this too! (R)●

This article was written by filipg@repairfaq.org [mailto]. The most recent version is

Fil's FAQ-Link-In Corner: Main Index

http://www.repairfaq.org/filipg/LINK/F_LINK_IN.html (6 of 7) [07.06.2001 13:00:06]

[Feedback Form]

available on the WWW server http://www.repairfaq.org/filipg/ [Copyright] [Disclaimer]

Fil's FAQ-Link-In Corner: Main Index

http://www.repairfaq.org/filipg/LINK/F_LINK_IN.html (7 of 7) [07.06.2001 13:00:06]