《通信原理》_樊昌信_曹麗娜(第六版)第11章_差錯控制編碼

1、通信原理1通信原理第第11章差錯控制編碼章差錯控制編碼 2差錯控制 error-control信道編碼器 channel encoder反饋信道 feedback channel檢錯重發(fā) error detection and retransmission前向糾錯 forward error correction自動請求重發(fā) automatic-repeat request3第11章差錯控制編碼l11.1 概述概述n信道分類：從差錯控制角度看u隨機信道：錯碼的出現(xiàn)是隨機的 u突發(fā)信道：錯碼是成串集中出現(xiàn)的u混合信道：既存在隨機錯碼又存在突發(fā)錯碼 n差錯控制技術的種類u 檢錯重發(fā)u前向糾錯 u反

2、饋校驗u檢錯刪除 4第11章差錯控制編碼n差錯控制編碼：常稱為糾錯編碼糾錯編碼u監(jiān)督碼元：監(jiān)督碼元：在發(fā)送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監(jiān)督碼元。 u不同的編碼方法，有不同的檢錯檢錯或糾錯糾錯能力。u多余度多余度：就是指增加的監(jiān)督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，則這種編碼的多余度為1/3。u編碼效率編碼效率(簡稱碼率碼率) ：設編碼序列中信息碼元數(shù)量為k，總碼元數(shù)量為n，則比值k/n 就是碼率。u冗余度：冗余度：監(jiān)督碼元數(shù)(n-k) 和信息碼元數(shù) k 之比。u理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。5第11章差錯控制編

3、碼n自動要求重發(fā)(ARQ)系統(tǒng)u3種ARQ系統(tǒng)p停止等待ARQ系統(tǒng) 數(shù)據(jù)按分組發(fā)送。每發(fā)送一組數(shù)據(jù)后發(fā)送端等待接收端的確認(ACK)答復，然后再發(fā)送下一組數(shù)據(jù)。系統(tǒng)是工作在半雙工狀態(tài)，時間沒有得到充分利用，傳輸效率較低。 接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯碼組有錯碼組6第11章差錯控制編碼p拉后ARQ系統(tǒng)發(fā)送端連續(xù)發(fā)送數(shù)據(jù)組，接收端對于每個接收到的數(shù)據(jù)組都發(fā)回確認確認(ACK)或否認否認(NAK)答復。 在這種系統(tǒng)中需要對發(fā)送的數(shù)據(jù)組和答復進行編號，以便識別。顯然，這種系統(tǒng)需要雙工信道 接收數(shù)據(jù)有錯碼組有錯碼組910 1110 11

4、12214365798576ACK1NAK5NAK9ACK5發(fā)送數(shù)據(jù)576952143679810 1110 11 12重發(fā)碼組重發(fā)碼組7第11章差錯控制編碼p選擇重發(fā)ARQ系統(tǒng)它只重發(fā)出錯的數(shù)據(jù)組，因此進一步提高了傳輸效率。接收數(shù)據(jù)有錯碼組有錯碼組9214365759810 11131412發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK98第11章差錯控制編碼uARQ的主要優(yōu)點：和前向糾錯方法相比p監(jiān)督碼元較少即能使誤碼率降到很低，即碼率較高；p檢錯的計算復雜度較低；p檢錯用的編碼方法和加性干擾的統(tǒng)計特性基本無關，能適應不同特性的信道

5、。uARQ的主要缺點：p需要雙向信道來重發(fā)，不能用于單向信道，也不能用于一點到多點的通信系統(tǒng)。p因為重發(fā)而使ARQ系統(tǒng)的傳輸效率降低。p在信道干擾嚴重時，可能發(fā)生因不斷反復重發(fā)而造成事實上的通信中斷。p在要求實時通信的場合，例如電話通信，往往不允許使用ARQ法。9第11章差錯控制編碼uARQ系統(tǒng)的原理方框圖n在發(fā)送端，輸入的信息碼元在編碼器中被分組編碼（加入監(jiān)督碼元）后，除發(fā)送外，還暫存于緩沖存儲器中。n接收端僅當解碼器認為接收信息碼元正確時，才將信息碼元送給收信者，否則在輸出緩沖存儲器中刪除接收碼元。n當解碼器未發(fā)現(xiàn)錯碼時，經(jīng)過反向信道發(fā)出不需重發(fā)指令。發(fā)送端收到此指令后，即繼續(xù)發(fā)送后一碼組

6、，發(fā)送端的緩沖存儲器中的內(nèi)容也隨之更新。10l11.2 糾錯編碼的基本原理糾錯編碼的基本原理n000(晴晴) 001(云云) 010(陰陰) 011(雨雨) 100(雪雪) 101(霜霜) 110(霧霧) 111(雹雹)000(晴晴) 011(云云) 101(陰陰) 110(雨雨)000(晴晴) 111(雨雨)只允許只允許使用使用4組組使用使用2組組不能發(fā)現(xiàn)錯誤不能發(fā)現(xiàn)錯誤可能發(fā)現(xiàn)一個錯誤可能發(fā)現(xiàn)一個錯誤或或檢測檢測3個錯碼個錯碼檢測檢測2個以下個以下錯碼，或能糾錯碼，或能糾正一個錯碼正一個錯碼11第11章差錯控制編碼信息位監(jiān)督位晴000云011陰101雨110如果不要求檢如果不要求檢(糾糾)

