第10章_檢錯(cuò)與糾錯(cuò)

1、P.174 本章學(xué)習(xí)如何檢測(cè)和糾正數(shù)據(jù)傳輸中“位差錯(cuò)”。l本章研究：l“位差錯(cuò)”的概念和類型l檢錯(cuò)技術(shù)基本原理l三種常用的檢錯(cuò)技術(shù)l奇偶校驗(yàn)技術(shù)l循環(huán)冗余校驗(yàn)技術(shù)l校驗(yàn)和技術(shù)l漢明碼糾錯(cuò)技術(shù)本章僅講技術(shù)原理，數(shù)學(xué)細(xì)節(jié)留給大家自己去深入1 差錯(cuò)類型差錯(cuò)類型 Types of Error 2 差錯(cuò)檢測(cè)差錯(cuò)檢測(cè) Error Detection3 差錯(cuò)糾正差錯(cuò)糾正 Error Detection l傳輸中差錯(cuò)是不可避免的。所以必須檢測(cè)和糾正比特流在傳輸中出現(xiàn)的“位差錯(cuò)”。l所謂“位差錯(cuò)” ，就是指將數(shù)據(jù)從一個(gè)節(jié)點(diǎn)傳送到下一個(gè)節(jié)點(diǎn)的過(guò)程中，數(shù)據(jù)中的一位（比特）或多位發(fā)生了改變。l“位差錯(cuò)”檢測(cè)的基本原理

2、是“冗余校檢技術(shù)”。l檢錯(cuò)技術(shù)的基本要求：檢錯(cuò)技術(shù)的基本要求：接收方應(yīng)在不知道實(shí)際發(fā)送的數(shù)據(jù)的情況下，能發(fā)現(xiàn)所接收到的數(shù)據(jù)是否有錯(cuò)。l在計(jì)算機(jī)通信中，通常是先檢錯(cuò)，發(fā)現(xiàn)差錯(cuò)時(shí)不是對(duì)有錯(cuò)的數(shù)據(jù)進(jìn)行糾錯(cuò)，而是丟棄有差錯(cuò)的數(shù)據(jù)，并通過(guò)“重傳”（將數(shù)據(jù)重新發(fā)送一遍）實(shí)現(xiàn)糾錯(cuò)。l無(wú)論是檢錯(cuò)還是糾錯(cuò)技術(shù)，都是數(shù)學(xué)研究的成果。l信號(hào)在物理信道中傳輸時(shí)，線路本身電器特性造成的隨機(jī)噪聲、信號(hào)幅度的衰減、頻率和相位的畸變、電器信號(hào)在線路上產(chǎn)生反射造成的回音效應(yīng)、相鄰線路間的串?dāng)_以及各種外界因素（如大氣中的閃電、開關(guān)的跳火、外界強(qiáng)電流磁場(chǎng)的變化、電源的波動(dòng)等）都會(huì)造成傳輸信號(hào)的失真。l在數(shù)據(jù)通信中，以上原因?qū)?huì)使接

