信息論與編碼技術(shù)

信息論與編碼技術(shù)第1頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月在通信系統(tǒng)中，要提高信息傳輸?shù)挠行?，我們將信源的輸出?jīng)過(guò)信源編碼用較少的符號(hào)來(lái)表達(dá)信源消息，這些符號(hào)剩余度很小，效率很高，但對(duì)噪聲干擾的抵抗能力很弱。信息傳輸要通過(guò)各種物理信道，由于干擾、設(shè)備故障等影響，被傳送的信源符號(hào)可能會(huì)發(fā)生失真，使有用信息遭受損壞，接收信號(hào)造成誤判。這種在接收端錯(cuò)誤地確定所接收的信號(hào)叫做差錯(cuò)。為了提高信息傳輸?shù)臏?zhǔn)確性，使其具有較好的抵抗信道中噪聲干擾的能力，在通信系統(tǒng)中需要采用專門的檢、糾錯(cuò)誤方法，即差錯(cuò)控制。

第2頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月差錯(cuò)控制的任務(wù)是發(fā)現(xiàn)所產(chǎn)生的錯(cuò)誤、并指出發(fā)生錯(cuò)誤的信號(hào)或者校正錯(cuò)誤，差錯(cuò)控制是采用可靠、有效的信道編碼方法來(lái)實(shí)現(xiàn)的。

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

第3頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.1信道編碼的概念

進(jìn)行信道編碼是為了提高信號(hào)傳輸?shù)目煽啃裕纳仆ㄐ畔到y(tǒng)的傳輸質(zhì)量，研究信道編碼的目標(biāo)是尋找具體構(gòu)造編碼的理論與方法。在理論上，香農(nóng)第二定理已指出，只要實(shí)際信息傳輸率(信道容量)，則無(wú)差錯(cuò)的信道編、譯碼方法是存在的。從原理上看，構(gòu)造信道碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為地加入一定的多余碼元(稱為監(jiān)督碼)，以引入最小的多余度為代價(jià)來(lái)?yè)Q取最好的抗干擾性能。

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

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

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

第6頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

其中分組碼又可分循環(huán)碼和非循環(huán)碼：對(duì)循環(huán)碼而言，其碼書的特點(diǎn)是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對(duì)非循環(huán)碼來(lái)說(shuō)，任一碼字中的碼元循環(huán)移位后不一定再是該碼書中的碼字。卷積碼----把信息序列以每(通常較小)個(gè)碼元分段，編碼器輸出該段的監(jiān)督碼元不但與本段的個(gè)信息元有關(guān)，而且還與其前面L段的信息碼元有關(guān)，故記卷積碼為。按照每個(gè)碼元的取值來(lái)分，可有二元碼和多元碼。由于目前的傳輸或存儲(chǔ)系統(tǒng)大都采用二進(jìn)制的數(shù)字系統(tǒng)，所以一般提到的糾錯(cuò)碼都是指二元碼。第7頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月綜上所述，糾錯(cuò)碼分類如圖6.1.1所示。

圖6.1.1糾錯(cuò)碼的分類

第8頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.1.2與糾錯(cuò)編碼有關(guān)的基本概念

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

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

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

第11頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月(3)重復(fù)碼和奇偶校驗(yàn)碼前面已述信道編碼的任務(wù)是構(gòu)造出以最小多余度的代價(jià)換取最大抗干擾性的“好“碼。下面，從直觀概念出發(fā)，說(shuō)明多余度與抗干擾性能的關(guān)系，介紹兩種極端情況：一是高可靠性，低有效性的重復(fù)碼；二是高有效性，低可靠性的奇偶校驗(yàn)碼。重復(fù)碼

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

第12頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月不重復(fù)時(shí)為(1，1)重復(fù)碼，如圖6.1.2所示:圖6.1.2發(fā)送碼元不重復(fù)

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

第13頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

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

(3，1)重復(fù)碼用“000”來(lái)代表信息“0”，用“111”來(lái)代表信息“1”，碼本中共有兩個(gè)碼字。

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

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

第16頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月奇偶校驗(yàn)又可以分為奇校驗(yàn)和偶校驗(yàn)。其規(guī)則如下：奇校驗(yàn)----如果信息碼元中“1”值的個(gè)數(shù)為奇數(shù)個(gè)，則校驗(yàn)碼元值為“0”；如果信息碼元中“1”值的個(gè)數(shù)為偶數(shù)個(gè)，則校驗(yàn)碼元值為“1”。即所有信息碼元與校驗(yàn)碼元的模二和等于“1”。

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

第17頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月表6.1.1奇偶校驗(yàn)規(guī)則表

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

第20頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月垂直奇偶校驗(yàn)在垂直奇偶校驗(yàn)編碼中，先將整個(gè)要發(fā)送的信號(hào)序列劃分成長(zhǎng)度為的若干個(gè)組，然后對(duì)每組按碼元中“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)的規(guī)律，在其后附加上一位奇偶校驗(yàn)位，如表6.1.2所示。表6.1.2中將70個(gè)碼元組成的信號(hào)序列劃分成長(zhǎng)度為7的10個(gè)組，每組按順序一列一列地排列起來(lái)，然后對(duì)垂直方向的碼元進(jìn)行奇偶校驗(yàn)(假設(shè)采用偶校驗(yàn))，得到一行校驗(yàn)位，附加在其他各行之后，然后按列的順序進(jìn)行傳輸。

