1、1第11章差錯控制編碼l11.1 概述概述n信道分類：從差錯控制角度看u隨機信道：錯碼的出現是隨機的 u突發信道：錯碼是成串集中出現的u混合信道：既存在隨機錯碼又存在突發錯碼 n差錯控制技術的種類u 檢錯重發u前向糾錯 u反饋校驗u檢錯刪除 2第11章差錯控制編碼n差錯控制編碼：常稱為糾錯編碼糾錯編碼u監督碼元：監督碼元：上述4種技術中除第3種外，都是在接收端識別有無錯碼。所以在發送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監督碼元。 u不同的編碼方法，有不同的檢錯檢錯或糾錯糾錯能力。u多余度多余度：就是指增加的監督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監督碼元，則

2、這種編碼的多余度為1/3。u編碼效率編碼效率(簡稱碼率碼率) ：設編碼序列中信息碼元數量為k，總碼元數量為n，則比值k/n 就是碼率。u冗余度：冗余度：監督碼元數(n-k) 和信息碼元數 k 之比。u理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。3第11章差錯控制編碼n自動要求重發(ARQ)系統u3種ARQ系統p停止等待ARQ系統 數據按分組發送。每發送一組數據后發送端等待接收端的確認(ACK)答復，然后再發送下一組數據。圖中的第3組接收數據有誤，接收端發回一個否認(NAK)答復。這時，發送端將重發第3組數據。系統是工作在半雙工狀態，時間沒有得到充分利用，傳輸效率較低。 接收碼組

3、ACKACKNAKACKACKNAKACKt1233455發送碼組12334556t有錯碼組有錯碼組4第11章差錯控制編碼p拉后ARQ系統發送端連續發送數據組，接收端對于每個接收到的數據組都發回確認確認(ACK)或否認否認(NAK)答復。 例如，圖中第5組接收數據有誤，則在發送端收到第5組接收的否認答復后，從第5組開始重發數據組。在這種系統中需要對發送的數據組和答復進行編號，以便識別。顯然，這種系統需要雙工信道 接收數據有錯碼組有錯碼組910 1110 1112214365798576ACK1NAK5NAK9ACK5發送數據576952143679810 1110 11 12重發碼組重發碼組5

4、第11章差錯控制編碼p選擇重發ARQ系統它只重發出錯的數據組，因此進一步提高了傳輸效率。接收數據有錯碼組有錯碼組9214365759810 11131412發送數據995852143671011131412重發碼組重發碼組NAK9ACK1NAK5ACK5ACK96第11章差錯控制編碼uARQ的主要優點：和前向糾錯方法相比p監督碼元較少即能使誤碼率降到很低，即碼率較高；p檢錯的計算復雜度較低；p檢錯用的編碼方法和加性干擾的統計特性基本無關，能適應不同特性的信道。uARQ的主要缺點：p需要雙向信道來重發，不能用于單向信道，也不能用于一點到多點的通信系統。p因為重發而使ARQ系統的傳輸效率降低。p在

5、信道干擾嚴重時，可能發生因不斷反復重發而造成事實上的通信中斷。p在要求實時通信的場合，例如電話通信，往往不允許使用ARQ法。7第11章差錯控制編碼uARQ系統的原理方框圖p在發送端，輸入的信息碼元在編碼器中被分組編碼（加入監督碼元）后，除了立即發送外，還暫存于緩沖存儲器中。若接收端解碼器檢出錯碼，則由解碼器控制產生一個重發指令。此指令經過反向信道送到發送端。由發送端重發控制器控制緩沖存儲器重發一次。p接收端僅當解碼器認為接收信息碼元正確時，才將信息碼元送給收信者，否則在輸出緩沖存儲器中刪除接收碼元。p當解碼器未發現錯碼時，經過反向信道發出不需重發指令。發送端收到此指令后，即繼續發送后一碼組，發

6、送端的緩沖存儲器中的內容也隨之更新。8第11章差錯控制編碼l11.2 糾錯編碼的基本原理糾錯編碼的基本原理n分組碼基本原理：舉例說明如下。u設有一種由3位二進制數字構成的碼組，它共有8種不同的可能組合。若將其全部用來表示天氣，則可以表示8種不同天氣， 例如：“000”（晴），“001”（云）， “010”（陰），“011”（雨）， “100”（雪），“101”（霜）， “110”（霧），“111”（雹）。u其中任一碼組在傳輸中若發生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發現錯誤。9第11章差錯控制編碼u若在上述8種碼組中只準許使用4種來傳送天氣，例如：“000”晴 “011

7、”云 “101”陰 “110”雨p這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發現碼組中的一個錯碼。p例如，若“000”（晴）中錯了一位，則接收碼組將變成“100”或“010”或“001”。這3種碼組都是不準使用的，稱為禁用碼組禁用碼組。p接收端在收到禁用碼組時，就認為發現了錯碼。當發生3個錯碼時，“000”變成了“111”，它也是禁用碼組，故這種編碼也能檢測3個錯碼。p但是這種碼不能發現一個碼組中的兩個錯碼，因為發生兩個錯碼后產生的是許用碼組許用碼組。10第11章差錯控制編碼u檢錯和糾錯p上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當接收碼組為禁用碼組“100”時，接收端將無法判斷

