1、整理ppt1整理ppt2通信原理第第11章差錯控制編碼章差錯控制編碼 整理ppt3第11章差錯控制編碼l11.1 概述概述n信道分類：從差錯控制角度看信道分類：從差錯控制角度看u隨機信道：錯碼的出現是隨機的隨機信道：錯碼的出現是隨機的 u突發信道：錯碼是成串集中出現的突發信道：錯碼是成串集中出現的u混合信道：既存在隨機錯碼又存在突發錯碼混合信道：既存在隨機錯碼又存在突發錯碼 n差錯控制技術的種類差錯控制技術的種類u 檢錯重發檢錯重發u前向糾錯前向糾錯 u反饋校驗反饋校驗u檢錯刪除檢錯刪除 整理ppt4第11章差錯控制編碼n差錯控制編碼：常稱為差錯控制編碼：常稱為糾錯編碼u監督碼元：上述上述4種

2、技術中除第種技術中除第3種外，都是在接收種外，都是在接收端識別有無錯碼。所以在發送端需要在信息碼元序端識別有無錯碼。所以在發送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監督碼元。列中增加一些差錯控制碼元，它們稱為監督碼元。 u不同的編碼方法，有不同的不同的編碼方法，有不同的檢錯或或糾錯能力。能力。u多余度：就是指增加的監督碼元多少。例如，若編：就是指增加的監督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監督碼元碼序列中平均每兩個信息碼元就添加一個監督碼元，則這種編碼的多余度為，則這種編碼的多余度為1/3。u編碼效率(簡稱簡稱碼率) ：設編碼序列中信息碼元數量：設編碼序列中

3、信息碼元數量為為k，總碼元數量為，總碼元數量為n，則比值，則比值k/n 就是碼率。就是碼率。u冗余度：監督碼元數監督碼元數(n-k) 和信息碼元數和信息碼元數 k 之比。之比。u理論上，差錯控制以降低信息傳輸速率為代價換取理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。提高傳輸可靠性。整理ppt5第11章差錯控制編碼n自動要求重發自動要求重發(ARQ)系統系統u3種種ARQ系統系統p停止等待停止等待ARQ系統系統 數據按分組發送。每發送一組數據后發送端等待接數據按分組發送。每發送一組數據后發送端等待接收端的確認收端的確認(ACK)答復，然后再發送下一組數據。答復，然后再發送下一組數

4、據。圖中的第圖中的第3組接收數據有誤，接收端發回一個否認組接收數據有誤，接收端發回一個否認(NAK)答復。這時，發送端將重發第答復。這時，發送端將重發第3組數據。組數據。系統是工作在半雙工狀態，時間沒有得到充分利用系統是工作在半雙工狀態，時間沒有得到充分利用，傳輸效率較低。，傳輸效率較低。 接收碼組ACKACKNAKACKACKNAKACKt1233455發送碼組12334556t有錯碼組有錯碼組整理ppt6第11章差錯控制編碼p拉后拉后ARQ系統系統發送端連續發送數據組，接收端對于每個接收到的數發送端連續發送數據組，接收端對于每個接收到的數據組都發回據組都發回確認(ACK)或或否認(NAK)

5、答復。答復。 例如，圖中第例如，圖中第5組接收數據有誤，則在發送端收到第組接收數據有誤，則在發送端收到第5組接收的否認答復后，從第組接收的否認答復后，從第5組開始重發數據組。組開始重發數據組。在這種系統中需要對發送的數據組和答復進行編號，在這種系統中需要對發送的數據組和答復進行編號，以便識別。顯然，這種系統需要雙工信道以便識別。顯然，這種系統需要雙工信道 接收數據有錯碼組有錯碼組910 1110 1112214365798576ACK1NAK5NAK9ACK5發送數據576952143679810 1110 11 12重發碼組重發碼組整理ppt7第11章差錯控制編碼p選擇重發選擇重發ARQ系統

6、系統它只重發出錯的數據組，因此進一步提高了傳輸效率它只重發出錯的數據組，因此進一步提高了傳輸效率。接收數據有錯碼組有錯碼組9214365759810 11131412發送數據995852143671011131412重發碼組重發碼組NAK9ACK1NAK5ACK5ACK9整理ppt8第11章差錯控制編碼uARQ的主要優點：和前向糾錯方法相比的主要優點：和前向糾錯方法相比p監督碼元較少即能使誤碼率降到很低，即碼率較高；監督碼元較少即能使誤碼率降到很低，即碼率較高；p檢錯的計算復雜度較低；檢錯的計算復雜度較低；p檢錯用的編碼方法和加性干擾的統計特性基本無關，檢錯用的編碼方法和加性干擾的統計特性基本

7、無關，能適應不同特性的信道。能適應不同特性的信道。uARQ的主要缺點：的主要缺點：p需要雙向信道來重發，不能用于單向信道，也不能用需要雙向信道來重發，不能用于單向信道，也不能用于一點到多點的通信系統。于一點到多點的通信系統。p因為重發而使因為重發而使ARQ系統的傳輸效率降低。系統的傳輸效率降低。p在信道干擾嚴重時，可能發生因不斷反復重發而造成在信道干擾嚴重時，可能發生因不斷反復重發而造成事實上的通信中斷。事實上的通信中斷。p在要求實時通信的場合，例如電話通信，往往不允許在要求實時通信的場合，例如電話通信，往往不允許使用使用ARQ法。法。整理ppt9第11章差錯控制編碼uARQ系統的原理方框圖系

