數(shù)據(jù)通信第三章

第三章差錯控制數(shù)據(jù)通信要求信息傳輸具有高度的可靠性，即要求誤碼率足夠低。然而，誤碼是不可避免的。造成誤碼的原因很多，但主要原因可以歸結(jié)為兩個方面:123.1差錯控制的基本概念及原理信道不理想造成的符號間干擾——使接受波形發(fā)生畸變采樣判決時會造成碼間干擾?？赏ㄟ^均衡方法改善消除。噪聲對信號的干擾——噪聲疊加在接受波形上。消除噪聲干擾產(chǎn)生誤碼的方法就是進行差錯控制。3.1.1差錯控制的基本概念1.差錯分類

危害數(shù)據(jù)傳輸?shù)脑肼曈袃深悾阂活愂请S機噪聲：包括熱噪聲、散彈噪聲以及傳輸媒介引起的噪聲等，引起隨機差錯；另一類是脈沖噪聲：是指突然發(fā)生的噪聲，包括雷電、開關(guān)引起的瞬態(tài)變化以及機電交換機的撥號脈沖等，引起突發(fā)差錯。隨機差錯，又稱獨立差錯，它是指那些獨立地、稀疏地和互不相關(guān)地發(fā)生的差錯。存在這種差錯的信道稱為無記憶信道或隨機信道。產(chǎn)生的原因：隨機噪聲突發(fā)差錯是指一串串，甚至是成片出現(xiàn)的差錯，差錯之間有相關(guān)性，差錯出現(xiàn)是密集的。產(chǎn)生突發(fā)錯誤的信道稱為有記憶信道或突發(fā)信道。產(chǎn)生的原因：脈沖噪聲2.差錯控制的基本思路差錯控制的核心是抗干擾編碼，或差錯控制編碼，簡稱糾錯編碼，也稱信道編碼。差錯控制的基本思路是：

在發(fā)送端被傳送的信息碼序列（本身無規(guī)律）的基礎(chǔ)上，按照一定的規(guī)則加入若干監(jiān)督碼元后進行傳輸，這些加入的碼元與原來的信息碼序列之間存在著某種確定的約束關(guān)系。在接收數(shù)據(jù)時，檢驗信息碼元與監(jiān)督碼元之間的既定的約束關(guān)系，如該關(guān)系遭到破壞，則收端可以發(fā)現(xiàn)傳輸中的錯誤，乃至糾正錯誤。信息碼（k）+監(jiān)督碼（r）=碼組（n）加的監(jiān)督碼越多，差錯控制能力越強3.差錯控制的方法在數(shù)據(jù)通信系統(tǒng)中，差錯控制一般可以分為4種類型。如圖3-1所示:（1）檢錯重發(fā)檢錯重發(fā)簡稱（ARQ：自動重發(fā)請求）。這種差錯控制方式在發(fā)送端對數(shù)據(jù)序列進行分組編碼（如數(shù)據(jù)幀），加入一定多余碼元使之具有一定的檢錯能力，成為能夠發(fā)現(xiàn)錯誤的碼組。接收端收到碼組后按一定的規(guī)則進行有無差錯的判決并把判決結(jié)果通過反向信道送回發(fā)送端，如有差錯，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為正確接收到信息為止。能夠?qū)崿F(xiàn)差錯檢測和差錯恢復(fù)以及流量控制的功能。處理傳輸差錯的重發(fā)技術(shù)有：差錯檢測技術(shù)；確認(rèn)幀技術(shù)；否認(rèn)幀技術(shù)；差錯重發(fā)技術(shù)；超時重發(fā)技術(shù)。在具體實現(xiàn)檢錯重發(fā)系統(tǒng)時,通常有3種形式,即停等ARQ、返回重發(fā)ARQ和選擇重發(fā)ARQ。Stop-and-WaitARQ

基本思路：停等ARQ是指發(fā)送端發(fā)送一幀數(shù)據(jù)并啟動定時器，不能繼續(xù)發(fā)送后續(xù)幀，而是等待接收方的確認(rèn)幀或否認(rèn)幀。接收端收到數(shù)據(jù)幀后經(jīng)過檢驗如果沒有發(fā)現(xiàn)差錯，則向發(fā)送方返回一確認(rèn)幀（ACK），再處理數(shù)據(jù)幀并交給上層，發(fā)送端收到ACK后認(rèn)為該幀數(shù)據(jù)成功傳輸，取出下一幀再發(fā)送；如果接收方經(jīng)過檢驗，發(fā)現(xiàn)有差錯，則向發(fā)送端返回一否認(rèn)幀（NAK），并丟棄出錯幀，發(fā)送端收到NAK則認(rèn)為傳輸出差錯，則取出緩沖區(qū)里原來的數(shù)據(jù)進行重發(fā)。分為四種情況討論：