8、是哪一位碼發生了錯誤，因為晴、陰、雨三者錯了一位都可以變成“100”。p要能夠糾正錯誤，還要增加多余度。例如，若規定許用碼組只有兩個：“000”（晴），“111”（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。p例如，當收到禁用碼組“100”時，若當作僅有一個錯碼，則可以判斷此錯碼發生在“1”位，從而糾正為“000”（晴）。因為“111”（雨）發生任何一位錯碼時都不會變成“100”這種形式。 p但是，這時若假定錯碼數不超過兩個，則存在兩種可能性：“000”錯一位和“111”錯兩位都可能變成“100”，因而只能檢測出存在錯碼而無法糾正錯碼。11第11章差錯控制編碼u分組碼的

9、結構p將信息碼分組，為每組信息碼附加若干監督碼的編碼稱為分組碼分組碼 。p在分組碼中，監督碼元僅監督本碼組中的信息碼元。 p信息位和監督位的關系：舉例如下信息位監督位晴000云011陰101雨11012第11章差錯控制編碼p分組碼的一般結構u分組碼的符號：(n, k)pN 碼組的總位數，又稱為碼組的長度（碼長），pk 碼組中信息碼元的數目，pn k r 碼組中的監督碼元數目，或稱監督位數目。 13第11章差錯控制編碼u分組碼的碼重和碼距p碼重：把碼組中“1”的個數目稱為碼組的重量，簡稱碼重碼重。p碼距：把兩個碼組中對應位上數字不同的位數稱為碼組的距離，簡稱碼距碼距。碼距又稱漢明距離漢明距離。p

10、例如，“000”晴，“011”云，“101”陰，“110”雨，4個碼組之間，任意兩個的距離均為2。p最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距最小碼距(d0)。例如，上面的編碼的最小碼距d0 = 2。14第11章差錯控制編碼u碼距的幾何意義p對于3位的編碼組，可以在3維空間中說明碼距的幾何意義。 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)(

11、0,1,1)(1,1,1)a2a0a115第11章差錯控制編碼u碼距和檢糾錯能力的關系p一種編碼的最小碼距d0的大小直接關系著這種編碼的檢錯和糾錯能力p為檢測e個錯碼，要求最小碼距 d0 e + 1【證】設一個碼組A位于O點。若碼組A中發生一個錯碼，則我們可以認為A的位置將移動至以O點為圓心，以1為半徑的圓上某點，但其位置不會超出此圓。 若碼組A中發生兩位錯碼，則其位置不會超出以O點為圓心，以2為半徑的圓。因此，只要最小碼距不小于3，碼組A發生兩位以下錯碼時，不可能變成另一個準用碼組，因而能檢測錯碼的位數等于2。 0123BA漢明距離ed016第11章差錯控制編碼同理，若一種編碼的最小碼距為d

12、0，則將能檢測(d0 - 1)個錯碼。反之，若要求檢測e個錯碼，則最小碼距d0至少應不小于( e + 1)。p為了糾正t個錯碼，要求最小碼距d0 2t + 1【證】圖中畫出碼組A和B的距離為5。碼組A或B若發生不多于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，若落于以B為圓心的圓上就判決為碼組B。這樣，就能夠糾正兩位錯碼。 BtA漢明距離012345td017第11章差錯控制編碼若這種編碼中除碼組A和B外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于5，則以各碼組的位置為中心以2為半徑畫出之圓都

13、不會互相重疊。這樣，每種碼組如果發生不超過兩位錯碼都將能被糾正。因此，當最小碼距d05時，能夠糾正2個錯碼，且最多能糾正2個。若錯碼達到3個，就將落入另一圓上，從而發生錯判。故一般說來，為糾正t個錯碼，最小碼距應不小于(2t + 1)。18第11章差錯控制編碼p為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距在解釋此式之前，先來分析下圖所示的例子。圖中碼組A和B之間距離為5。按照檢錯能力公式，最多能檢測4個錯碼，即e = d0 1 = 5 1 = 4，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時作到兩者，因為當錯碼位數超過糾錯能力時，該碼組立即進入另一碼組的圓內而被錯誤地“糾正”了。例

14、如，碼組A若錯了3位，就會被誤認為碼組B錯了2位造成的結果，從而被錯“糾”為B。這就是說，檢錯和糾錯公式不能同時成立或同時運用。 )(10tetedBtA漢明距離012345td019第11章差錯控制編碼所以，為了在可以糾正t個錯碼的同時，能夠檢測e個錯碼，就需要像下圖所示那樣，使某一碼組（譬如碼組A）發生e個錯誤之后所處的位置，與其他碼組（譬如碼組B）的糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發生錯誤地“糾正”。因此，由此圖可以直觀看出，要求最小碼距這種糾錯和檢錯結合的工作方式簡稱糾檢結合糾檢結合。 ABe1tt漢明距離)(10teted20第11章差錯控制編碼這種工作方式是自動在糾

15、錯和檢錯之間轉換的。當錯碼數量少時，系統按前向糾錯方式工作，以節省重發時間，提高傳輸效率；當錯碼數量多時，系統按反饋重發方式糾錯，以降低系統的總誤碼率。所以，它適用于大多數時間中錯碼數量很少，少數時間中錯碼數量多的情況。21第11章差錯控制編碼l11.3 糾錯編碼的性能糾錯編碼的性能n系統帶寬和信噪比的矛盾：u由上節所述的糾錯編碼原理可知，為了減少接收錯誤碼元數量，需要在發送信息碼元序列中加入監督碼元。這樣作的結果使發送序列增長，冗余度增大。若仍須保持發送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統帶寬。系統帶寬的增大將引起系統中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統接收

16、碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關。22第11章差錯控制編碼u編碼性能舉例p未采用糾錯編碼時，若接收信噪比等于7dB，編碼前誤碼率約為810-4，圖中A點，在采用糾錯編碼后，誤碼率降至約410-5，圖中B點。這樣，不增大發送功率 就能降低誤碼率約一個半數量級。10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)23第11章差錯控制編碼p由圖還可以看出，若保持誤碼率在10-5，圖中C點，未采用編碼時，約需要信噪比Eb / n0 = 10.5 dB。在采用這種編碼時，約需要信噪比7.5 dB，圖中

