第十二章電子講義：差錯控制編碼

1、第十二章 差錯控制編碼知識結構- 差錯控制的主要方式- 檢、糾錯編碼的基本概念和基本原理- 常用的簡單的檢、糾錯編碼- 線性分組碼- 卷積碼教學目的- 了解糾錯編碼的基本原理- 了解幾種常用編碼：奇偶校驗碼、正反碼等，線性分組碼、循環(huán)碼、卷積碼的編解碼原理教學重點- 重點掌握線性分組碼、循環(huán)碼、卷積碼的編解碼原理。教學難點- 生成矩陣和生成多項式教學方法及課時- 多媒體授課（8學時）（分4個單元）備注 單元二十八（2學時）§12.1 引言（差錯控制的作用和方式的分類）知識要點：信源編碼與信道編碼的基本概念、相互關系及區(qū)別 差錯控制的主要3種方式§12.1.1 信源編碼與信道

2、編碼的基本概念設計通信系統(tǒng)的目的就是把信源產(chǎn)生的信息有效可靠地傳送到目的地。在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。信源編碼信源可以有各種不同的形式，例如在無線廣播中，信源一般是一個語音源（話音或音樂）；在電視廣播中，信源主要是活動圖像的視頻信號源。這些信源的輸出都是模擬信號，所以稱之為模擬源。而數(shù)字通信系統(tǒng)是設計來傳送數(shù)字形式的信息，所以，這些模擬源如果想利用數(shù)字通信系統(tǒng)進行傳輸，就需要將模擬信息源的輸出轉化為數(shù)字信號，而這個轉化構成就稱為信源編碼。對于信源編碼的研究，在通信領域受到了人們的廣泛關注。特別在移動

3、通信系統(tǒng)中，信源編碼（語音編碼）決定了接收到的語音的質(zhì)量和系統(tǒng)容量。因為在移動通信系統(tǒng)中，帶寬是很珍貴的，所以，如何在有限的可分配的帶寬內(nèi)容納更多的用戶，已經(jīng)成為經(jīng)營者最為關心的問題。而低比特率語音編碼提供了解決該問題的一種方法。在編碼器能夠傳送高質(zhì)量語音的前提下，如果比特率越低，就可以在一定的帶寬內(nèi)能容納更多的語音通道。因此，生產(chǎn)商和服務提供商不斷地尋求新的編碼方法，以便在低比特率條件下提供高質(zhì)量的語音。語音編碼的目的就是在保持一定算法復雜程度和通信時延的前提下，運用盡可能少的信道容量，傳送盡可能高的語音質(zhì)量。目前較為常用的語音編碼形式有：脈沖編碼調(diào)制（PCM）、差分脈沖編碼調(diào)制（DPCM）

4、、自適應差分脈沖編碼調(diào)制（ADPCM）、增量調(diào)制（DM）、連續(xù)可變斜率增量調(diào)制（CVSDM）、自適應預測編碼（APC）、自帶編碼（SBC）、碼激勵線性預測編碼等等。信道編碼（差錯控制編碼）在實際信道傳輸數(shù)字信號的過程中，引起傳輸差錯的根本原因在于信道內(nèi)存在的噪聲以及信道傳輸特性不理想所造成的碼間串擾。為了提高數(shù)字傳輸系統(tǒng)的可靠性，降低信息傳輸?shù)牟铄e率，可以利用均衡技術消除碼間串擾，利用增大發(fā)射功率、降低接收設備本身的噪聲、選擇好的調(diào)制制度和解調(diào)方法、加強天線的方向性等措施，提高數(shù)字傳輸系統(tǒng)的抗噪性能，但上述措施也只能將傳輸差錯減小到一定程度。要進一步提高數(shù)字傳輸系統(tǒng)的可靠性，就需要采用差錯控制

5、編碼，對可能或已經(jīng)出現(xiàn)的差錯進行控制。差錯控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號；差錯控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，或進而糾正錯誤。原始數(shù)字信號是分組傳輸?shù)模缑縦個二進制碼元為一組（稱為信息組），經(jīng)信道編碼后轉換為每n個碼元一組的碼字（碼組），這里nk，分組碼通常表示為（n，k）。可見，信道編碼是用增加數(shù)碼，利用“冗余”來提高抗干擾能力的，也就是以降低信息傳輸速率為代價來減少錯誤的，或者說是用削弱有效性來增強可靠性的。本章首先給出了差錯控制編碼的基本概念，介紹了幾種常用簡單分組碼，在此

6、基礎上，對分組碼、循環(huán)碼和卷積碼基本原理和性能進行了研究分析。§12.1.2 糾錯編碼的分類在差錯控制系統(tǒng)中，信道編碼存在著多種實現(xiàn)方式，同時信道編碼也有多種分類方法。（）按照信道編碼的不同功能，可以將它分為檢錯碼和糾錯碼。檢錯碼僅能檢測誤碼，例如，在計算機串口通信中常用到的奇偶校驗碼等；糾錯碼可以糾正誤碼，當然同時具有檢錯的能力，當發(fā)現(xiàn)不可糾正的錯誤時可以發(fā)出出錯指示。（）按照信息碼元和監(jiān)督碼元之間的檢驗關系，可以將它分為線性和非線性碼。若信息碼元與監(jiān)督碼元之間的關系為線性關系，即滿足一組線性方程式，稱為線性碼；否則，稱為非線性碼。（）按照信息碼元和監(jiān)督碼元之間的約束方式不同，可以

