信息論與編碼技術

信息論與編碼技術第一頁，共一百六十五頁，2022年，8月28日在通信系統(tǒng)中，要提高信息傳輸?shù)挠行?，我們將信源的輸出?jīng)過信源編碼用較少的符號來表達信源消息，這些符號剩余度很小，效率很高，但對噪聲干擾的抵抗能力很弱。信息傳輸要通過各種物理信道，由于干擾、設備故障等影響，被傳送的信源符號可能會發(fā)生失真，使有用信息遭受損壞，接收信號造成誤判。這種在接收端錯誤地確定所接收的信號叫做差錯。為了提高信息傳輸?shù)臏蚀_性，使其具有較好的抵抗信道中噪聲干擾的能力，在通信系統(tǒng)中需要采用專門的檢、糾錯誤方法，即差錯控制。

第二頁，共一百六十五頁，2022年，8月28日差錯控制的任務是發(fā)現(xiàn)所產(chǎn)生的錯誤、并指出發(fā)生錯誤的信號或者校正錯誤，差錯控制是采用可靠、有效的信道編碼方法來實現(xiàn)的。

信道編碼器要對信源編碼輸出的符號進行變換，使其盡量少受噪聲干擾的影響，減少傳輸差錯，提高通信可靠性。本章要討論的問題是在符號受到噪聲干擾的影響后，如何從接收到的信號中恢復出原送入信道的信號、確定差錯概率是多少等等。本章首先討論信道編碼的基本概念和分類，在此基礎上再討論兩類主要的信道編、譯碼方法，即線性分組碼與卷積碼。

第三頁，共一百六十五頁，2022年，8月28日6.1信道編碼的概念

進行信道編碼是為了提高信號傳輸?shù)目煽啃?，改善通信系統(tǒng)的傳輸質(zhì)量，研究信道編碼的目標是尋找具體構造編碼的理論與方法。在理論上，香農(nóng)第二定理已指出，只要實際信息傳輸率(信道容量)，則無差錯的信道編、譯碼方法是存在的。從原理上看，構造信道碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為地加入一定的多余碼元(稱為監(jiān)督碼)，以引入最小的多余度為代價來換取最好的抗干擾性能。

第四頁，共一百六十五頁，2022年，8月28日6.1.1信道編碼的分類由于實際信道存在噪聲和干擾，使發(fā)送的碼字與信道傳輸后所接收到的碼字之間存在差錯。在一般情況下，信道中噪聲或干擾越大，碼字產(chǎn)生差錯的概率也就越大。有些實際信道既有獨立隨機差錯也有突發(fā)性成串的差錯，這種信道稱混合差錯信道，實際的移動信道屬于此類信道。對不同的信道需要設計不同類型的信道編碼方案，按照信道特性進行劃分，信道編碼可分為：以糾獨立隨機差錯為主的信道編碼、以糾突發(fā)差錯為主的信道編碼和糾混合差錯的信道編碼。從功能上看，信道編碼可分為檢錯(可以發(fā)現(xiàn)錯誤)碼與糾錯(不僅能發(fā)現(xiàn)而且能自動糾正)碼兩類，糾錯碼一定能檢錯，檢錯碼不一定能糾錯，平常所說的糾錯碼是兩者的統(tǒng)稱。第五頁，共一百六十五頁，2022年，8月28日

根據(jù)信息碼元與監(jiān)督碼元之間的關系，糾錯碼分為線性碼和非線性碼。線性碼——信息碼元與監(jiān)督碼元之間呈線性關系，它們的關系可用一組線性代數(shù)方程聯(lián)系起來。非線性碼——信息碼元與監(jiān)督校元之間不存在線性關系。按照對信息碼元處理的方法的不同，糾錯碼分為分組碼和卷積碼。

分組碼----把信息序列以每個碼元分組，然后把每組個信息元按一定規(guī)律產(chǎn)生個多余的監(jiān)督碼元，輸出序列每組長為，則每一碼字的個校驗元只與本碼字的個信息位有關，與別的碼字的信息位無關，通常記分組碼為。

第六頁，共一百六十五頁，2022年，8月28日

其中分組碼又可分循環(huán)碼和非循環(huán)碼：對循環(huán)碼而言，其碼書的特點是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對非循環(huán)碼來說，任一碼字中的碼元循環(huán)移位后不一定再是該碼書中的碼字。卷積碼----把信息序列以每(通常較小)個碼元分段，編碼器輸出該段的監(jiān)督碼元不但與本段的個信息元有關，而且還與其前面L段的信息碼元有關，故記卷積碼為。按照每個碼元的取值來分，可有二元碼和多元碼。由于目前的傳輸或存儲系統(tǒng)大都采用二進制的數(shù)字系統(tǒng)，所以一般提到的糾錯碼都是指二元碼。第七頁，共一百六十五頁，2022年，8月28日綜上所述，糾錯碼分類如圖6.1.1所示。

圖6.1.1糾錯碼的分類

第八頁，共一百六十五頁，2022年，8月28日6.1.2與糾錯編碼有關的基本概念

在通信系統(tǒng)的接收端，若接收到的消息序列和發(fā)送的碼符號序列不一樣，例如，而，與中有兩位不同，即出現(xiàn)兩個錯誤，這種錯誤是由信道中的噪聲干擾所引起的。為了說明如何描述這種錯誤及相應編碼方法的性質(zhì)，我們先介紹一些基本概念。(1)碼長、碼重和碼距碼字中碼元的個數(shù)稱為碼字的長度，簡稱碼長，用表示。碼字中非“0”碼元的個數(shù)稱為碼字的漢明重量(簡稱碼重，記作)。對二進制碼來說，碼重就是碼字中所含碼元“1”的數(shù)目，例如碼字“110000”，其碼長，碼重第九頁，共一百六十五頁，2022年，8月28日兩個等長碼字之間對應碼元不相同的數(shù)目稱為這兩個碼組的漢明距離(簡稱碼距)。例如碼字“110000”與“100001”，它們的漢明距離。在某一碼書中，任意兩個碼字之間漢明距離的最小值稱為該碼的最小距離，即：例如：碼組的最小碼距。從避免碼字受干擾而出錯的角度出發(fā)，總是希望碼字間有盡可能大的距離，因為最小碼距代表著一個碼組中最不利的情況，從安全出發(fā)，應使用最小碼距來分析碼的檢錯、糾錯能力。因此，最小碼距是衡量該碼糾錯能力的依據(jù)，是非常重要的一個參數(shù)。第十頁，共一百六十五頁，2022年，8月28日(2)錯誤圖樣在二元無記憶次擴展信道中，差錯的形式也可以用二元序列來描述。設發(fā)送碼字為，接收碼字為，兩者的差別:

稱為錯誤圖樣。如錯誤圖樣中的第位為“1”()，則表明傳輸過程中第位發(fā)生了錯誤。

例如：，而，則，可知接收的消息序列中的第“2”位和第“6”位出現(xiàn)了錯誤。

第十一頁，共一百六十五頁，2022年，8月28日(3)重復碼和奇偶校驗碼前面已述信道編碼的任務是構造出以最小多余度的代價換取最大抗干擾性的“好“碼。下面，從直觀概念出發(fā)，說明多余度與抗干擾性能的關系，介紹兩種極端情況：一是高可靠性，低有效性的重復碼；二是高有效性，低可靠性的奇偶校驗碼。重復碼