8、統的原理方框圖p在發送端，輸入的信息碼元在編碼器中被分組編碼（加入在發送端，輸入的信息碼元在編碼器中被分組編碼（加入監督碼元）后，除了立即發送外，還暫存于緩沖存儲器中監督碼元）后，除了立即發送外，還暫存于緩沖存儲器中。若接收端解碼器檢出錯碼，則由解碼器控制產生一個重。若接收端解碼器檢出錯碼，則由解碼器控制產生一個重發指令。此指令經過反向信道送到發送端。由發送端重發發指令。此指令經過反向信道送到發送端。由發送端重發控制器控制緩沖存儲器重發一次。控制器控制緩沖存儲器重發一次。p接收端僅當解碼器認為接收信息碼元正確時，才將信息碼接收端僅當解碼器認為接收信息碼元正確時，才將信息碼元送給收信者，否則在輸

9、出緩沖存儲器中刪除接收碼元。元送給收信者，否則在輸出緩沖存儲器中刪除接收碼元。p當解碼器未發現錯碼時，經過反向信道發出不需重發指令當解碼器未發現錯碼時，經過反向信道發出不需重發指令。發送端收到此指令后，即繼續發送后一碼組，發送端的。發送端收到此指令后，即繼續發送后一碼組，發送端的緩沖存儲器中的內容也隨之更新。緩沖存儲器中的內容也隨之更新。整理ppt10第11章差錯控制編碼l11.2 糾錯編碼的基本原理糾錯編碼的基本原理n分組碼基本原理：舉例說明如下。分組碼基本原理：舉例說明如下。u設有一種由設有一種由3位二進制數字構成的碼組，它共有位二進制數字構成的碼組，它共有8種不同種不同的可能組合。若將其

10、全部用來表示天氣，則可以表示的可能組合。若將其全部用來表示天氣，則可以表示8種種不同天氣，不同天氣， 例如：例如：“000”（晴），（晴），“001”（云），（云）， “010”（陰），（陰），“011”（雨），（雨）， “100”（雪），（雪），“101”（霜），（霜）， “110”（霧），（霧），“111”（雹）。（雹）。u其中任一碼組在傳輸中若發生一個或多個錯碼，則將變其中任一碼組在傳輸中若發生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發現錯誤。成另一個信息碼組。這時，接收端將無法發現錯誤。整理ppt11第11章差錯控制編碼u若在上述若在上述8種碼組中只準許使用種碼組中只

11、準許使用4種來傳送天氣，例如：種來傳送天氣，例如：“000”晴晴 “011”云云 “101”陰陰 “110”雨雨p這時，雖然只能傳送這時，雖然只能傳送4種不同的天氣，但是接收端卻種不同的天氣，但是接收端卻有可能發現碼組中的一個錯碼。有可能發現碼組中的一個錯碼。p例如，若例如，若“000”（晴）中錯了一位，則接收碼組將變（晴）中錯了一位，則接收碼組將變成成“100”或或“010”或或“001”。這。這3種碼組都是不準使種碼組都是不準使用的，稱為用的，稱為禁用碼組。p接收端在收到禁用碼組時，就認為發現了錯碼。當發接收端在收到禁用碼組時，就認為發現了錯碼。當發生生3個錯碼時，個錯碼時，“000”變成

12、了變成了“111”，它也是禁用碼，它也是禁用碼組，故這種編碼也能檢測組，故這種編碼也能檢測3個錯碼。個錯碼。p但是這種碼不能發現一個碼組中的兩個錯碼，因為發但是這種碼不能發現一個碼組中的兩個錯碼，因為發生兩個錯碼后產生的是生兩個錯碼后產生的是許用碼組。整理ppt12第11章差錯控制編碼u檢錯和糾錯檢錯和糾錯p上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當接上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當接收碼組為禁用碼組收碼組為禁用碼組“100”時，接收端將無法判斷是哪一位時，接收端將無法判斷是哪一位碼發生了錯誤，因為晴、陰、雨三者錯了一位都可以變成碼發生了錯誤，因為晴、陰、雨三者錯了一位都

13、可以變成“100”。p要能夠糾正錯誤，還要增加多余度。例如，若規定許用碼要能夠糾正錯誤，還要增加多余度。例如，若規定許用碼組只有兩個：組只有兩個：“000”（晴），（晴），“111”（雨），其他都是禁（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。p例如，當收到禁用碼組例如，當收到禁用碼組“100”時，若當作僅有一個錯碼，時，若當作僅有一個錯碼，則可以判斷此錯碼發生在則可以判斷此錯碼發生在“1”位，從而糾正為位，從而糾正為“000”（晴（晴）。因為）。因為“111”（雨）發生任何一位錯碼時都不會變成（雨）發生任何一位錯碼時

14、都不會變成“100”這種形式。這種形式。 p但是，這時若假定錯碼數不超過兩個，則存在兩種可能性但是，這時若假定錯碼數不超過兩個，則存在兩種可能性：“000”錯一位和錯一位和“111”錯兩位都可能變成錯兩位都可能變成“100”，因而，因而只能檢測出存在錯碼而無法糾正錯碼。只能檢測出存在錯碼而無法糾正錯碼。整理ppt13第11章差錯控制編碼u分組碼的結構分組碼的結構p將信息碼分組，為每組信息碼附加若干監督碼的編碼稱將信息碼分組，為每組信息碼附加若干監督碼的編碼稱為為分組碼 。p在分組碼中，監督碼元僅監督本碼組中的信息碼元。在分組碼中，監督碼元僅監督本碼組中的信息碼元。 p信息位和監督位的關系：舉例

15、如下信息位和監督位的關系：舉例如下信息位監督位晴000云011陰101雨110整理ppt14第11章差錯控制編碼p分組碼的一般結構分組碼的一般結構u分組碼的符號：分組碼的符號：(n, k)pN 碼組的總位數，又稱為碼組的長度（碼長），碼組的總位數，又稱為碼組的長度（碼長），pk 碼組中信息碼元的數目，碼組中信息碼元的數目，pn k r 碼組中的監督碼元數目，或稱監督位數目。碼組中的監督碼元數目，或稱監督位數目。 整理ppt15第11章差錯控制編碼u分組碼的碼重和碼距分組碼的碼重和碼距p碼重：把碼組中碼重：把碼組中“1”的個數目稱為碼組的重量，簡稱的個數目稱為碼組的重量，簡稱碼重。p碼距：把兩個