7、錯，為了傳輸錯，為了傳輸4種不同的信息，我們種不同的信息，我們用兩位碼組：用兩位碼組：00，01，10，11。代表所傳信息的這些。代表所傳信息的這些兩位碼，稱為信息位。兩位碼，稱為信息位。12第11章差錯控制編碼將信息碼分組，為每組信碼附加若干監(jiān)督碼的編碼集合，將信息碼分組，為每組信碼附加若干監(jiān)督碼的編碼集合，稱為分組碼。稱為分組碼。分組碼一般用符號分組碼一般用符號(n,k)表示，其中表示，其中k是每組二進信息碼元是每組二進信息碼元的數(shù)目，的數(shù)目，n是編碼組的總位數(shù)，又稱為碼組長度（碼長），是編碼組的總位數(shù)，又稱為碼組長度（碼長），n-k=r為每碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。為每碼組中

8、的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。13第11章差錯控制編碼u分組碼的碼重和碼距p碼重：把碼組中“1”的個數(shù)目稱為碼組的重量，簡稱碼碼重重。p碼距：把兩個碼組中對應位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距碼距。碼距又稱漢明距離漢明距離。p例如，“000”晴，“011”云，“101”陰，“110”雨，4個碼組之間，任意兩個的距離均為2。p最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距最小碼距(d0)。例如，上面的編碼的最小碼距d0 = 2。14第11章差錯控制編碼u碼距的幾何意義p對于3位的編碼組，可以在3維空間中說明碼距的幾何意義。 p每個碼組的3個碼元的值(a1, a2, a3)就

9、是此立方體各頂點的坐標。而上述碼距概念在此圖中就對應于各頂點之間沿立方體各邊行走的幾何距離。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)a2a0a115第11章差錯控制編碼u碼距和檢糾錯能力的關系p一種編碼的最小碼距d0的大小直接關系著這種編碼的檢錯和糾錯能力p為檢測e個錯碼，要求最小碼距 d0 e + 1【證】設一個碼組A位于O點。若碼組A中發(fā)生一個錯碼，則我們可以認為A的位置將移動至以O點為圓心，以1為半徑的圓上某點，但其位置不會超出此圓。 若碼組A中發(fā)生兩位錯碼，

10、則其位置不會超出以O點為圓心，以2為半徑的圓。因此，只要最小碼距不小于3，碼組A發(fā)生兩位以下錯碼時，不可能變成另一個準用碼組，因而能檢測錯碼的位數(shù)等于2。 0123BA漢明距離ed016第11章差錯控制編碼同理，若一種編碼的最小碼距為d0，則將能檢測(d0 - 1)個錯碼。反之，若要求檢測e個錯碼，則最小碼距d0至少應不小于( e + 1)。p為了糾正t個錯碼，要求最小碼距d0 2t + 1【證】圖中畫出碼組A和B的距離為5。碼組A或B若發(fā)生不多于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，若落于以

11、B為圓心的圓上就判決為碼組B。這樣，就能夠糾正兩位錯碼。 BtA漢明距離012345td017第11章差錯控制編碼若這種編碼中除碼組A和B外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于5，則以各碼組的位置為中心以2為半徑畫出之圓都不會互相重疊。這樣，每種碼組如果發(fā)生不超過兩位錯碼都將能被糾正。因此，當最小碼距d05時，能夠糾正2個錯碼，且最多能糾正2個。若錯碼達到3個，就將落入另一圓上，從而發(fā)生錯判。故一般說來，為糾正t個錯碼，最小碼距應不小于(2t + 1)。18第11章差錯控制編碼p為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距在解釋此式之前，先來分析下圖所示的例子。圖中碼組A和B之

12、間距離為5。按照檢錯能力公式，最多能檢測4個錯碼，即e = d0 1 = 5 1 = 4，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時作到兩者，因為當錯碼位數(shù)超過糾錯能力時，該碼組立即進入另一碼組的圓內(nèi)而被錯誤地“糾正”了。)(10tetedBtA漢明距離012345td019第11章差錯控制編碼所以，為了在可以糾正t個錯碼的同時，能夠檢測e個錯碼，就需要像下圖所示那樣，使某一碼組（譬如碼組A）發(fā)生e個錯誤之后所處的位置，與其他碼組（譬如碼組B）的糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發(fā)生錯誤地“糾正”。因此，由此圖可以直觀看出，要求最小碼距這種糾錯和檢錯結合的工作方式簡稱

13、糾檢結合糾檢結合。 ABe1tt漢明距離)(10teted20第11章差錯控制編碼這種工作方式是自動在糾錯和檢錯之間轉換的。當錯碼數(shù)量少時，系統(tǒng)按前向糾錯方式工作，以節(jié)省重發(fā)時間，提高傳輸效率；當錯碼數(shù)量多時，系統(tǒng)按反饋重發(fā)方式糾錯，以降低系統(tǒng)的總誤碼率。所以，它適用于大多數(shù)時間中錯碼數(shù)量很少，少數(shù)時間中錯碼數(shù)量多的情況。21第11章差錯控制編碼l11.3 糾錯編碼的性能糾錯編碼的性能n系統(tǒng)帶寬和信噪比的矛盾：u由上節(jié)所述的糾錯編碼原理可知，為了減少接收錯誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結果使發(fā)送序列增長，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大

14、，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關。22第11章差錯控制編碼u編碼性能舉例p未采用糾錯編碼時，若接收信噪比等于7dB，編碼前誤碼率約為810-4，圖中A點，在采用糾錯編碼后，誤碼率降至約410-5，圖中B點。這樣，不增大發(fā)送功率 就能降低誤碼率約一個半數(shù)量級。10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)23第11章差錯控制編碼p由圖還可以看出，若保持誤碼率在10-5，圖中C點，未采用

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

