中南大學(xué)信息論與編碼講義引言.ppt

1、信息論與編碼,主講教師：何毅,教材參考及參考書,教材：Robert J.McEliece著 李斗等譯，信息論與編碼理論，電子工業(yè)出版社，2004.2 參考書：姜丹，信息論與編碼，中國(guó)科學(xué)技術(shù)大學(xué)出版社，2001.8曹雪虹，信息論與編碼，清華大學(xué)出版社，2004,引言,本書研究的內(nèi)容 信息論的形成和發(fā)展 幾個(gè)概念 幾個(gè)編碼 信道編碼定理,本課程研究的內(nèi)容,信息論研究的內(nèi)容非常廣泛，本書的研究的內(nèi)容。分為兩個(gè)部分：信息論與編碼。 信息論主要從理論上解決下面的問(wèn)題： （1）什么是信息？如何度量信息？ （2）在信息傳輸中，基本的極限條件是什么？ （3）信息的壓縮和恢復(fù)的極限條件是什么？ （4）從環(huán)境中

2、抽取信息的極限條件是什么？ （5）設(shè)計(jì)什么樣的設(shè)備才能達(dá)到這些極限？ （6）實(shí)際上接近極限的設(shè)備是否存在,本課程研究的內(nèi)容,具體來(lái)說(shuō)，第一部分講解了香農(nóng)信息論與編碼理論的主要內(nèi)容，如熵和信息量的基本概念與性質(zhì)，以及信道、信源編碼定理。 第二部分介紹了一些香農(nóng)編碼理論的信道和信源編碼方法，具體包括線性碼、循環(huán)碼、BCH和RS碼、卷積碼等信道糾錯(cuò)編碼，以及變長(zhǎng)信源編碼等,信息論的形成和發(fā)展,20世紀(jì)20年代奈奎斯特（Nyquist，H）和哈特萊（Hartley，LVR）提出了信息的定義 1924年奈奎斯特解釋了信號(hào)帶寬和信息速率之間的關(guān)系 1928哈特萊最早研究了通信系統(tǒng)傳輸信息的能力，給出了信息

3、度量方法 1936年阿姆斯特朗（Armstrong）提出了增大帶寬可以使抗干擾能力加強(qiáng),信息論的形成和發(fā)展,19411944年香農(nóng)對(duì)通信和密碼進(jìn)行深人研究，用概率論的方法研究通信系統(tǒng)，揭示了通信系統(tǒng)傳遞的對(duì)象就是信息，并對(duì)信息給以科學(xué)的定量描述，提出了信息熵的概念。指出通信系統(tǒng)的中心問(wèn)題是在噪聲下如何有效而可靠地傳送信息以及實(shí)現(xiàn)這一目標(biāo)的主要方法是編碼等。香農(nóng)因此成為信息論的奠基人,信息論的形成和發(fā)展,60年代信道編碼技術(shù)有較大進(jìn)展，使它成為信息論的又一重要分支；信源編碼的研究落后于信道編碼。香農(nóng) 1959年的文章(Coding theorems for a discrete source w

4、ith a fidelity criterion)系統(tǒng)地提出了信息率失真理論，它是數(shù)據(jù)壓縮的數(shù)學(xué)基礎(chǔ)，為各種信源編碼的研究奠定了基礎(chǔ),信息論的形成和發(fā)展,到70年代，有關(guān)信息論的研究，從點(diǎn)與點(diǎn)間的單用戶通信推廣到多用戶系統(tǒng)的研究。到目前為止，多用戶信息論研究得不多，還有許多尚待解決的課題,幾個(gè)概念,信息、消息、信號(hào)、數(shù)據(jù) 信源、信道,信息,信息是指各個(gè)事物運(yùn)動(dòng)的狀態(tài)及狀態(tài)變化的方式。人們從來(lái)自對(duì)周圍世界的觀察得到的數(shù)據(jù)中獲得信息。信息是抽象的意識(shí)或知識(shí)，它是看不見(jiàn)、摸不到的。人腦的思維活動(dòng)產(chǎn)生的一種想法，當(dāng)它仍儲(chǔ)存在腦子中的時(shí)候它就是一種信息,消息,消息是指包含有信息的語(yǔ)言、文字和圖像等，例如

5、我們每天從廣播節(jié)目、報(bào)紙和電視節(jié)目中獲得各種新聞及其他消息。消息是具體的，它載荷信息，但它不是物理性的,信號(hào),信號(hào)是消息的物理體現(xiàn)，為了在信道上傳輸消息，就必須把消息加載（調(diào)制）到具有某種物理特征的信號(hào)上去。信號(hào)是信息的載荷子或載體，是物理性的。如電信號(hào)、光信號(hào)等,信號(hào),按照信息論或控制論的觀點(diǎn)，在通信和控制系統(tǒng)中傳送的本質(zhì)內(nèi)容是信息，系統(tǒng)中實(shí)際傳輸?shù)膭t是測(cè)量的信號(hào)，信息包含在信號(hào)之中，信號(hào)是信息的載體。信號(hào)到了接收端（信息論里稱為信宿）經(jīng)過(guò)處理變成文字、語(yǔ)聲或圖像，人們?cè)購(gòu)闹械玫接杏玫男畔?數(shù)據(jù),載有信息的可觀測(cè)、可傳輸、可存儲(chǔ)及可處理的信號(hào)均稱為數(shù)據(jù),二進(jìn)制對(duì)稱信源,是一個(gè)可以發(fā)出定義為“

