第六章差錯控制

本章學習目標了解差錯控制的基本概念和原理掌握糾檢錯的概念和簡單的差錯控制編碼掌握并理解線性分組碼和卷積碼的編碼方式了解網格編碼調制（TCM）的概念本章節重點難點檢錯糾錯的基本原理簡單的差錯控制編碼漢明碼循環碼

差錯控制是提高數字通信可靠性的重要方法，是數字通信中必須具有的功能。

6.1概述

6.1.1信道編碼

在實際信道傳輸數字信號的過程中,引起傳輸差錯的根本原因在于信道內存在噪聲以及信道傳輸特性不理想所造成的碼間串擾.為了提高數字傳輸系統的可靠性,降低信息傳輸的差錯率,可以利用均衡技術消除碼間串擾,利用增大發射功率、降低接收設備本身的噪聲、選擇好的調制制度和解調方式、加強天線的方向性等措施,提高數字傳輸系統的抗噪聲性能,但上述措施也只能將傳輸差錯減小到一定程度。要進一步提高數字傳輸系統的可靠性,就需要采用差錯控制編碼,對可能或已經出現的差錯進行控制。

差錯即是誤碼。差錯控制的基本思路就是:發送端在被發送的信息序列上附加上一些監督碼元,這些監督碼元與信息(指數據)碼元之間存在某種確定的約束關系;接收端根據既定的約束規則檢驗信息碼元與監督碼元之間的這種關系是否被破壞,如傳輸過程中發生差錯，則信息碼元與監督碼元之間的這一關系受到破壞，從而使接收端可以發現傳輸中的錯誤，乃至糾正錯誤。在數字通信系統中,差錯控制的方式一般可以分為四種類型:檢錯重發（簡稱ARQ）、前向糾錯(簡稱FEC)、混合糾錯（簡稱HEC）和信息反饋(簡稱IRQ)。它們的系統圖如圖6-1所示。

（a）檢錯重發（b）前向糾錯

（c）混合糾錯（d）信息反饋6.1.2差錯控制編碼的基本原理1.檢錯重發檢錯重發方式中，發送端加上的監督碼具有檢測錯誤的功能，接收端收到后檢驗如果發現傳輸中有錯誤，則通過反向信道把這一判斷結果反饋給發送端，然后，發送端把前面發出的信息重新傳送一次，直到接收端認為已正確收到信息為止。常用的檢錯重發系統有三種，即停發等候重發、返回重發和選擇重發。圖6-2所示為這3種系統的工作原理圖。

（a）停發等候重發

（b）返回重發

（c）選擇重發圖6-2檢錯重發差錯控制系統工作原理

圖6-2（a）所示表示停發等候重發系統的發送端、接收端的信號傳遞過程。發送端在時間內送出一個碼組給接收端，接收端收到后經檢測若未發現錯誤，則發回一個認可信號（ACK）給發送端，發送端收到ACK信號后再發出下一個碼組。返回重發系統如圖6-2（b）所示，選擇重發系統如圖6-2（c）所示。它們都與停發等候重發不同，其發送端是連續不斷地發送信號，不在等候收端返回的ACK信號；只不過返回重發系統重發的是前一段N組信號，而選擇重發只有重發有錯誤的那一碼組。返回重發系統和選擇重發系統都需要全雙工的數據鏈路，而停發等候重發只要求半雙工的數據鏈路。

2.前向糾錯前向糾錯系統中，發送端經信道編碼后可以發出具有糾錯能力的碼字；接收端譯碼后不僅可以發現錯誤碼，而且可以判斷錯誤碼的位置并予以糾正。然而，前向糾錯編碼需要附加較多的冗余碼元，影響數據傳輸效率，且編譯碼設備比較復雜。但是由于不需要反饋信道，實時性較好，因此，這種技術在單工信道中普遍采用，例如無線電尋呼系統中采用的POGSAG編碼等。3.混合糾錯混合糾錯方式是前向糾錯方式和檢錯重發方式的結合。在這種系統中接收端不僅具有糾正錯誤的能力，而且對超出糾錯能力的錯誤有檢測能力。遇到后一種情況，系統可以通過反饋信道要求發送端重發一次，混合糾錯方式在實時性和譯碼復雜性方面是前向糾錯和檢錯重發方式的折中。4.信息反饋

信息反饋方式是收端把收到的數據序列全部由反饋信道送到發端，發端比較發送的數據序列與送回的數據序列，從而發現是否有錯誤，對有錯誤的數據序列的原始數據再次傳送，直到發端沒有發現錯誤為止。信息反饋的優點是不需要糾錯、檢錯的譯碼器，設備簡單。缺點是需要和前向信道相同的反向信道，實時性差；并且發送端需要一定容量的存儲器以存儲發送碼組，環路時延越大，數據速率越高，所需的存儲容量也越大。上述差錯控制方式應根據實際情況合理選擇。除IRQ方式外，都需要發送端發送的數據序列具有糾錯和檢錯的能力。為此，必須對信息源輸出的數據以一定規則加入多余的碼元（糾錯編碼）。對于糾錯編碼的要求是加入的多余碼元少而糾錯能力卻很高，而且實現方便，設備簡單，成本低。【例6-1】一數字通信系統采用選擇重發的差錯控制方式。發端要向收端發送的數據是共有9個碼組，其順序號是1～9。傳輸過程中2號碼出現錯誤。試在下圖中空格里填入正確的碼組順序號。解：正確的碼組如下：

