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

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

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

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

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

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

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

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

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

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

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

①HEC的思路

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

②HEC的優(yōu)缺點(diǎn)

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

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

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

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

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

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

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

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

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

1.糾錯(cuò)碼的監(jiān)督位與碼組長度的關(guān)系若碼長為n信息位數(shù)為k，則監(jiān)督位數(shù)r。如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來指示一位錯(cuò)碼的種可能位置，則要求2.(7,4)漢明碼設(shè)分組碼(n，k)中k＝4。為了糾正一位錯(cuò)碼，要求監(jiān)督位數(shù)。若取，則。我們用表示這7個(gè)碼元，用表示三個(gè)監(jiān)督關(guān)系式中的校正子，則的值與錯(cuò)碼位置的對應(yīng)關(guān)系可以規(guī)定如表4-4所列，構(gòu)成監(jiān)督關(guān)系，在發(fā)送端編碼時(shí)，信息位和的值決定于輸入信號。而監(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）可知，這種碼能糾正一個(gè)錯(cuò)碼或檢測兩個(gè)錯(cuò)碼。②編碼效率（7，4）漢明碼的編碼效率為3.3.2線性分組碼1.線性分組碼的概念線性碼是指監(jiān)督碼元與信息碼元之間滿足一組線性方程的碼；分組碼是監(jiān)督碼元僅對本碼組中的碼元起監(jiān)督作用，或者說監(jiān)督碼元僅與本碼組的信息碼元有關(guān)。既是線性碼又是分組碼的編碼就叫線性分組碼。2.線性分組碼的主要性質(zhì)(1)封閉性所謂封閉性，是指一種線性分組碼中的任意兩個(gè)碼組之逐位模2和仍為這種碼中的另一個(gè)許用碼組。(2)碼的最小距離等于非零碼的最小重量線性分組碼的生成矩陣線性分組碼的編碼生成矩陣的典型化線性分組碼的監(jiān)督矩陣監(jiān)督矩陣與生成矩陣之間的關(guān)系3.4循環(huán)碼循環(huán)碼是線性分組碼中一類重要的碼。3.4.1循環(huán)碼的循環(huán)特性1.碼的多項(xiàng)式若碼組，則相應(yīng)的多項(xiàng)式表示為

2.循環(huán)碼的循環(huán)特性循環(huán)碼的循環(huán)性是指循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后(將最右端的碼元移至左端，或反之)所得到的碼組仍為它的一個(gè)許用碼組。表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)碼的生成多項(xiàng)式和生成矩陣1.生成多項(xiàng)式g(x)2.生成矩陣G由循環(huán)碼的生成多項(xiàng)式g(x)可得到生成矩陣G(x)，為典型的生成矩陣為可以通過線性變換將非典型的生成矩陣轉(zhuǎn)換為典型的生成矩陣，具體方法是：任意幾行模二加取代某一行。3.4.3循環(huán)碼的編碼方法1.CRC編碼方法設(shè)：要發(fā)送的信息碼字多項(xiàng)式為：M(x)

雙方協(xié)議規(guī)定的生成多項(xiàng)式為：G(x)通信系統(tǒng)中，常見的生成多項(xià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)用生成多項(xiàng)式的最高位乘以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校驗(yàn)碼：編碼后的數(shù)據(jù)流3.5卷積碼3.5.1卷積碼的基本概念1.卷積碼的概念在分組碼中，任何一段規(guī)定時(shí)間內(nèi)編碼器產(chǎn)生的n個(gè)碼元的一