文章目錄

• • 知道兩個(gè)概念
  • • 模2和
    • 模2減
  • 兩種不同的二進(jìn)制除法
  • • 除法
    • 模2除法
  • CRC 循環(huán)冗余校驗(yàn)
  • • 編碼過(guò)程
    • 差錯(cuò)檢測(cè)能力

談CRC循環(huán)冗余校驗(yàn)的之前，先把二進(jìn)制除法說(shuō)一下，先回憶一下十進(jìn)制之間的除法是如何運(yùn)算的，

這個(gè)式子在做除法的時(shí)候滿足了這幾個(gè)條件：

• 從被除數(shù)的最左邊開(kāi)始向右做除法
• 被除數(shù)運(yùn)算的兩位永遠(yuǎn)比除數(shù)大
• 如果相減的時(shí)候需要向前一位借1，則前一位要減1

知道兩個(gè)概念

模2和

兩個(gè)二進(jìn)制位相加不進(jìn)位，即 0+0=0，0+1=1，1+0=1，1+1=0（此時(shí)不進(jìn)位）

模2減

兩個(gè)二進(jìn)制位相減不借位，即0-0=0，0-1=1（此時(shí)不進(jìn)位），1-0=1，1-1=0

兩種不同的二進(jìn)制除法

除法

這個(gè)方法和正常的十進(jìn)制除法沒(méi)什么區(qū)別，就和剛開(kāi)始回顧的二進(jìn)制除法運(yùn)算方法一樣，在下面的例子中，被除數(shù)前四位1010除以111要考慮向前一位借1，其實(shí)把這些二進(jìn)制轉(zhuǎn)換成十進(jìn)制的除法就是83/7=11…6，而這個(gè)二進(jìn)制的運(yùn)算結(jié)果完全吻合。

模2除法

模2除法就要用到之前說(shuō)的兩個(gè)概念之中的1個(gè)，就是模2減，除數(shù)和被除數(shù)相減的時(shí)候不考慮進(jìn)位（可以看作做異或運(yùn)算），這就引出了CRC（Cyclic Redundancy Check）循環(huán)冗余校驗(yàn)，用來(lái)檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤，本次主要講解在計(jì)算機(jī)網(wǎng)絡(luò)信息傳輸中的校驗(yàn)，計(jì)算機(jī)組成原理的信息保存校驗(yàn)原理和網(wǎng)絡(luò)信息校驗(yàn)一樣，不做深入講解。在相減的時(shí)候每一次都是3位之間相減。你可能會(huì)問(wèn)，為什么有時(shí)結(jié)果是1，有時(shí)結(jié)果是0呢，主要是被除數(shù)百位和除數(shù)百位相減可以抵消，不然相減結(jié)果還是3位就沒(méi)有意義了。

CRC 循環(huán)冗余校驗(yàn)

編碼過(guò)程

計(jì)算機(jī)傳輸數(shù)據(jù)的時(shí)候要最底層是物理層，向上有數(shù)據(jù)鏈路，網(wǎng)絡(luò)層等等。當(dāng)然數(shù)據(jù)要從計(jì)算機(jī)輸出，是自上向下傳輸，比如從網(wǎng)絡(luò)層得到一個(gè)IP數(shù)據(jù)報(bào)，封裝成數(shù)據(jù)幀。在發(fā)送端把數(shù)據(jù)劃分成組，假設(shè)每一組k位，數(shù)據(jù)M=101001，那么k=6,在M后面添加n位的二進(jìn)制數(shù)值（冗余碼）用來(lái)差錯(cuò)檢驗(yàn)。添加冗余碼的時(shí)候被除數(shù)和除數(shù)之間進(jìn)行的是模2除法。

接下來(lái)確定除數(shù)，除數(shù)采用二進(jìn)制系數(shù)多項(xiàng)式，如下表

名稱多項(xiàng)式對(duì)應(yīng)除數(shù)

CRC-8	x8+x2+x+1	1000 0011 1
CRC-16	x12+x11+x3+x2+x+1	1100 0000 01111
…	…	…

x⁸+x²+x+1表示二進(jìn)制第8,2,1,0位為1，黃色的就是0位，其它多項(xiàng)式同理

接下來(lái)繼續(xù)M數(shù)據(jù)的處理，設(shè)除數(shù)P=1101，則n=3,為什么冗余碼的長(zhǎng)度是3呢？

因?yàn)橛鄶?shù)比除數(shù)少1，余數(shù)是被用來(lái)做校驗(yàn)用的。被除數(shù)是2ⁿM=101001000。

為什么后面多出來(lái)n個(gè)0呢？這和后面的檢驗(yàn)有關(guān)由于拿到的是（k+n）的數(shù)據(jù)要對(duì)數(shù)據(jù)做模2運(yùn)算最后判斷余數(shù)，只有被除數(shù)處于（除數(shù)+除數(shù)的余數(shù)）才會(huì)等于0，所以0的個(gè)數(shù)和余數(shù)的個(gè)數(shù)一樣。

根據(jù)上面模2除法運(yùn)算結(jié)果是商為110100，余數(shù)為001，把101010改為101001001，這就是一個(gè)完整的可校驗(yàn)數(shù)據(jù)。

下表是本題的各個(gè)數(shù)據(jù)的含義

符號(hào)含義值

M	一組數(shù)據(jù)	101001
n	冗余碼的位數(shù)	3
k	每組數(shù)據(jù)的位數(shù)	6
P	除數(shù)	1101
2nM	被除數(shù)	101001000
Q	商	110101
R	（余數(shù)）冗余碼	001
2nM+R	發(fā)送的數(shù)據(jù)	101001001

差錯(cuò)檢測(cè)能力

利用多項(xiàng)式，我們定義誤碼多項(xiàng)式E(X)是接收到的消息碼字與正確碼字的異或。即

E(X) = Trecv(X) XOR Tcorrect(X) …… (14)

當(dāng)E(X)能夠被CRC多項(xiàng)式P(X)整除的時(shí)候（即R=0）CRC算法無(wú)法檢查到錯(cuò)誤。當(dāng)我們選擇一個(gè)適當(dāng)?shù)腜(X)時(shí)，E(X)都不能被P(X)整除，因此可以檢測(cè)出的出錯(cuò)情況有：

• 單比特差錯(cuò)，只要P(X)含有一個(gè)以上的非零項(xiàng)。
• 雙比特差錯(cuò)，只要P(X)滿足上述兩種形式((12)(13)式)。
• 任意奇數(shù)個(gè)比特差錯(cuò)，只要P(X)含有因式(X - 1)。
• 任意突發(fā)差錯(cuò)，當(dāng)突發(fā)差錯(cuò)長(zhǎng)度小于或等于幀檢驗(yàn)序列(F(X))的長(zhǎng)度(n - k)。
• 長(zhǎng)度為(n - k + 1)的突發(fā)差錯(cuò)片段，這個(gè)片段等于(1-2-(n-k-1))。
• 長(zhǎng)度大于(n - k + 1)的突發(fā)差錯(cuò)片段，這個(gè)片段等于(1 - 2-(n-k))。

總結(jié)

以上是生活随笔為你收集整理的CRC循环冗余校验引起的二进制除法如何计算风暴的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。