有噪信道編碼定理.ppt

《有噪信道編碼定理.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《有噪信道編碼定理.ppt（32頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2020/7/23,1/17,理信學(xué)院 孫桂萍,有噪信道編碼定理,2020/7/23,2/17,理信學(xué)院 孫桂萍,主要內(nèi)容,錯(cuò)誤概率和譯碼規(guī)則 最大后驗(yàn)概率準(zhǔn)則 最大似然譯碼準(zhǔn)則 錯(cuò)誤概率與編碼方法 最小距離譯碼準(zhǔn)則,2020/7/23,3/17,理信學(xué)院 孫桂萍,信道編碼的目的,從信道編碼的構(gòu)造方法看，信道編碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼中加入一些人為多余的碼元，以保證傳輸過程可靠性。信道編碼的任務(wù)就是構(gòu)造出以最小的冗余度代價(jià)換取最大抗干擾性能的“好碼”。,2020/7/23,4/17,理信學(xué)院 孫桂萍,信道的統(tǒng)計(jì)特性,錯(cuò)誤概率與信道的統(tǒng)計(jì)特性有關(guān)，而信道的統(tǒng)計(jì)特性可由信道的傳

2、遞矩陣描述。 二元對(duì)稱信道，錯(cuò)誤的傳遞概率為p，正確的為1-p：,信道矩陣,2020/7/23,5/17,理信學(xué)院 孫桂萍,錯(cuò)誤概率不僅與信道的統(tǒng)計(jì)特性有關(guān)，還與接收端的譯碼規(guī)則有關(guān)。,譯碼規(guī)則a： 收到“0”譯成“0”；收到“1”譯成“1” 在規(guī)則a確定的情況下，錯(cuò)誤概率為： 發(fā)送“0”，收到“0”，譯成“0”正確的譯碼，譯碼正確的概率為1/3； 發(fā)送“0”，收到“1”，譯成“1”錯(cuò)誤的譯碼，譯碼錯(cuò)誤的概率為2/3,錯(cuò)誤概率與譯碼規(guī)則的關(guān)系,2020/7/23,6/17,理信學(xué)院 孫桂萍,,因?yàn)槭菍?duì)稱信道，那么發(fā)送“1”，錯(cuò)譯成“0”的概率也為2/3。 在此譯碼規(guī)則下，平均錯(cuò)誤概率PE 這

3、里，假設(shè)輸入端等概率分布。,2020/7/23,7/17,理信學(xué)院 孫桂萍,譯碼規(guī)則b： 收到“0”譯成“1”；收到“1”譯成“0” 在規(guī)則b確定的情況下，錯(cuò)誤概率為： 發(fā)送“0”，收到“1”，譯成“0”正確的譯碼，譯碼正確的概率為2/3； 發(fā)送“0”，收到“0”，譯成“1”錯(cuò)誤的譯碼，譯碼錯(cuò)誤的概率為1/3,在此譯碼規(guī)則下，平均錯(cuò)誤概率PE,可見，譯錯(cuò)的可能性減少，譯對(duì)的可能性增加了。,2020/7/23,8/17,理信學(xué)院 孫桂萍,譯碼規(guī)則,數(shù)學(xué)定義：設(shè)離散單符號(hào)信道的輸入符號(hào)集為A=ai，i=1,2,,r；輸出符號(hào)集為B=bj，j=1,2,,s。制定譯碼規(guī)則就是設(shè)計(jì)一個(gè)函數(shù)F(bj)，它

4、對(duì)于每一個(gè)輸出符號(hào)bj確定一個(gè)唯一的輸入符號(hào)ai與其對(duì)應(yīng)。 每一個(gè)輸入符號(hào)可以對(duì)應(yīng)于多個(gè)輸出符號(hào)，也就是s個(gè)輸出符號(hào)中的每一個(gè)都可以譯成r個(gè)輸入符號(hào)中的任何一個(gè)，所以共有r s種譯碼規(guī)則。,2020/7/23,9/17,理信學(xué)院 孫桂萍,譯碼規(guī)則舉例,例6.1：有一離散單符號(hào)信道，信道矩陣為：,針對(duì)于這種信道，設(shè)計(jì)兩種譯碼規(guī)則：,2020/7/23,10/17,理信學(xué)院 孫桂萍,平均錯(cuò)誤概率,譯碼規(guī)則的選取原則是使得平均錯(cuò)誤概率盡可能小。 在確定了譯碼規(guī)則F(bj)后，若 收到的為bj ，譯成ai，發(fā)送的是ai正確 收到的為bj ，譯成ai，發(fā)送的不是ai錯(cuò)誤 條件正確概率為： 條件錯(cuò)誤概