a.數(shù)據(jù)在傳輸?shù)倪^程中沒有出現(xiàn)差錯；

b.數(shù)據(jù)在傳輸過程中出現(xiàn)差錯；

c.數(shù)據(jù)幀丟失情況；

d.確認(rèn)幀（否認(rèn)幀）丟失的情況。發(fā)收ACK0正確發(fā)收NAK0錯誤重發(fā)發(fā)收重發(fā)超時重發(fā)正確發(fā)收重發(fā)正確ACK0超時重發(fā)正確重復(fù)幀(1)(2)(3)(4)01000000連續(xù)ARQ

基本思路：發(fā)送端連續(xù)地發(fā)送一系列的數(shù)據(jù)幀，而暫時不需要等待前面所發(fā)數(shù)據(jù)幀的確認(rèn)便發(fā)送下一幀。連續(xù)ARQ把等待時間利用起來，傳輸效率大大提高。傳輸信道是不可靠的，如果已經(jīng)連續(xù)發(fā)送到鏈路上的數(shù)據(jù)幀中，某一幀數(shù)據(jù)發(fā)生了差錯或丟失，在發(fā)送端發(fā)現(xiàn)已近出現(xiàn)差錯之前，很多后續(xù)幀就會達到接收端，接收端應(yīng)當(dāng)丟棄出錯數(shù)據(jù)幀，同時還必須保證發(fā)送順序交給上層，因此，接收端對后續(xù)正確的數(shù)據(jù)幀處理方式?jīng)Q定了發(fā)送端的重發(fā)機制，可將連續(xù)的ARQ分為返回重發(fā)ARQ和選擇性重發(fā)ARQ。返回重發(fā)012312345發(fā)6WT=7012312345收6WR=1丟棄等待1號幀交上層處理一般地，當(dāng)差錯檢測發(fā)現(xiàn)第I幀錯誤，則接收方給出否認(rèn)幀信息，并丟棄出錯幀及后續(xù)幀。發(fā)送方退回到第I幀，重發(fā)第I幀及I幀的后續(xù)幀。選擇性重發(fā)012314567發(fā)0WT>1012314567收0WR>1暫存緩存等待1號幀一起交上層處理ACK3③ARQ的優(yōu)缺點●需反向信道，實時性差?！馎RQ方式在信息碼后面所加的監(jiān)督碼不多，所以信息傳輸效率較高?！褡g碼設(shè)備較簡單（2）前向糾錯（FEC）①FEC的思路

前向糾錯系統(tǒng)中，發(fā)送端的信道編碼器將輸入數(shù)據(jù)序列變換成能夠糾正錯誤的碼，接收端的譯碼器根據(jù)編碼規(guī)律檢驗出錯誤的位置并自動糾正。②FEC的優(yōu)缺點●不需要反向信道，實時性好。●缺點是所選擇的糾錯碼必須與信道的錯碼特性密切配合，否則很難達到降低錯碼率的要求；●譯碼設(shè)備復(fù)雜；而要求附加的監(jiān)督碼也較多，傳輸效率就低。(3)混合糾錯檢錯（HEC）

①HEC的思路

混合糾錯檢錯方式是前向糾錯方式和檢錯重發(fā)方式的結(jié)合。在這種系統(tǒng)中，發(fā)送端發(fā)出同時具有檢錯和糾錯能力的碼，接收端收到碼后，檢查錯誤情況，如果錯誤少于糾錯能力，則自行糾正；如果干擾嚴(yán)重，錯誤很多，超出糾正能力，但能檢測出來，則經(jīng)反向信道要求發(fā)端重發(fā)。

②HEC的優(yōu)缺點

混合糾錯檢錯方式在實時性和譯碼復(fù)雜性方面是前向糾錯和檢錯重發(fā)方式的折衷，因而近年來，在數(shù)據(jù)通信系統(tǒng)中采用較多。(4)信息反饋（IRQ）①IRQ的思路