16、碼組中對應位上數字不同的位數稱為碼組的碼距：把兩個碼組中對應位上數字不同的位數稱為碼組的距離，簡稱距離，簡稱碼距。碼距又稱。碼距又稱漢明距離。p例如，例如，“000”晴，晴，“011”云，云，“101”陰，陰，“110”雨，雨，4個碼組之間，任意兩個的距離均為個碼組之間，任意兩個的距離均為2。p最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距(d0)。例如，上面的編碼的最小碼距。例如，上面的編碼的最小碼距d0 = 2。整理ppt16第11章差錯控制編碼u碼距的幾何意義碼距的幾何意義p對于對于3位的編碼組，可以在位的編碼組，可以在3維空

17、間中說明碼距的幾何意義。維空間中說明碼距的幾何意義。 p每個碼組的每個碼組的3個碼元的值個碼元的值(a1, a2, a3)就是此立方體各頂點的坐就是此立方體各頂點的坐標。而上述碼距概念在此圖中就對應于各頂點之間沿立方體標。而上述碼距概念在此圖中就對應于各頂點之間沿立方體各邊行走的幾何距離。各邊行走的幾何距離。p由此圖可以直觀看出，上例中由此圖可以直觀看出，上例中4個準用碼組之間的距離均為個準用碼組之間的距離均為2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1整理ppt17第11章差錯控制編碼u碼距和檢糾錯能力的關系

18、碼距和檢糾錯能力的關系p一種編碼的最小碼距一種編碼的最小碼距d0的大小直接關系著這種編碼的檢錯的大小直接關系著這種編碼的檢錯和糾錯能力和糾錯能力p為檢測為檢測e個錯碼，要求最小碼距個錯碼，要求最小碼距 d0 e + 1【證證】設一個碼組設一個碼組A位于位于O點。若碼組點。若碼組A中發生一個錯碼，中發生一個錯碼，則我們可以認為則我們可以認為A的位置將移動至以的位置將移動至以O點為圓心，以點為圓心，以1為半為半徑的圓上某點，但其位置不會超出此圓。徑的圓上某點，但其位置不會超出此圓。 若碼組若碼組A中發生兩位錯碼，則其位置不會超出以中發生兩位錯碼，則其位置不會超出以O點為圓點為圓心，以心，以2為半徑

19、的圓。因此，只要最小碼距不小于為半徑的圓。因此，只要最小碼距不小于3，碼組，碼組A發生兩位以下錯碼時，發生兩位以下錯碼時，不可能變成另一個準用不可能變成另一個準用碼組，因而能檢測錯碼碼組，因而能檢測錯碼的位數等于的位數等于2。 0123BA漢明距離ed0整理ppt18第11章差錯控制編碼同理，若一種編碼的最小碼距為同理，若一種編碼的最小碼距為d0，則將能檢測，則將能檢測(d0 - 1)個錯個錯碼。反之，若要求檢測碼。反之，若要求檢測e個錯碼，則最小碼距個錯碼，則最小碼距d0至少應不小于至少應不小于( e + 1)。p為了糾正為了糾正t個錯碼，要求最小碼距個錯碼，要求最小碼距d0 2t + 1【

20、證證】圖中畫出碼組圖中畫出碼組A和和B的距離為的距離為5。碼組。碼組A或或B若發生不多若發生不多于兩位錯碼，則其位置均不會超出半徑為于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心以原位置為圓心的圓。這兩個圓是不重疊的。判決規則為：若接收碼組落于的圓。這兩個圓是不重疊的。判決規則為：若接收碼組落于以以A為圓心的圓上就判決收到的是碼組為圓心的圓上就判決收到的是碼組A，若落于以，若落于以B為圓心為圓心的圓上就判決為碼組的圓上就判決為碼組B。這樣，就能夠糾這樣，就能夠糾正兩位錯碼。正兩位錯碼。 BtA漢明距離012345td0整理ppt19第11章差錯控制編碼若這種編碼中除碼組若這種編碼中除碼組

21、A和和B外，還有許多種不同碼組，但任外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于兩碼組之間的碼距均不小于5，則以各碼組的位置為中心以，則以各碼組的位置為中心以2為半徑畫出之圓都不會互相重疊。這樣，每種碼組如果發生為半徑畫出之圓都不會互相重疊。這樣，每種碼組如果發生不超過兩位錯碼都將能被糾正。因此，當最小碼距不超過兩位錯碼都將能被糾正。因此，當最小碼距d05時時，能夠糾正，能夠糾正2個錯碼，且最多能糾正個錯碼，且最多能糾正2個。若錯碼達到個。若錯碼達到3個，個，就將落入另一圓上，從而發生錯判。故一般說來，為糾正就將落入另一圓上，從而發生錯判。故一般說來，為糾正t個個錯碼，最小碼距應不小于

22、錯碼，最小碼距應不小于(2t + 1)。整理ppt20第11章差錯控制編碼p為糾正為糾正t個錯碼，同時檢測個錯碼，同時檢測e個錯碼，要求最小碼距個錯碼，要求最小碼距在解釋此式之前，先來分析下圖所示的例子。圖中碼組在解釋此式之前，先來分析下圖所示的例子。圖中碼組A和和B之間距離為之間距離為5。按照檢錯能力公式，最多能檢測。按照檢錯能力公式，最多能檢測4個錯碼，個錯碼，即即e = d0 1 = 5 1 = 4，按照糾錯能力公式糾錯時，能糾正，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時作到兩者，因為當錯碼位數超過糾個錯碼。但是，不能同時作到兩者，因為當錯碼位數超過糾錯能力時，該碼組立即進

