(出版社)教學(xué)講解課件

第九章信道編碼9.1引言9.2信道編碼的基本原理9.3線性分組碼

9.4循環(huán)碼9.5卷積碼

第九章信道編碼9.1引言19.1引言

由于實(shí)際信道存在噪聲和干擾，使得經(jīng)過信道傳輸后收到的碼字與發(fā)送碼字之間存在差錯(cuò)。一般情況下，信道噪聲和干擾越大，碼字產(chǎn)生差錯(cuò)的可能性也就越大。信道編碼的目的在于改善通信系統(tǒng)的傳輸質(zhì)量，發(fā)現(xiàn)或者糾正差錯(cuò)，以提高通信系統(tǒng)的可靠性。從信道編碼的構(gòu)造方法看，其基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中加入一些冗余的碼元，這些碼元稱為監(jiān)督碼元，也叫校驗(yàn)碼元。這樣接收端就可以利用監(jiān)督碼元與信息碼元的關(guān)系來發(fā)現(xiàn)或糾正錯(cuò)誤，以使受損或出錯(cuò)的信息仍能在接收端恢復(fù)。

9.1引言由于實(shí)際信道存在噪聲和干擾，使得經(jīng)過信道傳輸后2第九章(出版社)課件39.2信道編碼的基本原理香農(nóng)的信道編碼定理指出：對于一個(gè)給定的有擾信道，如果信道容量為C，只要發(fā)送端以低于C的信息速率R發(fā)送信息，則一定存在一種編碼方法，使譯碼差錯(cuò)概率隨著碼長的增加，按指數(shù)規(guī)律下降到任意小的值。這就是說，通過信道編碼可以使通信過程不發(fā)生差錯(cuò)，或者使差錯(cuò)控制在允許的數(shù)值之下。9.2信道編碼的基本原理香農(nóng)的信道編碼定理指出：對于一個(gè)49.2.1信道編碼的檢錯(cuò)和糾錯(cuò)能力信道編碼的檢錯(cuò)和糾錯(cuò)能力是通過信息量的冗余度來換取的。為了便于理解，先通過一個(gè)簡單的例子來說明。例如，要傳送A和B兩個(gè)消息，可以用一個(gè)二進(jìn)制碼元來表示一個(gè)消息，比如“0”

碼代表A，“1”碼表示B。在這種情況下，若傳輸中產(chǎn)生錯(cuò)碼，即“0”錯(cuò)成“1”，或“1”錯(cuò)成“0”，接收端將無法檢測到差錯(cuò)，因此，這種編碼沒有檢錯(cuò)和糾錯(cuò)能力。9.2.1信道編碼的檢錯(cuò)和糾錯(cuò)能力信道編碼的檢錯(cuò)和糾錯(cuò)能力5如果用兩個(gè)二進(jìn)制碼元來表示一個(gè)消息，有4種可能的碼字，即“00”、“01”、“10”和“11”。比如規(guī)定“00”表示消息A，“11”表示消息B。碼字“01”或“10”不允許使用，稱為禁用碼字，對應(yīng)地，用來表示消息的碼字稱為許用碼字。如果在傳輸消息的過程中發(fā)生一位錯(cuò)碼，則變成禁用碼字“01”或“10”，譯碼器就可判決為有錯(cuò)。這表明在信息碼元后面附加一位監(jiān)督碼元以后，當(dāng)只發(fā)生一位錯(cuò)碼時(shí)，碼字具有檢錯(cuò)能力。但由于不能判決是哪一位發(fā)生了錯(cuò)碼，所以沒有糾錯(cuò)能力。如果用兩個(gè)二進(jìn)制碼元來表示一個(gè)消息，有4種可能的碼字，即“06進(jìn)一步，如果在信息碼元之后附加兩位相同的監(jiān)督碼元，即用“000”代表消息A，“111”表示B。由于3位的二元碼有8種組合，除去2組許用碼字外，余下的6組001、010、100、011、101、110均為禁用碼字。此時(shí)，如果傳輸中產(chǎn)生一位錯(cuò)誤，接收端將收到禁用碼字，可以判決傳輸有錯(cuò)，而且還可以根據(jù)“

