曹素華差錯(cuò)檢測與CRC

1、差 錯(cuò) 檢 測與CRC 校 驗(yàn)UMTS 工 作 組caosh8/11/20221內(nèi)容概要 差錯(cuò)類型(A) 檢測方式概述(B) CRC檢測原理(C) 伽羅域基本知識(C1) CRC編碼(C2)8/11/20222(A)差錯(cuò)類型8/11/20223(A)單個(gè)比特錯(cuò)誤定義：在給定數(shù)據(jù)單元只有一個(gè)bit發(fā)生改 變比如一個(gè)字節(jié)、一個(gè)字符、一個(gè)數(shù)據(jù)單元或者數(shù)據(jù)包例子：發(fā)送：0000 0010 (ASCII code:STX 正文開始)接收：0000 1010(ASCII code:LF 換行)發(fā) 送00000010接 收000010100 18/11/20224(A)多個(gè)比特錯(cuò)誤定義：在給定數(shù)據(jù)單元有兩個(gè)

2、或者多個(gè)不連續(xù)的bit發(fā)生改變發(fā) 送01000010接 收00001010兩個(gè)bit 錯(cuò)誤8/11/20225(A)突發(fā)錯(cuò)誤定義：在給定數(shù)據(jù)單元連續(xù)兩個(gè)或者更多個(gè)bit發(fā)生改變 所 發(fā) 送 的 數(shù) 據(jù)01000010010000100011111000001010 所 接 收 的 數(shù) 據(jù)8/11/20226 (B)檢測方式概述將每個(gè)數(shù)據(jù)塊單元發(fā)送兩次，進(jìn)行逐bit比較(效率、時(shí)間)加冗余bit數(shù)據(jù)通信中常用冗余的方法來解決通信的可靠性問題8/11/20227(B)冗余校驗(yàn)的分類垂直冗余校驗(yàn)(VRC)縱向冗余校驗(yàn)(LRC)循環(huán)冗余校驗(yàn)(CRC)檢驗(yàn)和8/11/20228(B)垂直冗余校驗(yàn)(VRC

3、)奇偶校驗(yàn)：在數(shù)據(jù)塊加冗余bit，以保證數(shù)據(jù)中“1”的個(gè)數(shù)為奇數(shù)或者偶數(shù)數(shù)據(jù)偶校驗(yàn)產(chǎn)生器11發(fā)送端校驗(yàn)函數(shù)接收端校驗(yàn)：1的總數(shù)為偶數(shù)？Y:AcceptN:Reject8/11/20229(B)縱向冗余校驗(yàn)(LRC)本質(zhì)：2D VRC目的：檢測多個(gè)差錯(cuò)bit和突發(fā)錯(cuò)誤方法：將確定數(shù)據(jù)分組，保證單個(gè)數(shù)據(jù)塊和數(shù)據(jù)塊的相應(yīng)bit都具有VRC校驗(yàn)數(shù) 據(jù) 移 動(dòng) 方 向LRC數(shù) 據(jù)8/11/202210整個(gè)數(shù)據(jù)塊移動(dòng)方向0101010110010101100111001011101111100111數(shù) 據(jù) 移 動(dòng) 方 向LRC數(shù) 據(jù)單元數(shù)據(jù)方向(B)縱向冗余校驗(yàn)(LRC)VCRsVCR bitLRCVCR

4、 bit8/11/202211(B)循環(huán)冗余校驗(yàn)(CRC)功能最為強(qiáng)大方法：將冗余bit序列加在數(shù)據(jù)之后，使得新的數(shù)據(jù)單元正好能被預(yù)定的二進(jìn)制數(shù)除盡。（發(fā)送端和接收端都需要做）如果接收端發(fā)現(xiàn)了余數(shù)，則舍棄該數(shù)據(jù)塊8/11/202212(B)循環(huán)冗余校驗(yàn)(CRC)數(shù) 據(jù)數(shù) 據(jù)CRC除 法 器余 數(shù)數(shù) 據(jù)CRC000n位除 法 器n+1 位取余數(shù)CRCn位發(fā) 送 端接 收 端比預(yù)設(shè)除法器位數(shù)(n+1)少1如果所得到的余數(shù)少于n位，則所缺少的左邊的位假定為0；若余數(shù)為0，那么CRC部分為全00:接受非0:拒絕8/11/202213(B)校驗(yàn)和方式：發(fā)送數(shù)據(jù)時(shí)計(jì)算校驗(yàn)和并且將其同分組數(shù)據(jù)一起發(fā)送接收方

