Chip123 科技應用創新平台

 找回密碼
 申請會員

QQ登錄

只需一步,快速開始

Login

用FB帳號登入

搜索
1 2 3 4
查看: 8123|回復: 2
打印 上一主題 下一主題

[問題求助] 关于循环冗余校验CRC

[複製鏈接]
跳轉到指定樓層
1#
發表於 2007-6-17 01:10:56 | 只看該作者 回帖獎勵 |倒序瀏覽 |閱讀模式
CRC(Cyclic redundancy check)也就是循环冗余校验,是一种检验错误的方法,尤其在数据传输的时候,在发送端和接收端用同样的方法得到一个数字,然后接受端用该值和接收到的校验和进行比较。如果相同,则表示传送无误,可以处理数据。否则就是传送失败,并采取相应措施。) D% }+ v. g9 D6 f: C  h

" t) w: s  M- F& t1 p9 E我一直以为CRC就是简单的用相加的方法得到一个校验和(checksum),就像我们原来计算BIOS的校验和一样。crc8就是把所有的字节相加,得到一个8位的结果,crc16就是把所有的short相加,得到一个16位的结果,crc32就是把所有的整数相加,……以此类推。
0 `& M0 @- z% ^( f; {
4 _. T2 a5 H8 x; F( ?* Q' J2 [0 I但是,直到我真正开始做这个,才发现根本没有这么简单。这只是最基本的做法,虽然广泛使用(比如tcp标准校验和采用的就是该方法),但是却有着其本身不可克服的局限性。比如在传输数据时,如果数据本身和校验和都产生一位错误,就极有可能导致接受端发出错误的判断。所以crc才有很多变种,而且其最基本的数学原理也不是加法,而是除法,而且是多项式除法并取余。也就是用精心挑选的除数去除原数据,剩下的N位余数就是crc的结果。. l2 _. n% t2 T7 W1 D/ g; D4 j  B" M9 e

+ j; m! z7 k$ W4 t* Qcrc也不是以字节或整数为操作单位的,而是以比特为单位,只是人们为了简化运算,才有了以字节为单位的运算,才有了XOR,而非DIV的做法。而且为了对每一个原数据的位进行操作,才有了我们今天的查表法,也就是根据当前已得到的crc值和新输入的字节,产生一个索引,从表中查出相应数据,再和变化过的crc值进行异或,产生新的crc值。如此循环,直至所有的输入字节都处理完毕。; \/ N  L8 i# O4 V& G% F

* R* U0 o& |, z6 g9 D& C2 ^9 Lcrc虽然广泛用于全球标准化通讯系统中,但是并没有真正被标准化。大部分目前使用的crc都根据其长度和结构有着或多或少的弱点。现在主要用到的crc16采用的是CCITT的标准,而crc32用的是IEEE 802.3的标准。另外alder算法也非常流行,有兴趣的可以参考维基的英文网页,以crc为关键字查询,将得到非常详细的答案和参考书目。8 q  ?. f! i9 x6 B! s& i$ n9 k
- O" M1 M- f" Y6 `* l# R) A3 ^- {
因为crc是一个线形运算,所以易于破解,很难用于数据保护。一个比crc更有效地保护数据的方法就是one-way hash算法,也就是根据输入数据做运算,最后产生一段固定的输出。而其过程是非逆的。也就是说,你可以根据该算法轻易地得到输出,却几乎不可能根据输出来推断你的输入。比较流行的hash算法有MD5和SHA1以及SHA的各种变形。但随着技术的日新月异,MD5已经被证明不够安全,SHA1也被中国的教授发现了其弱对撞性。看来安全的路未来还很长。

評分

參與人數 1 +5 收起 理由
masonchung + 5 你的經驗就是知識的來源!

查看全部評分

分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏 分享分享 頂 踩 分享分享
2#
發表於 2007-6-17 15:45:44 | 只看該作者

A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS

不知這個錯誤偵測的方法如何~:o - r5 ]2 \: b2 e8 J6 R
Table of Contents * j5 f5 u& V% r* @% P, P, L
1. Preface
$ S7 v/ A8 N2 C' x8 n) E; `1 [  1.1) About the Author & Copyright   Q+ B0 {. U/ Z4 s5 q' ]. l
  1.2) Abstract
8 Z9 [1 H) K% N+ ]2. Introduction: Error Detection
( R% ~, A* ?: u: g; g3. The Need For Complexity 8 B: u( L) e4 q+ r# e
4. The Basic Idea Behind CRC Algorithms / F+ i6 |3 N  i
5. Polynomical Arithmetic + }. Y4 G, ^2 X, _% s, J
Chapter 6) Binary Arithmetic with No Carries 4 ?) m6 q% a% j0 M5 C) X8 D  G
Chapter 7) A Fully Worked Example # P& g2 ^. W/ `, m+ g
Chapter 8) Choosing A Poly & M+ O  c  J! J3 B# i0 r& T8 F' q" P1 S
Chapter 9) A Straightforward CRC Implementation * M7 l0 \+ X" a+ [4 [
Chapter 10) A Table-Driven Implementation
6 v& I0 a5 d$ W9 z6 bChapter 11) A Slightly Mangled Table-Driven Implementation 1 X3 I! d- A" ?% F  [
Chapter 12) "Reflected" Table-Driven Implementations 7 f9 s% \5 z1 M) S2 O5 D
Chapter 13) "Reversed" Polys
/ }& L# K; \: l* X+ LChapter 14) Initial and Final Values " d# f# H+ Z0 u% C% e9 _* p3 C
Chapter 15) Defining Algorithms Absolutely
0 z" @  o. e: R0 F7 p; iChapter 16) A Parameterized Model For CRC Algorithms 6 Z! \. X$ l; O( g; Q* t
Chapter 17) A Catalog of Parameter Sets for Standards
, W9 N( {4 e7 h2 M2 T' vChapter 18) An Implementation of the Model Algorithm
: ^5 i- q. c  Z' _  W# O1 RChapter 19) Roll Your Own Table-Driven Implementation * C6 e* b) H. o- ^
Chapter 20) Generating A Lookup Table
6 N* a5 B  L; D: MChapter 21) Summary 6 n1 l4 Y* K8 F: Q2 @5 k
Chapter 22) Corrections
! `9 w( t0 t0 N5 V2 [: J6 b( h3 w3 BChapter 23) Glossary 3 {1 J1 `- g% B  s/ {
Chapter 24) References
/ h) R4 q3 j5 J8 I, j' yChapter 25) References I Have Detected But Haven't Yet Sighted
* F* G# Z( N+ T! j/ G* \$ s9 d2 _9 E" j. m- A
http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
3#
 樓主| 發表於 2007-6-18 19:32:13 | 只看該作者
哎呀,太复杂了,不过原理应该是一样的。我这里有一个不错的文档,让我试试看上传
您需要登錄後才可以回帖 登錄 | 申請會員

本版積分規則

首頁|手機版|Chip123 科技應用創新平台 |新契機國際商機整合股份有限公司

GMT+8, 2025-4-3 05:04 PM , Processed in 0.175010 second(s), 18 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回復 返回頂部 返回列表