1、第八章差錯(cuò)控制編碼8.1 引言本節(jié)知識(shí)要點(diǎn)：信源及信源編碼信道編碼（差錯(cuò)控制編碼）糾錯(cuò)編碼的分類(lèi)網(wǎng)格編碼調(diào)制前向糾錯(cuò)差錯(cuò)控制（FEC）檢錯(cuò)重發(fā)差錯(cuò)控制（ARQ）混合糾錯(cuò)差錯(cuò)控制（HEC） 碼長(zhǎng)碼重碼距最小碼距糾錯(cuò)碼的基本原理8.1.1 信源編碼與信道編碼的基本概念設(shè)計(jì)通信系統(tǒng)的目的就是把信源產(chǎn)生的信息有效可靠地傳送到目的地。在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號(hào)傳輸?shù)挠行远扇〉木幋a稱(chēng)為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱(chēng)為信道編碼。信源編碼信源可以有各種不同的形式，例如在無(wú)線廣播中，信源一般是一個(gè)語(yǔ)音源（話音或音樂(lè)）；在電視廣播中，信源主要是活動(dòng)圖像的視頻信號(hào)源。這些信源的輸出都是

2、模擬信號(hào)，所以稱(chēng)之為模擬源。而數(shù)字通信系統(tǒng)是設(shè)計(jì)來(lái)傳送數(shù)字形式的信息，所以，這些模擬源如果想利用數(shù)字通信系統(tǒng)進(jìn)行傳輸，就需要將模擬信息源的輸出轉(zhuǎn)化為數(shù)字信號(hào)，而這個(gè)轉(zhuǎn)化構(gòu)成就稱(chēng)為信源編碼。對(duì)于信源編碼的研究，在通信領(lǐng)域受到了人們的廣泛關(guān)注。特別在移動(dòng)通信系統(tǒng)中，信源編碼（語(yǔ)音編碼）決定了接收到的語(yǔ)音的質(zhì)量和系統(tǒng)容量。因?yàn)樵谝苿?dòng)通信系統(tǒng)中，帶寬是很珍貴的，所以，如何在有限的可分配的帶寬內(nèi)容納更多的用戶(hù)，已經(jīng)成為經(jīng)營(yíng)者最為關(guān)心的問(wèn)題。而低比特率語(yǔ)音編碼提供了解決該問(wèn)題的一種方法。在編碼器能夠傳送高質(zhì)量語(yǔ)音的前提下，如果比特率越低，就可以在一定的帶寬內(nèi)能容納更多的語(yǔ)音通道。因此，生產(chǎn)商和服務(wù)提供商不

3、斷地尋求新的編碼方法，以便在低比特率條件下提供高質(zhì)量的語(yǔ)音。語(yǔ)音編碼的目的就是在保持一定算法復(fù)雜程度和通信時(shí)延的前提下，運(yùn)用盡可能少的信道容量，傳送盡可能高的語(yǔ)音質(zhì)量。目前較為常用的語(yǔ)音編碼形式有：脈沖編碼調(diào)制（PCM）、差分脈沖編碼調(diào)制（DPCM）、自適應(yīng)差分脈沖編碼調(diào)制（ADPCM）、增量調(diào)制（DM）、連續(xù)可變斜率增量調(diào)制（CVSDM）、自適應(yīng)預(yù)測(cè)編碼（APC）、自帶編碼（SBC）、碼激勵(lì)線性預(yù)測(cè)編碼等等。信道編碼（差錯(cuò)控制編碼）在實(shí)際信道傳輸數(shù)字信號(hào)的過(guò)程中，引起傳輸差錯(cuò)的根本原因在于信道內(nèi)存在的噪聲以及信道傳輸特性不理想所造成的碼間串?dāng)_。為了提高數(shù)字傳輸系統(tǒng)的可靠性，降低信息傳輸?shù)牟铄e(cuò)

4、率，可以利用均衡技術(shù)消除碼間串?dāng)_，利用增大發(fā)射功率、降低接收設(shè)備本身的噪聲、選擇好的調(diào)制制度和解調(diào)方法、加強(qiáng)天線的方向性等措施，提高數(shù)字傳輸系統(tǒng)的抗噪性能，但上述措施也只能將傳輸差錯(cuò)減小到一定程度。要進(jìn)一步提高數(shù)字傳輸系統(tǒng)的可靠性，就需要采用差錯(cuò)控制編碼，對(duì)可能或已經(jīng)出現(xiàn)的差錯(cuò)進(jìn)行控制。差錯(cuò)控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來(lái)不規(guī)律的或規(guī)律性不強(qiáng)的原始數(shù)字信號(hào)變?yōu)橛幸?guī)律的數(shù)字信號(hào)；差錯(cuò)控制譯碼則利用這些規(guī)律性來(lái)鑒別傳輸過(guò)程是否發(fā)生錯(cuò)誤，或進(jìn)而糾正錯(cuò)誤。原始數(shù)字信號(hào)是分組傳輸?shù)模缑縦個(gè)二進(jìn)制碼元為一組（稱(chēng)為信息組），經(jīng)信道編碼后轉(zhuǎn)換為每n個(gè)碼元一組的碼字（碼組

5、），這里nk，分組碼通常表示為（n，k）。可見(jiàn)，信道編碼是用增加數(shù)碼，利用“冗余”來(lái)提高抗干擾能力的，也就是以降低信息傳輸速率為代價(jià)來(lái)減少錯(cuò)誤的，或者說(shuō)是用削弱有效性來(lái)增強(qiáng)可靠性的。本章首先給出了差錯(cuò)控制編碼的基本概念，介紹了幾種常用簡(jiǎn)單分組碼，在此基礎(chǔ)上，對(duì)分組碼、循環(huán)碼和卷積碼基本原理和性能進(jìn)行了研究分析。8.1.2糾錯(cuò)編碼的分類(lèi)在差錯(cuò)控制系統(tǒng)中，信道編碼存在著多種實(shí)現(xiàn)方式，同時(shí)信道編碼也有多種分類(lèi)方法。（）按照信道編碼的不同功能，可以將它分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼僅能檢測(cè)誤碼，例如，在計(jì)算機(jī)串口通信中常用到的奇偶校驗(yàn)碼等；糾錯(cuò)碼可以糾正誤碼，當(dāng)然同時(shí)具有檢錯(cuò)的能力，當(dāng)發(fā)現(xiàn)不可糾正的錯(cuò)誤時(shí)

6、可以發(fā)出出錯(cuò)指示。（）按照信息碼元和監(jiān)督碼元之間的檢驗(yàn)關(guān)系，可以將它分為線性和非線性碼。若信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系，即滿(mǎn)足一組線性方程式，稱(chēng)為線性碼；否則，稱(chēng)為非線性碼。（）按照信息碼元和監(jiān)督碼元之間的約束方式不同，可以將它分為分組碼和卷積碼。在分組碼中，編碼后的碼元序列每n位分為一組，其中k位信息碼元，r個(gè)監(jiān)督位，r = n-k。監(jiān)督碼元僅與本碼字的信息碼元有關(guān)。卷積碼則不同，監(jiān)督碼元不但與本信息碼元有關(guān)，而且與前面碼字的信息碼元也有約束關(guān)系。（）按照信息碼元在編碼后是否保持原來(lái)的形式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元保持原樣不變，而非系統(tǒng)碼中的信息碼

