1、數據通信要求信息傳輸具有高度的可靠性，即要求誤碼率足夠低。然而，誤碼是不可避免的。造成誤碼的原因很多，但主要原因可以歸結為兩個方面:123.1 3.1 差錯控制的基本概念及原理差錯控制的基本概念及原理信道不理想造成的符號間干擾使接受波形發生畸變采樣判決時會造成碼間干擾。可通過均衡方法改善消除。噪聲對信號的干擾噪聲疊加在接受波形上。消除噪聲干擾產生誤碼的方法就是進行差錯控制。3.1.13.1.1差錯控制的基本概念差錯控制的基本概念1.差錯分類 危害數據傳輸的噪聲有兩類：一類是隨機噪聲：包括熱噪聲、散彈噪聲以及傳輸媒介引起的噪聲等，引起隨機差錯；另一類是脈沖噪聲：是指突然發生的噪聲，包括雷電、開關

2、引起的瞬態變化以及機電交換機的撥號脈沖等，引起突發差錯。 隨機差錯，又稱獨立差錯，它是指那些獨立地、稀疏地和互不相關地發生的差錯。存在這種差錯的信道稱為無記憶信道或隨機信道。產生的原因：隨機噪聲 突發差錯是指一串串，甚至是成片出現的差錯，差錯之間有相關性，差錯出現是密集的。產生突發錯誤的信道稱為有記憶信道或突發信道。產生的原因：脈沖噪聲2.2.差錯控制的基本思路差錯控制的基本思路 差錯控制的核心是抗干擾編碼，或差錯控制編碼，簡稱糾錯編碼，也稱信道編碼。差錯控制的基本思路是： 在發送端被傳送的信息碼序列（本身無規律）的基礎上，按照一定的規則加入若干監督碼元后進行傳輸，這些加入的碼元與原來的信息碼

3、序列之間存在著某種確定的約束關系。在接收數據時，檢驗信息碼元與監督碼元之間的既定的約束關系，如該關系遭到破壞，則收端可以發現傳輸中的錯誤，乃至糾正錯誤。 信息碼（k）+監督碼（r）=碼組（n）加的監督碼越多，差錯控制能力越強3.3.差錯控制的方法差錯控制的方法在數據通信系統中，差錯控制一般可以分為4種類型。如圖3-1所示:（1 1）檢錯重發）檢錯重發 檢錯重發簡稱（ARQ：自動重發請求）。這種差錯控制方式在發送端對數據序列進行分組編碼（如數據幀），加入一定多余碼元使之具有一定的檢錯能力，成為能夠發現錯誤的碼組。接收端收到碼組后按一定的規則進行有無差錯的判決并把判決結果通過反向信道送回發送端，如

4、有差錯，發送端把前面發出的信息重新傳送一次，直到接收端認為正確接收到信息為止。能夠實現差錯檢測和差錯恢復以及流量控制的功能。 處理傳輸差錯的重發技術有：差錯檢測技術；確認幀技術；否認幀技術；差錯重發技術；超時重發技術。 在具體實現檢錯重發系統時,通常有3種形式,即停等ARQ、返回重發ARQ和選擇重發ARQ。分為四種情況討論：分為四種情況討論： a.a.數據在傳輸的過程中沒有出現差錯；數據在傳輸的過程中沒有出現差錯； b.b.數據在傳輸過程中出現差錯；數據在傳輸過程中出現差錯； c.c.數據幀丟失情況；數據幀丟失情況； d.d.確認幀（否認幀）丟失的情況。確認幀（否認幀）丟失的情況。發收ACK0

5、正確正確發收NAK0錯誤錯誤重發重發發收重發重發超時超時重發重發正確正確發收重發重發正確正確ACK0超時超時重發重發正確正確重復幀重復幀(1)(2)(3)(4)01000000基本思路：基本思路： 發送端連續地發送一系列的數據幀，而暫時不需要等待前面發送端連續地發送一系列的數據幀，而暫時不需要等待前面所發數據幀的確認便發送下一幀。連續所發數據幀的確認便發送下一幀。連續ARQARQ把等待時間利用起把等待時間利用起來，傳輸效率大大提高。來，傳輸效率大大提高。 傳輸信道是不可靠的，如果已經連續發送到鏈路上的數據幀傳輸信道是不可靠的，如果已經連續發送到鏈路上的數據幀中，某一幀數據發生了差錯或丟失，在發

