1、第第8章章 編碼和差錯控制編碼和差錯控制無無線通信與網(wǎng)線通信與網(wǎng)絡(luò)絡(luò)(第第2版版) 作者作者 斯斯托林托林斯斯 何軍等何軍等 譯譯目錄 8.1 差錯檢測 8.1.1 奇偶校驗 8.1.2 循環(huán)冗余檢錯 8.2 塊糾錯碼 8.2.1 塊碼原理 8.2.2 海明碼 8.4 自動重發(fā)請求 8.4.1 流量控制 8.4.2 差錯控制8.1 差錯檢測 差錯定義：傳輸導(dǎo)致數(shù)字信號的1N位被改變。 三種解決差錯的方法 1、檢測碼計算機網(wǎng)絡(luò)學(xué)過 僅檢測差錯，例：奇偶校驗、循環(huán)冗余 (CRC)。 2、糾錯碼 功能：既可檢錯，又可糾錯。 常用于無線傳輸中，差錯率高，重傳效率低。 常用的糾錯方法：塊碼、海明碼、循環(huán)

2、碼等。 3、自動重發(fā)請求機制(ARQ) 依賴于檢測碼，發(fā)送端要重傳錯誤的數(shù)據(jù)。 8.1 差錯檢測整個幀無差錯的概率(全正確)，隨F增大整個幀有1或多位錯的概率(至少有1位錯) 例8.1：不同的環(huán)境有不同的誤碼率需求 用戶要求：平均每天出現(xiàn)1個錯幀，信道速率64 Kb/s ，幀長1000位。 現(xiàn)有條件：信道誤碼率Pb=10-6，是否達標(biāo)？是否達標(biāo)？ 答：1天可傳輸64*3600*24 = 5.5*106幀 允許差錯概率 P =l/5.5*106=0.18*10-6 整個幀無差錯的概率P1=(1-Pb)1000=0.999 至少1位錯概率P2=10-3，這比需求高，不達標(biāo)。 計算：現(xiàn)有條件下，平均

3、多久出現(xiàn)一個錯幀？計算：現(xiàn)有條件下，平均多久出現(xiàn)一個錯幀？ 答：平均1000/64=15.6s出現(xiàn)一個錯幀。 上述結(jié)果促使我們要使用差錯檢測技術(shù)檢測碼的基本原理8.1.1 奇偶校驗 發(fā)送方：11100000111000001(偶校驗) 在每個字節(jié)的尾部加上1個校驗碼，使得碼組中”1”的個數(shù)成為偶數(shù)(偶校驗)或者奇數(shù)(奇校驗) 。 接收方：110000001(偶校驗，不合格) 檢查碼組中”1”的個數(shù)，是否為偶數(shù)(或奇數(shù))，如果不符合校驗，要求重新發(fā)送該數(shù)據(jù)。 檢測不出什么錯誤？ 檢測不出偶數(shù)個錯誤，不能糾錯。 循環(huán)冗余校驗(CRC，Cyclic Redundancy Code) 發(fā)送端 原始信息

4、 k 位，加上 r 位的校驗序列(FCS)； 這 n 位數(shù)可以被某個事先設(shè)定好的數(shù)整除。 將 n 位數(shù)據(jù)，發(fā)送出去； 接收端 收到數(shù)據(jù)后用原先那個設(shè)定好的數(shù)來除； 若沒有余數(shù)出現(xiàn)，則表示數(shù)據(jù)傳送正確； 若有余數(shù)出現(xiàn)，則表示數(shù)據(jù)傳送有誤。 如何從k位原始信息，得到r位校驗序列？8.1.2 循環(huán)冗余檢錯(CRC)k 位r 位k + r = n位8.1.2 循環(huán)冗余檢錯(CRC)D: k位數(shù)據(jù)F: r位尾T: k+r=n 位8.1.2 循環(huán)冗余檢錯(CRC)8.1.2 循環(huán)冗余檢錯(CRC)(4)25D加上余數(shù)(R=01110)得到T=101000110101110異或運算(5)驗證：如果傳輸沒有差

5、錯，接收方收到原封不變T=101000110101110。用T 除以P，整除沒有余數(shù)，檢驗成功。8.1.2 循環(huán)冗余檢錯的檢錯能力 差錯模式 E E=001000000000000 (1表示差錯) 發(fā)送報文T=101000110101110 接收報文T=100000110101110 CRC的檢錯能力 假如有差錯， 當(dāng)且僅當(dāng) E可以被P 整除時，接收方才無法檢測到這個差錯。 直觀上看，這種情況概率比較低。目錄 8.1 差錯檢測 8.1.1 奇偶校驗 8.1.2 循環(huán)冗余檢錯 8.2 塊糾錯碼 8.2.1 塊碼原理 8.2.2 海明碼 8.4 自動重發(fā)請求 8.4.1 流量控制 8.4.2 差錯

6、控制8.2 塊糾錯碼 檢錯碼，不適宜無線信道 誤碼率高， 這會導(dǎo)致大量的重傳操作。 如：衛(wèi)星鏈路中，傳播延遲比幀的傳輸時間長許多，重傳的效率非常低。 糾錯碼，更適合無線信道 k位原始數(shù)據(jù)，n位傳輸信號。 校驗n-k位冗余，用于糾錯。 右邊的糾錯碼，能糾正1位數(shù)據(jù)位數(shù)據(jù)位k校驗位校驗位n-k84165326647128825698.2 塊糾錯碼 典型的糾錯碼：(n, k)塊碼 編碼后總位數(shù) n ，數(shù)據(jù)位 k 共有2n個碼字，其中2k 個有效碼字 冗余度 (n-k)/k，冗余位與數(shù)據(jù)位的比例 編碼速率 k/n，數(shù)據(jù)位與總位的比率 表示編碼需要額外增加多少帶寬8.2.1 塊碼原理28.2.1 塊碼原

