信息論與編碼-第一課.ppt

1、信息論與編碼,授課老師：魏平俊 聯(lián)系電話Email: ,信息論與編碼,教學(xué)內(nèi)容 香農(nóng)信息論的基本概念、基本理論 信息、熵、信道容量、編碼定理（無(wú)失真信源編碼、有 噪信道編碼，限失真信源編碼等，信道編碼理論） 信道編碼 基本原理、常用碼編譯原理和方法 信源編碼 密碼學(xué)簡(jiǎn)介,信息論與編碼,教學(xué)重點(diǎn)： 信息度量、信道容量、無(wú)失真信源編碼、限失真信源編碼、信道編碼的基本理論及實(shí)現(xiàn)原理。,信息論與編碼,參考書： 信息論與編碼，曹雪虹 張宗橙編，清華大學(xué)出版社，2004 信息論基礎(chǔ)理論與應(yīng)用， 傅祖蕓編著，電子工業(yè)出版社，2001 信息理論基礎(chǔ)，周炯槃 信息與編碼理論，王育民、梁

2、傳甲，西北電訊工程學(xué)院出版社 The theory of information and coding, R.J. McEliece 糾錯(cuò)碼-原理與方法，王新梅 信道編碼，劉玉君,信息論與編碼-緒論,第一章 緒論 1.1信息論的基本概念 1.2信息論發(fā)展簡(jiǎn)史 1.3信道編碼發(fā)展簡(jiǎn)史 1.4通信系統(tǒng)的基本模型,信息論與編碼-緒論,1.1信息論的基本概念,信息論與編碼-緒論,1.1信息論的基本概念 信息 如何定義信息、如何度量信息、如何計(jì)算信息,信息論與編碼-緒論,1.1信息論的基本概念 信息 如何定義信息、如何度量信息、如何計(jì)算信息 信息論 如何處理信息、如何傳遞信息、如何提取信息,信息論與編碼

3、-緒論,信息的一般含義,信息論與編碼-緒論,信息的一般含義 信息至今無(wú)確切定義，但是它是一種人人皆知的抽象概念，是一種不言自明的概念。,信息論與編碼-緒論,信息的一般含義 信息至今無(wú)確切定義，但是它是一種人人皆知的抽象概念，是一種不言自明的概念。 信息在不同的領(lǐng)域內(nèi)有不同的定義。,信息論與編碼-緒論,信息的一般含義 信息至今無(wú)確切定義，但是它是一種人人皆知的抽象概念，是一種不言自明的概念。 信息在不同的領(lǐng)域內(nèi)有不同的定義。 在通信領(lǐng)域內(nèi)是指通信時(shí)所要告訴對(duì)方的某種“內(nèi)容”?；蛘哒f(shuō)是接受方在接受到一個(gè)符號(hào)或一個(gè)序列后，所獲得的“內(nèi)容”。,信息論的研究范疇,信息論與編碼-緒論,信息論的研究范疇 信

4、息論是在信息可以度量的基礎(chǔ)上，對(duì)如何有效、可靠地傳遞信息進(jìn)行研究的科學(xué)。,信息論與編碼-緒論,信息論的研究范疇 信息論是在信息可以度量的基礎(chǔ)上，對(duì)如何有效、可靠地傳遞信息進(jìn)行研究的科學(xué) 狹義信息論：信息度量、信息特征、信息傳輸速率、信道容量、干擾對(duì)信息傳輸?shù)挠绊懙取?信息論與編碼-緒論,信息論的研究范疇 信息論是在信息可以度量的基礎(chǔ)上，對(duì)如何有效、可靠地傳遞信息進(jìn)行研究的科學(xué)。 狹義信息論：信息度量、信息特征、信息傳輸速率、信道容量、干擾對(duì)信息傳輸?shù)挠绊懙?廣義信息論：還包括信號(hào)設(shè)計(jì)、噪聲理論、信號(hào)的檢測(cè)與估值等。,信息論與編碼-緒論,信息論與編碼-緒論,本書所要解決的問(wèn)題 什么是信息、如何度