7、元?jiǎng)t發(fā)生了變化。除了個(gè)別情況，系統(tǒng)碼的性能大體上與非系統(tǒng)碼相同，但是非系統(tǒng)碼的譯碼較為復(fù)雜，因此，系統(tǒng)碼得到了廣泛的應(yīng)用。（）按照糾正錯(cuò)誤的類(lèi)型不同，可以將它分為糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼兩種。前者主要用于發(fā)生零星獨(dú)立錯(cuò)誤的信道，而后者用于對(duì)付以突發(fā)錯(cuò)誤為主的信道。（）按照信道編碼所采用的數(shù)學(xué)方法不同，可以將它分為代數(shù)碼、幾何碼和算術(shù)碼。其中代數(shù)碼是目前發(fā)展最為完善的編碼，線性碼就是代數(shù)碼的一個(gè)重要的分支。除上述信道編碼的分類(lèi)方法以外，還可以將它分為二進(jìn)制信道編碼和多進(jìn)制信道編碼等等。同時(shí)，隨著數(shù)字通信系統(tǒng)的發(fā)展，可以將信道編碼器和調(diào)制器統(tǒng)一起來(lái)綜合設(shè)計(jì)，這就是所謂的網(wǎng)格編碼調(diào)制（TCM

8、Trellis Coded Modulation）。8.1.3 差錯(cuò)控制方式常用的差錯(cuò)控制方式主要有三種：前向糾錯(cuò)（簡(jiǎn)稱(chēng)FEC）、檢錯(cuò)重發(fā)（簡(jiǎn)稱(chēng)ARQ）和混合糾錯(cuò)（簡(jiǎn)稱(chēng)HEC），它們的結(jié)構(gòu)如圖8-1所示。圖中有斜線的方框圖表示在該端進(jìn)行錯(cuò)誤的檢測(cè)。前向糾錯(cuò)系統(tǒng)中，發(fā)送端經(jīng)信道編碼后可以發(fā)出具有糾錯(cuò)能力的碼字；接收端譯碼后不僅可以發(fā)現(xiàn)錯(cuò)誤碼，而且可以判斷錯(cuò)誤碼的位置并予以自動(dòng)糾正。然而，前向糾錯(cuò)編碼需要附加較多的冗余碼元，影響數(shù)據(jù)傳輸效率，同時(shí)其編譯碼設(shè)備比較復(fù)雜。但是由于不需要反饋信道，實(shí)時(shí)性較好，因此，這種技術(shù)在單工信道中普遍采用，例如無(wú)線電尋呼系統(tǒng)中采用的POGSAG編碼等。圖8-1差錯(cuò)控

9、制方式檢錯(cuò)重發(fā)方式中，發(fā)送端經(jīng)信道編碼后可以發(fā)出能夠檢測(cè)出錯(cuò)誤能力的碼字；接收端收到后經(jīng)檢測(cè)如果發(fā)現(xiàn)傳輸中有錯(cuò)誤，則通過(guò)反饋信道把這一判斷結(jié)果反饋給發(fā)送端。然后，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為已經(jīng)正確后為止。典型系統(tǒng)檢錯(cuò)重發(fā)方式的原理方框圖如圖8-2所示：常用的檢錯(cuò)重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)。停發(fā)等候重發(fā)系統(tǒng)的發(fā)送端在某一時(shí)刻向接收端發(fā)送一個(gè)碼字，接收端收到后經(jīng)檢測(cè)若未發(fā)現(xiàn)傳輸錯(cuò)誤，則發(fā)送一個(gè)認(rèn)可信號(hào)（ACK）給發(fā)送端，發(fā)送端收到ACK信號(hào)后再發(fā)下一個(gè)碼字；如果接收端檢測(cè)出錯(cuò)誤，則發(fā)送一個(gè)否認(rèn)信號(hào)（NAK），發(fā)送端收到NAK信號(hào)后重發(fā)前一個(gè)碼字，并再

10、次等待ACK和NAK信號(hào)。這種方式效率不高，但工作方式簡(jiǎn)單，在計(jì)算機(jī)數(shù)據(jù)通信中仍在使用。圖8-2ARQ系統(tǒng)組成方框圖在返回重發(fā)系統(tǒng)中，發(fā)送端無(wú)停頓的送出一個(gè)又一個(gè)碼字，不再等待ACK信號(hào)，一旦接收端發(fā)現(xiàn)錯(cuò)誤并發(fā)回NAK信號(hào)，則發(fā)送端從下一個(gè)碼字開(kāi)始重發(fā)前一段N組信號(hào)，N的大小取決于信號(hào)傳遞及處理所帶來(lái)的延遲，這種系統(tǒng)比停發(fā)等候重發(fā)系統(tǒng)有很大的改進(jìn)，在許多數(shù)據(jù)傳輸系統(tǒng)中得到應(yīng)用。在選擇重發(fā)系統(tǒng)中，發(fā)送端也是連續(xù)不斷地發(fā)送碼字，接收端發(fā)現(xiàn)錯(cuò)誤發(fā)回NAK信號(hào)。與返回重發(fā)系統(tǒng)不同的是，發(fā)送端不是重發(fā)前面的所有碼字，而是只重發(fā)有錯(cuò)誤的那一組。顯然，這種選擇重發(fā)系統(tǒng)傳輸效率最高，但控制最為復(fù)雜。此外，返回

11、重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)都需要全雙工的鏈路，而停發(fā)等候重發(fā)系統(tǒng)只需要半雙工的鏈路。基于上述分析，檢錯(cuò)重發(fā)（ARQ）的優(yōu)點(diǎn)主要表現(xiàn)在：（1）只需要少量的冗余碼，就可以得到極低的輸出誤碼率；（2）使用的檢錯(cuò)碼基本上與信道的統(tǒng)計(jì)特性無(wú)關(guān)，有一定的自適應(yīng)能力；（3）與FEC相比，信道編譯碼器的復(fù)雜性要低得多。同時(shí)它也存在某些不足，主要表現(xiàn)在：（1）需要反向信道，故不能用于單向傳輸系統(tǒng)，并且實(shí)現(xiàn)重發(fā)控制比較復(fù)雜；（2）當(dāng)信道干擾增大時(shí)，整個(gè)系統(tǒng)有可能處在重發(fā)循環(huán)當(dāng)中，因而通信效率低，不大適合于嚴(yán)格實(shí)時(shí)傳輸系統(tǒng)。混合糾錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合。在這種系統(tǒng)中發(fā)送端不但具有糾正錯(cuò)誤的能力，而且對(duì)

