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

ThomasM.Cover.ElementsofInformationTheory.

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

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

Shannon信息論的基本目的1948年shannon發(fā)表了“通信的數(shù)學(xué)理論”奠定了信息論理論基礎(chǔ)基本任務(wù)是設(shè)計有效而可靠的通信系統(tǒng)保密性和認證性第二十四頁，共41頁。第二十四頁，共41頁?？藙诘隆ぐ瑺栁榈隆は戕r(nóng)（ClaudeElwoodShannon）

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

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

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

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

1941年他加入貝爾實驗室，工作到1972年。

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

1958年成為終生教授，1978年成為名譽教授。

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

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

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

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

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