欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標(biāo)題: 關(guān)于CRC（循環(huán)冗余校驗(yàn)）的基礎(chǔ)知識(shí) [打印本頁(yè)]

作者: stanleysit 時(shí)間: 2017-8-21 22:36
標(biāo)題: 關(guān)于CRC（循環(huán)冗余校驗(yàn)）的基礎(chǔ)知識(shí)

【強(qiáng)烈建議在PC端查看本文，否則將無(wú)法顯示完整的排版格式】

（版權(quán)說(shuō)明：基啟人|Gicren保留所有權(quán)利，允許轉(zhuǎn)發(fā)本文鏈接，禁止轉(zhuǎn)載本文內(nèi)容）

概述

      關(guān)于CRC的文章數(shù)不勝數(shù)，在此，由于筆者能力有限不予置評(píng)，但筆者認(rèn)為，若想徹底地了解并靈活地應(yīng)用CRC，必須從物理現(xiàn)象出發(fā)（畢竟，認(rèn)知一個(gè)新的事物往往始于它的現(xiàn)象），再推導(dǎo)出其數(shù)學(xué)表達(dá)式，最后再討論其軟件實(shí)現(xiàn)的方法。在閱讀本文之前希望大家建立一個(gè)宏觀的概念：CRC如同一個(gè)比特（bit）數(shù)據(jù)流的加工廠，即每一比特的數(shù)據(jù)經(jīng)過(guò)CRC處理后，將生成一個(gè)新的CRC運(yùn)算結(jié)果，該運(yùn)算結(jié)果又參與下一比特?cái)?shù)據(jù)的CRC運(yùn)算。

物理現(xiàn)象
      透過(guò)現(xiàn)象看本質(zhì)，是琢磨問(wèn)題的重要思想，琢磨CRC當(dāng)然亦是如此。欲了解CRC的物理現(xiàn)象，必須明確CRC的硬件模型，即硬件是如何實(shí)現(xiàn)CRC運(yùn)算的。CRC是由移位寄存器與異或單元組合而成（一旦數(shù)據(jù)流中一個(gè)比特?cái)?shù)據(jù)發(fā)生變化，后續(xù)的運(yùn)算全部受到影響，這將在下文分析過(guò)程的表格中會(huì)有非常直觀的體現(xiàn)。當(dāng)然，任何一種校驗(yàn)，都無(wú)法保證百分之百可靠，畢竟校驗(yàn)都是通過(guò)一個(gè)指定位寬的數(shù)據(jù)作為判定正確與否的依據(jù)），至于二者如何組合都只是一種約定而已（筆者認(rèn)為，CRC水域最深的地方莫過(guò)于生成多項(xiàng)式的定義，該部分已超乎筆者能力，不予詳述）。
      由于二進(jìn)制是分析CRC最直觀的形式，下文數(shù)據(jù)若無(wú)特殊修飾，均為二進(jìn)制表示形式，不添加二進(jìn)制的修飾符（如1011，即表示1011B）。CRC-4/GICREN的生成多項(xiàng)式為X^4+X+1（此處的"^"為冪符號(hào)，該式等于1*X^4+0*X^3+0*X^2+1*X^1+1*X^0，為數(shù)學(xué)角度的表現(xiàn)形式，將在下文的數(shù)學(xué)表達(dá)式中提及），二進(jìn)制表示形式為1 0011（即，取各項(xiàng)系數(shù)），其硬件模型如圖1-1。CRC-16/GICREN的生成多項(xiàng)式為X^16+X^15+X^2+1（此處的"^"為冪符號(hào)），二進(jìn)制表示形式為1 1000 0000 0000 0101，其硬件模型如圖1-2。

