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

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

2、任務(wù)是發(fā)現(xiàn)所產(chǎn)生的錯誤、并指出發(fā)生錯誤的信號或者校正錯誤，差錯控制是采用可靠、有效的信道編碼方法來實現(xiàn)的。 信道編碼器要對信源編碼輸出的符號進(jìn)行變換，使其盡量少受噪聲干擾的影響，減少傳輸差錯，提高通信可靠性。 本章要討論的問題是在符號受到噪聲干擾的影響后，如何從接收到的信號中恢復(fù)出原送入信道的信號、確定差錯概率是多少等等。 本章首先討論信道編碼的基本概念和分類，在此基礎(chǔ)上再討論兩類主要的信道編、譯碼方法，即線性分組碼與卷積碼。 第3頁，共165頁，2022年，5月20日，16點41分，星期一6.1 信道編碼的概念 進(jìn)行信道編碼是為了提高信號傳輸?shù)目煽啃?，改善通信系統(tǒng)的傳輸質(zhì)量，研究信道編碼的目

3、標(biāo)是尋找具體構(gòu)造編碼的理論與方法。 在理論上，香農(nóng)第二定理已指出，只要實際信息傳輸率 (信道容量)，則無差錯的信道編、譯碼方法是存在的。從原理上看，構(gòu)造信道碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為地加入一定的多余碼元(稱為監(jiān)督碼)，以引入最小的多余度為代價來換取最好的抗干擾性能。 第4頁，共165頁，2022年，5月20日，16點41分，星期一6.1.1 信道編碼的分類 由于實際信道存在噪聲和干擾，使發(fā)送的碼字與信道傳輸后所接收到的碼字之間存在差錯。在一般情況下，信道中噪聲或干擾越大，碼字產(chǎn)生差錯的概率也就越大。有些實際信道既有獨立隨機差錯也有突發(fā)性成串的差錯，這種信道稱混合差錯信

4、道，實際的移動信道屬于此類信道。 對不同的信道需要設(shè)計不同類型的信道編碼方案，按照信道特性進(jìn)行劃分，信道編碼可分為：以糾獨立隨機差錯為主的信道編碼、以糾突發(fā)差錯為主的信道編碼和糾混合差錯的信道編碼。 從功能上看，信道編碼可分為檢錯(可以發(fā)現(xiàn)錯誤)碼與糾錯(不僅能發(fā)現(xiàn)而且能自動糾正)碼兩類，糾錯碼一定能檢錯，檢錯碼不一定能糾錯，平常所說的糾錯碼是兩者的統(tǒng)稱。 第5頁，共165頁，2022年，5月20日，16點41分，星期一 根據(jù)信息碼元與監(jiān)督碼元之間的關(guān)系，糾錯碼分為線性碼和非線性碼。線性碼信息碼元與監(jiān)督碼元之間呈線性關(guān)系，它們的關(guān)系可用一組線性代數(shù)方程聯(lián)系起來。非線性碼信息碼元與監(jiān)督校元之間不

5、存在線性關(guān)系。 按照對信息碼元處理的方法的不同，糾錯碼分為分組碼和卷積碼。 分組碼-把信息序列以每 個碼元分組，然后把每組 個信息元按一定規(guī)律產(chǎn)生 個多余的監(jiān)督碼元，輸出序列每組長為 ，則每一碼字的 個校驗元只與本碼字的 個信息位有關(guān)，與別的碼字的信息位無關(guān)，通常記分組碼為 。 第6頁，共165頁，2022年，5月20日，16點41分，星期一 其中分組碼又可分循環(huán)碼和非循環(huán)碼：對循環(huán)碼而言，其碼書的特點是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對非循環(huán)碼來說，任一碼字中的碼元循環(huán)移位后不一定再是該碼書中的碼字。 卷積碼-把信息序列以每 (通常較小)個碼元分段

6、，編碼器輸出該段的監(jiān)督碼元 不但與本段的 個信息元有關(guān)，而且還與其前面L段的信息碼元有關(guān)，故記卷積碼為 。 按照每個碼元的取值來分，可有二元碼和多元碼。由于目前的傳輸或存儲系統(tǒng)大都采用二進(jìn)制的數(shù)字系統(tǒng)，所以一般提到的糾錯碼都是指二元碼。 第7頁，共165頁，2022年，5月20日，16點41分，星期一綜上所述，糾錯碼分類如圖6.1.1所示。 圖6.1.1 糾錯碼的分類 第8頁，共165頁，2022年，5月20日，16點41分，星期一6.1.2 與糾錯編碼有關(guān)的基本概念 在通信系統(tǒng)的接收端，若接收到的消息序列 和發(fā)送的碼符號序列 不一樣，例如 ，而 ， 與 中有兩位不同，即出現(xiàn)兩個錯誤，這種錯誤

7、是由信道中的噪聲干擾所引起的。 為了說明如何描述這種錯誤及相應(yīng)編碼方法的性質(zhì)，我們先介紹一些基本概念。(1)碼長、碼重和碼距 碼字中碼元的個數(shù)稱為碼字的長度，簡稱碼長，用 表示。碼字中非“0”碼元的個數(shù)稱為碼字的漢明重量(簡稱碼重，記作 )。對二進(jìn)制碼來說，碼重 就是碼字中所含碼元“1”的數(shù)目，例如碼字“110000”，其碼長 ，碼重第9頁，共165頁，2022年，5月20日，16點41分，星期一兩個等長碼字之間對應(yīng)碼元不相同的數(shù)目稱為這兩個碼組的漢明距離(簡稱碼距)。例如碼字“110000”與“100001”，它們的漢明距離 。 在某一碼書 中，任意兩個碼字之間漢明距離的最小值稱為該碼的最小

8、距離 ，即： 例如：碼組 的最小碼距 。從避免碼字受干擾而出錯的角度出發(fā)，總是希望碼字間有盡可能大的距離，因為最小碼距代表著一個碼組中最不利的情況，從安全出發(fā)，應(yīng)使用最小碼距來分析碼的檢錯、糾錯能力。因此，最小碼距是衡量該碼糾錯能力的依據(jù)，是非常重要的一個參數(shù)。 第10頁，共165頁，2022年，5月20日，16點41分，星期一(2) 錯誤圖樣在二元無記憶 次擴展信道中，差錯的形式也可以用二元序列來描述。設(shè)發(fā)送碼字為 ，接收碼字為 ，兩者的差別: 稱為錯誤圖樣。如錯誤圖樣中的第 位為“1”( )，則表明傳輸過程中第 位發(fā)生了錯誤。 例如： ，而 ，則 ，可知接收的消息序列 中的第“2”位和第“