信息反饋方式(IRQ)在發(fā)送端不進行糾錯編碼，接收端把收到的數(shù)據(jù)序列全部由反向信道送回發(fā)端，發(fā)端自己比較發(fā)送的數(shù)據(jù)序列與送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)是否有錯誤，并把認(rèn)為錯誤的數(shù)據(jù)序列的原數(shù)據(jù)再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。②IRQ的優(yōu)缺點●這種方式的優(yōu)點是不需要糾錯、檢錯的編譯器，設(shè)備簡單。●缺點是需要和前向信道相同的反向信道，實時性差?！癜l(fā)送端需要一定容量的存儲器以存儲發(fā)送碼組，環(huán)路時延越大，數(shù)據(jù)速率越高，所需存儲容量越大。3.1.2差錯控制的基本原理1.差錯控制的原理

糾錯編碼之所以具有檢錯和糾錯能力，是因為在信息碼之外附加了監(jiān)督碼，即碼的檢錯和糾錯能力是用信息量的冗余度來換取的。加入監(jiān)督碼越多，碼的檢錯、糾錯能力越強，但信息傳輸效率下降也越多。在糾錯編碼中將信息傳輸效率也稱為編碼效率，定義為

k為信息位長度，n為編碼的總長度，n-k為監(jiān)督元的長度。R越大編碼效率越高，它是衡量碼性能的一個重要參數(shù)2.漢明距離與檢錯和糾錯能力的關(guān)系（1）幾個概念碼組的重量——碼組中非零碼元的數(shù)目為碼組的重量，簡稱碼重。碼距——把兩個碼組中對應(yīng)碼位上具有不同二進制碼元的個數(shù)定

義為兩碼組的距離，簡稱碼距。漢明距離——在一種編碼中，任意兩個許用碼組間距離的最小值，稱為這一編碼的漢明距離，以表示。3.差錯控制編碼的分類(1)按碼組的功能分,有檢錯碼和糾錯碼。(2)按監(jiān)督碼與信息碼元之間的關(guān)系分,有線性碼和非線性碼。(3)按照對信息碼元處理方法的不同分,有分組碼和卷積碼。(4)按照信息碼元在編碼前后是否保持原來的形式不變——可劃分為系統(tǒng)碼和非系統(tǒng)碼。（5）按糾正差錯的類型——可分為糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼。（6）按照每個碼元取值來分——可分為二進制碼與多進制碼。3.2簡單的差錯控制編碼3.2.1奇偶監(jiān)督碼1.基本概念

