CRC校驗(yàn)原理及推導(dǎo)過程

CRC校驗(yàn)原理及推導(dǎo)過程代數(shù)引論參考文獻(xiàn)[1]對(duì)伽羅華域、線性碼、循環(huán)碼、縮短循環(huán)碼進(jìn)行了很好的論述。1.1伽羅華域????(????)在伽羅華域????(????)中的元素由????(2)上的本原多項(xiàng)式構(gòu)造，域中的元素兩兩運(yùn)算之后的結(jié)果依然是該域中的元素，域中運(yùn)算是基于模2的。??=4,??(??)=??4+??+1????(????){0,1αα2,α3}{0,1,2,4,8,3,6CB5A7EFD9}，轉(zhuǎn)換為多項(xiàng)式依次對(duì)應(yīng)為{0,1αα2α3α+1α2+αα3+α2α3+α+1α2+1α3+αα2+α+1,α3+α2+α,α3+α2+α+1,α3+α2+1,α3+1}。=α?α14=α?(1+α3)=α+α4=α+1+α=1α7+α5=(α2+α)+(α3+α+1)=α3+α2+1模運(yùn)算法則模運(yùn)算與基本四則運(yùn)算有些相似，但是除法例外。其規(guī)則如下(a+b)%p=(a%p+b%p)%p （1-1）(a-b)%p=(a%p-b%p)%p （1-2）(a×b)%p=((a%%p))%p （1-3）ab%p=((a%%p （1-4）結(jié)合率：

((a+b)%p+c)%p=(a+(b+c)%p)%p （1-5）((a×b)%p×c)%p=(a×(b×c)%p)%p （1-6）(a+b)%p=(b+a)%p （1-7）(a×b)%p=(b×a)%p （1-8）((a+b)%p×c)%p=((a×c)%p+(b×c)%p)%p（1-9）線性分組碼和循環(huán)碼一個(gè)長度為n，有2k個(gè)碼字的分組碼，當(dāng)且僅當(dāng)其2k個(gè)碼字構(gòu)成GF(2)域上所有n維向量組成的向量空間的一個(gè)k維子空間是被稱為(n,k)線性碼。線性碼的碼字由k位消息部分和(n?k)位冗余校驗(yàn)部分組成。（一般稱為線性時(shí)序電路其編碼和校正計(jì)算能夠一個(gè)(nk)C其為循環(huán)碼。給定一個(gè)(nk循環(huán)碼的生成多項(xiàng)式g(x)=gn?kxn?k+gn?k?1xn?k?1+g1x+u=(uk?1uk?2u1u(x)=uk?1xk?1+uk?2xk?2+?+u1x+u0 用xn?k乘以u(píng)(x)，得到次數(shù)不大于(n?的多項(xiàng)式為：xn?ku(x)=uk?1xn?1+uk?2xn?2+?+u1xn?k?1+u0xn?k 用生成多項(xiàng)式g(x)除xn?ku(x)得到：xn?ku(x)=m(x)g(x)+v(x) （1-12）和v(x)g(x)的最高次數(shù)為(n?v(x)的次數(shù)必不大于(n?k?。從而有v(x)=vn?k?1xn?k?1+?+v1xv0 整理得到次數(shù)不大于(n的多項(xiàng)式：xn?ku(x)+v(x)=m(x)g(x)=uk?1xn?1+uk?2xn?2+?+u1xn?k?1+u0xn?k+vn?k?1xn?k?1+?+v1x+v0 （1-14）該多項(xiàng)式能被多項(xiàng)式g(x)整除。相應(yīng)的完整碼字為u1,2,?1,0,1,?1,) （1-15）縮短的循環(huán)碼在系統(tǒng)設(shè)計(jì)中，如不能找到一個(gè)具有合適的自然長度的或者信息位數(shù)目的碼字，縮短碼是一種有效的解決方案。對(duì)一個(gè)(nk)循環(huán)碼Cl位均為零的碼字共有C的線性子碼。若從這些碼字中刪除這l個(gè)零信息位，將得到個(gè)長度為n?l的向量，這些向量組成了(n?l,k?l)線性碼。這種碼被稱為縮短循環(huán)碼，但不是循環(huán)碼?？s短循環(huán)碼的糾錯(cuò)能力與差錯(cuò)檢測(cè)能力至少與原碼相同。冗余碼所用符號(hào)數(shù)或信號(hào)碼元數(shù)比表示信息所必需的數(shù)目多的代碼叫冗余碼。循環(huán)冗余檢驗(yàn)CyclicalRedundancyCheck，CRC。它是利g(x)，得到一個(gè)余數(shù)多項(xiàng)式v(x)，將余數(shù)多項(xiàng)式加到信息多項(xiàng)式之后發(fā)送到接收端，接收端同樣用g(x)去除接收到的接收多項(xiàng)式r(x)，進(jìn)行計(jì)算，然后把計(jì)算結(jié)果與由生成多項(xiàng)式g(x)決定的固定序列比較，來檢測(cè)傳輸錯(cuò)誤。由此可以看出其同時(shí)具有循環(huán)碼和1-15理論上可以證明循環(huán)冗余校驗(yàn)碼的檢錯(cuò)能力有以下特點(diǎn)：(1)可檢測(cè)出所有奇數(shù)位錯(cuò)?？蓹z測(cè)出所有雙比特的錯(cuò)?？蓹z測(cè)出所有小于、等于校驗(yàn)位長度的突發(fā)錯(cuò)。CRC碼編碼1.31-15余校驗(yàn)碼的編碼步驟，歸納起來有以下三步驟：第1步 預(yù)先用xn?k乘以信息多項(xiàng)式u(x)，得到xn?ku(x)；第2步 用生成多項(xiàng)式g(x)去除xn?ku(x)，獲得余式v(x)；第3步 整合余式v(x)和xn?ku(x)，獲得碼多項(xiàng)式xn?ku(x)+v(x)。對(duì)于一個(gè)(n,k)g(xxn?kgn?k?1xn?k?1g1x1+一，信息位由高位到低位的順序從循環(huán)移位寄存器體左側(cè)依次輸入，信息位完全進(jìn)入循環(huán)體后繼續(xù)輸入nk?字；gggg0 1Din+D+D++D01圖1左側(cè)串行輸入循環(huán)移位寄存器體二，信息位由高位到低位的順序從循環(huán)移位寄存器體右側(cè)依次輸入，信息位完全進(jìn)入循環(huán)體后寄存器的值就是余式碼字。gggg0 1D+D++D+01Din圖2右側(cè)串行輸入循環(huán)移位寄存器體注：1，移位寄存器循環(huán)體中余式碼字低位在左側(cè)，高位在右側(cè)。以CRC4為例，其生成多項(xiàng)式為：g(x)=x4+x+1，當(dāng)信息多項(xiàng)式u=(101011)時(shí)用兩種方法計(jì)算得到得余式碼字是一樣的：v=(0100)，編碼后完整D120方法一方法二1001110101100000方法一方法二1001110101100000101100111000010011000001010100011010101101011001101101011010111001001101111111101001101101100001011101010011010010101010000010011001010011000100001001000000000CRC

0100圖3信息位為單比特兩種方法比較CRC所有的CRC校驗(yàn)都是基于以下這個(gè)等式：( +)mod= (3-1)其中= r(() 1 + + + () 1 1 0= ,,= 1 + + +,1 1 0= +1 1 + 1 1。M是信息字段（Message）多項(xiàng)式，R是校驗(yàn)字段（Remainder）多項(xiàng)式，r是校驗(yàn)字段多項(xiàng)式的最高次冪（也就是校驗(yàn)字段的長度，CRC-32對(duì)應(yīng)的?????，依次類推?l?ln取決于k的值即??=2??，l是信息字段長度，G是生成(GeneratorCRC32232?CRC32MG（CRCG）是已知的，CRCR；M，R，G為了驗(yàn)證等式是否成立，方法有很多種。CRC表示生成多項(xiàng)式對(duì)應(yīng)的十六進(jìn)制，MSB（mostsignificantbit，可以理解為最左邊的一位）1：表一幾種典型CRC生成多項(xiàng)式發(fā)送端和接收端的具體處理方法對(duì)CRCCRC校驗(yàn)碼在工程應(yīng)用過程中相比數(shù)學(xué)計(jì)算稍微有些變化：1，0數(shù)學(xué)計(jì)算中，當(dāng)信息字段全部為0時(shí)的得到的余式碼字也是全零的，但是在0CRCKeyCRC0Key1。12D1。2，對(duì)接收端收到的數(shù)據(jù)包中拖尾0數(shù)據(jù)的處理。段做比較，就能檢測(cè)出錯(cuò)誤。更簡(jiǎn)單的做法是，接收端對(duì)接收到的所有數(shù)據(jù)求余式（包括信息字段和余式字段），如果沒有傳輸錯(cuò)誤所得的余式一定為0。但00增加或者刪除的情況出現(xiàn)，就無法被檢測(cè)出來。1.2則。接收端如何才能識(shí)別無差錯(cuò)的傳輸呢？我們知道在發(fā)送側(cè)滿足：(??????+??)mod??=?? (3-1)如果用R1????+??? =(????+(??1 +??2 ?+1 ??mod??=((Mxr ??)+????1 +????2 +?+1)mod??=((Mxr+??)+????1 +????2 +?+1)mod??=(((M????+??)????????)+((????1 +????2 +?+1)????????))mod??=(0+((????1 +????2 +?+1)mod??))mod??=((????1 +????2 +?+1)mod??)mod??=(????1 +????2 +?+1)mod??因此，在發(fā)送端發(fā)出來的無差錯(cuò)的傳輸?shù)男ｒ?yàn)序列應(yīng)該是：(????1 +????2 +?+1)mod?? (3-2)在接收側(cè)收到的完整碼字多項(xiàng)式=M????+(3-3)用多項(xiàng)式G??′????取模為：M′?????? =(????+)????mod??=((M????+(????1 +????2 +?+1 ??))????)mod??=((M????+(????1 +????2 +?+1+??))????)mod??=((M????+??+(????1 +????2 +?+1))????)mod??=(((M????+??+(????1 +????2 +?+1))mod??)?? ??)mod??=(((????1 +????2 +?+1)mod??)?? ??)mod??=((????1 +????2 +?+1)????)mod??因此，在接收端計(jì)算出的無差錯(cuò)的傳輸?shù)男ｒ?yàn)和應(yīng)該是：((????1 +????2 +?+1)????)mod?? (3-4)G，CRC-32項(xiàng)式為：??31+