6、送端發現已近出現差中，某一幀數據發生了差錯或丟失，在發送端發現已近出現差錯之前，很多后續幀就會達到接收端，接收端應當丟棄出錯數錯之前，很多后續幀就會達到接收端，接收端應當丟棄出錯數據幀，同時還必須保證發送順序交給上層，因此，接收端對后據幀，同時還必須保證發送順序交給上層，因此，接收端對后續正確的數據幀處理方式決定了發送端的重發機制，可將續正確的數據幀處理方式決定了發送端的重發機制，可將連續連續的的ARQARQ分為返回重發分為返回重發ARQARQ和選擇性重發和選擇性重發ARQARQ。返回重發0123123456WT = 70123123456WR = 1丟棄丟棄等待等待1號幀號幀交上交上層處層處

7、理理一般地，當差錯檢測發現第一般地，當差錯檢測發現第I幀錯誤，則接收方給出否認幀信息，并丟幀錯誤，則接收方給出否認幀信息，并丟棄出錯幀及后續幀。發送方退回到第棄出錯幀及后續幀。發送方退回到第I幀，重發第幀，重發第I幀及幀及I幀的后續幀。幀的后續幀。選擇性重發0123145670WT 10123145670WR 1暫存緩暫存緩存存等待等待1號號幀幀一起交上層一起交上層處理處理ACK3ARQ的優缺點需反向信道，實時性差。ARQ方式在信息碼后面所加的監督碼不多，所以信息傳輸效率較高。譯碼設備較簡單（2 2）前向糾錯（）前向糾錯（FECFEC）FEC的思路 前向糾錯系統中，發送端的信道編碼器將輸入數據

8、序列變換成能夠糾正錯誤的碼，接收端的譯碼器根據編碼規律檢驗出錯誤的位置并自動糾正。FEC的優缺點不需要反向信道，實時性好。缺點是所選擇的糾錯碼必須與信道的錯碼特性密切配合，否則很難達到降低錯碼率的要求；譯碼設備復雜；而要求附加的監督碼也較多，傳輸效率就低。(3)(3)混合糾錯檢錯（混合糾錯檢錯（HECHEC） HEC的思路 混合糾錯檢錯方式是前向糾錯方式和檢錯重發方式的結合。在這種系統中，發送端發出同時具有檢錯和糾錯能力的碼，接收端收到碼后，檢查錯誤情況，如果錯誤少于糾錯能力，則自行糾正；如果干擾嚴重，錯誤很多，超出糾正能力，但能檢測出來，則經反向信道要求發端重發。 HEC的優缺點 混合糾錯檢

9、錯方式在實時性和譯碼復雜性方面是前向糾錯和檢錯重發方式的折衷，因而近年來，在數據通信系統中采用較多。(4)(4)信息反饋（信息反饋（IRQIRQ）IRQ的思路 信息反饋方式(IRQ)在發送端不進行糾錯編碼，接收端把收到的數據序列全部由反向信道送回發端，發端自己比較發送的數據序列與送回的數據序列，從而發現是否有錯誤，并把認為錯誤的數據序列的原數據再次傳送，直到發端沒有發現錯誤為止。IRQ的優缺點這種方式的優點是不需要糾錯、檢錯的編譯器，設備簡單。缺點是需要和前向信道相同的反向信道，實時性差。發送端需要一定容量的存儲器以存儲發送碼組，環路時延越大，數據速率越高，所需存儲容量越大。3.1.2 3.1