12、超出糾錯(cuò)能力的錯(cuò)誤有檢測(cè)能力。遇到后一種情況時(shí)，系統(tǒng)可以通過(guò)反饋信道要求發(fā)送端重發(fā)一遍。混和糾錯(cuò)方式在實(shí)時(shí)性和譯碼復(fù)雜性方面是前向糾錯(cuò)和檢錯(cuò)重發(fā)方式的折衷。在實(shí)際應(yīng)用中，上述幾種差錯(cuò)控制方式應(yīng)根據(jù)具體情況合理選用。8.1.4 糾錯(cuò)編碼的基本原理信道編碼的基本思想就是在被傳送的信息中附加一些監(jiān)督碼元，在收和發(fā)之間建立某種校驗(yàn)關(guān)系，當(dāng)這種校驗(yàn)關(guān)系因傳輸錯(cuò)誤而受到破壞時(shí)，可以被發(fā)現(xiàn)甚至糾正錯(cuò)誤，這種檢錯(cuò)與糾錯(cuò)能力是用信息量的冗余度來(lái)?yè)Q取的。下面將介紹幾個(gè)與信道編碼有關(guān)的基本概念：碼長(zhǎng)：碼字中碼元的數(shù)目；碼重：碼字中非0數(shù)字的數(shù)目；對(duì)于二進(jìn)制碼來(lái)講，碼重W就是碼元中1的數(shù)目，例如碼字10100，碼長(zhǎng)n

13、 = 5，碼重W = 2。碼距：兩個(gè)等長(zhǎng)碼字之間對(duì)應(yīng)位不同的數(shù)目，有時(shí)也稱(chēng)作這兩個(gè)碼字的漢明距離，例如碼字10100與11000之間的碼距d = 2。最小碼距：在碼字集合中全體碼字之間距離的最小數(shù)值。對(duì)于二進(jìn)制碼字而言，兩個(gè)碼字之間的模二相加，其不同的對(duì)應(yīng)位必為1，相同的對(duì)應(yīng)位必為0。因此，兩個(gè)碼字之間模二相加得到的碼重就是這兩個(gè)碼字之間的距離。以二進(jìn)制分組碼的糾錯(cuò)過(guò)程為例，可以較為詳細(xì)地說(shuō)明糾錯(cuò)碼檢錯(cuò)和糾錯(cuò)的基本原理。分組碼對(duì)于數(shù)字序列是分段進(jìn)行處理的，設(shè)每一段有k個(gè)碼元組成（稱(chēng)作長(zhǎng)度為k的信息組），由于每個(gè)碼元有0或1兩種值，故共有個(gè)不同的狀態(tài)。每段長(zhǎng)為k的信息組，以一定的規(guī)則增加r個(gè)多余

14、度碼元（稱(chēng)為監(jiān)督元），監(jiān)督這k個(gè)信息元，這樣就組成長(zhǎng)度為n k+r的碼字（又稱(chēng)n重）。共可以得到個(gè)長(zhǎng)度為n碼字，它們通常被稱(chēng)為許用碼字。而長(zhǎng)度為n的數(shù)字序列共有2n種可能的組合，其中 -個(gè)長(zhǎng)度為n碼字未被選用，故稱(chēng)它們?yōu)榻么a字。上述個(gè)長(zhǎng)度為n的許用碼字的集合稱(chēng)為分組碼。分組碼能夠檢錯(cuò)或糾錯(cuò)的原因是存在 -多余度碼字，或者說(shuō)在 碼字中有禁用碼字存在。下面就舉一個(gè)具體的例子：設(shè)發(fā)送端發(fā)送A和B兩個(gè)消息，分別用一位碼元來(lái)表示，1代表A，0代表B。如果這兩個(gè)信息組在傳輸中產(chǎn)生了錯(cuò)誤，那么就會(huì)使0錯(cuò)成了1或1錯(cuò)成了0，而接收端不能發(fā)現(xiàn)這種錯(cuò)誤，更談不上糾正錯(cuò)誤了。若在每個(gè)一位長(zhǎng)的信息組中加上一個(gè)監(jiān)督元

15、（r1），其規(guī)則是與信息元重復(fù)，這樣編出的兩個(gè)長(zhǎng)度為n2的碼字，它們分別為11（代表A）和00（代表B）。這時(shí)11、00就是許用碼字，這兩個(gè)碼字組成一個(gè)（2，1）分組碼，其特點(diǎn)是各碼字的碼元是重復(fù)的，故又稱(chēng)為重復(fù)碼。而01、10就是禁用碼字。設(shè)發(fā)送11經(jīng)信道傳輸錯(cuò)了一位，變成01或10，收端譯碼器根據(jù)重復(fù)碼的規(guī)則，能發(fā)現(xiàn)有一位錯(cuò)誤，但不能指明錯(cuò)在哪一位，也就是不能作出發(fā)送的消息是A（11）還是B（00）的判決。若信道干擾嚴(yán)重，使發(fā)送碼字的兩位都產(chǎn)生錯(cuò)誤，從而使11錯(cuò)成了00，收端譯碼器根據(jù)重復(fù)碼的規(guī)則檢驗(yàn)，不認(rèn)為有錯(cuò)，并且判決為消息B，造成了錯(cuò)判。這時(shí)可以發(fā)現(xiàn)：這種碼距為2的（2，1）重復(fù)碼能

16、確定一個(gè)碼元的錯(cuò)誤，不能確定二個(gè)碼元的錯(cuò)誤，也不能糾正錯(cuò)誤。若仍按重復(fù)碼的規(guī)則，再加一個(gè)監(jiān)督碼元，得到（3，1）重復(fù)碼，它的兩個(gè)碼字分別為111和000，其碼距為3。這樣其余六個(gè)碼字（001、010、100、110、101、011）為禁用碼字。設(shè)發(fā)送111（代表消息A），如果譯碼器收到的3重為110，根據(jù)重復(fù)碼的規(guī)則，發(fā)現(xiàn)有錯(cuò)，并且當(dāng)采用最大似然法譯碼時(shí)，把與發(fā)送碼字最相似的碼字認(rèn)為就是發(fā)送碼字。而110與111只有一位不同，與000有兩位不同，故判決為111。事實(shí)上，在一般情況下，錯(cuò)一位的可能性比錯(cuò)二位的可能性要大得多，從統(tǒng)計(jì)的觀點(diǎn)看，這樣判決是正確的。因此，這種（3，1）碼能夠糾正一個(gè)錯(cuò)誤

17、，但不能糾正兩個(gè)錯(cuò)誤，因?yàn)槿舭l(fā)送111，收到100時(shí)，根據(jù)譯碼規(guī)則將譯為000，這就判錯(cuò)了。類(lèi)似于前面的分析，這種碼若用來(lái)檢錯(cuò)，它可以發(fā)現(xiàn)兩個(gè)錯(cuò)誤，但不能發(fā)現(xiàn)三個(gè)錯(cuò)誤。當(dāng)然，還可以選用碼字更長(zhǎng)的重復(fù)碼進(jìn)行信道編碼，隨著碼字的增長(zhǎng)，重復(fù)碼的檢錯(cuò)和糾錯(cuò)能力會(huì)變得更強(qiáng)。上述例子表明：糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說(shuō)明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。因此，碼字之間的最小距離是衡量該碼字檢錯(cuò)和糾錯(cuò)能力的重要依據(jù)，最小碼距是信道編碼的一個(gè)重要的參數(shù)。在一般情況下，分組碼的最小漢明距離與檢錯(cuò)和糾錯(cuò)能力之間滿(mǎn)足下列關(guān)系：（1）當(dāng)碼字用于檢測(cè)錯(cuò)誤時(shí)，如果要檢測(cè)e個(gè)錯(cuò)誤