大數(shù)法則”來譯碼，即3位碼字中如有2個(gè)或3個(gè)“0”，則譯為消息A；如有2個(gè)或3個(gè)“1”，則譯為消息B。所以，此時(shí)可以糾正一位錯(cuò)碼。如果在傳輸中產(chǎn)生兩位錯(cuò)碼，接收端也將收到禁用碼字，譯碼器仍可檢錯(cuò)，但是不再具有糾錯(cuò)能力。如果在傳輸中產(chǎn)生三位錯(cuò)碼，接收端收到是許用碼字，這時(shí)不再具有檢錯(cuò)能力。因此，這時(shí)的信道編碼具有檢出兩位和兩位以下錯(cuò)碼的能力或者具有糾正一位錯(cuò)碼的能力。進(jìn)一步，如果在信息碼元之后附加兩位相同的監(jiān)督碼元，即用“007編碼中的幾個(gè)定義編碼中的幾個(gè)定義8第九章(出版社)課件99.2.2信道編碼的譯碼方法9.2.2信道編碼的譯碼方法10一、最大后驗(yàn)概率（MAP）譯碼一、最大后驗(yàn)概率（MAP）譯碼11二、最大似然（ML）譯碼二、最大似然（ML）譯碼12三、最小漢明距離譯碼三、最小漢明距離譯碼139.3線性分組碼9.3線性分組碼14圖9-3(n，k）線性分組碼為系統(tǒng)碼的結(jié)構(gòu)圖9-3(n，k）線性分組碼為系統(tǒng)碼的結(jié)構(gòu)159.3.1線性分組碼的編碼在介紹線性分組碼的原理之前，首先我們來看一種簡單而又常用的線性分組碼——奇偶監(jiān)督碼（也稱為奇偶校驗(yàn)碼），分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼。無論信息碼元有多少，監(jiān)督碼元只有一位。在偶數(shù)監(jiān)督碼中，監(jiān)督碼元的加入使得每個(gè)碼字中“1”的數(shù)目為偶數(shù)；在奇數(shù)監(jiān)督碼中，監(jiān)督碼元的加入使得每個(gè)碼字中“1”的數(shù)目為奇數(shù)。9.3.1線性分組碼的編碼在介紹線性分組碼的原理之前，首先我16第九章(出版社)課件17第九章(出版社)課件18線性分組碼的編碼原理線性分組碼的編碼原理19第九章(出版社)課件20第九章(出版社)課件21第九章(出版社)課件22第九章(出版社)課件23第九章(出版社)課件24第九章(出版社)課件25第九章(出版社)課件26生成矩陣和監(jiān)督矩陣的聯(lián)系生成矩陣和監(jiān)督矩陣的聯(lián)系279.3.2線性分組碼的譯碼9.3.2線性分組碼的譯碼28第九章(出版社)課件299.3.3漢明碼

9.3.3漢明碼309.4循環(huán)碼在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它除了具有線性分組碼的一般特點(diǎn)，還具有循環(huán)性：若循環(huán)碼中任一碼字的碼元循環(huán)移位（左移或右移）后仍是該碼的一個(gè)碼字。由于循環(huán)碼是在嚴(yán)密的現(xiàn)代代數(shù)理論的基礎(chǔ)上發(fā)展起來的，其編碼和譯碼的電路較簡單，且它的檢、糾錯(cuò)能力較強(qiáng)，目前它已成為研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。9.4循環(huán)碼在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它31第九章(出版社)課件329.4.1循環(huán)碼的碼多項(xiàng)式9.4.1循環(huán)碼的碼多項(xiàng)式33多項(xiàng)式的按模運(yùn)算多項(xiàng)式的按模運(yùn)算34第九章(出版社)課件35

9.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣

9.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣36第九章(出版社)課件37第九章(出版社)課件389.4.3循環(huán)碼的檢錯(cuò)和糾錯(cuò)9.4.3循環(huán)碼的檢錯(cuò)和糾錯(cuò)399.4.4循環(huán)碼的編碼和譯碼電路循環(huán)碼最引人注目的特點(diǎn)有兩個(gè)：一是由于循環(huán)碼有許多固有的代數(shù)結(jié)構(gòu)，從而可以找到各種簡單實(shí)用的譯碼方法；二是用反饋線性移位寄存器可以很容易地實(shí)現(xiàn)其編碼和監(jiān)督子的計(jì)算。9.4.4循環(huán)碼的編碼和譯碼電路循環(huán)碼最引人注目的特點(diǎn)有兩40一、循環(huán)碼的編碼電路一、循環(huán)碼的編碼電路41圖9-4（7，4）循環(huán)碼的編碼電路圖9-4（7，4）循環(huán)碼的編碼電路42二、循環(huán)碼的譯碼電路二、循環(huán)碼的譯碼電路43圖9-5（7，4）循環(huán)碼的譯碼電路示意圖圖9-5（7，4）循環(huán)碼的譯碼電路示意圖449.5卷積碼9.5卷積碼459.5.1卷積碼的解析表示9.5.1卷積碼的解析表示46圖9-6(3，1，2)卷積碼編碼器圖9-6(3，1，2)卷積碼編碼器47一、生成矩陣和監(jiān)督矩陣一、生成矩陣和監(jiān)督矩陣48第九章(出版社)課件49第九章(出版社)課件50監(jiān)督矩陣監(jiān)督矩陣51第九章(出版社)課件52第九章(出版社)課件53二、多項(xiàng)式表示二、多項(xiàng)式表示54第九章(出版社)課件559.5.2卷積碼的圖形描述以圖9-6所示的（3，1，2）卷積碼編碼器為例來說明其工作過程。假設(shè)移位寄存器的起始狀態(tài)全為零。當(dāng)?shù)谝粋€(gè)輸入比特為“0”時(shí)，輸出的子碼為000；若當(dāng)?shù)谝粋€(gè)輸入比特為“1”時(shí)，輸出的子碼為111。當(dāng)輸入第二比特時(shí)，第一比特右移一位，此時(shí)的輸出比特顯然與當(dāng)前輸入比特和前一輸入比特有關(guān)。當(dāng)輸入第三比特時(shí)，第一比特和第二比特都右移一位，此時(shí)的輸出比特顯然與當(dāng)前輸入比特和前二位輸入比特有關(guān)。當(dāng)輸入第四比特時(shí)，第二比特和第三比特都右移一位，此時(shí)的輸出比特與當(dāng)前輸入比特和前二個(gè)輸入比特有關(guān)，而這時(shí)第一比特已經(jīng)不再影響當(dāng)前的輸入比特了。編碼器在移位過程中可能產(chǎn)生的各種序列，可用樹狀圖來描述。9.5.2卷積碼的圖形描述以圖9-6所示的（3，1，2）56圖9-7給出了卷積碼的樹狀圖。由樹狀圖，已知輸入信息序列就可以得到輸出序列，當(dāng)輸入碼元是0時(shí)，則由節(jié)點(diǎn)出發(fā)走上支路；當(dāng)輸入碼元是1時(shí)，則由節(jié)點(diǎn)出發(fā)走下支路。例如當(dāng)輸入編碼器的信息序列為0110…時(shí)，輸出的序列為000111101011…。圖9-7給出了卷積碼的樹狀圖。由樹狀圖，已知輸入信息序列就可57圖9-7卷積碼的樹狀圖圖9-7卷積碼的樹狀圖589.5.3卷積碼的幾種譯碼方法卷積碼有三種主要的譯碼方法：序列譯碼、門限譯碼和最大似然譯碼。1957年伍成克拉夫(Wozencraft)提出了一種有效的譯碼方法，即序列譯碼。1963年梅西(Massey)提出了一種性能稍差，但比較實(shí)用的門限譯碼方法。1967年維特比(Viterbi)提出了最大似然譯碼法，它又稱為維特比譯碼。門限譯碼是一種代數(shù)譯碼法，序列譯碼和維特比最大似然譯碼都是概率譯碼。代數(shù)譯碼利用編碼本身得代數(shù)結(jié)構(gòu)進(jìn)行解碼，并不考慮信道的統(tǒng)計(jì)特性。比如門限譯碼，它以分組碼理論為基礎(chǔ)，其主要特點(diǎn)是算法簡單，易于實(shí)現(xiàn)，但是它的誤碼性能要比概率譯碼差。它的譯碼方法是從線性碼的監(jiān)督子出發(fā)，找到一組特殊的能夠檢查信息位置是否發(fā)生錯(cuò)誤的方程組，從而實(shí)現(xiàn)糾錯(cuò)譯碼。概率譯碼的基本思想是：把已經(jīng)接收到的序列與所有可能的發(fā)送序列相比較，選擇其中漢明距離最小的一個(gè)序列作為發(fā)送序列。維特比譯碼是目前用得較多的一種譯碼方法。它是一種最大似然譯碼，其譯碼的復(fù)雜性均隨m按指數(shù)增長。最大似然譯碼對存儲(chǔ)器級(jí)數(shù)較小的卷積碼很容易實(shí)現(xiàn)，被廣泛地應(yīng)用于現(xiàn)代通信中。隨著大規(guī)模集成電路技術(shù)的發(fā)展，對存儲(chǔ)器級(jí)數(shù)較大的卷積碼也可以采用最大似然譯碼。目前維特比譯碼已經(jīng)得到了廣泛的應(yīng)用。9.5.3卷積碼的幾種譯碼方法卷積碼有三種主要的譯碼方法：序59第九章信道編碼9.1引言9.2信道編碼的基本原理9.3線性分組碼

