通信原理課件-第十章

第10章差錯控制編碼7.1概述7.2常用的幾種簡單分組碼7.3線性分組碼7.4循環(huán)碼1第10章差錯控制編碼7.1概述1

10.1概述

在數(shù)字信號傳輸中，由于信道不理想以及加性噪聲的影響，被傳輸?shù)男盘柎a元波形會變壞，造成接收端錯誤判決。為了盡量減小數(shù)字通信中信息碼元的差錯概率，應合理設計基帶信號并采用均衡技術以減小信道線性畸變引起的碼間干擾；對于由信道噪聲引起的加性干擾，應考慮采取加大發(fā)送功率、適當選擇調(diào)制解調(diào)方式等措施。但是隨著現(xiàn)代數(shù)字通信技術的不斷發(fā)展，以及傳輸速率的不斷提高，對信息碼元的差錯概率Pe的要求也在提高，例如計算機間的數(shù)據(jù)傳輸，要求Pe低于10-9，并且信道帶寬和發(fā)送功率受到限制，此時就需要采用信道編碼，又稱為差錯控制編碼。2

10.1概述2

信道編碼理論建立在香農(nóng)信息論的基礎上，其實質(zhì)是給信息碼元增加冗余度，即增加一定數(shù)量的多余碼元(稱為監(jiān)督碼元或校驗碼元)，由信息碼元和監(jiān)督碼元共同組成一個碼字，兩者間滿足一定的約束關系。如果在傳輸過程中受到干擾，某位碼元發(fā)生了變化，就破壞了它們之間的約束關系。接收端通過檢驗約束關系是否成立，完成識別錯誤或者進一步判定錯誤位置并糾正錯誤，從而提高通信的可靠性。3信道編碼理論建立在香農(nóng)信息論的基礎上

10.2差錯控制編碼的基本概念

10.2.1差錯控制方式

在差錯控制系統(tǒng)中，差錯控制方式主要有三種。

1.前向糾錯控制方式(FEC)

又稱自動糾錯，是指發(fā)送端發(fā)出的可以糾正錯誤碼元的編碼序列，接收端的譯碼器能自動糾正傳輸中的錯碼，系統(tǒng)框圖如圖10.2.1(a)所示。這種方式的優(yōu)點是不需要反饋信道，譯碼實時性好，具有恒定的信息傳輸速率。缺點是為了要獲得比較低的誤碼率，必須以最壞的信道條件來設計糾錯碼，故需要附加較多的監(jiān)督碼元，這樣既增加了譯碼算法選擇的難度，也降低了系統(tǒng)的傳輸效率，所以不適宜應用在傳輸條件惡化的信道。

4

10.2差錯控制編碼的基本概念10.

2.反饋重發(fā)糾錯方式(ARQ)

發(fā)送端發(fā)出的是能夠檢測錯誤的編碼序列，接收端譯碼器根據(jù)編碼規(guī)則進行判決，并通過反饋信道把判決結果回傳，無錯認可(ACK)，有錯時否認(NAK)。發(fā)送端根據(jù)回傳指令，將有錯的碼組重發(fā)，直到接收端認為正確接收為止，系統(tǒng)框圖如圖10.2.1(b)所示。

優(yōu)點：檢錯碼構造簡單，不需要復雜的編譯碼設備，在冗余度一定的條件下，檢錯碼的檢錯能力比糾錯碼的糾錯能力強得多，故整個系統(tǒng)的誤碼率可以保持在極低的數(shù)量級上。

缺點：需要反饋信道，并要求發(fā)送端有大容量的信源存儲器，且為保證收、發(fā)兩端互相配合，控制電路較為復雜。另外，當信道干擾很頻繁時，系統(tǒng)經(jīng)常處于重發(fā)消息的狀態(tài)，使傳送信息的實時性變差。55

3．混合糾錯方式(HEC)

該方式是上述兩種方式的結合，即在ARQ系統(tǒng)中包含一個FEC子系統(tǒng)，系統(tǒng)框圖如圖10.2.1(c)所示。發(fā)送端發(fā)出的是具有一定糾錯能力和較強檢錯能力的碼，所以經(jīng)信道編碼而附加的監(jiān)督碼元并不多。接收端檢測數(shù)據(jù)碼流，發(fā)現(xiàn)錯誤先由FEC子系統(tǒng)自動糾錯，僅當錯誤較多超出糾錯能力時，再發(fā)反饋信息要求重發(fā)，因此大大減少了重發(fā)次數(shù)。HEC在一定程度上彌補了反饋重發(fā)和前向糾錯兩種方式的缺點，充分發(fā)揮了碼的檢、糾錯能力，在較強干擾的信道中仍可獲得較低誤碼率，是實際通信中應用較多的糾錯方式。63．混合糾錯方式(HEC)677

10.2.2差錯控制編碼的分類

用不同的方法可以對差錯控制編碼進行不同的分類。1.根據(jù)已編碼組中信息碼元與監(jiān)督碼元之間的函數(shù)關系，可分為線性碼及非線性碼。若信息碼元與監(jiān)督碼元之間的關系呈線性，即滿足一組線性方程式，則稱為線性碼。否則稱為非線性碼。

810.2.2差錯控制編碼的分類8

2.根據(jù)信息碼元和監(jiān)督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監(jiān)督碼元僅與本碼組的信息碼元有關，卷積碼的監(jiān)督碼元不僅與本組信息碼元有關，而且與前面若干碼組的信息碼元有約束關系。

3.根據(jù)編碼后信息碼元是否保持原來的形式，可分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元保持原樣，而非系統(tǒng)碼中的信息碼元則改變了原來的信號形式。92.根據(jù)信息碼元和監(jiān)督碼元之間的約

4.根據(jù)編碼的不同功能，可分為檢錯碼、糾錯碼和糾刪碼。檢錯碼只能夠發(fā)現(xiàn)錯誤，但不能糾正錯誤；糾錯碼能夠糾正錯誤；糾刪碼即可以檢錯又可以糾錯，但糾錯能力有限，當有不能糾正的錯誤時將發(fā)出錯誤指示或刪除不可糾正的錯誤段落。

5.根據(jù)糾正、檢驗錯誤的類型不同，可分為糾正、檢驗隨機性錯誤的碼和糾正、檢驗突發(fā)性錯誤的碼。

6.根據(jù)碼元取值的不同，可分為二進制碼和多進制碼。這里只介紹二進制糾、檢錯編碼。104.根據(jù)編碼的不同功能，可分為檢錯碼

10.2.3檢錯和糾錯的基本原理差錯控制編碼的基本思想是在被傳輸?shù)男畔⒋a元中附加一些監(jiān)督碼元，并且使它們之間確定某一種關系，根據(jù)傳輸過程中這種關系是否被破壞來發(fā)現(xiàn)或糾正錯誤?？梢娺@種差錯控制能力是用增加信息量的冗余度來換取的。

設編碼后的碼組長度、碼組中所含信息碼元個數(shù)以及監(jiān)督碼元個數(shù)分別為n、k和r，三者間滿足n=k+r，定義編碼效率為R=k/n=1-r/n?？梢姶a組長度一定時，所加入的監(jiān)督碼元個數(shù)越多，編碼效率越低。1110.2.3檢錯和糾錯的基本原理

