YN第1章信息論與編碼理論

ThomasM.Cover.ElementsofInformationTheory.

清華大學(xué)出版社影印版朱雪龍.應(yīng)用信息論基礎(chǔ).清華大學(xué)出版社傅祖蕓.信息論-基礎(chǔ)理論與應(yīng)用.電子工業(yè)出版社王育民.信息論與編碼理論.高等教育出版社.參考書第一頁(yè)，共41頁(yè)。第一頁(yè)，共41頁(yè)。第二頁(yè)，共41頁(yè)。第二頁(yè)，共41頁(yè)。閉卷+課程論文平時(shí)成績(jī)20%+論文成績(jī)20%+考試成績(jī)60%考核方式第三頁(yè)，共41頁(yè)。第三頁(yè)，共41頁(yè)。第一章緒論第四頁(yè)，共41頁(yè)。第四頁(yè)，共41頁(yè)。第一章緒論什么是信息？信息論研究什么？編碼研究什么？如何研究?第五頁(yè)，共41頁(yè)。第五頁(yè)，共41頁(yè)。2個(gè)重要概念信息是不確定性的：隨機(jī)性信息需要用數(shù)字信號(hào)：0和1來(lái)傳輸?shù)诹?yè)，共41頁(yè)。第六頁(yè)，共41頁(yè)。2個(gè)基本理論信源編碼理論：數(shù)據(jù)壓縮的臨界最小值信道編碼理論：數(shù)據(jù)傳輸?shù)呐R界最大值第七頁(yè)，共41頁(yè)。第七頁(yè)，共41頁(yè)。1.1通信系統(tǒng)模型和信息的概念1.2信息論研究的中心問(wèn)題及發(fā)展1.3shannon信息論的局限性1.4信息的廣義性第八頁(yè)，共41頁(yè)。第八頁(yè)，共41頁(yè)。1.1通信系統(tǒng)模型和信息的概念第九頁(yè)，共41頁(yè)。第九頁(yè)，共41頁(yè)。1、通信系統(tǒng)模型信源編碼器信道譯碼器信宿干擾源通信系統(tǒng)的基本任務(wù)要求可靠:要使信源發(fā)出的消息經(jīng)過(guò)傳輸后，盡可能準(zhǔn)確地、不失真或限定失真地再現(xiàn)在接收端有效:用盡可能短的時(shí)間和盡可能少的設(shè)備來(lái)傳輸最大的消息第十頁(yè)，共41頁(yè)。第十頁(yè)，共41頁(yè)。通信系統(tǒng)模型進(jìn)一步細(xì)分信源信源編碼器信道編碼器調(diào)制器信道干擾源解調(diào)器信道譯碼器信源譯碼器信宿等效離散信道等效離散信源等效信宿信道編碼器信道譯碼器第十一頁(yè)，共41頁(yè)。第十一頁(yè)，共41頁(yè)。2、信息的概念：信息、消息和信號(hào)信息一個(gè)抽象的概念，可以定量的描述。信息、物質(zhì)和能量是構(gòu)成一切系統(tǒng)的三大要素。消息中的有效內(nèi)容。消息是信息的載體，相對(duì)具體的概念，如語(yǔ)言，文字，數(shù)字，圖像。信號(hào)表示消息的物理量，電信號(hào)的幅度，頻率，相位等等。一般在通信領(lǐng)域表示消息的電信號(hào)。第十二頁(yè)，共41頁(yè)。第十二頁(yè)，共41頁(yè)。3、香農(nóng)信息的定義收信者在收到消息前不知道消息的具體內(nèi)容；通信的結(jié)果是消除不確定性從而獲得信息。干擾源信源信道信宿第十三頁(yè)，共41頁(yè)。第十三頁(yè)，共41頁(yè)。信息的定義信息是事物運(yùn)動(dòng)狀態(tài)或存在方式的不確定性的描述不僅僅是形式上的消息或情報(bào)，而且包括消息或情報(bào)所含的對(duì)事物狀態(tài)或不確定性的描述第十四頁(yè)，共41頁(yè)。第十四頁(yè)，共41頁(yè)?！澳覆∮?、收?qǐng)?bào)人之前不知道任何相關(guān)信息，也不知道有人給他發(fā)報(bào)——不確定性2、是關(guān)于身體健康的描述——是動(dòng)態(tài)的、隨機(jī)的3、收到報(bào)文后，報(bào)文清楚，則不確定性消除；報(bào)文不清——有可能消除一部分不確定性，不確定性減少，獲得一部分信息；或不確定性沒(méi)有減少，沒(méi)有獲得信息。第十五頁(yè)，共41頁(yè)。第十五頁(yè)，共41頁(yè)。4、香農(nóng)信息的度量天氣預(yù)測(cè)：晴雪；中獎(jiǎng)（1）樣本空間：某試驗(yàn)中各種可能出現(xiàn)的狀態(tài)的集合；或者所有消息的集合（2）概率測(cè)度：每一個(gè)可能的離散消息指定的概率（3）概率空間：一個(gè)樣本空間和它的消息測(cè)度稱為一個(gè)概率空間第十六頁(yè)，共41頁(yè)。第十六頁(yè)，共41頁(yè)。（4）自信息：如果事件ai發(fā)生的概率p(ai),事件ai發(fā)生所含有的信息量，就稱為自信息量，表示為平均信息量、熵（5）互信息：先驗(yàn)的不確定性減去尚存在的不確定性——是兩個(gè)隨機(jī)變量相互之間獨(dú)立程度的度量。先驗(yàn)概率:后驗(yàn)概率第十七頁(yè)，共41頁(yè)。第十七頁(yè)，共41頁(yè)。例1.1假定8名運(yùn)動(dòng)員參加一場(chǎng)比賽，設(shè)8人的獲勝概率分布為（1/2，1/4，1/8，1/16，1/64，1/64，1/64，1/64）。求該場(chǎng)比賽的平均信息量。解：H(X)=-1/2log(1/2)-1/4log(1/4)-1/8log(1/8)