5、進(jìn)行類似運(yùn)算并決定數(shù)據(jù)取舍校驗(yàn)和：將分組數(shù)據(jù)取固定長度，取反碼算術(shù)運(yùn)算相加（結(jié)果也為同樣長度），最后取反碼就得到校驗(yàn)和。接收端：類似反運(yùn)算即可校驗(yàn)8/11/202214(B)校驗(yàn)和 例子：數(shù)據(jù)校驗(yàn)和，包只在頭部校驗(yàn)，取固定長度取值：， 28，和校驗(yàn)和28（校驗(yàn)部分）8/11/202215CRC檢測原理 伽羅域基本知識 CRC編碼 軟件硬件實(shí)現(xiàn)8/11/202216（C1）伽羅域介紹(Galois Field:GF)數(shù)據(jù)、地址、校驗(yàn)碼等都可以看成是屬于GF(2m)中的元素或稱符號 取m=8，GF(28)表示域中有256個(gè)元素，除0，1之外的254個(gè)元素由本原多項(xiàng)式P(x)生成。本原多項(xiàng)式 的特性

6、是 得到的余式等于0。 8/11/202217加法：03 = 001011 = 010 = 1減法與加法相同乘法：54 = (54) mod7 = 2除法：5/3 = 2 3/5 = 2 = (27) =5對數(shù)：log(5) = 5(C1 )伽羅域介紹(Galois Field: GF)域的運(yùn)算：8/11/202218域的構(gòu)造（取m=3） 假設(shè)本原多項(xiàng)式：設(shè)為其一根，即：3 = 1 GF(23)中的元素可計(jì)算如下： 0mod(31) = 0(000)0mod(31) = 0 = 1(001)1mod(31) = 1(010)2mod(31) = 2(100)3 mod(31) = 1(011)

7、4 mod(31) = 2(110)5 mod(31) = 211(111)6 mod(31) = 21(101)（C1）伽羅域介紹(Galois Field:GF)8/11/202219本原元：一個(gè)元素能產(chǎn)生GF(2n)所有非零元素GF(24)元素a4：(24)0=1,(24)1=24,(24)4=216=21,(24)14=256=211元素的階： ak的階=本原多項(xiàng)式：如果一個(gè)多項(xiàng)式f(x)能夠產(chǎn)生2n個(gè)不同元素(包括0),則為本原多相式。 如：本原多項(xiàng)式f(x)=1+ x2+ x5,即能構(gòu)造域GF(25)2n-1GCD(2n-1,K)GCD(n,k)為求最大公約數(shù)函數(shù)（C1）伽羅域介紹

8、(Galois Field:GF)8/11/202220最小多項(xiàng)式： GF(2n)中部分元素具有相同的階，且均為某個(gè)多項(xiàng)式的根，取這類多項(xiàng)式的最低次數(shù)的多項(xiàng)式即為最小多項(xiàng)式共軛類：最小多項(xiàng)式相同的元素的組合， GF(2n)中的元素可以按照共軛類分組共軛類最小多項(xiàng)式根的階01M0(x)= 1 + x1a a2 a4 M1(x)= 1 + x2x37a3 a6 a5 M2(x)= 1 + x x37（C1）伽羅域介紹(Galois Field:GF)8/11/202221 （C2）CRC編碼編碼例子：已知：信息碼:110011信息多項(xiàng)式: K(X)=X5+X4+X+1，生成碼:11001，生成多項(xiàng)

9、式: G(X)=X4+X3+1(r=4) 8/11/202222Step 1)：(X5+X4+X+1)*X4的積是 X9+X8+X5+X4 對應(yīng)的碼是1100110000Step 2)：積G(X) 1 0 0 0 0 1Q(X) G(x)1 1 0 0 1 ) 1 1 0 0 1 1 0 0 0 0F(X)*Xr 1 1 0 0 1 1 0 0 0 0 1 1 0 0 11 0 0 1R(X)(冗余碼)冗余碼是1001,碼字就是1100111001 （C2）CRC編碼8/11/202223解碼驗(yàn)證步驟 接收碼字:1100111001多項(xiàng)式: T(X)=X9+X8+X5+X4+X3+1生成碼:1

10、1001 生成多項(xiàng)式: G(X)=X4+X3+1(r=4)step 1：用字碼除以生成碼，余數(shù)為0，所以碼字正確。 step 2：因r=4，所以冗余碼是：1001，信息碼是:110011 （C2）CRC編碼8/11/202224一些見于標(biāo)準(zhǔn)的CRC資料名稱生成多項(xiàng)式簡記式*應(yīng)用舉例CRC-4x4+x+1ITU G.704CRC-12x12+x11+x3+x+1CRC-16x16+x12+x2+11005IBM SDLCCRC-ITUx16+x12+x5+11021ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCSCRC-32x32+x26+x23+.+x2+

