A_PAINLESS_GUIDE_TO_CRC_ERROR_DETECTION_ALGORITHMS资源-CSDN文库

5星 · 超过95%的资源需积分: 15 93 浏览量 2014-10-14 23:03:47 上传评论 5 收藏 322KB PDF 举报

《A Painless Guide to CRC Error Detection Algorithms》是一份国外的经典资料，由Ross N. Williams所著，详细介绍了循环冗余校验（Cyclic Redundancy Check，简称CRC）算法及其基于表驱动的实现方式。本书于1993年首次发布，之后不断更新，最新版为3.00版，于1996年9月24日更新。作者的电子邮箱为***.au，同时提供了一个FTP地址***.au/pub/rocksoft/crc_v3.txt供读者下载该文档。文档还提供了一个WWW网址***，从中可以了解更多有关Rocksoft公司的信息。该公司是澳大利亚的一家私人公司，作者对其享有版权，并且允许无条件复制和分发文档副本，前提是必须包含版权声明。文档中还包含了C语言的代码模块，并将其完全置于公有领域（Public Domain，简称PD）。本书的目的在于清晰、细致地解释CRC算法及其实现，并且深入探讨了其高速实现的每一个细节。为了提供关于特定算法的参考，作者提供了一个名为“Rocksoft™ Model CRC Algorithm”的参数化模型CRC算法。该模型算法可以参数化配置以适应大多数CRC实现，因此可以作为描述特定算法的良好参考。文档还给出了模型CRC算法的一个低速实现版本，用C语言编写。此外，文档的另一部分介绍了两种高速表驱动实现方法，并提供了一个示例程序。 CRC算法是一种用于检测数据传输或存储后可能出现的错误的校验方法，其核心思想是通过一种算术运算来产生一个短小的校验值（也称为校验和或者CRC码），然后将这个校验值附加到数据中一起传输或存储。在接收端，接收方可以通过同样的运算来验证数据是否在传输或存储过程中产生了错误。CRC算法的优点是能够检测出包括单个错位、多个错位、奇偶位数错误等多种常见的错误类型。 CRC算法广泛应用于网络通信、数据存储等场景中。在不同的应用中，CRC算法根据其生成多项式、数据长度和位宽等因素的不同可以有许多变种。常见的CRC算法有CRC16、CRC32等，它们对应不同的校验位数和生成多项式。例如，CRC32算法使用的生成多项式为32位，计算得到的CRC码也是32位长度，它可以检测出更多的错误模式。本书通过详细的解释和实例代码，为读者提供了一个理解CRC算法的良好途径。通过对Rocksoft™ Model CRC Algorithm的详细探讨，读者可以加深对CRC算法内在原理的理解，并且能够了解到如何将这些算法应用在实际的软件开发中。对于从事IT行业的专业人士，尤其是那些需要在他们的产品中实现数据校验功能的开发者来说，这本书无疑是一份宝贵的资料。通过学习本书，他们不仅能够掌握CRC算法的理论知识，还能学会如何有效地在软件中实现和优化CRC校验算法。

资源推荐

资源详情

资源评论

A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS

[Document Version: 3.00] [Last Updated: 9/24/96]

Chapter 1) Preface

1.1) About the Author & Copyright

"Everything you wanted to know about CRC algorithms, but were afraid

to ask for fear that errors in your understanding might be detected."

 Author : Ross N. Williams

 E-Mail : ross@guest.adelaide.edu.au

 Date : 19 August 1993

 Version : 3.00

 FTP: ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt

 WWW: http://www.on.net/clients/rocksoft/rocksoft/

 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,1994,1995,1996.

However, permission is granted to make and distribute verbatim

copies of this document provided that this information block and

in this document are fully PUBLIC DOMAIN (PD).

 Thanks: Thanks to Jean-loup Gailly (jloup@chorus.fr) and Mark

Adler (me@quest.jpl.nasa.gov) who both proof read this document

and picked out lots of nits as well as some big fat bugs.

C sources to are referenced in this document:

 crcmodel.h (0KB)

 crcmodel.c (0KB)

 crctable.c (0KB)

1.2) Abstract

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.

Chapter 2) Introduction: Error Detection

The aim of an error detection technique is to enable the receiver of

a message transmitted through a noisy (error-introducing) channel to

determine whether the message has been corrupted. To do this, the

transmitter constructs a value (called a checksum) that is a function

of the message, and appends it to the message. The receiver can then

use the same function to calculate the checksum of the received message

and compare it with the appended checksum to see if the message was

correctly received. For example, if we chose a checksum function which

