各種校驗碼校驗算法分析

各種校驗碼校驗算法分析二進制數(shù)據(jù)經(jīng)過傳送、存取等環(huán)1001基礎上增加幾位校驗冗余位。各種校驗碼校驗算法分析的二進數(shù)位bit1bitbit1311。如果任何碼字中一位或多位被顛倒了結果這個碼字就不能與其它有效信息區(qū)分開。例如001011011011822a2a1a000001001201030114100510161107111圖1信息序號二進碼字a3a2a1a0000001100121010300114110050101601107111128-28100110111011有。然而差錯不能被糾正。假定只有一個數(shù)位是錯的正確碼1001111100111010。接收者不能確定原來到底42438-317123567001021212232333必須考慮信息發(fā)生差錯的概率和該系統(tǒng)能容許的最小差錯率等因素。要有專門的研究來解決這些問題。1“10110101”11。注意奇性檢測等效于所有碼元的模二加并能夠由所有碼元的n⊕a1⊕a2⊕…⊕an奇偶校驗可描述為給每一個碼字加一個8-2d21210ASCII01。接收端01100011ASCII101100001011000111、253ASCIIana0⊕a1⊕a2⊕…⊕an-1奇校驗位anNOTa0⊕a1⊕a2⊕…⊕an-1在一個典型系統(tǒng)里在傳輸以前由奇偶發(fā)生器把奇偶校驗位加到每個字中。原有信息中的數(shù)字在接收機中被檢測如果沒有出現(xiàn)正確的奇、偶性這個信息標定為錯誤的這個系統(tǒng)將把錯誤的字拋掉或者請求重發(fā)。在實際工作中還經(jīng)常采用縱橫都加校驗奇偶校驗位的編碼系統(tǒng)--分組奇偶校驗碼。m把這些信息都編成每組n4nHPVPmna2?a-1amHP1b1b2?1bmHP2c1c2?1cmHP3n1n2nm-1nmHPnVP1VP2VPm-1VPmHPn14用綜橫奇偶校驗的分組4樣先找一行或一列已知數(shù)據(jù)完整的確定出該行或列是奇校的行或列根據(jù)校驗性質(zhì)確定該未知數(shù)這樣不斷做下去就能求出所有未知數(shù)。【例】200167ASCII編碼排列再加上水平垂直奇偶校驗位構成下列矩陣最后一列為水平奇偶校驗位最后一行為垂直奇偶校驗位:字符7位ASCII碼HP30X1X200110Y1100100X31X41010110Y201X5X61111D100X710X800X9111X1011VP001X111X12則X1X2X3X4處的比特分別為 36 X51X61X7X8處的比特分別為

X9X10XI1X12處的比特分別為 38 Y1和Y2處的字符分別為 39 和 40