5、率為：,2020/7/23,11/17,理信學(xué)院 孫桂萍,平均錯(cuò)誤概率,平均錯(cuò)誤概率PE應(yīng)是條件錯(cuò)誤概率對(duì)所有的Y求統(tǒng)計(jì)平均。,為了是PE盡可能的小，對(duì)于“=”右側(cè)的每個(gè)求和項(xiàng)都是非負(fù)的，所以應(yīng)使得每個(gè)項(xiàng)盡量的小，而且譯碼規(guī)則只影響條件錯(cuò)誤概率，對(duì)P(bj)沒有影響，所以應(yīng)選取譯碼規(guī)則使得條件錯(cuò)誤概率盡量的小，那么也就是尋找條件正確概率盡量的大。,2020/7/23,12/17,理信學(xué)院 孫桂萍,最大后驗(yàn)概率準(zhǔn)則,數(shù)學(xué)描述 選擇譯碼函數(shù)：,并使之滿足條件,文字描述 采用一個(gè)譯碼函數(shù)，它對(duì)于每一個(gè)輸出符號(hào)均譯成具有最大后驗(yàn)概率的那個(gè)輸入符號(hào)，則信道錯(cuò)誤概率能達(dá)到最小，這種譯碼規(guī)則稱為最大后驗(yàn)

6、概率準(zhǔn)則或最小錯(cuò)誤概率準(zhǔn)則。,2020/7/23,13/17,理信學(xué)院 孫桂萍,最大后驗(yàn)概率準(zhǔn)則另一種描述,因?yàn)橐话阋阎獋鬟f概率 和輸入符號(hào)的先驗(yàn)概率 ，所以將 根據(jù)貝葉斯定律改寫為：,一般P(bj)不等于0，最大后驗(yàn)概率可表示為：選擇譯碼函數(shù)： 使?jié)M足,1式,2020/7/23,14/17,理信學(xué)院 孫桂萍,最大似然譯碼準(zhǔn)則,若輸入符號(hào)的先驗(yàn)概率 均相等，則1式可寫為： 數(shù)學(xué)描述： 選擇譯碼函數(shù)：,并滿足：,文字描述 選擇譯碼函數(shù)，收到bj后，譯成信道矩陣P的第j列中最大那個(gè)元素所對(duì)應(yīng)的信源符號(hào)。 注意：最大似然譯碼準(zhǔn)則對(duì)于先驗(yàn)概率等概率分布時(shí)才可使得錯(cuò)誤概率P

7、E最小。,2020/7/23,15/17,理信學(xué)院 孫桂萍,平均錯(cuò)誤概率的計(jì)算,求和：可先列后行或先行后列，也就是說對(duì)于聯(lián)合概率矩陣中可先求每列中除去 所對(duì)應(yīng)的以外所有元素，再對(duì)各列求和；也可以先對(duì)行i求和，除去譯碼規(guī)則中 所對(duì)應(yīng)的 ，然后再對(duì)各行求和。,2020/7/23,16/17,理信學(xué)院 孫桂萍,平均錯(cuò)誤概率的計(jì)算,如果先驗(yàn)概率 是等概率的 ，則PE為：,2020/7/23,17/17,理信學(xué)院 孫桂萍,例題6.2,已知信道矩陣如下，根據(jù)最大似然譯碼選取譯碼規(guī)則，并計(jì)算平均錯(cuò)誤概率。若輸入不等概，概率分別為1/4，1/4，1/2，比較按照最大似然譯碼準(zhǔn)則和最大

8、后驗(yàn)概率準(zhǔn)則選取的譯碼規(guī)則的PE,2020/7/23,18/17,理信學(xué)院 孫桂萍,費(fèi)諾不等式,平均錯(cuò)誤概率與譯碼規(guī)則有關(guān)，而譯碼規(guī)則又由信道特性決定，由于錯(cuò)誤的存在，所以當(dāng)收到某符號(hào)后對(duì)發(fā)送端仍存在不確定性?？梢姡琍E與信道疑義度有關(guān)：,費(fèi)諾不等式,2020/7/23,19/17,理信學(xué)院 孫桂萍,對(duì)于此二元對(duì)稱信道（假設(shè)等概）可以利用最大似然譯碼準(zhǔn)則選取譯碼規(guī)則，使得PE盡量的小。 F(b1)=a1 F(b2)=a2 注：b1=a1=0，b2=a2=1 PE=0.5*0.01+0.5*0.01=0.01 一般要求在-6到-9數(shù)量級(jí)上。,錯(cuò)誤概率與編碼方法的關(guān)系,,,,,0 輸入 1,

9、0 輸出 1,/p=0.99,p=0.01,二元對(duì)稱信道,0.01,0.99,例1,,2020/7/23,20/17,理信學(xué)院 孫桂萍,碼一：重復(fù)編碼 將待發(fā)送的消息碼重復(fù)發(fā)送幾遍，可以減小錯(cuò)誤的發(fā)生，提高可靠性。例如，重發(fā)三次，n=3 輸入序列 （i） 輸出序列（j） 000（許用碼字） 000 001 001 010 010 011 011 100 100 101 101 110 110 111 （許用碼字） 1