9、6”位出現(xiàn)了錯誤。 第11頁，共165頁，2022年，5月20日，16點41分，星期一(3) 重復(fù)碼和奇偶校驗碼 前面已述信道編碼的任務(wù)是構(gòu)造出以最小多余度的代價換取最大抗干擾性的“好“碼。下面，從直觀概念出發(fā)，說明多余度與抗干擾性能的關(guān)系，介紹兩種極端情況：一是高可靠性，低有效性的重復(fù)碼；二是高有效性，低可靠性的奇偶校驗碼。重復(fù)碼 構(gòu)成重復(fù)碼的方法是當(dāng)發(fā)送某個信源符號 時，不是只發(fā)一個，而是連續(xù)重發(fā)多個，連續(xù)重發(fā)的個數(shù)越多，重復(fù)碼的抗干擾能力就越強，當(dāng)然效率也越低。 第12頁，共165頁，2022年，5月20日，16點41分，星期一不重復(fù)時為(1，1)重復(fù)碼，如圖6.1.2所示: 圖6.1.

10、2 發(fā)送碼元不重復(fù) 對這種情況可得結(jié)論：不重復(fù)，方法簡單，但沒有任何抗干擾能力，既不能發(fā)現(xiàn)，更不能糾正錯誤。重復(fù)一次時為(2，1)重復(fù)碼，如圖6.1.3所示: 圖6.1.3 發(fā)送碼元重復(fù)一次 第13頁，共165頁，2022年，5月20日，16點41分，星期一 對這種情況可得結(jié)論：重發(fā)一次，效率降低一倍，可以換取在傳輸過程中允許產(chǎn)生一個錯誤(收端能發(fā)現(xiàn)它)，但不能糾正這個錯誤。 重復(fù)二次時為(3，1)重復(fù)碼，如圖6.1.4所示： 圖6.1.4 發(fā)送碼元重復(fù)二次 (3，1)重復(fù)碼用“000”來代表信息“0”，用“111”來代表信息“1”，碼本中共有兩個碼字。 第14頁，共165頁，2022年，5月

11、20日，16點41分，星期一 顯然，所增加的兩位碼元并不會增加信息，是多余的，因而使信息傳輸率降低。此外，除了傳送信息的“000”和“111”兩種組合之外，還有六種組合001，010，011，100，101，110沒有利用。當(dāng)信道上信噪比足夠大時，我們可以認(rèn)為碼字中產(chǎn)生的錯誤一般不多于一個碼元，那么，如果接收到“001”、“010”、“100”，我們就可判定實際傳輸?shù)氖恰?00”；同樣，如接收到“011”、“101”、“110”，則可判定為“111”。因此多余碼元使我們可檢出一個錯，并且還可糾正這個錯誤，這樣就提高了信息傳輸?shù)目煽啃浴?對這種情況可得結(jié)論：重發(fā)二次，效率降低二倍，但換取了可糾正

12、一個差錯或發(fā)現(xiàn)兩個差錯的性能改善。 第15頁，共165頁，2022年，5月20日，16點41分，星期一2) 奇偶檢驗碼 奇偶校驗是一種最基本的校驗方法。構(gòu)成奇偶檢驗碼的方法是在每 個二進(jìn)制信息位后加上一個奇(偶)監(jiān)督位(或稱校驗位)，使碼長 ，同時使碼中“1”的個數(shù)恒為奇數(shù)(或偶數(shù))，如圖6.1.5所示。在奇偶校驗碼中，監(jiān)督位 ，它是一種碼重 為奇數(shù)(或偶數(shù))的系統(tǒng)分組碼。圖6.1.5 奇偶校驗碼 第16頁，共165頁，2022年，5月20日，16點41分，星期一 奇偶校驗又可以分為奇校驗和偶校驗。其規(guī)則如下：奇校驗-如果信息碼元中“1”值的個數(shù)為奇數(shù)個，則校驗碼元值為“0”；如果信息碼元中“

13、1”值的個數(shù)為偶數(shù)個，則校驗碼元值為“1”。即所有信息碼元與校驗碼元的模二和等于“1”。 偶校驗-如果信息碼元中“1”值的個數(shù)為偶數(shù)個，則校驗碼元值為“0”；如果信息碼元中“1”值的個數(shù)為奇數(shù)個，則校驗碼元值為“1”。 即所有信息碼元與校驗碼元的模二和等于“0”。 根據(jù)奇偶校驗的規(guī)則，校驗位值的確定方法如表6.1.1所示。 第17頁，共165頁，2022年，5月20日，16點41分，星期一表6.1.1 奇偶校驗規(guī)則表 校驗方式信息位中“1”值的個數(shù)校驗位值奇校驗奇數(shù)個0偶數(shù)個1偶校驗偶數(shù)個0奇數(shù)個1第18頁，共165頁，2022年，5月20日，16點41分，星期一例如，在七位信息碼中，字符A的

14、代碼為1000001，其中有兩位碼元值為“1”。若采用奇校驗編碼，由于這個字符的七位代碼中有偶數(shù)個“1”，所以校驗位的值應(yīng)為“l(fā)”，其8位組合代碼為：10000011，前7位是信息位，最右邊的1位是校驗位。同理，若采用偶校驗，可得奇偶校驗位的值為“0”，其8位組合代碼為：10000010。這樣在接收端對碼字中“1”的個數(shù)進(jìn)行檢驗，如有不符，就可斷定發(fā)生了差錯。在接收端進(jìn)行校驗時，如采用奇校驗編碼，當(dāng)接收到的字符經(jīng)檢測其八位代碼“l(fā)”的個數(shù)為奇?zhèn)€數(shù)時，則被認(rèn)為傳輸正確；否則就被認(rèn)為傳輸中出現(xiàn)差錯。然而，如果在傳輸中有偶數(shù)位出現(xiàn)差錯，用此方法就檢測不出來了。 第19頁，共165頁，2022年，5月

