通信原理 5-3 常用差錯控制編碼方法.ppt

1、5.3常用的錯誤控制編碼方法、奇偶校驗監(jiān)督編碼或垂直冗馀校驗冗馀檢查(VRC)廣泛用于計算機數(shù)據(jù)傳輸。5.2.1奇偶編碼，編碼規(guī)則：發(fā)件人，分組要傳輸?shù)臄?shù)據(jù)代碼元素，在分組的數(shù)據(jù)后添加監(jiān)督代碼(奇偶位)，確保包含監(jiān)督代碼的代碼組的“1”數(shù)為奇數(shù)(奇偶)或偶數(shù)(奇偶)，如果根據(jù)編碼規(guī)則發(fā)現(xiàn)不匹配，則出現(xiàn)錯誤，但明確錯誤的確切位置(David aser，Northern Exposure，錯誤)，為以下二進制序列編寫奇偶校驗代碼。100110 01011111，為以下二進制序列創(chuàng)建奇偶校驗代碼：1100101 0110010，10011100，010111111，11001011，01100100

2、，5將要發(fā)送的信息代碼排成一行。矩陣中的每一行都是相同的組，每行的末尾都添加了奇偶校驗監(jiān)督代碼元素。大衛(wèi)亞設(shè)，Northern Exposure(美國電視劇)，矩陣中的每一列都由徐璐其他代碼組中相同位置的代碼元素組成，在每一列的末尾添加監(jiān)督代碼元素以執(zhí)行奇偶校驗。最后，按行或列代碼分組順序發(fā)送。行和列監(jiān)督代碼，也稱為矩陣代碼，代碼元素也稱為行和列雙向奇偶校驗，即二維奇偶校驗代碼?？梢栽谛械囊涣兄袡z測到奇數(shù)個錯誤和長度不大于行(列)數(shù)的拆分錯誤?？梢栽谛谢蛄兄袡z測偶數(shù)個錯誤。錯誤數(shù)正好是4的倍數(shù)，并且行矩陣/子矩陣的4個頂點上的錯誤無法更正。1、5.3.3在循環(huán)冗馀檢查(CRC)和循環(huán)冗馀檢查(

3、CRC)數(shù)據(jù)單元的末尾添加重復(fù)位字符串。CRC驗證的基本思想是，根據(jù)由要傳輸?shù)腒位信息位組成的消息，發(fā)射器生成稱為幀檢查序列FCS(幀檢查序列FCS)的R位序列，將R位FCS (CRC代碼)添加到K位信息序列，然后刪除實際傳輸?shù)臄?shù)據(jù)幀(k r接收器以相同的數(shù)字進入的幀)。沒有剩下的數(shù)字，我認為沒有錯誤。如果馀數(shù)不是零，則認為傳輸有錯誤。1，生成CRC代碼，第一步：在數(shù)據(jù)單位(K位)的末尾添加R 0。r是比預(yù)先確定的除數(shù)的位位數(shù)(r 1)少1的數(shù)字。步驟2:使用二進制除法將新增加的數(shù)據(jù)單元(k r位)除以除數(shù)(預(yù)先確定的二進制)得到的馀數(shù)是循環(huán)冗余代碼檢查代碼。步驟3:用在步驟2中獲取的R位的C

4、RC代碼替換附加到數(shù)據(jù)單元末尾的R 0。如果其馀位數(shù)小于r，則最左側(cè)的默認位數(shù)將填充0。如果除法過程完全不生成馀數(shù)(即原始數(shù)據(jù)單元格本身可以除以除數(shù))，則將馀數(shù)位置替換為R 0作為CRC代碼。2，確認CRC代碼，收件人首先到達的是數(shù)據(jù)，然后是CRC檢查代碼。CRC檢查器的功能與發(fā)生器完全相同。接收方收到附加了CRC代碼的數(shù)據(jù)后，將整個數(shù)據(jù)字符串作為一個整體刪除，從而生成循環(huán)冗馀檢查剩馀部分的相同除數(shù)。如果其馀全部為零，則放棄CRC代碼并接受數(shù)據(jù)。否則，丟棄收到的數(shù)據(jù)。CRC檢查代碼生成器和檢查器、R位0數(shù)據(jù)、G (X)、CRC檢查代碼、r 1、R、剩馀、數(shù)據(jù)、發(fā)件人、3、多項式，所有二進制序列