7、將它分為分組碼和卷積碼。在分組碼中，編碼后的碼元序列每n位分為一組，其中k位信息碼元，r個監(jiān)督位，r = n-k。監(jiān)督碼元僅與本碼字的信息碼元有關。卷積碼則不同，監(jiān)督碼元不但與本信息碼元有關，而且與前面碼字的信息碼元也有約束關系。（）按照信息碼元在編碼后是否保持原來的形式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元保持原樣不變，而非系統(tǒng)碼中的信息碼元則發(fā)生了變化。除了個別情況，系統(tǒng)碼的性能大體上與非系統(tǒng)碼相同，但是非系統(tǒng)碼的譯碼較為復雜，因此，系統(tǒng)碼得到了廣泛的應用。（）按照糾正錯誤的類型不同，可以將它分為糾正隨機錯誤碼和糾正突發(fā)錯誤碼兩種。前者主要用于發(fā)生零星獨立錯誤的信道，

8、而后者用于對付以突發(fā)錯誤為主的信道。（）按照信道編碼所采用的數(shù)學方法不同，可以將它分為代數(shù)碼、幾何碼和算術碼。其中代數(shù)碼是目前發(fā)展最為完善的編碼，線性碼就是代數(shù)碼的一個重要的分支。除上述信道編碼的分類方法以外，還可以將它分為二進制信道編碼和多進制信道編碼等等。同時，隨著數(shù)字通信系統(tǒng)的發(fā)展，可以將信道編碼器和調(diào)制器統(tǒng)一起來綜合設計，這就是所謂的網(wǎng)格編碼調(diào)制（TCM Trellis Coded Modulation）。§12.1.3 差錯控制方式常用的差錯控制方式主要有三種：前向糾錯（簡稱FEC）、檢錯重發(fā)（簡稱ARQ）和混合糾錯（簡稱HEC），它們的結構如圖12-1所示。圖中有斜線的方

9、框圖表示在該端進行錯誤的檢測。前向糾錯系統(tǒng)中，發(fā)送端經(jīng)信道編碼后可以發(fā)出具有糾錯能力的碼字；接收端譯碼后不僅可以發(fā)現(xiàn)錯誤碼，而且可以判斷錯誤碼的位置并予以自動糾正。然而，前向糾錯編碼需要附加較多的冗余碼元，影響數(shù)據(jù)傳輸效率，同時其編譯碼設備比較復雜。但是由于不需要反饋信道，實時性較好，因此，這種技術在單工信道中普遍采用，例如無線電尋呼系統(tǒng)中采用的POGSAG編碼等。圖12-1  差錯控制方式檢錯重發(fā)方式中，發(fā)送端經(jīng)信道編碼后可以發(fā)出能夠檢測出錯誤能力的碼字；接收端收到后經(jīng)檢測如果發(fā)現(xiàn)傳輸中有錯誤，則通過反饋信道把這一判斷結果反饋給發(fā)送端。然后，發(fā)送端把前面發(fā)出的信息重新傳送

10、一次，直到接收端認為已經(jīng)正確后為止。典型系統(tǒng)檢錯重發(fā)方式的原理方框圖如圖12-2所示：常用的檢錯重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)。圖12-2  ARQ系統(tǒng)組成方框圖在返回重發(fā)系統(tǒng)中，發(fā)送端無停頓的送出一個又一個碼字，不再等待ACK信號，一旦接收端發(fā)現(xiàn)錯誤并發(fā)回NAK信號，則發(fā)送端從下一個碼字開始重發(fā)前一段N組信號，N的大小取決于信號傳遞及處理所帶來的延遲，這種系統(tǒng)比停發(fā)等候重發(fā)系統(tǒng)有很大的改進，在許多數(shù)據(jù)傳輸系統(tǒng)中得到應用。在選擇重發(fā)系統(tǒng)中，發(fā)送端也是連續(xù)不斷地發(fā)送碼字，接收端發(fā)現(xiàn)錯誤發(fā)回NAK信號。與返回重發(fā)系統(tǒng)不同的是，發(fā)送端不是重發(fā)前面的所有碼字，而

11、是只重發(fā)有錯誤的那一組。顯然，這種選擇重發(fā)系統(tǒng)傳輸效率最高，但控制最為復雜。此外，返回重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)都需要全雙工的鏈路，而停發(fā)等候重發(fā)系統(tǒng)只需要半雙工的鏈路?；谏鲜龇治?，檢錯重發(fā)（ARQ）的優(yōu)點主要表現(xiàn)在：（1）只需要少量的冗余碼，就可以得到極低的輸出誤碼率；（2）使用的檢錯碼基本上與信道的統(tǒng)計特性無關，有一定的自適應能力；（3）與FEC相比，信道編譯碼器的復雜性要低得多。同時它也存在某些不足，主要表現(xiàn)在：（1）需要反向信道，故不能用于單向傳輸系統(tǒng)，并且實現(xiàn)重發(fā)控制比較復雜；（2）當信道干擾增大時，整個系統(tǒng)有可能處在重發(fā)循環(huán)當中，因而通信效率低，不大適合于嚴格實時傳輸系統(tǒng)?；旌霞m錯方

12、式是前向糾錯方式和檢錯重發(fā)方式的結合。在這種系統(tǒng)中發(fā)送端不但具有糾正錯誤的能力，而且對超出糾錯能力的錯誤有檢測能力。遇到后一種情況時，系統(tǒng)可以通過反饋信道要求發(fā)送端重發(fā)一遍?；旌图m錯方式在實時性和譯碼復雜性方面是前向糾錯和檢錯重發(fā)方式的折衷。在實際應用中，上述幾種差錯控制方式應根據(jù)具體情況合理選用。§12.1.4 糾錯編碼的基本原理信道編碼的基本思想就是在被傳送的信息中附加一些監(jiān)督碼元，在收和發(fā)之間建立某種校驗關系，當這種校驗關系因傳輸錯誤而受到破壞時，可以被發(fā)現(xiàn)甚至糾正錯誤，這種檢錯與糾錯能力是用信息量的冗余度來換取的。下面將介紹幾個與信道編碼有關的基本概念：碼長：碼字中碼元的數(shù)目