15、20日，16點41分，星期一所以，奇偶校驗方式只能檢測出位代碼中出現(xiàn)的任意奇數(shù)個錯誤，如果代碼中錯碼數(shù)為偶數(shù)個，則奇偶校驗不能奏效。由于奇偶校驗碼容易實現(xiàn)，所以當(dāng)信道干擾不太嚴(yán)重以及碼長不很長時很有用，特別是在計算機通信網(wǎng)的數(shù)據(jù)傳送中經(jīng)常應(yīng)用這種檢錯碼。奇偶校驗編碼如果是在一維空間上進(jìn)行，則是簡單的“水平奇偶校驗”或“垂直奇偶校驗”碼，如果是在二維空間上進(jìn)行，則是“水平垂直奇偶校驗碼”。 第20頁，共165頁，2022年，5月20日，16點41分，星期一垂直奇偶校驗 在垂直奇偶校驗編碼中，先將整個要發(fā)送的信號序列劃分成長度為的若干個組，然后對每組按碼元中“1”的個數(shù)為奇數(shù)或偶數(shù)的規(guī)律，在其后附

16、加上一位奇偶校驗位，如表6.1.2所示。 表6.1.2中將70個碼元組成的信號序列劃分成長度為7的10個組，每組按順序一列一列地排列起來，然后對垂直方向的碼元進(jìn)行奇偶校驗(假設(shè)采用偶校驗)，得到一行校驗位，附加在其他各行之后，然后按列的順序進(jìn)行傳輸。 第21頁，共165頁，2022年，5月20日，16點41分，星期一碼元位分組1234567891011000111001201101000113000101110041000100000500011011016011100100070110101001偶校驗位0111101010表6.1.2 垂直奇偶校驗 第22頁，共165頁，2022年，5月2

17、0日，16點41分，星期一在垂直奇偶校驗編碼和校驗過程中，用硬件方法或軟件方法來實現(xiàn)上述連續(xù)的奇偶校驗運算都非常容易，而且在發(fā)送時可以邊發(fā)送邊產(chǎn)生校驗位，并插入發(fā)送，在接收時邊接收邊進(jìn)行校驗后去掉校驗位。 垂直奇偶校驗方法的編碼效率為： 這種奇偶校驗方法能檢測出每個分組中的所有奇數(shù)位的錯，但檢測不出偶數(shù)位的錯。對于突發(fā)性錯誤，由于出錯碼元為奇數(shù)個或偶數(shù)個的概率各占一半，因而對差錯的漏檢率接近于1/2。 第23頁，共165頁，2022年，5月20日，16點41分，星期一水平奇偶校驗 為了降低對突發(fā)錯誤的漏檢率，可以采用“水平奇偶校驗”，它是以分組為單位，對一組中的相同位的碼元進(jìn)行奇偶校驗。在水平

18、奇偶校驗中，把信號序列先以適當(dāng)?shù)拈L度劃分成個組，每組位碼元，并把每組按順序一列一列地排列起來，如表6.1.3所示第24頁，共165頁，2022年，5月20日，16點41分，星期一碼元位分組偶校驗位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011 水平奇偶校驗 第25頁，共165頁，2022年，5月20日，16點41分，星期一水平奇偶校驗的編碼效率是：水平奇偶校驗不但可以檢測各組同一位上的奇數(shù)位錯，而且可以檢測出突發(fā)長度小于或等于(每組的碼元數(shù))的所有突發(fā)

19、性錯誤(突發(fā)性錯誤是指一連串的碼元均出錯)，因為傳輸時按組的順序發(fā)送，發(fā)生長度小于或等于的突發(fā)性錯誤必然分布在不同行中，每行最多只有一位出錯，所以可以檢出差錯。 水平奇偶校驗的漏檢率比垂直奇偶校驗碼要低。但是，在實現(xiàn)水平奇偶校驗時，不論采用硬件方法還是軟件方法，都不能在發(fā)送過程中邊產(chǎn)生邊插入奇偶校驗位，而必須等待要發(fā)送的完整數(shù)據(jù)信號序列到齊后，才能確定校驗位，也就是要使用一定的存儲空間。因此，其編碼和檢測的實現(xiàn)都要復(fù)雜一些。 第26頁，共165頁，2022年，5月20日，16點41分，星期一水平垂直奇偶校驗 同時進(jìn)行水平奇偶校驗和垂直奇偶校驗就構(gòu)成二維的“水平垂直奇偶校驗碼”，如表6.1.4所

20、示。 其具體實現(xiàn)過程是：先將整個欲發(fā)送的信號序列劃分成長度為的若干個組；然后對每個組按碼元中“1”的個數(shù)為奇或偶數(shù)的規(guī)律，在其后附加上一位奇偶校驗位(表中采用偶校驗)；再對每個字符的相同位按“1”的個數(shù)為奇或偶數(shù)的規(guī)律，增加一個校驗位(表中采用偶校驗)。 第27頁，共165頁，2022年，5月20日，16點41分，星期一碼元位分組偶校驗位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011偶校驗位01111010100 水平垂直奇偶校驗 第28頁，共165頁

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

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

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

24、附加 個( )校驗位。圖6.1.7 分組碼的結(jié)構(gòu) 實現(xiàn)檢糾錯常用的基本方法除了前面介紹的 重復(fù)碼方法和奇偶校驗方法外，還有等重碼(或定比碼)方法：奇偶校驗方法。增加偶(或奇)校驗位使得對消息序列 而言校驗方程成立，當(dāng)校驗位數(shù)增加時，可以檢測到差錯圖樣的種類數(shù)也增加，但同時碼率減小。 第32頁，共165頁，2022年，5月20日，16點41分，星期一 重復(fù)碼方法。重復(fù)消息位使之可以檢測出任意小于 個差錯的錯誤圖樣。等重碼方法。設(shè)計碼字中的非“0”符號個數(shù)(若是二進(jìn)制碼則為“1”的個數(shù))恒為常數(shù)，使碼書 由全體重量恒等的 長矢量組成。表6.1.5所示為一種用于表示數(shù)字“0”到“9”的五中取三等重碼

25、(所有碼字的碼重都等于“3”)的例子。 表6.1.5 五中取三等重碼 顯然五中取三等重碼可以檢測出全部奇數(shù)位差錯，對某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯。 123456789001011110011011011010001111010111100011101001101101第33頁，共165頁，2022年，5月20日，16點41分，星期一對于糾錯碼，其抗干擾能力完全取決于碼書C中許用碼字之間的距離。碼的最小距離越大，則碼字間的最小差別越大，抗干擾能力就越強，即受較強的干擾仍不會造成許用碼字之間的混淆。 差錯控制編碼是用增加碼元數(shù)，利用“冗余”來提高抗干擾能力的，即是以降低信息傳輸速率為代