圖 1-1

      接下來(lái)結(jié)合CRC-4/GICREN的硬件模型分析CRC的物理現(xiàn)象。假設(shè)即將輸入CRC-4/GICREN的比特?cái)?shù)據(jù)為X、當(dāng)前CRC的運(yùn)算結(jié)果為ABCD以及X ^ A = E（此處的"^"為異或符號(hào)），注意：A、B、C、D、E及X均為二進(jìn)制數(shù)，通過(guò)上述的硬件模型可得新的CRC運(yùn)算結(jié)果。為便于表達(dá)，采用表格形式體現(xiàn)整個(gè)運(yùn)算及變換的過(guò)程，如表1-1：

      用文字表達(dá)上述等效模型為：
      1.若輸入的比特?cái)?shù)據(jù)與原CRC運(yùn)算結(jié)果中最高位的異或值為1，新的CRC運(yùn)算結(jié)果等于原CRC運(yùn)算結(jié)果左移1位再按位異或0011（即CRC-4/GICREN生成多項(xiàng)式10011的簡(jiǎn)式，至于完整的生成多項(xiàng)式最高位為何多一個(gè)“1”，這是出于數(shù)學(xué)表達(dá)的需要，將在下文提及）。
      2.若輸入的比特?cái)?shù)據(jù)與原CRC運(yùn)算結(jié)果中最高位的異或值為0，新的CRC運(yùn)算結(jié)果等于原CRC運(yùn)算結(jié)果左移1位再按位異或0000。
      接下來(lái)用一段具體的比特?cái)?shù)據(jù)流來(lái)觀察CRC-4/GICREN的工作過(guò)程，數(shù)據(jù)流為10101110，CRC初值為1111（注意：若從軟件實(shí)現(xiàn)的角度討論，該值理論上可以是2^4（此處的"^"為冪符號(hào)）種取值中的任意值，但結(jié)合硬件的需求，通常取各位全為0或1，因?yàn)橐莆患拇嫫魇怯捎|發(fā)器構(gòu)成，統(tǒng)一初始狀態(tài)便于硬件設(shè)計(jì)），如表1-2。其表現(xiàn)形式與實(shí)際等效硬件模型的區(qū)別在于：全部保留每次移出的最高位，同時(shí)并未直接計(jì)算出每一時(shí)刻CRC的運(yùn)算結(jié)果。這種完全展開(kāi)的方式，便于橫向與縱向直觀地了解CRC的工作機(jī)理，同時(shí)也為下文逐漸引出的經(jīng)典計(jì)算方法埋下伏筆。欲求某一時(shí)刻CRC某位的運(yùn)算結(jié)果，只需將某列該時(shí)刻及以上所有背景色為灰色的比特?cái)?shù)據(jù)相異或即可（未填數(shù)據(jù)的部分為0，即左移后補(bǔ)進(jìn)的位），如第4個(gè)比特?cái)?shù)據(jù)（即0）進(jìn)入CRC-4/GICREN時(shí)，第4個(gè)比特?cái)?shù)據(jù)與原CRC運(yùn)算結(jié)果中的最高位的異或值 = 0 ^ (1 ^ 0 ^ 0 ^ 0) = 1（此處的"^"為異或符號(hào)），其余不再贅述。
表1-2
圖片

數(shù)學(xué)表達(dá)式
      在介紹CRC數(shù)學(xué)表達(dá)式之前，先介紹一種二進(jìn)制運(yùn)算方法，即模二運(yùn)算。它與四則運(yùn)算相同，亦包含加、減、乘及除，但區(qū)別在于模二運(yùn)算不用進(jìn)位與借位，僅根據(jù)待運(yùn)算的兩個(gè)位即可確定運(yùn)算結(jié)果，不受前一次運(yùn)算的影響，也不會(huì)對(duì)下一次運(yùn)算造成影響。
模二加：1 ＋ 1 = 0       0 ＋ 0 = 0       1 ＋ 0 = 1       0 ＋ 1 = 1
模二減：1 － 1 = 0       0 － 0 = 0       1 － 0 = 1       0 － 1 = 1
模二乘：1 × 1 = 1       0 × 0 = 0       1 × 0 = 0       0 × 1 = 0
模二除：0 ÷ 1 = 0       1 ÷ 1 = 1
      若將表1-2中的X0~X9均視為12位的數(shù)據(jù)（未填數(shù)據(jù)的部分均為0），同時(shí)在每項(xiàng)前面添加處理每一位數(shù)據(jù)時(shí)輸入的比特?cái)?shù)據(jù)與原CRC運(yùn)算結(jié)果中最高位的異或值，CRC終值亦等于X0~X9各列中的數(shù)據(jù)全部異或后再取其低4位（該結(jié)果與上述通過(guò)硬件模型得到的結(jié)果完全等效，因決定CRC終值的數(shù)據(jù)均未發(fā)生改變）。結(jié)合上述模二運(yùn)算法則（異或運(yùn)算亦等效于模二加或模二減），同時(shí)列出所有運(yùn)算過(guò)程中的中間量Y，表1-2則等效于表1-3（即經(jīng)典計(jì)算方法）。仔細(xì)觀測(cè)表1-3，從Y0開(kāi)始到運(yùn)算結(jié)束，整個(gè)過(guò)程與除法的豎式完全一致，且除數(shù)為10011（即CRC-4/GICREN完整的生成多項(xiàng)式的二進(jìn)制表示形式，同時(shí)印證了前文提到的最高位多一個(gè)“1”的觀點(diǎn)），最終得到的0011為Y0除10011的余數(shù)，即CRC運(yùn)算終值。
      細(xì)剖表1-1的結(jié)論，不難發(fā)現(xiàn)，每處理一位數(shù)據(jù)，需要兩次異或（一次異或0011或0000，另一次將輸入的比特?cái)?shù)據(jù)與原CRC運(yùn)算結(jié)果中最高位進(jìn)行異或）及一次移位。然而，表1-3第一次進(jìn)行多位異或，之后進(jìn)行一次異或及一次移位即可，這更加符合實(shí)際軟硬件的處理，因?yàn)殡m然從硬件角度，存儲(chǔ)數(shù)據(jù)的最小單元是位，但對(duì)數(shù)據(jù)的操作，一條指令便可實(shí)現(xiàn)多個(gè)位的同時(shí)操作。
