2.1.5-3 回圈冗余校驗(CRC)碼

想必是雪乞春華

(?????)☆萬圣節快樂?☆◥(?o￦o?)◤ 不給糖就搗蛋 ☆(●???●)沒錢(*＾3＾)/～☆

中午我們要學習最后一種校驗碼叫做回圈冗余校驗碼英文縮寫叫CrC碼，這給出了他的英文全稱，那這個小節中我們首先會介紹CrC碼的一個基本思想，然后介紹如何構造，還有如何使用，也就是如何檢錯和糾錯，那首先來看一下這種校驗碼的一個基本思想，我們從大家熟悉的實進制啊出發，假設現在你要給另一個人傳送882這樣的一個10進制資料，那為了防止傳送資料的程序中啊，某一個資料位發生錯誤，你可以和你的另一個小伙伴約定一個除數，比如說是7那882÷7剛好是除的進的，最后我們算得的余數應該是等于0那么當數劇的接收方姐收到資料的時候就可以用他接收到了這個資料，好，那么當資料的接收方接收到資料的時候，就可以用它接收到的這個資料和你們約定的這個除數進行一個除法操作檢查一下余數是否為零，如果余數不等于0，那么是不是就可以確定資料傳輸的程序中肯定是發生了錯誤，比如說啊，對方收到的其實是883，也就是最后一個數發生了錯誤，那883÷7，最后可以算的余數等于1不等于0，那么這就說明肯定是發生了錯誤，需要重新傳送，再比如說第2個資料位發生了錯誤，由8變成了5，那么除以7得到的余數是等于5，同樣這種情況也可以確定，我們的資料傳輸肯定出現了問題，那這是大家熟悉的時間之除法，我們通過約定一個除數，然后在接收到資料之后進行消除的操作，然后在接收到資料之后，與這個除數進行相除的操作檢查余數是否發生了改變，用這樣的方式就可以檢測出資料傳送的錯誤，那這個小節中我們要學習的回圈冗余校驗碼，和我們剛才說到的的實際是除法的例子，其實是類似的思想，就是資料的發送方和接收方會先約定一個除數，當然了我們處理的是計算機里邊的資料，所以這個除數肯定是一個二進制的除數，然后我們會想辦法在K個原始的資訊位后面加上R個校驗位，我們需要確保拼接上這R個校驗位之后，這一整串的資料和我們剛才約定的除數進行相除的操作，余數要等于0積聚的接收方接收到的資料之后需要用二進制除法來檢查余數是否定，假資料的接收方接收到這K加RV的資料之后，需要用二進制除法來檢查余數是否等于0，如果余數不等于0，那么就說明有一些二進制位出現了錯誤，那這種情況下我們就可以進行重傳，或者某些時候也可以進行單筆特位的糾錯，這個我們一會再展開好，總之這就是回圈冗余校驗碼的一個思想和大家熟悉的十進制處罰，其實是有某些聯系的，那剛才我們說過構建回圈冗余校驗碼需要有這樣的兩個關鍵的要素，一個是撤碩，一個是被除數，一般來說題目里會用這種生成多項式的方式給出除術，所以觀察這個生成多項式，我們可以把它寫成1×X的三次方加上一，二次方加上0×X的一次方，再加上1×X的0次方，那由于這個生成多項式里邊所有的這些項，它的系數要么為1，要么為0，因此我們可以把這個生成多項式轉換成對應的二進制數，那像這個GX我們可以轉換成1101就是和這些系數都是分別對應的，所以這兒給出的生成多項式，其實就是指明了我們的除數是多少好，接下來給出了K位的這個資訊嘛，這些資訊我們會把它放到高位的部分好，接下來我們需要確定校驗位的位數R應該等于多少，那么確定的方法是這樣的，R應該是等于它給出的生成多項式的最高次冪像這個式子當中最高的三次方所以我們最侄訓平街上三味的校驗位，等于它給出的生成多項式的最高次冪，像這個式子當中最高次冪是X的三次方，所以我們最侄訓拼接上三位的校驗位，現在大家先不要糾結為什么校驗位的位數啊等于3，我們先往后看會更容易理解，那由于資訊嘛有6位，然后剛才我們推出校驗位有三位，所以最終我們生成的CrC校驗碼總共應該是6+3=9倍，另外之前我們說過這個生成多項式，它對應了一串二進制碼，總共是4個位元好，還記不記得之前說的思路，我們會在這6位的資訊位后面加上三個校驗位，并且我們需要保證我們添加了這三位校驗位之后我們的校驗碼這個to余數等于零因此結下我們需要確定的，而除數要等于0，因此接下來我們需要確定的是，我們添加的這三位校驗位應該是多少，才能保證余數為0，那做法是這樣的，我們會把資訊嘛左移二位也就是左移三位，這是計算機硬體的處理方式，但我們手動做題的話，其實很簡單，就是在這6個資訊為后面補上二個也就是補上三個0，接下來我們會用這個數和除數進行相除的操作，那這個除法運算會讓我們得到三位，也就是RV的余數，不過這個地方我們需要進行的是摩爾除的運算，和我們普通的除法是有一些區別的，好來看一下這種特殊的除法摩爾除是怎么進行的，首先由于除數有4位，所以我們會取被除數度的高4位與他先商一次磨刀霍霍，除法摩爾除是怎么進行的，首先由于除數有4位，所以我們會取被除數部的高4位與他先傷一次，摩爾櫥里邊取商的方式比較特別，我們只看當前我們劃出來的最高位，如果它是1，那么我們就商1那1×10 0 1=1001，我們把它填到下面，接下來我們會對后三位進行摩二減的運算，其實摩爾減的效果和摩爾加是相同的，還記得嗎？摩爾加其實就是異或運算，所以事實上我們就是對后邊的三位進行了抑或運算，接下來看0和11或等于11和01或=10和1億或同樣等于1，因此后邊三位進行無二階或者說分別進行抑或得到的結果是111有點類似于十進制的處罰，分別進行抑或得到的結果是111好，那接下來有點類似于10進制的除法，我們把被除數的后面一位啊補到剛才得到的這個余數的低位，也就是這個樣子，好，接下來我們要確定下一位的首章，那和之前一樣，我們只看最高位，如果最高位為1的話，那我們就商一同樣的1×1101得到1101，接下來我們需要對后面的三位進行一次模2減的運算，那一盒一進行模二件就相當于他們倆進行了一次異或等于01和01或=10和11或=1所以這是一位現在由于高位為零所以接下來我們應該上林那么應該是等于四個零所以我們在，2級訓者說異或的運算得到三個1，現在由于高位是1，所以下一個商我們應該商一得到1101后三位進行，摩2減得到011再補一個0，現在由于高位是0，所以我們需要傷伶，因此接下來需要減0000啊，好颯未進行模2減得到110，好最后還剩一位，我們再把它補上去，由于此時高位為1，所以我們要商議，那么和1101的后三位進行摩二鍵得到的結果是001，那玲玲依舊是我們剛才的這一串代碼和1101進行模2除得到的一個余數除了規則最終得到的余數衛戍應該只比這個少一位那我們用這些操作得到就是我們的，我們的校驗位，所以最終我們得到的CrC校驗碼就應該是前6個資訊位在拼上最后的校驗位001這就是叫驗肺的一個確定方式，用這種方法是確定的校驗碼和1101進行模2，除得到的余數一定是000，好，現在我們已經有了校驗碼，那么我們就可以把這一整串的資訊進行傳輸發送，串的資訊進行傳輸發送那接收方接收到資料之后，就需要進行檢錯和糾錯，注意發送方和接收方提前已經約定好了這個啊，生成多項式或者說約定好了除數，那么當接收方接收到資料之后，就可以用接收到的這一串資訊和剛才約定好的這個除數進行模二除的運算，如果最終得到的余數是000，那么就代表沒有出錯來試一下進行摩爾圖娜，由于高位是1，所以商1的1101，然后后三位進行模2減應該是111啊，這兒補一個0，接下來商議1101后三位進行，摩爾姐應該是0151啊，接下來再補一個1，由于最高位是0，所以商0四個零后三位進行模二減幺幺幺接下來，1101最終得到的余數就應該是000，如果要類比10進制的除法，就相當于剛好除了進沒有余數，那這種情況下就表示沒有出錯，再看另一種情況，如果說倒數第2位出現了錯誤，那么和1101進行模，2除余數應該是等于010，好為了讓大家熟悉摩爾儲運，算我們還是啊動手來算一遍，二位也就是C2這一位如果發生了錯誤的話，那么我們最終得到的余數應該是010這里大家會發現一個巧合，我們得到的這個余數，如果把它翻譯成10進制的話，剛好就是二對吧，而出錯的位置剛好也是C2這個位置，但是其實這個余數和出錯位置之間并沒有這樣必然的聯系，所以這個地方我把劃了一條橫線啊，這句話既對也不對，為什么這么說呢？這地方我把原始的這一串資料，各個位置啊進行了一個改變，如果出錯為在第1位的話，那么和這個生成多項式進行模2，除得到的余數是001，如果出錯的位置是第2位，就是剛才那個例子那得到榆樹市零一零如果出錯的位置是第三位得道于樹是幺零零一看如果把幺零零三億成十進制的話應該是，等于4對吧？所以這個余數的值和出錯位置之間，其實并不是二進制到十進制呃，一轉換這么簡單，但是這余數和出錯位置確實又有對應關系，那細心的同學會發現我們這兒的余數只有三個位元的資訊，而三個位元的資訊總共只能表示2的三次方，也就是8種狀態，如果余數等于三個0，那么表示這個資料的傳輸是正確的，接下來出錯位為1234567，這幾種狀況分別會對應不同的余數，那這7種余數再加上000，是不是已經把三個位元能夠表示的資訊都表示了，所以我們再看如果第8位出錯的話，余數又會等于零零一如果是第九位出色的話語術you等于零一零也就相當于這個語速又重頭來了一，又會等于001，然后如果是第9位出錯的話，余數又等于010也就相當于這個余數又從頭來了一遍，第1個是001，第2個是010，所以上一頁PPT中余數等于010，就可以確定是第2位出錯了嗎？這個結論顯然是站不住腳的，因為如果第9位出錯也有可能會導致余數變為010，因此剛才那句話我們畫了一條橫線表示它并不嚴謹，并不正確，那既然如此，是不是意味著回圈冗余校驗碼它只有減錯的能力而沒有糾錯的能力，也就是無法確定出錯的位置在哪呢這種理解也不全對像剛才這個弟子當中由于我們總共有九個we只有三位的資訊三位的資訊最多只能表示無法完全的標注出這樣這種理解也不全對像剛才這個弟子當中由于我們總共有九個we只有三位的資訊三位的資訊最多只能表示無法完全的標注出這九，錯誤，所以并不是回圈冗余校驗碼沒有糾錯的能力，而是這個例子當中資訊為太長了，所以我們再看另一個例子，如果資訊為只有4類，然后生成多項式和之前是一樣的啊，1101，那首先我們在資訊位后邊補三個0，然后用這一整串對1101進行模二除運算得到余數011，所以最終得到CrC嘛，就應該是這4個資訊位在拼接上011這三個校驗位好，接下來如果這串資料傳輸程序中沒有任何一位發生錯誤，那顯然余數應該是等于0，而如果第1位發生錯誤，那余數是001，如果是第2位發生錯誤，余數是010，第3位是100，然后第4位第5位大家自己看，細心的同學會發現余數和出處位置之間的關系與上一個例子并沒有，余數和出錯位置之間的這個對應關系與上一個例子當中并沒有發生任何改變，上個例子當中，余數為001同樣出錯位是1010，同樣出錯位是2，然后100同樣出錯位是3，后續的也是一樣的，所以這也就意味著，只要我們確定了一個生成多項式，那么無論我們的資訊位如何變化，最終這個余數的值和出錯位置之間肯定都是一種固定不變的對應關系，而如果資料的位數并沒有超過余數所能表示的這個范圍，那么余數和出錯位之間就是一一對應的關系，在這個例子當中，如果余數不等于010，那我們就可以確定出錯位，一定是第2位，于是我們只需要糾正第2位就可以了所以回圈冗余校驗碼其實是有錯功能的只不過資訊為的衛戍部隊所以回圈冗余校驗碼其實是有錯功能的只不過資訊為的衛戍不能，太多那到底要多少個資訊費才不算多呢，這給出的這個不等式其實和上個小節當中還明碼的不等式是很類似的，我們有R個就因為就意味著最終我們會得到RV的余數，而這么多未得于數可以表示2的二次方，這么多種狀態，其中有一種狀態也就是余數為0，00這種狀態是對應正確的狀態，然后剩下的2a減1這么多種狀態需要分別對應上K加R，這么多為每一個未出現錯誤的那種情況，需要進行一個11的對應，所以如果能夠滿足2打二次方，大于等于K+2+1，那么CrC就業嘛，就擁有可以糾正一位錯誤的能力，不過在實際應用當中，CrC嘛，這種方式通常用于計算機網路的資料傳輸通常會把幾千個位元的資訊為加上幾個，過的資料傳輸通常會把幾千個位元的資訊位加上幾個交煙位，所以在實際使用當中，這種交樣碼通常只會用來檢錯，而不會用于糾錯，只不過大家也需要知道，它實際上是有糾錯能力的，理論上這種校驗碼它可以檢測出所有的基數各的錯誤，同時可以檢測出所有的雙位元錯誤，另外它可以檢測出小于等于校驗位長度，也就是小于等于RV的連續的錯誤，這是這種交易碼的一個檢測能力，那這一頁的知識大家能有一個簡要的了解就可以好，那這個小結當中我們學習了回圈冗余校驗碼，又叫CrC碼那考試中一般會給大家一個深沉多項式確定的資訊為大家需要通過這兩個處得到的余數也就是二位的校驗碼然后和資訊未進行接得到最終的一個叫夜盲，那考試中一般會給大家一個生成多項式然，然后給出確定的K個資訊位，大家需要通過這兩個初始條件得到RV的余數，也就是RV的校驗碼，然后和K的資訊位進行一個拼接，得到最終的一個校驗碼，二位的校驗碼，然后和K個資訊唄，進行一個拼接，得到最終的一個校驗碼，當接收方接收到資料之后，需要和這個生成多項式進行一個摩爾除的運算，來檢查余數是否為0，如果余數為0，那么說明沒有錯誤，如果余數非零，那么就說明有錯誤，這姐姐最后我們也探討了CrC碼的一個檢錯和糾錯能力，有不少教材會說CrC碼沒有糾錯能力，但是這種理解是錯誤的，只要資訊位的位數和校驗位的位數足夠合理，不超過某一種特定的范圍界限，那么CrC碼就可以糾正單位元的錯誤，因為我們得到的余數和出錯位置之間是有一一對應的關系的，那這種對應關系只要我們確定了生成多項式，其實就很好確定那這個小杰的那個同樣是祭祖也是g網查東西所以大家也需要重視的，大家也需要重視，當然最重要的是要自己嘗試著動手做一下題，熟悉所謂的摩爾除的運算好的，那以上就是這個小學的全部內容，最后再給大家分享一個有意思的東西來解釋一下，為什么這種校驗碼叫做回圈冗余校驗碼，我們剛才說過，如果出錯位，呃是在第1個位置，那么得到的余數是001，好，現在我們嘗試著001的后面給他添一個0，然后對這個生成多項式進行摩爾圖的運算生成多項式是1101進行模二除，那么應該商0等于4個0號后三位進行模，二件應該是010，有沒有發現這就是出錯為為第2個位置的時候的榆樹好繼續再來，沒為補一個0然后由于首位是琳琳進行，再在末尾補一個0，然后由于首位是0，因此我們需要雙零進行模2-=100和出錯位置為3的，這個余數是相同的，繼續再添一個0，接下來我們應該傷1=1101或3M2-=101和這是一樣的，那用剛才這種方法大家繼續往下算的話，會發現我們得到的三位余數永遠都是001，然后一路一直變到110110再回到001，如此回圈往復，所以為什么這種校驗碼叫回圈冗余校驗碼就是這個原因，剛才我們說的這些例子當中出錯位于8的時候啊，余數又回到了001為第9位的時候，回到了010也就是第2個位置，那如果資訊位更多一些，比如說有10位的話那么接下來一個語素肯定是幺零，這些東西很有意思，不過不是我們考試的重點，大家隨便一聽樂呵樂呵就行，6