23、入另一碼組的圓內而被錯誤地錯能力時，該碼組立即進入另一碼組的圓內而被錯誤地“糾糾正正”了。例如，碼組了。例如，碼組A若錯了若錯了3位，就會被誤認為碼組位，就會被誤認為碼組B錯了錯了2位造成的結果，從而被位造成的結果，從而被錯錯“糾糾”為為B。這就。這就是說，檢錯和糾錯是說，檢錯和糾錯公式不能同時成立公式不能同時成立或同時運用。或同時運用。 )(10tetedBtA漢明距離012345td0整理ppt21第11章差錯控制編碼所以，為了在可以糾正所以，為了在可以糾正t個錯碼的同時，能夠檢測個錯碼的同時，能夠檢測e個錯碼個錯碼，就需要像下圖所示那樣，使某一碼組（譬如碼組，就需要像下圖所示那樣，使某一

24、碼組（譬如碼組A）發）發生生e個錯誤之后所處的位置，與其他碼組（譬如碼組個錯誤之后所處的位置，與其他碼組（譬如碼組B）的）的糾錯圓圈至少距離等于糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發，不然將落在該糾錯圓上從而發生錯誤地生錯誤地“糾正糾正”。因此，由此圖可以直觀看出，要求最。因此，由此圖可以直觀看出，要求最小碼距小碼距這種糾錯和檢錯結合的工作方式簡稱這種糾錯和檢錯結合的工作方式簡稱糾檢結合。 ABe1tt漢明距離)(10teted整理ppt22第11章差錯控制編碼這種工作方式是自動在糾錯和檢錯之間轉換的。當錯碼數量這種工作方式是自動在糾錯和檢錯之間轉換的。當錯碼數量少時，系統按前向糾

25、錯方式工作，以節省重發時間，提高傳少時，系統按前向糾錯方式工作，以節省重發時間，提高傳輸效率；當錯碼數量多時，系統按反饋重發方式糾錯，以降輸效率；當錯碼數量多時，系統按反饋重發方式糾錯，以降低系統的總誤碼率。所以，它適用于大多數時間中錯碼數量低系統的總誤碼率。所以，它適用于大多數時間中錯碼數量很少，少數時間中錯碼數量多的情況。很少，少數時間中錯碼數量多的情況。整理ppt23第11章差錯控制編碼l11.3 糾錯編碼的性能糾錯編碼的性能n系統帶寬和信噪比的矛盾：系統帶寬和信噪比的矛盾：u由上節所述的糾錯編碼原理可知，為了減少接收錯誤碼由上節所述的糾錯編碼原理可知，為了減少接收錯誤碼元數量，需要在發

26、送信息碼元序列中加入監督碼元。這元數量，需要在發送信息碼元序列中加入監督碼元。這樣作的結果使發送序列增長，冗余度增大。若仍須保持樣作的結果使發送序列增長，冗余度增大。若仍須保持發送信息碼元速率不變，則傳輸速率必須增大，因而增發送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統帶寬。系統帶寬的增大將引起系統中噪聲功率大了系統帶寬。系統帶寬的增大將引起系統中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統接收增大，使信噪比下降。信噪比的下降反而又使系統接收碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度

27、和所用的誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關。編碼有關。整理ppt24第11章差錯控制編碼u編碼性能舉例編碼性能舉例p未采用糾錯編碼時，未采用糾錯編碼時，若接收信噪比等于若接收信噪比等于7dB，編碼前誤碼率，編碼前誤碼率約為約為8 10-4，圖中，圖中A點，在采用糾錯編碼點，在采用糾錯編碼后，誤碼率降至約后，誤碼率降至約4 10-5，圖中，圖中B點。這樣，點。這樣，不增大發送功率不增大發送功率 就能就能降低誤碼率約一個半降低誤碼率約一個半數量級。數量級。10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)整理ppt25第11章差錯控制編碼p由

28、圖還可以看出，若由圖還可以看出，若保持誤碼率在保持誤碼率在10-5，圖中圖中C點，未采用編點，未采用編碼時，約需要信噪比碼時，約需要信噪比Eb / n0 = 10.5 dB。在。在采用這種編碼時，約采用這種編碼時，約需要信噪比需要信噪比7.5 dB，圖，圖中中D點。可以節省功率點。可以節省功率2 dB。通常稱這。通常稱這2 dB為為編碼增益編碼增益。p上面兩種情況付出的代上面兩種情況付出的代價是帶寬增大。價是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)整理ppt26第11章差錯控制編碼p傳輸速率和傳輸速率和Eb/n0的關系的關系對于給定的傳輸系

29、統對于給定的傳輸系統式中，式中，RB為碼元速率。為碼元速率。若希望提高傳輸速率，若希望提高傳輸速率，由上式看出勢必使信由上式看出勢必使信噪比下降，誤碼率增噪比下降，誤碼率增大。假設系統原來工作大。假設系統原來工作在圖中在圖中C點，提高速率后點，提高速率后由由C點升到點升到E點。但加用點。但加用糾錯編碼后，仍可將誤碼糾錯編碼后，仍可將誤碼率降到率降到D點。這時付出的點。這時付出的代價仍是帶寬增大。代價仍是帶寬增大。BsssbRnPTnPnTPnE0000)/ 1 (10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)整理ppt27第11章差錯控制編碼l11.4簡單

30、的實用編碼簡單的實用編碼n11.4.1 奇偶監督碼奇偶監督碼u奇偶監督碼分為奇數監督碼和偶數監督碼兩種，兩者的奇偶監督碼分為奇數監督碼和偶數監督碼兩種，兩者的原理相同。在偶數監督碼中，無論信息位多少，監督位原理相同。在偶數監督碼中，無論信息位多少，監督位只有只有1位，它使碼組中位，它使碼組中“1”的數目為偶數，即滿足下式條的數目為偶數，即滿足下式條件：件：式中式中a0為監督位，其他位為信息位。為監督位，其他位為信息位。這種編碼能夠檢測奇數個錯碼。在接收端，按照上式求這種編碼能夠檢測奇數個錯碼。在接收端，按照上式求“模模2和和”，若計算結果為，若計算結果為“1”就說明存在錯碼，結果為就說明存在錯