構成重復碼的方法是當發(fā)送某個信源符號時，不是只發(fā)一個，而是連續(xù)重發(fā)多個，連續(xù)重發(fā)的個數(shù)越多，重復碼的抗干擾能力就越強，當然效率也越低。

第十二頁，共一百六十五頁，2022年，8月28日不重復時為(1，1)重復碼，如圖6.1.2所示:圖6.1.2發(fā)送碼元不重復

對這種情況可得結論：不重復，方法簡單，但沒有任何抗干擾能力，既不能發(fā)現(xiàn)，更不能糾正錯誤。重復一次時為(2，1)重復碼，如圖6.1.3所示:圖6.1.3發(fā)送碼元重復一次

第十三頁，共一百六十五頁，2022年，8月28日

對這種情況可得結論：重發(fā)一次，效率降低一倍，可以換取在傳輸過程中允許產(chǎn)生一個錯誤(收端能發(fā)現(xiàn)它)，但不能糾正這個錯誤。重復二次時為(3，1)重復碼，如圖6.1.4所示：圖6.1.4發(fā)送碼元重復二次

(3，1)重復碼用“000”來代表信息“0”，用“111”來代表信息“1”，碼本中共有兩個碼字。

第十四頁，共一百六十五頁，2022年，8月28日顯然，所增加的兩位碼元并不會增加信息，是多余的，因而使信息傳輸率降低。此外，除了傳送信息的“000”和“111”兩種組合之外，還有六種組合{001，010，011，100，101，110}沒有利用。當信道上信噪比足夠大時，我們可以認為碼字中產(chǎn)生的錯誤一般不多于一個碼元，那么，如果接收到“001”、“010”、“100”，我們就可判定實際傳輸?shù)氖恰?00”；同樣，如接收到“011”、“101”、“110”，則可判定為“111”。因此多余碼元使我們可檢出一個錯，并且還可糾正這個錯誤，這樣就提高了信息傳輸?shù)目煽啃?。對這種情況可得結論：重發(fā)二次，效率降低二倍，但換取了可糾正一個差錯或發(fā)現(xiàn)兩個差錯的性能改善。第十五頁，共一百六十五頁，2022年，8月28日2)奇偶檢驗碼

奇偶校驗是一種最基本的校驗方法。構成奇偶檢驗碼的方法是在每個二進制信息位后加上一個奇(偶)監(jiān)督位(或稱校驗位)，使碼長，同時使碼中“1”的個數(shù)恒為奇數(shù)(或偶數(shù))，如圖6.1.5所示。在奇偶校驗碼中，監(jiān)督位，它是一種碼重為奇數(shù)(或偶數(shù))的系統(tǒng)分組碼。圖6.1.5奇偶校驗碼

第十六頁，共一百六十五頁，2022年，8月28日奇偶校驗又可以分為奇校驗和偶校驗。其規(guī)則如下：奇校驗----如果信息碼元中“1”值的個數(shù)為奇數(shù)個，則校驗碼元值為“0”；如果信息碼元中“1”值的個數(shù)為偶數(shù)個，則校驗碼元值為“1”。即所有信息碼元與校驗碼元的模二和等于“1”。

偶校驗----如果信息碼元中“1”值的個數(shù)為偶數(shù)個，則校驗碼元值為“0”；如果信息碼元中“1”值的個數(shù)為奇數(shù)個，則校驗碼元值為“1”。即所有信息碼元與校驗碼元的模二和等于“0”。根據(jù)奇偶校驗的規(guī)則，校驗位值的確定方法如表6.1.1所示。

第十七頁，共一百六十五頁，2022年，8月28日表6.1.1奇偶校驗規(guī)則表

校驗方式信息位中“1”值的個數(shù)校驗位值奇校驗奇數(shù)個0偶數(shù)個1偶校驗偶數(shù)個0奇數(shù)個1第十八頁，共一百六十五頁，2022年，8月28日例如，在七位信息碼中，字符A的代碼為1000001，其中有兩位碼元值為“1”。若采用奇校驗編碼，由于這個字符的七位代碼中有偶數(shù)個“1”，所以校驗位的值應為“l(fā)”，其8位組合代碼為：10000011，前7位是信息位，最右邊的1位是校驗位。同理，若采用偶校驗，可得奇偶校驗位的值為“0”，其8位組合代碼為：10000010。這樣在接收端對碼字中“1”的個數(shù)進行檢驗，如有不符，就可斷定發(fā)生了差錯。在接收端進行校驗時，如采用奇校驗編碼，當接收到的字符經(jīng)檢測其八位代碼“l(fā)”的個數(shù)為奇?zhèn)€數(shù)時，則被認為傳輸正確；否則就被認為傳輸中出現(xiàn)差錯。然而，如果在傳輸中有偶數(shù)位出現(xiàn)差錯，用此方法就檢測不出來了。第十九頁，共一百六十五頁，2022年，8月28日所以，奇偶校驗方式只能檢測出位代碼中出現(xiàn)的任意奇數(shù)個錯誤，如果代碼中錯碼數(shù)為偶數(shù)個，則奇偶校驗不能奏效。由于奇偶校驗碼容易實現(xiàn)，所以當信道干擾不太嚴重以及碼長不很長時很有用，特別是在計算機通信網(wǎng)的數(shù)據(jù)傳送中經(jīng)常應用這種檢錯碼。奇偶校驗編碼如果是在一維空間上進行，則是簡單的“水平奇偶校驗”或“垂直奇偶校驗”碼，如果是在二維空間上進行，則是“水平垂直奇偶校驗碼”。

第二十頁，共一百六十五頁，2022年，8月28日垂直奇偶校驗在垂直奇偶校驗編碼中，先將整個要發(fā)送的信號序列劃分成長度為的若干個組，然后對每組按碼元中“1”的個數(shù)為奇數(shù)或偶數(shù)的規(guī)律，在其后附加上一位奇偶校驗位，如表6.1.2所示。表6.1.2中將70個碼元組成的信號序列劃分成長度為7的10個組，每組按順序一列一列地排列起來，然后對垂直方向的碼元進行奇偶校驗(假設采用偶校驗)，得到一行校驗位，附加在其他各行之后，然后按列的順序進行傳輸。

第二十一頁，共一百六十五頁，2022年，8月28日碼元位分組1234567891011000111001201101000113000101110041000100000500011011016011100100070110101001偶校驗位0111101010表6.1.2垂直奇偶校驗第二十二頁，共一百六十五頁，2022年，8月28日在垂直奇偶校驗編碼和校驗過程中，用硬件方法或軟件方法來實現(xiàn)上述連續(xù)的奇偶校驗運算都非常容易，而且在發(fā)送時可以邊發(fā)送邊產(chǎn)生校驗位，并插入發(fā)送，在接收時邊接收邊進行校驗后去掉校驗位。垂直奇偶校驗方法的編碼效率為：這種奇偶校驗方法能檢測出每個分組中的所有奇數(shù)位的錯，但檢測不出偶數(shù)位的錯。對于突發(fā)性錯誤，由于出錯碼元為奇數(shù)個或偶數(shù)個的概率各占一半，因而對差錯的漏檢率接近于1/2。