3、收端收到的二進(jìn)制數(shù)位和發(fā)送端實(shí)際發(fā)送的二進(jìn)制數(shù)位不太一致，從而造成由“0”變成“1”或由“1”變成“0”的差錯(cuò)。l信道本身的隨機(jī)熱噪聲 隨機(jī)錯(cuò)誤(某位錯(cuò)）,可通過(guò)提高信道的信噪比等方法來(lái)抑制l外界原因引起的沖擊噪聲 突發(fā)錯(cuò)誤（一連串碼元均出錯(cuò)）【突發(fā)長(zhǎng)度】從突發(fā)錯(cuò)誤發(fā)生的第一個(gè)碼元到有錯(cuò)的最后一個(gè)碼元間所有碼元的個(gè)數(shù) 一位差錯(cuò)：數(shù)據(jù)單元中僅某一位差錯(cuò)多位差錯(cuò)：數(shù)據(jù)單元中兩位或兩位以上差錯(cuò)突發(fā)差錯(cuò)：數(shù)據(jù)單元中連續(xù)兩位或兩位以上差錯(cuò)。受影響的位數(shù)取決于數(shù)據(jù)速度和噪聲的持續(xù)時(shí)間。參見(jiàn)P174-175圖10.1, 圖10.2 發(fā)生差錯(cuò)的碼元數(shù) Pe = 接收的總碼元數(shù) 在計(jì)算機(jī)網(wǎng)絡(luò)中，誤碼率一般要求低

4、于10-6。l實(shí)現(xiàn)差錯(cuò)檢測(cè)的基本思路 發(fā)送方添加一些附加的比特作為差錯(cuò)檢測(cè)碼l從最簡(jiǎn)單的做法說(shuō)起l問(wèn)題：知道了可能發(fā)生的差錯(cuò)類型，如何把它們檢測(cè)出來(lái)？l一種可用的方法：將每個(gè)數(shù)據(jù)單元發(fā)送兩次。如輸入密碼或告訴對(duì)方電話號(hào)碼兩遍。l缺點(diǎn)：這樣做將使數(shù)據(jù)傳送速率奇慢傳輸時(shí)間將要增加一倍，需花費(fèi)大量時(shí)間進(jìn)行逐個(gè)比特的比較。l使用“冗余校驗(yàn)技術(shù)” 最常用的技術(shù)是在每個(gè)數(shù)據(jù)單元中加入一些稱為“冗余位”的附加比特（即“差錯(cuò)控制編碼差錯(cuò)控制編碼”）。 這種技術(shù)之所以被稱為“冗余校驗(yàn)技術(shù)”,因?yàn)橐坏﹤鬏敱淮_認(rèn)無(wú)誤，那些附加的冗余數(shù)位便被自動(dòng)丟棄。 （第二遍給出的密碼或電話號(hào)碼即為“冗余位”） 數(shù)據(jù)位數(shù)據(jù)位要發(fā)送

5、的數(shù)據(jù) 冗余位冗余位差錯(cuò)控制編碼 碼碼 字字codewordl數(shù)據(jù)字：報(bào)文劃成的數(shù)據(jù)塊（假設(shè)為k位）l碼字：數(shù)據(jù)字冗余位P17圖10.P175圖10.3差錯(cuò)控制編碼差錯(cuò)控制編碼可分為： 檢錯(cuò)碼檢錯(cuò)碼 用于自動(dòng)發(fā)現(xiàn)傳輸差錯(cuò)的編碼 糾錯(cuò)碼糾錯(cuò)碼 能自動(dòng)發(fā)現(xiàn)而且能自動(dòng)糾正傳輸差錯(cuò)的編碼 編碼效率計(jì)算編碼效率計(jì)算: : k k R= = k+r n 式中: k - 碼字中信息位數(shù) r - 碼字中冗余位數(shù) n - 碼字總位數(shù)差錯(cuò)控制的兩大目標(biāo)：差錯(cuò)控制的兩大目標(biāo)：l 盡量降低誤碼率盡量降低誤碼率 盡量提高編碼效率盡量提高編碼效率l又稱異或運(yùn)算(XOR), 計(jì)算機(jī)編碼常用。l運(yùn)算法則: l相同是0,不同是

6、1l或者視為沒(méi)有進(jìn)位的1和0的簡(jiǎn)單加法P176 圖10.4l漢明距離漢明距離 兩個(gè)碼字作XOR運(yùn)算，運(yùn)算結(jié)果中1的個(gè)數(shù)。 例 10.4 1. d(000,011)的漢明距離是2 2. d(10101,11110)的漢明距離是3l在信息論中，兩個(gè)等長(zhǎng)字符串之間的漢明距離是兩個(gè)字符串對(duì)應(yīng)位置的不同字符的個(gè)數(shù)。換句話說(shuō)，它就是將一個(gè)字符串變換成另外一個(gè)字符串所需要替換的字符個(gè)數(shù)。 例如： 1011101 與 1001001 之間的漢明距離是 2。 2143896 與 2233796 之間的漢明距離是 3。 “toned” 與 “roses” 之間的漢明距離是 3。l漢明距離是以美國(guó)數(shù)學(xué)家理查德衛(wèi)斯里