第21頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月碼元位分組1234567891011000111001201101000113000101110041000100000500011011016011100100070110101001偶校驗(yàn)位0111101010表6.1.2垂直奇偶校驗(yàn)第22頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月在垂直奇偶校驗(yàn)編碼和校驗(yàn)過(guò)程中，用硬件方法或軟件方法來(lái)實(shí)現(xiàn)上述連續(xù)的奇偶校驗(yàn)運(yùn)算都非常容易，而且在發(fā)送時(shí)可以邊發(fā)送邊產(chǎn)生校驗(yàn)位，并插入發(fā)送，在接收時(shí)邊接收邊進(jìn)行校驗(yàn)后去掉校驗(yàn)位。垂直奇偶校驗(yàn)方法的編碼效率為：這種奇偶校驗(yàn)方法能檢測(cè)出每個(gè)分組中的所有奇數(shù)位的錯(cuò)，但檢測(cè)不出偶數(shù)位的錯(cuò)。對(duì)于突發(fā)性錯(cuò)誤，由于出錯(cuò)碼元為奇數(shù)個(gè)或偶數(shù)個(gè)的概率各占一半，因而對(duì)差錯(cuò)的漏檢率接近于1/2。

第23頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月水平奇偶校驗(yàn)為了降低對(duì)突發(fā)錯(cuò)誤的漏檢率，可以采用“水平奇偶校驗(yàn)”，它是以分組為單位，對(duì)一組中的相同位的碼元進(jìn)行奇偶校驗(yàn)。在水平奇偶校驗(yàn)中，把信號(hào)序列先以適當(dāng)?shù)拈L(zhǎng)度劃分成個(gè)組，每組位碼元，并把每組按順序一列一列地排列起來(lái)，如表6.1.3所示然后對(duì)水平方向的碼元進(jìn)行奇偶校驗(yàn)，得到一列校驗(yàn)位，附加在其他各列之后，最后按列的順序進(jìn)行傳輸。表中的信號(hào)序列共分成10個(gè)組，每組有7個(gè)碼元。傳輸時(shí)按列的順序先傳送第l組，再傳送第2組……，最后傳送第11列即校驗(yàn)位列(本例采用偶校驗(yàn))。因此，在信道中傳送的二進(jìn)制信號(hào)序列為：10010000100011……1101101。第24頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月碼元位分組偶校驗(yàn)位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011表6.1.3

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

水平垂直奇偶校驗(yàn)第28頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月水平垂直奇偶校驗(yàn)的編碼效率為：這種方法能檢測(cè)出所有3位或3位以下的錯(cuò)誤，因?yàn)樵谶@種情況下，至少會(huì)在某一行或某一列上出現(xiàn)一位錯(cuò)，這時(shí)錯(cuò)誤就能被檢測(cè)到；還能檢測(cè)出奇數(shù)位錯(cuò)、突發(fā)長(zhǎng)度小于或等于的突發(fā)性錯(cuò)以及很大一部分偶數(shù)位錯(cuò)。一些試驗(yàn)測(cè)量表明，這種方式的編碼可使誤碼率降至原始誤碼率的百分之一到萬(wàn)分之一。另外，水平垂直奇偶校驗(yàn)不僅可檢錯(cuò)，還可用來(lái)糾正部分差錯(cuò)。上述奇偶校驗(yàn)碼中，水平奇偶校驗(yàn)碼、垂直奇偶校驗(yàn)碼是單純檢錯(cuò)碼，而水平垂直奇偶校驗(yàn)碼則還具有有限的糾錯(cuò)能力，但多數(shù)情況下只用于檢錯(cuò)。第29頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.1.3檢錯(cuò)與糾錯(cuò)原理

檢錯(cuò)、糾錯(cuò)的目的是要根據(jù)信道接收端接收到的信息序列來(lái)判斷是否就是發(fā)送的序列，如果有錯(cuò)則盡可能糾正其中的錯(cuò)誤。要糾正傳輸差錯(cuò)，首先必須檢測(cè)出錯(cuò)誤。而要檢測(cè)出錯(cuò)誤，常用的方法是將發(fā)送端要傳送的信息序列(常為二進(jìn)制序列)中截取出長(zhǎng)度相等的碼元進(jìn)行分組，每組長(zhǎng)度為k，組成k位碼元信息序列，并根據(jù)某種編碼算法以一定的規(guī)則在每個(gè)信息組的后面產(chǎn)生個(gè)冗余碼元，由冗余碼元和信息碼元一起形成“位編碼序列”，即信號(hào)碼字，位的碼字比信息碼長(zhǎng)(有個(gè)碼元)，因而糾錯(cuò)編碼是冗余編碼，如圖6.1.6所示。第30頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月圖6.1.6糾錯(cuò)編碼

