差錯控制課件

差錯控制(信道編碼)

差錯控制的方式采用檢錯碼的差錯控制采用糾錯碼的差錯控制不用編碼的差錯控制關(guān)于幀或分組順序的差錯控制*網(wǎng)絡(luò)基礎(chǔ)數(shù)據(jù)通信中的實(shí)際情況*網(wǎng)絡(luò)基礎(chǔ)通信信道中的噪聲通信信道中的噪聲分為熱噪聲和沖擊噪聲。熱噪聲是由傳輸媒體的電子熱運(yùn)動產(chǎn)生的，其特點(diǎn)是時刻存在，幅度小，干擾強(qiáng)度與頻率無關(guān)，但頻譜很寬，屬于隨機(jī)噪聲。由熱噪聲引起的差錯屬于一種隨機(jī)差錯。沖擊噪聲是由外界電磁干擾引起的，與熱噪聲相比，沖擊噪聲的幅度較大，是引起差錯的主要原因。沖擊噪聲持續(xù)時間與數(shù)據(jù)傳輸中每個比特的發(fā)送時間相比，可能較長，因而沖擊噪聲引起的相鄰多個數(shù)據(jù)位出錯呈突發(fā)性。沖擊噪聲引起的傳輸差錯稱為突發(fā)差錯。*網(wǎng)絡(luò)基礎(chǔ)差錯產(chǎn)生的原因在通信過程中出現(xiàn)的傳輸差錯，是由隨機(jī)差錯和突發(fā)差錯共同構(gòu)成的，而造成差錯可能的原因包括：在數(shù)據(jù)通信中，信號在物理信道上的線路本身的電氣特性隨機(jī)產(chǎn)生的信號幅度、頻率、相位的畸形和衰減；電氣信號在線路上產(chǎn)生反射噪聲的回波效應(yīng)；相鄰線路之間的串線干擾；大氣中的閃電、電源開關(guān)的跳火、自然界磁場的變化以及電源的波動等外界因素。*網(wǎng)絡(luò)基礎(chǔ)差錯的控制在數(shù)據(jù)通信中，原發(fā)送信息，不具備抗干擾性能，如果引入冗余度后，就可以使新的碼組具有一定的抗干擾能力。例如，兩個碼元構(gòu)成四種碼組00、01、10、11，無法檢錯，而使用三個碼元，有用碼組為000、011、101和110；目前差錯控制常采用冗余編碼方案，檢測和糾正信息傳輸中產(chǎn)生的錯誤。冗余編碼思想就是：把要發(fā)送的有效數(shù)據(jù)在發(fā)送時按照所使用的某種差錯編碼規(guī)則加上控制碼（冗余碼），當(dāng)信息到達(dá)接收端后，再按照相應(yīng)的校驗(yàn)規(guī)則檢驗(yàn)收到的信息是否正確。差錯控制的基本工作方式前向糾錯方式FEC發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。特點(diǎn)是單向傳輸，實(shí)時性好，但譯碼設(shè)備較復(fù)雜。檢錯重發(fā)方式ARQ發(fā)端發(fā)送檢錯碼，收端收到信碼后能夠檢查出錯誤。混合糾錯方式HEC是FEC和ARQ方式的結(jié)合。信息反饋方式IF收端將接收的消息原封不動地送回發(fā)端，由發(fā)端將反饋信息和原發(fā)送信息進(jìn)行比較，發(fā)現(xiàn)錯誤進(jìn)行重發(fā)，其優(yōu)點(diǎn)是方法和設(shè)備簡單，無需糾（檢）錯編譯系統(tǒng)。差錯控制的基本工作方式對于不同類型的信道，應(yīng)采用不同的差錯控制技術(shù)，否則就將事倍功半。