7、漢明(Richard Wesley Hamming,1915-1998)的名字命名的。l最小漢明距離最小漢明距離 有效碼字表中所以碼字對(duì)的最小漢明距離。 例10.5 求表10.1的最小漢明距離(dmin=2) 例10.6 求表10.2的最小漢明距離(dmin=3)l編碼方案三參數(shù)編碼方案三參數(shù) 碼字長(zhǎng)度n， 數(shù)據(jù)位長(zhǎng)度k，最小漢明距離dmin 寫法 C(n,k)和dmin=l檢錯(cuò)定理檢錯(cuò)定理 一個(gè)編碼方案的最小漢明距離如果是dmin=s+1，那么只能檢測(cè)出不多于s個(gè)的差錯(cuò)。l糾錯(cuò)定理糾錯(cuò)定理 一個(gè)編碼方案的最小漢明距離如果是dmin=2s+1，那么只能糾正不多于s個(gè)的差錯(cuò)。l奇偶校驗(yàn)l奇、偶位

8、值的加入，使字符中“1”的個(gè)數(shù)為偶數(shù)（“偶校驗(yàn)”）或奇數(shù)（“奇校驗(yàn)”）l無(wú)法檢測(cè)整數(shù)倍偶數(shù)個(gè)比特差錯(cuò)l使用奇偶校驗(yàn)并不是十分安全，因?yàn)樵肼暶}沖持續(xù)的時(shí)間經(jīng)常足以破壞一個(gè)以上的比特，特別是在數(shù)據(jù)率較高的情況下。l奇偶校驗(yàn)碼 通過(guò)增加冗余位使碼字中“1”的個(gè)數(shù)保持奇數(shù)或偶數(shù)的編碼方法。簡(jiǎn)單經(jīng)濟(jì)，但漏檢率較高。 垂直奇偶校驗(yàn) (簡(jiǎn)單奇偶校驗(yàn)，行奇偶校驗(yàn)) 水平奇偶校驗(yàn)（列奇偶校驗(yàn)） 水平垂直奇偶校驗(yàn)(兩維奇偶校驗(yàn))P176 圖10.4l垂直奇偶校驗(yàn)( “簡(jiǎn)單奇偶校驗(yàn)”或“行奇偶校驗(yàn)”) 編碼和校驗(yàn)實(shí)現(xiàn)最簡(jiǎn)單。 可以邊發(fā)送邊插入冗余位。 最常用而且最經(jīng)濟(jì)的檢錯(cuò)技術(shù)。l偶校驗(yàn)（even-parity c