譯碼就是利用校驗(yàn)關(guān)系進(jìn)行檢錯(cuò)、糾錯(cuò)的，在接收端收到的位碼字中，信息碼元與冗余碼元之間也應(yīng)符合上述編碼規(guī)則，并根據(jù)這一規(guī)則進(jìn)行檢驗(yàn)，從而確定是否有錯(cuò)誤。這就是差錯(cuò)控制的基本思想。我們把這種將信息碼元分組，為每組碼附加若干校驗(yàn)碼的編碼稱為分組碼。在分組碼中，校驗(yàn)碼元僅校驗(yàn)本碼組中的信息碼元。分組碼一般用符號(hào)表示，其中是每組二進(jìn)制信息碼元的數(shù)目，是編碼組的長(zhǎng)度(簡(jiǎn)稱碼長(zhǎng))，即編碼組的總位數(shù)，為每碼組中的校驗(yàn)碼元(或稱監(jiān)督位)數(shù)目。第31頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月通常，將分組碼規(guī)定為具有如圖6.1.7所示的結(jié)構(gòu)。圖中前面位()為信息位，后面附加個(gè)()校驗(yàn)位。圖6.1.7分組碼的結(jié)構(gòu)

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

第32頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

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

顯然五中取三等重碼可以檢測(cè)出全部奇數(shù)位差錯(cuò)，對(duì)某些碼字的傳輸則可以檢測(cè)出部分偶數(shù)位差錯(cuò)。123456789001011110011011011010001111010111100011101001101101第33頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月對(duì)于糾錯(cuò)碼，其抗干擾能力完全取決于碼書C中許用碼字之間的距離。碼的最小距離越大，則碼字間的最小差別越大，抗干擾能力就越強(qiáng)，即受較強(qiáng)的干擾仍不會(huì)造成許用碼字之間的混淆。差錯(cuò)控制編碼是用增加碼元數(shù)，利用“冗余”來(lái)提高抗干擾能力的，即是以降低信息傳輸速率為代價(jià)來(lái)減少錯(cuò)誤的，或者說(shuō)是用削弱有效性來(lái)增強(qiáng)可靠性的。第34頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.1.4檢錯(cuò)與糾錯(cuò)方式和能力

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

第35頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月圖6.1.8差錯(cuò)控制的工作方式

ARQ方式：發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)進(jìn)行差錯(cuò)編碼，通過(guò)正向信道送到接收端，而接收端經(jīng)譯碼器處理后只是檢測(cè)有無(wú)差錯(cuò)，不作自動(dòng)糾正。如檢測(cè)到差錯(cuò)，則利用反向信道反饋信號(hào)，請(qǐng)求發(fā)送端重發(fā)有錯(cuò)的數(shù)據(jù)單元，直到接收端檢測(cè)不到差錯(cuò)為止。第36頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月FEC方式：發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)進(jìn)行差錯(cuò)編碼，在接收端用譯碼器對(duì)接收到的數(shù)據(jù)進(jìn)行譯碼后檢測(cè)有無(wú)差錯(cuò)，通過(guò)按預(yù)定規(guī)則的運(yùn)算，如檢測(cè)到差錯(cuò)，則確定差錯(cuò)的具體位置和性質(zhì)，自動(dòng)加以糾正，故稱為“前向糾錯(cuò)”。HEC方式：是檢錯(cuò)重發(fā)和前向糾錯(cuò)兩種方式的混合。發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)進(jìn)行便于檢錯(cuò)和糾錯(cuò)的編碼，通過(guò)正向信道送到接收端，接收端對(duì)少量的接收差錯(cuò)進(jìn)行自動(dòng)前向糾正，而對(duì)超出糾正能力的差錯(cuò)則通過(guò)反饋重發(fā)方式加以糾正，所以是一種糾檢結(jié)合的混合方式。(2)檢錯(cuò)與糾錯(cuò)能力一個(gè)糾錯(cuò)碼的每個(gè)碼字都可以形成一個(gè)漢明球，因此要能夠糾正所有不多于位的差錯(cuò)，糾錯(cuò)碼的所有漢明球均應(yīng)不相交，判定糾錯(cuò)碼的檢、糾錯(cuò)能力可根據(jù)任意兩個(gè)漢明球不相交的要求，由碼的最小距離來(lái)決定。第37頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月定理6.1.1

若糾錯(cuò)碼的最小距離為，那么如下三個(gè)結(jié)論的任何一個(gè)結(jié)論獨(dú)立成立：①若要發(fā)現(xiàn)個(gè)獨(dú)立差錯(cuò)，則要求最小碼距；②若要糾正個(gè)獨(dú)立差錯(cuò)，則要求最小碼距；③若要求發(fā)現(xiàn)個(gè)同時(shí)又糾正個(gè)獨(dú)立差錯(cuò)，則；這里說(shuō)的“同時(shí)”是指在譯碼過(guò)程中，若錯(cuò)誤個(gè)數(shù)≤，則能糾正；若錯(cuò)誤個(gè)數(shù)＞，但≤，則能檢測(cè)這些錯(cuò)誤，但不能糾正?；蛘哒f(shuō)能檢測(cè)個(gè)錯(cuò)誤，其中個(gè)錯(cuò)誤可以糾正。其直觀的關(guān)系如圖6.1.9所示。第38頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月(a)糾錯(cuò)能力的幾何說(shuō)明(b)檢錯(cuò)能力的幾何說(shuō)明(c)區(qū)分糾錯(cuò)和檢錯(cuò)的示意圖(d)檢錯(cuò)、糾錯(cuò)能力與最小碼距的關(guān)系圖6.1.9最小碼距與檢錯(cuò)、糾錯(cuò)能力第39頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月圖6.1.9(c)中，粗線球面(圓)是糾正個(gè)錯(cuò)誤的球面，細(xì)線球面(圓)代表檢出個(gè)錯(cuò)誤的球面。當(dāng)接收碼字中不包含錯(cuò)誤或錯(cuò)誤，將落在粗線球內(nèi)或球上，因而可把糾正為原發(fā)送的碼字，當(dāng)接收碼字包含個(gè)而個(gè)錯(cuò)誤時(shí)，不會(huì)落在任何碼字的糾錯(cuò)球內(nèi)，但此時(shí)代表糾錯(cuò)范圍的粗線球面與另一碼字的代表檢錯(cuò)范圍的細(xì)線球面沒(méi)有相交或相切，于是可將糾錯(cuò)和檢錯(cuò)區(qū)分開(kāi)來(lái)。

