信息論與編碼糾錯第5章-課件

第5章有噪信道編碼第5章內容提要本章介紹了信道編碼和譯碼的基本概念，介紹了兩種常用的譯碼準則：最大后驗概率譯碼準則和極大似然譯碼準則,還介紹了在這兩種譯碼準則下錯誤概率的計算方法。本章還介紹了信道編碼定理及信道編碼逆定理，以及信息論中的一個重要不等式Fnao不等式。內容提要本章介紹了信道編碼和譯碼的基本概念，介紹了兩種常用的§5.1信道編碼的基本概念

我們要盡可能的提高信息傳輸率，并控制傳輸誤差。信源編碼以提高傳輸效率作為主要考慮因素，信道編碼以提高傳輸可靠性作為主要考慮因素。信道有多種形式，如電視、廣播、微波、電話、計算機局域網和寬帶網等，對于所有的信道可用下圖所示的模型來表示：§5.1信道編碼的基本概念我們要盡可能的提高信息傳輸率，并衡量信道傳輸快慢的指標是信息傳輸率，而衡量信息傳輸可靠性的指標是平均錯誤概率，平均錯誤概率與信道的統(tǒng)計特性有關。要改變信道統(tǒng)計特性成本太大，所以可事先對信源編碼器輸出的符號序列按照某種規(guī)則進行編碼，一般的方法是給信源序列加上一定的冗余度，這種編碼稱為信道編碼，編好的代碼稱為碼字，將碼字送入信道傳輸，在信道的輸出端，信道譯碼器根據編碼規(guī)則對信道輸出符號進行估值，盡量使這種估值接近輸入碼字。信源輸出序列，經信道編碼器編成碼字并輸入信道，由于干擾，信道輸出，信道譯碼器對估值得。衡量信道傳輸快慢的指標是信息傳輸率，而衡量信息傳輸可靠性的指【例】給定二元對稱信道，信道固有錯誤概率為p（p<0.5）編碼規(guī)則：為提高可靠性，每個信道符號重復三次發(fā)送。

譯碼規(guī)則：擇多譯碼，即信宿方收到的三個符號中有兩個或三個為1，就將此次接收符號判決為1；若三個符號中有兩個或三個為0，就將此次接收符號判決為0。

下面為重復編碼傳輸示意圖，計算錯誤概率pe?！纠拷o定二元對稱信道，信道固有錯誤概率為p（p<0.5信源輸出序列為：

信道輸入序列為：

由于p的存在，使得傳輸出錯，故信道輸出為：

根據譯碼規(guī)則，信道估值輸出：

信道錯誤概率：假設信道離散無記憶，即

錯誤概率為：

重復編碼的結果使錯誤概率下降。