第二十三頁，共一百六十五頁，2022年，8月28日水平奇偶校驗為了降低對突發(fā)錯誤的漏檢率，可以采用“水平奇偶校驗”，它是以分組為單位，對一組中的相同位的碼元進行奇偶校驗。在水平奇偶校驗中，把信號序列先以適當?shù)拈L度劃分成個組，每組位碼元，并把每組按順序一列一列地排列起來，如表6.1.3所示第二十四頁，共一百六十五頁，2022年，8月28日碼元位分組偶校驗位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011

水平奇偶校驗第二十五頁，共一百六十五頁，2022年，8月28日水平奇偶校驗的編碼效率是：水平奇偶校驗不但可以檢測各組同一位上的奇數(shù)位錯，而且可以檢測出突發(fā)長度小于或等于(每組的碼元數(shù))的所有突發(fā)性錯誤(突發(fā)性錯誤是指一連串的碼元均出錯)，因為傳輸時按組的順序發(fā)送，發(fā)生長度小于或等于的突發(fā)性錯誤必然分布在不同行中，每行最多只有一位出錯，所以可以檢出差錯。水平奇偶校驗的漏檢率比垂直奇偶校驗碼要低。但是，在實現(xiàn)水平奇偶校驗時，不論采用硬件方法還是軟件方法，都不能在發(fā)送過程中邊產(chǎn)生邊插入奇偶校驗位，而必須等待要發(fā)送的完整數(shù)據(jù)信號序列到齊后，才能確定校驗位，也就是要使用一定的存儲空間。因此，其編碼和檢測的實現(xiàn)都要復雜一些。第二十六頁，共一百六十五頁，2022年，8月28日水平垂直奇偶校驗同時進行水平奇偶校驗和垂直奇偶校驗就構成二維的“水平垂直奇偶校驗碼”，如表6.1.4所示。其具體實現(xiàn)過程是：先將整個欲發(fā)送的信號序列劃分成長度為的若干個組；然后對每個組按碼元中“1”的個數(shù)為奇或偶數(shù)的規(guī)律，在其后附加上一位奇偶校驗位(表中采用偶校驗)；再對每個字符的相同位按“1”的個數(shù)為奇或偶數(shù)的規(guī)律，增加一個校驗位(表中采用偶校驗)。第二十七頁，共一百六十五頁，2022年，8月28日碼元位分組偶校驗位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011偶校驗位01111010100

水平垂直奇偶校驗第二十八頁，共一百六十五頁，2022年，8月28日水平垂直奇偶校驗的編碼效率為：這種方法能檢測出所有3位或3位以下的錯誤，因為在這種情況下，至少會在某一行或某一列上出現(xiàn)一位錯，這時錯誤就能被檢測到；還能檢測出奇數(shù)位錯、突發(fā)長度小于或等于的突發(fā)性錯以及很大一部分偶數(shù)位錯。一些試驗測量表明，這種方式的編碼可使誤碼率降至原始誤碼率的百分之一到萬分之一。另外，水平垂直奇偶校驗不僅可檢錯，還可用來糾正部分差錯。上述奇偶校驗碼中，水平奇偶校驗碼、垂直奇偶校驗碼是單純檢錯碼，而水平垂直奇偶校驗碼則還具有有限的糾錯能力，但多數(shù)情況下只用于檢錯。第二十九頁，共一百六十五頁，2022年，8月28日6.1.3檢錯與糾錯原理

檢錯、糾錯的目的是要根據(jù)信道接收端接收到的信息序列來判斷是否就是發(fā)送的序列，如果有錯則盡可能糾正其中的錯誤。要糾正傳輸差錯，首先必須檢測出錯誤。而要檢測出錯誤，常用的方法是將發(fā)送端要傳送的信息序列(常為二進制序列)中截取出長度相等的碼元進行分組，每組長度為k，組成k位碼元信息序列，并根據(jù)某種編碼算法以一定的規(guī)則在每個信息組的后面產(chǎn)生個冗余碼元，由冗余碼元和信息碼元一起形成“位編碼序列”，即信號碼字，位的碼字比信息碼長(有個碼元)，因而糾錯編碼是冗余編碼，如圖6.1.6所示。第三十頁，共一百六十五頁，2022年，8月28日圖6.1.6糾錯編碼

譯碼就是利用校驗關系進行檢錯、糾錯的，在接收端收到的位碼字中，信息碼元與冗余碼元之間也應符合上述編碼規(guī)則，并根據(jù)這一規(guī)則進行檢驗，從而確定是否有錯誤。這就是差錯控制的基本思想。我們把這種將信息碼元分組，為每組碼附加若干校驗碼的編碼稱為分組碼。在分組碼中，校驗碼元僅校驗本碼組中的信息碼元。分組碼一般用符號表示，其中是每組二進制信息碼元的數(shù)目，是編碼組的長度(簡稱碼長)，即編碼組的總位數(shù)，為每碼組中的校驗碼元(或稱監(jiān)督位)數(shù)目。第三十一頁，共一百六十五頁，2022年，8月28日通常，將分組碼規(guī)定為具有如圖6.1.7所示的結構。圖中前面位()為信息位，后面附加個()校驗位。圖6.1.7分組碼的結構

實現(xiàn)檢糾錯常用的基本方法除了前面介紹的重復碼方法和奇偶校驗方法外，還有等重碼(或定比碼)方法：奇偶校驗方法。增加偶(或奇)校驗位使得對消息序列而言校驗方程成立，當校驗位數(shù)增加時，可以檢測到差錯圖樣的種類數(shù)也增加，但同時碼率減小。

第三十二頁，共一百六十五頁，2022年，8月28日

重復碼方法。重復消息位使之可以檢測出任意小于個差錯的錯誤圖樣。等重碼方法。設計碼字中的非“0”符號個數(shù)(若是二進制碼則為“1”的個數(shù))恒為常數(shù)，使碼書由全體重量恒等的長矢量組成。表6.1.5所示為一種用于表示數(shù)字“0”到“9”的五中取三等重碼(所有碼字的碼重都等于“3”)的例子。表6.1.5五中取三等重碼

顯然五中取三等重碼可以檢測出全部奇數(shù)位差錯，對某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯。123456789001011110011011011010001111010111100011101001101101第三十三頁，共一百六十五頁，2022年，8月28日對于糾錯碼，其抗干擾能力完全取決于碼書C中許用碼字之間的距離。碼的最小距離越大，則碼字間的最小差別越大，抗干擾能力就越強，即受較強的干擾仍不會造成許用碼字之間的混淆。差錯控制編碼是用增加碼元數(shù)，利用“冗余”來提高抗干擾能力的，即是以降低信息傳輸速率為代價來減少錯誤的，或者說是用削弱有效性來增強可靠性的。第三十四頁，共一百六十五頁，2022年，8月28日6.1.4檢錯與糾錯方式和能力

檢錯與糾錯方式自動請求重發(fā)方式----用于檢錯的糾錯碼在譯碼器輸出端給出當前碼字傳輸是否可能出錯的指示，當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的全部或部分碼字，這種糾錯碼的應用方式稱為自動請求重發(fā)方式(ARQ，Automatic-Repeat-reQuest)。前向糾錯方式----用于糾錯的糾錯碼在譯碼器輸出端總要輸出一個碼字或是否出錯的標志，這種糾錯碼的應用方式稱為前向糾錯方式(FEC，F(xiàn)orward-errorcontrol)。另外用于檢錯與糾錯的方式還有混合糾錯(HEC，HybridErrorCorrection)。圖6.1.8所示為上述幾種檢錯與糾錯方式示意圖，圖中有斜線的方框表示在該端檢出錯誤。