6.1.3糾錯碼的分類

按碼組的功能分，有檢錯碼和糾錯碼。按監督碼與信息碼之間的關系分，有線性碼和非線性碼。線性碼是指監督碼元與信息碼元之間的關系是線性關系，即可用一組線性代數方程聯系起來；非線性碼指的是二者是非線性關系。按對信息碼元處理方法的不同分，有分組碼和卷積碼。分組碼是指信息碼與監督碼以組為單位建立關系；卷積碼是指監督碼與本組和前面碼組中的信息碼有關。分組碼一般用符號表示，結構如圖6-3所示，其中k是每組二進制信息碼元的數目，n是編碼組的總位數，又稱為碼組長度（碼長），為每個碼組中的監督碼元數目或稱監督位數目。通常，將分組碼規定為具有如圖6-3所示的結構。圖中前面k位為信息位，后面附加r個監督位。

圖6-3分組碼的結構

按照信息碼元在編碼后是否保持原來的形式不變分，可劃分為系統碼和非系統碼。系統碼是指編碼后碼組中信息碼保持原圖樣順序不變；而非系統碼是指編碼后碼組中信息碼原圖樣發生變化。按糾正差錯的類型分，可分為糾正隨機錯誤的碼和糾正突發錯誤的碼。按照每個碼元取值來分，可分為二進制碼與多進制碼。

6.1.4糾錯編碼的基本原理

信道編碼的基本思想就是在被傳送的信息中附加一些監督碼元，在接收端和發送端之間建立某中校驗關系，當這種校驗關系在傳輸中受到破壞時，可以被發現甚至被糾正，這種檢錯和糾錯能力是用信息量的冗余度來換取的。下面介紹幾個與信道編碼有關的基本概念：碼長：碼字中碼元的數目。例如“11010”的碼長為n=5。碼重：信道編碼中，定義碼組中非零碼元的數目為碼組的重量，簡稱碼重。例如“010”碼組的碼重W=1，“011”碼組的碼重W=2。碼距：兩個等長碼字之間對應位上不同碼元的數目，有時也稱作這兩個碼字的漢明距離，例如碼字10100與11000之間的碼距d=2。最小碼距：在一種編碼中，任意兩個許用碼組間距離的最小值，即碼組集合中任意兩個碼組之間的最小距離，稱為這一編碼的最小碼距。用表示。

對于二進制碼字而言，兩個碼字之間的模2相加，其不同的對應位必為1，相同的對應位必為0，因此，兩個碼字之間模2相加得到的碼重就是這兩個碼字之間的距離。以二進制分組碼的糾錯過程為例，可以較為詳細的說明糾錯碼檢錯和糾錯的基本原理。分組碼對于數字序列是分段進行處理的，設每一段由k個碼元組成（稱作長度為k的信息組），由于每個碼元有0或1兩種值，故共有個不同的狀態。每段長為k的信息組，以一定的規則增加r個多余度碼元（稱為監督元），監督這k個信息元，這樣就組成長度為的碼字（又稱n重）。共可以得到個長度為n的碼字，它們通常被稱為許用碼字。

設法送11經信道傳輸錯了一位，也就是不能作出發送的消息是A(11)還是B（00）的判決。若信道干擾嚴重，使發送碼字的兩位都產生錯誤，從而使11錯成00，收端譯碼器根據重復碼的規則檢驗，不認為有錯，并且判決為消息B，造成了錯判。這時可以發現：這種碼距為2的（2，1）重復碼能確定一個碼元的錯誤，不能確定兩個碼元的錯誤，也不能糾正錯誤。

若任按重復碼的規則，再加一個監督碼元，得到（3，1）重復碼，它的兩個碼字分別為111和000，其碼距為3。這樣其余六個碼字（001、010、100、110、101、011）為禁用碼字。設發送111（代表消息A），如果譯碼器收到的消息為110，根據重復碼的規則，發現錯誤，并且當采用最大似然法譯碼時，把與發送碼字最相似的碼字認為就是發送碼字。而110與111只有一位不同，與000有兩位不同，故判決為111。事實上，在一般情況下，錯一位的可能性要比錯兩位的可能性大得多，從統計的觀念看，這樣判決是正確的。因此，這種（3，1）碼能夠糾正一個錯誤，但不能糾正兩個錯誤，因為若發送111，收到000時，根據譯碼規則將譯為000，這就判錯了。類似于前面的分析，這種碼若用來檢錯，它可以發現兩個錯誤，但不能發現3個錯誤。