信源輸出序列為：信道輸入序列為：由于p的存在，使得傳輸出【例】逆重復碼離散無記憶二進制對稱信道，固有誤碼率為p(p<0.5)，信源輸出序列為三位二進制數(shù)字。編碼規(guī)則：為提高傳輸效率，僅向信道發(fā)送一位，預先將信源輸出序列進行擇多編碼：信源輸出的三位符號中有兩位或3位是1，信源序列編碼為1，若三位符號中有兩位或3位是0，就將此信源序列編碼為0。譯碼規(guī)則：將接收的一位符號重復三次譯出，即若接收到1就譯碼為111，即若接收到0就譯碼為000。下面為重復編碼傳輸示意圖，計算錯誤概率pe。【例】逆重復碼離散無記憶二進制對稱信道，固有誤碼率為p(（1）先設p=0，計算這種編碼方法帶來的固有錯誤p1。信道輸入符號集

X={000，001，010，011，100，101，110，111}

判決輸出符號集Y={000，111}

譯碼規(guī)則：

因為后驗概率：

則出錯概率：

（1）先設p=0，計算這種編碼方法帶來的固有錯誤p1假設8組輸入序列是等概發(fā)送的，由于信道的對稱性，兩個估值序列也是等概分布的，則每個序列的平均錯誤概率為:誤比特率（2）再設p≠0，計算由于信道噪聲引起的錯誤概率p2。

因為每個序列有三位二進制數(shù)字，但只發(fā)送一位，這一位的出錯概率為p，故序列差錯概率為p，誤比特率（3）總差錯概率（誤比特率）：假設8組輸入序列是等概發(fā)送的，由于信道的對稱性，兩個估值序列【例】奇偶校驗碼在信息序列后面加上一位校驗位，使之模2和等于1，這樣的編碼稱為奇校驗碼；若使模2和等于0，這樣的編碼就稱為偶校驗碼，即每個碼矢中1的個數(shù)固定為奇數(shù)或偶數(shù)。奇偶校驗碼能檢測出奇數(shù)位錯誤，但無法判斷錯的是哪一位，故沒有糾錯能力。這種編碼方式可用在反饋信道場合，如計算機通信串口通信。【例】奇偶校驗碼在信息序列后面加上一位校驗位，使之模2和等§5.2譯碼規(guī)則及錯誤概率信道總不可避免會攙雜噪聲，所以信息在信道傳輸過程中，差錯是不可避免的。選擇合適的譯碼規(guī)則可以彌補信道的不足?！纠緽SC信道的轉移概率如下

時，這是一種強噪聲信道，在這種情況下，若按常規(guī)譯碼，肯定出錯，但可將判決取反，收到0判為1，收到1判為0，反而正確。可見譯碼規(guī)則對傳輸系統(tǒng)錯誤概率的影響是很大的。

§5.2譯碼規(guī)則及錯誤概率信道總不可避免會攙雜噪聲，所一．最大后驗概率譯碼準則設信源有M個消息，信道編碼器已用M個碼矢

對它進行了最佳編碼。

編碼后發(fā)送碼矢量，其發(fā)送概率為，通過信道轉移概率為的信道傳輸，接收矢量為，信道譯碼器輸出。通信過程框圖如下：

一．最大后驗概率譯碼準則設信源有M個消息，信道編碼器已用M個當估值時，就產生了誤碼，用表示后驗概率，則收到估錯的錯誤概率為：通信總希望錯誤概率最小，由上式可看出錯誤概率最小等同于后驗概率最大，這就是最大后驗概率譯碼準則。當估值時，就產生了誤碼，用根據概率關系式根據最大后驗概率譯碼準則，收到矢量

后，在所有

中，

選一個后驗概率

最大的

值，作為對

的估值

，那么對這M個

說，概率是同一值，根據上式后驗概率

值來就意味著全概率最大，因此最大后驗概率譯碼準則也稱為最大聯(lián)合概率譯碼準則。

最大根據概率關系式根據最大后驗概率譯碼準則，收到矢量后，在所有【例】信源分布

信道轉移概率矩陣

信道輸出符號Y={y1，y2，y3}，按最大后驗概率準則譯碼。

(1)根據p(xy)=p(y/x)p(x)算出全概率，用矩陣表示

(2)根據

，算出[p(y)]=[0.380.340.28]

【例】信源分布信道轉移概率矩陣信道輸出符號Y={y1(3)再由

算出后驗概率，用矩陣表示

(4)按最大后驗概率準則譯碼，在后驗概率矩陣中，每列選一最大值（矩陣中帶下劃線的值），譯為

(3)再由算出后驗概率，用矩陣表示(4)按最大后驗(5)若按最大聯(lián)合概率譯碼準則譯碼，在全概率矩陣[p(xy)]中每列選一最大值（矩陣中帶下劃線的值），也可譯出(5)若按最大聯(lián)合概率譯碼準則譯碼，在全概率矩陣[p(二．極大似然譯碼準則前面介紹的最大后驗概率譯碼準則等同于最小傳輸錯誤概率準則，從錯誤概率最小角度，該譯碼準則是最好的。在實際應用中，通常用同一信道去傳輸各種不同的信源，只知道信道的轉移概率，而不知道信源的分布，故無法計算全概率，故無法采用最大后驗概率譯碼準則進行譯碼。

在這種情況下，一般采用最大信道轉移概率來確定估值，即在收到矢量

后，在所有的

中，選一個轉移概率

最大的

值，作為對

的估值

譯碼規(guī)則。

，這一譯碼規(guī)則稱為極大似然二．極大似然譯碼準則前面介紹的最大后驗概率譯碼準則等同于最實際上，在信道輸入等概率條件下，極大似然譯碼規(guī)則也是最佳的。

輸入等概率時，有

，故

則有

實際上，在信道輸入等概率條件下，極大似然譯碼規(guī)則也是最佳的。三．平均錯誤概率對信道譯碼器估錯概率關于輸出求統(tǒng)計平均值：三．平均錯誤概率對信道譯碼器估錯概率關于輸出求統(tǒng)計平均值：【例】信源分布

信道轉移概率矩陣

，信道輸出符號Y={y1，y2，y3}。（1）計算按最大后驗概率準則譯碼的平均錯誤概率；（2）若信源等概分布，對其按極大似然譯碼準則譯碼，并求平均錯誤概率。

【解】（1）最大后驗概率準則譯碼

【例】信源分布信道轉移概率矩陣，信道輸出符號Y={y平均錯誤概率：

平均錯誤概率：（2）當信源等概分布，按最大似然函數(shù)譯碼準則譯碼，已給出信道轉移概率矩陣為

在矩陣的每列中選一最大值(矩陣中帶下劃線的值)，譯碼為

平均錯誤概率：

（2）當信源等概分布，按最大似然函數(shù)譯碼準則譯碼，已給出信道【例】考慮重復碼，信源等概率分布，采用極大似然譯碼規(guī)則進行譯碼，并計算平均錯誤概率。

根據編碼規(guī)則：

重復3次編碼，即

原信道的固有錯誤概率為p（p<0.5）的二進制對稱信道，其信道轉移概率矩陣為：

經編碼后得到的碼字是碼長為3的碼矢量，送入3次擴展信道傳輸，信道離散無記憶，擴展信道的信道轉移概率矩陣為：

【例】考慮重復碼，信源等概率分布，采用極大似然譯碼規(guī)則進行譯按極大似然譯碼準則譯碼，在矩陣的每列中選一最大值（帶下劃線的值），譯碼為：

計算平均錯誤概率，信源等概率分布

按極大似然譯碼準則譯碼，在矩陣的每列中選一最大值（帶下劃線的§5.3信道編碼定理及逆定理由于信道在傳輸過程中不可避免地拾取干擾，以致產生錯誤，選擇合適的編譯規(guī)則可以使錯誤概率盡可能小，信道編碼定理（香農第二定理）指出：信道容量C是在滿足錯誤概率pe→0時，信道所能容納的信息傳輸率的極限值?！径ɡ怼坑性胄诺谰幋a定理（香農第二定理）

對于任何離散無記憶信道DMC，存在信息傳輸率為R<C，長為n的碼，當n→∞時，平均差錯概率pe<exp{-nE(R)}→0。式中E(R)為可靠性函數(shù)，E(R)在0<R<C的范圍內為正。說明：1．設離散信道的信道容量為C，只要信息傳輸率R<C，總可以找到一種編碼方法，使得當代碼組長度n足夠長時，接收端恢復消息的誤碼率pe→0；即若R<C，有擾離散信道存在可靠性編碼。§5.3信道編碼定理及逆定理由于信道在傳輸過程中不可避免2．pe

<exp{-nE(R)}，當n增大，則pe急劇減?。籲→∞，pe→0；

3．可靠性函數(shù)E(R)：只要R<C，則E(R)>0。

【定理】信道編碼逆定理

信道容量C是可靠通信系統(tǒng)信息傳輸率的上界，當R>C，不可能存在任何方法使差錯概率任意小。也就是說，當R>C時，誤碼率有一固定下界值，即使增加代碼組長度n，也不能使誤碼率任意小，即，R>C，不存在可靠性編碼。2．pe<exp{-nE(R)}，當n增大，則pe急信道譯碼器信道譯碼器第5章有噪信道編碼第5章內容提要本章介紹了信道編碼和譯碼的基本概念，介紹了兩種常用的譯碼準則：最大后驗概率譯碼準則和極大似然譯碼準則,還介紹了在這兩種譯碼準則下錯誤概率的計算方法。本章還介紹了信道編碼定理及信道編碼逆定理，以及信息論中的一個重要不等式Fnao不等式。內容提要本章介紹了信道編碼和譯碼的基本概念，介紹了兩種常用的§5.1信道編碼的基本概念

我們要盡可能的提高信息傳輸率，并控制傳輸誤差。信源編碼以提高傳輸效率作為主要考慮因素，信道編碼以提高傳輸可靠性作為主要考慮因素。信道有多種形式，如電視、廣播、微波、電話、計算機局域網和寬帶網等，對于所有的信道可用下圖所示的模型來表示：§5.1信道編碼的基本概念我們要盡可能的提高信息傳輸率，并衡量信道傳輸快慢的指標是信息傳輸率，而衡量信息傳輸可靠性的指標是平均錯誤概率，平均錯誤概率與信道的統(tǒng)計特性有關。要改變信道統(tǒng)計特性成本太大，所以可事先對信源編碼器輸出的符號序列按照某種規(guī)則進行編碼，一般的方法是給信源序列加上一定的冗余度，這種編碼稱為信道編碼，編好的代碼稱為碼字，將碼字送入信道傳輸，在信道的輸出端，信道譯碼器根據編碼規(guī)則對信道輸出符號進行估值，盡量使這種估值接近輸入碼字。信源輸出序列，經信道編碼器編成碼字并輸入信道，由于干擾，信道輸出，信道譯碼器對估值得。衡量信道傳輸快慢的指標是信息傳輸率，而衡量信息傳輸可靠性的指【例】給定二元對稱信道，信道固有錯誤概率為p（p<0.5）編碼規(guī)則：為提高可靠性，每個信道符號重復三次發(fā)送。

譯碼規(guī)則：擇多譯碼，即信宿方收到的三個符號中有兩個或三個為1，就將此次接收符號判決為1；若三個符號中有兩個或三個為0，就將此次接收符號判決為0。

下面為重復編碼傳輸示意圖，計算錯誤概率pe?！纠拷o定二元對稱信道，信道固有錯誤概率為p（p<0.5信源輸出序列為：

信道輸入序列為：

由于p的存在，使得傳輸出錯，故信道輸出為：

根據譯碼規(guī)則，信道估值輸出：

信道錯誤概率：假設信道離散無記憶，即

錯誤概率為：

重復編碼的結果使錯誤概率下降。

信源輸出序列為：信道輸入序列為：由于p的存在，使得傳輸出【例】逆重復碼離散無記憶二進制對稱信道，固有誤碼率為p(p<0.5)，信源輸出序列為三位二進制數(shù)字。編碼規(guī)則：為提高傳輸效率，僅向信道發(fā)送一位，預先將信源輸出序列進行擇多編碼：信源輸出的三位符號中有兩位或3位是1，信源序列編碼為1，若三位符號中有兩位或3位是0，就將此信源序列編碼為0。譯碼規(guī)則：將接收的一位符號重復三次譯出，即若接收到1就譯碼為111，即若接收到0就譯碼為000。下面為重復編碼傳輸示意圖，計算錯誤概率pe?！纠磕嬷貜痛a離散無記憶二進制對稱信道，固有誤碼率為p(（1）先設p=0，計算這種編碼方法帶來的固有錯誤p1。信道輸入符號集

X={000，001，010，011，100，101，110，111}

判決輸出符號集Y={000，111}

譯碼規(guī)則：

因為后驗概率：

則出錯概率：

（1）先設p=0，計算這種編碼方法帶來的固有錯誤p1假設8組輸入序列是等概發(fā)送的，由于信道的對稱性，兩個估值序列也是等概分布的，則每個序列的平均錯誤概率為:誤比特率（2）再設p≠0，計算由于信道噪聲引起的錯誤概率p2。

因為每個序列有三位二進制數(shù)字，但只發(fā)送一位，這一位的出錯概率為p，故序列差錯概率為p，誤比特率（3）總差錯概率（誤比特率）：假設8組輸入序列是等概發(fā)送的，由于信道的對稱性，兩個估值序列【例】奇偶校驗碼在信息序列后面加上一位校驗位，使之模2和等于1，這樣的編碼稱為奇校驗碼；若使模2和等于0，這樣的編碼就稱為偶校驗碼，即每個碼矢中1的個數(shù)固定為奇數(shù)或偶數(shù)。奇偶校驗碼能檢測出奇數(shù)位錯誤，但無法判斷錯的是哪一位，故沒有糾錯能力。這種編碼方式可用在反饋信道場合，如計算機通信串口通信。【例】奇偶校驗碼在信息序列后面加上一位校驗位，使之模2和等§5.2譯碼規(guī)則及錯誤概率信道總不可避免會攙雜噪聲，所以信息在信道傳輸過程中，差錯是不可避免的。選擇合適的譯碼規(guī)則可以彌補信道的不足?！纠緽SC信道的轉移概率如下

時，這是一種強噪聲信道，在這種情況下，若按常規(guī)譯碼，肯定出錯，但可將判決取反，收到0判為1，收到1判為0，反而正確?？梢娮g碼規(guī)則對傳輸系統(tǒng)錯誤概率的影響是很大的。

§5.2譯碼規(guī)則及錯誤概率信道總不可避免會攙雜噪聲，所一．最大后驗概率譯碼準則設信源有M個消息，信道編碼器已用M個碼矢

對它進行了最佳編碼。

編碼后發(fā)送碼矢量，其發(fā)送概率為，通過信道轉移概率為的信道傳輸，接收矢量為，信道譯碼器輸出。通信過程框圖如下：

一．最大后驗概率譯碼準則設信源有M個消息，信道編碼器已用M個當估值時，就產生了誤碼，用表示后驗概率，則收到估錯的錯誤概率為：通信總希望錯誤概率最小，由上式可看出錯誤概率最小等同于后驗概率最大，這就是最大后驗概率譯碼準則。當估值時，就產生了誤碼，用根據概率關系式根據最大后驗概率譯碼準則，收到矢量

后，在所有

中，

選一個后驗概率

最大的

值，作為對

的估值

，那么對這M個

說，概率是同一值，根據上式后驗概率

值來就意味著全概率最大，因此最大后驗概率譯碼準則也稱為最大聯(lián)合概率譯碼準則。

最大根據概率關系式根據最大后驗概率譯碼準則，收到矢量后，在所有【例】信源分布

信道轉移概率矩陣

信道輸出符號Y={y1，y2，y3}，按最大后驗概率準則譯碼。

(1)根據p(xy)=p(y/x)p(x)算出全概率，用矩陣表示

(2)根據

，算出[p(y)]=[0.380.340.28]

【例】信源分布信道轉移概率矩陣信道輸出符號Y={y1(3)再由

算出后驗概率，用矩陣表示

(4)按最大后驗概率準則譯碼，在后驗概率矩陣中，每列選一最大值（矩陣中帶下劃線的值），譯為

(3)再由算出后驗概率，用矩陣表示(4)按最大后驗(5)若按最大聯(lián)合概率譯碼準則譯碼，在全概率矩陣[p(xy)]中每列選一最大值（矩陣中帶下劃線的值），也可譯出(5)若按最大聯(lián)合概率譯碼準則譯碼，在全概率矩陣[p(二．極大似然譯碼準則前面介紹的最大后驗概率譯碼準則等同于最小傳輸錯誤概率準則，從錯誤概率最小角度，該譯碼準則是最好的。在實際應用中，通常用同一信道去傳輸各種不同的信源，只知道信道的轉移概率，而不知道信源的分布，故無法計算全概率，故無法采用最大后驗概率譯碼準則進行譯碼。

在這種情況下，一般采用最大信道轉移概率來確定估值，即在收到矢量

后，在所有的

中，選一個轉移概率

最大的

值，作為對

的估值

譯碼規(guī)則。

，這一譯碼規(guī)則稱為極大似然二．極大似然譯碼準則前面介紹的最大后驗概率譯碼準則等同于最實際上，在信道輸入等概率條件下，極大似然譯碼規(guī)則也是最佳的。

輸入等概率時，有

，故

則有

實際上，在信道輸入等概率條件下，極大似然譯碼規(guī)則也是最佳的。三．平均錯誤概率對信道譯碼器估錯概率關于輸出求統(tǒng)計平均值：三．平均錯誤概率對信道譯碼器估錯概率關于輸出求統(tǒng)計平均值：【例】信源分布

信道轉移概率矩陣

，信道輸出符號Y={y1，y2，y3}。（1）計算按最大后驗概率準則譯碼的平均錯誤概率；（2）若信源等概分布，對其按極大似然譯碼準則譯碼，并求平均錯誤概率。

【解】（1）最大后驗概率準則譯碼

【例】信源分布信道轉移概率矩陣，信道輸出符號Y={y平均錯誤概率：

平均錯誤概率：（2）當信源等概分布，按最大似然函數(shù)譯碼準則譯碼，已給出信道轉移概率矩陣為

在矩陣的每列中選一最大值(矩陣中帶下劃線的值)，譯碼為

平均錯誤概率：

（2）當信源等概分布，按最大似然函數(shù)譯碼準則譯碼，已給出信道【例】考慮重復碼，信源等概率分布，采用極大似然譯