13、；碼重：碼字中非0數(shù)字的數(shù)目；對于二進制碼來講，碼重W就是碼元中1的數(shù)目，例如碼字10100，碼長n = 5，碼重W = 2。碼距：兩個等長碼字之間對應位不同的數(shù)目，有時也稱作這兩個碼字的漢明距離，例如碼字10100與11000之間的碼距d = 2。最小碼距：在碼字集合中全體碼字之間距離的最小數(shù)值。對于二進制碼字而言，兩個碼字之間的模二相加，其不同的對應位必為1，相同的對應位必為0。因此，兩個碼字之間模二相加得到的碼重就是這兩個碼字之間的距離。以二進制分組碼的糾錯過程為例，可以較為詳細地說明糾錯碼檢錯和糾錯的基本原理。分組碼對于數(shù)字序列是分段進行處理的，設每一段有k個碼元組成（稱作長度為k的信

14、息組），由于每個碼元有0或1兩種值，故共有個不同的狀態(tài)。每段長為k的信息組，以一定的規(guī)則增加r個多余度碼元（稱為監(jiān)督元），監(jiān)督這k個信息元，這樣就組成長度為n k+r的碼字（又稱n重）。共可以得到個長度為n碼字，它們通常被稱為許用碼字。而長度為n的數(shù)字序列共有2n種可能的組合，其中 -個長度為n碼字未被選用，故稱它們?yōu)榻么a字。上述個長度為n的許用碼字的集合稱為分組碼。分組碼能夠檢錯或糾錯的原因是存在 -多余度碼字，或者說在 碼字中有禁用碼字存在。下面就舉一個具體的例子：設發(fā)送端發(fā)送A和B兩個消息，分別用一位碼元來表示，1代表A，0代表B。如果這兩個信息組在傳輸中產(chǎn)生了錯誤，那么就會使0錯成了

15、1或1錯成了0，而接收端不能發(fā)現(xiàn)這種錯誤，更談不上糾正錯誤了。若在每個一位長的信息組中加上一個監(jiān)督元（r1），其規(guī)則是與信息元重復，這樣編出的兩個長度為n2的碼字，它們分別為11（代表A）和00（代表B）。這時11、00就是許用碼字，這兩個碼字組成一個（2，1）分組碼，其特點是各碼字的碼元是重復的，故又稱為重復碼。而01、10就是禁用碼字。設發(fā)送11經(jīng)信道傳輸錯了一位，變成01或10，收端譯碼器根據(jù)重復碼的規(guī)則，能發(fā)現(xiàn)有一位錯誤，但不能指明錯在哪一位，也就是不能作出發(fā)送的消息是A（11）還是B（00）的判決。若信道干擾嚴重，使發(fā)送碼字的兩位都產(chǎn)生錯誤，從而使11錯成了00，收端譯碼器根據(jù)重復碼

16、的規(guī)則檢驗，不認為有錯，并且判決為消息B，造成了錯判。這時可以發(fā)現(xiàn)：這種碼距為2的（2，1）重復碼能確定一個碼元的錯誤，不能確定二個碼元的錯誤，也不能糾正錯誤。若仍按重復碼的規(guī)則，再加一個監(jiān)督碼元，得到（3，1）重復碼，它的兩個碼字分別為111和000，其碼距為3。這樣其余六個碼字（001、010、100、110、101、011）為禁用碼字。設發(fā)送111（代表消息A），如果譯碼器收到的3重為110，根據(jù)重復碼的規(guī)則，發(fā)現(xiàn)有錯，并且當采用最大似然法譯碼時，把與發(fā)送碼字最相似的碼字認為就是發(fā)送碼字。而110與111只有一位不同，與000有兩位不同，故判決為111。事實上，在一般情況下，錯一位的可能

17、性比錯二位的可能性要大得多，從統(tǒng)計的觀點看，這樣判決是正確的。因此，這種（3，1）碼能夠糾正一個錯誤，但不能糾正兩個錯誤，因為若發(fā)送111，收到100時，根據(jù)譯碼規(guī)則將譯為000，這就判錯了。類似于前面的分析，這種碼若用來檢錯，它可以發(fā)現(xiàn)兩個錯誤，但不能發(fā)現(xiàn)三個錯誤。當然，還可以選用碼字更長的重復碼進行信道編碼，隨著碼字的增長，重復碼的檢錯和糾錯能力會變得更強。上述例子表明：糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。因此，碼字之間的最小距離是衡量該碼字檢錯和糾錯能力的重要依據(jù)，最小碼距是信道編碼的一個重要的參數(shù)。在一般情況下，

18、分組碼的最小漢明距離與檢錯和糾錯能力之間滿足下列關系：（1）當碼字用于檢測錯誤時，如果要檢測e個錯誤，則                                      （12-1）圖12-3 

19、60;糾（檢）錯能力的幾何解釋這個關系可以利用圖12-3（a）予以說明。在圖中用A和B分別表示兩個碼距為d0的碼字，若A發(fā)生e個錯誤，則A就變成以A為球心，e為半徑的球面上的碼字，為了能將這些碼字分辯出來，它們必須距離其最近的碼字B有一位的差別，即A和B之間最小距離為。（2）當碼字用于糾正錯誤時，如果要糾正t個錯誤，則                       &#