9、heck） 使碼字中“1”的個(gè)數(shù)保持偶數(shù)。l奇校驗(yàn)（odd-parity check） 使碼字中“1”的個(gè)數(shù)保持奇數(shù)。偶校驗(yàn)位 p = (d1+d2+dn-1) = 奇校驗(yàn)位 p = (d1+d2+dn-1+1) =)2模(11niik)2模( 111niikl表10.1和表10.3分別是數(shù)據(jù)位為2和5時(shí)的“簡(jiǎn)單奇偶校驗(yàn)碼” C(3,2)和C(5,4)。l可以證明C(3,2)和C(5,4)編碼方案的最小漢明距離都是dmin=2。l根據(jù)檢錯(cuò)定理，這種編碼只能檢測(cè)出單個(gè)位的差錯(cuò)，且不能糾正任何差錯(cuò)。l實(shí)際上，簡(jiǎn)單奇偶校驗(yàn)碼可以檢測(cè)出發(fā)生奇數(shù)個(gè)差錯(cuò)出現(xiàn)的問(wèn)題，但不能檢測(cè)出發(fā)生偶數(shù)個(gè)差錯(cuò)的問(wèn)題。lP1

10、82 例10.12 (數(shù)據(jù)見(jiàn)下頁(yè))l如果接收到的碼字不在上表，則被拒收（檢錯(cuò)成功）l如果接收到的碼字在上表中，則被接收（無(wú)出錯(cuò)或漏檢）垂直奇偶校驗(yàn)可以檢測(cè)出所有的1位差錯(cuò)，但只能檢測(cè)差錯(cuò)數(shù)為奇數(shù)的多位差錯(cuò)或突發(fā)差錯(cuò)。差錯(cuò)漏檢率1/2?！纠吭紨?shù)據(jù)000111011，采用偶校驗(yàn)。 則發(fā)送端通過(guò)線路傳輸發(fā)出的碼字為1000111011。 若接收端接收到的是 1111111011 或0110111011 或 1100010011，將均被拒收。 但若接收端接收到的是1110111011或1100011011或 1000011010，仍會(huì)通過(guò)驗(yàn)收（漏檢）。 編碼效率 R： (設(shè)發(fā)送的數(shù)據(jù)為k位,發(fā)送時(shí)

11、另加一個(gè)奇校驗(yàn)位或偶校驗(yàn)位) 水平奇偶校驗(yàn)又稱水平奇偶校驗(yàn)又稱“列奇偶校驗(yàn)列奇偶校驗(yàn)” 。 P183 圖10.11au水平奇偶校驗(yàn)(列奇偶校驗(yàn))差錯(cuò)漏檢率1/2；編碼和校驗(yàn)實(shí)現(xiàn)復(fù)雜；不能邊發(fā)送邊生成并插入冗余位。l兩維奇偶校驗(yàn)編碼，又稱“水平垂直奇偶校驗(yàn)”。水平冗余校驗(yàn)位水平冗余校驗(yàn)位( (列奇偶位列奇偶位) )垂直冗余校驗(yàn)位垂直冗余校驗(yàn)位( (行奇偶位行奇偶位) )u誤碼率可減少到原誤碼率1/1001/10000，但如某個(gè)信息段中出現(xiàn)偶數(shù)個(gè)差錯(cuò)，而另一個(gè)信息段的對(duì)應(yīng)位置處也正好都出現(xiàn)差錯(cuò)，這種差錯(cuò)無(wú)法檢測(cè)出來(lái)。l一種最有效的冗余校驗(yàn)技術(shù)。l與基于加法的奇偶校驗(yàn)不同，CRC基于二進(jìn)制除法。l在

12、CRC中，不是把二進(jìn)制數(shù)位相加來(lái)獲得一個(gè)所需的奇偶數(shù)位，而是在數(shù)據(jù)單元（比如一個(gè)字節(jié)）的后面附加一個(gè)稱為“循環(huán)冗余碼循環(huán)冗余碼”或“CRC余數(shù)余數(shù)”的冗余比特串，使該數(shù)據(jù)單元可被另一個(gè)預(yù)先給定的二進(jìn)制數(shù)完全除盡。l接收端將所接收的數(shù)據(jù)單元用同樣的二進(jìn)制數(shù)相除，如果無(wú)余數(shù)，則可認(rèn)為所接收的數(shù)據(jù)單元正確無(wú)誤，如果有余數(shù)，則認(rèn)定該數(shù)據(jù)單元已有差錯(cuò)。lCRC所用的冗余位串是通過(guò)將數(shù)據(jù)單元除以預(yù)先給定的除數(shù)獲得。余數(shù)即為“循環(huán)冗余碼”。l一個(gè)有效的“循環(huán)冗余碼”應(yīng)具有兩種品質(zhì)：必須正好比給定的除數(shù)少一位，附加到數(shù)據(jù)串后必須使新形成的位串能被該除數(shù)完全除盡。l可靠性 除了正好數(shù)據(jù)塊的比特值是按除數(shù)值變化的

13、差錯(cuò)外，CRC將檢測(cè)出其他所有的差錯(cuò)。由于常用的CRC除數(shù)為13、17或是33個(gè)比特，所以誤碼的可能性幾乎為零。l假設(shè)給定除數(shù)的位數(shù)是n+1，首先在數(shù)據(jù)單元的末尾加上n個(gè)0。l用二進(jìn)制除法將加長(zhǎng)后的數(shù)據(jù)單元除以給定除數(shù)，得到的余數(shù)即為循環(huán)冗余編碼（CRC）。碼字碼字l用以上獲得的n位CRC碼替換數(shù)據(jù)單元附加的n個(gè)0，然后傳送。l如余數(shù)為0（被整除了），則以n位0為CRC碼（即不作替換）。l如果余數(shù)位數(shù)小于n，則最左邊的不足位數(shù)用0填充。l接收方收到數(shù)據(jù)單元和CRC后，將整個(gè)碼字除以給定除數(shù)（同生成CRC用的除數(shù)）。l如果到達(dá)的數(shù)據(jù)沒(méi)有差錯(cuò)，接收方CRC校驗(yàn)器產(chǎn)生的余數(shù)應(yīng)是0，數(shù)據(jù)被接收，如果產(chǎn)