第三十五頁，共一百六十五頁，2022年，8月28日圖6.1.8差錯控制的工作方式

ARQ方式：發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進行差錯編碼，通過正向信道送到接收端，而接收端經(jīng)譯碼器處理后只是檢測有無差錯，不作自動糾正。如檢測到差錯，則利用反向信道反饋信號，請求發(fā)送端重發(fā)有錯的數(shù)據(jù)單元，直到接收端檢測不到差錯為止。第三十六頁，共一百六十五頁，2022年，8月28日FEC方式：發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進行差錯編碼，在接收端用譯碼器對接收到的數(shù)據(jù)進行譯碼后檢測有無差錯，通過按預定規(guī)則的運算，如檢測到差錯，則確定差錯的具體位置和性質(zhì)，自動加以糾正，故稱為“前向糾錯”。HEC方式：是檢錯重發(fā)和前向糾錯兩種方式的混合。發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進行便于檢錯和糾錯的編碼，通過正向信道送到接收端，接收端對少量的接收差錯進行自動前向糾正，而對超出糾正能力的差錯則通過反饋重發(fā)方式加以糾正，所以是一種糾檢結合的混合方式。(2)檢錯與糾錯能力一個糾錯碼的每個碼字都可以形成一個漢明球，因此要能夠糾正所有不多于位的差錯，糾錯碼的所有漢明球均應不相交，判定糾錯碼的檢、糾錯能力可根據(jù)任意兩個漢明球不相交的要求，由碼的最小距離來決定。第三十七頁，共一百六十五頁，2022年，8月28日

若糾錯碼的最小距離為，那么如下三個結論的任何一個結論獨立成立：①若要發(fā)現(xiàn)個獨立差錯，則要求最小碼距；②若要糾正個獨立差錯，則要求最小碼距；③若要求發(fā)現(xiàn)個同時又糾正個獨立差錯，則；這里說的“同時”是指在譯碼過程中，若錯誤個數(shù)≤，則能糾正；若錯誤個數(shù)＞，但≤，則能檢測這些錯誤，但不能糾正。或者說能檢測個錯誤，其中個錯誤可以糾正。其直觀的關系如圖6.1.9所示。第三十八頁，共一百六十五頁，2022年，8月28日(a)糾錯能力的幾何說明(b)檢錯能力的幾何說明(c)區(qū)分糾錯和檢錯的示意圖(d)檢錯、糾錯能力與最小碼距的關系圖6.1.9最小碼距與檢錯、糾錯能力第三十九頁，共一百六十五頁，2022年，8月28日圖6.1.9(c)中，粗線球面(圓)是糾正個錯誤的球面，細線球面(圓)代表檢出個錯誤的球面。當接收碼字中不包含錯誤或錯誤，將落在粗線球內(nèi)或球上，因而可把糾正為原發(fā)送的碼字，當接收碼字包含個而個錯誤時，不會落在任何碼字的糾錯球內(nèi)，但此時代表糾錯范圍的粗線球面與另一碼字的代表檢錯范圍的細線球面沒有相交或相切，于是可將糾錯和檢錯區(qū)分開來。

當碼的最小碼距為3或4時，可以糾正所有1位錯。當碼的最小碼距為5時，可以糾正所有2位錯。當碼的最小碼距為時，可以糾正所有位錯。

第四十頁，共一百六十五頁，2022年，8月28日定理6.1.1說明，碼的最小距離越大，碼的糾(檢)錯誤的能力越強。但是，隨著多余碼元的增多，信息傳輸速率會降低得越多。通常用來表示碼字中信息碼元所占的比例，稱為編碼效率，簡稱碼率，它是衡量碼性能的又一個重要參數(shù)。碼率越高，信息傳輸率就越高，但此時糾錯能力要降低，若時就沒有糾錯能力了?？梢姡a率與糾錯能力之間是有矛盾的。第四十一頁，共一百六十五頁，2022年，8月28日6.2線性分組碼

線性分組碼是糾錯碼中非常重要的一類碼，雖然對于同樣碼長的非線性碼來說線性碼可用碼字較少，但由于線性碼的編碼和譯碼容易實現(xiàn)，而且是討論其他各類碼的基礎，至今仍是廣泛應用的一類碼。第四十二頁，共一百六十五頁，2022年，8月28日6.2.1線性分組碼的基本概念

定義6.2.1對信源編碼器輸出的進制序列進行分組，設分組長度為，相應的碼字表示為：

其中：每個碼元都是進制的，顯然這樣的碼字共有個。信道編碼(糾錯編碼)的目的是將信息碼字進行變換，使其成為以下形式：

其中：，為進制數(shù)，顯然這樣的碼字共有個。我們稱全體碼字的集合為元分組碼。若由到之間的變換為線性變換，則稱全體碼字的集合為元線性分組碼，常用線性分組碼來表示全體碼字的集合。第四十三頁，共一百六十五頁，2022年，8月28日例6.2.1設將信源編碼器輸出的二進制序列進行分組，分組長度為，相應的碼字表示為：，這里是二進制的，即。這樣的碼字共有兩個，即“1”和“0”。現(xiàn)將進行變換，變換規(guī)則為：

因此，形成的糾錯碼具有以下形式：。由于只取“0”或“l(fā)”，所以的全體碼字只有兩個：長為的全“0”或全“l(fā)”序列。即經(jīng)過上述變換，得到了重復碼。

第四十四頁，共一百六十五頁，2022年，8月28日例6.2.2設信源編碼器輸出的信息序列為，其中：是二進制數(shù)。信道編碼器輸出的碼字為，其中：也是二進制數(shù)。若從到的變換規(guī)則為：由于從到的變換是一種線性變換，所以全體的集合構成了—種線性分組碼。

第四十五頁，共一百六十五頁，2022年，8月28日由本例可以看出，變換后碼字集合中每一個碼字的所有碼元之和為：因為假設了碼為二進制碼，上述碼元的和是模2和。因此，變換后將每一個碼字的碼元全部加起來，它的模2和為“0”，即每一個碼字中“1”的個數(shù)為偶數(shù)個，所以這種碼為偶校驗碼。第四十六頁，共一百六十五頁，2022年，8月28日例6.2.3分組碼，按以下的規(guī)則(校驗方程)可得到四個校驗元：式中：是三個信息碼元，方程中的加運算均為模2加。由此可得到分組碼的八個碼字。八個信源序列與八個碼字的對應關系列于表6.2.1中。由校驗方程看到，信息碼元與校驗碼元滿足線性關系，因此該碼是線性碼。

第四十七頁，共一百六十五頁，2022年，8月28日表6.2.1例6.2.3編出的線性碼的碼字與信息碼元的對應關系信息碼元碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100第四十八頁，共一百六十五頁，2022年，8月28日對于線性分組碼有一個非常重要的結論：一個線性分組碼中非零碼字的最小重量等于該碼的最小距離。

[證明]設有任意兩個碼字。根據(jù)線性分組碼的性質(zhì)，有。而的碼重等于的碼距。即：

而是C中任意兩個非全零碼字，所以：

[證畢]

由例6.2.3線性碼的八個碼字可見，除全零碼字外，其余七個碼字最小重量，所以該線性碼的最小距離。

第四十九頁，共一百六十五頁，2022年，8月28日6.2.2生成矩陣和一致校驗矩陣