5、量信息？ 在信息傳輸中，基本的極限條件是什么？ 對(duì)于信息的壓縮和恢復(fù)的極限條件是什么？ 從環(huán)境中抽取信息極限的條件是什么？ 設(shè)計(jì)什么樣的設(shè)備才能達(dá)到這些極限？ 這些設(shè)備是否存在？,信息論與編碼-緒論,1.2 信息論發(fā)展簡(jiǎn)史和現(xiàn)狀 信息論的奠基人克勞德艾爾伍德香農(nóng)（Claude Elwood Shannon，1916年4月30日2001年2月26日）美國(guó)數(shù)學(xué)家 于1916年4月30日出生于美國(guó)密歇根州的Petoskey 1936年畢業(yè)于密歇根大學(xué)并獲得數(shù)學(xué)和電子工程學(xué)士學(xué)位 1940年獲得麻省理工學(xué)院（MIT）數(shù)學(xué)博士學(xué)位和電子工程碩士學(xué)位 1941年他加入貝爾實(shí)驗(yàn)室數(shù)學(xué)部，工作到1972年 1

6、956年他成為麻省理工學(xué)院（MIT）客座教授，并于1958年成為終生教授，1978年成為名譽(yù)教授 香農(nóng)博士于2001年2月26日去世，享年84歲,信息論與編碼-緒論,1948年在貝爾系統(tǒng)技術(shù)雜志上發(fā)表了244頁(yè)的長(zhǎng)篇論著，通信的數(shù)學(xué)理論。 1949年，他又在同一雜志上發(fā)表了另一篇名著噪聲下的通信。 在這兩篇文章中，他解決了過(guò)去許多懸而未決的問(wèn)題：經(jīng)典地闡明了通信的基本問(wèn)題，提出了通信系統(tǒng)的模型，給出了信息量的數(shù)學(xué)表達(dá)式，解決了信道容量、信源統(tǒng)計(jì)特性、信源編碼、信道編碼等有關(guān)精確地傳送通信符號(hào)的基本技術(shù)問(wèn)題。 兩篇文章成了現(xiàn)在信息論的奠基著作,信息論與編碼-緒論,信息論與編碼-緒論,1832年莫

7、爾斯電報(bào)系統(tǒng)中高效率編碼方法對(duì)后來(lái)香農(nóng)的編碼理論是有啟發(fā)的。 1885年凱爾文(L. Kelvin)曾經(jīng)研究過(guò)一條電纜的極限傳信率問(wèn)題。 1922年卡遜(JRCarson)對(duì)調(diào)幅信號(hào)的頻譜結(jié)構(gòu)進(jìn)行了研究，并建立了信號(hào)頻譜概念。 1924年奈奎斯特(HNyquist)指出，如果以一個(gè)確定的速度來(lái)傳輸電報(bào)信號(hào)，就需要一定的帶寬。他把信息率與帶寬聯(lián)系起來(lái)了。 1928年哈特萊(RVHartley)發(fā)展了奈奎斯特的工作，并提出把消息考慮為代碼或單語(yǔ)的序列。 1936年阿姆斯特朗(EHArmstrong)認(rèn)識(shí)到在傳輸過(guò)程中增加帶寬的辦法對(duì)抑制噪聲干擾肯定有好處。根據(jù)這一思想他提出了寬偏移的頻率調(diào)制方法，

8、該方法是有劃時(shí)代意義的。,信息論與編碼-緒論,Shannon受著前輩的工作的啟示，其中最具代表性的是貝爾系統(tǒng)技術(shù)雜志上所披露的奈奎斯特的影響電報(bào)速率的一些因素和哈特萊的信息的傳輸。正是他們最早研究了通信系統(tǒng)的信息傳輸能力，第一次提出了信息量的概念，并試圖用教學(xué)公式予以描述。而香農(nóng)則創(chuàng)造性地繼承了他們的事業(yè)，在信息論的領(lǐng)域中鉆研了8年之久，終于創(chuàng)建了信息論。,信息論與編碼-緒論,“通信的基本問(wèn)題就是在一點(diǎn)重新準(zhǔn)確地或近似地再現(xiàn)另一點(diǎn)所選擇的消息”。通信的數(shù)學(xué)理論中的一句銘言。正是沿著這一思路他應(yīng)用數(shù)理統(tǒng)計(jì)的方法來(lái)研究通信系統(tǒng)，從而創(chuàng)立了影響深遠(yuǎn)的信息論。 不確定性 接收者收到某一消息后所獲得的信