14、生的余數(shù)非0則被拒收。 “循環(huán)冗余碼”的產(chǎn)生使用所謂“模2”除法按位作異或運(yùn)算。右圖為其過(guò)程示意。P187 圖10.15l產(chǎn)生“循環(huán)冗余碼”的除數(shù)通常不是用0和1二進(jìn)制位串表示，而是用一個(gè)代數(shù)多項(xiàng)式（稱為“生成多項(xiàng)式”）表示。使用生成多項(xiàng)式的原因有兩個(gè)：簡(jiǎn)短，且可從數(shù)學(xué)角度驗(yàn)證有關(guān)概念。（進(jìn)行多項(xiàng)式除法時(shí)，只要對(duì)其相應(yīng)系數(shù)相除即可）。參見(jiàn)P190 圖10.21l常用的“循環(huán)冗余碼”生成多項(xiàng)式已有三個(gè)國(guó)際標(biāo)準(zhǔn)： CRC-12 = x12+x11+x3+ x2+x+1 （13位除數(shù)：1100000001111） CRC-16= x16+x15+x2+1 （17位除數(shù)：110000000000001

15、01） CRC-ITU= x16+x12+x5+1 （ITU-國(guó)際電信聯(lián)盟） （17位除數(shù)：10001000000100001）l另外還有（在若干網(wǎng)絡(luò)協(xié)議中被規(guī)定為選件）： CRC-32=x32+x26+x23+ x22+ x16+ x12+ x11+ x10+ x8+ x7+ x5+x4+ x2+x+1 （33位除數(shù)：100000100110000010001110110110111）參見(jiàn)P195 表10.7有資料指出，如果使用CRC-16或CRC-ITU為生成多項(xiàng)式(即發(fā)生器產(chǎn)生16位數(shù)作循環(huán)冗余校驗(yàn)）,可以查出全部一位差錯(cuò)、雙位差錯(cuò)、奇數(shù)位差錯(cuò)，全部16位或16位以下突發(fā)差錯(cuò)，99.99

16、7%的17位突發(fā)差錯(cuò)及99.998%的18位或更長(zhǎng)的突發(fā)差錯(cuò)；傳輸速率為9600 bps時(shí)，數(shù)據(jù)傳輸3000年才會(huì)有一個(gè)差錯(cuò)漏檢。l高層協(xié)議中使用的差錯(cuò)檢測(cè)技術(shù)稱為“校驗(yàn)和技術(shù)” 。校驗(yàn)和技術(shù)也是建立在冗余技術(shù)的概念上的。l校驗(yàn)和技術(shù)原理 在發(fā)送端，由校驗(yàn)和發(fā)生器將數(shù)據(jù)分成相同的n位數(shù)據(jù)段（通常是16位）。然后以每?jī)蓚€(gè)字節(jié)為1個(gè)單位相加，若相加的結(jié)果有進(jìn)位，那么將和加1。如此反復(fù)，直到全部數(shù)據(jù)都相加完為止。將最后的和值取二進(jìn)制反碼，便得到16位的校驗(yàn)和。將此校驗(yàn)和作為冗余位附加在數(shù)據(jù)上發(fā)送給接收方以供校驗(yàn)。 為了生成校驗(yàn)和，發(fā)送方要做以下工作：n將數(shù)據(jù)單元分為 k 個(gè)分段，每段n個(gè)比特n以反碼