16、1 (10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)2526線性分組碼 linear block codes循環(huán)碼 cyclic codes卷積碼 convolutional codes糾錯碼 error-correcting codes檢錯 error detection糾錯 error correcting混合糾錯 hybrid error correct27第11章差錯控制編碼l11.4簡單的實用編碼簡單的實用編碼n11.4.1 奇偶監(jiān)督碼u奇偶監(jiān)督碼分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩種，兩者的原理相同。在偶數(shù)監(jiān)督碼中，無論信息位多少，監(jiān)督位只有1位，它使

17、碼組中“1”的數(shù)目為偶數(shù)，即滿足下式條件：式中a0為監(jiān)督位，其他位為信息位。這種編碼能夠檢測奇數(shù)個錯碼。在接收端，按照上式求“模2和”，若計算結果為“1”就說明存在錯碼，結果為“0”就認為無錯碼。奇數(shù)監(jiān)督碼與偶數(shù)監(jiān)督碼相似，只不過其碼組中“1”的數(shù)目為奇數(shù)：0021aaann1021aaann28第11章差錯控制編碼n11.4.2 二維奇偶監(jiān)督碼（方陣碼）u二維奇偶監(jiān)督碼的構成它是先把上述奇偶監(jiān)督碼的若干碼組排成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位，如下圖所示圖中a01 a02 a0m為m行奇偶監(jiān)督碼中的m個監(jiān)督位。cn-1 cn-2 c1 c0為按列進行第二次編碼所增加的

18、監(jiān)督位，它們構成了一監(jiān)督位行。012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn29第11章差錯控制編碼u二維奇偶監(jiān)督碼的性能p這種編碼有可能檢測偶數(shù)個錯碼。因為每行的監(jiān)督位雖然不能用于檢測本行中的偶數(shù)個錯碼，但按列的方向有可能由cn-1 cn-2 c1 c0等監(jiān)督位檢測出來。有一些偶數(shù)錯碼不可能檢測出來。例如，構成矩形的4個錯碼，譬如圖中錯了，就檢測不出。p這種二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。因為突發(fā)錯碼常常成串出現(xiàn)，隨后有較長一段無錯區(qū)間。p由于方陣碼只對構成矩形四角的錯碼無法檢測，故其檢錯能力較強。 p二維奇偶監(jiān)督碼不僅可用來檢錯，還

19、可以用來糾正一些錯碼。 例如，僅在一行中有奇數(shù)個錯碼時。mmnnaaaa12212230第11章差錯控制編碼n 11.4.3 恒比碼恒比碼u在恒比碼中，每個碼組均含有相同數(shù)目的“1”（和“0”）。由于“1”的數(shù)目與“0”的數(shù)目之比保持恒定，故得此名。u這種碼在檢測時，只要計算接收碼組中“1”的數(shù)目是否對，就知道有無錯碼。u恒比碼的主要優(yōu)點是簡單和適于用來傳輸電傳機或其他鍵盤設備產(chǎn)生的字母和符號。對于信源來的二進制隨機數(shù)字序列，這種碼就不適合使用了。31第11章差錯控制編碼n11.4.4 正反碼正反碼u正反碼的編碼：p它是一種簡單的能夠糾正錯碼的編碼。其中的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與

20、信息碼元相同或者相反則由信息碼中“1”的個數(shù)而定。p例如，若碼長n = 10，其中信息位 k = 5，監(jiān)督位 r = 5。其編碼規(guī)則為：當信息位中有奇數(shù)個“1”時，監(jiān)督位是信息位的簡單重復；當信息位有偶數(shù)個“1”時，監(jiān)督位是信息位的反碼。例如，若信息位為11001，則碼組為1100111001；若信息位為10001，則碼組為1000101110。32第11章差錯控制編碼u正反碼的解碼p在上例中，先將接收碼組中信息位和監(jiān)督位按模 2 相加，得到一個5位的合成碼組。然后，由此合成碼組產(chǎn)生一個校驗碼組。p若接收碼組的信息位中有奇數(shù)個“1”，則合成碼組就是校驗碼組；若接收碼組的信息位中有偶數(shù)個“1”，