18、，則（8-1）這個(gè)關(guān)系可以利用圖8-3（a）予以說(shuō)明。在圖中用A和B分別表示兩個(gè)碼距為d0的碼字，若A發(fā)生e個(gè)錯(cuò)誤，則A就變成以A為球心，e為半徑的球面上的碼字，為了能將這些碼字分辯出來(lái)，它們必須距離其最近的碼字B有一位的差別，即A和B之間最小距離為。（2）當(dāng)碼字用于糾正錯(cuò)誤時(shí)，如果要糾正t個(gè)錯(cuò)誤，則（8-2）這個(gè)關(guān)系可以利用圖8-3（b）予以說(shuō)明。在圖中用A和B分別表示兩個(gè)碼距為的碼字，若A發(fā)生t個(gè)錯(cuò)誤，則A就變成以A為球心，t為半徑的球面上的碼字；B發(fā)生t個(gè)錯(cuò)誤，則B就變成以B為球心，t為半徑的球面上的碼字。為了在出現(xiàn)t個(gè)錯(cuò)誤之后，仍能夠分辯出A和B來(lái)，那么，A和B之間距離應(yīng)大于2t，最小

19、距離也應(yīng)當(dāng)使兩球體表面相距為1，即滿(mǎn)足不等式（8-2）。（2）若碼字用于糾t個(gè)錯(cuò)誤，同時(shí)檢e個(gè)錯(cuò)誤時(shí)（et），則（8-3）這個(gè)關(guān)系可以利用圖8-3(c)予以說(shuō)明。在圖中用A和B分別表示兩個(gè)碼距為的碼字，當(dāng)碼字出現(xiàn)t個(gè)或小于t個(gè)錯(cuò)誤時(shí)，系統(tǒng)按照糾錯(cuò)方式工作；當(dāng)碼字出現(xiàn)大于t個(gè)而小于e個(gè)錯(cuò)誤時(shí)，系統(tǒng)按照檢錯(cuò)方式工作；若A發(fā)生t個(gè)錯(cuò)誤，B發(fā)生e個(gè)錯(cuò)誤時(shí)，既要糾A的錯(cuò)，又要檢B的錯(cuò)，則A和B之間距離應(yīng)大于t+e，也就是滿(mǎn)足式（8-3）。圖8-3糾（檢）錯(cuò)能力的幾何解釋通常，在信道編碼過(guò)程中，監(jiān)督位越多糾錯(cuò)能力就越強(qiáng)，但編碼效率就越低。若碼字中信息位數(shù)為k，監(jiān)督位數(shù)為r，碼長(zhǎng)n = k+r。則編碼效率R

20、c可以用下式表示： （8-4）信道編碼的任務(wù)就是要根據(jù)不同的干擾特性，設(shè)計(jì)出編碼效率高、糾錯(cuò)能力強(qiáng)的編碼。在實(shí)際設(shè)計(jì)過(guò)程中，需要根據(jù)具體指標(biāo)要求，盡量簡(jiǎn)化編碼實(shí)現(xiàn)的復(fù)雜度，節(jié)省設(shè)計(jì)費(fèi)用。8.2 常用簡(jiǎn)單分組碼本節(jié)知識(shí)要點(diǎn)：奇偶監(jiān)督碼行列監(jiān)督碼恒比碼本節(jié)介紹幾種簡(jiǎn)單的檢錯(cuò)碼，這些信道編碼很簡(jiǎn)單，但有一定的檢錯(cuò)能力，且易于實(shí)現(xiàn)，因此得到廣泛應(yīng)用。8.2.1奇偶監(jiān)督碼奇偶監(jiān)督碼是奇監(jiān)督碼和偶監(jiān)督碼的統(tǒng)稱(chēng)，是一種最基本的檢錯(cuò)碼。它是由n-1位信息元和1位監(jiān)督元組成，可以表示成為（n，n-1）。如果是奇監(jiān)督碼，在附加上一個(gè)監(jiān)督元以后，碼長(zhǎng)為n的碼字中“1”的個(gè)數(shù)為奇數(shù)個(gè)；如果是偶監(jiān)督碼，在附加上一個(gè)監(jiān)督

21、元以后，碼長(zhǎng)為n的碼字中“1”的個(gè)數(shù)為偶數(shù)個(gè)。設(shè)：如果一個(gè)偶監(jiān)督碼的碼字用A=表示，則：=0（8-5）式中為監(jiān)督元，“+”為模二和（以后也這樣表示，請(qǐng)注意）。式（8-5）通常被稱(chēng)為監(jiān)督方程。利用式（8-5），由信息元即可求出監(jiān)督元。另外，如果發(fā)生單個(gè)（或奇數(shù)個(gè)）錯(cuò)誤，就會(huì)破壞這個(gè)關(guān)系式，因此通過(guò)該式能檢測(cè)碼字中是否發(fā)生了單個(gè)或奇數(shù)個(gè)錯(cuò)誤。奇偶監(jiān)督碼是一種有效地檢測(cè)單個(gè)錯(cuò)誤的方法，之所以將注意力集中在檢（或糾）單個(gè)錯(cuò)，這主要是因?yàn)榇a字中發(fā)生單個(gè)錯(cuò)誤的概率要比發(fā)生2個(gè)或多個(gè)錯(cuò)誤的概率大得多。例如，n = 5的碼字，如果碼字中各碼元的錯(cuò)誤是互相獨(dú)立，誤碼率為10-4，則錯(cuò)1、2、3、4和5位的概率分

22、別為：5、和。由此可見(jiàn)，要檢（或糾）錯(cuò)誤，首先要解決單個(gè)錯(cuò)誤，這樣才抓住了主要矛盾。一般情況下用上述偶監(jiān)督碼來(lái)檢出單個(gè)錯(cuò)誤，檢錯(cuò)效果是令人滿(mǎn)意的，不僅如此，奇偶監(jiān)督碼的編碼效率很高，隨n增大而趨近于l。下面就給出以碼長(zhǎng)n5為例，利用表8-1列出全部偶監(jiān)督碼字：在數(shù)字信息傳輸中，奇偶監(jiān)督碼的編碼可以用軟件實(shí)現(xiàn)，也可用硬件電路實(shí)現(xiàn)。圖8-4(a)就是碼長(zhǎng)為5的偶監(jiān)督碼編碼器。從圖中可以看到，4位碼元長(zhǎng)的信息組，串行送入四級(jí)移位寄存器（輸入定時(shí)緩沖器），同時(shí)經(jīng)模二運(yùn)算得到監(jiān)督元，存入輸出緩沖器末級(jí)，編碼完成即可輸出碼字。接收端的檢錯(cuò)電路如圖8-4(b)所示。當(dāng)一個(gè)接收碼組B完全進(jìn)入五級(jí)移存器內(nèi)時(shí)，開(kāi)

23、關(guān)S立即接通，從而得到檢錯(cuò)信號(hào)。如果接收碼組B無(wú)錯(cuò)，BA，則M0；如果接收碼組B有單個(gè)（或奇數(shù)個(gè)）錯(cuò)誤，則M1。表8-1碼長(zhǎng)5的偶監(jiān)督碼字序號(hào)碼字序號(hào)碼字信息碼元a4a3a2a1監(jiān)督字a0信息碼元a4a3a2a1監(jiān)督字a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110（a）編碼器（b）檢錯(cuò)電路圖8-4奇偶監(jiān)督碼的硬件實(shí)現(xiàn)8.2.2 行列監(jiān)督碼行列監(jiān)督碼又稱(chēng)水平垂直一致監(jiān)督碼或二維奇偶監(jiān)督碼，有時(shí)還被稱(chēng)為矩陣碼。它不僅對(duì)水平（行）方向的碼元