31、碼，結果為“0”就認為無錯碼。就認為無錯碼。奇數監督碼與偶數監督碼相似，只不過其碼組中奇數監督碼與偶數監督碼相似，只不過其碼組中“1”的的數目為奇數：數目為奇數：0021aaann1021aaann整理ppt28第11章差錯控制編碼n11.4.2 二維奇偶監督碼（方陣碼）二維奇偶監督碼（方陣碼）u二維奇偶監督碼的構成二維奇偶監督碼的構成它是先把上述奇偶監督碼的若干碼組排成矩陣，每一碼組寫它是先把上述奇偶監督碼的若干碼組排成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監督位，如下圖所示成一行，然后再按列的方向增加第二維監督位，如下圖所示圖中圖中a01 a02 a0m為為m行奇偶監督碼中的行

32、奇偶監督碼中的m個監督位。個監督位。cn-1 cn-2 c1 c0為按列進行第二次編碼所增加的監督位，它為按列進行第二次編碼所增加的監督位，它們構成了一監督位行。們構成了一監督位行。012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn整理ppt29第11章差錯控制編碼u二維奇偶監督碼的性能二維奇偶監督碼的性能p這種編碼有可能檢測偶數個錯碼。因為每行的監督位雖然這種編碼有可能檢測偶數個錯碼。因為每行的監督位雖然不能用于檢測本行中的偶數個錯碼，但按列的方向有可能不能用于檢測本行中的偶數個錯碼，但按列的方向有可能由由cn-1 cn-2 c1 c0等

33、監督位檢測出來。有一些偶數錯碼不等監督位檢測出來。有一些偶數錯碼不可能檢測出來。例如，構成矩形的可能檢測出來。例如，構成矩形的4個錯碼，譬如圖中個錯碼，譬如圖中錯了，就檢測不出。錯了，就檢測不出。p這種二維奇偶監督碼適于檢測突發錯碼。因為突發錯碼常這種二維奇偶監督碼適于檢測突發錯碼。因為突發錯碼常常成串出現，隨后有較長一段無錯區間。常成串出現，隨后有較長一段無錯區間。p由于方陣碼只對構成矩形四角的錯碼無法檢測，故其檢錯由于方陣碼只對構成矩形四角的錯碼無法檢測，故其檢錯能力較強。能力較強。 p二維奇偶監督碼不僅可用來檢錯，還可以用來糾正一些錯二維奇偶監督碼不僅可用來檢錯，還可以用來糾正一些錯碼。

34、碼。 例如，僅在一行中有奇數個錯碼時。例如，僅在一行中有奇數個錯碼時。mmnnaaaa122122整理ppt30第11章差錯控制編碼n 11.4.3 恒比碼u在恒比碼中，每個碼組均含有相同數目的在恒比碼中，每個碼組均含有相同數目的“1”（和（和“0”）。由于）。由于“1”的數目與的數目與“0”的數目之比保持恒定的數目之比保持恒定，故得此名。，故得此名。u這種碼在檢測時，只要計算接收碼組中這種碼在檢測時，只要計算接收碼組中“1”的數目是的數目是否對，就知道有無錯碼。否對，就知道有無錯碼。u恒比碼的主要優點是簡單和適于用來傳輸電傳機或其恒比碼的主要優點是簡單和適于用來傳輸電傳機或其他鍵盤設備產生的

35、字母和符號。對于信源來的二進制他鍵盤設備產生的字母和符號。對于信源來的二進制隨機數字序列，這種碼就不適合使用了。隨機數字序列，這種碼就不適合使用了。整理ppt31第11章差錯控制編碼n11.4.4 正反碼u正反碼的編碼：正反碼的編碼：p它是一種簡單的能夠糾正錯碼的編碼。其中的監督位數它是一種簡單的能夠糾正錯碼的編碼。其中的監督位數目與信息位數目相同，監督碼元與信息碼元相同或者相目與信息位數目相同，監督碼元與信息碼元相同或者相反則由信息碼中反則由信息碼中“1”的個數而定。的個數而定。p例如，若碼長例如，若碼長n = 10，其中信息位，其中信息位 k = 5，監督位，監督位 r = 5。其編碼規則

36、為：其編碼規則為：當信息位中有奇數個當信息位中有奇數個“1”時，監督位是信息位的簡時，監督位是信息位的簡單重復；單重復；當信息位有偶數個當信息位有偶數個“1”時，監督位是信息位的反碼時，監督位是信息位的反碼。例如，若信息位為例如，若信息位為11001，則碼組為，則碼組為1100111001；若；若信息位為信息位為10001，則碼組為，則碼組為1000101110。整理ppt32第11章差錯控制編碼u正反碼的解碼正反碼的解碼p在上例中，先將接收碼組中信息位和監督位按模在上例中，先將接收碼組中信息位和監督位按模 2 相加，相加，得到一個得到一個5位的合成碼組。然后，由此合成碼組產生一個位的合成碼組

37、。然后，由此合成碼組產生一個校驗碼組。校驗碼組。p若接收碼組的信息位中有奇數個若接收碼組的信息位中有奇數個“1”，則合成碼組就是校，則合成碼組就是校驗碼組；若接收碼組的信息位中有偶數個驗碼組；若接收碼組的信息位中有偶數個“1”，則取合成，則取合成碼組的反碼作為校驗碼組。碼組的反碼作為校驗碼組。p最后，觀察校驗碼組中最后，觀察校驗碼組中“1”的個數，按下表進行判決及糾的個數，按下表進行判決及糾正可能發現的錯碼。正可能發現的錯碼。 整理ppt33第11章差錯控制編碼p校驗碼組和錯碼的關系校驗碼組和錯碼的關系例如，若發送碼組為例如，若發送碼組為1100111001，接收碼組中無錯碼，接收碼組中無錯碼