當(dāng)碼的最小碼距為3或4時(shí)，可以糾正所有1位錯(cuò)。當(dāng)碼的最小碼距為5時(shí)，可以糾正所有2位錯(cuò)。當(dāng)碼的最小碼距為時(shí)，可以糾正所有位錯(cuò)。

第40頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月定理6.1.1說(shuō)明，碼的最小距離越大，碼的糾(檢)錯(cuò)誤的能力越強(qiáng)。但是，隨著多余碼元的增多，信息傳輸速率會(huì)降低得越多。通常用來(lái)表示碼字中信息碼元所占的比例，稱為編碼效率，簡(jiǎn)稱碼率，它是衡量碼性能的又一個(gè)重要參數(shù)。碼率越高，信息傳輸率就越高，但此時(shí)糾錯(cuò)能力要降低，若時(shí)就沒(méi)有糾錯(cuò)能力了。可見(jiàn)，碼率與糾錯(cuò)能力之間是有矛盾的。第41頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.2線性分組碼

線性分組碼是糾錯(cuò)碼中非常重要的一類碼，雖然對(duì)于同樣碼長(zhǎng)的非線性碼來(lái)說(shuō)線性碼可用碼字較少，但由于線性碼的編碼和譯碼容易實(shí)現(xiàn)，而且是討論其他各類碼的基礎(chǔ)，至今仍是廣泛應(yīng)用的一類碼。第42頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.2.1線性分組碼的基本概念

定義6.2.1對(duì)信源編碼器輸出的進(jìn)制序列進(jìn)行分組，設(shè)分組長(zhǎng)度為，相應(yīng)的碼字表示為：

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

其中：，為進(jìn)制數(shù)，顯然這樣的碼字共有個(gè)。我們稱全體碼字的集合為元分組碼。若由到之間的變換為線性變換，則稱全體碼字的集合為元線性分組碼，常用線性分組碼來(lái)表示全體碼字的集合。第43頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例6.2.1設(shè)將信源編碼器輸出的二進(jìn)制序列進(jìn)行分組，分組長(zhǎng)度為，相應(yīng)的碼字表示為：，這里是二進(jìn)制的，即。這樣的碼字共有兩個(gè)，即“1”和“0”?，F(xiàn)將進(jìn)行變換，變換規(guī)則為：

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

第44頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例6.2.2設(shè)信源編碼器輸出的信息序列為，其中：是二進(jìn)制數(shù)。信道編碼器輸出的碼字為，其中：也是二進(jìn)制數(shù)。若從到的變換規(guī)則為：由于從到的變換是一種線性變換，所以全體的集合構(gòu)成了—種線性分組碼。

第45頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月由本例可以看出，變換后碼字集合中每一個(gè)碼字的所有碼元之和為：因?yàn)榧僭O(shè)了碼為二進(jìn)制碼，上述碼元的和是模2和。因此，變換后將每一個(gè)碼字的碼元全部加起來(lái)，它的模2和為“0”，即每一個(gè)碼字中“1”的個(gè)數(shù)為偶數(shù)個(gè)，所以這種碼為偶校驗(yàn)碼。第46頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例6.2.3分組碼，按以下的規(guī)則(校驗(yàn)方程)可得到四個(gè)校驗(yàn)元：式中：是三個(gè)信息碼元，方程中的加運(yùn)算均為模2加。由此可得到分組碼的八個(gè)碼字。八個(gè)信源序列與八個(gè)碼字的對(duì)應(yīng)關(guān)系列于表6.2.1中。由校驗(yàn)方程看到，信息碼元與校驗(yàn)碼元滿足線性關(guān)系，因此該碼是線性碼。

第47頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月表6.2.1例6.2.3編出的線性碼的碼字與信息碼元的對(duì)應(yīng)關(guān)系信息碼元碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100第48頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月對(duì)于線性分組碼有一個(gè)非常重要的結(jié)論：一個(gè)線性分組碼中非零碼字的最小重量等于該碼的最小距離。

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

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

[證畢]

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

第49頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.2.2生成矩陣和一致校驗(yàn)矩陣

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

第50頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月定義6.2.2若信息組以不變的形式，在碼字的任意位中出現(xiàn)，則該碼稱為系統(tǒng)碼。否則，稱為非系統(tǒng)碼。目前常用的有兩種形式的系統(tǒng)碼：一種是把信息組排在碼字的最左邊位：，式(6.2.2)就是這種形式，若非特別說(shuō)明，我們后面所說(shuō)的系統(tǒng)碼均指這種形式。