從矢量空間的角度，形形色色的編碼方法實質(zhì)上是采用了不同的基底選擇方法及矢量映射規(guī)則而形成的?；椎倪x擇與映射規(guī)則均可用矩陣來表示，因此在線性分組碼的討論中就有了生成矩陣和一致校驗矩陣的概念。生成矩陣在討論生成矩陣之前，我們再看例6.2.3的線性分組碼。該碼所滿足的校驗方程可寫成矩陣形式：式中稱線性分組碼的生成矩陣。

第五十頁，共一百六十五頁，2022年，8月28日定義6.2.2若信息組以不變的形式，在碼字的任意位中出現(xiàn)，則該碼稱為系統(tǒng)碼。否則，稱為非系統(tǒng)碼。目前常用的有兩種形式的系統(tǒng)碼：一種是把信息組排在碼字的最左邊位：，式(6.2.2)就是這種形式，若非特別說明，我們后面所說的系統(tǒng)碼均指這種形式。

另一種是把信息組安置在碼字的最右邊位：。第五十一頁，共一百六十五頁，2022年，8月28日能夠產(chǎn)生系統(tǒng)碼的生成矩陣為典型矩陣(或稱標準陣)，典型矩陣的最大優(yōu)勢是便于檢查生成矩陣的各行是否是線性無關。如果不具有標準型，雖能產(chǎn)生線性碼，但碼字不具備系統(tǒng)碼的結構，因而存在難以區(qū)分碼字中信息碼元和監(jiān)督碼元的缺點。由于系統(tǒng)碼的編碼與譯碼較非系統(tǒng)碼簡單，而且對分組碼來說，系統(tǒng)碼與非系統(tǒng)碼的抗干擾能力是等價的，故若無特別聲明，我們僅討論系統(tǒng)碼。如果生成矩陣為非標準型的，可經(jīng)過行初等變換變成標準型。第五十二頁，共一百六十五頁，2022年，8月28日(2)一致校驗矩陣

從前面的討論我們知道，編碼問題就是在給定的下如何從已知的個信息碼元求得個校驗碼元。一般可寫成：

或

式(6.2.3)表明，中各碼元是滿足由矩陣所確定的個線性方程的解，故是碼書中的一個碼字，由的全體就構成了碼書；反之，若某碼元序列滿足由所確定的個線性方程，則該碼元序列一定是碼書中的一個碼字。

第五十三頁，共一百六十五頁，2022年，8月28日因此，一定，便可由信息碼元求出校驗碼元，編碼問題就迎刃而解；或者說，要解決編碼問題，只要找到即可。由于碼的所有碼字均按所確定的規(guī)則求出，故稱為其一致校驗矩陣。綜上所述，我們將矩陣的特點歸納如下：

①矩陣的每一行代表一個線性方程的系數(shù)，它對應求一個校驗碼元的線性方程。②矩陣每一列代表此碼元與哪幾個校驗方程有關。③由該矩陣得到的分組碼的每一碼字都必須滿足由矩陣的行所確定的線性方程，即式(6.2.3)或式(6.2.4)。第五十四頁，共一百六十五頁，2022年，8月28日碼需有個校驗碼元，故需有個獨立的線性方程。因此，矩陣必須有行，且各行之間線性無關，即矩陣的秩為。⑤由于生成矩陣中的每一行及其線性組合都是碼中的一個碼字，故有：或

⑥由例6.2.3不難看出，碼的矩陣右邊為一個四階單位矩陣。通常，系統(tǒng)型線性分組碼的矩陣右邊列組成一個單位矩陣，故有：

式中是一個階矩陣。我們稱這種形式的矩陣為典型矩陣(或標準矩陣)，同樣，采用典型矩陣形式的矩陣更易于檢查各行是否線性無關。

第五十五頁，共一百六十五頁，2022年，8月28日⑦由式(6.2.5)易得：

由此關系可知

或

這說明，的第一行就是的第一列，的第二行就是的第二列，……，因此，矩陣一旦確定，則矩陣也就確定，反之亦然。第五十六頁，共一百六十五頁，2022年，8月28日(3)線性分組碼的編碼

線性分組碼的編碼就是根據(jù)一致校驗矩陣或生成矩陣將長度為的信息碼元變換成長度為的碼字。這里以線性分組碼為例來說明構造編碼電路的方法。

設二元碼字為，碼的一致校驗矩陣為：由得：

第五十七頁，共一百六十五頁，2022年，8月28日按照該線性方程組，可直接畫出線性分組碼的并行編碼電路和串行編碼電路，如圖6.2.1所示。

(a)并行編碼電路(b)串行編碼電路圖6.2.1線性分組碼編碼電路原理圖第五十八頁，共一百六十五頁，2022年，8月28日(4)對偶碼和縮短碼我們已經(jīng)討論了線性分組碼的生成矩陣與其對應的一致校驗矩陣，如果把碼的一致校驗矩陣看成是碼的生成矩陣，將碼的生成矩陣看成是碼的一致校驗矩陣，則稱這兩種碼互為對偶碼。

例6.2.6求例6.2.3所述碼的對偶碼。顯然，碼的對偶碼應是碼，由對偶碼的定義得，碼的矩陣就是碼的矩陣，將其化成標準形式后即可按式(6.2.1)得到碼的對偶碼碼，如表6.2.2所示。第五十九頁，共一百六十五頁，2022年，8月28日表6.2.2例6.2.3線性碼的對偶碼

信息碼元碼字信息碼元碼字00000000000100010001010001000101110011001110001000101101010101001100110011101101110110000100010011111001100010010101011001101110100101100110001111011101000111011101011111111111第六十頁，共一百六十五頁，2022年，8月28日

在有些情況下，如果對某一給定長度的信息碼元找不到合適碼長的碼，則可將某一碼縮短以滿足要求。例如，在線性分組碼的碼字集合中將最左邊一位為“0”的消息和對應的碼字選出來，并把消息中最左邊的“0”去掉，則可構成線性分組碼，這種碼稱為縮短碼。如表6.2.3所示。表6.2.3例6.2.3線性碼的縮短碼信息碼元碼字00000000010111011010011111111010第六十一頁，共一百六十五頁，2022年，8月28日6.2.3線性分組碼的譯碼

只要找到矩陣或矩陣，便解決了編碼問題。經(jīng)編碼后發(fā)送的碼字，由于信道干擾可能出錯，接收方怎樣發(fā)現(xiàn)或糾正錯誤呢，這就是譯碼要解決的問題。

定義6.2.3設碼的一致校驗矩陣為，是發(fā)送碼字為時的接收序列，則稱：為接收序列的伴隨式或校正子。伴隨式是一致校驗矩陣的線性組合，如果錯誤圖樣中有一些分量不為“0”，則在中正好就是中不為“0”的那幾列組合而成。由于是維的列向量，所以伴隨式也是一個維向量。第六十二頁，共一百六十五頁，2022年，8月28日由上面的分析，可得如下結論：①從式(6.2.7)可知伴隨式僅與錯誤圖樣有關，它充分反映了信道受干擾的情況，而與發(fā)送的是什么碼字無關。②伴隨式是是否有錯的判別式，若，則判沒有出錯；若，則判有錯。③不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的，對二元碼來說，伴隨式即為矩陣中與錯誤圖樣對應的各列之和。注意，如果錯誤圖樣本身就是一個碼字，即碼，那么計算伴隨式得到的結果必為“”，此時的錯誤不能發(fā)現(xiàn)，也無法糾正，因而這樣的錯誤圖樣稱為不可檢錯誤圖樣。