38、，則合成碼組應為則合成碼組應為11001 11001=00000。由于接收碼組信息。由于接收碼組信息位中有奇數個位中有奇數個“1”，所以校驗碼組就是，所以校驗碼組就是00000。按上表判。按上表判決，結論是無錯碼。決，結論是無錯碼。 校驗碼組的組成錯碼情況1全為“0”無錯碼2有4個“1”和1個“0”信息碼中有1位錯碼，其位置對應校驗碼組中“0”的位置3有4個“0”和1個“1”監督碼中有1位錯碼，其位置對應校驗碼組中“1”的位置4其他組成錯碼多于1個整理ppt34第11章差錯控制編碼若傳輸中產生了差錯，使接收碼組變成若傳輸中產生了差錯，使接收碼組變成1000111001，則合成，則合成碼組為碼組

39、為10001 1100101000。由于接收碼組中信息位有偶數。由于接收碼組中信息位有偶數個個“1”，所以校驗碼組應取合成碼組的反碼，即，所以校驗碼組應取合成碼組的反碼，即10111。由。由于其中有于其中有4個個“1”和和1個個“0”，按上表判斷信息位中左邊第，按上表判斷信息位中左邊第2位為錯碼。位為錯碼。若接收碼組錯成若接收碼組錯成1100101001，則合成碼組變成，則合成碼組變成11001 0100110000。由于接收碼組中信息位有奇數個。由于接收碼組中信息位有奇數個“1”，故校驗碼，故校驗碼組就是組就是10000，按上表判斷，監督位中第，按上表判斷，監督位中第1位為錯碼。位為錯碼。最

40、后，若接收碼組為最后，若接收碼組為1001111001，則合成碼組為，則合成碼組為10011 1100101010，校驗碼組與其相同，按上表判斷，這，校驗碼組與其相同，按上表判斷，這時錯碼多于時錯碼多于1個。個。p上述長度為上述長度為10的正反碼具有糾正的正反碼具有糾正1位錯碼的能力，并能檢測位錯碼的能力，并能檢測全部全部2位以下的錯碼和大部分位以下的錯碼和大部分2位以上的錯碼。位以上的錯碼。整理ppt35第11章差錯控制編碼l11.5 線性分組碼線性分組碼n基本概念基本概念u代數碼：建立在代數學基礎上的編碼。建立在代數學基礎上的編碼。u線性碼：按照一組線性方程構成的代數碼。在線性：按照一組線

41、性方程構成的代數碼。在線性碼中信息位和監督位是由一些線性代數方程聯系著碼中信息位和監督位是由一些線性代數方程聯系著的。的。u線性分組碼：按照一組線性方程構成的分組碼：按照一組線性方程構成的分組碼 。本節將以漢明碼為例引入線性分組碼的一般原理本節將以漢明碼為例引入線性分組碼的一般原理。整理ppt36第11章差錯控制編碼n漢明碼能夠糾正能夠糾正1位錯碼且編碼效率較高的一種線性分組碼位錯碼且編碼效率較高的一種線性分組碼u漢明碼的構造原理。漢明碼的構造原理。p在偶數監督碼中，由于使用了一位監督位在偶數監督碼中，由于使用了一位監督位a0，它和信息，它和信息位位an-1 a1一起構成一個代數式：一起構成一

42、個代數式：在接收端解碼時，實際上就是在計算在接收端解碼時，實際上就是在計算若若S = 0，就認為無錯碼；若，就認為無錯碼；若S = 1，就認為有錯碼。現，就認為有錯碼。現將上式稱為將上式稱為監督關系式，S稱為稱為校正子。由于校正子。由于校正子S只只有兩種取值，故它只能代表有錯和無錯這兩種信息，而有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。不能指出錯碼的位置。 0021aaann021aaaSnn整理ppt37第11章差錯控制編碼p若監督位增加一位，即變成兩位，則能增加一個類似的監督若監督位增加一位，即變成兩位，則能增加一個類似的監督關系式。由于兩個校正子的可能值有關系式

43、。由于兩個校正子的可能值有4中組合：中組合： 00，01，10，11，故能表示，故能表示4種不同的信息。若用其中種不同的信息。若用其中1種組合表示無錯種組合表示無錯，則其余，則其余3種組合就有可能用來指示一個錯碼的種組合就有可能用來指示一個錯碼的3種不同位置種不同位置。同理，。同理，r個監督關系式能指示個監督關系式能指示1位錯碼的位錯碼的(2r 1)個可能位置個可能位置。p一般來說，若碼長為一般來說，若碼長為n，信息位數為，信息位數為k，則監督位數，則監督位數rnk。如果希望用。如果希望用r個監督位構造出個監督位構造出r個監督關系式來指示個監督關系式來指示1位錯位錯碼的碼的n種可能位置，則要求

44、種可能位置，則要求下面通過一個例子來說明如何具體構造這些監督關系式。下面通過一個例子來說明如何具體構造這些監督關系式。1212rknrr或整理ppt38第11章差錯控制編碼p例：設例：設分組碼(n, k)中中k = 4，為了糾正，為了糾正1位錯碼，由上式可知位錯碼，由上式可知，要求監督位數，要求監督位數 r 3。若取。若取 r = 3，則，則n = k + r = 7。我們用。我們用a6 a5 a0表示這表示這7個碼元，用個碼元，用S1、S2和和S3表示表示3個監督關系式個監督關系式中的校正子，則中的校正子，則S1、S2和和S3的值與錯碼位置的對應關系可以的值與錯碼位置的對應關系可以規定如下表