9、息，可以用接收者在通信前后“不確定性”的消除量來(lái)度量。簡(jiǎn)而言之，接收者所得到的信息量，在數(shù)量上等于通信前后“不確定性”的消除量(或減少量)。-這就是信息理論中度量信息的基本觀點(diǎn)。,信息論與編碼-緒論,香農(nóng)信息理論具有嶄新的風(fēng)貌，是通信科學(xué)發(fā)展史上的一個(gè)轉(zhuǎn)折點(diǎn)，它使通信問(wèn)題的研究從經(jīng)驗(yàn)轉(zhuǎn)變?yōu)榭茖W(xué)。因此，它一出現(xiàn)就在科學(xué)界引起了巨大的轟動(dòng)，許多不同領(lǐng)域的科學(xué)工作者對(duì)它懷有濃厚的興趣，并試圖爭(zhēng)相應(yīng)用這一理論來(lái)解決各自領(lǐng)域的問(wèn)題從此，信息問(wèn)題的研究，進(jìn)入了一個(gè)新的紀(jì)元。,信息論與編碼-緒論,廣義信息論 信息論的誕生，激起了人們對(duì)信息論的巨大熱情，它向各門學(xué)科沖擊，研究規(guī)模像滾雪球一樣越來(lái)越大。不僅在電

10、子學(xué)的其他領(lǐng)域，如計(jì)算機(jī)、自動(dòng)控制等方面大顯身手，而且遍及物理學(xué)、化學(xué)、生物學(xué)、心理學(xué)、醫(yī)學(xué)、經(jīng)濟(jì)學(xué)、人類學(xué)、語(yǔ)音學(xué)、統(tǒng)計(jì)學(xué)、管理學(xué)等學(xué)科。它已遠(yuǎn)遠(yuǎn)地突破了香農(nóng)本人所研究和意料的范疇，即從香農(nóng)的所謂“狹義信息論”發(fā)展到了“廣義信息論”,信息論與編碼-緒論,信息的定義 Shannon:隨機(jī)不定性程度的減少 局限性:沒(méi)有包含信息的內(nèi)容和價(jià)值，只考慮了隨機(jī)型的不定性，沒(méi)有從根本上回答“信息是什么”的問(wèn)題。 1948年維納（N. Wiener）:信息是人們?cè)谶m應(yīng)外部世界，并且這種適應(yīng)反作用于外部世界的過(guò)程中，同外部世界進(jìn)行互相交換的內(nèi)容的名稱。維納關(guān)于信息的定義包含了信息的內(nèi)容與價(jià)值，從動(dòng)態(tài)的角度揭示

11、了信息的功能與范圍，但也有局限性。由于人們?cè)谂c外部世界的相互作用過(guò)程中，同時(shí)也存在著物質(zhì)與能量的交換，維納關(guān)于信息的定義沒(méi)有將信息與物質(zhì)、能量區(qū)別開來(lái)。 1975年，意大利學(xué)者朗高（G. Longo）在信息論：新的趨勢(shì)與未決問(wèn)題一書的序言中認(rèn)為信息是反映事物的形式、關(guān)系和差別的東西，它包含在事物的差異之中，而不在事物本身。當(dāng)然，有差異就是信息的觀點(diǎn)是正確的，但是反過(guò)來(lái)說(shuō)沒(méi)有差異就沒(méi)有信息就不夠確切。所以，信息就是差異的定義也有其局限性。,信息論與編碼-緒論,據(jù)不完全統(tǒng)計(jì)，有關(guān)信息的定義有100多種，它們都從不同的側(cè)面、不同的層次揭示了信息的特征與性質(zhì)，但同時(shí)也都有這樣或那樣的局限性。 1988