20、160;              （12-2）這個關系可以利用圖12-3（b）予以說明。在圖中用A和B分別表示兩個碼距為的碼字，若A發(fā)生t個錯誤，則A就變成以A為球心，t為半徑的球面上的碼字；B發(fā)生t個錯誤，則B就變成以B為球心，t為半徑的球面上的碼字。為了在出現(xiàn)t個錯誤之后，仍能夠分辯出A和B來，那么，A和B之間距離應大于2t，最小距離也應當使兩球體表面相距為1，即滿足不等式（12-2）。（3）若碼字用于糾t個錯誤，同時檢e個錯誤時（e>t），則

21、                                    （12-3）這個關系可以利用圖12-3(c)予以說明。在圖中用A和B分別表示兩個碼距為的碼字，當碼字出現(xiàn)t個或小于t個錯誤時，系統(tǒng)按照糾錯方式工作；當碼字出現(xiàn)大于t個而

22、小于e個錯誤時，系統(tǒng)按照檢錯方式工作；若A發(fā)生t個錯誤，B發(fā)生e個錯誤時，既要糾A的錯，又要檢B的錯，則A和B之間距離應大于t+e，也就是滿足式（12-3）。通常，在信道編碼過程中，監(jiān)督位越多糾錯能力就越強，但編碼效率就越低。若碼字中信息位數(shù)為k，監(jiān)督位數(shù)為r，碼長n = k+r。則編碼效率Rc可以用下式表示：                         

23、;     （12-4）信道編碼的任務就是要根據(jù)不同的干擾特性，設計出編碼效率高、糾錯能力強的編碼。在實際設計過程中，需要根據(jù)具體指標要求，盡量簡化編碼實現(xiàn)的復雜度，節(jié)省設計費用。§12.2 常用的簡單的檢、糾錯編碼知識要點：奇偶監(jiān)督 恒比碼 正反碼本節(jié)介紹幾種簡單的檢錯碼，這些信道編碼很簡單，但有一定的檢錯能力，且易于實現(xiàn)，因此得到廣泛應用。§12.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼是奇監(jiān)督碼和偶監(jiān)督碼的統(tǒng)稱，是一種最基本的檢錯碼。它是由n-1位信息元和1位監(jiān)督元組成，可以表示成為（n，n-1）。如果是奇監(jiān)督碼，在附加上一個監(jiān)督

24、元以后，碼長為n的碼字中“1”的個數(shù)為奇數(shù)個；如果是偶監(jiān)督碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為偶數(shù)個。設：如果一個偶監(jiān)督碼的碼字用A=表示，則：=0                           （12-5）式中為監(jiān)督元，“+”為模二和（以后也這樣表示，請注意）。式（12-5）通常被稱為監(jiān)督方程。利用

25、式（12-5），由信息元即可求出監(jiān)督元。另外，如果發(fā)生單個（或奇數(shù)個）錯誤，就會破壞這個關系式，因此通過該式能檢測碼字中是否發(fā)生了單個或奇數(shù)個錯誤。奇偶監(jiān)督碼是一種有效地檢測單個錯誤的方法，之所以將注意力集中在檢（或糾）單個錯，這主要是因為碼字中發(fā)生單個錯誤的概率要比發(fā)生2個或多個錯誤的概率大得多。例如，n = 5的碼字，如果碼字中各碼元的錯誤是互相獨立，誤碼率為10-4，則錯1、2、3、4和5位的概率分別為：5×、和。由此可見，要檢（或糾）錯誤，首先要解決單個錯誤，這樣才抓住了主要矛盾。一般情況下用上述偶監(jiān)督碼來檢出單個錯誤，檢錯效果是令人滿意的，不僅如此，奇偶監(jiān)督碼的編碼效率很高

26、，隨n增大而趨近于l。下面就給出以碼長n5為例，利用表12-1列出全部偶監(jiān)督碼字：表12-1碼長5的偶監(jiān)督碼字序號碼字序號碼字信息碼元a4a3a2a1監(jiān)督字a0信息碼元a4a3a2a1監(jiān)督字a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110在數(shù)字信息傳輸中，奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬件電路實現(xiàn)。圖12-4(a)就是碼長為5的偶監(jiān)督碼編碼器。從圖中可以看到，4位碼元長的信息組，串行送入四級移位寄存器（輸入定時緩沖器），同時經(jīng)模

27、二運算得到監(jiān)督元，存入輸出緩沖器末級，編碼完成即可輸出碼字。圖12-4 奇偶監(jiān)督碼的硬件實現(xiàn)§12.2.2 行列監(jiān)督碼行列監(jiān)督碼又稱水平垂直一致監(jiān)督碼或二維奇偶監(jiān)督碼，有時還被稱為矩陣碼。它不僅對水平（行）方向的碼元，而且還對垂直（列）方向的碼元實施奇偶監(jiān)督。一般L×m個信息元，附加L+m+1個監(jiān)督元，由L+1行，m+1列組成一個（Lm+L+m+1，Lm）行列監(jiān)督碼的碼字。表12-2就是（66，50）行列監(jiān)督碼的一個碼字（L5，M10），它的各行和各列對l的數(shù)目都實行偶數(shù)監(jiān)督?？梢灾鹦袀鬏敚部梢灾鹆袀鬏?。譯碼時分別檢查各行、各列的監(jiān)督關系，判斷是否有錯。表12-