9.4循環(huán)碼9.5卷積碼

第九章信道編碼9.1引言609.1引言

由于實(shí)際信道存在噪聲和干擾，使得經(jīng)過信道傳輸后收到的碼字與發(fā)送碼字之間存在差錯(cuò)。一般情況下，信道噪聲和干擾越大，碼字產(chǎn)生差錯(cuò)的可能性也就越大。信道編碼的目的在于改善通信系統(tǒng)的傳輸質(zhì)量，發(fā)現(xiàn)或者糾正差錯(cuò)，以提高通信系統(tǒng)的可靠性。從信道編碼的構(gòu)造方法看，其基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中加入一些冗余的碼元，這些碼元稱為監(jiān)督碼元，也叫校驗(yàn)碼元。這樣接收端就可以利用監(jiān)督碼元與信息碼元的關(guān)系來發(fā)現(xiàn)或糾正錯(cuò)誤，以使受損或出錯(cuò)的信息仍能在接收端恢復(fù)。

9.1引言由于實(shí)際信道存在噪聲和干擾，使得經(jīng)過信道傳輸后61第九章(出版社)課件629.2信道編碼的基本原理香農(nóng)的信道編碼定理指出：對于一個(gè)給定的有擾信道，如果信道容量為C，只要發(fā)送端以低于C的信息速率R發(fā)送信息，則一定存在一種編碼方法，使譯碼差錯(cuò)概率隨著碼長的增加，按指數(shù)規(guī)律下降到任意小的值。這就是說，通過信道編碼可以使通信過程不發(fā)生差錯(cuò)，或者使差錯(cuò)控制在允許的數(shù)值之下。9.2信道編碼的基本原理香農(nóng)的信道編碼定理指出：對于一個(gè)639.2.1信道編碼的檢錯(cuò)和糾錯(cuò)能力信道編碼的檢錯(cuò)和糾錯(cuò)能力是通過信息量的冗余度來換取的。為了便于理解，先通過一個(gè)簡單的例子來說明。例如，要傳送A和B兩個(gè)消息，可以用一個(gè)二進(jìn)制碼元來表示一個(gè)消息，比如“0”

