城市軌道交通通信設(shè)備技術(shù)-循環(huán)冗余校驗(yàn)

CRC校驗(yàn)碼設(shè)計(jì)CRC產(chǎn)生背景在數(shù)字通信系統(tǒng)中可靠與快速往往是矛盾的。如何合理地解決可靠與速度這一對(duì)矛盾呢？

可靠性快速性可靠性快速性糾錯(cuò)碼：在每一個(gè)發(fā)送的數(shù)據(jù)塊中包含足夠的冗余信息，以便接收方可以推斷出被發(fā)送的數(shù)據(jù)中肯定有哪些內(nèi)容。檢錯(cuò)碼：包含一些冗余信息，但是這些信息只能讓接收方推斷出發(fā)生了錯(cuò)誤，但推斷不出發(fā)生了哪個(gè)錯(cuò)誤，然后接收方可以請(qǐng)求重傳。參考：《計(jì)算機(jī)網(wǎng)絡(luò)》中3.2節(jié)錯(cuò)誤檢測(cè)和糾正海明碼、CRC校驗(yàn)碼的區(qū)別在無線鏈路、光纖、銅線上應(yīng)用的區(qū)別checksum:3A0101FFF1002C

CRC產(chǎn)生背景多項(xiàng)式編碼特點(diǎn):檢錯(cuò)能力極強(qiáng)，開銷小，易于用編碼器及檢測(cè)電路實(shí)現(xiàn)。從其檢錯(cuò)能力來看，它所不能發(fā)現(xiàn)的錯(cuò)誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠(yuǎn)遠(yuǎn)優(yōu)于奇偶校驗(yàn)及算術(shù)和校驗(yàn)等方式。因而，在數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)通訊領(lǐng)域，CRC無處不在：著名的通訊協(xié)議X.25的FCS(幀檢錯(cuò)序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等壓縮工具軟件采用的是CRC32，磁盤驅(qū)動(dòng)器的讀寫采用了CRC16，通用的圖像存儲(chǔ)格式GIF、TIFF等也都用CRC作為檢錯(cuò)手段。多項(xiàng)式編碼多項(xiàng)式編碼（polynomialcode），也稱為CRC(cyclicredundancycheck，循環(huán)冗余校驗(yàn)碼)，多項(xiàng)式編碼的思想是：將位串看成是系數(shù)為0或1的多項(xiàng)式。CRC校驗(yàn)保護(hù)的單位是數(shù)據(jù)塊。數(shù)據(jù)塊的大小根據(jù)實(shí)際情況而定。每一個(gè)數(shù)據(jù)塊均被看作是一個(gè)二進(jìn)制多項(xiàng)式，即所有系數(shù)均為二進(jìn)制（即1或0）的多項(xiàng)式。當(dāng)使用多項(xiàng)式編碼時(shí)，發(fā)送方和接受方必須預(yù)先商定一個(gè)生成多項(xiàng)式（generatorpolynomial）G(x)。生成多項(xiàng)式的最高位和最低位必須為1。CRC應(yīng)用CRC的主要特點(diǎn)檢錯(cuò)能力極強(qiáng)開銷很小易于實(shí)現(xiàn)ARJ,LHA,ZIP等壓縮軟件采用的是CRC-32；GIF,TIFF等圖像存儲(chǔ)格式；所有鏈路層或網(wǎng)絡(luò)接口層協(xié)議中，例如HDLC、DDCMP等眾多領(lǐng)域。應(yīng)用范圍廣CRC原理將待發(fā)送的位串看成系數(shù)為0或1的多項(xiàng)式；收發(fā)雙方約定一個(gè)生成多項(xiàng)式G(x)（其最高階和最低階系數(shù)必須為1），發(fā)送方用位串及G(x)進(jìn)行某種運(yùn)算得到校驗(yàn)和，并在幀的末尾加上校驗(yàn)和，使帶校驗(yàn)和的幀的多項(xiàng)式能被G(x)整除;接收方收到后，用G(x)除多項(xiàng)式，若有余數(shù)，則傳輸有錯(cuò)。CRC校驗(yàn)和計(jì)算法1.若生成多項(xiàng)式G(x)為r階(即r＋1位位串)，原幀為m位，其多項(xiàng)式為M(x)，則在原幀后面添加r個(gè)0，即循環(huán)左移r位，幀成為m+r位，相應(yīng)多項(xiàng)式成為xrM(x);2.按模2除法用G(x)對(duì)應(yīng)的位串去除對(duì)應(yīng)于xrM(x)的位串,得余數(shù)R(x)；3.按模2減法(即模2加)從對(duì)應(yīng)于xrM(x)的位串中減去(加上)余數(shù)R(x),結(jié)果即傳送的帶校驗(yàn)和的幀多項(xiàng)式T(x)。

T(x)=xrM(x)+R(x)CRC驗(yàn)證發(fā)送方設(shè)xrM(x)除以G(x)的商和余數(shù)分別為Q(x)和R(x)。則有:xrM(x)=G(x)Q(x)+R(x)即：接收方收到帶CRC校驗(yàn)和的幀多項(xiàng)式T(x)=xrM(x)+R(x)。由于模2加減相當(dāng)于異或運(yùn)算,于是接收方模2除后商Q(x),余數(shù)0.得證！舉一個(gè)例子（1）發(fā)送數(shù)據(jù)110011；（2）生成多項(xiàng)式G(x)=x4+x3+1；（3）將要發(fā)送的數(shù)據(jù)系列左移4位，新的序列為1100110000；（4）按模2算法，將生成的新序列除以生成多項(xiàng)式序列；（5）將余數(shù)多項(xiàng)式比特序列加到新的序列中即得發(fā)送端傳送序列。下面。

10000111001

1100110000

11001

100001001

11001

1100111001接收方校驗(yàn)方案方案二：提取接收到序列的信息碼元，重復(fù)發(fā)送方的操作xrM(x)

，再除以生成多項(xiàng)式G(x),如果余數(shù)R’(x)=R(x),則證明傳輸正確。方案一：直接用接收到的序列除以生成多項(xiàng)式G(x),如果余數(shù)R’(x)=0,則證明傳輸正確。接收方校驗(yàn)方案生成多項(xiàng)式G(x)的國際標(biāo)準(zhǔn)CRC-12：x12+x11+x3+x2+x+1CRC-32：x32+x26+x23+x22+x16+x12CRC-8:x8+x2+x+1CRC-10:x10+x9+x5+x4+x2+1CRC-16：x16+x15+x2+1+x11+x10+x8+x7+x5+x4+x2+x+1CRC-CCITT：x16+x12+x5+1CRC校驗(yàn)碼設(shè)計(jì)差錯(cuò)檢測(cè)

循環(huán)冗余校驗(yàn)碼(CRC，CyclicRedundancycheck)編碼對(duì)于一個(gè)碼長為n，信息碼元為k位的循環(huán)碼(n，k),其構(gòu)成形式為：12knk+1k+2n位信息碼元k位校驗(yàn)碼元r位差錯(cuò)檢測(cè)

循環(huán)冗余校驗(yàn)碼(CRC，CyclicRedundancycheck)若生成多項(xiàng)式G(x)為r階(即r＋1位位串)，原幀為m位，其多項(xiàng)式為M(x)，則在原幀后面添加r個(gè)0，即循環(huán)左移r位，幀成為m+r位，相應(yīng)多項(xiàng)式成為xrM(x);按模2除法用G(x)對(duì)應(yīng)的位串去除對(duì)應(yīng)于xrM(x)的位串,得余數(shù)R(x)；按模2減法(即模2加)從對(duì)應(yīng)于xrM(x)的位串中減去(加上)余數(shù)R(x),結(jié)果即傳送的帶校驗(yàn)和的幀多項(xiàng)式T(x)。例m(x)=x9+x8+x6+x4+x3+x+1,k=10(3)1101011011.0000

10011(模二除)商數(shù)：1100001010

余數(shù)：1110

r(x)=x3+x2+x+0所需的循環(huán)編碼C(x)為C(x)=xn·m(x)+r(x)=

1101011011，1110設(shè)編碼的信息碼元為1101011011(1)假設(shè)G(x)=x4+x+1系數(shù)形成的位串為10011則將m(x)·x4余數(shù)取4位(2)x4·m(x)=1101011011，0000另一個(gè)例子多項(xiàng)式除法1101011011,0000100111001110011100111011010011101001001111101100001010商數(shù)被除數(shù)m(x)余數(shù)r(x)除數(shù)P(x)1101011011.0000

10011另一個(gè)例子模2運(yùn)算①模2加法運(yùn)算定義為：（對(duì)應(yīng)于邏輯異或）0＋0＝00＋1＝11＋0＝11＋1＝0例如0101＋0011＝0110，列豎式計(jì)算：0101＋0011──────0110異或計(jì)算為：1^1=00^0=01^0=10^1=1多項(xiàng)式的算術(shù)運(yùn)算采用代數(shù)域理論的規(guī)則，加法沒進(jìn)位，減法沒借位，加法和減法都等同于異或。模2運(yùn)算②模2減法運(yùn)算定義為：（對(duì)應(yīng)于邏輯異或）0－0＝00－1＝11－0＝11－1＝0例如0110－0011＝0101，列豎式計(jì)算：0110－0011──────0101異或計(jì)算為：1^1=00^0=01^0=10^1=1模2運(yùn)算③模2乘法運(yùn)算定義為：0×0＝00×1＝01×0＝01×1＝1例如1011×101＝100111，列豎式計(jì)算：1011×101──────10110000＋1011────────100111模2運(yùn)算④模2除法運(yùn)算定義為：0÷1＝01÷1＝1模二除法是利用模二減求余數(shù)的，余數(shù)最高位為“1”，則商“1”，否則商“0”，每商1位則余數(shù)減少一位，直到余數(shù)位數(shù)少于除數(shù)位數(shù)。1110────────1011〕1100100－1011──────1111－1011──────1000－1011──────0110－0000──────110位運(yùn)算按位與運(yùn)算按位與運(yùn)算符"&"是雙目運(yùn)算符。其功能是參與運(yùn)算的兩數(shù)各對(duì)應(yīng)的二進(jìn)位相與。只有對(duì)應(yīng)的兩個(gè)二進(jìn)位均為1時(shí)，結(jié)果位才為1，否則為0。參與運(yùn)算的數(shù)以補(bǔ)碼方式出現(xiàn)。例如：9&5可寫算式如下：00001001(9的二進(jìn)制補(bǔ)碼)&00000101(5的二進(jìn)制補(bǔ)碼)00000001可見9&5=1。按位或運(yùn)算按位或運(yùn)算符“|”是雙目運(yùn)算符。其功能是參與運(yùn)算的兩數(shù)各對(duì)應(yīng)的二進(jìn)位相或。只要對(duì)應(yīng)的二個(gè)二進(jìn)位有一個(gè)為1時(shí)，結(jié)果位就為1。參與運(yùn)算的兩個(gè)數(shù)均以補(bǔ)碼出現(xiàn)。例如：9|5可寫算式如下：00001001|0000010100001101(十進(jìn)制為13)可見9|5=13求反運(yùn)算符～為單目運(yùn)算符，具有右結(jié)合性。其功能是對(duì)參與運(yùn)算的數(shù)的各二進(jìn)位按位求反。例如～9的運(yùn)算為：位運(yùn)算按位異或運(yùn)算按位異或運(yùn)算符“^”是雙目運(yùn)算符。其功能是參與運(yùn)算的兩數(shù)各對(duì)應(yīng)的二進(jìn)位相異或，當(dāng)兩對(duì)應(yīng)的二進(jìn)位相異時(shí)，結(jié)果為1。參與運(yùn)算數(shù)仍以補(bǔ)碼出現(xiàn)，例如9^5可寫成算式如下：00001001^0000010100001100(十進(jìn)制為12)左移運(yùn)算左移運(yùn)算符“<<”是雙目運(yùn)算符。其功能把“<<”左邊的運(yùn)算數(shù)的各二進(jìn)位全部左移若干位，由“<<”右邊的數(shù)指定移動(dòng)的位數(shù)，高位丟棄，低位補(bǔ)0。例如：a<<4指把a(bǔ)的各二進(jìn)位向左移動(dòng)4位。如a=00000011(十進(jìn)制3)，左移4位后為00110000(十進(jìn)制48)。右移運(yùn)算右移運(yùn)算符“>>”是雙目運(yùn)算符。其功能是把“>>”左邊的運(yùn)算數(shù)的各二進(jìn)位全部右移若干位，“>>”右邊的數(shù)指定移動(dòng)的位數(shù)。例如：設(shè)a=15，a>>2表示把000001111右移為00000011(十進(jìn)制3)。CRC校驗(yàn)碼設(shè)計(jì)實(shí)驗(yàn)要求：(1)、完成基本CRC校驗(yàn)碼生成的功能；（位數(shù)不限）；(2)、嘗試完成CRC-16；CRC-16發(fā)送數(shù)據(jù)為:0X02生成多項(xiàng)式：0X18005余數(shù)為：0X800FMD5信息摘要算法介紹電子商務(wù)采取的主要安全保密措施，是最常用的安全保密手段，利用技術(shù)手段把重要的數(shù)據(jù)變?yōu)閬y碼（加密）傳送，到達(dá)目的地后再用相同或不同的手段還原（解密）。加密技術(shù)·概念加密技術(shù)·應(yīng)用廣泛應(yīng)用于電子商務(wù)和虛擬專用網(wǎng)絡(luò)上的應(yīng)用，深受廣大用戶的喜愛。消息摘要算法·特點(diǎn)加密過程不需要密鑰，加密后的數(shù)據(jù)無法被解密。只有輸入相同的明文數(shù)據(jù)經(jīng)過相同的消息摘要算法才能得到相同的密文。所以不存在密鑰的管理與分發(fā)問題。MD5·概念MessageDigestAlgorithmMD5（消息摘要算法第五版），它是一種消息摘要算法。為計(jì)算機(jī)安全領(lǐng)域廣泛使用的一種散列函數(shù)，用以提供消息的完整性保護(hù)。MD5的前身為MD2、MD3、MD4，可以說，MD5是MD4的升級(jí)版。MD5·效果把一個(gè)任意長度的字節(jié)串變換成一定長度的十六進(jìn)制數(shù)字串。目的是讓大容量信息在用數(shù)字簽名軟件簽署私人密鑰前被"壓縮"成一種保密的格式。MD5·應(yīng)用一致性驗(yàn)證：從網(wǎng)上下載文件，軟件，各種資料的時(shí)候，有些文件會(huì)提供MD5對(duì)照信息。利用MD5校驗(yàn)軟件來核對(duì)下載的文件，以此觀測(cè)下載得到的文件與傳送者是否相符。MD5·應(yīng)用一致性驗(yàn)證：利用MD5算法來進(jìn)行文件校驗(yàn)的方案被大量應(yīng)用到軟件下載站、論壇數(shù)據(jù)庫、系統(tǒng)文件安全等方面。MD5·應(yīng)用數(shù)字證書：對(duì)一段Message(字節(jié)串)產(chǎn)生fingerprint(指紋），以防止被“篡改”。例子：將一段話寫在一個(gè)叫readme.txt文件中，并對(duì)這個(gè)readme.txt產(chǎn)生一個(gè)MD5的值并記錄在案，然后你可以傳播這個(gè)文件給別人，別人如果修改了文件中的任何內(nèi)容，你對(duì)這個(gè)文件重新計(jì)算MD5時(shí)就會(huì)發(fā)現(xiàn)（兩個(gè)MD5值不相同）。如果再有一個(gè)第三方的認(rèn)證機(jī)構(gòu)，用MD5還可以防止文件作者的“抵賴”，這就是所謂的數(shù)字簽名應(yīng)用。MD5·應(yīng)用安全訪問認(rèn)證：用于操作系統(tǒng)的登陸認(rèn)證上。當(dāng)用戶登錄的時(shí)候，系統(tǒng)把用戶輸入的密碼進(jìn)行MD5Hash運(yùn)算，然后再去和保存在文件系統(tǒng)中的MD5值進(jìn)行比較，進(jìn)而確定輸入的密碼是否正確。通過這樣的步驟，系統(tǒng)在并不知道用戶密碼的明碼的情況下就可以確定用戶登錄系統(tǒng)的合法性。這可以避免用戶的密碼被具有系統(tǒng)管理員權(quán)限的用戶知道。MD5信息摘要算法介紹MD5·崩塌2004年8月17日的美國加州圣巴巴拉的國際密碼學(xué)會(huì)議上，來自中國山東大學(xué)的王小云教授做了破譯MD5、HAVAL-128、MD4和RIPEMD算法的報(bào)告，公布了MD系列算法的破解結(jié)果。宣告了固若金湯的世界通行密碼標(biāo)準(zhǔn)MD5的堡壘轟然倒塌，引發(fā)了密碼學(xué)界的軒然大波。MD5·崩塌由于這個(gè)里程碑式的發(fā)現(xiàn)，MD5CRK項(xiàng)目將在隨后48小時(shí)內(nèi)結(jié)束。MD5·評(píng)論那么，我干嘛還來講這個(gè)似乎已經(jīng)被KO掉的MD5呢？好吧，我們來理一理思路MD5·評(píng)論至于那個(gè)在數(shù)個(gè)小時(shí)內(nèi)就可以找到MD5碰撞的程序....就是你用一臺(tái)IBMP690，在數(shù)小時(shí)內(nèi)，創(chuàng)造出兩個(gè)MD5相同但內(nèi)容不同的東東來，有點(diǎn)意思吧~MD5·評(píng)論雖然，我們的王大神已經(jīng)做出了如此驚人的工作。但由于MD5算法的使用不需要支付任何版權(quán)費(fèi)用的，所以在一般的情況下（非絕密應(yīng)用領(lǐng)域）怎么都算得上是非常安全的了。即便是應(yīng)用在絕密領(lǐng)域內(nèi)，MD5也不失為一種非常優(yōu)秀的中間技術(shù)。檢錯(cuò)與糾錯(cuò)本章主要內(nèi)容

What’saboutThisChapter？

本章學(xué)習(xí)如何檢測(cè)和糾正數(shù)據(jù)傳輸中“位差錯(cuò)”。本章研究：“位差錯(cuò)”的概念和類型檢錯(cuò)技術(shù)基本原理三種常用的檢錯(cuò)技術(shù)奇偶校驗(yàn)技術(shù)循環(huán)冗余校驗(yàn)技術(shù)校驗(yàn)和技術(shù)漢明碼糾錯(cuò)技術(shù)本章僅講技術(shù)原理，數(shù)學(xué)細(xì)節(jié)留給大家自己去深入…本章主要內(nèi)容

Contents1差錯(cuò)類型

TypesofError

2差錯(cuò)檢測(cè)

ErrorDetection3差錯(cuò)糾正

ErrorDetection

概述

Overview傳輸中差錯(cuò)是不可避免的。