10、.2 差錯控制的基本原理差錯控制的基本原理1.差錯控制的原理 糾錯編碼之所以具有檢錯和糾錯能力，是因為在信息碼之外附加了監督碼，即碼的檢錯和糾錯能力是用信息量的冗余度來換取的。 加入監督碼越多，碼的檢錯、糾錯能力越強，但信息傳輸效率下降也越多。 在糾錯編碼中將信息傳輸效率也稱為編碼效率，定義為 k為信息位長度，n為編碼的總長度，n-k為監督元的長度。nkR R越大編碼效率越高，它是衡量碼性能的一個重要參數越大編碼效率越高，它是衡量碼性能的一個重要參數2.2.漢明距離與檢錯和糾錯能力的關系漢明距離與檢錯和糾錯能力的關系（1）幾個概念碼組的重量碼組中非零碼元的數目為碼組的重量，簡稱碼重。碼距把兩個

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

12、單的差錯控制編碼3.2.1 3.2.1 奇偶監督碼奇偶監督碼1.基本概念 這是一種最簡單的檢錯碼,又稱奇偶校驗碼。其編碼規則是先將所要傳輸的數據碼元分組,在每組數據后面附加一位監督位,使得該組碼連同監督位在內的碼組中的“1”的個數為偶數(稱為偶校驗)或奇數(稱為奇檢驗),在接收端按同樣的規律檢查,如發現不符就說明產生了差錯,但是不能確定差錯的具體位置,即不能糾錯。設碼組長度為n，表示為( )，其中前n-1位為信息碼元，第n位為監督位a0。偶檢驗的監督關系在奇校驗的監督關系 0121,aaaann0110 naaa1110 naaa2.檢錯能力(1）只能檢測奇數個錯誤，而不能檢測出偶數個錯誤。（

13、2）適合檢測隨機差錯。3.2.1 3.2.1 水平奇偶監督碼水平奇偶監督碼 水平奇偶監督碼的構成思路是：將信息碼序列按行排成方陣，每行后面加一個奇或偶監督編碼，即每行為一個奇偶監督碼組(見表3-2，以偶監督為例)，但發送時則按列的順序傳輸：11101110011000010101，接收端仍將碼元排成與發送端一樣的方陣形式，然后按行進行奇偶校驗。 信信 息息 碼碼 元元 監督碼元監督碼元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1

14、 0 13.2.2 3.2.2 二維奇偶監督碼二維奇偶監督碼 二維奇偶監督碼是將水平奇偶監督碼推廣而得，又稱水平垂直奇偶監督碼、行列監督碼和方陣碼。它的方法是在水平監督基礎上對表3-2方陣中每一列再進行奇偶校驗，就可得表3-3（以偶監督為例）所示的方陣。發送是按列或按行的順序傳輸。接收端重新將碼元排成發送時方陣形式，然后每行、每列都進行奇偶校驗。 信信 息息 碼碼 元元 監督監督碼元碼元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0

15、1 0 1監督碼監督碼元元 0 1 1 0 1 1 0 0 0 1 13.3 3.3 漢明碼及線性分組碼漢明碼及線性分組碼3.3.1 3.3.1 漢明碼漢明碼 漢明碼是1950年由美國貝爾實驗室提出來的，是第一個設計用來糾正錯誤的線性分組碼，漢明碼及其變型已廣泛應用于數字通信和數據存儲系統中作為差錯控制碼。 1. 糾錯碼的監督位與碼組長度的關系 若碼長為n n信息位數為k k，則監督位數r r。如果希望用r r個監督位構造出r r個監督關系式來指示一位錯碼的種可能位置，則要求knrnr122.(7,4)漢明碼 設分組碼( n，k )中 k 4。為了糾正一位錯碼，要求監督位數 。若取 ，則 。我

16、們 用表示這7個碼元，用 表示三個監督關系式中的校正子，則 的值與錯碼位置的對應關系可以規定如表4-4 所列，3r3r7rkn0123456aaaaaaa321SSS321SSS s1 s2 s3 s1 s2 s3 錯碼位置錯碼位置 0 0 0 0 0 0 無錯無錯 0 0 1 0 0 1 a0 a0 0 1 0 0 1 0 a1 a1 1 0 0 1 0 0 a2 a2 0 1 1 0 1 1 a3 a3 1 0 1 1 0 1 a4 a4 1 1 0 1 1 0 a5 a5 1 1 1 1 1 1 a6 a6 構成監督關系， 在發送端編碼時，信息位 和 的值決定于輸入信號。而監督位 和 應

17、根據信息位的取值按監督關系來確定， 按照上述監督關系所構成的線性分組碼就是(7,4)漢明碼。65421aaaaS65312aaaaS64303aaaaS3561aaaa3460aaaa456,aaa3a12, aa0a4562aaaa（3）（7，4）漢明碼的漢明距離及編碼效率漢明距離漢明碼屬于線性分組碼，根據線性分組碼的性質可以求出（7，4）漢明碼的漢明距離 。因此由式(3-2)和（3-3）可知，這種碼能糾正一個錯碼或檢測兩個錯碼。編碼效率（7，4）漢明碼的編碼效率為%5774nkR3mind3.3.2 3.3.2 線性分組碼線性分組碼1.線性分組碼的概念 線性碼是指監督碼元與信息碼元之間滿足

18、一組線性方程的碼；分組碼是監督碼元僅對本碼組中的碼元起監督作用，或者說監督碼元僅與本碼組的信息碼元有關。既是線性碼又是分組碼的編碼就叫線性分組碼。2.線性分組碼的主要性質 (1)封閉性 所謂封閉性，是指一種線性分組碼中的任意兩個碼組之逐位模2和仍為這種碼中的另一個許用碼組。 (2)碼的最小距離等于非零碼的最小重量線性分組碼的生成矩陣線性分組碼的生成矩陣線性分組碼的編碼線性分組碼的編碼生成矩陣的典型化生成矩陣的典型化線性分組碼的監督矩陣線性分組碼的監督矩陣監督矩陣與生成矩陣之間的關系監督矩陣與生成矩陣之間的關系3.4 3.4 循環碼循環碼循環碼是線性分組碼中一類重要的碼。3.4.1 3.4.1

19、循環碼的循環特性循環碼的循環特性1.碼的多項式若碼組 ，則相應的多項式表示為 2.循環碼的循環特性 循環碼的循環性是指循環碼中任一許用碼組經過循環移位后(將最右端的碼元移至左端，或反之)所得到的碼組仍為它的一個許用碼組。 表3-6給出一種(7，3)循環碼的全部碼組，由此表可直觀看出這種碼的循環性。例如，表中的第2碼組向右循環移一位即得到第5碼組，第2碼組向左循環移一位即得到第3碼組。),(0121aaaaAnn00112211)(xaxaxaxaxAnnnn 碼組編號碼組編號 信息位信息位 監督位監督位 碼組編號碼組編號 信息位信息位 監督位監督位 1 1 2 2 3 3 4 4 0 0 0

20、0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 5 5 6 6 7 7 8 8 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 （7 7，3 3）循環碼的一種碼組）循環碼的一種碼組3.4.2 3.4.2 循環碼的生成多項式和生成矩陣循環碼的生成多項式和生成矩陣

21、1.生成多項式 g(x)2.生成矩陣G由循環碼的生成多項式g(x)可得到生成矩陣G(x)，為)()()()()(21xgxxgxgxxgxxGkk典型的生成矩陣為可以通過線性變換將非典型的生成矩陣轉換為典型的生成矩陣，具體方法是：任意幾行模二加取代某一行。QIGk3.4.3循環碼的編碼方法編碼步驟：編碼步驟： (1)(1)用生成多項式的最高位乘以用生成多項式的最高位乘以M(x)M(x)：x xn-kn-kM(x)M(x) (2) (2)用用(1)(1)的結果除以的結果除以G(x)G(x) (3) (3)所得余數所得余數R(x)R(x)即為即為CRCCRC的冗余碼。的冗余碼。3.4.4 循環碼的解碼方法循環碼的解碼方法3.5 3.5 卷積碼卷積碼3.5.1 卷積碼的基本概念1.