21、則取合成碼組的反碼作為校驗碼組。p最后，觀察校驗碼組中“1”的個數(shù)，按下表進行判決及糾正可能發(fā)現(xiàn)的錯碼。 33第11章差錯控制編碼p校驗碼組和錯碼的關系例如，若發(fā)送碼組為1100111001，接收碼組中無錯碼，則合成碼組應為1100111001=00000。由于接收碼組信息位中有奇數(shù)個“1”，所以校驗碼組就是00000。按上表判決，結論是無錯碼。 校驗碼組的組成錯碼情況1全為“0”無錯碼2有4個“1”和1個“0”信息碼中有1位錯碼，其位置對應校驗碼組中“0”的位置3有4個“0”和1個“1”監(jiān)督碼中有1位錯碼，其位置對應校驗碼組中“1”的位置4其他組成錯碼多于1個34第11章差錯控制編碼若傳輸中

22、產(chǎn)生了差錯，使接收碼組變成1000111001，則合成碼組為100011100101000。由于接收碼組中信息位有偶數(shù)個“1”，所以校驗碼組應取合成碼組的反碼，即10111。由于其中有4個“1”和1個“0”，按上表判斷信息位中左邊第2位為錯碼。若接收碼組錯成1100101001，則合成碼組變成110010100110000。由于接收碼組中信息位有奇數(shù)個“1”，故校驗碼組就是10000，按上表判斷，監(jiān)督位中第1位為錯碼。最后，若接收碼組為1001111001，則合成碼組為100111100101010，校驗碼組與其相同，按上表判斷，這時錯碼多于1個。p上述長度為10的正反碼具有糾正1位錯碼的能力

23、，并能檢測全部2位以下的錯碼和大部分2位以上的錯碼。35第11章差錯控制編碼l11.5 線性分組碼線性分組碼n基本概念u代數(shù)碼代數(shù)碼：建立在代數(shù)學基礎上的編碼。u線性碼線性碼：按照一組線性方程構成的代數(shù)碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。u線性分組碼線性分組碼：按照一組線性方程構成的分組碼 。本節(jié)將以漢明碼為例引入線性分組碼的一般原理。36第11章差錯控制編碼n漢明碼漢明碼能夠糾正1位錯碼且編碼效率較高的一種線性分組碼u漢明碼的構造原理。p在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位a0，它和信息位an-1 a1一起構成一個代數(shù)式：在接收端解碼時，實際上就是在計算若S = 0，就

24、認為無錯碼；若S = 1，就認為有錯碼?，F(xiàn)將上式稱為監(jiān)督關系式監(jiān)督關系式，S稱為校正子校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。 0021aaann021aaaSnn37第11章差錯控制編碼p若監(jiān)督位增加一位，即變成兩位，則能增加一個類似的監(jiān)督關系式。由于兩個校正子的可能值有4中組合： 00，01，10，11，故能表示4種不同的信息。若用其中1種組合表示無錯，則其余3種組合就有可能用來指示一個錯碼的3種不同位置。同理，r個監(jiān)督關系式能指示1位錯碼的 個可能位置。p一般來說，若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)rnk。如果希望用r個監(jiān)督位構造出r個

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

26、中規(guī)定可見，僅當一位錯碼的位置在a2 、a4、a5或a6時，校正子S1為1；否則S1為零。這就意味著a2 、a4、a5和a6四個碼元構成偶數(shù)監(jiān)督關系：同理， a1、a3、a5和a6構成偶數(shù)監(jiān)督關系：以及a0、a3、a4 和a6構成偶數(shù)監(jiān)督關系24561aaaaS13562aaaaS03463aaaaS40第11章差錯控制編碼在發(fā)送端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監(jiān)督位a2、a1和a0應根據(jù)信息位的取值按監(jiān)督關系來確定，即監(jiān)督位應使上3式中S1、S2和S3的值為0（表示編成的碼組中應無錯碼）：上式經(jīng)過移項運算，解出監(jiān)督位給定信息位后，可以直接按上式算出

27、監(jiān)督位， 結果見下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa41第11章差錯控制編碼信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111142第11章差錯控制編碼接收端收到每個碼組后，先計算出S1、S2和S3，再查表判斷錯碼情況。例如，若接收碼組為0000011，按

28、上述公式計算可得：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?？梢姡瑵h明碼是一種高效碼。 43第11章差錯控制編碼n線性分組碼的一般原理u線性分組碼的構造pH矩陣上面(7, 4)漢明碼的例子有現(xiàn)在將上面它改寫為上式中已經(jīng)將“”簡寫成“+”。 000034613562456aaaaaaaaaaaa01001101001

29、0101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa44第11章差錯控制編碼上式可以表示成如下矩陣形式：上式還可以簡記為H AT = 0T 或A HT = 0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123456aaaaaaa45第11章差錯控制編碼H AT = 0T 或A HT = 0式中 A = a6 a5 a4 a3 a2 a1 a00 = 000右上標“T”表示將矩陣轉置。例如，HT

30、是H的轉置，即HT的第一行為H的第一列，HT的第二行為H的第二列等等。將H稱為監(jiān)督矩陣監(jiān)督矩陣。 只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關系就完全確定了。 101100111010101110100H46第11章差錯控制編碼H矩陣的性質(zhì)： 1) H的行數(shù)就是監(jiān)督關系式的數(shù)目，它等于監(jiān)督位的數(shù)目r。H的每行中“1”的位置表示相應碼元之間存在的監(jiān)督關系。例如，H的第一行1110100表示監(jiān)督位a2是由a6 a5 a4之和決定的。H矩陣可以分成兩部分，例如 式中，P為r k階矩陣，Ir為r r階單位方陣。我們將具有P Ir形式的H矩陣稱為典型陣典型陣。rPIH001101101011011001