檢錯重發(fā)可用于雙向數(shù)據(jù)通信，前向糾錯則用于單向數(shù)字信號的傳輸，例如廣播數(shù)字電視系統(tǒng)，因?yàn)檫@種系統(tǒng)沒有反饋通道。檢錯重發(fā)（ARQ）典型系統(tǒng)檢錯重發(fā)方式的原理方框圖常用的檢錯重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)。*網(wǎng)絡(luò)基礎(chǔ)檢錯重發(fā)（ARQ）1、檢錯重發(fā)（ARQ）（1）思路發(fā)送端對數(shù)據(jù)序列進(jìn)行分組編碼，加入一定的碼元使之具有一定的檢錯能力，成為能夠發(fā)現(xiàn)錯誤的碼組。接收端收到碼組后，按一定規(guī)則對其進(jìn)行有無錯誤的判別，并把判決結(jié)果（應(yīng)答信號）通過反向信道送回發(fā)送端。如有錯誤，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為已正確接收到信息為止。（2）重發(fā)方式（3種形式）：·停發(fā)等候重發(fā)·返回重發(fā)·選擇重發(fā)*網(wǎng)絡(luò)基礎(chǔ)連續(xù)ARQ協(xié)議工作原理發(fā)送方發(fā)完一幀后，不必停下來等待對方的應(yīng)答，可以連續(xù)發(fā)送若干幀；如果在發(fā)送過程中收到接收方的肯定應(yīng)答，可以繼續(xù)發(fā)送；若收到對其中某一幀的否認(rèn)幀，則使用某種ARQ方式重發(fā)數(shù)據(jù)；優(yōu)點(diǎn)連續(xù)發(fā)送提高了信道利用率；連續(xù)ARQ協(xié)議包括選擇ARQGo-Back-NARQ*網(wǎng)絡(luò)基礎(chǔ)ARQ*網(wǎng)絡(luò)基礎(chǔ)選擇ARQ與Go-Back-N的比較采用選擇ARQ方式時，由于接收到的數(shù)據(jù)幀有可能是亂序的，因此，接收端必須提供足夠的緩存先將每個數(shù)據(jù)幀保存下來，然后對數(shù)據(jù)幀重新排序。但由于該方式僅重發(fā)出錯的數(shù)據(jù)幀，因此，信道利用率高。對于Go-Back-N方式，接收到的數(shù)據(jù)幀是按順序排列的，因而接收端不需要太多的緩存，但由于發(fā)送端要將出錯數(shù)據(jù)之后的已發(fā)送數(shù)據(jù)幀重新發(fā)送，致使信道利用率相對較低。*網(wǎng)絡(luò)基礎(chǔ)三種重發(fā)方式的比較

停發(fā)等候重發(fā)返回重發(fā)選擇重發(fā)發(fā)送方式停止等待發(fā)送連續(xù)發(fā)送連續(xù)發(fā)送傳輸效率最低比較高最高控制方法簡單比較簡單比較復(fù)雜緩沖存儲器發(fā)送端有發(fā)送端有發(fā)送和接收端都要求有成本低比較低比較高*網(wǎng)絡(luò)基礎(chǔ)ARQ的優(yōu)缺點(diǎn)（3）ARQ的優(yōu)缺點(diǎn)·需反向信道，實(shí)時性差。

·編碼效率較高?！ぷg碼設(shè)備較簡單。

*網(wǎng)絡(luò)基礎(chǔ)前向糾錯（FEC）2、前向糾錯（FEC）思路前向糾錯系統(tǒng)中，發(fā)送端的信道編碼器將輸入數(shù)據(jù)序列變換成能夠糾正錯誤的碼，接收端的譯碼器根據(jù)編碼規(guī)律檢驗(yàn)出錯誤的位置并自動糾正。優(yōu)點(diǎn)：不需要反向信道，實(shí)時性好。缺點(diǎn)：1、所選擇的糾錯碼必須與信道的錯碼特性密切配合，否則很難達(dá)到降低錯碼率的要求；2、為了糾正較多的錯碼，譯碼設(shè)備復(fù)雜；3、要求附加的監(jiān)督碼也較多，傳輸效率較低。*網(wǎng)絡(luò)基礎(chǔ)例1：某數(shù)據(jù)通信系統(tǒng)采用停發(fā)等候重發(fā)的差錯控制方式，請?jiān)谙聢D的“？”處填入ACK、NAK或碼組號。

*網(wǎng)絡(luò)基礎(chǔ)例2：某數(shù)據(jù)通信系統(tǒng)采用選擇重發(fā)的差錯控制方式，發(fā)送端要向接收端發(fā)送7個碼組（序號0∽6），其中1號碼組出錯，請?jiān)谙聢D中的空格里填入正確的碼組號。