28、2（66，50）行列監(jiān)督碼的一個碼字1  1  0  0  1  0  1  0  0  00  1  0  0  0  0  1  1  0  10   1   1   1   1   0  0  0  0  11  

29、 0   0   1   1   1  0  0  0  01   0   1   0   1   0  1  0  1  0001011   1   0   0   0 

30、;  1  1  1  1  00這種碼有可能檢測偶數(shù)個錯誤。因為每行的監(jiān)督位雖然不能用于檢測本行中的偶數(shù)個錯碼，但按列的方向就有可能檢測出來。可是也有一些偶數(shù)錯碼不可能檢測出，例如，構成矩形的四個錯碼就檢測不出來。這種二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。因為這種突發(fā)錯碼常常成串出現(xiàn)，隨后有較長一段無錯區(qū)間，所以在某一行中出現(xiàn)多個奇數(shù)或偶數(shù)錯碼的機會較多，這種方陣碼適于檢測這類錯碼。前述的一維奇偶監(jiān)督碼一般只適于檢測隨機錯誤。由于方陣碼只對構成矩形四角的錯碼無法檢測，故其檢錯能力較強。一些試驗測量表明，這種碼

31、可使誤碼率降至原誤碼率的百分之一到萬分之一。二維奇偶監(jiān)督碼不僅可用來檢錯，還可用來糾正一些錯碼。例如，當碼組中僅在一行中有奇數(shù)個錯誤時，則能夠確定錯碼位置，從而糾正它。§12.2.3 恒比碼恒比碼又稱等重碼,這種碼的碼子中1和0的位數(shù)保持恒定比例。由于每個碼字的長度是相同的，若1、0恒比，則碼字必等重。若碼長為n，碼重為w，則此碼的碼字個數(shù)為，禁用碼字數(shù)為。該碼的檢錯能力較強，除對換差錯（1和0成對的產(chǎn)生錯誤）不能發(fā)現(xiàn)外，其它各種錯誤均能發(fā)現(xiàn)。目前我國電傳通信中普遍采用3：2碼，該碼共有個許用碼字，用來傳送10個阿拉伯數(shù)字，如表12-3所示。這種碼又稱為5中取3數(shù)字保護碼。因為每個漢

32、字是以四位十進制數(shù)來代表的，所以提高十進制數(shù)字傳輸?shù)目煽啃?，就等于提高漢字傳輸?shù)目煽啃?。實踐證明，采用這種碼后，我國漢字電報的差錯串大為降低。表12-3 3:2數(shù)字保護碼數(shù)字碼字01234567890  1  1  0  10  1  0  1  11  1  0  0  11  0  1  1&#

33、160; 01  1  0  1  00  0  1  1  11  0  1  0  11  1  1  0  00  1  1  1  01  0 

34、0;0  1  1目前國際上通用的ARQ電報通信系統(tǒng)中，采用3：4碼即7中取3碼，這種碼共有個許用碼字，93個禁用碼字。35個許用碼字用來代表不同的字母和符號。實踐證明，應用這種碼，使國際電報通信的誤碼率保持在以下。 單元二十九（2學時）§12.3 線性分組碼知識要點：分組碼 線性分組碼 線性分組碼的性質(zhì) 線性分組碼的構造 監(jiān)督矩陣H 生成矩陣G 校驗子 漢明碼§12.3.1 分組碼的基本概念分組碼是一組固定長度的碼組，可表示為（n , k），通常它用于前向糾錯。在分組碼中，監(jiān)督位被加到信息位之后，形成新的碼。在編碼時，k個信息位被編

35、為n位碼組長度，而n-k個監(jiān)督位的作用就是實現(xiàn)檢錯與糾錯。當分組碼的信息碼元與監(jiān)督碼元之間的關系為線性關系時，這種分組碼就稱為線性分組碼。對于長度為n的二進制線性分組碼，它有種可能的碼組，從種碼組中，可以選擇M=個碼組（k<n）組成一種碼。這樣，一個k比特信息的線性分組碼可以映射到一個長度為n碼組上，該碼組是從M=個碼組構成的碼集中選出來的，這樣剩下的碼組就可以對這個分組碼進行檢錯或糾錯。線性分組碼是建立在代數(shù)群論基礎之上的，各許用碼的集合構成了代數(shù)學中的群，它們的主要性質(zhì)如下：（1）任意兩許用碼之和（對于二進制碼這個和的含義是模二和）仍為一許用碼，也就是說，線性分組碼具有封閉性；（2）

36、碼組間的最小碼距等于非零碼的最小碼重。在12.2.1節(jié)中介紹的奇偶監(jiān)督碼，就是一種最簡單的線性分組碼，由于只有一位監(jiān)督位通?？梢员硎緸椋╪,n-1），式（12-5）表示采用偶校驗時的監(jiān)督關系。在接收端解碼時，實際上就是在計算：                              （12-6）其

37、中，   表示接收到的信息位，表示接收到的監(jiān)督位，若S0，就認為無錯；若S1就認為有錯。式（12-6）被稱為監(jiān)督關系式，S是校正子。由于校正子S的取值只有“0”和“1”兩種狀態(tài)，因此，它只能表示有錯和無錯這兩種信息，而不能指出錯碼的位置。設想如果監(jiān)督位增加一位，即變成兩位，則能增加一個類似于式（12-6）的監(jiān)督關系式，計算出兩個校正子和， 而共有4種組合：00，01，10，11，可以表示4種不同的信息。除了用00表示無錯以外，其余3種狀態(tài)就可用于指示3種不同的誤碼圖樣。同理，由r個監(jiān)督方程式計算得到的校正子有r位，可以用來指示-1種誤碼圖樣。對于一位誤碼來說，就可以指示-1