12、年，我國(guó)信息論專家鐘義信教授在信息科學(xué)原理一書中把信息定義為：信息是事物的運(yùn)動(dòng)狀態(tài)和狀態(tài)變化的方式。并通過(guò)引入約束條件推導(dǎo)了信息的概念體系，對(duì)信息進(jìn)行了完整和準(zhǔn)確的描述。 信息的這個(gè)定義具有最大的普遍性，不僅涵蓋所有其他的信息定義，而且通過(guò)引入約束條件還能轉(zhuǎn)化為所有其他的信息定義。 也有人對(duì)此提出異議，如魯晨光（廣義信息論作者）。,信息論與編碼-緒論,鐘義信 1940年2月出生, 漢族，北京郵電大學(xué)教授、 博士生導(dǎo)師、副校長(zhǎng)、校學(xué)術(shù)委員會(huì)主席。 長(zhǎng)期從事通信理論、信息理論、信息科學(xué)、人工智能、 神經(jīng)網(wǎng)絡(luò)、決策學(xué)、信息經(jīng)濟(jì)學(xué)領(lǐng)域的研究和教學(xué)工作，在上述領(lǐng)域先后出版學(xué)術(shù)著作16 部，在國(guó)內(nèi)外學(xué)術(shù)刊

13、物和學(xué)術(shù)會(huì)議上發(fā)表學(xué)術(shù)論文380多篇。 代表性學(xué)術(shù)論著包括信息科學(xué)原理（1988年）、信息技術(shù)通論（1994）、智能理論與技術(shù)人工智能與神經(jīng)網(wǎng)絡(luò)（1992）、偽隨機(jī)編碼通信：原理與應(yīng)用（1978）等。 具有重要?jiǎng)?chuàng)新意義的學(xué)術(shù)貢獻(xiàn)主要包括 “知識(shí)論”、“全信息理論”、“意識(shí)機(jī)模型”、“信息科學(xué)原理與信息科學(xué)方法論”、“信息基礎(chǔ)結(jié)構(gòu)理論模型”等。,信息論與編碼-緒論,為什么Shannon信息論在解決通信系統(tǒng)的問(wèn)題方面非常有效，但是在涉及人工智能理論研究的問(wèn)題是就無(wú)能為力？ 信息論只關(guān)注信號(hào)（信息的載體）的波形，不關(guān)心它的內(nèi)容和價(jià)值。通信系統(tǒng)的設(shè)計(jì)可以只關(guān)心信號(hào)的波形。 人工智能卻必須“理解信息的內(nèi)

14、容和價(jià)值”。 為此，經(jīng)過(guò)長(zhǎng)期的研究，提出和建立了“全信息理論”-能夠統(tǒng)一考慮信息的形式因素（稱為語(yǔ)法信息）、內(nèi)容因素（稱為語(yǔ)義信息）和價(jià)值因素（稱為語(yǔ)用信息）的全新的信息理論。,信息論與編碼-緒論,信息論的研究范疇,基礎(chǔ) 信息論,工 程信息論,廣義 信息論,信息論與編碼-緒論,基礎(chǔ)信息論 主要研究通信系統(tǒng)的數(shù)學(xué)描述與定量分析，研究系統(tǒng)的最優(yōu)狀態(tài)與優(yōu)化理論，即研究通信系統(tǒng)理論上的潛在能力與數(shù)學(xué)上的極限情況。它是以存在性研究為主體，又稱它為數(shù)學(xué)信息論。 工程信息論 以工程為背景，主要研究通信系統(tǒng)中各部分的最佳工作規(guī)律，與最佳設(shè)計(jì)原則，它以構(gòu)造性為主體，以工程上技術(shù)問(wèn)題為主。主要包括： 信源編、譯碼

15、理論及其設(shè)計(jì)構(gòu)造方法； 信道編、譯碼理論及其設(shè)計(jì)構(gòu)造方法； 最佳調(diào)制與解調(diào)理論與實(shí)現(xiàn)； 最佳檢測(cè)、估值與最佳接收理論與實(shí)現(xiàn)； 最佳信息處理理論、方法與算法； ,信息論與編碼-緒論,廣義信息論： 核心問(wèn)題是拓廣，有三重含義： 首先是在信息含義的拓廣，以語(yǔ)言信息為例：,仙農(nóng)信息,語(yǔ)法信息,語(yǔ)義信息,語(yǔ)用信息,信息論與編碼-緒論,其次是在描述方法上的拓廣： 從定量到定性； 從客觀到主觀； 從概率到模糊； 從統(tǒng)計(jì)到單個(gè)實(shí)發(fā)。,信息論與編碼-緒論,最后是用途上的拓廣： 從通信領(lǐng)域拓廣至相鄰自然科學(xué)領(lǐng)域； 從自然科學(xué)領(lǐng)域拓廣至社會(huì)科學(xué)領(lǐng)域。,信息論與編碼-緒論,進(jìn)入20世紀(jì)80年代以來(lái)，當(dāng)人們?cè)谧h論未來(lái)的