31、11047第11章差錯控制編碼2) 由代數(shù)理論可知，H矩陣的各行應該是線性無關的，否則將得不到 r個線性無關的監(jiān)督關系式，從而也得不到 r個獨立的監(jiān)督位。若一矩陣能寫成典型陣形式P Ir，則其各行一定是線性無關的。因為容易驗證Ir的各行是線性無關的，故P Ir的各行也是線性無關的。pG矩陣： 上面漢明碼例子中的監(jiān)督位公式為也可以改寫成矩陣形式：346035614562aaaaaaaaaaaa3456012101111011110aaaaaaa48第11章差錯控制編碼或者寫成式中，Q為一個k r階矩陣，它為P的轉置，即 Q = PT 上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督

32、位。3456012101111011110aaaaaaaQ34563456012011101110111aaaaaaaaaaa49第11章差錯控制編碼我們將Q的左邊加上1個k k階單位方陣，就構成1個矩陣G G稱為生成矩陣生成矩陣，因為由它可以產(chǎn)生整個碼組，即有或者因此，如果找到了碼的生成矩陣G，則編碼的方法就完全確定了。具有IkQ形式的生成矩陣稱為典型生成矩陣典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱為系統(tǒng)碼系統(tǒng)碼。 0110001101001011001001111000QGkI I G34560123456aaaaaaaaaaaGA34

33、56aaaa50第11章差錯控制編碼G矩陣的性質(zhì)：1) G矩陣的各行是線性無關的。因為由上式可以看出，任一碼組A都是G的各行的線性組合。G共有k行，若它們線性無關，則可以組合出2k種不同的碼組A，它恰是有k位信息位的全部碼組。若G的各行有線性相關的，則不可能由G生成2k種不同的碼組了。2) 實際上，G的各行本身就是一個碼組。因此，如果已有k個線性無關的碼組，則可以用其作為生成矩陣G，并由它生成其余碼組。51第11章差錯控制編碼p錯碼矩陣和錯誤圖樣 一般說來，A為一個n列的行矩陣。此矩陣的n個元素就是碼組中的n個碼元，所以發(fā)送的碼組就是A。此碼組在傳輸中可能由于干擾引入差錯，故接收碼組一般說來與

34、A不一定相同。若設接收碼組為一n列的行矩陣B，即則發(fā)送碼組和接收碼組之差為B A = E (模2)它就是傳輸中產(chǎn)生的錯碼錯碼行矩陣矩陣 式中0121bbbbnnB0121eeeennEiiiiiababe當當, 1, 052第11章差錯控制編碼因此，若ei = 0，表示該接收碼元無錯；若ei = 1，則表示該接收碼元有錯。 B A = E 可以改寫成 B = A + E例如，若發(fā)送碼組A = 1000111，錯碼矩陣E = 0000100，則接收碼組B = 1000011。錯碼矩陣有時也稱為錯誤圖樣錯誤圖樣。53第11章差錯控制編碼p校正子S當接收碼組有錯時，E 0，將B當作A代入公式(A H

35、 T = 0)后，該式不一定成立。在錯碼較多，已超過這種編碼的檢錯能力時，B變?yōu)榱硪辉S用碼組，則該式仍能成立。這樣的錯碼是不可檢測的。在未超過檢錯能力時，上式不成立，即其右端不等于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將能代表錯碼的位置。54第11章差錯控制編碼u線性分組碼的性質(zhì)p封閉性：封閉性：是指一種線性碼中的任意兩個碼組之和仍為這種碼中的

36、一個碼組。這就是說，若A1和A2是一種線性碼中的兩個許用碼組，則(A1+A2)仍為其中的一個碼組。這一性質(zhì)的證明很簡單。若A1和A2是兩個碼組，則有A1 HT = 0,A2 HT = 0將上兩式相加，得出A1 HT + A2 HT = (A1 + A2) HT = 0所以(A1 + A2)也是一個碼組。由于線性碼具有封閉性，所以兩個碼組(A1和A2)之間的距離（即對應位不同的數(shù)目）必定是另一個碼組(A1 + A2)的重量（即“1”的數(shù)目）。因此，碼的最小距離就是碼的最小重量（除全“0”碼組外）。55 151115411nrnkRC5657生成多項式 generator polynomial奇偶

37、校驗 parity-check移位寄存器 shift register約束長度 constraint length編碼器 encoder系統(tǒng)碼systematic code 58第11章差錯控制編碼l11.6 循環(huán)碼循環(huán)碼n11.6.1 循環(huán)碼原理u循環(huán)性循環(huán)性：循環(huán)性是指任一碼組循環(huán)一位（即將最右端的一個碼元移至左端，或反之）以后，仍為該碼中的一個碼組。在下表中給出一種(7, 3)循環(huán)碼的全部碼組。例如，表中的第2碼組向右移一位即得到第5碼組；第6碼組向右移一位即得到第7碼組。 碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005