11、x+104C11DB7ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32cx32+x28+x27+.+x8+x6+11EDC6F41SCTP最高冪次項(xiàng)系數(shù)是固定的1，故在簡記式中，將最高的1統(tǒng)一去掉了，如04C11DB7實(shí)際上是104C11DB7 8/11/202225（C2）CRC校驗(yàn)硬件實(shí)現(xiàn)二進(jìn)制本原多項(xiàng)式的線性反饋移位寄存器機(jī)理：考慮二進(jìn)制一般既約多項(xiàng)式： f(x)=cnxn+.+cixi+.+c2x2+c1x+1, ci GF(2)硬件實(shí)現(xiàn)用除法電路（主體移位寄存器和模2加法器(異或單元)組成 ）產(chǎn)生分為兩種結(jié)構(gòu)： SSRG :簡

12、單移位寄存產(chǎn)生器MSRG:模塊式移位寄存產(chǎn)生器8/11/202226（C2）SSRG :簡單移位寄存產(chǎn)生器8/11/202227矩陣表示：（C2）SSRG :簡單移位寄存產(chǎn)生器8/11/202228（C2）MSRG :模塊移位寄存產(chǎn)生器8/11/202229矩陣表示：（C2）MSRG :模塊移位寄存產(chǎn)生器8/11/202230（C2）SSRG與MSRG的關(guān)系SSRG與MSRG最后的輸出就是一個(gè)長度為2n的PN序列(但是二者不相同)產(chǎn)生相同的PN序列，SSRG與MSRG應(yīng)該取互反的。 即：假設(shè)SSRG用f(x)來得到，那么MSRG就要用 g(x)= xn f(x-1)來得到 8/11/20223

13、1（C2）硬件實(shí)現(xiàn)的例子SSRG：MSRG：8/11/202232（C2）硬件實(shí)現(xiàn)狀態(tài)表時(shí)鐘SSRGMSRGR3 R2 R1狀態(tài)矢量R3 R2 R1狀態(tài)矢量T=00 0 110 0 11T=10 1 00 1 0T=21 0 131 0 02T=30 1 151 0 13T=41 1 141 1 14T=51 1 060 1 15T=61 0 021 1 06R3 輸出： 0 0 1 0 1 1 1R2 輸出： 0 1 0 1 1 1 0R1 輸出： 1 0 1 1 1 0 0R3 輸出： 0 0 1 1 1 0 1R2 輸出： 0 1 0 0 1 1 1R1 輸出： 1 0 0 1 1 1

14、08/11/202233（C2）CRC-ITU為例 x16+x12+x5+116級移位寄存器和3個(gè)加法器組成，編碼、解碼前將各寄存器初始化為“1”，信息位隨著時(shí)鐘移入。當(dāng)信息位全部輸入后，從寄存器組輸出CRC結(jié)果。(編碼解碼結(jié)構(gòu)相同) 8/11/202234(C2)CRC軟件實(shí)現(xiàn)比特型算法 ：定義一個(gè)寄存器組，初始化為全1。依照電路圖，每輸入一個(gè)信息位，相當(dāng)于一個(gè)時(shí)鐘脈沖到來，從高到低依次移位。移位前信息位與bit0相加產(chǎn)生臨時(shí)位，其中bit15移入臨時(shí)位，bit10、bit3還要加上臨時(shí)位。當(dāng)全部信息位輸入完成后，從寄存器組取出它們的值，這就是CRC碼。 CRC-ITU為例 x16+x12+

15、x5+18/11/202235數(shù)字通信系統(tǒng)一般是對一幀數(shù)據(jù)進(jìn)行CRC校驗(yàn)，而字節(jié)是幀的基本單位。最常用的是一種按字節(jié)查表的快速算法 .根據(jù)：計(jì)算本字節(jié)后的CRC碼，等于上一字節(jié)余式CRC碼的低8位左移8位，加上上一字節(jié)CRC右移8位和本字節(jié)之和后所求得的CRC碼。 把8位二進(jìn)制序列數(shù)的CRC(共256個(gè))全部計(jì)算出來，放在一個(gè)表里 ，編碼時(shí)只要從表中查找對應(yīng)的值進(jìn)行處理 字節(jié)型算法(C2)CRC軟件實(shí)現(xiàn)8/11/202236CRC-ITU的計(jì)算算法如下：a.寄存器組初始化為全1(0 xFFFF)。b.寄存器組向右移動(dòng)一個(gè)字節(jié)。c.剛移出的那個(gè)字節(jié)與數(shù)據(jù)字節(jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向值表的索引。d.索引所指的表值與寄存器組做異或運(yùn)算。f.數(shù)據(jù)指針加1，如果數(shù)據(jù)沒有全部處理完，則重復(fù)步驟b。g.寄存器組取反，得到CRC，附加在數(shù)據(jù)之后。字節(jié)型算法編碼CRC-ITU為例 x16+x12+x5+18/11/202237a.寄存器組初始化為全1(0 xFFFF)。b