碼代表A，“1”碼表示B。在這種情況下，若傳輸中產(chǎn)生錯(cuò)碼，即“0”錯(cuò)成“1”，或“1”錯(cuò)成“0”，接收端將無法檢測到差錯(cuò)，因此，這種編碼沒有檢錯(cuò)和糾錯(cuò)能力。9.2.1信道編碼的檢錯(cuò)和糾錯(cuò)能力信道編碼的檢錯(cuò)和糾錯(cuò)能力64如果用兩個(gè)二進(jìn)制碼元來表示一個(gè)消息，有4種可能的碼字，即“00”、“01”、“10”和“11”。比如規(guī)定“00”表示消息A，“11”表示消息B。碼字“01”或“10”不允許使用，稱為禁用碼字，對應(yīng)地，用來表示消息的碼字稱為許用碼字。如果在傳輸消息的過程中發(fā)生一位錯(cuò)碼，則變成禁用碼字“01”或“10”，譯碼器就可判決為有錯(cuò)。這表明在信息碼元后面附加一位監(jiān)督碼元以后，當(dāng)只發(fā)生一位錯(cuò)碼時(shí)，碼字具有檢錯(cuò)能力。但由于不能判決是哪一位發(fā)生了錯(cuò)碼，所以沒有糾錯(cuò)能力。如果用兩個(gè)二進(jìn)制碼元來表示一個(gè)消息，有4種可能的碼字，即“065進(jìn)一步，如果在信息碼元之后附加兩位相同的監(jiān)督碼元，即用“000”代表消息A，“111”表示B。由于3位的二元碼有8種組合，除去2組許用碼字外，余下的6組001、010、100、011、101、110均為禁用碼字。此時(shí)，如果傳輸中產(chǎn)生一位錯(cuò)誤，接收端將收到禁用碼字，可以判決傳輸有錯(cuò)，而且還可以根據(jù)“