第六十三頁，共一百六十五頁，2022年，8月28日例6.2.7計算例6.2.3所述碼接收時的伴隨式。

解：碼的一致校驗矩陣為：

當接收時，接收端譯碼器根據(jù)接收序列計算的伴隨式為：第六十四頁，共一百六十五頁，2022年，8月28日

因此，譯碼器判別接收序列無錯，傳輸中沒有發(fā)生錯誤。

當接收時，接收端譯碼器根據(jù)接收序列計算的伴隨式為:由于，所以譯碼器判別接收序列有錯，傳輸中有錯誤發(fā)生。碼是糾正單個錯誤的碼，觀察即為的第二行，因此可判定接收序列的第二位發(fā)生了錯誤。由于接收序列中錯誤個數(shù)與碼的糾錯能力相符，所以可正確譯碼，即發(fā)送碼字應為。第六十五頁，共一百六十五頁，2022年，8月28日當接收時，接收端譯碼器根據(jù)接收序列計算的伴隨式為：，但與的任何一列都不相同，無法判別錯誤發(fā)生在哪些位上，此時只能發(fā)現(xiàn)有錯。伴隨式的計算可用電路來實現(xiàn)，如前所述的碼，設接收序列，則伴隨式為：

第六十六頁，共一百六十五頁，2022年，8月28日根據(jù)上式，可畫出碼的伴隨式計算電路，如圖6.2.3所示。圖6.2.3碼的伴隨式計算電路

第六十七頁，共一百六十五頁，2022年，8月28日6.2.4線性分組碼的糾錯能力

由前面的介紹可知，線性分組碼的糾錯能力和碼字的最小距離有關，一般是在設計通信系統(tǒng)時提出的，那么尋找滿足糾正個錯誤碼元的碼字就是編碼技術的任務，為此我們還需進一步研究和碼字結構的關系。線性分組碼碼字的結構是由生成矩陣(或一致校驗矩陣)決定的，若巳知矩陣，該碼的結構也就知道了，實際上所謂校驗就是利用矩陣去鑒別接收矢量的結構。那么從研究碼的糾錯能力角度來看與有什么關系呢？定理6.2.1線性分組碼最小碼距等于的充要條件是矩陣中任何列線性無關。第六十八頁，共一百六十五頁，2022年，8月28日定理6.1.2是構造任何類型線性分組碼的基礎，由定理可得出以下三個結論：①為了構造最小距離(可檢測個錯誤)或(可糾正個錯誤)的線性分組碼，其充要條件是要求矩陣中任意列線性無關。例如，要構造最小距離為3的碼，則要求矩陣中任意2列線性無關。對于二元碼，即要求矩陣滿足無相同的列和無全“0”的列，就可糾正所有單個錯誤。②因為交換矩陣的各列不會影響碼的最小距離，因此所有列向量相同但排列位置不同的矩陣所對應的分組碼，其糾錯能力和碼率是等價的。③任一線性分組碼的最小距離(或最小重量)均滿足。第六十九頁，共一百六十五頁，2022年，8月28日滿足的線性分組碼稱為極大最小距離碼。在同樣的之下，由于最大，因此糾錯能力更強，所以設計這種碼，是編碼理論中人們感興趣的一個課題。根據(jù)定理6.2.1，我們可以由矩陣的列的相關性直接知道碼的糾錯、檢錯能力。在巳知信息位的條件下，如何去確定監(jiān)督位的位數(shù)(即確定碼長)，才能滿足對糾錯能力的要求？對此有下述結論：

若是二元碼，當巳知時，要使能糾正個錯，則必須有不少于個校驗位，并且使?jié)M足：

第七十頁，共一百六十五頁，2022年，8月28日式中的為中取的組合。滿足時的碼稱為完備碼，這種碼的校驗元得到了最充分的利用。式(6.2.9)又稱為漢明不等式。

第七十一頁，共一百六十五頁，2022年，8月28日6.2.5漢明碼

漢明碼是漢明(Hamming)于1950年提出的能糾正一位錯的特殊的線性分組碼。漢明碼有許多很好的性質(zhì)，是一種完備碼，它可以用一種簡潔有效的方法進行譯碼。由于它的編、譯碼較簡單，且較容易實現(xiàn)，因此被廣泛采用，尤其是在計算機存儲與運算系統(tǒng)中被廣泛應用。漢明碼的參數(shù)對于任意正整數(shù)，存在具有下列參數(shù)的二進制漢明碼：碼長：信息位數(shù)：監(jiān)督位數(shù)：最小碼距：第七十二頁，共一百六十五頁，2022年，8月28日給定后，即可構造出具體的漢明碼，這可以從建立—致校驗矩陣入手。我們知道，矩陣的列數(shù)就是碼長，行數(shù)等于。例如，可算出，因而是(7，4)線性碼。其矩陣正是用個非零三維列向量構成的。如：此時，矩陣的列所對應的十進制數(shù)正好是“1”“7”，對于糾一位差錯來說，其伴隨式的值就等于對應的矩陣的列矢量，即錯誤位置。所以這種形式的矩陣構成的碼很便于糾錯，但這是非系統(tǒng)的(7，4)漢明碼的一致校驗矩陣。如果要得到系統(tǒng)碼，可調(diào)整各列次序來實現(xiàn)：第七十三頁，共一百六十五頁，2022年，8月28日有了，就可得到系統(tǒng)碼的校驗位，其相應的生成矩陣為：設碼字，根據(jù)(或)及關系式，有：

(7，4)漢明碼的編碼電路原理圖如圖6.2.4所示。第七十四頁，共一百六十五頁，2022年，8月28日漢明碼的譯碼，可以采用計算伴隨式，然后確定錯誤圖樣并加以糾正的方法。圖6.2.5所示為(7，4)漢明碼的譯碼電路原理圖。需要注意的是(7，4)漢明碼的矩陣并非只有以上兩種。原則上講，漢明碼的一致校驗矩陣有列行，它的列由除了全“0”以外的位碼組構成，每個碼組只在某列中出現(xiàn)一次，矩陣中各列的次序是可任意改變。另外，對照完備碼的定義可知，漢明碼實際上是的完備碼。第七十五頁，共一百六十五頁，2022年，8月28日圖6.2.5(7，4)漢明譯碼器電路原理圖第七十六頁，共一百六十五頁，2022年，8月28日6.3循環(huán)碼循環(huán)碼是一種特殊的線性分組碼，屬于線性分組碼的一個重要子類，也是目前研究最為透徹的一類碼，大多數(shù)有實用價值的糾錯碼都是循環(huán)碼。循環(huán)碼與一般的線性分組碼相比具有以下優(yōu)點：循環(huán)碼的編碼及譯碼易于用簡單的具有反饋連接的移位寄存器來實現(xiàn)。定義6.3.1設有線性分組碼，如果它的任意一個碼字的每一次循環(huán)移位仍然是中的一個碼字，則稱為循環(huán)碼。也即，如果是循環(huán)碼的一個碼字，那么等也都是的碼字時，則所有這些具有循環(huán)特性的碼字的全體便構成了循環(huán)碼。第七十七頁，共一百六十五頁，2022年，8月28日例如在例6.2.3中的線性分組碼就是循環(huán)碼，該碼如表6.3.1所示。由表可以看到，在右邊的碼字欄內(nèi)，任意一個碼字將其循環(huán)移位后，其結果仍然是該欄內(nèi)的一個碼字。例如將第二行的碼字循環(huán)右移一位后可得到第五行的碼字，第五行的碼字循環(huán)右移一位后得到第三行的碼字等。實際上右移和左移具有同樣的效果。循環(huán)碼的主要特點是：①理論成熟：可利用成熟的代數(shù)結構深入探討其性質(zhì)；②實現(xiàn)簡單：可利用循環(huán)移位特性在工程上進行編、譯碼；第七十八頁，共一百六十五頁，2022年，8月28日③循環(huán)碼的描述方式有很多，但在工程上最有用的是采用多項式的描述方法。由于循環(huán)碼的以上特點，可以將其用多項式來表示，從而可以借助代數(shù)的工具對循環(huán)碼進行分析，這也是循環(huán)碼能被廣泛應用的原因之一。信息碼元碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100第七十九頁，共一百六十五頁，2022年，8月28日6.3.1循環(huán)碼的多項式描述