17、D點。可以節省功率2 dB。通常稱這2 dB為編碼增益。p上面兩種情況付出的代價是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)24第11章差錯控制編碼p傳輸速率和Eb/n0的關系對于給定的傳輸系統式中，RB為碼元速率。若希望提高傳輸速率，由上式看出勢必使信噪比下降，誤碼率增大。假設系統原來工作在圖中C點，提高速率后由C點升到E點。但加用糾錯編碼后，仍可將誤碼率降到D點。這時付出的代價仍是帶寬增大。BsssbRnPTnPnTPnE0000)/ 1 (10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)25第11章差

18、錯控制編碼l11.4簡單的實用編碼簡單的實用編碼n11.4.1 奇偶監督碼u奇偶監督碼分為奇數監督碼和偶數監督碼兩種，兩者的原理相同。在偶數監督碼中，無論信息位多少，監督位只有1位，它使碼組中“1”的數目為偶數，即滿足下式條件：式中a0為監督位，其他位為信息位。這種編碼能夠檢測奇數個錯碼。在接收端，按照上式求“模2和”，若計算結果為“1”就說明存在錯碼，結果為“0”就認為無錯碼。奇數監督碼與偶數監督碼相似，只不過其碼組中“1”的數目為奇數：0021aaann1021aaann26第11章差錯控制編碼n11.4.2 二維奇偶監督碼（方陣碼）u二維奇偶監督碼的構成它是先把上述奇偶監督碼的若干碼組排

19、成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監督位，如下圖所示圖中a01 a02 a0m為m行奇偶監督碼中的m個監督位。cn-1 cn-2 c1 c0為按列進行第二次編碼所增加的監督位，它們構成了一監督位行。012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn27第11章差錯控制編碼u二維奇偶監督碼的性能p這種編碼有可能檢測偶數個錯碼。因為每行的監督位雖然不能用于檢測本行中的偶數個錯碼，但按列的方向有可能由cn-1 cn-2 c1 c0等監督位檢測出來。有一些偶數錯碼不可能檢測出來。例如，構成矩形的4個錯碼，譬如圖中錯了，就檢測不出。

20、p這種二維奇偶監督碼適于檢測突發錯碼。因為突發錯碼常常成串出現，隨后有較長一段無錯區間。p由于方陣碼只對構成矩形四角的錯碼無法檢測，故其檢錯能力較強。 p二維奇偶監督碼不僅可用來檢錯，還可以用來糾正一些錯碼。 例如，僅在一行中有奇數個錯碼時。mmnnaaaa12212228第11章差錯控制編碼n 11.4.3 恒比碼恒比碼u在恒比碼中，每個碼組均含有相同數目的“1”（和“0”）。由于“1”的數目與“0”的數目之比保持恒定，故得此名。u這種碼在檢測時，只要計算接收碼組中“1”的數目是否對，就知道有無錯碼。u恒比碼的主要優點是簡單和適于用來傳輸電傳機或其他鍵盤設備產生的字母和符號。對于信源來的二進

21、制隨機數字序列，這種碼就不適合使用了。29第11章差錯控制編碼n11.4.4 正反碼正反碼u正反碼的編碼：p它是一種簡單的能夠糾正錯碼的編碼。其中的監督位數目與信息位數目相同，監督碼元與信息碼元相同或者相反則由信息碼中“1”的個數而定。p例如，若碼長n = 10，其中信息位 k = 5，監督位 r = 5。其編碼規則為：當信息位中有奇數個“1”時，監督位是信息位的簡單重復；當信息位有偶數個“1”時，監督位是信息位的反碼。例如，若信息位為11001，則碼組為1100111001；若信息位為10001，則碼組為1000101110。30第11章差錯控制編碼u正反碼的解碼p在上例中，先將接收碼組中信

22、息位和監督位按模 2 相加，得到一個5位的合成碼組。然后，由此合成碼組產生一個校驗碼組。p若接收碼組的信息位中有奇數個“1”，則合成碼組就是校驗碼組；若接收碼組的信息位中有偶數個“1”，則取合成碼組的反碼作為校驗碼組。p最后，觀察校驗碼組中“1”的個數，按下表進行判決及糾正可能發現的錯碼。 31第11章差錯控制編碼p校驗碼組和錯碼的關系例如，若發送碼組為1100111001，接收碼組中無錯碼，則合成碼組應為1100111001=00000。由于接收碼組信息位中有奇數個“1”，所以校驗碼組就是00000。按上表判決，結論是無錯碼。 校驗碼組的組成錯碼情況1全為“0”無錯碼2有4個“1”和1個“0