-1/16log(1/16)-4*1/64log(1/64)

=2比特假設(shè)要把某人獲勝的消息傳出去，可以發(fā)送該人的編號(hào)；由于獲勝概率不同，獲勝可能大的用較短描述，可以獲得2比特的平均信息量。第十八頁(yè)，共41頁(yè)。第十八頁(yè)，共41頁(yè)。5Shannon信息論的優(yōu)點(diǎn)

Shannon定理的證明是非構(gòu)造性的，而且也不夠嚴(yán)格，但他的“數(shù)學(xué)直觀出奇地正確”(A.N.Kolmogrov，1963)。已在數(shù)學(xué)上嚴(yán)格地證明了Shannon編碼定理，而且發(fā)現(xiàn)了各種具體可構(gòu)造的有效編碼理論和方法，可以實(shí)現(xiàn)Shannon指出的極限。幾乎無(wú)錯(cuò)地經(jīng)由Gaussian信道傳信對(duì)于非白Gassian信道，Shannon的注水定理和多載波調(diào)制(MCM)CDMA、MCM(COFDM)、TCM、BCM、各種均衡、對(duì)消技術(shù)、以及信息存儲(chǔ)編碼調(diào)制技術(shù)第十九頁(yè)，共41頁(yè)。第十九頁(yè)，共41頁(yè)。6Shannon信息論的局限性如果實(shí)際信源或信道符合所采用的概率模型描述，這種方法是有效的，否則只能是近似的，甚至根本無(wú)效。語(yǔ)言的熵描述是非常困難的，它是非平穩(wěn)的，除了確定的信息，還有模糊的信息，比如“韻味”，“意境”不同的接收者對(duì)同一個(gè)東西得到的信息可能是不同的Shannon信息論適合于能夠定量描述的信息，對(duì)難于定量描述的信息則無(wú)能為力。第二十頁(yè)，共41頁(yè)。第二十頁(yè)，共41頁(yè)。7信息論的廣義性第二十一頁(yè)，共41頁(yè)。第二十一頁(yè)，共41頁(yè)。信息論常被理解為包括更廣的領(lǐng)域語(yǔ)義學(xué)語(yǔ)言學(xué)神經(jīng)生理學(xué)心理學(xué)組織學(xué)信息的不同屬性的定義產(chǎn)生不同的信息論模糊信息論量子信息論生物信息論信息復(fù)雜度的信息理論第二十二頁(yè)，共41頁(yè)。第二十二頁(yè)，共41頁(yè)。1.2信息論研究的中心問(wèn)題和發(fā)展第二十三頁(yè)，共41頁(yè)。第二十三頁(yè)，共41頁(yè)。1

Shannon信息論的基本目的1948年shannon發(fā)表了“通信的數(shù)學(xué)理論”奠定了信息論理論基礎(chǔ)基本任務(wù)是設(shè)計(jì)有效而可靠的通信系統(tǒng)保密性和認(rèn)證性第二十四頁(yè)，共41頁(yè)。第二十四頁(yè)，共41頁(yè)。克勞德·艾爾伍德·香農(nóng)（ClaudeElwoodShannon）