6、0”、“1”的兩種特定的實(shí)體，數(shù)率為單位時(shí)間內(nèi)R個(gè)符號(hào)。稱這些符號(hào)為比特(bits，binary digits)。信源隨機(jī)地發(fā)出這些比特“0”、“1”的數(shù)率概率相同,二進(jìn)制對(duì)稱信道,簡(jiǎn)稱BSC，是一個(gè)單位時(shí)間內(nèi)可以傳送1比特?cái)?shù)據(jù)的實(shí)體。但是該信道并不是完全可靠的：存在一個(gè)固定的概率p(稱為原始誤比特率)，滿足0p1/2，使輸出比特與輸入比特不相同,重復(fù)編碼-多票判決譯碼,R=1/3,信源輸出： 1 0 1 0 0 信道編碼：111 000 111 000 000 信道輸出：101 011 111 001 100 信道解碼： 1 1 1 0 0 用Pe表示誤比特率 Pe =P2個(gè)信道錯(cuò)誤+P3個(gè)

7、信道錯(cuò)誤 =3p2(1-p)+ p3 =3p2-2p3 p,重復(fù)編碼-多票判決譯碼,R=1/(2n+1,對(duì)于原始誤比特率p1/2的固定BSC，當(dāng)n時(shí)，Pe0，即通過(guò)這些重復(fù)編碼方式，可以使信道達(dá)到理想的可靠度,拋硬幣方式編碼,R1，只傳輸信源比特的1/R部分，并讓接收者以拋硬幣的方式猜測(cè)其余的部分,多票判決編碼-重復(fù)譯碼,R=3,信源輸出：101 110 101 000 101 信道編碼： 1 1 1 0 1 信道輸出： 1 0 1 0 1 信道解碼：111 000 111 000 111 Pe =1/4(1-p)+3/4p=1/4+p/2。 比“拋硬幣”方式1/3+p/3小,多票判決編碼-重

8、復(fù)譯碼,R=2n+1,4,7)漢明碼,R=4/7。 編碼方式,信源的4個(gè)比特為：x0, x1, x2, x3，附加3個(gè)比特奇偶校驗(yàn)碼x4, x5, x6： x4x1+ x2+ x3 (mod 2) x5=x0+ x2+ x3 (mod 2) x6=x0+ x1+ x3 (mod 2) 舉例： 信源輸出：0110 信道編碼：0110011,4,7)漢明碼,譯碼分析,按下面方式重寫奇偶校驗(yàn)式： x1+x2+x3+x4 =0 x0+ x2+x3 +x5 =0 x0+ x1 +x3 +x6=0 定義二進(jìn)制矩陣H為,16個(gè)可能的碼字x=(x0, x1, x2, x3, x4, x5, x6)都滿足矩陣方

9、程,4,7)漢明碼,譯碼分析,如果傳輸?shù)氖鞘噶縳，則接收的是矢量y=x+z。z=(z0,z1,z6)稱為錯(cuò)誤圖案。 定義矢量s=(s0,s1,s6)為y的伴隨式(syndrome,4,7)漢明碼,譯碼分析,一旦計(jì)算出s，就通過(guò)方程sT=HzT求解z。但只有三個(gè)方程卻有七個(gè)未知量，因此對(duì)任一s，總有16個(gè)可能的z。 例如：接收到y(tǒng)=(0111001)，則s=(101)，z的16個(gè)候選值為： 01000000010011110001100010100000101011100101101101010000 0101111100100110001101111010 1110101001110011011001011111 最佳估計(jì)是z=(0100000)。從而對(duì)傳輸字的估計(jì)是x=y+z=(0011001)。最終估計(jì)四個(gè)信源比特是(0011)。 對(duì)于任意伴隨式s，HzT=sT總存在重量為0或1的唯一解。若s0，則sT必為H中的每一列,4,7)漢明碼,譯碼算法,1、計(jì)算伴隨式sT=HyT。 2、如果s=0，設(shè)置z=0；到第四步。 3、尋找H中的唯一與s相同的列，使其對(duì)應(yīng)的位為1，其余為0。 4、設(shè)置x=y+z。 5、輸出x 的前四個(gè)分量(x0,x1,x2,x3,4,7)漢明碼,誤組率PE=Pxx,Pe(i)表示誤比特率Pxixi,7,4)漢明碼,R=7/4,編碼