38、100101120010111610111003010111071100101401110018111001059第11章差錯控制編碼一般說來，若(an-1 an-2 a0)是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組(an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2) (a0 an-1 a2 a1)也是該編碼中的碼組。60第11章差錯控制編碼u碼多項式p碼組的多項式表示法把碼組中各碼元當作是一個多項式的系數(shù)，即把一個長度為n的碼組表示成例如，上表中的任意一個碼組可以表示為其中第7個碼組可以表示為012211)(axaxaxaxTnnnn012233445566)(axa

39、xaxaxaxaxaxT11010011)(25623456xxxxxxxxxxT61第11章差錯控制編碼p 碼多項式的按模運算在整數(shù)運算中，有模n運算。例如，在模2運算中，有1 + 1 = 2 0 (模2)，1 + 2 = 3 1 (模2)， 2 3 = 6 0 (模2)等等。一般說來，若一個整數(shù)m可以表示為式中，Q 整數(shù)，則在模 n 運算下，有m p (模n)即，在模 n 運算下，一個整數(shù)m等于它被 n 除得的余數(shù)。 npnpQnm,62第11章差錯控制編碼在碼多項式運算中也有類似的按模運算。若一任意多項式F(x)被一 n 次多項式N (x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x

40、)，即則寫為這時，碼多項式系數(shù)仍按模2 運算，即系數(shù)只取 0 和1。例如，x3被(x3 + 1)除，得到余項1。所以有同理因為)()()()(xRxQxNxF）（模)()()(xNxRxF）（模)1(133xx）（模) 1(113224xxxxx xx3 + 1 x4 +x2 + 1 x4 + x x2 +x +1應當注意，由于在模2運算中，用加法代替了減法，故余項不是x2 x + 1，而是x2 + x + 1。63第11章差錯控制編碼u循環(huán)碼的碼多項式p在循環(huán)碼中，若T(x)是一個長為n的許用碼組，則xiT(x)在按模xn + 1運算下，也是該編碼中的一個許用碼組，即若則T (x)也是該編碼

41、中的一個許用碼組?！咀C】因為若則（模(xn + 1)）所以，這時有）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnnnininininniniinininninniaxaxaxaxaxaxaxaxaxaxTx1102211011112211)(ininininninaxaxaxaxaxT1102211)(64第11章差錯控制編碼上式中T (x)正是T(x)代表的碼組向左循環(huán)移位i次的結果。因為原已假定T(x)是循環(huán)碼的一個碼組，所以T (x)也必為該碼中一個碼組。例如，循環(huán)碼組其碼長n = 7?，F(xiàn)給定i = 3，則其對應的碼組為0101110，它正是表中第3碼組。由

42、上述分析可見，一個長為n的循環(huán)碼必定為按模(xn + 1)運算的一個余式。ininininninaxaxaxaxaxT1102211)(1)(256xxxxT）（模) 1() 1()(7235358925633xxxxxxxxxxxxxxTx65第11章差錯控制編碼u循環(huán)碼的生成矩陣Gp由上節(jié)中公式可知，有了生成矩陣G，就可以由k個信息位得出整個碼組，而且生成矩陣G的每一行都是一個碼組。p在循環(huán)碼中，一個(n, k)碼有2k個不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這k個碼組是線性無關的。因此它們

43、可以用來構成此循環(huán)碼的生成矩陣G。GA3456aaaa66第11章差錯控制編碼p在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)k位均為“0”的碼組，即連“0”的長度最多只能有(k - 1)位。否則，在經(jīng)過若干次循環(huán)移位后將得到一個k位信息位全為“0”，但監(jiān)督位不全為“0”的一個碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個常數(shù)項不為“0”的(n - k)次多項式，而且這個g(x)還是這種(n, k)碼中次數(shù)為(n k)的唯一多項式。因為如果有兩個，則由碼的封閉性，把這兩個相加也應該是一個碼組，且此碼組多項式的次數(shù)將小于(n k)，即連續(xù)“0”的個數(shù)多于(k 1)。顯然，這是與前面的結論矛盾