美國(guó)數(shù)學(xué)家、信息論的創(chuàng)始人。

1916年4月30日出生于美國(guó)密歇根州的Petoskey，2001年2月26日去世，享年84歲。

1936年畢業(yè)于密歇根大學(xué)并獲得數(shù)學(xué)和電子工程學(xué)士學(xué)位

1940年獲得麻省理工學(xué)院（MIT）數(shù)學(xué)博士學(xué)位和電子工程碩士學(xué)位

1941年他加入貝爾實(shí)驗(yàn)室，工作到1972年。

1956年他成為麻省理工學(xué)院（MIT）客座教授

1958年成為終生教授，1978年成為名譽(yù)教授。

第二十五頁(yè)，共41頁(yè)。第二十五頁(yè)，共41頁(yè)。香農(nóng)的學(xué)術(shù)研究香農(nóng)于1940年在普林斯頓高級(jí)研究所（TheInstituteforAdvancedStudyatPrinceton）期間開(kāi)始思考信息論與有效通信系統(tǒng)的問(wèn)題。經(jīng)過(guò)8年的努力，香農(nóng)在1948年6月和10月在《貝爾系統(tǒng)技術(shù)雜志》（BellSystemTechnicalJournal）上連載發(fā)表了他影像深遠(yuǎn)的論文《通訊的數(shù)學(xué)原理》。1949年，香農(nóng)又在該雜志上發(fā)表了另一著名論文《噪聲下的通信》。在這兩篇論文中，香農(nóng)闡明了通信的基本問(wèn)題，給出了通信系統(tǒng)的模型，提出了信息量的數(shù)學(xué)表達(dá)式，并解決了信道容量、信源統(tǒng)計(jì)特性、信源編碼、信道編碼等一系列基本技術(shù)問(wèn)題。兩篇論文成為了信息論的奠基性著作。他的工作被稱為二十世紀(jì)的偉大創(chuàng)造(intellectualachievements)之一。第二十六頁(yè)，共41頁(yè)。第二十六頁(yè)，共41頁(yè)?？藙诘隆ぐ瑺栁榈隆は戕r(nóng)（ClaudeElwoodShannon）第二十七頁(yè)，共41頁(yè)。第二十七頁(yè)，共41頁(yè)。信息論在領(lǐng)域內(nèi)的基本作用第二十八頁(yè)，共41頁(yè)。第二十八頁(yè)，共41頁(yè)。2信息論的研究?jī)?nèi)容狹義信息論（經(jīng)典信息論）研究信息測(cè)度，信道容量以及信源和信道編碼理論