另一種是把信息組安置在碼字的最右邊位：。第51頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月能夠產(chǎn)生系統(tǒng)碼的生成矩陣為典型矩陣(或稱標(biāo)準(zhǔn)陣)，典型矩陣的最大優(yōu)勢(shì)是便于檢查生成矩陣的各行是否是線性無(wú)關(guān)。如果不具有標(biāo)準(zhǔn)型，雖能產(chǎn)生線性碼，但碼字不具備系統(tǒng)碼的結(jié)構(gòu)，因而存在難以區(qū)分碼字中信息碼元和監(jiān)督碼元的缺點(diǎn)。由于系統(tǒng)碼的編碼與譯碼較非系統(tǒng)碼簡(jiǎn)單，而且對(duì)分組碼來(lái)說(shuō)，系統(tǒng)碼與非系統(tǒng)碼的抗干擾能力是等價(jià)的，故若無(wú)特別聲明，我們僅討論系統(tǒng)碼。如果生成矩陣為非標(biāo)準(zhǔn)型的，可經(jīng)過(guò)行初等變換變成標(biāo)準(zhǔn)型。第52頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月(2)一致校驗(yàn)矩陣

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

或

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

第53頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月因此，一定，便可由信息碼元求出校驗(yàn)碼元，編碼問(wèn)題就迎刃而解；或者說(shuō)，要解決編碼問(wèn)題，只要找到即可。由于碼的所有碼字均按所確定的規(guī)則求出，故稱為其一致校驗(yàn)矩陣。綜上所述，我們將矩陣的特點(diǎn)歸納如下：

①矩陣的每一行代表一個(gè)線性方程的系數(shù)，它對(duì)應(yīng)求一個(gè)校驗(yàn)碼元的線性方程。②矩陣每一列代表此碼元與哪幾個(gè)校驗(yàn)方程有關(guān)。③由該矩陣得到的分組碼的每一碼字都必須滿足由矩陣的行所確定的線性方程，即式(6.2.3)或式(6.2.4)。第54頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月碼需有個(gè)校驗(yàn)碼元，故需有個(gè)獨(dú)立的線性方程。因此，矩陣必須有行，且各行之間線性無(wú)關(guān)，即矩陣的秩為。⑤由于生成矩陣中的每一行及其線性組合都是碼中的一個(gè)碼字，故有：或

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

式中是一個(gè)階矩陣。我們稱這種形式的矩陣為典型矩陣(或標(biāo)準(zhǔn)矩陣)，同樣，采用典型矩陣形式的矩陣更易于檢查各行是否線性無(wú)關(guān)。

第55頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月⑦由式(6.2.5)易得：

由此關(guān)系可知

或

這說(shuō)明，的第一行就是的第一列，的第二行就是的第二列，……，因此，矩陣一旦確定，則矩陣也就確定，反之亦然。第56頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月(3)線性分組碼的編碼

線性分組碼的編碼就是根據(jù)一致校驗(yàn)矩陣或生成矩陣將長(zhǎng)度為的信息碼元變換成長(zhǎng)度為的碼字。這里以線性分組碼為例來(lái)說(shuō)明構(gòu)造編碼電路的方法。例6.2.4

設(shè)二元碼字為，碼的一致校驗(yàn)矩陣為：由得：

第57頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月按照該線性方程組，可直接畫出線性分組碼的并行編碼電路和串行編碼電路，如圖6.2.1所示。

(a)并行編碼電路(b)串行編碼電路圖6.2.1線性分組碼編碼電路原理圖第58頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月(4)對(duì)偶碼和縮短碼我們已經(jīng)討論了線性分組碼的生成矩陣與其對(duì)應(yīng)的一致校驗(yàn)矩陣，如果把碼的一致校驗(yàn)矩陣看成是碼的生成矩陣，將碼的生成矩陣看成是碼的一致校驗(yàn)矩陣，則稱這兩種碼互為對(duì)偶碼。

例6.2.6求例6.2.3所述碼的對(duì)偶碼。顯然，碼的對(duì)偶碼應(yīng)是碼，由對(duì)偶碼的定義得，碼的矩陣就是碼的矩陣，將其化成標(biāo)準(zhǔn)形式后即可按式(6.2.1)得到碼的對(duì)偶碼碼，如表6.2.2所示。第59頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月表6.2.2例6.2.3線性碼的對(duì)偶碼

信息碼元碼字信息碼元碼字00000000000100010001010001000101110011001110001000101101010101001100110011101101110110000100010011111001100010010101011001101110100101100110001111011101000111011101011111111111第60頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

在有些情況下，如果對(duì)某一給定長(zhǎng)度的信息碼元找不到合適碼長(zhǎng)的碼，則可將某一碼縮短以滿足要求。例如，在線性分組碼的碼字集合中將最左邊一位為“0”的消息和對(duì)應(yīng)的碼字選出來(lái)，并把消息中最左邊的“0”去掉，則可構(gòu)成線性分組碼，這種碼稱為縮短碼。如表6.2.3所示。表6.2.3例6.2.3線性碼的縮短碼信息碼元碼字00000000010111011010011111111010第61頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.2.3線性分組碼的譯碼

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