24、，而且還對(duì)垂直（列）方向的碼元實(shí)施奇偶監(jiān)督。一般Lm個(gè)信息元，附加L+m+1個(gè)監(jiān)督元，由L+1行，m+1列組成一個(gè)（Lm+L+m+1，Lm）行列監(jiān)督碼的碼字。表8-2就是（66，50）行列監(jiān)督碼的一個(gè)碼字（L5，M10），它的各行和各列對(duì)l的數(shù)目都實(shí)行偶數(shù)監(jiān)督。可以逐行傳輸，也可以逐列傳輸。譯碼時(shí)分別檢查各行、各列的監(jiān)督關(guān)系，判斷是否有錯(cuò)。表8-2（66，50）行列監(jiān)督碼的一個(gè)碼字1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10111100001100111000010101010100010111000111100這種碼有可能檢測(cè)偶數(shù)個(gè)錯(cuò)誤。因?yàn)槊啃械谋O(jiān)督位雖然

25、不能用于檢測(cè)本行中的偶數(shù)個(gè)錯(cuò)碼，但按列的方向就有可能檢測(cè)出來(lái)。可是也有一些偶數(shù)錯(cuò)碼不可能檢測(cè)出，例如，構(gòu)成矩形的四個(gè)錯(cuò)碼就檢測(cè)不出來(lái)。這種二維奇偶監(jiān)督碼適于檢測(cè)突發(fā)錯(cuò)碼。因?yàn)檫@種突發(fā)錯(cuò)碼常常成串出現(xiàn)，隨后有較長(zhǎng)一段無(wú)錯(cuò)區(qū)間，所以在某一行中出現(xiàn)多個(gè)奇數(shù)或偶數(shù)錯(cuò)碼的機(jī)會(huì)較多，這種方陣碼適于檢測(cè)這類(lèi)錯(cuò)碼。前述的一維奇偶監(jiān)督碼一般只適于檢測(cè)隨機(jī)錯(cuò)誤。由于方陣碼只對(duì)構(gòu)成矩形四角的錯(cuò)碼無(wú)法檢測(cè)，故其檢錯(cuò)能力較強(qiáng)。一些試驗(yàn)測(cè)量表明，這種碼可使誤碼率降至原誤碼率的百分之一到萬(wàn)分之一。二維奇偶監(jiān)督碼不僅可用來(lái)檢錯(cuò)，還可用來(lái)糾正一些錯(cuò)碼。例如，當(dāng)碼組中僅在一行中有奇數(shù)個(gè)錯(cuò)誤時(shí)，則能夠確定錯(cuò)碼位置，從而糾正它。8.

26、2.3 恒比碼恒比碼又稱(chēng)等重碼,這種碼的碼子中1和0的位數(shù)保持恒定比例。由于每個(gè)碼字的長(zhǎng)度是相同的，若1、0恒比，則碼字必等重。若碼長(zhǎng)為n，碼重為w，則此碼的碼字個(gè)數(shù)為，禁用碼字?jǐn)?shù)為。該碼的檢錯(cuò)能力較強(qiáng)，除對(duì)換差錯(cuò)（1和0成對(duì)的產(chǎn)生錯(cuò)誤）不能發(fā)現(xiàn)外，其它各種錯(cuò)誤均能發(fā)現(xiàn)。目前我國(guó)電傳通信中普遍采用3：2碼，該碼共有個(gè)許用碼字，用來(lái)傳送10個(gè)阿拉伯?dāng)?shù)字，如表8-3所示。這種碼又稱(chēng)為5中取3數(shù)字保護(hù)碼。因?yàn)槊總€(gè)漢字是以四位十進(jìn)制數(shù)來(lái)代表的，所以提高十進(jìn)制數(shù)字傳輸?shù)目煽啃裕偷扔谔岣邼h字傳輸?shù)目煽啃浴?shí)踐證明，采用這種碼后，我國(guó)漢字電報(bào)的差錯(cuò)串大為降低。表8-3 3:2數(shù)字保護(hù)碼數(shù)字碼字012345

27、678901101010111100110110110100011110101111000111010011目前國(guó)際上通用的ARQ電報(bào)通信系統(tǒng)中，采用3：4碼即7中取3碼，這種碼共有個(gè)許用碼字，93個(gè)禁用碼字。35個(gè)許用碼字用來(lái)代表不同的字母和符號(hào)。實(shí)踐證明，應(yīng)用這種碼，使國(guó)際電報(bào)通信的誤碼率保持在以下。8.3 線性分組碼本節(jié)知識(shí)要點(diǎn)：分組碼線性分組碼線性分組碼的性質(zhì)線性分組碼的構(gòu)造監(jiān)督矩陣H生成矩陣G校驗(yàn)子漢明碼8.3.1 基本概念分組碼是一組固定長(zhǎng)度的碼組，可表示為（n , k），通常它用于前向糾錯(cuò)。在分組碼中，監(jiān)督位被加到信息位之后，形成新的碼。在編碼時(shí)，k個(gè)信息位被編為n位碼組長(zhǎng)度，而

28、n-k個(gè)監(jiān)督位的作用就是實(shí)現(xiàn)檢錯(cuò)與糾錯(cuò)。當(dāng)分組碼的信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系時(shí)，這種分組碼就稱(chēng)為線性分組碼。對(duì)于長(zhǎng)度為n的二進(jìn)制線性分組碼，它有種可能的碼組，從種碼組中，可以選擇M=個(gè)碼組（kn）組成一種碼。這樣，一個(gè)k比特信息的線性分組碼可以映射到一個(gè)長(zhǎng)度為n碼組上，該碼組是從M=個(gè)碼組構(gòu)成的碼集中選出來(lái)的，這樣剩下的碼組就可以對(duì)這個(gè)分組碼進(jìn)行檢錯(cuò)或糾錯(cuò)。線性分組碼是建立在代數(shù)群論基礎(chǔ)之上的，各許用碼的集合構(gòu)成了代數(shù)學(xué)中的群，它們的主要性質(zhì)如下：（1）任意兩許用碼之和（對(duì)于二進(jìn)制碼這個(gè)和的含義是模二和）仍為一許用碼，也就是說(shuō)，線性分組碼具有封閉性；（2）碼組間的最小碼距等于非零碼

29、的最小碼重。在8.2.1節(jié)中介紹的奇偶監(jiān)督碼，就是一種最簡(jiǎn)單的線性分組碼，由于只有一位監(jiān)督位通常可以表示為（n,n-1），式（8-5）表示采用偶校驗(yàn)時(shí)的監(jiān)督關(guān)系。在接收端解碼時(shí)，實(shí)際上就是在計(jì)算：（8-6）其中， 表示接收到的信息位，表示接收到的監(jiān)督位，若S0，就認(rèn)為無(wú)錯(cuò)；若S1就認(rèn)為有錯(cuò)。式（8-6）被稱(chēng)為監(jiān)督關(guān)系式，S是校正子。由于校正子S的取值只有“0”和“1”兩種狀態(tài)，因此，它只能表示有錯(cuò)和無(wú)錯(cuò)這兩種信息，而不能指出錯(cuò)碼的位置。設(shè)想如果監(jiān)督位增加一位，即變成兩位，則能增加一個(gè)類(lèi)似于式（8-6）的監(jiān)督關(guān)系式，計(jì)算出兩個(gè)校正子和，而共有4種組合：00，01，10，11，可以表示4種不同的信