5、只能包含0和1。因此，用于查找CRC代碼的除數(shù)通常用多項式表示。原因如下：代數(shù)多項式很短，可以通過多項式數(shù)學(xué)證明概念。代碼多項式和二進制序列之間的一對一對應(yīng)：(an-1 an-2a1a 0)n a(x)=an-1xn-1 an-2xn-2 a1xa0x 0，所有n位二進制數(shù)都可以使用n，代碼多項式，多項式二進制序列實例，n=3位二進制作為示例，多項式000 001 010 011 100 101 111，0，1，x，x 1，x2，x2 1，x2 x 1，1011 Crc-16: gCRC-CCITT:G(x)=x 16 x 12 x 51 CRC-32:G(x)=x 32 x 26 x 23

6、x 23 x 16 x 12 x 10x 10x 81 x7x 5x 4x 2x 1，多項式G(x循環(huán)冗馀檢查(CRC)檢測數(shù)據(jù)塊中的位值除數(shù)值以外的所有其他錯誤。此外，常用的CRC除數(shù)通常為13、17或33位，因此可以將無法檢測到的錯誤減少到接近0。CRC接收電路與適當?shù)挠布娐方Y(jié)合使用，不僅可以檢測錯誤，還可以更正錯誤，糾錯功能特別適合檢測突發(fā)性錯誤，在數(shù)據(jù)通信中廣泛使用。錯誤性能檢測、所有單個錯誤檢測、所有隨機2位錯誤檢測、所有奇數(shù)錯誤檢測、檢測所有長度小于k位的突發(fā)錯誤、以1-(1/2)k-1概率檢測長度(k 1)位的突發(fā)錯誤、CRC奇偶校驗共同情況下的奇偶校驗、一次一個字符串行同步通

7、信幾乎都使用這種驗證方法。讀取/寫入磁盤信息等，將漢明碼、錯誤朱正廷代碼多奇偶鄭智薰系統(tǒng)代碼、事故考試問題、1K個蘋果分成10個籃子。(當然，蘋果分在籃子里，不能再動了。只能分一次。)要求：這10個籃子可以構(gòu)成1-1000個數(shù)字。微軟的面子問題是二進制思想考察的題目。只要每個籃子的蘋果數(shù)等于二進制位權(quán)重即可。也就是說，分別放1，2，4，8，每個蘋果。解釋代碼編碼思想，解釋代碼是這樣的，K個檢查代碼(K個籃子)表示N個信息位(N個蘋果)，可以表示任何錯誤(可以配置任何數(shù)字)，首先從左到右依次為1，2，3，3，顯然應(yīng)將檢查位放在1，2，4，8，編號上，數(shù)據(jù)放在其他編號上。必須具有2K-1=N K才

8、能表示所有N位信息。驗證規(guī)則思想，每個數(shù)據(jù)位影響多個檢查位，例如與數(shù)字11對應(yīng)的數(shù)據(jù)影響編號1、2、8對應(yīng)的檢查位。因為11=1 2 8。例：將1001000代碼設(shè)計為漢明碼。(使用偶數(shù)檢查)編號1、2、4、8是k位，因此3、5、6、7、9、10、11是n個數(shù)據(jù)位，要傳輸?shù)臄?shù)據(jù)和編號是1 2 3 4 5 6 7 8 9 10 11。1？0 01？0 0 0 0，數(shù)據(jù)位影響檢查位為：3次數(shù)據(jù)位影響編號1、2次奇偶校驗位、3=1 2、相同編號5次數(shù)據(jù)位：5=1 4次6次數(shù)據(jù)位33606=2 4次7次數(shù)據(jù)位：7=1 2 4，最后獲得的漢明碼偶檢查計算如下：1 2 3 4 5 6 7 8 9 10 1