定義6.2.3設(shè)碼的一致校驗(yàn)矩陣為，是發(fā)送碼字為時(shí)的接收序列，則稱：為接收序列的伴隨式或校正子。伴隨式是一致校驗(yàn)矩陣的線性組合，如果錯(cuò)誤圖樣中有一些分量不為“0”，則在中正好就是中不為“0”的那幾列組合而成。由于是維的列向量，所以伴隨式也是一個(gè)維向量。第62頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月由上面的分析，可得如下結(jié)論：①?gòu)氖?6.2.7)可知伴隨式僅與錯(cuò)誤圖樣有關(guān)，它充分反映了信道受干擾的情況，而與發(fā)送的是什么碼字無(wú)關(guān)。②伴隨式是是否有錯(cuò)的判別式，若，則判沒(méi)有出錯(cuò)；若，則判有錯(cuò)。③不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)應(yīng)的，對(duì)二元碼來(lái)說(shuō)，伴隨式即為矩陣中與錯(cuò)誤圖樣對(duì)應(yīng)的各列之和。注意，如果錯(cuò)誤圖樣本身就是一個(gè)碼字，即碼，那么計(jì)算伴隨式得到的結(jié)果必為“”，此時(shí)的錯(cuò)誤不能發(fā)現(xiàn)，也無(wú)法糾正，因而這樣的錯(cuò)誤圖樣稱為不可檢錯(cuò)誤圖樣。

第63頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例6.2.7計(jì)算例6.2.3所述碼接收時(shí)的伴隨式。

解：碼的一致校驗(yàn)矩陣為：

當(dāng)接收時(shí)，接收端譯碼器根據(jù)接收序列計(jì)算的伴隨式為：第64頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

因此，譯碼器判別接收序列無(wú)錯(cuò)，傳輸中沒(méi)有發(fā)生錯(cuò)誤。

當(dāng)接收時(shí)，接收端譯碼器根據(jù)接收序列計(jì)算的伴隨式為:由于，所以譯碼器判別接收序列有錯(cuò)，傳輸中有錯(cuò)誤發(fā)生。碼是糾正單個(gè)錯(cuò)誤的碼，觀察即為的第二行，因此可判定接收序列的第二位發(fā)生了錯(cuò)誤。由于接收序列中錯(cuò)誤個(gè)數(shù)與碼的糾錯(cuò)能力相符，所以可正確譯碼，即發(fā)送碼字應(yīng)為。第65頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月當(dāng)接收時(shí)，接收端譯碼器根據(jù)接收序列計(jì)算的伴隨式為：，但與的任何一列都不相同，無(wú)法判別錯(cuò)誤發(fā)生在哪些位上，此時(shí)只能發(fā)現(xiàn)有錯(cuò)。伴隨式的計(jì)算可用電路來(lái)實(shí)現(xiàn)，如前所述的碼，設(shè)接收序列，則伴隨式為：

第66頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月根據(jù)上式，可畫出碼的伴隨式計(jì)算電路，如圖6.2.3所示。圖6.2.3碼的伴隨式計(jì)算電路

第67頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.2.4線性分組碼的糾錯(cuò)能力

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

若是二元碼，當(dāng)巳知時(shí)，要使能糾正個(gè)錯(cuò)，則必須有不少于個(gè)校驗(yàn)位，并且使?jié)M足：

第70頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月式中的為中取的組合。滿足時(shí)的碼稱為完備碼，這種碼的校驗(yàn)元得到了最充分的利用。式(6.2.9)又稱為漢明不等式。

第71頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.2.5漢明碼

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

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

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

即碼字與碼多項(xiàng)式一一對(duì)應(yīng)。

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

(6.3.2)

比較式(6.3.1)和式(6.3.2)，得：第80頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

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

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

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

第81頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例如前面所述循環(huán)碼可由任一個(gè)碼字(如“0011101”)經(jīng)循環(huán)移位后，得到其他6個(gè)碼字；也可由相應(yīng)的碼多項(xiàng)式乘以后，再模得到其他6個(gè)非零碼多項(xiàng)式。這個(gè)移位過(guò)程及相應(yīng)的多項(xiàng)式運(yùn)算如表6.3.2所示。第82頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月表6.3.2循環(huán)碼的循環(huán)移位循環(huán)次數(shù)碼字碼多項(xiàng)式000000000011101101110102111010031101001410100115010011161001110第83頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.3.2循環(huán)碼的生成矩陣

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

(6.3.4)

第84頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月碼的生成矩陣一旦確定，碼也就確定了。這說(shuō)明循環(huán)碼可由它的一個(gè)次首一多項(xiàng)式來(lái)確定，所以可以說(shuō)由生成了循環(huán)碼，因此稱為碼的生成多項(xiàng)式，即：

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