23、”信息碼中有1位錯碼，其位置對應校驗碼組中“0”的位置3有4個“0”和1個“1”監督碼中有1位錯碼，其位置對應校驗碼組中“1”的位置4其他組成錯碼多于1個32第11章差錯控制編碼若傳輸中產生了差錯，使接收碼組變成1000111001，則合成碼組為100011100101000。由于接收碼組中信息位有偶數個“1”，所以校驗碼組應取合成碼組的反碼，即10111。由于其中有4個“1”和1個“0”，按上表判斷信息位中左邊第2位為錯碼。若接收碼組錯成1100101001，則合成碼組變成110010100110000。由于接收碼組中信息位有奇數個“1”，故校驗碼組就是10000，按上表判斷，監督位中第1位

24、為錯碼。最后，若接收碼組為1001111001，則合成碼組為100111100101010，校驗碼組與其相同，按上表判斷，這時錯碼多于1個。p上述長度為10的正反碼具有糾正1位錯碼的能力，并能檢測全部2位以下的錯碼和大部分2位以上的錯碼。33第11章差錯控制編碼l11.5 線性分組碼線性分組碼n基本概念u代數碼代數碼：建立在代數學基礎上的編碼。u線性碼線性碼：按照一組線性方程構成的代數碼。在線性碼中信息位和監督位是由一些線性代數方程聯系著的。u線性分組碼線性分組碼：按照一組線性方程構成的分組碼 。本節將以漢明碼為例引入線性分組碼的一般原理。34第11章差錯控制編碼n漢明碼漢明碼能夠糾正1位錯碼

25、且編碼效率較高的一種線性分組碼u漢明碼的構造原理。p在偶數監督碼中，由于使用了一位監督位a0，它和信息位an-1 a1一起構成一個代數式：在接收端解碼時，實際上就是在計算若S = 0，就認為無錯碼；若S = 1，就認為有錯碼。現將上式稱為監督關系式監督關系式，S稱為校正子校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。 0021aaann021aaaSnn35第11章差錯控制編碼p若監督位增加一位，即變成兩位，則能增加一個類似的監督關系式。由于兩個校正子的可能值有4中組合： 00，01，10，11，故能表示4種不同的信息。若用其中1種組合表示無錯，則其

26、余3種組合就有可能用來指示一個錯碼的3種不同位置。同理，r個監督關系式能指示1位錯碼的(2r 1)個可能位置。p一般來說，若碼長為n，信息位數為k，則監督位數rnk。如果希望用r個監督位構造出r個監督關系式來指示1位錯碼的n種可能位置，則要求下面通過一個例子來說明如何具體構造這些監督關系式。1212rknrr或36第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的值與錯碼位置

27、的對應關系可以規定如下表所列：S1 S2 S3錯碼位置S1 S2 S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼37第11章差錯控制編碼由表中規定可見，僅當一位錯碼的位置在a2 、a4、a5或a6時，校正子S1為1；否則S1為零。這就意味著a2 、a4、a5和a6四個碼元構成偶數監督關系：同理， a1、a3、a5和a6構成偶數監督關系：以及a0、a3、a4 和a6構成偶數監督關系24561aaaaS13562aaaaS03463aaaaS38第11章差錯控制編碼在發送端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監督

28、位a2、a1和a0應根據信息位的取值按監督關系來確定，即監督位應使上3式中S1、S2和S3的值為0（表示編成的碼組中應無錯碼）：上式經過移項運算，解出監督位給定信息位后，可以直接按上式算出監督位， 結果見下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa39第11章差錯控制編碼信息位a6 a5 a4 a3監督位a2 a1 a0信息位a6 a5 a4 a3監督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010

29、10011001111101000111000111111140第11章差錯控制編碼接收端收到每個碼組后，先計算出S1、S2和S3，再查表判斷錯碼情況。例如，若接收碼組為0000011，按上述公式計算可得：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很小時，碼率接近1。可見，漢明碼是一種高效碼。 41第11章差錯控制編碼n線性分組碼的一

30、般原理u線性分組碼的構造pH矩陣上面(7, 4)漢明碼的例子有現在將上面它改寫為上式中已經將“”簡寫成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa42第11章差錯控制編碼上式可以表示成如下矩陣形式：上式還可以簡記為H AT = 0T 或A HT = 0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123

31、456aaaaaaa43第11章差錯控制編碼H AT = 0T 或A HT = 0式中 A = a6 a5 a4 a3 a2 a1 a00 = 000右上標“T”表示將矩陣轉置。例如，HT是H的轉置，即HT的第一行為H的第一列，HT的第二行為H的第二列等等。將H稱為監督矩陣監督矩陣。 只要監督矩陣H給定，編碼時監督位和信息位的關系就完全確定了。 101100111010101110100H44第11章差錯控制編碼H矩陣的性質： 1) H的行數就是監督關系式的數目，它等于監督位的數目r。H的每行中“1”的位置表示相應碼元之間存在的監督關系。例如，H的第一行1110100表示監督位a2是由a6 a