9、1？-嗯？1？0 01？000，k1=n3 xor n5 xor n7 xor n11=0k 2=n3 xor n6 xor n7 xor n10 xor n11=0k 4=n5 xor n6 xor n7=1k 8=n9 xor n10 xor n11=，收件人錯誤控制，收件人通過檢查檢查位來計算出錯的位。如果檢查位I的奇偶校驗不正確，計數(shù)器值加1將檢查所有檢查位，如果計數(shù)器為0，則檢查成功，檢查位的位數(shù)K和數(shù)據(jù)位的位數(shù)N之間的關(guān)系由以下解釋不等式給出：解釋代碼編碼規(guī)則，確認K位放置在2i位置(i=0，1，2，)。也就是說，檢查位通常從低到高依次放置在1、2、4、8位數(shù)據(jù)N位中。漢明碼生成編

10、碼和驗證規(guī)則，發(fā)送者生成漢明碼：根據(jù)受監(jiān)督位影響的信息位，通過驗證規(guī)則(通常為偶數(shù)驗證)構(gòu)建生成關(guān)系(例如，A=0 xor Di xor Dk xor Dl)。根據(jù)生成關(guān)系獲取監(jiān)督位，并生成漢明碼傳輸。接收人驗證規(guī)則接收人根據(jù)創(chuàng)建關(guān)系創(chuàng)建關(guān)系監(jiān)督關(guān)系SA=A xor Di xor Dk xor Dl是SDSCSBSA，sdscsbsa=，解釋：1)將重復(fù)代碼A、B、C、D、順序放入信息代碼中，解釋代碼3360 A B1 C，2)重復(fù)代碼(監(jiān)督代碼)受A、B、C、D影響的線性代碼位(信息代碼)與(監(jiān)督關(guān)系相同)a-1、3、5、7、9、11；B-2，3，6，7，10，11；C-4、5、6、7、12

11、；(注5=4 1；6=4 2；7=4 2 1；12=8 4)D-8，9，10，11，12。3)使用線性代碼位值的奇偶校驗作為冗馀代碼值(將冗馀代碼初始值設(shè)置為0):a=(0，1，1，0，1，0)=1b=(0，1，0，1 4)解釋代碼為33601 0 1 0 0 0 1 0 0 0 0 0 0 0 0(k=，解釋：1)假定重復(fù)代碼為A、B、C、D，則此解釋代碼包含以下內(nèi)容：代碼：“A b0c 100 d100”代碼位：1 2 3 4 5 6 7 8 9 10 11 12 a，B，C；碼位各為1，2，4，8。其中A=1；b=0；c=1；D=0，2)根據(jù)重復(fù)代碼(監(jiān)督代碼)A、B、C、D影響的線性代

12、碼位(信息代碼)，監(jiān)督關(guān)系如下：SA-1，3，5，7，9，11；SB-2，3，6，7，10，11；Sc-4、5、6、7、12；(注5=4 1；6=4 2；7=4 2 1；12=8 4)SD-8，9，10，11，12。3)使用線性代碼位值的奇偶校驗作為冗馀代碼值(將冗馀代碼初始值設(shè)置為0):SA=(1，0，1，0，1，0)=1SB=(0，0，0，0，4)正確的解釋代碼為33601 0 1 0 0 0 1 0 0 0 0 0 0 0另一種是接收端可以發(fā)現(xiàn)錯誤，但不能自動更正錯誤，發(fā)送端請求重新發(fā)送數(shù)據(jù)等來更正錯誤。錯誤控制的兩個基本思路：第一，通過錯誤編碼，接收端翻譯器發(fā)現(xiàn)錯誤，準確判斷錯誤位置，自動糾正。、錯誤控制方法、反饋重發(fā)錯誤修正(ARQ)前向錯誤修正(FEC)混合錯誤修正(HEC)、ARQ、自動-Repeat請求必須具有用于點對點通信的反饋通道。ARQ類型、等待停止接收方的響應(yīng)信號正確接收(ACK)未正確接收(NAK)、返回N-ARQ、發(fā)生