第85頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例6.3.2求二進(jìn)制循環(huán)碼的生成多項(xiàng)式。解：分解多項(xiàng)式，取其四次首一多項(xiàng)式作為生成多項(xiàng)式：可將一次和任一個(gè)三次多項(xiàng)式的乘積作為生成多項(xiàng)式：或由于線性碼的生成矩陣與一致校驗(yàn)矩陣滿足關(guān)系：，而循環(huán)碼也是線性碼，如果設(shè)為循環(huán)碼的生成多項(xiàng)式，它必為的因式，則有：(6.3.6)第86頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月因?yàn)槭谴味囗?xiàng)式，以為生成多項(xiàng)式，則生成一個(gè)循環(huán)碼，以為生成多項(xiàng)式，則生成一個(gè)循環(huán)碼，這兩個(gè)循環(huán)碼互為對(duì)偶碼。稱為循環(huán)碼的校驗(yàn)多項(xiàng)式，且：(6.3.7)顯然，循環(huán)碼也可由其校驗(yàn)多項(xiàng)式完全確定，循環(huán)碼的一致校驗(yàn)矩陣為(6.3.8)

第87頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月式中為的反多項(xiàng)式：

第88頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例6.3.3以二進(jìn)制碼碼為例，說(shuō)明循環(huán)碼可由生成多項(xiàng)式或校驗(yàn)多項(xiàng)式完全確定。

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

第89頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

的系數(shù)的系數(shù)的系數(shù)的系數(shù)將上述方程組寫成矩陣形式：第90頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月上式中列矩陣的元素就是生成多項(xiàng)式的系數(shù)，它本身是一個(gè)碼字，那么第一個(gè)矩陣即為循環(huán)碼的一致校驗(yàn)矩陣，即：可見(jiàn)，一致校驗(yàn)矩陣的第一行是碼的校驗(yàn)多項(xiàng)式的系數(shù)的反序排列，而第二、三、四行分別是第一行的移位，由此得到用校驗(yàn)多項(xiàng)式的系數(shù)來(lái)構(gòu)成的一致校驗(yàn)矩陣：第91頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月由上分析可得以下結(jié)論：給定了循環(huán)碼的生成多項(xiàng)式，可以求得相應(yīng)的生成矩陣，由又可以確定校驗(yàn)多項(xiàng)式，并可由確定循環(huán)碼的一致校驗(yàn)矩陣。生成多項(xiàng)式與生成矩陣的含義是相同的，前者對(duì)應(yīng)于循環(huán)碼的多項(xiàng)式表示方式，而后者對(duì)應(yīng)于循環(huán)碼的矩陣表示方式，兩者之間可以相互轉(zhuǎn)換。第92頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.3.3系統(tǒng)循環(huán)碼

前面介紹的生成矩陣所產(chǎn)生循環(huán)碼不是系統(tǒng)碼。我們可以通過(guò)矩陣的行運(yùn)算，得到系統(tǒng)循環(huán)碼的生成矩陣，使之具有的形式，生成矩陣的行運(yùn)算實(shí)質(zhì)上就是碼字間個(gè)基底間進(jìn)行線性組合運(yùn)算。系統(tǒng)循環(huán)碼的生成矩陣的一致校驗(yàn)矩陣是。例6.3.4以為生成多項(xiàng)式生成一個(gè)循環(huán)碼，要求生成的循環(huán)碼是系統(tǒng)的。解：由例6.3.1得對(duì)應(yīng)給定的循環(huán)碼的一般生成矩陣為：第93頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

對(duì)矩陣的行進(jìn)行運(yùn)算，將第⑴、⑶、⑷行相加后作為第1行，第⑵、⑷行相加后作為第2行，得：對(duì)應(yīng)：這樣，就得到系統(tǒng)循環(huán)碼的生成矩陣和一致校驗(yàn)矩陣。第94頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.3.4多項(xiàng)式運(yùn)算電路

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

設(shè)有多項(xiàng)式和，則：

與的相加電路如圖6.3.1所示。若的階數(shù)小于的階數(shù)，則將也擴(kuò)充為次多項(xiàng)式，其擴(kuò)充的冪次項(xiàng)系數(shù)為“0”。圖6.3.1多項(xiàng)式相加第95頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月多項(xiàng)式的乘法電路如圖6.3.2所示，按照?qǐng)D6.3.2的乘法電路構(gòu)成，與乘法的—般電路如圖6.3.3所示。在乘法電路中總假設(shè)多項(xiàng)式的低位在前，電路中的所有寄存器初態(tài)為“0”。圖6.3.2多項(xiàng)式乘法電路例第96頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月圖6.3.3多項(xiàng)式乘法電路

設(shè)，，則用多項(xiàng)式去除任意多項(xiàng)式的電路即為除法電路，如圖6.3.4所示。移位寄存器的初始狀態(tài)全為“0”，當(dāng)輸入完畢，移位寄存器()中的內(nèi)容即為余式。圖6.3.4除法電路第97頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月例6.3.5設(shè)被除式與除式都是系數(shù)為二進(jìn)制的多項(xiàng)式，且：

則完成除以的電路如圖6.3.5所示。完成上述二個(gè)多項(xiàng)式相除的算式如下：這里商為，余式為，表6.3.3給出了圖6.3.5電路的運(yùn)算過(guò)程，經(jīng)過(guò)次移位后得到商項(xiàng)的系數(shù)，=5次移位后，完成了整個(gè)除法運(yùn)算，在移位寄存器中保存的數(shù)(001)代表余式的系數(shù)。第98頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月1100111節(jié)拍輸入移位寄存器的內(nèi)容輸出000000111000211100300110401111510011余式商式表6.3.3例6.3.5的運(yùn)算過(guò)程表第99頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月圖6.3.5例6.3.5的除法電路