6.2.1奇偶監督碼奇偶監督碼是在原信息碼后面附加一個監督元，使得碼組中“1”的個數是奇數或偶數，或者說，它是含一個監督元、碼重為奇數或偶數的分組碼。奇偶監督碼又分為奇監督碼和偶監督碼。設碼字，對偶監督碼有：（6-5）式中，為信息元，為監督元。由于該碼的每一個碼字均按同一規則構成式（6-5），故又稱為一致監督碼。接收端譯碼時，按式（6-5）將碼組中的碼元模2相加，若結果為“0”，就認為無錯，結果為“1”，就可斷定該碼組經傳輸后有奇數個錯誤。與偶監督碼情況相似，奇監督碼只是碼組中“1”的數目為奇數，即滿足條件：

（6-6）

6.2常用的幾種簡單分組碼

而檢錯能力和偶監督碼相同。奇偶監督碼的編碼效率很高，，隨n增大而趨近于1，但一般情況奇偶監督碼不能發現偶數個錯誤，是簡單的檢錯碼，在計算機數據傳輸中得到廣泛的應用。

6.2.2行列監督碼行列監督碼又稱水平垂直一致監督碼或二維奇偶監督碼或矩陣碼。它不僅對水平（行）方向的碼元，而且對垂直（列）方向的碼元實施奇偶監督。一般個信息元，附加個監督元；由行，列組成一個行列監督碼的碼字。表6-1是（66，50）行列監督碼的一個碼字,它的各行和列對1的數目都實行偶數監督.可以逐行傳輸,也可以逐列傳輸.譯碼時分別檢查各行、各列的監督關系，判斷是否出錯。碼組監督位第1組11001010000第2組01000011010第3組01111000011第4組10011100000第5組11000111101監督碼組11000111100表6-1（66，50）行列監督碼

這種碼具有較強的檢測隨機錯誤的能力，能發現所有1、2、3及其他奇數個錯誤，也能發現大部分偶數個錯誤，但分布在矩形的4個頂點這類偶數個錯誤則是例外。這種碼適于檢測突發錯誤。逐行傳輸時，能檢測長度的突發錯誤，逐列傳輸時，能檢測長度的突發錯誤。這種碼還可糾正一些錯誤：單個錯誤、僅在一行中的奇數個錯誤等。因為這些錯誤的位置可以由行、列監督而確定的。1.漢明碼的原理漢明碼是一種能夠糾正一位錯碼且編碼效率較高的線性分組碼。在前面我們討論奇偶校驗時，如按偶監督，由于使用了一位監督位，故它就能和信息位一起構成一個代數式，在接收端解碼時，實際上是計算

（6-7）

6.3線性分組碼6.3.1漢明碼

若,就認為無錯；若，就認為有錯。上式（6-7）就稱為監督方程（或監督關系式），S稱為校正子，或稱伴隨式。簡單的奇偶監督只有一位監督碼元，一個監督方程，S也只有1和0兩種取值，因此只能表示有錯和無錯兩種狀態。不難推想，如果增加一位監督碼元，相應的就會增加一個監督方程，這樣校正子的值有4種組合：00、01、10和11，故能表示4種不同的信息。若用其中一種表示無錯，則其余3種就有可能用來指示一位錯碼的3種不同位置。

信息位監督位信息位監督位0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111表6-3（7，4）漢明碼的許用碼組

信息位監督位信息位監督位0000000100011000011111001001001001110101010011100101101001001011100011010101011011000110110111000001110011111111表6-4（7，4）漢明碼的許用碼組1.循環碼的概念及特性循環碼是一種線性分組碼，又稱為系統碼，即前k位為信息位，后r位為監督位，它除了具有線形分組碼的一般性質外，還具有循環性，即循環碼中任一許用碼組經過循環移位后（即將最右端的碼元移至左端，或反之）所得到的碼組仍為它的許用碼組。下表給出了一種（7，3）循環碼的全部碼組，由此表我們可以直觀的看出這種碼的循環性。例如，表6-6中的第2碼組向右移一位即可得到第5碼組；第5碼組向右移一位即得到第7碼組。6.3.2循環碼碼組編號信息位監督位碼組編號信息位監督位1000000051001011200101116101110030101110711001014011100181110010表6-6（7，3）循環碼碼組

一般來說，若（）是一個（

n,k）循環碼的碼組，則（）（）

...（）

也都是該編碼中的碼組。2.循環碼的多項式表示(1)碼多項式為了便于用代數法來研究循環碼，我們可將碼組用多項式來表示，該多項式稱為碼多項式。一般地，長為n的碼組，對應碼多項式

(6-20)式中，系數對應碼字中的取值，它的存在只表示該對應碼位上是“1”碼，否則為“0”碼。對于（7，3）循環碼中的任一碼組都可以表示為

例如，（7，3）碼字