44、的，故是不可能的。我們稱這唯一的(n k)次多項式g(x)為碼的生成多項式。一旦確定了g(x)，則整個(n, k)循環(huán)碼就被確定了。 67第11章差錯控制編碼p因此，循環(huán)碼的生成矩陣G可以寫成 p例：在上表所給出的(7, 3)循環(huán)碼中，n = 7, k = 3, n k = 4。由此表可見，唯一的一個(n k) = 4次碼多項式代表的碼組是第二碼組0010111，與它相對應的碼多項式（即生成多項式）g(x) = x4 + x2 + x + 1。將此g(x)代入上式，得到或)()()()()(21xgxxgxgxxgxxkkG)()()()(2xgxxgxgxxG0010111010111010

45、11100)(xG68第11章差錯控制編碼由于上式不符合G = IkQ的形式，所以它不是典型陣。不過，將它作線性變換，不難化成典型陣。我們可以寫出此循環(huán)碼組，即上式表明，所有碼多項式T(x)都可被g(x)整除，而且任意一個次數(shù)不大于(k 1)的多項式乘g(x)都是碼多項式。)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG69第11章差錯控制編碼u如何尋找任一(n, k)循環(huán)碼的生成多項式 由上式可知，任一循環(huán)碼多項式T(x)都是g(x)的倍式，故它可以寫成T(x) = h(x)g(x)而生成多項式g(

46、x)本身也是一個碼組，即有 T (x) = g(x)由于碼組T (x)是一個(n k)次多項式，故xk T (x)是一個n次多項式。由下式可知，xk T (x)在模(xn + 1)運算下也是一個碼組，故可以寫成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx70第11章差錯控制編碼上式左端分子和分母都是n次多項式，故商式Q(x) = 1。因此，上式可以化成將T(x)和T(x)表示式代入上式，經(jīng)過化簡后得到上式表明，生成多項式g(x)應該是(xn + 1)的一個因子。例如，(x7 + 1)可以分解為為了求(7, 3)循環(huán)碼的生成多項式g(x)，需要從上式中找到一個(

47、n k) = 4次的因子。不難看出，這樣的因子有兩個，即1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx71第11章差錯控制編碼以上兩式都可作為生成多項式。不過，選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx72第11章差錯控制編碼n11.6.2 循環(huán)碼的編解碼方法u循環(huán)碼的編碼方法p編碼原則在編碼時，首先要根據(jù)給定的(n, k)值選定生成多項式g(x)，即從(xn + 1)的因子中選一個(n - k)次多項式作為g(x)。由于所

48、有碼多項式T(x)都可以被g(x)整除。根據(jù)這條原則，就可以對給定的信息位進行編碼：設m(x)為信息碼多項式，其次數(shù)小于k。用xn - k乘m(x)，得到的xn-k m(x)的次數(shù)必定小于n。用g(x)除xn - k m(x)，得到余式r(x)，r(x)的次數(shù)必定小于g(x)的次數(shù)，即小于(n k)。將此余式r(x)加于信息位之后作為監(jiān)督位，即將r(x)和xn - k m(x)相加，得到的多項式必定是一個碼多項式。因為它必須能被g(x)整除，且商的次數(shù)不大于(k 1)。73第11章差錯控制編碼p編碼步驟：用xn - k乘m(x)。這一運算實際上是在信息碼后附加上(n k)個“0”。例如，信息碼