32、5 a4之和決定的。H矩陣可以分成兩部分，例如 式中，P為r k階矩陣，Ir為r r階單位方陣。我們將具有P Ir形式的H矩陣稱為典型陣典型陣。rPIH00110110101101100111045第11章差錯控制編碼2) 由代數理論可知，H矩陣的各行應該是線性無關的，否則將得不到 r個線性無關的監督關系式，從而也得不到 r個獨立的監督位。若一矩陣能寫成典型陣形式P Ir，則其各行一定是線性無關的。因為容易驗證Ir的各行是線性無關的，故P Ir的各行也是線性無關的。pG矩陣： 上面漢明碼例子中的監督位公式為也可以改寫成矩陣形式：346035614562aaaaaaaaaaaa345601210

33、1111011110aaaaaaa46第11章差錯控制編碼或者寫成式中，Q為一個k r階矩陣，它為P的轉置，即 Q = PT 上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產生出監督位。3456012101111011110aaaaaaaQ34563456012011101110111aaaaaaaaaaa47第11章差錯控制編碼我們將Q的左邊加上1個k k階單位方陣，就構成1個矩陣G G稱為生成矩陣生成矩陣，因為由它可以產生整個碼組，即有或者因此，如果找到了碼的生成矩陣G，則編碼的方法就完全確定了。具有IkQ形式的生成矩陣稱為典型生成矩陣典型生成矩陣。由典型生成矩陣得出的碼組A中，信息

34、位的位置不變，監督位附加于其后。這種形式的碼稱為系統碼系統碼。 0110001101001011001001111000QGkI I G34560123456aaaaaaaaaaaGA3456aaaa48第11章差錯控制編碼G矩陣的性質：1) G矩陣的各行是線性無關的。因為由上式可以看出，任一碼組A都是G的各行的線性組合。G共有k行，若它們線性無關，則可以組合出2k種不同的碼組A，它恰是有k位信息位的全部碼組。若G的各行有線性相關的，則不可能由G生成2k種不同的碼組了。2) 實際上，G的各行本身就是一個碼組。因此，如果已有k個線性無關的碼組，則可以用其作為生成矩陣G，并由它生成其余碼組。49第

35、11章差錯控制編碼p錯碼矩陣和錯誤圖樣 一般說來，A為一個n列的行矩陣。此矩陣的n個元素就是碼組中的n個碼元，所以發送的碼組就是A。此碼組在傳輸中可能由于干擾引入差錯，故接收碼組一般說來與A不一定相同。若設接收碼組為一n列的行矩陣B，即則發送碼組和接收碼組之差為B A = E (模2)它就是傳輸中產生的錯碼錯碼行矩陣矩陣 式中0121bbbbnnB0121eeeennEiiiiiababe當當, 1, 0505152535455565758596061626364656667686970717273747576777879第11章差錯控制編碼p戈萊碼：在上表中的(23, 12)碼稱為戈萊(Go

36、lay)碼。它能糾正3個隨機錯碼，并且容易解碼，實際應用較多。p擴展BCH碼：BCH碼的長度都為奇數。在應用中，為了得到偶數長度的碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上一個因式(x + 1)，從而得到擴展BCH碼(n + 1, k)。擴展BCH碼相當于在原BCH碼上增加了一個校驗位，因此碼距比原BCH碼增加1。擴展BCH碼已經不再具有循環性。例如，廣泛實用的擴展戈萊碼(24, 12)，其最小碼距為8，碼率為1/2，能夠糾正3個錯碼和檢測4個錯碼。它比漢明碼的糾錯能力強很多，付出的代價是解碼更復雜，碼率也比漢明碼低。此外，它不再是循環碼了。80第11章差錯控制編碼n11.6.5 RS

37、碼：碼：它是一類具有很強糾錯能力的多進制BCH碼。u若仍用n表示RS碼的碼長，則對于m進制的RS碼，其碼長需要滿足下式：n = m 1 = 2q 1 式中 q 2，為整數。u對于能夠糾正t個錯誤的RS碼，其監督碼元數目為r = 2t，這時的最小碼距d0 = 2t + 1。uRS碼的生成多項式為g(x) = (x + )(x +2) (x +2t)式中， 伽羅華域GF(2q)中的本原元。u若將每個m進制碼元表示成相應的q位二進制碼元，則得到的二進制碼的參數為：碼長：n = q(2q 1)（二進制碼元）監督碼：r = 2qt（二進制碼元）81第11章差錯控制編碼u由于RS碼能夠糾正t個m進制錯碼，

38、或者說，能夠糾正碼組中t個不超過q位連續的二進制錯碼，所以RS碼特別適用于存在突發錯誤的信道，例如移動通信網等衰落信道中。此外，因為它是多進制糾錯編碼，所以特別適合用于多進制調制的場合。82第11章差錯控制編碼l11.7 卷積碼卷積碼n非分組碼概念：u卷積碼是一種非分組碼。通常它更適用于前向糾錯，因為對于許多實際情況它的性能優于分組碼，而且運算較簡單。u卷積碼在編碼時雖然也是把k個比特的信息段編成n個比特的碼組，但是監督碼元不僅和當前的k比特信息段有關，而且還同前面m = (N 1)個信息段有關。所以一個碼組中的監督碼元監督著N個信息段。通常將N稱為編碼約束度，并將nN稱為編碼約束長度。一般說