45、所列：規定如下表所列：S1 S2 S3錯碼位置S1 S2 S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼整理ppt39第11章差錯控制編碼由表中規定可見，僅當一位錯碼的位置在由表中規定可見，僅當一位錯碼的位置在a2 、a4、a5或或a6時時，校正子，校正子S1為為1；否則；否則S1為零。這就意味著為零。這就意味著a2 、a4、a5和和a6四四個碼元構成偶數監督關系：個碼元構成偶數監督關系：同理，同理， a1、a3、a5和和a6構成偶數監督關系：構成偶數監督關系：以及以及a0、a3、a4 和和a6構成偶數監督關系構成偶數監督關系24561aaaaS

46、13562aaaaS03463aaaaS整理ppt40第11章差錯控制編碼在發送端編碼時，信息位在發送端編碼時，信息位a6、a5、a4和和a3的值決定于輸入的值決定于輸入信號，因此它們是隨機的。監督位信號，因此它們是隨機的。監督位a2、a1和和a0應根據信息應根據信息位的取值按監督關系來確定，即監督位應使上位的取值按監督關系來確定，即監督位應使上3式中式中S1、S2和和S3的值為的值為0（表示編成的碼組中應無錯碼）：（表示編成的碼組中應無錯碼）：上式經過移項運算，解出監督位上式經過移項運算，解出監督位給定信息位后，可以直接按上式算出監督位，給定信息位后，可以直接按上式算出監督位， 結果見下表：

47、結果見下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa整理ppt41第11章差錯控制編碼信息位a6 a5 a4 a3監督位a2 a1 a0信息位a6 a5 a4 a3監督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111整理ppt42第11章差錯控制編碼接收端收到每個碼組后，先計算出接收端收到每個碼組后，先計算出S1、S2和和S3，再查表判，再查

48、表判斷錯碼情況。例如，若接收碼組為，按上述公式計算可斷錯碼情況。例如，若接收碼組為，按上述公式計算可得：得：S1 = 0，S2 = 1，S3 = 1。由于。由于S1 S2 S3 等于等于011，故查，故查表可知在表可知在a3位有位有1錯碼。錯碼。 p按照上述方法構造的碼稱為漢明碼。表中所列的按照上述方法構造的碼稱為漢明碼。表中所列的(7, 4)漢明碼漢明碼的最小碼距的最小碼距d0 = 3。因此，這種碼能夠糾正。因此，這種碼能夠糾正1個錯碼或檢測個錯碼或檢測2個錯碼。由于碼率個錯碼。由于碼率k/n = (n - r) /n =1 r/n，故當，故當n很大和很大和r很很小時，碼率接近小時，碼率接近

49、1。可見，漢明碼是一種高效碼。可見，漢明碼是一種高效碼。 整理ppt43第11章差錯控制編碼n線性分組碼的一般原理線性分組碼的一般原理u線性分組碼的構造線性分組碼的構造pH矩陣矩陣上面上面(7, 4)漢明碼的例子有漢明碼的例子有現在將上面它改寫為現在將上面它改寫為上式中已經將上式中已經將“ ”簡寫成簡寫成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa整理ppt44第11章差錯控制編碼上式可以表示成如下矩陣形式：上式可以表示成如下矩陣形式：上式還可

50、以簡記為上式還可以簡記為H AT = 0T 或或A HT = 0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123456aaaaaaa整理ppt45第11章差錯控制編碼H AT = 0T 或或A HT = 0式中式中 A = a6 a5 a4 a3 a2 a1 a00 = 000右上標右上標“T”表示將矩陣轉置。例如，表示將矩陣轉置。例如，HT是是H的轉置，即的轉置，即HT的的第一行為第一行為H的第一列，的第一列，HT的第二行為的第二行為H的第二列等

51、等。的第二列等等。將將H稱為稱為監督矩陣。 只要監督矩陣只要監督矩陣H給定，編碼時監督位和信息位的關系就完全給定，編碼時監督位和信息位的關系就完全確定了。確定了。 101100111010101110100H整理ppt46第11章差錯控制編碼H矩陣的性質：矩陣的性質： 1) H的行數就是監督關系式的數目，它等于監督位的數的行數就是監督關系式的數目，它等于監督位的數目目r。H的每行中的每行中“1”的位置表示相應碼元之間存在的監的位置表示相應碼元之間存在的監督關系。例如，督關系。例如，H的第一行表示監督位的第一行表示監督位a2是由是由a6 a5 a4之和之和決定的。決定的。H矩陣可以分成兩部分，例

52、如矩陣可以分成兩部分，例如 式中，式中，P為為r k階矩陣，階矩陣，Ir為為r r階單位方陣。我們將具階單位方陣。我們將具有有P Ir形式的形式的H矩陣稱為矩陣稱為典型陣。rPIH001101101011011001110整理ppt47第11章差錯控制編碼2) 由代數理論可知，由代數理論可知，H矩陣的各行應該是線性無關的，矩陣的各行應該是線性無關的，否則將得不到否則將得不到 r個線性無關的監督關系式，從而也得不到個線性無關的監督關系式，從而也得不到 r個獨立的監督位。若一矩陣能寫成典型陣形式個獨立的監督位。若一矩陣能寫成典型陣形式P Ir，則其各行一定是線性無關的。因為容易驗證則其各行一定是線

53、性無關的。因為容易驗證Ir的各行是的各行是線性無關的，故線性無關的，故P Ir的各行也是線性無關的。的各行也是線性無關的。pG矩陣：矩陣： 上面漢明碼例子中的監督位公式為上面漢明碼例子中的監督位公式為也可以改寫成矩陣形式：也可以改寫成矩陣形式：346035614562aaaaaaaaaaaa3456012101111011110aaaaaaa整理ppt48第11章差錯控制編碼或者寫成或者寫成式中，式中，Q為一個為一個k r階矩陣，它為階矩陣，它為P的轉置，即的轉置，即 Q = PT 上式表示，在信息位給定后，用信息位的行矩陣乘矩陣上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產生出監督位