38、個誤碼位置。對于碼組長度為n、信息碼元為k位、監(jiān)督碼元為rn - k位的分組碼（常記作（n，k）碼），如果希望用r個監(jiān)督位構造出r個監(jiān)督關系式來指示一位錯碼的n種可能，則要求：                               （12-7)下面通過一個例子來說明線性分組碼是如何構

39、造的。設分組碼（n , k）中k = 4，為了能夠糾正一位錯誤，由式（12-7）可以看到，要求r 3，若取r = 3，則n = k+r = 7。因此，可以用表示這7個碼元，用、表示利用三個監(jiān)督方程，通過計算得到的校正子，并且假設、三位校正字碼組與誤碼位置的關系如表12-4（當然，也可以規(guī)定成另一種對應關系，這并不影響討論的一般性）：表12-4校正字與誤碼位置S1S2S3誤碼位置S1S2S3誤碼位置001010100011a0a1a2a3101110111000a4a5a6無錯由表中規(guī)定可已看到，僅當一錯碼位置在時，校正子為1；否則為0。這就意味著四個碼元構成偶數(shù)監(jiān)督關系：  

40、;       (12-8a）同理，構成偶數(shù)監(jiān)督關系：        （12-8b）以及構成有數(shù)監(jiān)督關系： （12-8c）在發(fā)送端編碼時是信息碼元，它們的值取決于輸入信號，因此是隨機的。是監(jiān)督碼元，它們的取值由監(jiān)督關系來確定，即監(jiān)督位應使式（12-8）的三個表達式中的、和的值為零（表示編成的碼組中應無錯碼），這樣式（8-8）的三個表達式可以表示成下面的方程組形式：       

41、                           （12-9）由上式經(jīng)移項運算，接出監(jiān)督位                   

42、0;                （12-10）根據(jù)上面兩個線性關系，可以得到16個許用碼組如表12-5所示：表12-5 （7,4）分組碼的所有許用碼組信息位監(jiān)督位信息位監(jiān)督位信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a0000000010010001100001110111001000101010001111101010110001000100

43、1101010111111000100011100110111001111001010100111接收端收到每個碼組后，計算出、和，如不全為0，則可按表12-4確定誤碼的位置，然后予以糾正。例如，接收碼組為0000011，可算出011，由表12-4可知在位置上有一誤碼。不難看出，上述（7，4）碼的最小碼距，因此，它能糾正一個誤碼或檢測兩個誤碼。如超出糾錯能力，則反而會因“亂糾”而增加新的誤碼。（說明此類碼不適合誤碼較大的信道！）§12.3.2 監(jiān)督矩陣H和生成矩陣G式（12-9）所述（7，4）碼的三個監(jiān)督方程式可以重新改寫為如下形式：    &

44、#160;              （12-11）對于式（12-11）可以用矩陣形式來表示：            （12-12）上式可以記作：或，其中               

45、60;    （12-13a）                        （12-13b）                   

46、;       （12-13c）通常H稱為監(jiān)督矩陣，A稱為信道編碼得到的碼字。在這個例子中H為r×n階矩陣，P為r×k階矩陣，Ir為r×r階單位矩陣，具有這種特性的H矩陣稱為典型監(jiān)督矩陣，這是一種較為簡單的信道編譯碼方式。典型形式的監(jiān)督矩陣各行是線性無關的，非典型形式的監(jiān)督矩陣可以經(jīng)過行或列的運算化為典型形式。對于式（12-10）也可以用矩陣形式來表示：或者           

47、0; （12-14）比較式（12-13a）和式（12-14）可以看到，如果在Q矩陣的左邊在加上一個k×k的單位矩陣，就形成了一個新矩陣G：                      （12-15）這里G稱為生成矩陣，利用它可以產(chǎn)生整個碼組          &

48、#160;             （12-16）由式（12-15）表示的生成矩陣形式稱為典型生成矩陣，利用式（8-16）產(chǎn)生的分組碼必為系統(tǒng)碼，也就是信息碼元保持不變，監(jiān)督碼元附加在其后。§12.3.3 校驗子S在發(fā)送端信息碼元M利用式（12-16），實現(xiàn)信道編碼，產(chǎn)生線性分組碼A；在傳輸過程中有可能出現(xiàn)誤碼，設接收到的碼組為B。則收發(fā)碼組之差為：         

49、    （12-17）這里，表示i位有錯，表示i位無錯?；谶@樣的原則接收端利用接收到的碼組B計算校正子：                  （12-18）因此，校正子僅與E有關，即錯誤圖樣與校正子之間有確定的關系。對于上述（7，4）碼，校正子S與錯誤圖樣的對應關系可由式（12-18）求得，其計算結果見表12-6所示。在接收端的譯碼器中有專門的校正子計算電路，從而實現(xiàn)檢錯和糾錯

50、。表12-6（7，4）碼校正子與錯誤圖樣的對應關系序號錯誤碼位ESe6 e5 e4 e3 e2 e1 e0S3 S2 S101234567/b0b1b2b3b4b5b60  0  0  0  0  0  00  0  0  0  0  0  10  0  0  0 &#

51、160;0  1  00  0  0  0  1  0  00  0  0  1  0  0  00  0  1  0  0  0  00  1  0 

52、; 0  0  0  01  0  0  0  0  0  00  0  00  0  10  1  01  0  00  1  11  0  11  

53、;1  01  1  1§12.3.4 漢明碼漢明碼是一種能夠糾正單個錯誤的線性分組碼。它有以下特點：（1）最小碼距，可以糾正一位錯誤；（2）碼長n與監(jiān)督元個數(shù)r之間滿足關系式：。如果要產(chǎn)生一個系統(tǒng)漢明碼，可以將矩陣H轉換成典型形式的監(jiān)督矩陣，進一步利用Q = PT的關系，得到相應的生成矩陣G。通常二進制漢明碼可以表示為：                 &

54、#160;   （12-19）根據(jù)上述漢明碼定義可以看到，12.3.1構造的（7，4）線性分組碼實際上就是一個漢明碼，它滿足漢明碼的兩個特點。圖12-5中給出（7，4）系統(tǒng)漢明碼的編碼器和譯碼器電路。（a）發(fā)端編碼器（b）收端譯編碼器圖12-5 （7，4）漢明碼的編譯碼器 單元三十（2學時）§12.4 循環(huán)碼知識要點：碼多項式 循環(huán)碼的生成多項式及其特征循環(huán)碼是線性分組碼的一個重要子集，是目前研究得最成熟的一類碼。它有許多特殊的代數(shù)性質(zhì)，這些性質(zhì)有助于按所要求的糾錯能力系統(tǒng)地構造這類碼，且易于實現(xiàn)；同時循環(huán)碼的性能也較好，具有較強的檢錯和糾錯能

55、力。§12.4.1 循環(huán)碼的特點循環(huán)碼最大的特點就是碼字的循環(huán)特性，所謂循環(huán)特性是指：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。若（   ）為一循環(huán)碼組，則（  ）、（ ）、還是許用碼組。也就是說，不論是左移還是右移，也不論移多少位，仍然是許用的循環(huán)碼組。表12-7給出了一種（7，3）循環(huán)碼的全部碼字。由此表可以直觀地看出這種碼的循環(huán)特性。例如，表中的第2碼字向右移一位，即得到第5碼字；第6碼字組向右移一位，即得到第3碼字。表12-7一種（7，3）循環(huán)碼的全部碼字序號碼字序號碼字信息位a6 a5 a4監(jiān)督位a3 a2 a1

56、 a0信息位a6 a5 a4監(jiān)督位a3 a2 a1 a010  0  00  0  0  051  0  01  0  1  120  0  10  1  1  161  0  11  1  0  0

57、30  1  01  1  1  071  1  00  1  0  140  1  11  0  0  181  1  10  0  1  0為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項是來表示

58、，這個多項式被稱為碼多項式，對于許用循環(huán)碼A=(   )，可以將它的碼多項式表示為：                （12-20）對于二進制碼組，多項式的每個系數(shù)不是0就是1，x僅是碼元位置的標志。因此，這里并不關心x的取值。而表12-7中的任一碼組可以表示為：             &

59、#160;      （12-20）對于二進制碼組，多項式的每個系數(shù)不是0就是1，x僅是碼元位置的標志。因此，這里并不關心x的取值。而表12-7中的任一碼組可以表示為：                 （12-21）例如，表中的第7碼字可以表示為：  （12-22）在整數(shù)運算中，有模n運算。例如，在模2運算中，有1+120（模2），1+231（模2），2&#

60、215;360（模2）等。因此，若一個整數(shù)m可以表示為:                        （12-23）則在模n運算下，有mp（模n），也就是說，在模n運算下，一整數(shù)m等于其被n除所得的余數(shù)。在碼多項式運算中也有類似的按模運算法則。若一任意多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，也就是：

61、0;                             （12-24）則可以寫為：F(x)R(x)（模N(x)）。這時，碼多項式系數(shù)仍按模2運算，即只取值0和1，假設：計算x4+x2+1除以x3+1的值可得：        

62、                     （12-25）注意，在上述運算中，由于是模2運算，因此，加法和減法是等價的，在式子中通常用加法運算符，具體模2運算的規(guī)則定義如下：模2加0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0模2乘0×0 = 00×1 = 01×0 = 01×1 = 1這樣式（12-25）也可以表示為：&#

63、160;                       (12-26)在循環(huán)碼中，若A(x)是一個長為n的許用碼組，則在按模運算下，亦是一個許用碼組，也就是假如：（模），可以證明亦是一個許用碼組，并且，正是A(x)代表的碼組向左循環(huán)移位i次的結果。例如，由式（12-22）表示的循環(huán)碼，其碼長n7，現(xiàn)給定i3，則：     

64、;           （12-27）其對應的碼組為0101110，它正是表12-7中第3碼字。通過上述分析和演算可以得到了一個重要的結論：一個長度為n的循環(huán)碼，它必為按模（）運算的一個余式。§12.4.2 循環(huán)碼的生成多項式和生成矩陣前k-1位為0的碼組（全0碼字除外）對應的多項式稱為生成多項式，用g(x)表示?？梢宰C明生成多項式g(x)具有以下特性：（1）g(x)是一個常數(shù)項為1的r=n-k次多項式；（2）g(x)是的一個因式；（3）該循環(huán)碼中其它碼多項式都是g(x)的倍

65、式。為了保證構成的生成矩陣G的各行線性不相關，通常用g(x)來構造生成矩陣，這時，生成矩陣G(x)可以表示成為：                           （12-28） 其中，因此，一旦生成多項式g(x)確定以后，該循環(huán)碼的生成矩陣就可以確定，進而該循環(huán)碼的所有碼字就可以確定。顯然，式（12-28）不符合形

66、式，所以此生成矩陣不是典型形式，不過，可以通過簡單的代數(shù)變換將它變成典型矩陣。現(xiàn)在以表12-7的（7，3）循環(huán)碼為例，來構造它的生成矩陣和生成多項式，這個循環(huán)碼主要參數(shù)為，n7，k3，r4。從表中可以看到，其生成多項式可以用第1碼字構造：                     （12-29）        

67、              （12-30）在上面的例子中，是利用表12-7給出的（7，3）循環(huán)碼的所有碼字，構造了它的生成多項式和生成矩陣。但在實際循環(huán)碼設計過程中，通常只給出碼長和信息位數(shù)，這就需要設計生成多項式和生成矩陣，這時可以利用g(x)所具有基本特性進行設計。首先，生成多項式g(x)是的一個因式，其次g(x)是一個r次因式。因此，就可以先對進行因式分解，找到它的r次因式。下面仍以（7，3）循環(huán)碼為例進行分析。第一步：對進行因式分解得： 

68、                      （12-31）第二步：構造生成多項式g（x）為了求（7，3）循環(huán)碼的生成多項式g(x)，要從式（8-31）中找到r=n-k次的因子。不難看出，這樣的因子有兩個，即：              &#

69、160;        (12-32)  (12-33)以上兩式都可作為生成多項式用。不過，選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組就不同。用式（12-32）作為生成多項式產(chǎn)生的循環(huán)碼即為表12-7所列。當然，在利用式（12-30）得到生成矩陣G以后，可以通過線性變化，使之成為典型矩陣，這時就可以采用類似式（12-13a）和式（12-15）方法，得到監(jiān)督矩陣H。除此之外，還可以利用循環(huán)碼的特點來確定監(jiān)督矩陣H。由于（n,k）循環(huán)碼中g(x)是的因式，因此可令：    

70、;                 (12-34)這里h（x）稱為監(jiān)督多項式。與式（12-28）所表示的G(x)相對應，監(jiān)督矩陣表示為：                        

71、60;     (12-35)其中是逆多項式。                 （12-36）對于表12-7中的（7,3）循環(huán)碼，則：§12.4.3 循環(huán)碼的編、譯碼方法1.編碼過程在編碼時，首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項式g(x)，也就是從的因子中選一個（n-k）次多項式作為g(x)；然后，利用循環(huán)碼的編碼特點，即所有循環(huán)碼多項式A(x)都可以被g(x)整

72、除，來定義生成多項式g(x)。根據(jù)上述原理可以得到一個較簡單的系統(tǒng)循環(huán)碼編碼方法：設要產(chǎn)生（n,k）循環(huán)碼，m(x)表示信息多項式，則其次數(shù)必小于k，而·m(x)的次數(shù)必小于n，用·m(x)除以g(x)，可得余數(shù)r(x)，r(x)的次數(shù)必小于（n-k），將r(x)加到信息位后作監(jiān)督位，就得到了系統(tǒng)循環(huán)碼。下面就將以上各步處理加以解釋。（1）用乘m(x)。這一運算實際上是把信息碼后附加上（n-k）個“0”。例如，信息碼為110，它相當于m(x)+x。當n-k7-34時，·m（x）+，它相當于1100000。而希望的到得系統(tǒng)循環(huán)碼多項式應當是A(x) = ·

73、m(x) + r(x)。（2）求r(x)。由于循環(huán)碼多項式A(x)都可以被g(x)整除，也就是：                     （12-37）因此，用·m(x)除以g(x)，就得到商Q(x)和余式r(x)，即             

74、60;                    （12-38）這樣就得到了r(x)。（3）編碼輸出系統(tǒng)循環(huán)碼多項式A(x)為：                       

75、      （12-39）例如，對于（7，3）循環(huán)碼，若選用，信息碼110時，則：                （12-40）上式相當于：這時的編碼輸出為：1100101。上述三步編碼過程，在硬件實現(xiàn)時，可以利用除法電路來實現(xiàn)，這里的除法電路采用一些移位寄存器和模2加法器來構成。下面將以（7,3）循環(huán)碼為例，來說明其具體實現(xiàn)過程。設該（7,3）循環(huán)碼的生成多項式為：，則構成的

76、系統(tǒng)循環(huán)碼編碼器如圖12-6所示，圖中有4個移位寄存器，一個雙刀雙擲開關。當信息位輸入時，開關位置接“2”，輸入的信息碼一方面送到除法器進行運算，一方面直接輸出；當信息位全部輸出后，開關位置接“1”，這時輸出端接到移位寄存器的輸出，這時除法的余項，也就是監(jiān)督位依次輸出。當信息碼為110時，編碼器的工作過程如表12-8：圖12-6 （7，3）循環(huán)碼編碼器順便指出，由于數(shù)字信號處理器（DSP）和大規(guī)?？删幊踢壿嬈骷–PLD和FPGA）的廣泛應用，目前已多采用這些先進器件和相應的軟件來實現(xiàn)上述編碼。表12-8 編碼器工作過程輸入 (m)移位寄存器 (abcd)反饋 (e) 輸出 (f)

77、00   0   0   0001101   1   1   01   0   0   11   0   1   011111000000   1   0  &

78、#160;10   0   1   00   0   0   10   0   0   0010101012.譯碼過程對于接收端譯碼的要求通常有兩個：檢錯與糾錯。達到檢錯目的的譯碼十分簡單，可以由式（12-37），通過判斷接收到的碼組多項式B(x)是否能被生成多項式g(x)整除作為依據(jù)。當傳輸中未發(fā)生錯誤時，也就是接收的碼組與發(fā)送的碼組相同，即A(x)=B(x)，則接收的碼組B(x)必能被g(x)整除；若傳輸中發(fā)生了錯誤，則A(x)B(x)，B(x)不能被g(x)整除。因此，可以根據(jù)余項是否