16、時(shí)候，人們的注意力又異口同聲地集中到信息領(lǐng)域。按照國(guó)際一種流行的說(shuō)法，未來(lái)將是一個(gè)高度信息化的社會(huì)。信息工業(yè)將發(fā)展成頭號(hào)工業(yè)，社會(huì)上大多數(shù)的人將是在從事信息的生產(chǎn)、加工和流通。 這時(shí)，人們才能更正確地估價(jià)香農(nóng)工作的全部含義。信息論這個(gè)曾經(jīng)只在專家們中間流傳的學(xué)說(shuō)，將來(lái)到更廣大的人群之中。香農(nóng)這個(gè)名字也飛出了專家的書齋和實(shí)驗(yàn)室，為更多的人所熟悉和了解,信息論與編碼-緒論,信息、消息、信號(hào) 消息是信息的載體，信息是由消息表達(dá)出來(lái)的 信號(hào)是消息的物理體現(xiàn)，或者說(shuō)是消息的載體,信息論與編碼-緒論,信道編碼發(fā)展簡(jiǎn)史 糾錯(cuò)碼的主要發(fā)展過(guò)程大致分以下幾個(gè)階段 50年代至60年代初，主要研究各種有效的編、譯碼

17、方法，奠定了線性分組碼的理論基礎(chǔ)；提出了BCH碼編、譯碼方法以及卷積碼的序列譯碼；給出了糾錯(cuò)碼的基本碼限； 第一個(gè)分組碼是1950年發(fā)現(xiàn)的能糾正單個(gè)錯(cuò)誤的Hamming碼； 1954年Golay發(fā)現(xiàn)的Golay碼以及Reed和Muller發(fā)現(xiàn)的RM碼 Prange 在1957年發(fā)現(xiàn)的循環(huán)碼等。 最有意義的是Bose和Ray-Chaudhuri在1960年，Hocquenghem在1959年發(fā)現(xiàn)的能糾多個(gè)錯(cuò)誤的BCH碼，以及Reed和Solomon在1960年發(fā)現(xiàn)的非二進(jìn)制RS碼，并認(rèn)識(shí)到BCH碼可以看成某個(gè)RS碼的子域子碼，RS碼又可以看作是BCH碼的特例,信息論與編碼-緒論,60年代至70年

18、代初，這是糾錯(cuò)碼發(fā)展過(guò)程中最為活躍的時(shí)期。提出了如門限譯碼、迭代譯碼、軟判決譯碼和卷積碼的Viterbi譯碼等有效的編譯碼方法；同時(shí)注意到了糾錯(cuò)碼實(shí)用化的問(wèn)題，討論了如碼重量分布、譯碼錯(cuò)誤概率和不可檢錯(cuò)誤概率的計(jì)算、信道的模型化等與實(shí)用化有關(guān)的各種問(wèn)題。 發(fā)現(xiàn)的分組碼主要有1970年的Goppa碼和1982年的代數(shù)幾何碼。 在所有這些分組碼中，除了Goppa碼和代數(shù)幾何碼中存在個(gè)別達(dá)到GV限的漸進(jìn)好碼外，其它碼字都不是漸進(jìn)的好碼。分組碼的譯碼主要采用基于代數(shù)的硬判決譯碼。,信息論與編碼-緒論,70年代以來(lái)，糾錯(cuò)碼在實(shí)際應(yīng)用中得到了更大的發(fā)展。大規(guī)模集成電路和微機(jī)的迅速發(fā)展，為糾錯(cuò)碼的實(shí)用打下了