——香農(nóng)基本理論P(yáng)11圖1.5一般信息論研究信息傳輸和處理問(wèn)題，除經(jīng)典信息論外還包括噪聲理論，信號(hào)濾波和預(yù)測(cè)，統(tǒng)計(jì)檢測(cè)和估值理論，調(diào)制理論，信息處理理論和保密理論廣義信息論除上述內(nèi)容外，還包括自然和社會(huì)領(lǐng)域有關(guān)信息的內(nèi)容，如模式識(shí)別，計(jì)算機(jī)翻譯，心理學(xué)，遺傳學(xué)，神經(jīng)生理學(xué)第二十九頁(yè)，共41頁(yè)。第二十九頁(yè)，共41頁(yè)。Shannon理論Shannon定理的證明是非構(gòu)造性的，而且也不夠嚴(yán)格，但他的“數(shù)學(xué)直觀出奇地正確”(A.N.Kolmogrov，1963)。已在數(shù)學(xué)上嚴(yán)格地證明了Shannon編碼定理，而且發(fā)現(xiàn)了各種具體可構(gòu)造的有效編碼理論和方法，可以實(shí)現(xiàn)Shannon指出的極限。幾乎無(wú)錯(cuò)地經(jīng)由Gaussian信道傳信對(duì)于非白Gassian信道，Shannon的注水定理和多載波調(diào)制(MCM)CDMA、MCM(COFDM)、TCM、BCM、各種均衡、對(duì)消技術(shù)、以及信息存儲(chǔ)編碼調(diào)制技術(shù)第三十頁(yè)，共41頁(yè)。第三十頁(yè)，共41頁(yè)。消息伴隨著可以量化的信息——熵、平均互信息信源發(fā)出的消息有冗余度，因此可進(jìn)行信源編碼，熵是無(wú)失真信源編碼的最低極限噪聲使信道可靠傳輸能力受限，提出信道可靠傳輸能力——信道容限為可靠通信，通過(guò)增加冗余進(jìn)行信道糾錯(cuò)編碼，信道容限是錯(cuò)誤足夠小的信道編碼的臨界上限干擾源信源信道信宿第三十一頁(yè)，共41頁(yè)。第三十一頁(yè)，共41頁(yè)。1.3信息論幾個(gè)方面的主要進(jìn)展Ⅰ．信源編碼與數(shù)據(jù)壓縮Ⅱ．信道編碼與差錯(cuò)控制技術(shù)Ⅲ．多用戶信息論與網(wǎng)絡(luò)通信Ⅳ．多媒體與信息論Ⅴ．信息論與密碼學(xué)和數(shù)據(jù)安全Ⅵ．信息論與概率統(tǒng)計(jì)Ⅶ．信息論與經(jīng)濟(jì)學(xué)Ⅷ．信息論與計(jì)算復(fù)雜性Ⅸ．信息論與系統(tǒng)、控制、信號(hào)檢測(cè)和處理Ⅹ．量子信息論Ⅺ．Shannon的其它重要貢獻(xiàn)第三十二頁(yè)，共41頁(yè)。第三十二頁(yè)，共41頁(yè)。1信源編碼與數(shù)據(jù)壓縮-關(guān)鍵理論進(jìn)展的十個(gè)里程碑[Kieffer1993]無(wú)擾信源編碼的誕生(1948,C.E.Shannon)。Huffman算法的發(fā)現(xiàn)(1952,D.A.Huffman)。建立Shannon-McMillan定理(1953,B.McMillan)。發(fā)現(xiàn)Lloyd算法(1957,S.P.Lloyd,1982年發(fā)表,)。率失真理論系統(tǒng)化(1959,C.E.Shannon,)。KolmogorovComplexity概念誕生(1964,A.N.Kolmogorov,)。通用信源編碼理論系統(tǒng)化(1973,L.D.Davission)。多端信源編碼理論誕生(1973,D.Slepian和J.K.Wolf)。第一個(gè)實(shí)際的算術(shù)編碼方案(1976,J.Rissannen和R.Pasco1976博士論文)。發(fā)現(xiàn)Lempel-Ziv碼(1977,J.Ziv和A.Lempel)。第三十三頁(yè)，共41頁(yè)。第三十三頁(yè)，共41頁(yè)。信道編碼與差錯(cuò)控制技術(shù)

1．Shannon信道編碼定理和Shannon極限。Shannon編碼信道定理:R<C，存在編碼方法可任意小的錯(cuò)誤率傳遞速率為R的信息，碼長(zhǎng)N要足夠大。R>C不存在有編碼方法實(shí)現(xiàn)滿足誤碼率要求的速率為R的傳信。Shannon證明碼長(zhǎng)N大時(shí)，隨機(jī)選擇的碼以很高概率為好碼。問(wèn)題：Shannon的證明是非構(gòu)造性，如何構(gòu)造好碼實(shí)現(xiàn)定理目標(biāo)?實(shí)現(xiàn)ML譯碼的復(fù)雜性隨N呈指數(shù)增長(zhǎng)。第三十四頁(yè)，共41頁(yè)。第三十四頁(yè)，共41頁(yè)。第三十五頁(yè)，共41頁(yè)。第三十五頁(yè)，共41頁(yè)。第三十六頁(yè)，共41頁(yè)。第三十六頁(yè)，共41頁(yè)。第三十七頁(yè)，共41頁(yè)。第三十七頁(yè)，共41頁(yè)。3．多用戶信息論與網(wǎng)絡(luò)通信

(1)理論基礎(chǔ)。兩路通信系統(tǒng)(Shannon1961)。(2)理論進(jìn)展。Cover,Schalkwijk,Van.derMeulen,Alswede,Slepian,Wolf,WynerLiao(UniverstyofHawaii),Han等。(3)技術(shù)成就。CDMA(Virerbi,Qaulecom)的技術(shù)問(wèn)題：聯(lián)合檢測(cè)和譯碼、均衡、干擾抵消、速率分拆(ratesplitting)、功率檢測(cè)控制等(Verdu,ShamaiandRimoldi)。STC(Spacetimecode)，源于信息論考慮。線性網(wǎng)絡(luò)編碼合作編碼技術(shù)第三十八頁(yè)，共41頁(yè)。第三十八頁(yè)，共41頁(yè)。

過(guò)去50年中Shannon信息論已取得巨大、豐富的理論和技術(shù)成果，在未來(lái)的