設有循環(huán)碼字，則可以用一個次數(shù)不超過的多項式惟一確定，其相應的多項式可表示為：(6.3.1)

即碼字與碼多項式一一對應。

由循環(huán)碼的特性可知，若是循環(huán)碼的一個碼字，則也是該循環(huán)碼的一個碼字，它的碼多項式為：

(6.3.2)

比較式(6.3.1)和式(6.3.2)，得：第八十頁，共一百六十五頁，2022年，8月28日

該式說明，碼字循環(huán)一次的碼多項式是原碼多項式乘后再除以所得的余式，即：

由此可以推知，的次循環(huán)移位是原碼多項式乘后再除以所得的余式，即：(6.3.3)

式(6.3.3)揭示了線性碼中碼多項式與碼字循環(huán)移位之間的關系，它對循環(huán)碼的研究起著重要的作用。

第八十一頁，共一百六十五頁，2022年，8月28日例如前面所述循環(huán)碼可由任一個碼字(如“0011101”)經(jīng)循環(huán)移位后，得到其他6個碼字；也可由相應的碼多項式乘以后，再模得到其他6個非零碼多項式。這個移位過程及相應的多項式運算如表6.3.2所示。第八十二頁，共一百六十五頁，2022年，8月28日表6.3.2循環(huán)碼的循環(huán)移位循環(huán)次數(shù)碼字碼多項式000000000011101101110102111010031101001410100115010011161001110第八十三頁，共一百六十五頁，2022年，8月28日6.3.2循環(huán)碼的生成矩陣

根據(jù)循環(huán)碼的循環(huán)特性，可由一個碼字的循環(huán)移位得到其他非“0”碼字。在循環(huán)碼的碼多項式中，每一個能整除的次首一多項式(其最高次項系數(shù)為“l(fā)”)都是該碼的生成多項式，記為。將經(jīng)過次循環(huán)移位，共得到個碼多項式：、、…、。這個碼多項式顯然是相互獨立的，可作為碼生成矩陣的行，于是得到循環(huán)碼的生成矩陣：

(6.3.4)

第八十四頁，共一百六十五頁，2022年，8月28日碼的生成矩陣一旦確定，碼也就確定了。這說明循環(huán)碼可由它的一個次首一多項式來確定，所以可以說由生成了循環(huán)碼，因此稱為碼的生成多項式，即：

(6.3.5)如果某一個碼具有生成多項式，則該碼一定是循環(huán)碼。碼的生成多項式具有如下性質(zhì)：①在循環(huán)碼中，次碼多項式是最低次的碼多項式。②在循環(huán)碼中，是惟一的次多項式。③在循環(huán)碼中，每個碼多項式都是的倍式。④任意循環(huán)碼的生成多項式一定整除。

第八十五頁，共一百六十五頁，2022年，8月28日例6.3.2求二進制循環(huán)碼的生成多項式。解：分解多項式，取其四次首一多項式作為生成多項式：可將一次和任一個三次多項式的乘積作為生成多項式：或由于線性碼的生成矩陣與一致校驗矩陣滿足關系：，而循環(huán)碼也是線性碼，如果設為循環(huán)碼的生成多項式，它必為的因式，則有：(6.3.6)第八十六頁，共一百六十五頁，2022年，8月28日因為是次多項式，以為生成多項式，則生成一個循環(huán)碼，以為生成多項式，則生成一個循環(huán)碼，這兩個循環(huán)碼互為對偶碼。稱為循環(huán)碼的校驗多項式，且：(6.3.7)顯然，循環(huán)碼也可由其校驗多項式完全確定，循環(huán)碼的一致校驗矩陣為(6.3.8)

第八十七頁，共一百六十五頁，2022年，8月28日式中為的反多項式：

第八十八頁，共一百六十五頁，2022年，8月28日例6.3.3以二進制碼碼為例，說明循環(huán)碼可由生成多項式或校驗多項式完全確定。

由多項式的因式分解知：其四次多項式為生成多項式：其三次多項式為校驗多項式：由等式，兩端的同次系數(shù)應相等，得：

第八十九頁，共一百六十五頁，2022年，8月28日

的系數(shù)的系數(shù)的系數(shù)的系數(shù)將上述方程組寫成矩陣形式：第九十頁，共一百六十五頁，2022年，8月28日上式中列矩陣的元素就是生成多項式的系數(shù)，它本身是一個碼字，那么第一個矩陣即為循環(huán)碼的一致校驗矩陣，即：可見，一致校驗矩陣的第一行是碼的校驗多項式的系數(shù)的反序排列，而第二、三、四行分別是第一行的移位，由此得到用校驗多項式的系數(shù)來構成的一致校驗矩陣：第九十一頁，共一百六十五頁，2022年，8月28日由上分析可得以下結論：給定了循環(huán)碼的生成多項式，可以求得相應的生成矩陣，由又可以確定校驗多項式，并可由確定循環(huán)碼的一致校驗矩陣。生成多項式與生成矩陣的含義是相同的，前者對應于循環(huán)碼的多項式表示方式，而后者對應于循環(huán)碼的矩陣表示方式，兩者之間可以相互轉換。第九十二頁，共一百六十五頁，2022年，8月28日6.3.3系統(tǒng)循環(huán)碼

前面介紹的生成矩陣所產(chǎn)生循環(huán)碼不是系統(tǒng)碼。我們可以通過矩陣的行運算，得到系統(tǒng)循環(huán)碼的生成矩陣，使之具有的形式，生成矩陣的行運算實質(zhì)上就是碼字間個基底間進行線性組合運算。系統(tǒng)循環(huán)碼的生成矩陣的一致校驗矩陣是。例6.3.4以為生成多項式生成一個循環(huán)碼，要求生成的循環(huán)碼是系統(tǒng)的。解：由例6.3.1得對應給定的循環(huán)碼的一般生成矩陣為：第九十三頁，共一百六十五頁，2022年，8月28日

對矩陣的行進行運算，將第⑴、⑶、⑷行相加后作為第1行，第⑵、⑷行相加后作為第2行，得：對應：這樣，就得到系統(tǒng)循環(huán)碼的生成矩陣和一致校驗矩陣。第九十四頁，共一百六十五頁，2022年，8月28日6.3.4多項式運算電路

由于多項式表示的是時間序列，因而多項式的運算表現(xiàn)為對時間序列的操作。

設有多項式和，則：