26、價來減少錯誤的，或者說是用削弱有效性來增強可靠性的。第34頁，共165頁，2022年，5月20日，16點41分，星期一6.1.4 檢錯與糾錯方式和能力 檢錯與糾錯方式 自動請求重發(fā)方式-用于檢錯的糾錯碼在譯碼器輸出端給出當(dāng)前碼字傳輸是否可能出錯的指示，當(dāng)有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的全部或部分碼字，這種糾錯碼的應(yīng)用方式稱為自動請求重發(fā)方式(ARQ，Automatic-Repeat-reQuest)。前向糾錯方式-用于糾錯的糾錯碼在譯碼器輸出端總要輸出一個碼字或是否出錯的標(biāo)志，這種糾錯碼的應(yīng)用方式稱為前向糾錯方式(FEC，F(xiàn)orward-error control)。另外

27、用于檢錯與糾錯的方式還有混合糾錯(HEC，Hybrid Error Correction)。圖6.1.8所示為上述幾種檢錯與糾錯方式示意圖，圖中有斜線的方框表示在該端檢出錯誤。 第35頁，共165頁，2022年，5月20日，16點41分，星期一圖6.1.8 差錯控制的工作方式 ARQ方式：發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行差錯編碼，通過正向信道送到接收端，而接收端經(jīng)譯碼器處理后只是檢測有無差錯，不作自動糾正。如檢測到差錯，則利用反向信道反饋信號，請求發(fā)送端重發(fā)有錯的數(shù)據(jù)單元，直到接收端檢測不到差錯為止。 第36頁，共165頁，2022年，5月20日，16點41分，星期一FEC方式：發(fā)送端用編碼器對發(fā)

28、送數(shù)據(jù)進(jìn)行差錯編碼，在接收端用譯碼器對接收到的數(shù)據(jù)進(jìn)行譯碼后檢測有無差錯，通過按預(yù)定規(guī)則的運算，如檢測到差錯，則確定差錯的具體位置和性質(zhì)，自動加以糾正，故稱為“前向糾錯”。 HEC方式：是檢錯重發(fā)和前向糾錯兩種方式的混合。發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行便于檢錯和糾錯的編碼，通過正向信道送到接收端，接收端對少量的接收差錯進(jìn)行自動前向糾正，而對超出糾正能力的差錯則通過反饋重發(fā)方式加以糾正，所以是一種糾檢結(jié)合的混合方式。(2) 檢錯與糾錯能力 一個糾錯碼的每個碼字都可以形成一個漢明球，因此要能夠糾正所有不多于 位的差錯，糾錯碼的所有漢明球均應(yīng)不相交，判定糾錯碼的檢、糾錯能力可根據(jù)任意兩個漢明球不相交的

29、要求，由碼的最小距離 來決定。 第37頁，共165頁，2022年，5月20日，16點41分，星期一 若糾錯碼的最小距離為 ，那么如下三個結(jié)論的任何一個結(jié)論獨立成立： 若要發(fā)現(xiàn)個獨立差錯，則要求最小碼距 ； 若要糾正個獨立差錯，則要求最小碼距 ； 若要求發(fā)現(xiàn)個同時又糾正個獨立差錯，則；這里說的“同時”是指在譯碼過程中，若錯誤個數(shù) ，則能糾正；若錯誤個數(shù) ，但 ，則能檢測 這些錯誤，但不能糾正?；蛘哒f能檢測個錯誤，其中 個錯誤可以糾正。其直觀的關(guān)系如圖6.1.9所示。 第38頁，共165頁，2022年，5月20日，16點41分，星期一 (a) 糾錯能力的幾何說明 (b) 檢錯能力的幾何說明 (c)

30、 區(qū)分糾錯和檢錯的示意圖 (d) 檢錯、糾錯能力與最小碼距的關(guān)系圖6.1.9 最小碼距與檢錯、糾錯能力 第39頁，共165頁，2022年，5月20日，16點41分，星期一圖6.1.9(c)中，粗線球面(圓)是糾正 個錯誤的球面，細(xì)線球面(圓)代表檢出 個錯誤的球面。當(dāng)接收碼字 中不包含錯誤或錯誤 ，將落在粗線球內(nèi)或球上，因而可把 糾正為原發(fā)送的碼字，當(dāng)接收碼字 包含 個而 個錯誤時，不會落在任何碼字的糾錯球內(nèi)，但此時代表糾錯范圍的粗線球面與另一碼字的代表檢錯范圍的細(xì)線球面沒有相交或相切，于是可將糾錯和檢錯區(qū)分開來。 當(dāng)碼的最小碼距為3或4時，可以糾正所有1位錯。 當(dāng)碼的最小碼距為5時，可以糾正

31、所有2位錯。 當(dāng)碼的最小碼距為時，可以糾正所有 位錯。 第40頁，共165頁，2022年，5月20日，16點41分，星期一定理6.1.1說明，碼的最小距離 越大，碼的糾(檢)錯誤的能力越強。但是，隨著多余碼元的增多，信息傳輸速率會降低得越多。通常用 來表示碼字中信息碼元所占的比例，稱為編碼效率，簡稱碼率，它是衡量碼性能的又一個重要參數(shù)。碼率越高，信息傳輸率就越高，但此時糾錯能力要降低，若 時就沒有糾錯能力了?？梢?，碼率與糾錯能力之間是有矛盾的。 第41頁，共165頁，2022年，5月20日，16點41分，星期一6.2 線性分組碼 線性分組碼是糾錯碼中非常重要的一類碼，雖然對于同樣碼長的非線性碼

32、來說線性碼可用碼字較少，但由于線性碼的編碼和譯碼容易實現(xiàn)，而且是討論其他各類碼的基礎(chǔ)，至今仍是廣泛應(yīng)用的一類碼。第42頁，共165頁，2022年，5月20日，16點41分，星期一6.2.1 線性分組碼的基本概念 定義6.2.1 對信源編碼器輸出的 進(jìn)制序列進(jìn)行分組，設(shè)分組長度為 ，相應(yīng)的碼字表示為： 其中：每個碼元 都是 進(jìn)制的，顯然這樣的碼字共有 個。信道編碼(糾錯編碼)的目的是將信息碼字 進(jìn)行變換，使其成為以下形式： 其中： ， 為 進(jìn)制數(shù)，顯然這樣的碼字共有 個。我們稱全體碼字 的集合為 元分組碼。若由 到 之間的變換為線性變換，則稱全體碼字 的集合為 元線性分組碼，常用 線性分組碼 來