香農(nóng)的信道編碼定理指出:對于一個給定的有擾信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進制碼元速率），則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值?？梢员硎緸槠渲蠩(R)稱為誤差指數(shù)，它與R和C的關系如圖10.2.2所示。(10.2.1)12香農(nóng)的信道編碼定理指出:(10.21313

由定理有如下結論:1.在碼長及發(fā)送信息速率一定的情況下，為減小P可以增大信道容量。由圖10.2.2可知，E(R)隨信道容量的增加而增大。由式(10.2.1)可知，錯誤概率隨E(R)的增大而指數(shù)下降。2.在信道容量及發(fā)送信息速率一定的條件下，增加碼長，可以使錯誤概率指數(shù)下降。對于實際應用來說，此時的設備復雜性和譯碼延時也隨之增加。14由定理有如下結論:14

香農(nóng)的信道編碼定理為信道編碼奠定了理論基礎，雖然定理本身并沒有給出具體的差錯控制編碼方法和糾錯碼的結構，但它從理論上為信道編碼的發(fā)展指出了努力方向。

我們用3位二進制碼組來說明檢錯糾錯的基本原理。3位二進制碼元共有8種可能的組合:000、001、010、011、100、101、110、111。如果這8種碼組都可傳遞消息，若在傳輸過程中發(fā)生一個誤碼，則一種碼組會錯誤地變成另一種碼組。由于每一種碼組都可能出現(xiàn)，沒有多余的信息量，因此接收端不可能發(fā)現(xiàn)錯誤，認為發(fā)送的就是另一種碼組。15香農(nóng)的信道編碼定理為信道編碼奠定了理

如果選其中000、011、101、110來傳送消息，這相當于只傳遞00、01、10、11四種信息，而第3位是附加的。這位附加的監(jiān)督碼元與前面兩位碼元一起，保證碼組中“1”碼的個數(shù)為偶數(shù)。這4種碼組稱為許用碼組。另外4種碼組不滿足這種校驗關系，稱為禁用碼組，它們在編碼后的發(fā)送碼元中不會出現(xiàn)。接收時一旦發(fā)現(xiàn)有禁用碼組，就表明傳輸過程中發(fā)生了錯誤。用這種簡單的校驗關系可以發(fā)現(xiàn)1個或3個錯誤，但不能糾正錯誤。因為當接收到的碼組為禁用碼組時，比如為010，無法判斷發(fā)送的是哪個碼組。雖然原發(fā)送碼組為101的可能性很小(因為3個誤碼的概率一般很小)，但不能絕對排除，即使傳輸過程中只發(fā)生一個誤碼，也有三種可能的發(fā)送碼組即000、011和110。16如果選其中000、011、101、1

假如我們進一步將許用碼組限制為二種即000和111，顯然這樣可以發(fā)現(xiàn)所有2位以下的誤碼，若用來糾錯，可以用最大似然準則糾正1位錯誤?？梢杂靡粋€三維立方體來表示上述3位二進制碼組的例子，如圖10.2.3所示。圖中立方體各頂點分別表示8位碼組，3位碼元依次表示x、y、z軸的坐標。17假如我們進一步將許用碼組限制為二種即1818

這里定義碼組中非零碼元的數(shù)目為碼組的重量，簡稱碼重。比如100碼組的碼重為1，101碼組的碼重為2。定義兩個碼組中對應碼位上具有不同二進制碼元的位數(shù)為兩碼組的距離，稱為漢明(Hamming)距，簡稱碼距。在前面3位二進制碼組的例子中，當8種碼組均為許用碼組時，兩碼組間的最小距離為1，稱這種編碼的最小碼距為1，一般記為dmin=l；當選4種碼組為許用碼組時，最小碼距dmin

=2；當用2種碼組作為許用碼組時，dmin=3。19這里定義碼組中非零碼元的數(shù)目為碼組的

從圖10.2.3所示的立方體可以看出，碼距就是從一個頂點沿立方體各邊移到另一個頂點所經(jīng)過的最少邊數(shù)。圖中粗線表示000與111之間的一條最短路徑。很容易得出前例中各種情況下的碼距。根據(jù)以上分析可知，編碼的最小碼距直接關系到這種碼的檢錯和糾錯能力，所以最小碼距是差錯控制編碼的一個重要參數(shù)。對于分組碼一般有以下結論:20從圖10.2.3所示的立方體可以看出

1.在一個碼組內(nèi)檢測e個誤碼，要求最小碼距dmin≥e+1(10.2.2)2.在一個碼組內(nèi)糾正t個誤碼，要求最小碼距dmin≥2t+1(10.2.3)3.在一個碼組內(nèi)糾正t個誤碼，同時檢測e(e≥t)個誤碼，要求最小碼距dmin≥t+e+1(10.2.4)這些結論可以用圖10.2.4所示的幾何圖形簡單的給予證明。211.在一個碼組內(nèi)檢測e個誤碼，要求2222

可見dmin體現(xiàn)了碼組的糾、檢錯能力。碼組間最小距離越大，說明碼字間最小差別越大，抗干擾能力就越強。

由于編碼系統(tǒng)具有糾錯能力，因此在達到同樣誤碼率要求時，編碼系統(tǒng)會使所要求的輸入信噪比低于非編碼系統(tǒng)，為此引入了編碼增益的概念。其定義為，在給定誤碼率下，非編碼系統(tǒng)與編碼系統(tǒng)之間所需信噪比Eb/N0之差(用dB表示)。采用不同的編碼會得到不同的編碼增益，但編碼增益的提高要以增加系統(tǒng)帶寬或復雜度來換取。23可見dmin體現(xiàn)了碼組的糾、檢錯能

10.2.4常用的簡單檢錯碼

常用檢錯碼的結構一般都很簡單，由于這些碼組具有較強的檢錯能力，并且易于實現(xiàn)，所以在實際當中應用很廣泛。

1．奇偶校驗碼奇偶校驗碼又稱奇偶監(jiān)督碼，它只有一個監(jiān)督碼元，是一種最簡單的檢錯碼，在計算機數(shù)據(jù)傳輸中得到廣泛應用。編碼時，首先將要傳送的信息分組，按每組中“1”碼的個數(shù)計算監(jiān)督碼元的值。編碼后，整個碼組中“1”碼個數(shù)成為奇數(shù)的稱奇校驗，成為偶數(shù)的稱偶校驗。2410.2.4常用的簡單檢錯碼

設碼組長度為n，其中前n-1位(an-1,an-2

,?,a1)是信息碼元，a0是監(jiān)督碼元，二者之間的監(jiān)督關系可用公式表示。

奇校驗滿足

偶校驗滿足(10.2.6)(10.2.5)25設碼組長度為n，其中前n-1位(a

接收端用一個模2加法器就可以完成檢錯工作。當錯碼為一個或奇數(shù)個時，因打亂了“1”數(shù)目的奇偶性，故能發(fā)現(xiàn)差錯。然而，當錯誤個數(shù)為偶數(shù)時，由于未破壞“l(fā)”數(shù)目的奇偶性，所以不能發(fā)現(xiàn)偶數(shù)個錯碼。26接收端用一個模2加法器就可以完成檢錯

2．行列監(jiān)督碼

行列監(jiān)督碼也叫方陣校驗碼，編碼原理與簡單的奇偶監(jiān)督碼相似，不同之處在于每個碼元都要受到縱、橫兩個方向的監(jiān)督。以圖10.2.5為例，有28個待發(fā)送的數(shù)據(jù)碼元，將它們排成4行7列的方陣。方陣中每行是一個碼組，每行的最后加上一個監(jiān)督碼元進行行監(jiān)督，同樣在每列的最后也加上一個監(jiān)督碼元進行列監(jiān)督，然后按行(或列)發(fā)送。接收端按同樣行列排成方陣，發(fā)現(xiàn)不符合行列監(jiān)督規(guī)則的判為有錯。它除了能檢出所有行、列中的奇數(shù)個錯誤外，也能發(fā)現(xiàn)大部分偶數(shù)個錯誤。因為如果碰到差錯個數(shù)恰為4的倍數(shù)，而且差錯位置正好處于矩形四個角的情況，方陣碼無法發(fā)現(xiàn)錯誤。27

2828

行列監(jiān)督碼在某些條件下還能糾錯，觀察第3行、第4列出錯的情況，假設在傳輸過程中第3行、第4列的“1”錯成“0”，由于此錯誤同時破壞了第3行、第4列的偶監(jiān)督關系，所以接收端很容易判斷是3行4列交叉位置上的碼元出錯，從而給予糾正。

行列監(jiān)督碼也常用于檢查或糾正突發(fā)錯誤。它可以檢查出錯誤碼元長度小于和等于碼組長度的所有錯碼，并糾正某些情況下的突發(fā)差錯。

行列監(jiān)督碼實質(zhì)上是運用矩陣變換，把突發(fā)差錯變成獨立差錯加以處理。因為這種方法比較簡單，所以被認為是克制突發(fā)差錯很有效的手段。29行列監(jiān)督碼在某些條件下還能糾錯，觀

3.恒比碼

恒比碼又稱等比碼或等重碼。恒比碼的每個碼組中，“1”和“0”的個數(shù)比是恒定的。我國電傳通信中采用的五單位數(shù)字保護電碼是一種3∶2等比碼，也叫五中取三的恒比碼，即在5單位電傳碼的碼組中(25=32)，取其“1”的數(shù)目恒為3的碼組(C53=10)，代表10個字符(0～9)，如表10.2.1所示。因為每個漢字是以四位十進制數(shù)表示的，所以提高十進制數(shù)字傳輸?shù)目煽啃?，相當于提高了漢字傳輸?shù)目煽啃浴?03.恒比碼30