。解從ASCII碼左起第5列可知垂直為偶校驗。1X403X317X808X1217行可知X1116X1006X912可知X111X213X51445X7036X1X2X3X4111037X5X6X7X8100038X9X10X11X12101139由字符Y1100100149H知道Y1“I”由“D”ASCII100010044H40由字符Y2ASCII011011137H知道Y2“7”由“3”的ASCII011001133H的ASCII011000030H“A”的ASCII100000141H3。實現(xiàn)這種糾正的方法之一是海明系統(tǒng)對于錯誤的數(shù)位無論是原有信息位中的還是附加校驗m1、確定最小的校驗位數(shù)k成D1D2?Dk2kmkk013、對所接收的信息k4、如果所有的奇偶檢查結果均為正確的則認為信息無錯誤。如果發(fā)現(xiàn)有一個或多個錯了則錯誤的位由這些檢查的結果來唯一地確定。校驗位數(shù)的位數(shù)kmkmkkk2k2k-12k-1≥mk放在任何位置但習慣上校驗位被安排在1248、?的位5m4k3B1B2B3B4B5B6B7xxxxxxP1P2D1P3D2D3D45海明碼中校驗位和kmkP11、3、5、7、?P1、D1、D2、D4、?位包括P1自己P22367、?P2D1D3D4、?位包括P2P34、5、6、7、?P3、D2、D3、D4、?位包括P3m4k3ABC61234567BCxxxxxxxxxxxx6AB1⊕B3⊕B5⊕B70得P1D1⊕D2⊕D4BB2⊕B3⊕B6⊕B70得P2D1⊕D3⊕D4CB4⊕B5⊕B6⊕B70得P3D2⊕D3⊕D4若四位信息碼1001P1、P2、P371001816B1B2B3B4B5B6B7P1P2D1P3D2D3D41000010011001圖四位信息碼的海明編碼P1P2D1P3D2D3D400000011010010101010100001110011000100101110011000011111110000001100110110100110011011110010101010010110111111可根據(jù)這三個校驗方程對接收到的信息進行同樣的奇偶測試AB1⊕B3⊕B5⊕B70BB2⊕B3⊕B6⊕B70CB4⊕B5⊕B5⊕B70003C0B3AB1B3?？蓸嫵啥M數(shù)CBAA00111004312113212k-1≥mk。但在清華的王愛英主編的《計算機組成與結構》該書已成為國內(nèi)的4212k-1≥mk3些書簡單抄襲時沒有仔細消化所以出現(xiàn)一些概念錯。對于一32121CRC。CRC上幾位校驗碼以增加整個編碼系統(tǒng)的碼距和查錯糾錯能力。CRCCRCK后再拼接RN叫NKNK為N-KRGxGxKCRCCXCxR示成Cx2RCxR通過Cx2RGx1、多項式與二進制數(shù)碼多項式和二進制數(shù)有直接對應關系x10。可以看出xRR1GxCx為Gxx4x3x111011Cxx3x2x12輸過程中這個數(shù)始終保持不變。在發(fā)送方利用生成多項式22滿足以下條件a1。bCRC20c、不同位發(fā)生錯誤時應該使d29NK碼距dGxGx743x3x11011743x3x21110134x4x3x2111101734x4x2x11011115113x4x1100111575x8x7x6x4111101000131263x5x2110010131215x10x9x8x6x5x311110110100163573x6x1100001163515x12x10x5x4x21101000011010110411024x16x15x211100000000000010193222a2b11200c、一直做到余數(shù)的位數(shù)小于除數(shù)時該余111100011011011————1111000-----被除數(shù)1101————除數(shù)————0100001101————010101101————111————余數(shù)CRC碼的生成步驟1、將x的最高冪次為RGxR12、將信RCx2R32R4、將余數(shù)CRCGxx3x1。410101、將生成多項式Gxx3x1101124R1始報文Cx3R10100003、用生成多項式對應的421001-------商------------------------10100001011 除數(shù)------------10001011------------011 余數(shù)校驗位5、編碼后的報文CRC碼1010000011------------------1010011CRC的和糾錯在接收端收到了CRCGx20010了Gx1011Cx1010CxCRCA7A6A5A4A3A2A1正確101001000無錯誤101001010100011010111101101110000111110011001001100101010001111011110112345671074CRCGx1011Gx20010001001203010021000ll?00210101A7A110的CRC碼Gx1011Cx10101010111用Gx101120100021010111410141111010。說A71011101037A31010011CRC在數(shù)據(jù)通信與網(wǎng)絡中通常k后采用CRCrr1616CRC-16x16x15x21和CRC-CCITTx16x15x21。一般情況下rCRCr1-2-r-11-2-rr1上述r161699997179999817CRC這里突發(fā)錯誤是指幾乎是連續(xù)發(fā)生的一串錯突發(fā)長度就是指從出錯的第一位到出錯的最后一位的長度但是中間并不1】某循環(huán)冗余碼CRC1111和1100CRC碼分別為AB。由于某種原因使接收端收到了按某種規(guī)律可判斷CRCC、DE。199811供選擇的答案A①lllll00②1111101③1111110④1111111B①1100100②1100101③1100110④1100111CE①0000000②0001100③0010111⑤1000110⑥1001111⑦1010001⑧1011000AGx1101Cx1111Cx23÷Gx1111000÷11011011111CRC1111111BGx1101Cx1100Cx23÷Gx1100000÷11011001101得到的CRC1100101CE分別用Gx11012除:①0000000÷11