was simply the sum of the bytes in the message mod 256 (i.e. modulo

256), then it might go something as follows. All numbers are in decimal.

Message : 6 23 4

Message with checksum : 6 23 4 33

Message after transmission : 6 27 4 33

In the above, the second byte of the message was corrupted from 23

to 27 by the communications channel. However, the receiver can detect

this by comparing the transmitted checksum (33) with the computer

checksum of 37 (6 + 27 + 4). If the checksum itself is corrupted, a

correctly transmitted message might be incorrectly identified as a

corrupted one. However, this is a safe-side failure. A dangerous-side

failure occurs where the message and/or checksum is corrupted in a

manner that results in a transmission that is internally consistent.

Unfortunately, this possibility is completely unavoidable and the best

that can be done is to minimize its probability by increasing the amount

of information in the checksum (e.g. widening the checksum from one

byte to two bytes).

A register width wide enough to provide a low a-priori probability

of failure (e.g. 32-bits gives a 1/2^32 chance of failure).

CHAOS

A formula that gives each input byte the potential to change any

number of bits in the register.

Note: The term "checksum" was presumably used to describe early summing

formulas, but has now taken on a more general meaning encompassing

more sophisticated algorithms such as the CRC ones. The CRC algorithms

to be described satisfy the second condition very well, and can be

configured to operate with a variety of checksum widths.

Chapter 4) The Basic Idea Behind CRC Algorithms

Where might we go in our search for a more complex function than summing?

All sorts of schemes spring to mind. We could construct tables using

the digits of pi, or hash each incoming byte with all the bytes in

the register. We could even keep a large telephone book on-line, and

use each incoming byte combined with the register bytes to index a

new phone number which would be the next register value. The

possibilities are limitless.

However, we do not need to go so far; the next arithmetic step suffices.

While addition is clearly not strong enough to form an effective

checksum, it turns out that division is, so long as the divisor is

about as wide as the checksum register.

The basic idea of CRC algorithms is simply to treat the message as

an enormous binary number, to divide it by another fixed binary number,

and to make the remainder from this division the checksum. Upon receipt

of the message, the receiver can perform the same division and compare

the remainder with the "checksum" (transmitted remainder).

Example: Suppose the the message consisted of the two bytes (6,23)

as in the previous example. These can be considered to be the

hexadecimal number 0617 which can be considered to be the binary number

0000-0110-0001-0111. Suppose that we use a checksum register one-byte

wide and use a constant divisor of 1001, then the checksum is the

remainder after 0000-0110-0001-0111 is divided by 1001. While in this

case, this calculation could obviously be performed using common garden

variety 32-bit registers, in the general case this is messy. So instead,

we'll do the division using good-'ol long division which you learned

in school (remember?). Except this time, it's in binary:

剩余36页未读，继续阅读

评论收藏

内容反馈

zzia_cy

2016-05-16

非常好，读完之后，终于理解了crc，学习crc，这一个资料就够了
渣渣黑

2017-10-12

非常好的资料
tqxxzy

2019-05-28

可以看下，还行！
qianyinggaozhong

2016-07-26

非常的好，很有借鉴意义！
mavels

2016-06-17

不容易看懂，直接看后面的实现方法写代码就好了。

前往

页

fandelxin

粉丝: 240
资源: 28

A_PAINLESS_GUIDE_TO_CRC_ERROR_DETECTION_ALGORITHMS

A-PAINLESS-GUIDE-TO-CRC-ERROR-DETECTION-ALGORITHMS

A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS

CRC算法 A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS

CRC-error-detection.zip_algorithms_crc

循环冗余校验(CRC)算法入门引导.pdf

crc_model.zip_algorithms

painless_vim.pdf

painless_git.pdf

Code for a painless q-learning tutorial

A Painless introduction to monads

CRC校验算法

Elasticsearch Painless Script入门教程--示例数据-sat.json

两篇CRC导论及源代码实现

elasticsearch对painless脚本的常用操作api实例

Painless Docker Basic Edition

painless_logger

random_walk.zip_Q learning_Q-learning_Q-learning、_Q算法_random wal

painless-conjugate-gradient

groovy脚本转painless语法总结

React Quickly Painless web apps with React, JSX, Redux, and GraphQL-原书代码

Mastering ROS for Robotics Programming - Second Edition[www.rejoiceblog.com].pdf

painless:无痛参数处理，易于探索

CSS Mastery(Apress,3ed,2016)

ABAP Logging as painless as any other language.zip

Learning Windows 8 Game Development

Java Programming 24-Hour Trainer(Wrox,2ed,2015)

Apache Maven Dependency Management

延时加载JS，解决JS阻塞问题

最新资源