30、息。除了用00表示無(wú)錯(cuò)以外，其余3種狀態(tài)就可用于指示3種不同的誤碼圖樣。同理，由r個(gè)監(jiān)督方程式計(jì)算得到的校正子有r位，可以用來(lái)指示-1種誤碼圖樣。對(duì)于一位誤碼來(lái)說(shuō)，就可以指示-1個(gè)誤碼位置。對(duì)于碼組長(zhǎng)度為n、信息碼元為k位、監(jiān)督碼元為rn - k位的分組碼（常記作（n，k）碼），如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來(lái)指示一位錯(cuò)碼的n種可能，則要求：（8-7)下面通過(guò)一個(gè)例子來(lái)說(shuō)明線性分組碼是如何構(gòu)造的。設(shè)分組碼（n , k）中k = 4，為了能夠糾正一位錯(cuò)誤，由式（8-7）可以看到，要求r 3，若取r = 3，則n = k+r = 7。因此，可以用表示這7個(gè)碼元，用、表示利用三個(gè)監(jiān)督方程，

31、通過(guò)計(jì)算得到的校正子，并且假設(shè)、三位校正字碼組與誤碼位置的關(guān)系如表8-4（當(dāng)然，也可以規(guī)定成另一種對(duì)應(yīng)關(guān)系，這并不影響討論的一般性）：由表中規(guī)定可已看到，僅當(dāng)一錯(cuò)碼位置在時(shí)，校正子為1；否則為0。這就意味著四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：(8-8a）同理，構(gòu)成偶數(shù)監(jiān)督關(guān)系：（8-8b）表8-4校正字與誤碼位置S1S2S3誤碼位置S1S2S3誤碼位置001010100011a0a1a2a3101110111000a4a5a6無(wú)錯(cuò)以及構(gòu)成有數(shù)監(jiān)督關(guān)系：（8-8c）在發(fā)送端編碼時(shí)是信息碼元，它們的值取決于輸入信號(hào)，因此是隨機(jī)的。是監(jiān)督碼元，它們的取值由監(jiān)督關(guān)系來(lái)確定，即監(jiān)督位應(yīng)使式（8-8）的三個(gè)表達(dá)式中

32、的、和的值為零（表示編成的碼組中應(yīng)無(wú)錯(cuò)碼），這樣式（8-8）的三個(gè)表達(dá)式可以表示成下面的方程組形式：（8-9）由上式經(jīng)移項(xiàng)運(yùn)算，接出監(jiān)督位（8-10）根據(jù)上面兩個(gè)線性關(guān)系，可以得到16個(gè)許用碼組如表8-5所示：表8-5許用碼組信息位監(jiān)督位信息位監(jiān)督位信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001001000110000111011100100010101000111110101011000100010011010101111110001000111001101110011110010101

33、00111接收端收到每個(gè)碼組后，計(jì)算出、和，如不全為0，則可按表8-4確定誤碼的位置，然后予以糾正。例如，接收碼組為0000011，可算出011，由表8-4可知在位置上有一誤碼。不難看出，上述（7，4）碼的最小碼距，因此，它能糾正一個(gè)誤碼或檢測(cè)兩個(gè)誤碼。如超出糾錯(cuò)能力，則反而會(huì)因“亂糾”而增加新的誤碼。8.3.2 監(jiān)督矩陣H和生成矩陣G式（8-9）所述（7，4）碼的三個(gè)監(jiān)督方程式可以重新改寫(xiě)為如下形式：（8-11）對(duì)于式（8-11）可以用矩陣形式來(lái)表示：（8-12）上式可以記作：或，其中（8-13a）（8-13b）（8-13c）通常H稱(chēng)為監(jiān)督矩陣，A稱(chēng)為信道編碼得到的碼字。在這個(gè)例子中H為rn

34、階矩陣，P為rk階矩陣，Ir為rr階單位矩陣，具有這種特性的H矩陣稱(chēng)為典型監(jiān)督矩陣，這是一種較為簡(jiǎn)單的信道編譯碼方式。典型形式的監(jiān)督矩陣各行是線性無(wú)關(guān)的，非典型形式的監(jiān)督矩陣可以經(jīng)過(guò)行或列的運(yùn)算化為典型形式。對(duì)于式（8-10）也可以用矩陣形式來(lái)表示：或者（8-14）比較式（8-13a）和式（8-14）可以看到，如果在Q矩陣的左邊在加上一個(gè)kk的單位矩陣，就形成了一個(gè)新矩陣G：（8-15）這里G稱(chēng)為生成矩陣，利用它可以產(chǎn)生整個(gè)碼組（8-16）由式（8-15）表示的生成矩陣形式稱(chēng)為典型生成矩陣，利用式（8-16）產(chǎn)生的分組碼必為系統(tǒng)碼，也就是信息碼元保持不變，監(jiān)督碼元附加在其后。8.3.3 校驗(yàn)子

35、S在發(fā)送端信息碼元M利用式（8-16），實(shí)現(xiàn)信道編碼，產(chǎn)生線性分組碼A；在傳輸過(guò)程中有可能出現(xiàn)誤碼，設(shè)接收到的碼組為B。則收發(fā)碼組之差為：（8-17）這里，表示i位有錯(cuò)，表示i位無(wú)錯(cuò)。基于這樣的原則接收端利用接收到的碼組B計(jì)算校正子：（8-18）因此，校正子僅與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系。對(duì)于上述（7，4）碼，校正子S與錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系可由式（8-18）求得，其計(jì)算結(jié)果見(jiàn)表8-6所示。在接收端的譯碼器中有專(zhuān)門(mén)的校正子計(jì)算電路，從而實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。表8-6（7，4）碼校正子與錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系序號(hào)錯(cuò)誤碼位ESe6 e5 e4 e3 e2 e1 e0S3S2S101234567/

36、b0b1b2b3b4b5b6000000000000010000010000010000010000010000010000010000000000010101000111011101118.3.4漢明碼漢明碼是一種能夠糾正單個(gè)錯(cuò)誤的線性分組碼。它有以下特點(diǎn)：（1）最小碼距，可以糾正一位錯(cuò)誤；（2）碼長(zhǎng)n與監(jiān)督元個(gè)數(shù)r之間滿(mǎn)足關(guān)系式：。如果要產(chǎn)生一個(gè)系統(tǒng)漢明碼，可以將矩陣H轉(zhuǎn)換成典型形式的監(jiān)督矩陣，進(jìn)一步利用Q = PT的關(guān)系，得到相應(yīng)的生成矩陣G。通常二進(jìn)制漢明碼可以表示為：（8-19）根據(jù)上述漢明碼定義可以看到，8.3.1構(gòu)造的（7，4）線性分組碼實(shí)際上就是一個(gè)漢明碼，它滿(mǎn)足漢明碼的兩個(gè)特

37、點(diǎn)。圖8-5中給出（7，4）系統(tǒng)漢明碼的編碼器和譯碼器電路。（a）發(fā)端編碼器（b）收端譯編碼器圖8-5（7，4）漢明碼的編譯碼器8.4循環(huán)碼本節(jié)知識(shí)要點(diǎn)：循環(huán)碼的特點(diǎn)碼多項(xiàng)式循環(huán)碼的生成多項(xiàng)式及其特征循環(huán)碼的生成矩陣生成多項(xiàng)式和生成矩陣的設(shè)計(jì)監(jiān)督矩陣H循環(huán)碼的編碼循環(huán)碼編碼硬件實(shí)現(xiàn)循環(huán)碼的譯碼循環(huán)碼是線性分組碼的一個(gè)重要子集，是目前研究得最成熟的一類(lèi)碼。它有許多特殊的代數(shù)性質(zhì)，這些性質(zhì)有助于按所要求的糾錯(cuò)能力系統(tǒng)地構(gòu)造這類(lèi)碼，且易于實(shí)現(xiàn)；同時(shí)循環(huán)碼的性能也較好，具有較強(qiáng)的檢錯(cuò)和糾錯(cuò)能力。8.4.1循環(huán)碼的特點(diǎn)循環(huán)碼最大的特點(diǎn)就是碼字的循環(huán)特性，所謂循環(huán)特性是指：循環(huán)碼中任一許用碼組經(jīng)過(guò)循環(huán)移位

38、后，所得到的碼組仍然是許用碼組。若（ ）為一循環(huán)碼組，則（）、（ ）、還是許用碼組。也就是說(shuō)，不論是左移還是右移，也不論移多少位，仍然是許用的循環(huán)碼組。表8-7給出了一種（7，3）循環(huán)碼的全部碼字。由此表可以直觀地看出這種碼的循環(huán)特性。例如，表中的第2碼字向右移一位，即得到第5碼字；第6碼字組向右移一位，即得到第3碼字。為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項(xiàng)是來(lái)表示，這個(gè)多項(xiàng)式被稱(chēng)為碼多項(xiàng)式，對(duì)于許用循環(huán)碼A=( )，可以將它的碼多項(xiàng)式表示為：（8-20）對(duì)于二進(jìn)制碼組，多項(xiàng)式的每個(gè)系數(shù)不是0就是1，x僅是碼元位置的標(biāo)志。因此，這里并不關(guān)心x的取值。而表8-7中的任一碼組可以表示為：

39、（8-20）對(duì)于二進(jìn)制碼組，多項(xiàng)式的每個(gè)系數(shù)不是0就是1，x僅是碼元位置的標(biāo)志。因此，這里并不關(guān)心x的取值。而表8-7中的任一碼組可以表示為：（8-21）表8-7一種（7，3）循環(huán)碼的全部碼字序號(hào)碼字序號(hào)碼字信息位a6 a5 a4監(jiān)督位a3 a2 a1 a0信息位a6 a5 a4監(jiān)督位a3 a2 a1 a01000000051001011200101116101110030101110711001014011100181110010例如，表中的第7碼字可以表示為：（8-22）在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有1+120（模2），1+231（模2），2360（模2）等。因此，若一個(gè)

40、整數(shù)m可以表示為:（8-23）則在模n運(yùn)算下，有mp（模n），也就是說(shuō)，在模n運(yùn)算下，一整數(shù)m等于其被n除所得的余數(shù)。在碼多項(xiàng)式運(yùn)算中也有類(lèi)似的按模運(yùn)算法則。若一任意多項(xiàng)式F(x)被一個(gè)n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，也就是：（8-24）則可以寫(xiě)為：F(x)R(x)（模N(x)）。這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，即只取值0和1，假設(shè)：計(jì)算x4+x2+1除以x3+1的值可得：（8-25）注意，在上述運(yùn)算中，由于是模2運(yùn)算，因此，加法和減法是等價(jià)的，在式子中通常用加法運(yùn)算符，具體模2運(yùn)算的規(guī)則定義如下：模2加0 + 0 = 00 + 1 = 11 + 0 =

41、11 + 1 = 0模2乘00 = 001 = 010 = 011 = 1這樣式（8-25）也可以表示為：(8-26)在循環(huán)碼中，若A(x)是一個(gè)長(zhǎng)為n的許用碼組，則在按模運(yùn)算下，亦是一個(gè)許用碼組，也就是假如：（模），可以證明亦是一個(gè)許用碼組，并且，正是A(x)代表的碼組向左循環(huán)移位i次的結(jié)果。例如，由式（8-22）表示的循環(huán)碼，其碼長(zhǎng)n7，現(xiàn)給定i3，則：（8-27）其對(duì)應(yīng)的碼組為0101110，它正是表8-7中第3碼字。通過(guò)上述分析和演算可以得到了一個(gè)重要的結(jié)論：一個(gè)長(zhǎng)度為n的循環(huán)碼，它必為按模（）運(yùn)算的一個(gè)余式。8.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣（全0碼字除外）稱(chēng)為生成多項(xiàng)式，用g(

42、x)表示。可以證明生成多項(xiàng)式g(x)具有以下特性：（1）g(x)是一個(gè)常數(shù)項(xiàng)為1的r=n-k次多項(xiàng)式；（2）g(x)是的一個(gè)因式；（3）該循環(huán)碼中其它碼多項(xiàng)式都是g(x)的倍式。為了保證構(gòu)成的生成矩陣G的各行線性不相關(guān)，通常用g(x)來(lái)構(gòu)造生成矩陣，這時(shí)，生成矩陣G(x)可以表示成為：（8-28）其中，因此，一旦生成多項(xiàng)式g(x)確定以后，該循環(huán)碼的生成矩陣就可以確定，進(jìn)而該循環(huán)碼的所有碼字就可以確定。顯然，式（8-28）不符合形式，所以此生成矩陣不是典型形式，不過(guò)，可以通過(guò)簡(jiǎn)單的代數(shù)變換將它變成典型矩陣。現(xiàn)在以表8-7的（7，3）循環(huán)碼為例，來(lái)構(gòu)造它的生成矩陣和生成多項(xiàng)式，這個(gè)循環(huán)碼主要參數(shù)

43、為，n7，k3，r4。從表中可以看到，其生成多項(xiàng)式可以用第1碼字構(gòu)造：（8-29）（8-30）在上面的例子中，是利用表8-7給出的（7，3）循環(huán)碼的所有碼字，構(gòu)造了它的生成多項(xiàng)式和生成矩陣。但在實(shí)際循環(huán)碼設(shè)計(jì)過(guò)程中，通常只給出碼長(zhǎng)和信息位數(shù)，這就需要設(shè)計(jì)生成多項(xiàng)式和生成矩陣，這時(shí)可以利用g(x)所具有基本特性進(jìn)行設(shè)計(jì)。首先，生成多項(xiàng)式g(x)是的一個(gè)因式，其次g(x)是一個(gè)r次因式。因此，就可以先對(duì)進(jìn)行因式分解，找到它的r次因式。下面仍以（7，3）循環(huán)碼為例進(jìn)行分析。第一步：對(duì)進(jìn)行因式分解得：（8-31）第二步：構(gòu)造生成多項(xiàng)式g（x）為了求（7，3）循環(huán)碼的生成多項(xiàng)式g(x)，要從式（8-31

44、）中找到r=n-k次的因子。不難看出，這樣的因子有兩個(gè)，即：(8-32)(8-33)以上兩式都可作為生成多項(xiàng)式用。不過(guò)，選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組就不同。用式（8-32）作為生成多項(xiàng)式產(chǎn)生的循環(huán)碼即為表8-7所列。當(dāng)然，在利用式（8-30）得到生成矩陣G以后，可以通過(guò)線性變化，使之成為典型矩陣，這時(shí)就可以采用類(lèi)似式（8-13a）和式（8-15）方法，得到監(jiān)督矩陣H。除此之外，還可以利用循環(huán)碼的特點(diǎn)來(lái)確定監(jiān)督矩陣H。由于（n,k）循環(huán)碼中g(shù)(x)是的因式，因此可令：(8-34)這里h（x）稱(chēng)為監(jiān)督多項(xiàng)式。與式（8-28）所表示的G(x)相對(duì)應(yīng)，監(jiān)督矩陣表示為：(8-35)其中是逆多

45、項(xiàng)式。（8-36）對(duì)于表8-7中的（7,3）循環(huán)碼，則：8.4.3循環(huán)碼的編、譯碼方法1.編碼過(guò)程在編碼時(shí)，首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項(xiàng)式g(x)，也就是從的因子中選一個(gè)（n-k）次多項(xiàng)式作為g(x)；然后，利用循環(huán)碼的編碼特點(diǎn)，即所有循環(huán)碼多項(xiàng)式A(x)都可以被g(x)整除，來(lái)定義生成多項(xiàng)式g(x)。根據(jù)上述原理可以得到一個(gè)較簡(jiǎn)單的系統(tǒng)循環(huán)碼編碼方法：設(shè)要產(chǎn)生（n,k）循環(huán)碼，m(x)表示信息多項(xiàng)式，則其次數(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)碼。下面就將以上

46、各步處理加以解釋。（1）用乘m(x)。這一運(yùn)算實(shí)際上是把信息碼后附加上（n-k）個(gè)“0”。例如，信息碼為110，它相當(dāng)于m(x)+x。當(dāng)n-k7-34時(shí)，m（x）+，它相當(dāng)于1100000。而希望的到得系統(tǒng)循環(huán)碼多項(xiàng)式應(yīng)當(dāng)是A(x) = m(x) + r(x)。（2）求r(x)。由于循環(huán)碼多項(xiàng)式A(x)都可以被g(x)整除，也就是：（8-37）因此，用m(x)除以g(x)，就得到商Q(x)和余式r(x)，即（8-38）這樣就得到了r(x)。（3）編碼輸出系統(tǒng)循環(huán)碼多項(xiàng)式A(x)為：（8-39）例如，對(duì)于（7，3）循環(huán)碼，若選用，信息碼110時(shí)，則：（8-40）上式相當(dāng)于：這時(shí)的編碼輸出為：11

47、00101。上述三步編碼過(guò)程，在硬件實(shí)現(xiàn)時(shí)，可以利用除法電路來(lái)實(shí)現(xiàn)，這里的除法電路采用一些移位寄存器和模2加法器來(lái)構(gòu)成。下面將以（7,3）循環(huán)碼為例，來(lái)說(shuō)明其具體實(shí)現(xiàn)過(guò)程。設(shè)該（7,3）循環(huán)碼的生成多項(xiàng)式為：，則構(gòu)成的系統(tǒng)循環(huán)碼編碼器如圖8-6所示，圖中有4個(gè)移位寄存器，一個(gè)雙刀雙擲開(kāi)關(guān)。當(dāng)信息位輸入時(shí)，開(kāi)關(guān)位置接“2”，輸入的信息碼一方面送到除法器進(jìn)行運(yùn)算，一方面直接輸出；當(dāng)信息位全部輸出后，開(kāi)關(guān)位置接“1”，這時(shí)輸出端接到移位寄存器的輸出，這時(shí)除法的余項(xiàng)，也就是監(jiān)督位依次輸出。當(dāng)信息碼為110時(shí)，編碼器的工作過(guò)程如表8-8：圖8-6（7，3）循環(huán)碼編碼器順便指出，由于數(shù)字信號(hào)處理器（DSP

48、）和大規(guī)模可編程邏輯器件（CPLD和FPGA）的廣泛應(yīng)用，目前已多采用這些先進(jìn)器件和相應(yīng)的軟件來(lái)實(shí)現(xiàn)上述編碼。表8-8 編碼器工作過(guò)程輸入 (m)移位寄存器 (abcd)反饋 (e)輸出 (f)000000011011101001101011111000000101001000010000010101012.譯碼過(guò)程對(duì)于接收端譯碼的要求通常有兩個(gè)：檢錯(cuò)與糾錯(cuò)。達(dá)到檢錯(cuò)目的的譯碼十分簡(jiǎn)單，可以由式（8-37），通過(guò)判斷接收到的碼組多項(xiàng)式B(x)是否能被生成多項(xiàng)式g(x)整除作為依據(jù)。當(dāng)傳輸中未發(fā)生錯(cuò)誤時(shí)，也就是接收的碼組與發(fā)送的碼組相同，即A(x)=B(x)，則接收的碼組B(x)必能被g(x)整

49、除；若傳輸中發(fā)生了錯(cuò)誤，則A(x)B(x)，B(x)不能被g(x)整除。因此，可以根據(jù)余項(xiàng)是否為零來(lái)判斷碼組中有無(wú)錯(cuò)碼。需要指出的是，有錯(cuò)碼的接收碼組也有可能被g(x)整除，這時(shí)的錯(cuò)碼就不能檢出了。這種錯(cuò)誤被稱(chēng)為不可檢錯(cuò)誤，不可檢錯(cuò)誤中的錯(cuò)碼數(shù)必將超過(guò)這種編碼的檢錯(cuò)能力。在接收端為糾錯(cuò)而采用的譯碼方法自然比檢錯(cuò)要復(fù)雜許多，因此，對(duì)糾錯(cuò)碼的研究大都集中在譯碼算法上。我們知道，校正子與錯(cuò)誤圖樣之間存在某種對(duì)應(yīng)關(guān)系。如同其它線性分組碼，循環(huán)碼的譯碼可以分三步進(jìn)行：（1）由接收到的碼多項(xiàng)式B(x)計(jì)算校正子（伴隨式）多項(xiàng)式S(x)；（2）由校正子S(x)確定錯(cuò)誤圖樣E(x)；（3）將錯(cuò)誤圖樣E(x)與B(x)相加，糾正錯(cuò)誤。上述第（1）步運(yùn)算和檢錯(cuò)譯碼類(lèi)似，也就是求解B(x)整除g(x)的余式，第（3）步也很簡(jiǎn)單。因此，糾錯(cuò)碼譯碼器的復(fù)雜性主要取決于譯碼過(guò)程的第（2）步。基于錯(cuò)誤圖樣識(shí)別的譯碼器稱(chēng)為梅吉特譯碼器，它的原理圖如圖8-7所示。錯(cuò)誤圖樣識(shí)別器是一個(gè)具有（n-k）個(gè)輸入端的邏輯電路，原則