33、表示全體碼字 的集合。 第43頁，共165頁，2022年，5月20日，16點41分，星期一例6.2.1 設(shè)將信源編碼器輸出的二進(jìn)制序列進(jìn)行分組，分組長度為 ，相應(yīng)的碼字表示為： ，這里 是二進(jìn)制的，即 。這樣的碼字共有兩個，即“1”和“0”?，F(xiàn)將 進(jìn)行變換，變換規(guī)則為： 因此，形成的糾錯碼具有以下形式： 。由于 只取“0”或“l(fā)”，所以 的全體碼字只有兩個：長為 的全“0”或全“l(fā)”序列。即經(jīng)過上述變換，得到了 重復(fù)碼。 第44頁，共165頁，2022年，5月20日，16點41分，星期一例6.2.2 設(shè)信源編碼器輸出的信息序列為 ，其中 ：是二進(jìn)制數(shù)。信道編碼器輸出的碼字為 ，其中 ：也是二進(jìn)

34、制數(shù)。若從 到 的變換規(guī)則為：由于從 到 的變換是一種線性變換，所以全體 的集合構(gòu)成了種 線性分組碼。 第45頁，共165頁，2022年，5月20日，16點41分，星期一由本例可以看出，變換后碼字集合中每一個碼字的所有碼元之和為：因為假設(shè)了碼為二進(jìn)制碼，上述碼元的和是模2和。因此，變換后將每一個碼字的碼元全部加起來，它的模2和為“0”，即每一個碼字中“1”的個數(shù)為偶數(shù)個，所以這種碼為偶校驗碼。 第46頁，共165頁，2022年，5月20日，16點41分，星期一例6.2.3 分組碼，按以下的規(guī)則(校驗方程)可得到四個校驗元： 式中： 是三個信息碼元，方程中的加運算均為模2加。由此可得到 分組碼的

35、八個碼字。八個信源序列與八個碼字的對應(yīng)關(guān)系列于表6.2.1中。由校驗方程看到，信息碼元與校驗碼元滿足線性關(guān)系，因此該 碼是線性碼。 第47頁，共165頁，2022年，5月20日，16點41分，星期一表6.2.1 例6.2.3編出的 線性碼的碼字與信息碼元的對應(yīng)關(guān)系 信息碼元碼字0 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 0第48頁，共165頁，2022年，

36、5月20日，16點41分，星期一對于線性分組碼有一個非常重要的結(jié)論：一個 線性分組碼中非零碼字的最小重量等于該碼的最小距離 。 證明 設(shè)有任意兩個碼字 。根據(jù)線性分組碼的性質(zhì)，有 。而 的碼重等于 的碼距 。即： 而 是C中任意兩個非全零碼字，所以： 證畢 由例6.2.3 線性碼的八個碼字可見，除全零碼字外，其余七個碼字最小重量 ，所以該 線性碼的最小距離 。 第49頁，共165頁，2022年，5月20日，16點41分，星期一6.2.2 生成矩陣和一致校驗矩陣 從矢量空間的角度，形形色色的編碼方法實質(zhì)上是采用了不同的基底選擇方法及矢量映射規(guī)則而形成的?；椎倪x擇與映射規(guī)則均可用矩陣來表示，因此

37、在線性分組碼的討論中就有了生成矩陣和一致校驗矩陣的概念。生成矩陣 在討論生成矩陣之前，我們再看例6.2.3的 線性分組碼。該碼所滿足的校驗方程可寫成矩陣形式： 式中稱線性分組碼的生成矩陣。 第50頁，共165頁，2022年，5月20日，16點41分，星期一定義6.2.2 若信息組以不變的形式，在碼字的任意 位中出現(xiàn)，則該碼稱為系統(tǒng)碼。否則，稱為非系統(tǒng)碼。 目前常用的有兩種形式的系統(tǒng)碼：一種是把信息組排在碼字 的最左邊 位： ，式(6.2.2)就是這種形式，若非特別說明，我們后面所說的系統(tǒng)碼均指這種形式。 另一種是把信息組安置在碼字 的最右邊 位： 。 第51頁，共165頁，2022年，5月20

38、日，16點41分，星期一能夠產(chǎn)生系統(tǒng)碼的生成矩陣為典型矩陣(或稱標(biāo)準(zhǔn)陣)，典型矩陣的最大優(yōu)勢是便于檢查生成矩陣 的各行是否是線性無關(guān)。如果 不具有標(biāo)準(zhǔn)型，雖能產(chǎn)生線性碼，但碼字不具備系統(tǒng)碼的結(jié)構(gòu)，因而存在難以區(qū)分碼字中信息碼元和監(jiān)督碼元的缺點。由于系統(tǒng)碼的編碼與譯碼較非系統(tǒng)碼簡單，而且對分組碼來說，系統(tǒng)碼與非系統(tǒng)碼的抗干擾能力是等價的，故若無特別聲明，我們僅討論系統(tǒng)碼。如果生成矩陣 為非標(biāo)準(zhǔn)型的，可經(jīng)過行初等變換變成標(biāo)準(zhǔn)型。第52頁，共165頁，2022年，5月20日，16點41分，星期一(2) 一致校驗矩陣 從前面的討論我們知道，編碼問題就是在給定的 下如何從已知的 個信息碼元求得 個校驗碼

39、元。 一般可寫成： 或 式(6.2.3)表明， 中各碼元是滿足由矩陣 所確定的個線性方程的解，故 是碼書 中的一個碼字，由 的全體就構(gòu)成了碼書 ；反之，若某碼元序列滿足由 所確定的 個線性方程，則該碼元序列一定是碼書 中的一個碼字。 第53頁，共165頁，2022年，5月20日，16點41分，星期一因此， 一定，便可由信息碼元求出校驗碼元，編碼問題就迎刃而解；或者說，要解決編碼問題，只要找到 即可。由于 碼的所有碼字均按所確定的規(guī)則求出，故稱 為其一致校驗矩陣。 綜上所述，我們將 矩陣的特點歸納如下： 矩陣的每一行代表一個線性方程的系數(shù)，它對應(yīng)求一 個校驗碼元的線性方程。 矩陣每一列代表此碼元