*網(wǎng)絡(luò)基礎(chǔ)例3：某數(shù)據(jù)通信系統(tǒng)采用返回重發(fā)的差錯控制方式，發(fā)送端要向接收端發(fā)送8個碼組（序號0∽7），其中1號碼組出錯，請?jiān)谙聢D中的空格里填入正確的碼組號。

差錯控制編碼的基本原理差錯編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關(guān)系加以校驗(yàn)，以檢測和糾正錯誤，增加冗余碼的個數(shù)可增加糾檢錯能力。信息碼元、監(jiān)督碼元

信息碼元又稱信息序列或信息位，這是發(fā)端由信源編碼后得到的被傳送的信息數(shù)據(jù)比特，通常以k表示。監(jiān)督碼元又稱監(jiān)督位或附加數(shù)據(jù)比特，這是為了檢糾錯碼而在信道編碼時加入的判斷數(shù)據(jù)位。通常以r表示，即為：

n=k+r或r=n－k經(jīng)過分組編碼后的碼又稱為(n,k)碼，即表示總碼長為n位，其中信息碼長(碼元數(shù))為k位，監(jiān)督碼長(碼元數(shù))為r=n－k。通常稱其為長為n的碼字(或碼組、碼矢)。

碼長、碼重、碼距編碼碼組的碼元總位數(shù)稱為碼組的長度，簡稱碼長。碼組中，“1”碼元的數(shù)目稱為碼組的重量，簡稱碼重。兩個等長碼組之間對應(yīng)位上碼元不同的數(shù)目稱為這兩個碼組的距離，簡稱碼距。碼距又稱漢明距。通常用d表示。各碼組之間距離最小值稱為最小碼距，通常用d0表示。*網(wǎng)絡(luò)基礎(chǔ)最小碼距與檢糾錯能力的關(guān)系

①在一個碼組內(nèi)為了檢測e個誤碼，要求最小碼距應(yīng)滿足：

d0≥e＋1

②在一個碼組內(nèi)為了糾正t個誤碼，要求最小碼距應(yīng)滿足：

d0≥2t＋1

③在一個碼組內(nèi)為了糾正t個誤碼，同時能檢測e個誤碼(e＞t)，要求最小碼距應(yīng)滿足：

d0≥e＋t＋1；*網(wǎng)絡(luò)基礎(chǔ)差錯編碼差錯檢測編碼：奇偶校驗(yàn)碼；水平垂直奇偶校驗(yàn)碼；恒比碼CRC循環(huán)冗余碼等；差錯糾錯編碼：漢明碼；卷積碼；*網(wǎng)絡(luò)基礎(chǔ)奇偶校驗(yàn)碼采用奇偶校驗(yàn)法，在每個字符的數(shù)據(jù)位傳輸之前，先檢測并計(jì)算奇偶校驗(yàn)位，然后將其附加在后；根據(jù)采用的奇偶校驗(yàn)位是奇數(shù)還是偶數(shù)，推出一個字符包含“1”的數(shù)目，接收機(jī)重新計(jì)算收到字符的奇偶校驗(yàn)位，并確定該字符是否出現(xiàn)傳輸差錯；若每個字符只采用一個奇偶校驗(yàn)位時，只能發(fā)現(xiàn)單個比特差錯，如果有兩個或兩個以上比特出錯，奇偶校驗(yàn)位無效；異步傳輸和面向字符的同步傳輸均采用奇偶校驗(yàn)技術(shù)；多用于計(jì)算機(jī)內(nèi)部數(shù)據(jù)校驗(yàn)。