49、為110，它相當于m(x) = x2 + x。當n k = 7 3 = 4時，xn - k m(x) = x4 (x2 + x) = x6 + x5，它相當于1100000。用g(x)除xn - k m(x)，得到商Q(x)和余式r(x)，即例如，若選定g(x) = x4 + x2 + x + 1，則 上式相當于)()()()()(xgxrxQxgxmxkn11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn1011110111110111110000074第11章差錯控制編碼編出的碼組T(x)為T(x) = xn - k m(x) + r(x) 在上例中，T(x) =

50、1100000 + 101 = 1100101，它就是上表中的第7碼組。75第11章差錯控制編碼u循環(huán)碼的解碼方法p解碼要求：檢錯和糾錯。p檢錯解碼原理：由于任意一個碼組多項式T(x)都應該能被生成多項式g(x)整除，所以在接收端可以將接收碼組R(x)用原生成多項式g(x)去除。當傳輸中未發(fā)生錯誤時，接收碼組與發(fā)送碼組相同，即R(x) = T(x)，故接收碼組R(x)必定能被g(x)整除；若碼組在傳輸中發(fā)生錯誤，則R(x) T(x)，R(x)被g(x)除時可能除不盡而有余項，即有因此，就以余項是否為零來判別接收碼組中有無錯碼。需要指出，有錯碼的接收碼組也有可能被g(x)整除。這時的錯碼就不能檢

51、出了。這種錯誤稱為不可檢錯誤。不可檢錯誤中的誤碼數(shù)必定超過了這種編碼的檢錯能力。)(/ )()()(/ )(xgxrxQxgxR76第11章差錯控制編碼p糾錯解碼原理：為了能夠糾錯，要求每個可糾正的錯誤圖樣必須與一個特定余式有一一對應關系。因為只有存在上述一一對應的關系時，才可能從上述余式唯一地決定錯誤圖樣，從而糾正錯碼。因此，原則上糾錯可按下述步驟進行：用生成多項式g(x)除接收碼組R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通過某種計算得到錯誤圖樣E(x)；例如，通過計算校正子S和查表，就可以確定錯碼的位置。從R(x)中減去E(x)，便得到已經(jīng)糾正錯碼的原發(fā)送碼組T(x)。p

52、通常，一種編碼可以有幾種糾錯解碼方法，上述解碼方法稱為捕錯解碼法。 u目前多采用軟件運算實現(xiàn)上述編解碼運算。77第11章差錯控制編碼n11.6.3 截短循環(huán)碼截短循環(huán)碼u截短目的：在設計糾錯編碼方案時，常常信息位數(shù)k、碼長n和糾錯能力都是預先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。這時，可以采用將碼長截短的方法，得出滿足要求的編碼。u截短方法：設給定一個(n, k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i (0 i k)個信息位全為“0”，于是它變成僅有2k-i種碼組。然后從中刪去這i位全“0”的信息位，最終得到一個(n i, k i)的線性碼。將這種碼稱為截短循環(huán)碼。 u截短循環(huán)碼

53、性能：循環(huán)碼截短前后至少具有相同的糾錯能力，并且編解碼方法仍和截短前的方法一樣。 u例：要求構造一個能夠糾正1位錯碼的(13, 9)碼。這時可以由(15, 11)循環(huán)碼的11種碼組中選出前兩信息位均為“0”的碼組，構成一個新的碼組集合。然后在發(fā)送時不發(fā)送這兩位“0”。于是發(fā)送碼組成為(13, 9)截短循環(huán)碼。 78第11章差錯控制編碼n11.6.4 BCH碼u什么是BCH碼？它是一種獲得廣泛應用的能夠糾正多個錯碼的循環(huán)碼，是以3位發(fā)明這種碼的人名(Bose - Chaudhuri - Hocguenghem)命名的。BCH碼的重要性在于它解決了生成多項式與糾錯能力的關系問題，可以在給定糾錯能力

54、要求的條件下尋找到碼的生成多項式。有了生成多項式，編碼的基本問題就隨之解決了。uBCH碼分類：p本原BCH碼：其生成多項式g(x)中含有最高次數(shù)為m的本原多項式，且碼長為n = 2m 1，(m 3，為正整數(shù))。p非本原BCH碼：其生成多項式中不含這種本原多項式，且碼長n是(2m 1)的一個因子，即碼長n一定除得盡2m 1。79第11章差錯控制編碼uBCH碼的性能：p碼長n與監(jiān)督位、糾錯個數(shù) t 之間的關系：對于正整數(shù)m (m 3)和正整數(shù)t 1，且除得盡(2m -1)），則為非本原BCH碼。p漢明碼是能夠糾正單個隨機錯誤的碼。可以證明，具有循環(huán)性質(zhì)的漢明碼就是能糾正單個隨機錯誤的本原BCH碼。

55、p例如，(7, 4)漢明碼就是以g1(x) = x3 + x + 1或g2(x) = x3 + x2 + 1生成的BCH碼，而用g3(x) = x4 + x + 1或g4(x) = x4 + x3 + 1都能生成(15, 11)漢明碼。80第11章差錯控制編碼uBCH碼的設計p在工程設計中，一般不需要用計算方法去尋找生成多項式g(x)。因為前人早已將尋找到的g(x)列成表，故可以用查表法找到所需的生成多項式。p下表給出了碼長n 127的二進制本原BCH碼生成多項式。81第11章差錯控制編碼n = 3k t g(x)1 1 7n = 63k t g(x)57 1 10351 2 1247145

56、3 170131739 4 16662356736 5 103350042330 6 15746416534724 7 1732326040444118 10 136302651235172516 11 633114136723545310 13 4726223055272501557 15 52310455435032717371 31 全部為1n = 7k t g(x)4 1 131 3 77n = 15k t g(x)11 1 23 7 2 721 5 3 2467 1 7 7777782第11章差錯控制編碼n = 31 k t g(x)26 1 4521 2 355116 3 1076

57、5711 5 54233256 7 3133650471 15 = 127 k t g(x)120 1 211113 2 41567106 3 11554743 99 4 3447023271 92 5 624730022327 85 6 130704476322273 78 7 26230002166130115 71 9 6255010713253127753 64 10 1206534025570773100045 57 11 235265252505705053517721 50 13 54446512523314012421501421 43 15 1772

58、1772213651227521220574343 36 15 3146074666522075044764574721735 29 22 403114461367670603667530141176155 22 23 123376070404722522435445626637647043 15 27 22057042445604554770523013762217604353 8 31 7047264052751030651476224271567733130217 1 63 全部為183第11章差錯控制編碼p表中給出的生成多項式系數(shù)是用8進制數(shù)字列出的。例如，g(x) = (13)8是指

59、g(x) = x3 + x + 1，因為(13)8 = (1011)2，后者就是此3次方程g(x)的各項系數(shù)。p下表列出了部分非本原BCH碼的生成多項式參數(shù)。nktg(x)nktg(x)1721233341912122221223247271663534351456647133476565732453404652444307335710761354300067171777353784第11章差錯控制編碼p戈萊碼：在上表中的(23, 12)碼稱為戈萊(Golay)碼。它能糾正3個隨機錯碼，并且容易解碼，實際應用較多。p擴展BCH碼：BCH碼的長度都為奇數(shù)。在應用中，為了得到偶數(shù)長度的碼，并增大檢

60、錯能力，可以在BCH碼生成多項式中乘上一個因式(x + 1)，從而得到擴展BCH碼(n + 1, k)。擴展BCH碼相當于在原BCH碼上增加了一個校驗位，因此碼距比原BCH碼增加1。擴展BCH碼已經(jīng)不再具有循環(huán)性。例如，廣泛實用的擴展戈萊碼(24, 12)，其最小碼距為8，碼率為1/2，能夠糾正3個錯碼和檢測4個錯碼。它比漢明碼的糾錯能力強很多，付出的代價是解碼更復雜，碼率也比漢明碼低。此外，它不再是循環(huán)碼了。85第11章差錯控制編碼n11.6.5 RS碼：碼：它是一類具有很強糾錯能力的多進制BCH碼。u若仍用n表示RS碼的碼長，則對于m進制的RS碼，其碼長需要滿足下式：n = m 1 = 2