表1-3
圖片

      在代數(shù)編碼理論中，將一組信息碼（簡(jiǎn)稱碼組）表示為一個(gè)多項(xiàng)式，碼組中各碼元作為多項(xiàng)式的系數(shù)，如 10101110 表示為1•X^7 + 0 • X^6 + 1 • X^5 + 0 • X^4 + 1 • X^3 + 1 • X^2 + 1 • X^1 + 0 • X^0（此處的"^"為冪符號(hào)），接下來(lái)用數(shù)學(xué)語(yǔ)言表達(dá)上述過(guò)程如下：設(shè)源數(shù)據(jù)流位寬為m，CRC的位寬為n，F(xiàn)(x)表示源數(shù)據(jù)流對(duì)應(yīng)的多項(xiàng)式（階數(shù)為m-1），G(x)表示生成多項(xiàng)式（即除數(shù)，階數(shù)為n），L(X)表示系數(shù)為CRC初值的多項(xiàng)式（階數(shù)為n-1），D(x)表示被除數(shù)多項(xiàng)式（= X^n • F(x) + X^m • L(x)，此處的"^"為冪符號(hào)）。根據(jù)代數(shù)編碼理論中的表示法及表1-3的分析結(jié)果可知，CRC的運(yùn)算結(jié)果等于D(x)除G(x)的余數(shù)，應(yīng)注意所有運(yùn)算均須遵循模二運(yùn)算法則。

軟件實(shí)現(xiàn)（查表法）
      經(jīng)典計(jì)算方法雖然減少了異或的次數(shù)，但仍是一種基于位判別的方法，一次僅處理一個(gè)位。然而從實(shí)際應(yīng)用的角度出發(fā)，我們希望一次可處理幾個(gè)位（即塊判別），這將會(huì)極大程度地提升軟件的效率。至于一次處理幾個(gè)位根據(jù)實(shí)際情況自行設(shè)定，且與CRC位寬無(wú)關(guān)，僅是軟件上時(shí)間復(fù)雜度與空間復(fù)雜度權(quán)衡的問(wèn)題。例如上述的例子，可以2位為一個(gè)數(shù)據(jù)塊，抑或先以3位為一個(gè)數(shù)據(jù)塊再以2位為一個(gè)數(shù)據(jù)塊。接下來(lái)將上述的例子分3位和5位兩個(gè)數(shù)據(jù)塊進(jìn)行處理，分析數(shù)據(jù)塊小于或大于CRC位寬的情況，以便洞察查表法的本質(zhì)。
      先處理前3位數(shù)據(jù)101，此時(shí)的CRC初值為1111，根據(jù)經(jīng)典計(jì)算方法及模二運(yùn)算法則可得：
圖片
      再處理后5位數(shù)據(jù)01110，注意此時(shí)的CRC初值是處理完前3位后的余數(shù)，即1110。
圖片
      由上述兩個(gè)過(guò)程可以發(fā)現(xiàn)，假設(shè)一次處理k位，其CRC運(yùn)算結(jié)果等于這k位數(shù)據(jù)與CRC原值的異或（注意高位對(duì)齊，當(dāng)k大于CRC位寬時(shí)，應(yīng)在CRC原值后補(bǔ)k-4個(gè)0；當(dāng)k小于或等于CRC位寬時(shí)，僅取CRC原值的k位）再補(bǔ)四個(gè)0后對(duì)10011取余，該余數(shù)再與CRC原值左移k位后的值進(jìn)行異或（注意移位時(shí)應(yīng)保持CRC位寬不變）。
      由上述的分析可知查表法的表即預(yù)先計(jì)算出2^3種MOD(xxx0000/10011)及2^5種MOD(yyyyy0000/10011)的結(jié)果，如表1-4及表1-5（表中的待查數(shù)據(jù)僅顯示xxx及yyyyy）：
         表1-4                                                                                  表1-5
圖片

      修正+補(bǔ)充中……

余下內(nèi)容詳見(jiàn)作者博客：
http://user.qzone.qq.com/2294515665/blog/1491534995

歡迎光臨 (http://www.raoushi.com/bbs/)