*網(wǎng)絡(luò)基礎(chǔ)循環(huán)冗余碼CRCCRC是一種較為復(fù)雜的校驗(yàn)方法，它先將要發(fā)送的信息數(shù)據(jù)與一個通信雙方共同約定的數(shù)據(jù)進(jìn)行除法運(yùn)算，并根據(jù)余數(shù)得出一個校驗(yàn)碼，然后將這個校驗(yàn)碼附加在信息數(shù)據(jù)幀之后發(fā)送出去。接收端接收數(shù)據(jù)后，將包括校驗(yàn)碼在內(nèi)的數(shù)據(jù)幀再與約定的數(shù)據(jù)進(jìn)行除法運(yùn)算，若余數(shù)為“0”，就表示接收的數(shù)據(jù)正確，若余數(shù)不為“0”，則表明數(shù)據(jù)在傳輸?shù)倪^程中出錯。*網(wǎng)絡(luò)基礎(chǔ)循環(huán)冗余校驗(yàn)碼(CRC)所謂循環(huán)碼是這樣一組代碼,其中任一有效碼字經(jīng)過循環(huán)移位后得到的碼字仍然是有效碼字,不論是右移或左移,也不論移多少位。例如,若(an-1an-2…a1a0)是有效碼字,則(an-2an-3…a0an-1),(an-3an-4…an-1an-2),…,等都是有效碼字。循環(huán)冗余校驗(yàn)碼是一種循環(huán)碼,它有很強(qiáng)的糾錯檢錯能力,而且硬件實(shí)現(xiàn)很容易,在局域網(wǎng)中有廣泛的應(yīng)用。它所約定的校驗(yàn)規(guī)則是：讓校驗(yàn)碼能為某一約定代碼所除盡；如果除得盡，表明代碼正確；如果除不盡，余數(shù)將指明出錯位所在位置。*網(wǎng)絡(luò)基礎(chǔ)CRC校驗(yàn)碼編碼過程取k位信息碼，再將其左移r位，得到k+r位二進(jìn)制碼；用生成碼去模2除（異或）該二進(jìn)制碼，得到r為余數(shù)。該余數(shù)即為所得校驗(yàn)碼；將該校驗(yàn)碼加在原信息碼后，就構(gòu)成待傳輸?shù)膋+r位CRC碼（信息碼加校驗(yàn)碼）?！?運(yùn)算:

用模2運(yùn)算進(jìn)行加法時不進(jìn)位，減法和加法是一樣的。例如：1111＋1010＝0101*網(wǎng)絡(luò)基礎(chǔ)CRC碼的譯碼過程接收端譯碼要求有兩個：檢錯和糾錯。檢錯：原理和操作都很簡單。以生成多項(xiàng)式G(x)對應(yīng)的代碼去模2除收到的代碼，即T’(x)對應(yīng)的代碼，若余數(shù)為0，則說明傳輸過程無差錯，否則有差錯。*網(wǎng)絡(luò)基礎(chǔ)編碼：信息序列對應(yīng)的碼多項(xiàng)式為K(x)＝x6+x3+1xr.K(x)＝x9+x6+x3，對應(yīng)的代碼為1001001000(相當(dāng)于信息碼左移3位)選生成多項(xiàng)式G(x)＝x3+x2+1，對應(yīng)的碼多項(xiàng)式為1101

應(yīng)用舉例*網(wǎng)絡(luò)基礎(chǔ)100100100011011101

10001101

10101101

11111101

10001101

10101101

1111111011余數(shù)運(yùn)算演示：*網(wǎng)絡(luò)基礎(chǔ)編碼結(jié)果：得到檢驗(yàn)序列111。因此傳輸?shù)拇a序列為1001001111,碼多項(xiàng)式為T(x)。譯碼：如收到的代碼為1001001111，則用其除以生成多項(xiàng)式對應(yīng)的代碼1101，得余數(shù)為0(讀者自己驗(yàn)證)。說明信息在傳輸過程中沒錯，將最后的r位校驗(yàn)位碼“111”去掉，就得到信息碼。*網(wǎng)絡(luò)基礎(chǔ)譯碼并糾錯：若收到的T’(x)代碼為1001001101，按原過程計(jì)算，將其除以生成多項(xiàng)式對應(yīng)的代碼1101，得余數(shù)為10(如下頁)。這就說明傳輸有差錯，差錯e(x)=x，其代碼為10。將其糾正1001001101+10=1001001111*網(wǎng)絡(luò)基礎(chǔ)100100110111011101

10001101

10101101

11111101

10101101

11111101

0101111011運(yùn)算演示：*網(wǎng)絡(luò)基礎(chǔ)

糾錯依據(jù)：更換不同值的M(x)可以證明,出錯模式只與碼制和選用的G(x)有關(guān),與M(x)代碼值無關(guān)。據(jù)此可作為該種碼制的糾錯依據(jù)。a1a2a3a4a5a6a7