第100頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.3.5循環(huán)碼的編碼電路

利用生成多項(xiàng)式實(shí)現(xiàn)編碼是循環(huán)碼編碼電路的常用實(shí)現(xiàn)方法。若已知信息位為位，要求糾錯(cuò)能力為，可以按循環(huán)碼的性質(zhì)來(lái)設(shè)計(jì)循環(huán)碼編碼電路。首先可以根據(jù)式(6.2.9)：，求出所需要的和求出以后，再?gòu)牡囊蚴街姓页錾啥囗?xiàng)式，由生成的碼就是滿足要求的循環(huán)碼。給定后，實(shí)現(xiàn)編碼電路的方法有兩種：一種方法采用的乘法電路；另一種方法是除以的除法電路。前者主要是利用方程式進(jìn)行編碼，這樣編出的碼為非系統(tǒng)碼；而后者是系統(tǒng)碼編碼器中常用的電路，所編出的碼為系統(tǒng)碼。我們?cè)谶@里只介紹更常使用的系統(tǒng)碼編碼電路。

第101頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月設(shè)從信源輸入編碼器的位信息組多項(xiàng)式為：如果要編出系統(tǒng)碼的碼字，則：

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

第102頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月實(shí)現(xiàn)系統(tǒng)循環(huán)碼編碼的電路如圖6.3.6所示。圖6.3.6級(jí)系統(tǒng)碼編碼器

第103頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月下面以二進(jìn)制循環(huán)碼(漢明碼)為例，來(lái)說(shuō)明編碼器的工作原理。

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

第104頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月則：

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

第105頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月圖6.3.7循環(huán)系統(tǒng)碼編碼器

②四次移位后，信息組全部通過(guò)或門輸出，它就是系統(tǒng)碼碼字的前四個(gè)信息碼元，同時(shí)它也全部進(jìn)入除電路，完成除法運(yùn)算。此時(shí)在移存器中存的數(shù)就是余式的系數(shù)，也就是碼字的校驗(yàn)碼元。③門1關(guān)閉，門2打開(kāi)，再經(jīng)三次移位后，移存器中的校驗(yàn)碼元跟在信息組后面輸出，形成一個(gè)完整的碼字。④門1打開(kāi)，門2關(guān)閉，送入第二組信息組，重復(fù)上述過(guò)程。第106頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月

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

第107頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月6.3.6循環(huán)碼的譯碼電路

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

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

①根據(jù)接收碼字多項(xiàng)式計(jì)算相應(yīng)的伴隨式多項(xiàng)式：或，它等價(jià)于根據(jù)接收碼字來(lái)計(jì)算相應(yīng)的伴隨式：。

第108頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月②根據(jù)伴隨式(或伴隨式多項(xiàng)式)求對(duì)應(yīng)的錯(cuò)誤圖樣。③利用錯(cuò)誤圖樣進(jìn)行糾錯(cuò)，得到對(duì)碼字的估計(jì)(即譯碼輸出)。下面我們用例題來(lái)說(shuō)明循環(huán)碼伴隨式譯碼的具體過(guò)程。例6.3.6已知二進(jìn)制循環(huán)碼的生成多項(xiàng)式，一致校驗(yàn)矩陣為：

試設(shè)計(jì)能糾正一個(gè)信道錯(cuò)誤的伴隨式譯碼電路。

第109頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月解：由定義6.3.2知伴隨式多項(xiàng)式的計(jì)算，實(shí)際上是用做除法并求余，所以伴隨式譯碼器中必須要有除法電路。此外，必須根據(jù)所求得的伴隨式結(jié)果進(jìn)行正確的解碼。假設(shè)信道錯(cuò)誤出現(xiàn)在最高位，即，對(duì)應(yīng)的錯(cuò)誤圖樣多項(xiàng)式為，則我們可以求得相應(yīng)的伴隨式多項(xiàng)式：即相應(yīng)的伴隨式多項(xiàng)式為，對(duì)應(yīng)的伴隨式為。同樣，我們也可以由一致校驗(yàn)矩陣求得伴隨式為：相應(yīng)的譯碼電路如圖6.3.8所示。

第110頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月圖6.3.8(7，4)循環(huán)碼的伴隨式譯碼器假設(shè)接收碼字，其譯碼過(guò)程如下：①開(kāi)始譯碼時(shí)，門1打開(kāi)，7個(gè)時(shí)鐘過(guò)后，全部進(jìn)入七個(gè)緩沖器中，同時(shí)，被除的求余運(yùn)算也巳進(jìn)行完畢，除法電路中的三個(gè)移位寄存器中存放的是伴隨式多項(xiàng)式的系數(shù)，其結(jié)果為，其中最低位對(duì)應(yīng)于，最高位對(duì)應(yīng)于。第111頁(yè)，課件共165頁(yè)，創(chuàng)作于2023年2月②接收碼字輸入完畢后，門1關(guān)閉。當(dāng)?shù)诎藗€(gè)時(shí)鐘到來(lái)時(shí)，開(kāi)始糾錯(cuò)譯碼，因?yàn)榇藭r(shí)從中出來(lái)的“10