10、11,,輸出序列8種可能，每一位都可能出錯(cuò),2020/7/23,21/17,理信學(xué)院 孫桂萍,碼一：重復(fù)編碼（n=3）的PE 利用最大似然譯碼準(zhǔn)則選取譯碼規(guī)則時(shí)需要知道信道矩陣，可計(jì)算得,依據(jù)最大似然譯碼準(zhǔn)則，應(yīng)選取信道矩陣的每列中最大的那個(gè)傳遞概率對(duì)應(yīng)的輸入符號(hào)即為該列對(duì)應(yīng)的輸出要譯成的輸入符號(hào)。 在此規(guī)則下求出PE： 與發(fā)送單個(gè)符號(hào)相 比，平均錯(cuò)誤概率 減小了兩個(gè)數(shù)量級(jí),,2020/7/23,22/17,理信學(xué)院 孫桂萍,重復(fù)編碼可以使平均錯(cuò)誤概率減小的原因 重復(fù)編碼三次時(shí)，1(000)對(duì)應(yīng)的輸出序列為 1(000)， 2 (001) ， 3 (010) ， 5 (100) ， 與1比

11、較之后可發(fā)現(xiàn)，或是相同，或是發(fā)生了一位錯(cuò)誤，但是譯碼的結(jié)果都是正確的，降低了譯錯(cuò)的可能性，平均錯(cuò)誤概率減小了。 若繼續(xù)增大n，PE可逐漸減小，n可以無限增大嗎？,,2020/7/23,23/17,理信學(xué)院 孫桂萍,答案是否定的，n不可以無限量增大 因?yàn)閚增大的同時(shí)，會(huì)降低信息傳輸率 編碼后的信道的信息傳輸率 R=log M / n（比特/碼符號(hào)） M不變的情況下，n增大，R變小 所以不能為了使平均錯(cuò)誤概率降低而一味的增大n。 尋找好的編碼方法的思路： 找到一種編碼方法，使PE相當(dāng)?shù)?，但R能保持在一定水平。,2020/7/23,24/17,理信學(xué)院 孫桂萍,碼二：將8個(gè)符號(hào)均作為許用

12、碼字傳送 M=8，log M=3，R=log M / n=3/3=1 同樣利用最大似然譯碼準(zhǔn)則選取譯碼規(guī)則，并可求得 PE =3*10-2 ，比10-2還大。 可發(fā)現(xiàn)，在二元信道的n次擴(kuò)展信道中有2n個(gè)輸入，從中取出M個(gè)做許用碼字，M大， PE大，R大； M小， PE小，R小。,,2020/7/23,25/17,理信學(xué)院 孫桂萍,碼三：在這個(gè)二元三次擴(kuò)展信道中，取M=4再比較一下PE和R 取000， 011，101，110 PE =2*10-2， R=2/3,與M=8比較都變小了。 從8個(gè)中取4個(gè)有70種方法，選兩組比較一下,比較一下兩組碼的特點(diǎn)，分析為什么第組的平均錯(cuò)誤概率大,2020

13、/7/23,26/17,理信學(xué)院 孫桂萍,碼四：M=4，n=5，從二元五次擴(kuò)展信道中32個(gè)輸入符號(hào)中取4個(gè)，再比較一下PE和R R=log4 /5=2/5,PE =7.8*10-4,結(jié)論：增大了n，并適當(dāng)?shù)脑龃驧及合適的編碼方法，即可達(dá)到希望的結(jié)果,重點(diǎn)比較一下M=4，n=3的情況，R略降，但PE卻減少很多,2020/7/23,27/17,理信學(xué)院 孫桂萍,漢明距離：碼字對(duì)應(yīng)位置上不同碼元的個(gè)數(shù)D（ i ， j ） 兩個(gè)二元碼字Ci和Cj的距離等于對(duì)應(yīng)位置上碼元的模二和。 碼C的最小距離：這個(gè)碼C中，任意兩個(gè)碼字的漢明距離的最小值dmin。,碼字距離,2020/7/23,28/17,

14、理信學(xué)院 孫桂萍,,,2020/7/23,29/17,理信學(xué)院 孫桂萍,最小距離譯碼準(zhǔn)則,選擇譯碼函數(shù),使?jié)M足,即滿足,注意：二元對(duì)稱信道中最小距離譯碼準(zhǔn)則等于最大似然譯碼準(zhǔn)則。,文字描述： 二元信道中最大似然譯碼準(zhǔn)則可表述為：當(dāng)收到j(luò)后，譯成與之距離最近的輸入碼字* 。,2020/7/23,30/17,理信學(xué)院 孫桂萍,總結(jié) 編碼，應(yīng)采用選擇M個(gè)消息所對(duì)應(yīng)的碼字之間最小距離dmin盡可能的大。 譯碼，將接收的序列j譯成與之距離最近的那個(gè)碼字* 。,2020/7/23,31/17,理信學(xué)院 孫桂萍,有噪信道編碼定理,對(duì)于離散無記憶信道，P(y/x)為信道傳遞概率，其信道容量為C。當(dāng)信息傳輸率R