39、來，對于卷積碼，k 和 n 的值是比較小的整數。我們將卷積碼記作(n, k, N)。碼率則仍定義為k / n。 83第11章差錯控制編碼n11.7.1 卷積碼的基本原理u編碼器原理方框圖編碼輸出每次輸入k比特1k1k1k1k 1 k2k3kNk 12nNk級移存器n個模2加法器每輸入k比特旋轉1周84第11章差錯控制編碼u例： (n, k, N) = (3, 1, 3)卷積碼編碼器p方框圖p設輸入信息比特序列是bi-2 bi-1 bi bi+1，則當輸入bi時，此編碼器輸出3比特ci di ei，輸入和輸出的關系如下：bi-2bi輸入bibi-1編碼輸出dicieiM2M3M121 2iiii

40、iiiiibbbebbdbc85ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt輸入輸出第11章差錯控制編碼在下圖中用虛線示出了信息位bi的監督位和各信息位之間的約束關系。這里的編碼約束長度nN等于9。 86第11章差錯控制編碼n11.7.2 卷積碼的代數表述上式表示卷積碼也是一種線性碼。一個線性碼完全由一個監督矩陣H或生成矩陣G所確定。下面就來尋找這兩個矩陣。u 監督矩陣H現在仍從上面的實例開始分析。假設上圖中在第1個信息位b1進入編碼器之前，各級移存器都處于“0”狀態，則監督位di、ei和信息位bi之間的關系可以寫為87第11章差錯控制編碼 左式可以改寫為

41、在上面兩個式子和后面的式子中，為簡便計，用“”代替“”。將上式用矩陣表示時，可以寫成11112222133133214424432dbebdbebbdbbebbbdbbebbb 1111221221331233244234400000000bdbebdbbebbdbbbebbdbbbe 88第11章差錯控制編碼與11.5節公式H AT = 0T對比，可以看出監督矩陣為Oedbedbedbedb4443332221110100010010011000100000110010010110000011100101000111011189第11章差錯控制編碼由此例可見，卷積碼的監督矩陣H是一個有頭無尾

42、的半無窮矩陣。此外，這個矩陣的每3列的結構是相同的，只是后3列比前3列向下移了兩行。例如，第4 6列比第1 3列低2行。自第7行起，每兩行的左端比上兩行多了3個“0”。 01000100100110001000001100100101100000111001010001110111H90第11章差錯控制編碼雖然這樣的半無窮矩陣不便于研究，但是只要研究產生前9個碼元（9為約束長度）的監督矩陣就足夠了。不難看出，這種截短監督矩陣的結構形式如下圖所示：由此圖可見，H1的最左邊是n列(n-k)N行的一個子矩陣，且向右的每n列均相對于前n列降低(n - k)行。H1 =nn k(n k)N91第11章差

43、錯控制編碼此例中碼的截短監督矩陣可以寫成如下形式：式中 2階單位方陣； Pi 1 2階矩陣，i = 1, 2, 3； O2 2階全零方陣。2122232122211100100101100000111001010001110111IPOPOPIPOPIPH01102I92第11章差錯控制編碼一般說來，卷積碼的截短監督矩陣具有如下形式：式中 In-k (n k)階單位方陣； Pi k (n k)階矩陣； On-k (n k)階全零方陣。有時還將H1的末行稱為基本監督矩陣hh = PN On-k PN-1 On-k PN-2 On-k P1 In-k它是卷積碼的一個最重要的矩陣，因為只要給定了h，

44、則H1也就隨之決定了。或者說，我們從給定的h不難構造出H1。knknNknNknNknknknknknknIPOPOPOPIPOPOPIPOPIPH121123121193第11章差錯控制編碼u生成矩陣生成矩陣G上例中的輸出碼元序列可以寫成 b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4 = b1 b1 b1 b2 b2 (b2 + b1) b3 (b3 + b1) (b3 + b2 + b1) b4 (b4 + b2) (b4 + b3 + b2) 000000000000000000000000001000000000000011100000000000011110

45、00000001100111100000000110011114321bbbb94第11章差錯控制編碼此碼的生成矩陣G即為上式最右矩陣： 它也是一個半無窮矩陣，其特點是每一行的結構相同，只是比上一行向右退后3列（因現在n = 3）。0000000000000000000000000010000000000000111000000000000111100000000110011110000000011001111G95第11章差錯控制編碼u截短生成矩陣：類似地，也有截短生成矩陣式中 I1 一階單位方陣；Qi 2 1階矩陣。與H1矩陣比較可見，Qi是矩陣PiT的轉置：Qi = PiT (i = 1

46、, 2, )一般說來，截短生成矩陣具有如下形式：1121132111111000000001111000011001111QIQOQIQOQOQIG96第11章差錯控制編碼式中 Ik k階單位方陣； Qi (n k)k階矩陣； Ok k階全零方陣。并將上式中矩陣第一行稱為基本生成矩陣g Ik Q1 Ok Q2 Ok Q3Ok QN同樣，如果基本生成矩陣g已經給定，則可以從已知的信息位得到整個編碼序列。1211213211QIQOQIQOQOQIQOQOQOQIGkNkkNkkkNkkkk97第11章差錯控制編碼n11.7.3 卷積碼的解碼u分類：p代數解碼：利用編碼本身的代數結構進行解碼，不考