40、與哪幾個校驗方程有關(guān)。 由該 矩陣得到的 分組碼的每一碼字 都必須滿足 由 矩陣的行所確定的線性方程，即式(6.2.3)或式 (6.2.4)。 第54頁，共165頁，2022年，5月20日，16點41分，星期一 碼需有 個校驗碼元，故需有 個獨立的線性方程。因此， 矩陣必須有 行，且各行之間線性無關(guān)，即 矩陣的秩為 。 由于生成矩陣 中的每一行及其線性組合都是 碼中的一個碼字，故有： 或 由例6.2.3不難看出， 碼的 矩陣右邊為一個四階單位矩陣。通常，系統(tǒng)型 線性分組碼的 矩陣右邊 列組成一個單位矩陣 ，故有： 式中 是一個 階矩陣。我們稱這種形式的 矩陣為典型矩陣(或標(biāo)準(zhǔn)矩陣)，同樣，采用

41、典型矩陣形式的 矩陣更易于檢查各行是否線性無關(guān)。 第55頁，共165頁，2022年，5月20日，16點41分，星期一 由式(6.2.5)易得： 由此關(guān)系可知 或 這說明， 的第一行就是 的第一列， 的第二行就是 的第二列，因此， 矩陣一旦確定，則 矩陣也就確定，反之亦然。 第56頁，共165頁，2022年，5月20日，16點41分，星期一(3) 線性分組碼的編碼 線性分組碼的編碼就是根據(jù)一致校驗矩陣 或生成矩陣 將長度為 的信息碼元變換成長度為 的碼字。這里以 線性分組碼為例來說明構(gòu)造編碼電路的方法。 設(shè)二元碼字為 ，碼的一致校驗矩陣 為： 由 得： 第57頁，共165頁，2022年，5月20

42、日，16點41分，星期一 按照該線性方程組，可直接畫出 線性分組碼的并行編碼電路和串行編碼電路，如圖6.2.1所示。 (a) 并行編碼電路 (b) 串行編碼電路圖6.2.1 線性分組碼編碼電路原理圖 第58頁，共165頁，2022年，5月20日，16點41分，星期一(4) 對偶碼和縮短碼 我們已經(jīng)討論了 線性分組碼的生成矩陣 與其對應(yīng)的一致校驗矩陣 ，如果把 碼的一致校驗矩陣看成是 碼的生成矩陣，將 碼的生成矩陣看成是 碼的一致校驗矩陣，則稱這兩種碼互為對偶碼。 例6.2.6 求例6.2.3所述 碼的對偶碼。 顯然， 碼的對偶碼應(yīng)是 碼，由對偶碼的定義得， 碼的 矩陣就是 碼的 矩陣，將其化成

43、標(biāo)準(zhǔn)形式后即可按式(6.2.1)得到 碼的對偶碼 碼，如表6.2.2所示。 第59頁，共165頁，2022年，5月20日，16點41分，星期一表6.2.2 例6.2.3線性碼的對偶碼 信息碼元碼字信息碼元碼字0 0 0 00 0 0 0 0 0 01 0 0 01 0 0 0 1 0 10 0 0 10 0 0 1 0 1 11 0 0 11 0 0 1 1 1 00 0 1 00 0 1 0 1 1 01 0 1 01 0 1 0 0 1 10 0 1 10 0 1 1 1 0 11 0 1 11 0 1 1 0 0 00 1 0 00 1 0 0 1 1 11 1 0 01 1 0 0 0

44、 1 00 1 0 10 1 0 1 1 0 01 1 0 11 1 0 1 0 0 10 1 1 00 1 1 0 0 0 11 1 1 01 1 1 0 1 0 00 1 1 10 1 1 1 0 1 01 1 1 11 1 1 1 1 1 1第60頁，共165頁，2022年，5月20日，16點41分，星期一 在有些情況下，如果對某一給定長度的信息碼元找不到合適碼長的碼，則可將某一 碼縮短以滿足要求。例如，在 線性分組碼的碼字集合中將最左邊一位為“0”的消息和對應(yīng)的碼字選出來，并把消息中最左邊的“0”去掉，則可構(gòu)成 線性分組碼，這種碼稱為縮短碼。如表6.2.3所示。表6.2.3 例6.2.

45、3線性碼的縮短碼 信息碼元碼字0 00 0 0 0 0 00 10 1 1 1 0 11 01 0 0 1 1 11 11 1 1 0 1 0第61頁，共165頁，2022年，5月20日，16點41分，星期一6.2.3 線性分組碼的譯碼 只要找到 矩陣或 矩陣，便解決了編碼問題。經(jīng)編碼后發(fā)送的碼字，由于信道干擾可能出錯，接收方怎樣發(fā)現(xiàn)或糾正錯誤呢，這就是譯碼要解決的問題。 定義6.2.3 設(shè) 碼的一致校驗矩陣為 ， 是發(fā)送碼字為 時的接收序列，則稱： 為接收序列 的伴隨式或校正子。 伴隨式 是一致校驗矩陣 的線性組合，如果錯誤圖樣中有一些分量不為“0”，則在 中正好就是 中不為“0”的那幾列組

46、合而成。由于 是 維的列向量，所以伴隨式 也是一個 維向量。 第62頁，共165頁，2022年，5月20日，16點41分，星期一由上面的分析，可得如下結(jié)論： 從式(6.2.7)可知伴隨式 僅與錯誤圖樣 有關(guān)，它充分反映了信道受干擾的情況，而與發(fā)送的是什么碼字無關(guān)。 伴隨式是是否有錯的判別式，若 ，則判沒有出錯；若 ，則判有錯。 不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的，對二元碼來說，伴隨式即為 矩陣中與錯誤圖樣對應(yīng)的各列之和。 注意，如果錯誤圖樣 本身就是一個碼字，即 碼，那么計算伴隨式 得到的結(jié)果必為“”，此時的錯誤不能發(fā)現(xiàn)，也無法糾正，因而這樣的錯誤圖樣稱為不可檢錯誤圖樣。 第63