54、。就產生出監督位。3456012101111011110aaaaaaaQ34563456012011101110111aaaaaaaaaaa整理ppt49第11章差錯控制編碼我們將我們將Q的左邊加上的左邊加上1個個k k階單位方陣，就構成階單位方陣，就構成1個矩陣個矩陣G G稱為稱為生成矩陣，因為由它可以產生整個碼組，即有，因為由它可以產生整個碼組，即有或者或者因此，如果找到了碼的生成矩陣因此，如果找到了碼的生成矩陣G，則編碼的方法就完全確，則編碼的方法就完全確定了。具有定了。具有IkQ形式的生成矩陣稱為形式的生成矩陣稱為典型生成矩陣。由典型。由典型生成矩陣得出的碼組生成矩陣得出的碼組A中，信

55、息位的位置不變，監督位附加中，信息位的位置不變，監督位附加于其后。這種形式的碼稱為于其后。這種形式的碼稱為系統碼。 0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaGA3456aaaa整理ppt50第11章差錯控制編碼G矩陣的性質：矩陣的性質：1) G矩陣的各行是線性無關的。因為由上式可以看出，矩陣的各行是線性無關的。因為由上式可以看出，任一碼組任一碼組A都是都是G的各行的線性組合。的各行的線性組合。G共有共有k行，若它們行，若它們線性無關，則可以組合出線性無關，則可以組合出2k種不同的碼組種不同的碼組A，它恰是有，它恰是有k位

56、信息位的全部碼組。若位信息位的全部碼組。若G的各行有線性相關的，則不的各行有線性相關的，則不可能由可能由G生成生成2k種不同的碼組了。種不同的碼組了。2) 實際上，實際上，G的各行本身就是一個碼組。因此，如果已的各行本身就是一個碼組。因此，如果已有有k個線性無關的碼組，則可以用其作為生成矩陣個線性無關的碼組，則可以用其作為生成矩陣G，并，并由它生成其余碼組。由它生成其余碼組。整理ppt51第11章差錯控制編碼p錯碼矩陣和錯誤圖樣錯碼矩陣和錯誤圖樣 一般說來，一般說來，A為一個為一個n列的行矩陣。此矩陣的列的行矩陣。此矩陣的n個元素就個元素就是碼組中的是碼組中的n個碼元，所以發送的碼組就是個碼元

57、，所以發送的碼組就是A。此碼組在。此碼組在傳輸中可能由于干擾引入差錯，故接收碼組一般說來與傳輸中可能由于干擾引入差錯，故接收碼組一般說來與A不一定相同。不一定相同。若設接收碼組為一若設接收碼組為一n列的行矩陣列的行矩陣B，即，即則發送碼組和接收碼組之差為則發送碼組和接收碼組之差為B A = E (模模2)它就是傳輸中產生的它就是傳輸中產生的錯碼行行矩陣 式中式中0121bbbbnnB0121eeeennEiiiiiababe當當, 1, 0整理ppt52第11章差錯控制編碼因此，若因此，若ei = 0，表示該接收碼元無錯；若，表示該接收碼元無錯；若ei = 1，則表示該，則表示該接收碼元有錯。

58、接收碼元有錯。 B A = E 可以改寫成可以改寫成 B = A + E例如，若發送碼組例如，若發送碼組A = 1000111，錯碼矩陣，錯碼矩陣E = 0000100，則接收碼組則接收碼組B = 1000011。錯碼矩陣有時也稱為錯碼矩陣有時也稱為錯誤圖樣。整理ppt53第11章差錯控制編碼p校正子校正子S當接收碼組有錯時，當接收碼組有錯時，E 0，將，將B當作當作A代入公式代入公式(A H T = 0)后，該式不一定成立。在錯碼較多，已超過這種編碼的檢錯后，該式不一定成立。在錯碼較多，已超過這種編碼的檢錯能力時，能力時，B變為另一許用碼組，則該式仍能成立。這樣的錯變為另一許用碼組，則該式仍

59、能成立。這樣的錯碼是不可檢測的。在未超過檢錯能力時，上式不成立，即其碼是不可檢測的。在未超過檢錯能力時，上式不成立，即其右端不等于右端不等于0。假設這時該式的右端為。假設這時該式的右端為S，即，即B H T = S將將B = A + E代入上式，可得代入上式，可得S = (A + E) H T = A H T + E H T由于由于A HT = 0，所以，所以S = E H T式中式中S稱為校正子。它能用來指示錯碼的位置。稱為校正子。它能用來指示錯碼的位置。S和錯碼和錯碼E之間有確定的線性變換關系。若之間有確定的線性變換關系。若S和和E之間一一對應之間一一對應，則，則S將能代表錯碼的位置。將能

60、代表錯碼的位置。整理ppt54第11章差錯控制編碼u線性分組碼的性質線性分組碼的性質p封閉性：是指一種線性碼中的任意兩個碼組之和仍為這種是指一種線性碼中的任意兩個碼組之和仍為這種碼中的一個碼組。碼中的一個碼組。這就是說，若這就是說，若A1和和A2是一種線性碼中的兩個許用碼組，則是一種線性碼中的兩個許用碼組，則(A1+A2)仍為其中的一個碼組。這一性質的證明很簡單。若仍為其中的一個碼組。這一性質的證明很簡單。若A1和和A2是兩個碼組，則有是兩個碼組，則有A1 HT = 0,A2 HT = 0將上兩式相加，得出將上兩式相加，得出A1 HT + A2 HT = (A1 + A2) HT = 0所以所