17、相加的規(guī)則將分段1和分段2相加起來(lái)n將分段3與以上求得的結(jié)果相加n將分段4與以上求得的結(jié)果相加n重復(fù)以上步驟，直到第 k 個(gè)分段也被相加為止n將最后結(jié)果取反，即得到該數(shù)據(jù)單元的校驗(yàn)和自動(dòng)請(qǐng)求重發(fā)自動(dòng)請(qǐng)求重發(fā) (ARQ , Automatic Repeat Request） 自動(dòng)發(fā)現(xiàn)差錯(cuò)并要求對(duì)方重發(fā)正向糾錯(cuò)正向糾錯(cuò) (FEC , Forward Error Correction） 自動(dòng)發(fā)現(xiàn)并糾正錯(cuò)誤lARQ只需檢錯(cuò)碼，編碼效率高，設(shè)備簡(jiǎn)單，但要求雙向信道，發(fā)送方要有數(shù)據(jù)緩沖區(qū)。lFEC要用糾錯(cuò)碼，編碼效率低，設(shè)備復(fù)雜，但實(shí)時(shí)性好，只需單向信道。 l理論上，自動(dòng)糾正每一個(gè)二進(jìn)制代碼的傳輸差錯(cuò)是可

18、以做到的。但糾錯(cuò)碼比檢錯(cuò)碼復(fù)雜得多，而且需要更多的冗余位。用于多位或突發(fā)差錯(cuò)糾錯(cuò)的位數(shù)太大的，以致大部分情況下，將使編碼效率低到不可接受的程度。為此，大部分糾錯(cuò)碼只限于處理1位、2位或3位差錯(cuò)。l在數(shù)據(jù)通信中，最常用的糾錯(cuò)碼是所謂“漢明碼”(Hamming Code），是貝爾實(shí)驗(yàn)室的科學(xué)家R.W.Hamming 于1950年提出的，主要用來(lái)糾正1位差錯(cuò)。l奇偶校驗(yàn)可以檢測(cè)出1位差錯(cuò)的情況，方法是加上一個(gè)冗余的奇校驗(yàn)位或偶校驗(yàn)位。糾錯(cuò)則需確定其中哪位有差錯(cuò)。l如果要確定一個(gè)ASCII字符（7位）中的某位差錯(cuò)，此時(shí)需要區(qū)別8種情況：沒(méi)差錯(cuò)，第1位錯(cuò)，第2位錯(cuò)，第7位錯(cuò)。于是，需要3個(gè)冗余位來(lái)表示8

19、種不同的狀態(tài)（000 -111）。l實(shí)際上，3位冗余是不夠的。因?yàn)椋哂辔槐旧硪部赡艹霈F(xiàn)差錯(cuò)！l如何計(jì)算為m位數(shù)據(jù)糾錯(cuò)時(shí)所需的冗余位數(shù) r 呢? l此時(shí)數(shù)據(jù)傳輸?shù)目偽粩?shù)是m+r，且要求 r必須能夠至少表示 m+r+1 種狀態(tài)。其中，一種狀態(tài)表示無(wú)差錯(cuò)，m+r 種狀態(tài)分別表示在 m+r 位每個(gè)位置上發(fā)生的差錯(cuò)。l由于r 位二進(jìn)制數(shù)可以表示2r種不同的狀態(tài),所以，2r必須大于或等于 m+r+1。 2 r m+r+1 如果m=7（ASCII代碼），則能滿足上式的最小 r 值是4。因?yàn)椋?24 7+4+11234567 2333444 356791011 下表為一些可能的 m 值及其對(duì)應(yīng)的 r 值。l冗余位的定位冗余位的定位 漢明碼可用于任何長(zhǎng)度的數(shù)據(jù)塊，并利用了上面討論的數(shù)據(jù)位數(shù)和冗余位數(shù)的關(guān)系。例如，一個(gè)7位ASCII碼要求4個(gè)冗余位，它們可以附加在數(shù)據(jù)位的后面，亦可散布在數(shù)據(jù)位之中。下圖中，各冗余位處于第1、2、4、8位（2的n次方處），分別用r1，r2，r4，r8表示。l在漢明碼中，每一個(gè)r位都是一組數(shù)據(jù)位的奇偶校驗(yàn)碼。用于計(jì)算7數(shù)據(jù)位4個(gè)r值（奇偶校驗(yàn)碼）的方案