47、頁，共165頁，2022年，5月20日，16點41分，星期一例6.2.7 計算例6.2.3所述 碼接收 時的伴隨式。 解： 碼的一致校驗矩陣為： 當(dāng)接收時，接收端譯碼器根據(jù)接收序列計算的伴隨式為： 第64頁，共165頁，2022年，5月20日，16點41分，星期一 因此，譯碼器判別接收序列無錯，傳輸中沒有發(fā)生錯誤。 當(dāng)接收時，接收端譯碼器根據(jù)接收序列計算的伴隨式為: 由于 ，所以譯碼器判別接收序列有錯，傳輸中有錯誤發(fā)生。 碼是糾正單個錯誤的碼，觀察 即為 的第二行，因此可判定接收序列 的第二位發(fā)生了錯誤。由于接收序列中錯誤個數(shù)與碼的糾錯能力相符，所以可正確譯碼，即發(fā)送碼字應(yīng)為 。 第65頁，共

48、165頁，2022年，5月20日，16點41分，星期一當(dāng)接收 時，接收端譯碼器根據(jù)接收序列計算的伴隨式 為： ，但與 的任何一列都不相同，無法判別錯誤發(fā)生在哪些位上，此時只能發(fā)現(xiàn)有錯。伴隨式的計算可用電路來實現(xiàn)，如前所述的 碼，設(shè)接收序列 ，則伴隨式為： 第66頁，共165頁，2022年，5月20日，16點41分，星期一根據(jù)上式，可畫出 碼的伴隨式計算電路，如圖6.2.3所示。圖6.2.3 碼的伴隨式計算電路 第67頁，共165頁，2022年，5月20日，16點41分，星期一6.2.4 線性分組碼的糾錯能力 由前面的介紹可知，線性分組碼的糾錯能力 和碼字的最小距離 有關(guān)，一般 是在設(shè)計通信系統(tǒng)

49、時提出的，那么尋找滿足糾正 個錯誤碼元的碼字就是編碼技術(shù)的任務(wù)，為此我們還需進(jìn)一步研究 和碼字結(jié)構(gòu)的關(guān)系。線性分組碼碼字的結(jié)構(gòu)是由生成矩陣(或一致校驗矩陣)決定的，若巳知 矩陣，該碼的結(jié)構(gòu)也就知道了，實際上所謂校驗就是利用 矩陣去鑒別接收矢量 的結(jié)構(gòu)。那么從研究碼的糾錯能力角度來看 與 有什么關(guān)系呢？ 定理6.2.1 線性分組碼最小碼距等于 的充要條件是 矩陣中任何 列線性無關(guān)。 第68頁，共165頁，2022年，5月20日，16點41分，星期一定理6.1.2是構(gòu)造任何類型線性分組碼的基礎(chǔ)，由定理可得出以下三個結(jié)論： 為了構(gòu)造最小距離 (可檢測 個錯誤)或 (可糾正 個錯誤)的線性分組碼，其充

50、要條件是要求 矩陣中任意 列線性無關(guān)。 例如，要構(gòu)造最小距離為3的碼，則要求 矩陣中任意2列線性無關(guān)。對于二元碼，即要求 矩陣滿足無相同的列和無全“0”的列，就可糾正所有單個錯誤。 因為交換 矩陣的各列不會影響碼的最小距離，因此所有列向量相同但排列位置不同的 矩陣所對應(yīng)的分組碼，其糾錯能力和碼率是等價的。 任一線性分組碼的最小距離(或最小重量) 均滿足 。 第69頁，共165頁，2022年，5月20日，16點41分，星期一滿足 的線性分組碼稱為極大最小距離碼。在同樣的 之下，由于 最大，因此糾錯能力更強，所以設(shè)計這種碼，是編碼理論中人們感興趣的一個課題。 根據(jù)定理6.2.1，我們可以由 矩陣的

51、列的相關(guān)性直接知道碼的糾錯、檢錯能力。在巳知信息位 的條件下，如何去確定監(jiān)督位 的位數(shù)(即確定碼長)，才能滿足對糾錯能力 的要求？對此有下述結(jié)論： 若 是 二元碼，當(dāng)巳知 時，要使 能糾正 個錯，則必須有不少于 個校驗位，并且使 滿足： 第70頁，共165頁，2022年，5月20日，16點41分，星期一式中的 為 中 取的組合。滿足 時的碼稱為完備碼，這種碼的校驗元得到了最充分的利用。式(6.2.9)又稱為漢明不等式。 第71頁，共165頁，2022年，5月20日，16點41分，星期一6.2.5 漢明碼 漢明碼是漢明(Hamming)于1950年提出的能糾正一位錯的特殊的線性分組碼。漢明碼有許

52、多很好的性質(zhì)，是一種完備碼，它可以用一種簡潔有效的方法進(jìn)行譯碼。由于它的編、譯碼較簡單，且較容易實現(xiàn)，因此被廣泛采用，尤其是在計算機存儲與運算系統(tǒng)中被廣泛應(yīng)用。漢明碼的參數(shù) 對于任意正整數(shù) ，存在具有下列參數(shù)的二進(jìn)制漢明碼：碼 長：信息位數(shù)：監(jiān)督位數(shù)：最小碼距：第72頁，共165頁，2022年，5月20日，16點41分，星期一給定 后，即可構(gòu)造出具體的 漢明碼，這可以從建立致校驗矩陣 入手。我們知道， 矩陣的列數(shù)就是碼長 ，行數(shù)等于 。例如 ，可算出 ，因而是(7，4)線性碼。其 矩陣正是用 個非零三維列向量構(gòu)成的。如：此時， 矩陣的列所對應(yīng)的十進(jìn)制數(shù)正好是“1”“7”，對于糾一位差錯來說，其