國際電傳電報上通用的ARQ通信系統(tǒng)中，選用三個“1”、四個“0”的3:4碼，即七中取三碼。它有C73=35個碼組，分別表示26個字母及其他符號。

在檢測恒比碼時，通過計算接收碼組中“1”的數(shù)目，判定傳輸有無錯誤。除了“1”錯成“0”和“0”錯成“1”成對出現(xiàn)的錯誤以外，這種碼能發(fā)現(xiàn)其他所有形式的錯誤，因此檢錯能力很強。實踐證明，應用這種碼，國際電報通信的誤碼率保持在10-6以下。3131

4.ISBN國際統(tǒng)一圖書編號

國際統(tǒng)一圖書編號是一種檢錯碼，以防止書號在通信過程中發(fā)生誤傳。這里以編號ISBN0-1315-2447-X為例，其中第一位數(shù)字“0”表示該書是美國及其它英語國家的出版物(中國的代號是數(shù)字“7”)，“1315”代表出版公司，“2447”代表書名編號，最后一位數(shù)字“X”是校驗位(這是10的羅馬字表示)。這里采用的校驗方法如圖10.2.6所示。324.ISBN國際統(tǒng)一圖書編號323333

圖中第1行為ISBN編號。第2行第1個數(shù)字與第1行第1個數(shù)字相同；第2行第2個數(shù)字則為第1行第2個數(shù)字與第2行第1個數(shù)字之和，即1+0=1；第2行第3個數(shù)字為第1行第3個數(shù)字與第2行第2個數(shù)字之和，即3+1=4；依次類推，第2行最后所得的累計和為37。用同樣方法得到第3行的最后累計和為132。然后用模11對132進行校驗，132(mod11)≡0。

顯然，若通信過程中統(tǒng)一書號發(fā)生了錯誤，則上累計和就不能被11所整除，從而可校驗出來。34圖中第1行為ISBN編號。第2行第10.3線性分組碼

10.3.1基本概念

一個長為n的分組碼，碼字由兩部分構成，即信息碼元(k位)+監(jiān)督碼元(r位)。監(jiān)督碼元是根據(jù)一定規(guī)則由信息碼元變換得到的，變換規(guī)則不同就構成不同的分組碼。如果監(jiān)督位為信息位的線性組合，就稱其為線性分組碼。

要從k個信息碼元中求出r個監(jiān)督碼元，必須有r個獨立的線性方程。根據(jù)不同的線性方程，可得到不同的(n,k)線性分組碼。3510.3線性分組碼10.3.1基本概念35

例如，已知一個(7，4)線性分組碼，4個信息碼元a6、a5、a4、a3和3個監(jiān)督碼元a2、a1、a0之間符合以下規(guī)則

計算上式得到此(7，4)線性分組碼的全部碼組，列于表10.3.1中(許用碼組的個數(shù)等于k個信息碼元的全部組合數(shù)2k個)。(10.3.1)36例如，已知一個(7，4)線性分組碼，43737

前面介紹的奇偶監(jiān)督碼是一種最簡單的線性碼。改寫式(10.2.5)、式(10.2.6)可以得到監(jiān)督碼元a0和信息碼元之間的關系。

奇校驗

偶校驗(10.3.2)(10.3.3)38前面介紹的奇偶監(jiān)督碼是一種最簡單的線

線性碼各許用碼組的集合構成了代數(shù)學中的群，因此又稱群碼。它有如下性質(zhì):

1）任意兩許用碼組之和(按位模2加)仍為一許用碼組，即線性碼具有封閉性；

2）集合中的最小距離等于碼組中非全“0”碼字的最小重量。

在群中只存在一種運算，即模2加，通常四則運算中的加、減法在這里都是模2加的關系。所以后面將簡化運算符號⊕為“+”。

為了說明(n,k)線性分組碼的編碼原理，下面引入監(jiān)督矩陣H和生成矩陣G的概念。39線性

10.3.2監(jiān)督矩陣和生成矩陣

1.監(jiān)督矩陣H

改寫式(10.3.1)所示(7，4)線性分組碼的3個線性方程式

寫成矩陣形式(10.3.4)(10.3.5)4010.3.2監(jiān)督矩陣和生成矩陣或(10.3.6)41或(10.3.6)41分別記作或

式中

是r×n階矩陣，稱為線性分組碼的一致監(jiān)督矩陣(或校驗矩陣)。(10.3.8)(10.3.7)(10.3.9)42分別記作(10.3.8)(10.3.7)(10.3.9)

AT、0T、HT分別是A、0、H矩陣的轉置。

對于碼字A來說，恒有

或

成立，即當監(jiān)督矩陣H給定時，利用式(10.3.7)可以驗證接收碼是否正確。

H矩陣可以分成兩部分:43AT、0T、HT分別是A、0、H矩陣

H矩陣可以分成兩部分:

