第10章_檢錯與糾錯_第1頁
第10章_檢錯與糾錯_第2頁
第10章_檢錯與糾錯_第3頁
第10章_檢錯與糾錯_第4頁
第10章_檢錯與糾錯_第5頁
已閱讀5頁,還剩62頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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

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

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

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

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

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

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

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

9、heck) 使碼字中“1”的個數(shù)保持偶數(shù)。l奇校驗(yàn)(odd-parity check) 使碼字中“1”的個數(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時的“簡單奇偶校驗(yàn)碼” C(3,2)和C(5,4)。l可以證明C(3,2)和C(5,4)編碼方案的最小漢明距離都是dmin=2。l根據(jù)檢錯定理,這種編碼只能檢測出單個位的差錯,且不能糾正任何差錯。l實(shí)際上,簡單奇偶校驗(yàn)碼可以檢測出發(fā)生奇數(shù)個差錯出現(xiàn)的問題,但不能檢測出發(fā)生偶數(shù)個差錯的問題。lP1

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

11、另加一個奇校驗(yàn)位或偶校驗(yàn)位) 水平奇偶校驗(yàn)又稱水平奇偶校驗(yàn)又稱“列奇偶校驗(yàn)列奇偶校驗(yàn)” 。 P183 圖10.11au水平奇偶校驗(yàn)(列奇偶校驗(yàn))差錯漏檢率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,但如某個信息段中出現(xiàn)偶數(shù)個差錯,而另一個信息段的對應(yīng)位置處也正好都出現(xiàn)差錯,這種差錯無法檢測出來。l一種最有效的冗余校驗(yàn)技術(shù)。l與基于加法的奇偶校驗(yàn)不同,CRC基于二進(jìn)制除法。l在

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

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

14、生的余數(shù)非0則被拒收。 “循環(huán)冗余碼”的產(chǎn)生使用所謂“模2”除法按位作異或運(yùn)算。右圖為其過程示意。P187 圖10.15l產(chǎn)生“循環(huán)冗余碼”的除數(shù)通常不是用0和1二進(jìn)制位串表示,而是用一個代數(shù)多項式(稱為“生成多項式”)表示。使用生成多項式的原因有兩個:簡短,且可從數(shù)學(xué)角度驗(yàn)證有關(guān)概念。(進(jìn)行多項式除法時,只要對其相應(yīng)系數(shù)相除即可)。參見P190 圖10.21l常用的“循環(huán)冗余碼”生成多項式已有三個國際標(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-國際電信聯(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)參見P195 表10.7有資料指出,如果使用CRC-16或CRC-ITU為生成多項式(即發(fā)生器產(chǎn)生16位數(shù)作循環(huán)冗余校驗(yàn)),可以查出全部一位差錯、雙位差錯、奇數(shù)位差錯,全部16位或16位以下突發(fā)差錯,99.99

16、7%的17位突發(fā)差錯及99.998%的18位或更長的突發(fā)差錯;傳輸速率為9600 bps時,數(shù)據(jù)傳輸3000年才會有一個差錯漏檢。l高層協(xié)議中使用的差錯檢測技術(shù)稱為“校驗(yàn)和技術(shù)” 。校驗(yàn)和技術(shù)也是建立在冗余技術(shù)的概念上的。l校驗(yàn)和技術(shù)原理 在發(fā)送端,由校驗(yàn)和發(fā)生器將數(shù)據(jù)分成相同的n位數(shù)據(jù)段(通常是16位)。然后以每兩個字節(jié)為1個單位相加,若相加的結(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 個分段,每段n個比特n以反碼

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

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

19、種不同的狀態(tài)(000 -111)。l實(shí)際上,3位冗余是不夠的。因?yàn)?,冗余位本身也可能出現(xiàn)差錯!l如何計算為m位數(shù)據(jù)糾錯時所需的冗余位數(shù) r 呢? l此時數(shù)據(jù)傳輸?shù)目偽粩?shù)是m+r,且要求 r必須能夠至少表示 m+r+1 種狀態(tài)。其中,一種狀態(tài)表示無差錯,m+r 種狀態(tài)分別表示在 m+r 位每個位置上發(fā)生的差錯。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 值及其對應(yīng)的 r 值。l冗余位的定位冗余位的定位 漢明碼可用于任何長度的數(shù)據(jù)塊,并利用了上面討論的數(shù)據(jù)位數(shù)和冗余位數(shù)的關(guān)系。例如,一個7位ASCII碼要求4個冗余位,它們可以附加在數(shù)據(jù)位的后面,亦可散布在數(shù)據(jù)位之中。下圖中,各冗余位處于第1、2、4、8位(2的n次方處),分別用r1,r2,r4,r8表示。l在漢明碼中,每一個r位都是一組數(shù)據(jù)位的奇偶校驗(yàn)碼。用于計算7數(shù)據(jù)位4個r值(奇偶校驗(yàn)碼)的方案

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論