47、慮信道的統計特性。大數邏輯解碼，又稱門限解碼，是卷積碼代數解碼的最主要一種方法，它也可以應用于循環碼的解碼。大數邏輯解碼對于約束長度較短的卷積碼最為有效，而且設備較簡單。p概率解碼：又稱最大似然解碼。它基于信道的統計特性和卷積碼的特點進行計算。針對無記憶信道提出的序貫解碼就是概率解碼方法之一。另一種概率解碼方法是維特比算法。當碼的約束長度較短時，它比序貫解碼算法的效率更高、速度更快，目前得到廣泛的應用。98第11章差錯控制編碼u大數邏輯解碼p工作原理圖中首先將接收信息位暫存于移存器中，并從接收碼元的信息位和監督位計算校正子。然后，將計算得出的校正子暫存，并用它來檢測錯碼的位置。在信息位移存器輸

48、出端，接有一個模2加電路；當檢測到輸出的信息位有錯時，在輸出的信息位上加“1”，從而糾正之。 校正子計算信息位移存器校正子移存器錯碼檢測 輸入輸出修正校正子信息位監督位99第11章差錯控制編碼這里的錯碼檢測是采用二進制碼的大數邏輯解碼算法。它利用一組“正交”校驗方程進行計算。這里的“正交” 定義：若被校驗的那個信息位出現在校驗方程組的每一個方程中，而其他的信息位至多在一個方程中出現，則稱這組方程為正交校驗方程。這樣就可以根據被錯碼影響了的方程數目在方程組中是否占多數來判斷該信息位是否錯了。下面將用一個實例來具體講述這一過程。100第11章差錯控制編碼p例：(2, 1, 6)卷積碼編碼器方框圖監

49、督位和信息位的關系當輸入序列為b1 b2 b3 b4 時，監督位為c1 = b1c2 = b2c3 = b3c4 = b1 + b4c5 = b1 + b2 + b5c6 = b1 + b2 + b3 + b6 b6b5b4b3b2b1bi ci輸入輸出bici101第11章差錯控制編碼監督關系式 參照11.5節中監督關系的定義式，容易寫出 S1 = c1 + b1S2 = c2 + b2S3 = c3 + b3S4 = c4 + b1 + b4S5 = c5 + b1 + b2 + b5S6 = c6 + b1 + b2 + b3 + b6上式中的Si (i = 1 6)稱為校正子。正交校驗

50、方程組上式經過簡單線性變換后，得出如下正交校驗方程組：102第11章差錯控制編碼S1 = c1 + b1S4 = c4 + b1 + b4S5 = c5 + b1 + b2 + b5S2 + S6 = c2 + c6 + b1 + b3 + b6在上式中，只有信息位b1出現在每個方程中，監督位和其他信息位均最多只出現一次。因此，在接收端解碼時，考察b1、c1至b6、c6等12個碼元，僅當b1出錯時，式中才可能有3個或3個以上方程等于“1”。從而能夠糾正b1的錯誤。 103輸入輸出Yb6b5b4b3b2b1S6S5S4S3S2S1門限電路：“1”的個數 3？校正子Si校正子移存器信息位移存器重算

51、監督位ci接收監督位計算校正子Si6 5 4 3 2 1第11章差錯控制編碼解碼器方框圖按照這一原理畫出的此(2, 1, 6)卷積碼解碼器方框圖如下104第11章差錯控制編碼由此圖可見，當信息位出現一個錯碼時，僅當它位于信息位移存器的第6、3、2和1級時，才使校正子等于“1”。因此，這時的校正子序列為100111；反之，當監督位出現一個錯碼時，校正子序列將為100000。由此可見，當校正子序列中出現第一個“1”時，表示已經檢出一個錯碼。后面的幾位校正子則指出是信息位錯了，還是監督位錯了。圖中門限電路的輸入代表式中4個方程的4個電壓。門限電路將這4個電壓（非模2）相加。當相加結果大于或等于3時，

52、門限電路輸出“1”，它除了送到輸出端的模2加法器上糾正輸出碼元b1的錯碼外，還送到校正子移存器糾正其中錯誤。此卷積碼除了能夠糾正兩位在約束長度中的隨機錯誤外，還能糾正部分多于兩位的錯誤。 105第11章差錯控制編碼u卷積碼的幾何表述p碼樹圖：現仍以上面(3, 1, 3)碼為例，介紹卷積碼的碼樹 起點信息位狀態 M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位 11 0 1000111c1d1e1000111001110011100010101000111001110011100010101c4d4e4111000001110c2d2e22000100111011001101

53、110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab011001106第11章差錯控制編碼將圖中移存器M1，M2和M3的初始狀態000作為碼樹的起點。現在規定：輸入信息位為“0”，則狀態向上支路移動；輸入信息位為“1”，則狀態向下支路移動。于是，就可以得出圖中所示的碼樹。設現在的輸入碼元序列為1101，則當第1個信息位b1 = 1輸入后，各移存器存儲的信息分別為M1 = 1，M2 = M3 = 0。此時的輸出為c1 d1 e1= 111，碼樹的狀態將從起點a向下到達狀態b；此后，第2個輸入信息位b2 = 1，故碼樹狀態將從狀態b向下到達狀態d。