式中P為r×k階矩陣，Ir為r×r階單位方陣，具有[PIr]形式的H矩陣被稱為典型矩陣。線性代數(shù)的基本理論指出，典型形式的監(jiān)督矩陣各行一定是線性無關的，非典型形式的監(jiān)督矩陣可以經(jīng)過線性變換化為典型形式，除非非典型形式監(jiān)督矩陣的各行不是線性無關的。(10.3.10)44H矩陣可以分成兩部分:(10.3

2.生成矩陣G

改寫式(10.3.1)為矩陣形式

或者(10.3.11)(10.3.12)452.生成矩陣G(10.3.11)(10.3.

其中Q為k×r階矩陣。該式表明，已知Q矩陣，同樣可以由信息位算出監(jiān)督碼元。不難看出,Q是P的轉置，即

如果在Q的左邊加上一個k×k階單位方陣，就構成了生成矩陣(10.3.13)(10.3.14)46其中Q為k×r階矩陣。該式表明，已知

稱G為生成矩陣，是因為利用它可以產(chǎn)生碼組A，即

符合[IkQ]形式的生成矩陣稱為典型形式的生成矩陣，由該矩陣得到的碼組是系統(tǒng)碼。利用此生成矩陣同樣可以得到表10.3.1中給出的(7，4)線性分組碼的全部碼字。

同樣，典型形式的生成矩陣的各行也必定是線性無關的，每行都是一個許用碼組，k行許用碼組經(jīng)過行運算可以生成2k個不同的許用碼組。非典型形式的生成矩陣經(jīng)過運算也一定可以化為典型形式。

典型監(jiān)督矩陣和典型生成矩陣之間存在關系

(10.3.15)(10.3.16)47稱G為生成矩陣，是因為利用它可以產(chǎn)生

10.3.3伴隨式（校正子）

發(fā)送碼組A=[an-1an-2

?a0

]在傳輸過程中可能會發(fā)生誤碼。設接收到的碼組為B=[bn-1bn-2

?b0]，則收、發(fā)碼組之差為B–A=E

或?qū)懗葿=A+E

式中E=[en-1en-2

?e0]為錯誤圖樣。

令

S=BHT

為分組碼的伴隨式(亦稱校正子或校驗子)。

利用式(10.3.8)，可以得到S=(A+E)HT=AHT+EHT=EHT

這樣就把校正子S與接收碼組B的關系轉換成了校正子S與錯誤圖樣E的關系。(10.3.17)(10.3.18)(10.3.19)4810.3.3伴隨式（校正子）(10.3.17

在接收機中只要用式(10.3.18)計算校正子S，并判斷計算結果是否為0，就可完成檢錯工作。因為如果是正確接收(E=0)，則B=A+E=A，依照式(10.3.8)有S=BHT=AHT=0

如果接收碼組不等于發(fā)送碼組(B≠A)，則E≠0，故S=EHT≠0。

在討論怎樣利用校正子S完成糾錯工作之前，先看一下S與E的關系。

前面所說的(7，4)線性分組碼[見式(10.3.9)]

49在接收機中只要用式(10.3.18)計

設接收碼組的最高位有錯，錯誤圖樣E=[1000000]，計算5050

它的轉置

恰好是典型監(jiān)督矩陣H中的第一列。

如果是接收碼組B中的次高位有錯，E=[0100000]，那么算出的S=[110]，其轉置ST恰好是典型監(jiān)督矩陣H中的第二列。

換言之，在接收碼組只錯一位碼元的情況下，計算出的校正子S總是和典型監(jiān)督矩陣HT中的某一行相同?？梢宰C明，只要不超出線性分組碼的糾錯能力，接收機依據(jù)計算出的校正子S，可以判斷碼組的錯誤位置并予以糾正。這里僅討論糾正一位錯誤碼元的情況。51它的轉置51

例10.3.1已知前述(7，4)線性分組碼某碼組，在傳輸過程中發(fā)生一位誤碼，設接收碼組B=[0000101]，試將其恢復為正確碼組。解:(1)首先確定碼組的糾、檢錯能力查表10.3.1，得到最小碼距dmin=3，故此碼組可以糾正一位錯碼或檢測兩位錯誤碼元。(2)計算ST52例10.3.1已知前述(7，4)線已知前述(7,4)線性分組碼的典型監(jiān)督矩陣利用矩陣性質(zhì)汁算校正子的轉置53已知前述(7,4)線性分組碼的典型監(jiān)督矩陣53

(3)恢復正確碼組因為此碼組具有糾正一位錯誤的能力，且計算結果ST與H矩陣中的第三列相同，相當于得到錯誤圖樣E=[0010000]，所以正確碼組為A=B+E

=[0000101]+[0010000]=[0010101]54(3)恢復正確碼組54

10.3.4漢明碼

漢明碼是一種可以糾正單個隨機錯誤的線性分組碼。它的最小碼距dmin=3，監(jiān)督碼元位數(shù)r=n–k(r是一個大于或等于2的正整數(shù))，碼長n=2r-1，信息碼元位數(shù)k=2r-1-r,編碼效率R=k/n=(2r-1-r)/(2r-1)=1-r/(2r-1)。當r很大時，極限趨于1，所以是一種高效碼。

漢明碼的監(jiān)督矩陣H有n列r行，它的n列由不全為0的二進制r位碼的不同組合構成，即每種組合只在某列中出現(xiàn)一次。55

10.3.4漢明碼55

以r=3為例，它的碼長n=23-1=7，所以前面所說的(7，4)線性分組碼就是漢明碼，并且任意調(diào)換H矩陣中各列的位置，不會影響碼的糾、檢錯能力。例如可以構造出與式(10.3.9)不同的監(jiān)督矩陣，即

其相應的生成矩陣為(10.3.21)(10.3.20)56以r=3為例，它的碼長n=23-

因此，漢明碼H矩陣中各列的位置還可以有其它多種排列形式。

漢明碼的譯碼方法，可以采用計算校正子，然后確定錯誤圖樣并加以糾正的方法。圖10.3.1中給出式(10.3.20)所示(7，4)漢明碼的編碼器和譯碼器電路圖。57因此，漢明碼H矩陣中各列的位置還可以5858

糾正單個錯誤的漢明碼中，r位校正子碼組與誤碼圖樣一一對應，最充分地利用了監(jiān)督位所能提供的信息，這種碼稱為完備碼。在一般情況下，對于能糾正t個錯誤的線性分組碼(n，k)，應滿足不等式(10.3.22)59糾正單個錯誤的漢明碼中，r位校正子碼組與誤碼圖樣

這里，

為中n取i的組合，其物理意義是n位碼組中有i個誤碼的錯誤圖樣數(shù)目(i≠0)。

式(10.3.22)取等號時，校正子與誤碼不超過t個的所有錯誤圖樣一一對應，監(jiān)督碼元得到最充分的利用，這種(n，k)碼即為完備碼。

除了漢明碼外，迄今為止已找到的唯一能糾正多個錯誤的完備碼是(23，12)非本原BCH碼，常稱為戈雷碼。60這里，為中n取i的組合，其物理意10.4循環(huán)碼

循環(huán)碼是線性分組碼中一個最重要的分支。它的檢、糾錯能力較強，編碼和譯碼設備并不復雜，所以循環(huán)碼受到人們的高度重視，在前向糾錯系統(tǒng)中得到了廣泛應用。

循環(huán)碼有嚴密的代數(shù)理論基礎，是目前研究得最成熟的一類碼。這里對循環(huán)碼不作嚴格的數(shù)學分析，只重點介紹循環(huán)碼在差錯控制中的應用。6110.4循環(huán)碼循環(huán)碼是線性分組碼中

10.4.1循環(huán)碼的特點

循環(huán)碼有兩個數(shù)學特征：

1）線性分組碼的封閉性；

2）循環(huán)性，即任一許用碼組經(jīng)過循環(huán)移位后所得到的碼組仍為該許用碼組集合中的一個碼組。

表10.4.1列出了某(7，3)循環(huán)碼的全部碼組。6210.4.1循環(huán)碼的特點62

以2號碼組(0010111)為例，左移循環(huán)一位變成3號碼組(0101110)，依次左移一位構成的狀態(tài)圖如圖10.4.1所示。63以2號碼組(0010111)為例，左

可見除全零碼組外，不論循環(huán)右移或左移，移多少位，其結果均在該循環(huán)碼組的集合中(全零碼組自己構成獨立的循環(huán)圈)。

為了用代數(shù)學理論研究循環(huán)碼，可將碼組用多項式表示，稱為碼多項式。循環(huán)碼組中各碼元分別為多項式的系數(shù)。長度為n的碼組A=(an-1an-2

?a1a0)用碼多項式可表示為(10.4.2)64可見除全零碼組外，不論循環(huán)右移或左移

若左移i位后的碼組A(i)=(an-i-1an-i-2

?an-i+1an-i

)，其碼多項式為A(i)(x)可以用下式由xiA(x)求得:

這里Q(x)是xiA(x)除以(xi

+1)的商式，而A(i)(x)是所得的余式。式(10.4.4)也可表示為(10.4.3)(10.4.4)(10.4.5)65若左移i位后的碼組A(i)=(an

在A(x)的表達式中，系數(shù)ai=0的項常略去不寫，ai=1的項只寫符號x及其冪次。

碼多項式之間可以進行代數(shù)運算，在二元碼中遵循模2運算的規(guī)則。根據(jù)線性碼的封閉性，任意兩碼字經(jīng)模運算后仍為本碼組中的碼字。

從代數(shù)學的角度，每個二進制碼組可以看成是只有0和1兩個元素的二元域中的n重。所有二元n重的集合稱為二元域上的一個矢量空間。二元域上只有兩種運算，即加和乘，所有運算結果也必定在同一個二元集合中。66在A(x)的表達式中，系數(shù)ai=0的

在二元域中加和乘的運算規(guī)則定義為

一組多項式就構成一個(n,k)循環(huán)碼。也就是說，階數(shù)小于等于n-1能被g(x)除盡的每個多項式都是該循環(huán)碼的許用碼組。(n,k)循環(huán)碼有2k個碼組，因為可以構成循環(huán)許用碼組A(x)的信息碼組m(x)有2k個。67在二元域中加和乘的運算規(guī)則定義為67

這里，m(x)為不大于k-1階的多項式。

例如，令n＝7，g(x)＝x4+x3+x2+1是x7+1的一個因式，共有8個階次不大于6的多項式是g(x)的倍式，即(10.4.6)68這里，m(x)為不大于k-1階的多

這8個多項式是一個(7，3)循環(huán)碼。由于它有8個碼組，k＝3，因此n-k＝7-3＝4，這必定是生成多項式的階次。

為了尋找生成多項式，必須對xn

+1進行因式分解，這可以用計算機來完成。對于某些n值，xn+1只有很少幾個因式，因而碼長為這些n值的循環(huán)碼很少。僅對于很少幾個n值才有很多因式。69這8個多項式是一個(7，3)循環(huán)碼。

對于任意n值有

若取x+1為生成多項式，這樣構成的循環(huán)碼就是簡單的偶監(jiān)督碼(n，n-1)。由于g(x)為一階多項式，因此只有一位監(jiān)督碼?？梢宰C明，x+1的任何倍式的碼重（即碼組中1的個數(shù)）必定保持偶數(shù)。這是一種最簡單的循環(huán)碼，dmin

=2。(10.4.7)70對于任意n值有(10.4.7)70

另一個最簡單的循環(huán)碼是以xn-1

+xn-2

+?+x+1為生成多項式，由于生成多項式是n-1階．故信息碼位為1。只有兩種碼組即全0和全1，因此這種循環(huán)碼是重復碼(n，1)，dmin=n。

任何(n,k)循環(huán)碼的生成多項式g(x)，用乘上(x+1)后得到生成多項式g(x)·(x+1)所構造的循環(huán)碼(n，k-1)，其最小碼距增加1。(n，k-1)碼是(n，k)碼的一個子集。71另一個最簡單的循環(huán)碼是以xn-1+

以因式分解中的本原多項式作為生成多項式，可以構造出糾正一個錯誤的循環(huán)漢明碼。

考查表10.4.1，其中n-k=4階的多項式只有編號為(2)的碼組(0010111)，所以表中所示(7，3)循環(huán)碼組的生成多項式g(x)=x4+x2+x+1，并且該碼組集合中的任何碼多項式A(x)都可由信息位乘以生成多項式得到7272

式中(mk-1

mk-2?m1

m0)為信息碼元。

對于(7，k)循環(huán)碼，有

表10.4.1中所示(7，3)循環(huán)碼組的g(x)，是由式(10.4.9)中第1、3兩項相乘得到的。

如果令式(10.4.9)中第1、2兩項相乘，也得到一個4階多項式，由它可以構成另一個(7，3)循環(huán)碼組的集合?？梢娺x擇不同的因式組合會得到不同的生成多項式，從而構成不同的循環(huán)碼組。(10.4.8)(10.4.9)73(10.4.8)(10.4.9)73

由于g(x)為n-k階多項式，以與此相對應的碼組作為生成矩陣中的一行，可以證明g(x)，xg(x)，?，xk-1g(x)等多項式必定是線性無關的。把這k個多項式相對應的碼組作為各行構成的矩陣即為生成矩陣，由各行的線性組合可以得到2k個循環(huán)碼碼組。這樣循環(huán)碼的生成矩陣多項式可以寫成(10.4.10)74由于g(x)為n-k階多項式，以與此

以表10.4.1中的生成多項式g(x)構造G(x)，相應的矩陣形式為

作線性變換，整理成典型形式的生成矩陣(10.4.12)(10.4.11)75以表10.4.1中的生成多項式g(x

信息碼元與式(10.4.12)相乘，得到的就是系統(tǒng)循環(huán)碼。

由式(10.4.10)生成矩陣得到的循環(huán)碼并非系統(tǒng)碼。在系統(tǒng)碼中碼組的最左k位是信息碼元，隨后是n-k位監(jiān)督碼元。這相當于碼多項式為76信息碼元與式(10.4.12)相乘，得

這里r(x)=rn-k-1xn-k-1+?+r0為監(jiān)督碼多項式，其相應的監(jiān)督碼元為(rn-k-1,?,r0)。由式(10.4.14)可知

可見，構造系統(tǒng)循環(huán)碼時，只需將信息碼多項式升n-k階(即乘上xn-k

)，然后以g(x)為模，即除以g(x)，所得余式r(x)即為監(jiān)督碼元。因此，系統(tǒng)循環(huán)碼的編碼過程就變成用除法求余的問題。

系統(tǒng)碼的生成矩陣為典型形式G=[IkQ]，與單位矩陣Ik每行對應的信息多項式為(10.4.14)(10.4.15)77這里r(x)=rn-k-1xn-k-由式(10.4.15)可得相應的監(jiān)督多項式為由此得到生成矩陣中每行的碼多項式為因此系統(tǒng)循環(huán)碼生成矩陣多項式的一般表示為(10.4.18)(10.4.17)(10.4.16)78由式(10.4.15)可得相應的監(jiān)督多項式為(10.4.1

10.4.3監(jiān)督多項式與監(jiān)督矩陣

如前所述，在(n,k)循環(huán)碼中，xn

+l可分解成g(x)和其它因式的乘積，記為

由于g(x)是常數(shù)項為1的r次多項式，則h(x)為k次多項式,即h(x)=hkxk+?+h1x+h0,稱h(x)為監(jiān)督多項式。若g(x)=gn-kxn-k

+?+g1x+g0，由式(10.4.19)可知，必定有(10.4.19)7910.4.3監(jiān)督多項式與監(jiān)督矩陣(10.

這樣可以得到循環(huán)碼的監(jiān)督矩陣為

它有n-k行n列，完全由h(x)的系數(shù)確定，可以證明GHT=0。(10.4.20)(10.4.21)80(10.4.20)(10.4.21)80

與式(10.4.10)給出的G(x)相對應，監(jiān)督矩陣多項式可用下式表示

其中h*(x)是h(x)的逆多項式。

典型形式的監(jiān)督矩陣可以由式(10.4.22)作線性變換得到。(10.4.22)81與式(10.4.10)給出的G(x)

例10.4.1已知(7，4)系統(tǒng)碼的生成多項式為g(x)=x3+x2+1，求生成矩陣。解：由式(10.4.16)可得

(10.4.23)82例10.4.1已知(7，4)系統(tǒng)碼的生成因此，生成矩陣多項式表示為由多項式系數(shù)得到的生成矩陣為(10.4.25)(10.4.24)83因此，生成矩陣多項式表示為(10.4.25)(10.4.24

10.4.4系統(tǒng)循環(huán)碼的編譯碼方法

1.系統(tǒng)循環(huán)碼的編碼

對于碼組前k位是信息碼元的系統(tǒng)碼，用多項式表示則為

式中，m(x)是不大于(k-1)次的多項式，代表信息碼元；r(x)是不大于(r-1)次的多項式，代表監(jiān)督碼元。

若令式(10.4.8)中的信息碼元為m‘(x)，則碼組多項式可寫成(10.4.27)(10.4.26)8410.4.4系統(tǒng)循環(huán)碼的編譯碼方

聯(lián)立式(10.4.26)、式(10.4.27)得

即

這就是循環(huán)碼編碼的數(shù)學依據(jù)，式中為m‘(x)商，r(x)為余式。(10.4.28)85聯(lián)立式(10.4.26)、式(10.

利用生成多項式g(x)作除法運算的循環(huán)碼編碼方法歸納如下:

1）信息多項式m(x)左移n-k位，即相當于m(x)乘因子xn-k；

2）以g(x)為除式作模運算，得余式r(x)；即

3）余式的系數(shù)作監(jiān)督碼元，附加在信息碼元之后形成系統(tǒng)碼，相當于令余式r(x)和已經(jīng)左移n-k位的信息碼多項式作按位模2加運算。即(10.4.29)(10.4.30)86利用生成多項式g(x)作除法運算的循8787

以上編碼方法的實現(xiàn)電路并不復雜，多項式除法可以用帶反饋的線性移位寄存器來實現(xiàn)。有兩種不同的除法電路即采用“內(nèi)接”的模2和（異或門）電路與采用“外接”的模2和電路。生成多項式為g(x)=x6+x5+x4+x3+1的兩種除法電路如圖10.4.2中(a)、(b)所示，一般多采用內(nèi)接模2和的除法電路。內(nèi)接模2和除法電路的工作過程與采用手算進行長除的過程完全一致。88以上編碼方法的實現(xiàn)電路并不復雜，多項2.系統(tǒng)循環(huán)碼的譯碼(了解)892.系統(tǒng)循環(huán)碼的譯碼(了解)89TheEnd!90TheEnd!90第10章差錯控制編碼7.1概述7.2常用的幾種簡單分組碼7.3線性分組碼7.4循環(huán)碼91第10章差錯控制編碼7.1概述1

10.1概述

在數(shù)字信號傳輸中，由于信道不理想以及加性噪聲的影響，被傳輸?shù)男盘柎a元波形會變壞，造成接收端錯誤判決。為了盡量減小數(shù)字通信中信息碼元的差錯概率，應合理設計基帶信號并采用均衡技術以減小信道線性畸變引起的碼間干擾；對于由信道噪聲引起的加性干擾，應考慮采取加大發(fā)送功率、適當選擇調(diào)制解調(diào)方式等措施。但是隨著現(xiàn)代數(shù)字通信技術的不斷發(fā)展，以及傳輸速率的不斷提高，對信息碼元的差錯概率Pe的要求也在提高，例如計算機間的數(shù)據(jù)傳輸，要求Pe低于10-9，并且信道帶寬和發(fā)送功率受到限制，此時就需要采用信道編碼，又稱為差錯控制編碼。92

10.1概述2

信道編碼理論建立在香農(nóng)信息論的基礎上，其實質(zhì)是給信息碼元增加冗余度，即增加一定數(shù)量的多余碼元(稱為監(jiān)督碼元或校驗碼元)，由信息碼元和監(jiān)督碼元共同組成一個碼字，兩者間滿足一定的約束關系。如果在傳輸過程中受到干擾，某位碼元發(fā)生了變化，就破壞了它們之間的約束關系。接收端通過檢驗約束關系是否成立，完成識別錯誤或者進一步判定錯誤位置并糾正錯誤，從而提高通信的可靠性。93信道編碼理論建立在香農(nóng)信息論的基礎上

10.2差錯控制編碼的基本概念

10.2.1差錯控制方式

在差錯控制系統(tǒng)中，差錯控制方式主要有三種。

1.前向糾錯控制方式(FEC)

又稱自動糾錯，是指發(fā)送端發(fā)出的可以糾正錯誤碼元的編碼序列，接收端的譯碼器能自動糾正傳輸中的錯碼，系統(tǒng)框圖如圖10.2.1(a)所示。這種方式的優(yōu)點是不需要反饋信道，譯碼實時性好，具有恒定的信息傳輸速率。缺點是為了要獲得比較低的誤碼率，必須以最壞的信道條件來設計糾錯碼，故需要附加較多的監(jiān)督碼元，這樣既增加了譯碼算法選擇的難度，也降低了系統(tǒng)的傳輸效率，所以不適宜應用在傳輸條件惡化的信道。

94

10.2差錯控制編碼的基本概念10.

2.反饋重發(fā)糾錯方式(ARQ)

發(fā)送端發(fā)出的是能夠檢測錯誤的編碼序列，接收端譯碼器根據(jù)編碼規(guī)則進行判決，并通過反饋信道把判決結果回傳，無錯認可(ACK)，有錯時否認(NAK)。發(fā)送端根據(jù)回傳指令，將有錯的碼組重發(fā)，直到接收端認為正確接收為止，系統(tǒng)框圖如圖10.2.1(b)所示。

優(yōu)點：檢錯碼構造簡單，不需要復雜的編譯碼設備，在冗余度一定的條件下，檢錯碼的檢錯能力比糾錯碼的糾錯能力強得多，故整個系統(tǒng)的誤碼率可以保持在極低的數(shù)量級上。

缺點：需要反饋信道，并要求發(fā)送端有大容量的信源存儲器，且為保證收、發(fā)兩端互相配合，控制電路較為復雜。另外，當信道干擾很頻繁時，系統(tǒng)經(jīng)常處于重發(fā)消息的狀態(tài)，使傳送信息的實時性變差。955

3．混合糾錯方式(HEC)

該方式是上述兩種方式的結合，即在ARQ系統(tǒng)中包含一個FEC子系統(tǒng)，系統(tǒng)框圖如圖10.2.1(c)所示。發(fā)送端發(fā)出的是具有一定糾錯能力和較強檢錯能力的碼，所以經(jīng)信道編碼而附加的監(jiān)督碼元并不多。接收端檢測數(shù)據(jù)碼流，發(fā)現(xiàn)錯誤先由FEC子系統(tǒng)自動糾錯，僅當錯誤較多超出糾錯能力時，再發(fā)反饋信息要求重發(fā)，因此大大減少了重發(fā)次數(shù)。HEC在一定程度上彌補了反饋重發(fā)和前向糾錯兩種方式的缺點，充分發(fā)揮了碼的檢、糾錯能力，在較強干擾的信道中仍可獲得較低誤碼率，是實際通信中應用較多的糾錯方式。963．混合糾錯方式(HEC)6977

10.2.2差錯控制編碼的分類

用不同的方法可以對差錯控制編碼進行不同的分類。1.根據(jù)已編碼組中信息碼元與監(jiān)督碼元之間的函數(shù)關系，可分為線性碼及非線性碼。若信息碼元與監(jiān)督碼元之間的關系呈線性，即滿足一組線性方程式，則稱為線性碼。否則稱為非線性碼。

9810.2.2差錯控制編碼的分類8

2.根據(jù)信息碼元和監(jiān)督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監(jiān)督碼元僅與本碼組的信息碼元有關，卷積碼的監(jiān)督碼元不僅與本組信息碼元有關，而且與前面若干碼組的信息碼元有約束關系。

3.根據(jù)編碼后信息碼元是否保持原來的形式，可分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元保持原樣，而非系統(tǒng)碼中的信息碼元則改變了原來的信號形式。992.根據(jù)信息碼元和監(jiān)督碼元之間的約

4.根據(jù)編碼的不同功能，可分為檢錯碼、糾錯碼和糾刪碼。檢錯碼只能夠發(fā)現(xiàn)錯誤，但不能糾正錯誤；糾錯碼能夠糾正錯誤；糾刪碼即可以檢錯又可以糾錯，但糾錯能力有限，當有不能糾正的錯誤時將發(fā)出錯誤指示或刪除不可糾正的錯誤段落。

5.根據(jù)糾正、檢驗錯誤的類型不同，可分為糾正、檢驗隨機性錯誤的碼和糾正、檢驗突發(fā)性錯誤的碼。

6.根據(jù)碼元取值的不同，可分為二進制碼和多進制碼。這里只介紹二進制糾、檢錯編碼。1004.根據(jù)編碼的不同功能，可分為檢錯碼

10.2.3檢錯和糾錯的基本原理差錯控制編碼的基本思想是在被傳輸?shù)男畔⒋a元中附加一些監(jiān)督碼元，并且使它們之間確定某一種關系，根據(jù)傳輸過程中這種關系是否被破壞來發(fā)現(xiàn)或糾正錯誤?？梢娺@種差錯控制能力是用增加信息量的冗余度來換取的。

設編碼后的碼組長度、碼組中所含信息碼元個數(shù)以及監(jiān)督碼元個數(shù)分別為n、k和r，三者間滿足n=k+r，定義編碼效率為R=k/n=1-r/n?？梢姶a組長度一定時，所加入的監(jiān)督碼元個數(shù)越多，編碼效率越低。10110.2.3檢錯和糾錯的基本原理

香農(nóng)的信道編碼定理指出:對于一個給定的有擾信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進制碼元速率），則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值?？梢员硎緸槠渲蠩(R)稱為誤差指數(shù)，它與R和C的關系如圖10.2.2所示。(10.2.1)102香農(nóng)的信道編碼定理指出:(10.210313

由定理有如下結論:1.在碼長及發(fā)送信息速率一定的情況下，為減小P可以增大信道容量。由圖10.2.2可知，E(R)隨信道容量的增加而增大。由式(10.2.1)可知，錯誤概率隨E(R)的增大而指數(shù)下降。2.在信道容量及發(fā)送信息速率一定的條件下，增加碼長，可以使錯誤概率指數(shù)下降。對于實際應用來說，此時的設備復雜性和譯碼延時也隨之增加。104由定理有如下結論:14

香農(nóng)的信道編碼定理為信道編碼奠定了理論基礎，雖然定理本身并沒有給出具體的差錯控制編碼方法和糾錯碼的結構，但它從理論上為信道編碼的發(fā)展指出了努力方向。

我們用3位二進制碼組來說明檢錯糾錯的基本原理。3位二進制碼元共有8種可能的組合:000、001、010、011、100、101、110、111。如果這8種碼組都可傳遞消息，若在傳輸過程中發(fā)生一個誤碼，則一種碼組會錯誤地變成另一種碼組。由于每一種碼組都可能出現(xiàn)，沒有多余的信息量，因此接收端不可能發(fā)現(xiàn)錯誤，認為發(fā)送的就是另一種碼組。105香農(nóng)的信道編碼定理為信道編碼奠定了理

如果選其中000、011、101、110來傳送消息，這相當于只傳遞00、01、10、11四種信息，而第3位是附加的。這位附加的監(jiān)督碼元與前面兩位碼元一起，保證碼組中“1”碼的個數(shù)為偶數(shù)。這4種碼組稱為許用碼組。另外4種碼組不滿足這種校驗關系，稱為禁用碼組，它們在編碼后的發(fā)送碼元中不會出現(xiàn)。接收時一旦發(fā)現(xiàn)有禁用碼組，就表明傳輸過程中發(fā)生了錯誤。用這種簡單的校驗關系可以發(fā)現(xiàn)1個或3個錯誤，但不能糾正錯誤。因為當接收到的碼組為禁用碼組時，比如為010，無法判斷發(fā)送的是哪個碼組。雖然原發(fā)送碼組為101的可能性很小(因為3個誤碼的概率一般很小)，但不能絕對排除，即使傳輸過程中只發(fā)生一個誤碼，也有三種可能的發(fā)送碼組即000、011和110。106如果選其中000、011、101、1

假如我們進一步將許用碼組限制為二種即000和111，顯然這樣可以發(fā)現(xiàn)所有2位以下的誤碼，若用來糾錯，可以用最大似然準則糾正1位錯誤?？梢杂靡粋€三維立方體來表示上述3位二進制碼組的例子，如圖10.2.3所示。圖中立方體各頂點分別表示8位碼組，3位碼元依次表示x、y、z軸的坐標。107假如我們進一步將許用碼組限制為二種即10818

這里定義碼組中非零碼元的數(shù)目為碼組的重量，簡稱碼重。比如100碼組的碼重為1，101碼組的碼重為2。定義兩個碼組中對應碼位上具有不同二進制碼元的位數(shù)為兩碼組的距離，稱為漢明(Hamming)距，簡稱碼距。在前面3位二進制碼組的例子中，當8種碼組均為許用碼組時，兩碼組間的最小距離為1，稱這種編碼的最小碼距為1，一般記為dmin=l；當選4種碼組為許用碼組時，最小碼距dmin

=2；當用2種碼組作為許用碼組時，dmin=3。109這里定義碼組中非零碼元的數(shù)目為碼組的

從圖10.2.3所示的立方體可以看出，碼距就是從一個頂點沿立方體各邊移到另一個頂點所經(jīng)過的最少邊數(shù)。圖中粗線表示000與111之間的一條最短路徑。很容易得出前例中各種情況下的碼距。根據(jù)以上分析可知，編碼的最小碼距直接關系到這種碼的檢錯和糾錯能力，所以最小碼距是差錯控制編碼的一個重要參數(shù)。對于分組碼一般有以下結論:110從圖10.2.3所示的立方體可以看出

1.在一個碼組內(nèi)檢測e個誤碼，要求最小碼距dmin≥e+1(10.2.2)2.在一個碼組內(nèi)糾正t個誤碼，要求最小碼距dmin≥2t+1(10.2.3)3.在一個碼組內(nèi)糾正t個誤碼，同時檢測e(e≥t)個誤碼，要求最小碼距dmin≥t+e+1(10.2.4)這些結論可以用圖10.2.4所示的幾何圖形簡單的給予證明。1111.在一個碼組內(nèi)檢測e個誤碼，要求11222

可見dmin體現(xiàn)了碼組的糾、檢錯能力。碼組間最小距離越大，說明碼字間最小差別越大，抗干擾能力就越強。

由于編碼系統(tǒng)具有糾錯能力，因此在達到同樣誤碼率要求時，編碼系統(tǒng)會使所要求的輸入信噪比低于非編碼系統(tǒng)，為此引入了編碼增益的概念。其定義為，在給定誤碼率下，非編碼系統(tǒng)與編碼系統(tǒng)之間所需信噪比Eb/N0之差(用dB表示)。采用不同的編碼會得到不同的編碼增益，但編碼增益的提高要以增加系統(tǒng)帶寬或復雜度來換取。113可見dmin體現(xiàn)了碼組的糾、檢錯能

10.2.4常用的簡單檢錯碼

常用檢錯碼的結構一般都很簡單，由于這些碼組具有較強的檢錯能力，并且易于實現(xiàn)，所以在實際當中應用很廣泛。

1．奇偶校驗碼奇偶校驗碼又稱奇偶監(jiān)督碼，它只有一個監(jiān)督碼元，是一種最簡單的檢錯碼，在計算機數(shù)據(jù)傳輸中得到廣泛應用。編碼時，首先將要傳送的信息分組，按每組中“1”碼的個數(shù)計算監(jiān)督碼元的值。編碼后，整個碼組中“1”碼個數(shù)成為奇數(shù)的稱奇校驗，成為偶數(shù)的稱偶校驗。11410.2.4常用的簡單檢錯碼

設碼組長度為n，其中前n-1位(an-1,an-2

,?,a1)是信息碼元，a0是監(jiān)督碼元，二者之間的監(jiān)督關系可用公式表示。

奇校驗滿足

偶校驗滿足(10.2.6)(10.2.5)115設碼組長度為n，其中前n-1位(a

接收端用一個模2加法器就可以完成檢錯工作。當錯碼為一個或奇數(shù)個時，因打亂了“1”數(shù)目的奇偶性，故能發(fā)現(xiàn)差錯。然而，當錯誤個數(shù)為偶數(shù)時，由于未破壞“l(fā)”數(shù)目的奇偶性，所以不能發(fā)現(xiàn)偶數(shù)個錯碼。116接收端用一個模2加法器就可以完成檢錯

2．行列監(jiān)督碼

行列監(jiān)督碼也叫方陣校驗碼，編碼原理與簡單的奇偶監(jiān)督碼相似，不同之處在于每個碼元都要受到縱、橫兩個方向的監(jiān)督。以圖10.2.5為例，有28個待發(fā)送的數(shù)據(jù)碼元，將它們排成4行7列的方陣。方陣中每行是一個碼組，每行的最后加上一個監(jiān)督碼元進行行監(jiān)督，同樣在每列的最后也加上一個監(jiān)督碼元進行列監(jiān)督，然后按行(或列)發(fā)送。接收端按同樣行列排成方陣，發(fā)現(xiàn)不符合行列監(jiān)督規(guī)則的判為有錯。它除了能檢出所有行、列中的奇數(shù)個錯誤外，也能發(fā)現(xiàn)大部分偶數(shù)個錯誤。因為如果碰到差錯個數(shù)恰為4的倍數(shù)，而且差錯位置正好處于矩形四個角的情況，方陣碼無法發(fā)現(xiàn)錯誤。117

11828

行列監(jiān)督碼在某些條件下還能糾錯，觀察第3行、第4列出錯的情況，假設在傳輸過程中第3行、第4列的“1”錯成“0”，由于此錯誤同時破壞了第3行、第4列的偶監(jiān)督關系，所以接收端很容易判斷是3行4列交叉位置上的碼元出錯，從而給予糾正。

行列監(jiān)督碼也常用于檢查或糾正突發(fā)錯誤。它可以檢查出錯誤碼元長度小于和等于碼組長度的所有錯碼，并糾正某些情況下的突發(fā)差錯。

行列監(jiān)督碼實質(zhì)上是運用矩陣變換，把突發(fā)差錯變成獨立差錯加以處理。因為這種方法比較簡單，所以被認為是克制突發(fā)差錯很有效的手段。119行列監(jiān)督碼在某些條件下還能糾錯，觀

3.恒比碼

恒比碼又稱等比碼或等重碼。恒比碼的每個碼組中，“1”和“0”的個數(shù)比是恒定的。我國電傳通信中采用的五單位數(shù)字保護電碼是一種3∶2等比碼，也叫五中取三的恒比碼，即在5單位電傳碼的碼組中(25=32)，取其“1”的數(shù)目恒為3的碼組(C53=10)，代表10個字符(0～9)，如表10.2.1所示。因為每個漢字是以四位十進制數(shù)表示的，所以提高十進制數(shù)字傳輸?shù)目煽啃?，相當于提高了漢字傳輸?shù)目煽啃浴?203.恒比碼30

國際電傳電報上通用的ARQ通信系統(tǒng)中，選用三個“1”、四個“0”的3:4碼，即七中取三碼。它有C73=35個碼組，分別表示26個字母及其他符號。

在檢測恒比碼時，通過計算接收碼組中“1”的數(shù)目，判定傳輸有無錯誤。除了“1”錯成“0”和“0”錯成“1”成對出現(xiàn)的錯誤以外，這種碼能發(fā)現(xiàn)其他所有形式的錯誤，因此檢錯能力很強。實踐證明，應用這種碼，國際電報通信的誤碼率保持在10-6以下。12131

4.ISBN國際統(tǒng)一圖書編號

國際統(tǒng)一圖書編號是一種檢錯碼，以防止書號在通信過程中發(fā)生誤傳。這里以編號ISBN0-1315-2447-X為例，其中第一位數(shù)字“0”表示該書是美國及其它英語國家的出版物(中國的代號是數(shù)字“7”)，“1315”代表出版公司，“2447”代表書名編號，最后一位數(shù)字“X”是校驗位(這是10的羅馬字表示)。這里采用的校驗方法如圖10.2.6所示。1224.ISBN國際統(tǒng)一圖書編號3212333

圖中第1行為ISBN編號。第2行第1個數(shù)字與第1行第1個數(shù)字相同；第2行第2個數(shù)字則為第1行第2個數(shù)字與第2行第1個數(shù)字之和，即1+0=1；第2行第3個數(shù)字為第1行第3個數(shù)字與第2行第2個數(shù)字之和，即3+1=4；依次類推，第2行最后所得的累計和為37。用同樣方法得到第3行的最后累計和為132。然后用模11對132進行校驗，132(mod11)≡0。

顯然，若通信過程中統(tǒng)一書號發(fā)生了錯誤，則上累計和就不能被11所整除，從而可校驗出來。124圖中第1行為ISBN編號。第2行第10.3線性分組碼

10.3.1基本概念

一個長為n的分組碼，碼字由兩部分構成，即信息碼元(k位)+監(jiān)督碼元(r位)。監(jiān)督碼元是根據(jù)一定規(guī)則由信息碼元變換得到的，變換規(guī)則不同就構成不同的分組碼。如果監(jiān)督位為信息位的線性組合，就稱其為線性分組碼。

要從k個信息碼元中求出r個監(jiān)督碼元，必須有r個獨立的線性方程。根據(jù)不同的線性方程，可得到不同的(n,k)線性分組碼。12510.3線性分組碼10.3.1基本概念35

例如，已知一個(7，4)線性分組碼，4個信息碼元a6、a5、a4、a3和3個監(jiān)督碼元a2、a1、a0之間符合以下規(guī)則

計算上式得到此(7