大數(shù)法則”來譯碼，即3位碼字中如有2個(gè)或3個(gè)“0”，則譯為消息A；如有2個(gè)或3個(gè)“1”，則譯為消息B。所以，此時(shí)可以糾正一位錯(cuò)碼。如果在傳輸中產(chǎn)生兩位錯(cuò)碼，接收端也將收到禁用碼字，譯碼器仍可檢錯(cuò)，但是不再具有糾錯(cuò)能力。如果在傳輸中產(chǎn)生三位錯(cuò)碼，接收端收到是許用碼字，這時(shí)不再具有檢錯(cuò)能力。因此，這時(shí)的信道編碼具有檢出兩位和兩位以下錯(cuò)碼的能力或者具有糾正一位錯(cuò)碼的能力。進(jìn)一步，如果在信息碼元之后附加兩位相同的監(jiān)督碼元，即用“0066編碼中的幾個(gè)定義編碼中的幾個(gè)定義67第九章(出版社)課件689.2.2信道編碼的譯碼方法9.2.2信道編碼的譯碼方法69一、最大后驗(yàn)概率（MAP）譯碼一、最大后驗(yàn)概率（MAP）譯碼70二、最大似然（ML）譯碼二、最大似然（ML）譯碼71三、最小漢明距離譯碼三、最小漢明距離譯碼729.3線性分組碼9.3線性分組碼73圖9-3(n，k）線性分組碼為系統(tǒng)碼的結(jié)構(gòu)圖9-3(n，k）線性分組碼為系統(tǒng)碼的結(jié)構(gòu)749.3.1線性分組碼的編碼在介紹線性分組碼的原理之前，首先我們來看一種簡單而又常用的線性分組碼——奇偶監(jiān)督碼（也稱為奇偶校驗(yàn)碼），分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼。無論信息碼元有多少，監(jiān)督碼元只有一位。在偶數(shù)監(jiān)督碼中，監(jiān)督碼元的加入使得每個(gè)碼字中“1”的數(shù)目為偶數(shù)；在奇數(shù)監(jiān)督碼中，監(jiān)督碼元的加入使得每個(gè)碼字中“1”的數(shù)目為奇數(shù)。9.3.1線性分組碼的編碼在介紹線性分組碼的原理之前，首先我75第九章(出版社)課件76第九章(出版社)課件77線性分組碼的編碼原理線性分組碼的編碼原理78第九章(出版社)課件79第九章(出版社)課件80第九章(出版社)課件81第九章(出版社)課件82第九章(出版社)課件83第九章(出版社)課件84第九章(出版社)課件85生成矩陣和監(jiān)督矩陣的聯(lián)系生成矩陣和監(jiān)督矩陣的聯(lián)系869.3.2線性分組碼的譯碼9.3.2線性分組碼的譯碼87第九章(出版社)課件889.3.3漢明碼

9.3.3漢明碼899.4循環(huán)碼在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它除了具有線性分組碼的一般特點(diǎn)，還具有循環(huán)性：若循環(huán)碼中任一碼字的碼元循環(huán)移位（左移或右移）后仍是該碼的一個(gè)碼字。由于循環(huán)碼是在嚴(yán)密的現(xiàn)代代數(shù)理論的基礎(chǔ)上發(fā)展起來的，其編碼和譯碼的電路較簡單，且它的檢、糾錯(cuò)能力較強(qiáng)，目前它已成為研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。9.4循環(huán)碼在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它90第九章(出版社)課件919.4.1循環(huán)碼的碼多項(xiàng)式9.4.1循環(huán)碼的碼多項(xiàng)式92多項(xiàng)式的按模運(yùn)算多項(xiàng)式的按模運(yùn)算93第九章(出版社)課件94

9.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣

9.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣95第九章(出版社)課件96第九章(出版社)課件979.4.3循環(huán)碼的檢錯(cuò)和糾錯(cuò)9.4.3循環(huán)碼的檢錯(cuò)和糾錯(cuò)989.4.4循環(huán)碼的編碼和譯碼電路循環(huán)碼最引人注目的特點(diǎn)有兩個(gè)：一是由于循環(huán)碼有許多固有的代數(shù)結(jié)構(gòu)，從而可以找到各種簡單實(shí)用的譯碼方法；二是用反饋線性移位寄存器可以很容易地實(shí)現(xiàn)其編碼和監(jiān)督子的計(jì)算。9.4.4循環(huán)碼的編碼和譯碼電路循環(huán)碼最引人注目的特點(diǎn)有兩99一、循環(huán)碼的編碼電路一、循環(huán)碼的編碼電路100圖9-4（7，4）循環(huán)碼的編碼電路圖9-4（7，4）循環(huán)碼的編碼電路101二、循環(huán)碼的譯碼電路二、循環(huán)碼的譯碼電路102圖9-5（7，4）循環(huán)碼的譯碼電路示意圖圖9-5（7，4）循環(huán)碼的譯碼電路示意圖1039.5卷積碼9.5卷積碼1049.5.1卷積碼的解析表示9.5.1卷積碼的解析表示105圖9-6(3，1，2)卷積碼編碼器圖9-6(3，1，2)卷積碼編碼器106一、生成矩陣和監(jiān)督矩陣一、生成矩陣和監(jiān)督矩陣107第九章(出版社)課件108第九章(出版社)課件109監(jiān)督矩陣監(jiān)督矩陣110第九章(出版社)課件111第九章(出版社)課件112二、多項(xiàng)式表示二、多項(xiàng)式表示113第九章(出版社)課件1149.5.2卷積碼的圖形描述以圖9-6所示的（3，1，2）卷積碼編碼器為例來說明其工作過程。假設(shè)移位寄存器的起始狀態(tài)全為零。當(dāng)?shù)谝粋€(gè)輸入比特為“0”時(shí)，輸出的子碼為000；若當(dāng)?shù)谝粋€(gè)輸入比特為“1”時(shí)，輸出的子碼為111。當(dāng)輸入第二比特時(shí)，第一比特右移一位，此時(shí)的輸出比特顯然與當(dāng)前輸入比特和前一輸入比特有關(guān)。當(dāng)輸入第三比特時(shí)，第一比特和第二比特都右移一位，此時(shí)的輸出比特顯然與當(dāng)前輸入比特和前二位輸入比特有關(guān)。當(dāng)輸入第四比特時(shí)，第二比特和第三比特都右移一位，此時(shí)的輸出比特與當(dāng)前輸入比特和前二個(gè)輸入比特有關(guān)，而這時(shí)第一比特已經(jīng)不再影響當(dāng)前的輸入比特了。編