54、這時M2 = 1，M3 = 0，此時，c2d2e2 = 110。第3位和后繼各位輸入時，編碼器將按照圖中粗線所示的路徑前進，得到輸出序列：111 110 010 100 。由此碼樹圖還可以看到，從第4級支路開始，碼樹的上半部和下半部相同。這意味著，從第4個輸入信息位開始，輸出碼元已經與第1位輸入信息位無關，即此編碼器的約束度N = 3。107第11章差錯控制編碼若觀察在新碼元輸入時編碼器的過去狀態，即觀察M2 M3的狀態和輸入信息位的關系，則可以得出圖中的a b c和d四種狀態。這些狀態和M2 M3的關系也在圖中給出了。 碼樹圖原則上還可以用于解碼。在解碼時，按照漢明距離最小的準則沿上面的碼樹

55、進行搜索。例如，若接收碼元序列為111 010 010 110 ，和發送序列相比可知第4和第11碼元為錯碼。當接收到第46個碼元“010”時，將這3個碼元和對應的第2級的上下兩個支路比較，它和上支路“001”的漢明距離等于2，和下支路“110”的漢明距離等于1，所以選擇走下支路。 類似地，當接收到第1012個碼元“110”時，和第4級的上下支路比較，它和上支路的“011”的漢明距離等于2，和下支路“100”的漢明距離等于1，所以走下支路。這樣，就能夠糾正這兩個錯碼。 108第11章差錯控制編碼一般說來，碼樹搜索解碼法并不實用，因為隨著信息序列的增長，碼樹分支數目按指數規律增長；在上面的碼樹圖中

56、，只有4個信息位，分支已有24 = 16個。但是它為以后實用解碼算法建立了初步基礎。109第11章差錯控制編碼p狀態圖上面的碼樹可以改進為下述的狀態圖。由上例的編碼器結構可知，輸出碼元ci di ei決定于當前輸入信息位bi和前兩位信息位bi-1和bi-2（即移存器M2和M3的狀態）。在上圖中已經為M2和M3的4種狀態規定了代表符號a, b, c 和d。所以，可以將當前輸入信息位、移存器前一狀態、移存器下一狀態和輸出碼元之間的關系歸納于下表中。110第11章差錯控制編碼由上表看出，前一狀態a只能轉到下一狀態a或b，前一狀態b只能轉到下一狀態c或d，等等。按照此表中的規律，可以畫出狀態圖如下圖所

57、示。 移存器前一狀態M3 M2當前輸入信息位 bi輸出碼元cidiei移存器下一狀態M3 M2a (00)01000111a (00)b (01)b (01)01001110c (10)d (11)c (10)01011100a (00)b (01)d (11)01010101c (10)d (11)111第11章差錯控制編碼在此圖中，虛線表示輸入信息位為“0”時狀態轉變的路線；實線表示輸入信息位為“1”時狀態轉變的路線。線條旁的3位數字是編碼輸出比特。利用這種狀態圖可以方便地從輸入序列得到輸出序列。 abcd000111101110010011100001112第11章差錯控制編碼p網格圖將

58、狀態圖在時間上展開，可以得到網格圖如下：圖中畫出了5個時隙。在此圖中，仍用虛線表示輸入信息位為“0”時狀態轉變的路線；實線表示輸入信息位為“1”時狀態轉變的路線。可以看出，在第4時隙以后的網格圖形完全是重復第3時隙的圖形。這也反映了此(3, 1, 3)卷積碼的約束長度為3。 110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100113第11章差錯控制編碼在上圖中給出了輸入信息位為11010時，在網格圖中的編碼路徑。圖中示出這時的輸出編碼序列是：111 1

59、10 010 100 011。由上述可見，用網格圖表示編碼過程和輸入輸出關系比碼樹圖更為簡練。有了上面的狀態圖和網格圖，下面就可以討論維特比解碼算法了。abcdabcd110010001111100114第11章差錯控制編碼u維特比解碼算法p基本原理將接收到的信號序列和所有可能的發送信號序列比較，選擇其中漢明距離最小的序列認為是當前發送信號序列。若發送一個k位序列，則有2k種可能的發送序列。計算機應存儲這些序列，以便用作比較。當k較大時，存儲量太大，使實用受到限制。維特比算法對此作了簡化，使之能夠實用。現在仍用上面(3, 1, 3)卷積碼的例子來說明維特比算法的原理。115第11章差錯控制編碼

60、p例： (3, 1, 3)卷積碼設現在的發送信息位為1101，為了使圖中移存器的信息位全部移出，在信息位后面加入3個“0”，故編碼后的發送序列為111 110 010 100 001 011 000。并且假設接收序列為111 010 010 110 001 011 000，其中第4和第11個碼元為錯碼。由于這是一個(n, k, N) = (3, 1, 3)卷積碼，發送序列的約束度N = 3，所以首先需考察nN 9比特。第1步考察接收序列前9位“111 010 010”。由此碼的網格圖可見，沿路徑每一級有4種狀態a, b, c和d。每種狀態只有兩條路徑可以到達。故4種狀態共有8條到達路徑。現在比