7、理 例8.6： 對k=2, n=5 ，指定如下映射： 如果接收的碼字為00100 這不是一個有效的碼字，肯定出了差錯。 猜一猜，最可能是哪個有效碼字？原始數(shù)據(jù)原始數(shù)據(jù)有效碼字有效碼字0000000010011110110011111110000008.2.1 塊碼原理 計算海明距離 糾錯結(jié)果 最可能的碼字是00000，數(shù)據(jù)是00。數(shù)據(jù)塊數(shù)據(jù)塊 有效碼字有效碼字海明距離海明距離0000000d(00000, 00100)=10100111d(00111, 00100)=21011001d(11001, 00100)=41111110d(11110, 00100)=38.2.1 塊碼原理 如果發(fā)生

8、1位差錯 既可以檢錯，又可以糾錯。 結(jié)果碼字僅與一個有效碼字距離為1。 如果發(fā)生2位差錯 能夠檢測，無法糾錯。 與2個有效碼字距離都是2，接收端無法判斷從哪個有效碼字變化而來。8.2.1 塊碼原理 判斷糾錯能力的另一個方法：有效碼字兩兩距離 有效碼字之間的最小距離是3，可能錯誤0-3位 00000錯0位，有效碼字 00001錯1位，如果是0000錯1位，可以糾錯 00011錯2位，如果是0000錯2位，無法糾錯 00111錯3位，變成有效碼字 該編碼總可以糾正1位差錯，檢測2位差錯。d(00000，00111)=3；d(00000，11001)=3；d(00000，11110)=4；d(001

9、11，11001)=4；d(00111，11110)=3；d(11001，11110)=3；dmin -18.2.2 海明碼8.2.2 海明碼kn-kn-k8.2.2 海明碼例8.78位的數(shù)據(jù)塊是00111001海明碼插入數(shù)據(jù)位的1248處將所有1的位置值異或運算得出海明碼為0111將海明碼插入數(shù)據(jù)塊的位置傳輸12位塊是001101001111求8位數(shù)據(jù)00111001的海明碼0 0 1 1 1 0 0 18.2.2 海明碼例8.7傳輸?shù)?2位塊是001101001111傳輸過程中，第6位錯接收的12位塊是001101101111將海明碼和所有非0數(shù)據(jù)位進行異或運算結(jié)論：差錯發(fā)生在位置6 處因

10、此可以糾正1位錯誤=6目錄 8.1 差錯檢測 8.1.1 奇偶校驗 8.1.2 循環(huán)冗余檢錯 8.2 塊糾錯碼 8.2.1 塊碼原理 8.2.2 海明碼 8.4 自動重發(fā)請求 8.4.1 流量控制 8.4.2 差錯控制8.4 自動重發(fā)請求（了解） 自動重發(fā)請求(ARQ) 作用：使不可靠的數(shù)據(jù)鏈路變得可靠。 在數(shù)據(jù)鏈路層和傳輸層協(xié)議中使用。 配合CRC這樣的差錯檢測碼的使用。 包含兩部分 流量控制和差錯控制8.4.1 流量控制 流量控制的作用 接收方數(shù)據(jù)緩沖區(qū)，長度有限。 確保發(fā)送數(shù)據(jù)不會超出接收實體接收數(shù)據(jù)能力。 如果沒有流量控制，接收器緩沖區(qū)可能會溢出。8.4.1 流量控制 滑動窗口機制 將

11、很長的數(shù)據(jù)塊拆成小PDU，降低傳輸風(fēng)險。 PDU：協(xié)議數(shù)據(jù)單元(protocal data unit) 窗口寬度W：接收站點分配了W個PDU的緩沖區(qū)，允許發(fā)送站點在不等待任何確認(rèn)的情況下同時發(fā)送W個PDU。 確認(rèn)報文RR X：接收站點發(fā)送，告知PDU (X-1)己被接收，準(zhǔn)備接收PDU X。8.4.1 流量控制已經(jīng)收到2準(zhǔn)備接收3已經(jīng)收到3準(zhǔn)備接收4窗口延伸至2收到確認(rèn)2后，窗口延伸至1滑動窗口寬度為7發(fā)送確認(rèn)2后，窗口延伸至1如果窗口長度為1會發(fā)生什么影響？8.4.2 差錯控制 差錯控制的作用 檢測和校正傳輸過程中出現(xiàn)的差錯PDU。 差錯的類型 時延太大，PDU丟失、PDU損壞。 差錯控制的措施 超時后重傳：源站點在預(yù)定時間沒有收到確認(rèn)的情況下，會重新傳輸一個PDU。 否認(rèn)和重傳：目的站點為檢測到差錯的PDU返回一個否定確認(rèn)，源站點重新傳輸這些PDU。返回NARQ的例子 A的數(shù)據(jù)PDU 5出錯：當(dāng)A接收到B返回的REJ 5(否定確認(rèn))時，由于傳播延遲， A已經(jīng)發(fā)送PDU 6, 7，于是PDU 5, 6, 7 都重傳。 B的確認(rèn)RR 0出錯：A計時器超時， 傳輸一個RR(P=