19、堅(jiān)實(shí)的物質(zhì)基礎(chǔ)。 70年代末、80年代初，G. Ungerboeck把編碼與調(diào)制相結(jié)合提出了網(wǎng)格編碼調(diào)制（TCM, trellis-coded modulation）技術(shù)是編碼理論的又一重要里程碑。,信息論與編碼-緒論,1993年C. Berrou，A. Glavieux發(fā)現(xiàn)的Turbo碼是又一重大突破； LDPC碼的進(jìn)一步研究； 空時(shí)碼的出現(xiàn)。,信息論與編碼-緒論,1.3 通信系統(tǒng)的基本模型 詳細(xì)模型,信息論與編碼-緒論,常用模型,信息論與編碼-緒論,簡(jiǎn)化模型,信息論與編碼-緒論,信源：是產(chǎn)生消息(或消息序列)的源，消息通常是符號(hào)序列或時(shí)間函數(shù)。 例如在電報(bào)系統(tǒng)中，消息是由文字、符號(hào)、數(shù)字組

20、成的報(bào)文(符號(hào)序列)，稱為離散消息；在電話系統(tǒng)中，消息是語(yǔ)聲波形(時(shí)間函數(shù))，稱為連續(xù)消息。 消息取值服從一定的統(tǒng)計(jì)規(guī)律，故信源的數(shù)學(xué)模型是一個(gè)在信源符號(hào)集中取值的隨機(jī)變量序列或隨機(jī)過(guò)程。 如何由信源產(chǎn)生消息、消息的統(tǒng)計(jì)特性，是研究的重點(diǎn),信息論與編碼-緒論,信源編碼器 將信源產(chǎn)生的消息變換為一個(gè)數(shù)字序列(通常為二進(jìn)制數(shù)字序列)，也稱基帶信號(hào)。 壓縮信源的冗余度，以提高傳輸效率。盡量減少各符號(hào)之間的相關(guān)性。 信源編碼分為無(wú)失真信源編碼（離散信源）和限失真信源編碼（連續(xù)信源） 主要指標(biāo)是編碼效率，即理論上所需的碼率與實(shí)際達(dá)到的碼率之比。 主要作用是增加信息傳輸?shù)挠行浴?信息論與編碼-緒論,信源

21、編碼理論要回答兩個(gè)問(wèn)題： 對(duì)給定的信源，可能達(dá)到的最小編碼速率是多少？ 如何構(gòu)造實(shí)現(xiàn)這一速率的最優(yōu)編碼。 這兩個(gè)問(wèn)題在信息論發(fā)展的最初年代里就已獲得解決。,信息論與編碼-緒論,信道 信道是指?jìng)鬏斝盘?hào)的媒質(zhì)或通道 架空明線、電線、射頻波束、人造衛(wèi)星等都是信道。 廣義信道：在信息論的模型里，有時(shí)為了研究方便，可以將發(fā)送端和接收端的一部分如調(diào)制器和解調(diào)器歸入信道。 信道的主要問(wèn)題是傳送信息的能力，即信道容量,信息論與編碼-緒論,干擾源（噪聲） 影響信號(hào)傳輸?shù)母鞣N因素 內(nèi)部噪聲（設(shè)備的熱噪聲，變換產(chǎn)生的非線性失真，等）和外噪聲（外部環(huán)境的影響，有人為的和自然的） 加性噪聲、乘性噪聲；隨機(jī)噪聲、突發(fā)噪聲；等 一般是將系統(tǒng)各部分的噪聲和干擾都?xì)w入信道中考慮。根據(jù)噪聲和干擾的統(tǒng)計(jì)特性對(duì)信道進(jìn)行分類。 最簡(jiǎn)單的是離散無(wú)記憶(恒參)信道。 噪聲的特性，尤其是統(tǒng)計(jì)特性，是研究的重點(diǎn)。 最常用的噪聲是高斯白噪聲。,信息論與編碼-緒論,信道編碼器 增加信息傳輸?shù)目煽啃?基本思想就是通過(guò)編碼引進(jìn)多余度以提高信息傳送的可靠性。更確切地說(shuō)，信道譯碼器利用引入的多余度，是個(gè)各符號(hào)之間滿足某種約束關(guān)系，從而達(dá)