53、伴隨式的值就等于對應(yīng)的 矩陣的列矢量，即錯誤位置。所以這種形式的 矩陣構(gòu)成的碼很便于糾錯，但這是非系統(tǒng)的(7，4)漢明碼的一致校驗矩陣。如果要得到系統(tǒng)碼，可調(diào)整各列次序來實現(xiàn)： 第73頁，共165頁，2022年，5月20日，16點41分，星期一有了 ，就可得到系統(tǒng)碼的校驗位，其相應(yīng)的生成矩陣為： 設(shè)碼字 ，根據(jù) (或 )及關(guān)系式 ，有： (7，4)漢明碼的編碼電路原理圖如圖6.2.4所示。 第74頁，共165頁，2022年，5月20日，16點41分，星期一漢明碼的譯碼，可以采用計算伴隨式，然后確定錯誤圖樣并加以糾正的方法。圖6.2.5所示為(7，4)漢明碼的譯碼電路原理圖。 需要注意的是(7，

54、4)漢明碼的矩陣并非只有以上兩種。原則上講， 漢明碼的一致校驗矩陣有 列 行，它的 列由除了全“0”以外的 位碼組構(gòu)成，每個碼組只在某列中出現(xiàn)一次， 矩陣中各列的次序是可任意改變。另外，對照完備碼的定義可知，漢明碼實際上是 的完備碼。 第75頁，共165頁，2022年，5月20日，16點41分，星期一圖6.2.5 (7，4)漢明譯碼器電路原理圖 第76頁，共165頁，2022年，5月20日，16點41分，星期一6.3 循環(huán)碼循環(huán)碼是一種特殊的線性分組碼，屬于線性分組碼的一個重要子類，也是目前研究最為透徹的一類碼，大多數(shù)有實用價值的糾錯碼都是循環(huán)碼。循環(huán)碼與一般的線性分組碼相比具有以下優(yōu)點：循環(huán)

55、碼的編碼及譯碼易于用簡單的具有反饋連接的移位寄存器來實現(xiàn)。 定義6.3.1 設(shè)有 線性分組碼 ，如果它的任意一個碼字的每一次循環(huán)移位仍然是 中的一個碼字，則稱 為循環(huán)碼。也即，如果 是循環(huán)碼 的一個碼字，那么 等也都是 的碼字時，則所有這些具有循環(huán)特性的碼字的全體便構(gòu)成了循環(huán)碼 。 第77頁，共165頁，2022年，5月20日，16點41分，星期一例如在例6.2.3中的 線性分組碼就是循環(huán)碼，該碼如表6.3.1所示。由表可以看到，在右邊的碼字欄內(nèi)，任意一個碼字將其循環(huán)移位后，其結(jié)果仍然是該欄內(nèi)的一個碼字。例如將第二行的碼字循環(huán)右移一位后可得到第五行的碼字，第五行的碼字循環(huán)右移一位后得到第三行的

56、碼字等。實際上右移和左移具有同樣的效果。 循環(huán)碼的主要特點是： 理論成熟：可利用成熟的代數(shù)結(jié)構(gòu)深入探討其性質(zhì)； 實現(xiàn)簡單：可利用循環(huán)移位特性在工程上進(jìn)行編、譯碼； 第78頁，共165頁，2022年，5月20日，16點41分，星期一 循環(huán)碼的描述方式有很多，但在工程上最有用的是采用多 項式的描述方法。 由于循環(huán)碼的以上特點，可以將其用多項式來表示，從而可以借助代數(shù)的工具對循環(huán)碼進(jìn)行分析，這也是循環(huán)碼能被廣泛應(yīng)用的原因之一。 信息碼元碼字0 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0

57、0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 0第79頁，共165頁，2022年，5月20日，16點41分，星期一6.3.1 循環(huán)碼的多項式描述 設(shè)有循環(huán)碼字 ，則可以用一個次數(shù)不超過 的多項式惟一確定，其相應(yīng)的多項式可表示為： (6.3.1) 即碼字 與碼多項式 一一對應(yīng)。 由循環(huán)碼的特性可知，若 是循環(huán)碼 的一個碼字，則 也是該循環(huán)碼的一個碼字，它的碼多項式為： (6.3.2) 比較式(6.3.1)和式(6.3.2)，得： 第80頁，共165頁，2022年，5月20日，16點41分，星期一 該式說明，碼字循環(huán)一次

58、的碼多項式 是原碼多項式 乘 后再除以 所得的余式，即： 由此可以推知， 的 次循環(huán)移位 是原碼多項式 乘 后再除以 所得的余式，即： (6.3.3) 式(6.3.3)揭示了 線性碼中碼多項式與碼字循環(huán)移位之間的關(guān)系，它對循環(huán)碼的研究起著重要的作用。 第81頁，共165頁，2022年，5月20日，16點41分，星期一例如前面所述 循環(huán)碼可由任一個碼字(如“0011101”)經(jīng)循環(huán)移位后，得到其他6個碼字；也可由相應(yīng)的碼多項式 乘以 后，再模 得到其他6個非零碼多項式。這個移位過程及相應(yīng)的多項式運算如表6.3.2所示。 第82頁，共165頁，2022年，5月20日，16點41分，星期一表6.3.

59、2 循環(huán)碼的循環(huán)移位 循環(huán)次數(shù)碼字碼多項式0 0 0 0 0 0 000 0 1 1 1 0 110 1 1 1 0 1 021 1 1 0 1 0 031 1 0 1 0 0 141 0 1 0 0 1 150 1 0 0 1 1 161 0 0 1 1 1 0第83頁，共165頁，2022年，5月20日，16點41分，星期一6.3.2 循環(huán)碼的生成矩陣 根據(jù)循環(huán)碼的循環(huán)特性，可由一個碼字的循環(huán)移位得到其他非“0”碼字。在 循環(huán)碼的碼多項式中，每一個能整除 的 次首一多項式(其最高次項系數(shù)為“l(fā)”)都是該碼的生成多項式，記為 。將 經(jīng)過 次循環(huán)移位，共得到 個碼多項式： 、 、 。這 個碼多

60、項式顯然是相互獨立的，可作為碼生成矩陣的 行，于是得到 循環(huán)碼的生成矩陣 ： (6.3.4) 第84頁，共165頁，2022年，5月20日，16點41分，星期一碼的生成矩陣一旦確定，碼也就確定了。這說明 循環(huán)碼可由它的一個 次首一多項式 來確定，所以可以說由 生成了 循環(huán)碼，因此稱 為碼的生成多項式，即： (6.3.5) 如果某一個碼具有生成多項式，則該碼一定是循環(huán)碼。碼的生成多項式具有如下性質(zhì)： 在 循環(huán)碼中， 次碼多項式是最低次的碼多項式。 在 循環(huán)碼中， 是惟一的 次多項式。 在 循環(huán)碼中，每個碼多項式 都是 的倍式。 任意 循環(huán)碼的生成多項式 一定整除 。 第85頁，共165頁，202