與的相加電路如圖6.3.1所示。若的階數(shù)小于的階數(shù)，則將也擴充為次多項式，其擴充的冪次項系數(shù)為“0”。圖6.3.1多項式相加第九十五頁，共一百六十五頁，2022年，8月28日多項式的乘法電路如圖6.3.2所示，按照圖6.3.2的乘法電路構成，與乘法的—般電路如圖6.3.3所示。在乘法電路中總假設多項式的低位在前，電路中的所有寄存器初態(tài)為“0”。圖6.3.2多項式乘法電路例第九十六頁，共一百六十五頁，2022年，8月28日圖6.3.3多項式乘法電路

設，，則用多項式去除任意多項式的電路即為除法電路，如圖6.3.4所示。移位寄存器的初始狀態(tài)全為“0”，當輸入完畢，移位寄存器()中的內(nèi)容即為余式。圖6.3.4除法電路第九十七頁，共一百六十五頁，2022年，8月28日例6.3.5設被除式與除式都是系數(shù)為二進制的多項式，且：

則完成除以的電路如圖6.3.5所示。完成上述二個多項式相除的算式如下：這里商為，余式為，表6.3.3給出了圖6.3.5電路的運算過程，經(jīng)過次移位后得到商項的系數(shù)，=5次移位后，完成了整個除法運算，在移位寄存器中保存的數(shù)(001)代表余式的系數(shù)。第九十八頁，共一百六十五頁，2022年，8月28日1100111節(jié)拍輸入移位寄存器的內(nèi)容輸出000000111000211100300110401111510011余式商式表6.3.3例6.3.5的運算過程表第九十九頁，共一百六十五頁，2022年，8月28日圖6.3.5例6.3.5的除法電路

第一百頁，共一百六十五頁，2022年，8月28日6.3.5循環(huán)碼的編碼電路

利用生成多項式實現(xiàn)編碼是循環(huán)碼編碼電路的常用實現(xiàn)方法。若已知信息位為位，要求糾錯能力為，可以按循環(huán)碼的性質(zhì)來設計循環(huán)碼編碼電路。首先可以根據(jù)式(6.2.9)：，求出所需要的和求出以后，再從的因式中找出生成多項式，由生成的碼就是滿足要求的循環(huán)碼。給定后，實現(xiàn)編碼電路的方法有兩種：一種方法采用的乘法電路；另一種方法是除以的除法電路。前者主要是利用方程式進行編碼，這樣編出的碼為非系統(tǒng)碼；而后者是系統(tǒng)碼編碼器中常用的電路，所編出的碼為系統(tǒng)碼。我們在這里只介紹更常使用的系統(tǒng)碼編碼電路。

第一百零一頁，共一百六十五頁，2022年，8月28日設從信源輸入編碼器的位信息組多項式為：如果要編出系統(tǒng)碼的碼字，則：

(6.3.9)從式(6.3.9)知，系統(tǒng)碼的編碼器就是將信息組乘上，然后用生成多項式除，求余式的電路，由此得系統(tǒng)循環(huán)碼的編碼步驟如下：①以乘以；②以除以，得到余式；③組合和得互碼字“”。

第一百零二頁，共一百六十五頁，2022年，8月28日實現(xiàn)系統(tǒng)循環(huán)碼編碼的電路如圖6.3.6所示。圖6.3.6級系統(tǒng)碼編碼器

第一百零三頁，共一百六十五頁，2022年，8月28日下面以二進制循環(huán)碼(漢明碼)為例，來說明編碼器的工作原理。

當輸入信息碼元為(1001)，即，設循環(huán)碼的生成多項式，由系統(tǒng)碼生成規(guī)則：其運算過程為：

第一百零四頁，共一百六十五頁，2022年，8月28日則：

由此得二進制循環(huán)系統(tǒng)碼編碼器如圖6.3.7所示。電路的編碼過程如下：①三級移存器初始狀態(tài)全為“0”，門1開，門2關。信息組以高位先入的次序送入電路，一方面經(jīng)或門輸出編碼的前個信息碼元，另一方面送入除法電路的右端，這對應于完成用除的除法運算。

第一百零五頁，共一百六十五頁，2022年，8月28日圖6.3.7循環(huán)系統(tǒng)碼編碼器

②四次移位后，信息組全部通過或門輸出，它就是系統(tǒng)碼碼字的前四個信息碼元，同時它也全部進入除電路，完成除法運算。此時在移存器中存的數(shù)就是余式的系數(shù)，也就是碼字的校驗碼元。③門1關閉，門2打開，再經(jīng)三次移位后，移存器中的校驗碼元跟在信息組后面輸出，形成一個完整的碼字。④門1打開，門2關閉，送入第二組信息組，重復上述過程。第一百零六頁，共一百六十五頁，2022年，8月28日

表6.3.4列出了上述編碼器的工作過程。設輸入信息組為(1001)，七個移位脈沖過后，在輸出端得到了已編好的碼字(1001110)。

第一百零七頁，共一百六十五頁，2022年，8月28日6.3.6循環(huán)碼的譯碼電路

若給定循環(huán)碼的生成多項式，為求伴隨式多項式，有以下定義：定義6.3.2循環(huán)碼的伴隨式多項式是接收碼字多項式或錯誤圖樣多項式除以生成多項式所得的余式。若給定循環(huán)碼的一致校驗矩陣，則伴隨式式中為發(fā)送端發(fā)送的碼字，為信道的錯誤圖樣。

循環(huán)碼的伴隨式譯碼一般包括以下三個步驟：

①根據(jù)接收碼字多項式計算相應的伴隨式多項式：或，它等價于根據(jù)接收碼字來計算相應的伴隨式：。

第一百零八頁，共一百六十五頁，2022年，8月28日②根據(jù)伴隨式(或伴隨式多項式)求對應的錯誤圖樣。③利用錯誤圖樣進行糾錯，得到對碼字的估計(即譯碼輸出)。下面我們用例題來說明循環(huán)碼伴隨式譯碼的具體過程。例6.3.6已知二進制循環(huán)碼的生成多項式，一致校驗矩陣為：

試設計能糾正一個信道錯誤的伴隨式譯碼電路。

第一百零九頁，共一百六十五頁，2022年，8月28日解：由定義6.3.2知伴隨式多項式的計算，實際上是用做除法并求余，所以伴隨式譯碼器中必須要有除法電路。此外，必須根據(jù)所求得的伴隨式結果進行正確的解碼。假設信道錯誤出現(xiàn)在最高位，即，對應的錯誤圖樣多項式為，則我們可以求得相應的伴隨式多項式：即相應的伴隨式多項式為，對應的伴隨式為。同樣，我們也可以由一致校驗矩陣求得伴隨式為：相應的譯碼電路如圖6.3.8所示。

第一百一十頁，共一百六十五頁，2022年，8月28日圖6.3.8(7，4)循環(huán)碼的伴隨式譯碼器假設接收碼字，其譯碼過程如下：①開始譯碼時，門1打開，7個時鐘過后，全部進入七個緩沖器中，同時，被除的求余運算也巳進行完畢，除法電路中的三個移位寄存器中存放的是伴隨式多項式的系數(shù)，其結果為，其中最低位對應于，最高位對應于。第一百一十一頁，共一百六十五頁，2022年，8月28日②接收碼字輸入完畢后，門1關閉。當?shù)诎藗€時鐘到來時，開始糾錯譯碼，因為此時從中出來的“101”數(shù)字