這是一種最簡單的檢錯碼,又稱奇偶校驗碼。其編碼規(guī)則是先將所要傳輸?shù)臄?shù)據(jù)碼元分組,在每組數(shù)據(jù)后面附加一位監(jiān)督位,使得該組碼連同監(jiān)督位在內(nèi)的碼組中的“1”的個數(shù)為偶數(shù)(稱為偶校驗)或奇數(shù)(稱為奇檢驗),在接收端按同樣的規(guī)律檢查,如發(fā)現(xiàn)不符就說明產(chǎn)生了差錯,但是不能確定差錯的具體位置,即不能糾錯。設(shè)碼組長度為n，表示為(

)，其中前n-1位為信息碼元，第n位為監(jiān)督位a0。偶檢驗的監(jiān)督關(guān)系在奇校驗的監(jiān)督關(guān)系2.檢錯能力(1）只能檢測奇數(shù)個錯誤，而不能檢測出偶數(shù)個錯誤。（2）適合檢測隨機差錯。3.2.1水平奇偶監(jiān)督碼

水平奇偶監(jiān)督碼的構(gòu)成思路是：將信息碼序列按行排成方陣，每行后面加一個奇或偶監(jiān)督編碼，即每行為一個奇偶監(jiān)督碼組(見表3-2，以偶監(jiān)督為例)，但發(fā)送時則按列的順序傳輸：111011100110000…10101，接收端仍將碼元排成與發(fā)送端一樣的方陣形式，然后按行進行奇偶校驗。注意：通常能查出不大于列長個比特的錯誤。3.2.2二維奇偶監(jiān)督碼

二維奇偶監(jiān)督碼是將水平奇偶監(jiān)督碼推廣而得，又稱水平垂直奇偶監(jiān)督碼、行列監(jiān)督碼和方陣碼。它的方法是在水平監(jiān)督基礎(chǔ)上對表3-2方陣中每一列再進行奇偶校驗，就可得表3-3（以偶監(jiān)督為例）所示的方陣。發(fā)送是按列或按行的順序傳輸。接收端重新將碼元排成發(fā)送時方陣形式，然后每行、每列都進行奇偶校驗。注意：能查出所有奇數(shù)個比特的錯誤。能查出部分偶數(shù)個比特的錯誤。具有一定的糾錯能力。3.3漢明碼及線性分組碼3.3.1漢明碼漢明碼是1950年由美國貝爾實驗室提出來的，是第一個設(shè)計用來糾正錯誤的線性分組碼，漢明碼及其變型已廣泛應(yīng)用于數(shù)字通信和數(shù)據(jù)存儲系統(tǒng)中作為差錯控制碼。

1.糾錯碼的監(jiān)督位與碼組長度的關(guān)系若碼長為n信息位數(shù)為k，則監(jiān)督位數(shù)r。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示一位錯碼的種可能位置，則要求2.(7,4)漢明碼設(shè)分組碼(n，k)中k＝4。為了糾正一位錯碼，要求監(jiān)督位數(shù)。若取，則。我們用表示這7個碼元，用表示三個監(jiān)督關(guān)系式中的校正子，則的值與錯碼位置的對應(yīng)關(guān)系可以規(guī)定如表4-4所列，構(gòu)成監(jiān)督關(guān)系，在發(fā)送端編碼時，信息位和的值決定于輸入信號。而監(jiān)督位和應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，

按照上述監(jiān)督關(guān)系所構(gòu)成的線性分組碼就是(7,4)漢明碼。（3）（7，4）漢明碼的漢明距離及編碼效率①漢明距離漢明碼屬于線性分組碼，根據(jù)線性分組碼的性質(zhì)可以求出（7，4）漢明碼的漢明距離。因此由式(3-2)和（3-3）可知，這種碼能糾正一個錯碼或檢測兩個錯碼。②編碼效率（7，4）漢明碼的編碼效率為3.3.2線性分組碼1.線性分組碼的概念線性碼是指監(jiān)督碼元與信息碼元之間滿足一組線性方程的碼；分組碼是監(jiān)督碼元僅對本碼組中的碼元起監(jiān)督作用，或者說監(jiān)督碼元僅與本碼組的信息碼元有關(guān)。既是線性碼又是分組碼的編碼就叫線性分組碼。2.線性分組碼的主要性質(zhì)(1)封閉性所謂封閉性，是指一種線性分組碼中的任意兩個碼組之逐位模2和仍為這種碼中的另一個許用碼組。(2)碼的最小距離等于非零碼的最小重量線性分組碼的生成矩陣線性分組碼的編碼生成矩陣的典型化線性分組碼的監(jiān)督矩陣監(jiān)督矩陣與生成矩陣之間的關(guān)系3.4循環(huán)碼循環(huán)碼是線性分組碼中一類重要的碼。3.4.1循環(huán)碼的循環(huán)特性1.碼的多項式若碼組，則相應(yīng)的多項式表示為

2.循環(huán)碼的循環(huán)特性循環(huán)碼的循環(huán)性是指循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后(將最右端的碼元移至左端，或反之)所得到的碼組仍為它的一個許用碼組。表3-6給出一種(7，3)循環(huán)碼的全部碼組，由此表可直觀看出這種碼的循環(huán)性。例如，表中的第2碼組向右循環(huán)移一位即得到第5碼組，第2碼組向左循環(huán)移一位即得到第3碼組。

（7，3）循環(huán)碼的一種碼組3.4.2循環(huán)碼的生成多項式和生成矩陣1.生成多項式g(x)2.生成矩陣G由循環(huán)碼的生成多項式g(x)可得到生成矩陣G(x)，為典型的生成矩陣為可以通過線性變換將非典型的生成矩陣轉(zhuǎn)換為典型的生成矩陣，具體方法是：任意幾行模二加取代某一行。3.4.3循環(huán)碼的編碼方法1.CRC編碼方法設(shè)：要發(fā)送的信息碼字多項式為：M(x)

雙方協(xié)議規(guī)定的生成多項式為：G(x)通信系統(tǒng)中，常見的生成多項式標(biāo)準(zhǔn)有：CRC－12=x12+x11+x3+x2+x1+1CRC－16=x16+x15+x2+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+1CRC－CCITT=x16+x12+x5+1編碼步驟：

(1)用生成多項式的最高位乘以M(x)：xn-kM(x)(2)用(1)的結(jié)果除以G(x)(3)所得余數(shù)R(x)即為CRC的冗余碼。3.4.4循環(huán)碼的解碼方法2.CRC譯碼方法

xn-kM(x)

G(x)=Q(x)余數(shù)為：R(x)xn-kM(x)=Q(x)G(x)+R(x)有：xn-kM(x)+R(x)=Q(x)G(x)CRC校驗碼：編碼后的數(shù)據(jù)流3.5卷積碼3.5.1卷積碼的基本概念1.卷積碼的概念在分組碼中，任何一段規(guī)定時間內(nèi)編碼器產(chǎn)生的n個碼元的一