余數(shù)

出錯位

正確1100010000

無

出錯1100011110000011001101101010111001010000100

1000100010101000111101111017654321(7,4)制CRC碼的出錯模式表(G(x)=1011)*網(wǎng)絡(luò)基礎(chǔ)

CRC碼的特點(diǎn)CRC碼是面向數(shù)據(jù)幀編碼檢錯；理論證明，循環(huán)冗余檢驗(yàn)碼能夠檢驗(yàn)出：全部奇數(shù)個錯、全部偶數(shù)位錯和全部小于、等于冗余位數(shù)的突發(fā)性錯誤；理論證明,余數(shù)代碼與出錯位序號之間有唯一的對應(yīng)關(guān)系，據(jù)此，CRC有糾錯功能；一旦G(x)選定，CRC碼對幀內(nèi)有(r+1)bit出錯時無法糾錯；使用CRC技術(shù)只能做到無差錯接受(不包括丟失幀),可靠傳輸需加上確認(rèn)重傳機(jī)制。*網(wǎng)絡(luò)基礎(chǔ)由以上分析可知，只要選擇足夠的冗余位，就可以使得漏檢率減少到任意小的程度。廣泛使用的生成碼多項(xiàng)式主要有以下四種：CRC12＝x12+x11+x3+x2+x

+1CRC16＝x16+x15+x2+１(IBM公司)CRC16＝x16+x12+x5+１(ITU-T)CRC32＝X32+x26+x23+x22+x16++x11+x10+x8+x7+x5+x4+x2+x+13.線性分組碼線性分組碼的定義和特點(diǎn)線性分組碼，是指信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示的分組碼，即在（n，d）分組碼中，每一個監(jiān)督碼元都是碼組中某些信息碼元按模2和而得到的，線性分組碼是一類重要的糾錯碼，應(yīng)用很廣。漢明碼漢明碼是一類常見的線性分組碼，是一種能夠糾正單個錯誤的完備碼。要糾正碼組中的單個錯誤，則要求與單個錯誤圖樣對應(yīng)的伴隨式各不相同，且不能為全零。若碼長為n，監(jiān)督碼元的個數(shù)為r，則要求2r-1≥n。碼組為漢明碼時取等號。即用來糾正單個錯誤時，漢明碼所用的監(jiān)督碼元個數(shù)最少，效率最高。循環(huán)碼循環(huán)碼是另一類重要的線性分組碼，它除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。CRC碼的原理如果有r個校驗(yàn)碼元，其中每一個校驗(yàn)碼元是該碼元組中某些信息碼元的模2和，由此組成的一組長為n=k+r的碼，稱為線性碼，假定我們構(gòu)成(n=7,k=3)這樣的線性碼，若已知三個信息碼元為C6、C5和C4，而校驗(yàn)碼元C3、C2、C1和C0是未知的。校驗(yàn)碼元與信息碼元間的關(guān)系是根據(jù)以下四個線性關(guān)系式確立的。

CRC碼的原理CRC碼的原理按上頁編出的線性碼息碼元碼組C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100CRC碼的原理當(dāng)我們從表中任意挑選出兩個碼組時，將對應(yīng)比特按模2相加，所得到的新碼組仍然是上頁表中的某一碼組。這說明由8個碼字組成的線性碼具有封閉性。封閉性是線性碼的一個重要特性。CRC碼的原理假設(shè)待傳送的數(shù)據(jù)M

（kbit）。我們在M的后面再添加供差錯檢測用的rbit冗余碼一起發(fā)送。用二進(jìn)制的模

2

運(yùn)算進(jìn)行2r乘M的運(yùn)算，這相當(dāng)于在M后面添加r個0。得到的(k+r)bit的數(shù)除以事先選定好的長度為(r+1)bit的數(shù)G，得出商是Q而余數(shù)是R，余數(shù)R比除數(shù)G至少要少1個比特。例子設(shè)

M=1010001101，r=5,G=110101，模2運(yùn)算的結(jié)果是：商Q=1101010110，余數(shù)R=01110。將余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或2rM+R。例子

1101010110

←

Q

商

除數(shù)

P→

110101101000110100000

←

2nM被除數(shù)

110101

111011