信息率與編碼第一章

——主講教師：李曉花/p>

教材：

曹雪虹,張宗橙．信息論與編碼．北京：清華大學(xué)出版社，2004信息論與編碼1.肖國鎮(zhèn)，卿斯?jié)h．編碼理論．北京：國防工業(yè)出版社，19932.孫麗華，陳榮伶．信息論與編碼．江西：科學(xué)技術(shù)出版社，2002

3.田麗華．編碼理論．西安：西安電子科技大學(xué)出版社，20034.張鳴瑞，鄒世開．編碼理論．北京：北京航天航空出版社，19905.姜丹．信息論與編碼．北京：中國科學(xué)技術(shù)大學(xué)出版社，20046.曹雪虹，張宗橙．信息論與編碼．北京：北京郵電大學(xué)出版社，20017.傅祖蕓．信息理論與編碼學(xué)習(xí)輔導(dǎo)及精選題解．北京：電子工業(yè)出版社，2004

參考書：考核方式通信：考試課(30學(xué)時)總評成績=平時成績占30％+卷面成績占70％注意事項1、實行請假制度2、保持課堂紀(jì)律3、歡迎提出反饋意見4、三人行，必有我?guī)煴菊n程以概率論為基礎(chǔ)，數(shù)學(xué)推導(dǎo)較多，學(xué)習(xí)時主要把注意力集中到概念的理解上，不過分追求數(shù)學(xué)細(xì)節(jié)的推導(dǎo)。學(xué)習(xí)時一定要從始至終注意基本概念的理解，不斷加深概念的把握。學(xué)習(xí)時注意理解各個概念的“用處”，結(jié)合其他課程理解它的意義，而不要把它當(dāng)作數(shù)學(xué)課來學(xué)習(xí)，提倡獨立思考，注重思考在學(xué)習(xí)中的重要性。學(xué)習(xí)方法課程概述當(dāng)今的時代是一個信息的時代，信息處理技術(shù)的不斷進步極大的影響了我們的生活，使我們的生活質(zhì)量得到很大提高。本課程將介紹信息科學(xué)的基礎(chǔ)理論和基本方法，課程將基于一個通訊系統(tǒng)的抽象數(shù)學(xué)模型進行展開，課程的數(shù)學(xué)基礎(chǔ)為概率論。整個課程可分為基礎(chǔ)理論和編碼理論兩部分組成第一章緒論1.1信息論的形成和發(fā)展1.2通信系統(tǒng)的模型本章重點信息、消息、信號的聯(lián)系與區(qū)別通信系統(tǒng)模型及其各部件的功能作用1.1信息論的形成和發(fā)展什么叫信息？信息的主要特征是什么？什么叫消息、信號、數(shù)據(jù)？信息、消息、信號三者之間的聯(lián)系是什么？一、信息的概念1.信息從哲學(xué)的角度上講，信息是構(gòu)成物質(zhì)世界的三大支柱之一，其他兩個是物質(zhì)和能量。美國安東尼.歐廷教授:沒有物質(zhì),就什么東西也不存在.沒有能量,就什么事情也不發(fā)生.沒有信息,就什么東西也無意義.

可以說我們生活在信息的海洋之中，沒有信息就沒有世界，當(dāng)然也就沒有我們?nèi)祟惿鐣?。人類利用信息的歷史非常悠久，而且隨著人類社會的發(fā)展而發(fā)展。到了現(xiàn)代，信息的利用已經(jīng)非常重要，以至于我們當(dāng)今生活的社會被稱作信息社會?？梢娦畔⒌闹匾?。但是有史以來，人們都沒有對信息下過一個確切的定義。就像對于物質(zhì)和能量一樣。信息雖無確切定義，但是卻具有兩個明顯的特征：廣泛性與抽象性。廣泛性客觀世界充滿著信息

人類離不開信息

知識、書本是有用信息的積累

抽象性三大要素是：物質(zhì)、能量與信息。三要素中物質(zhì)是基礎(chǔ)，是實體。能量是物質(zhì)運動的形式，E=mc2，物質(zhì)可轉(zhuǎn)換成能量，而能量又是改造客觀世界的主要動力。信息：它依附于物質(zhì)和能量，但又不同于物質(zhì)和能量。沒有信息就不能更好地利用物質(zhì)和能量，人類利用信息和知識改造物質(zhì)，創(chuàng)造新物質(zhì)，提高能量利用效率，發(fā)現(xiàn)新能量形式。信息也是客觀存在的，它是人類認(rèn)識、改造客觀世界的主要動力，是人類認(rèn)識客觀世界的更高層次。就狹義而言，在通信中對信息的表達(dá)分為三個層次：信號、消息、信息。

信號：是信息的物理表達(dá)層，是三個層次中最具體的層次。它是一個物理量，是一個載荷信息的實體，可測量、可描述、可顯示。如電信號、光信號、生物信號等。消息：(或稱為符號)是信息的數(shù)學(xué)表達(dá)層，它雖不是一個物理量，但是可以定量地加以描述，它是具體物理信號的進一步數(shù)學(xué)抽象。（消息是指包含有信息的語言、文字和圖像等）信息：是指各個事物運動的狀態(tài)及狀態(tài)變化的方式。人們從來自對周圍世界的觀察得到的數(shù)據(jù)中獲得信息。信息是抽象的意識或知識，它是看不見、摸不到的。人腦的思維活動產(chǎn)生的一種想法，當(dāng)它仍儲存在腦子中的時候就是一種信息。信息是信號與消息的更高表達(dá)層次。三個層次中，信號最具體，信息最抽象。它們?nèi)咧g的關(guān)系是哲學(xué)上的內(nèi)涵與外延的關(guān)系。數(shù)據(jù)：載有信息的可觀測、可傳輸、可存儲及可處理的信號均稱為數(shù)據(jù)。接收者在收到信息之前，對它的內(nèi)容是不知道的，所以信息是新知識、新內(nèi)容；信息是能使認(rèn)識主體對某一事物的未知性或不確定性減少的有用知識；信息可以產(chǎn)生，也可以消失，同時信息可以被攜帶、貯存及處理；信息是可以量度的，信息量有多少的差別。2.信息的主要特征P3

信息的基本概念在于它的不確定性，任

何已經(jīng)確定的事物都不含有信息。例.如果你問你的同學(xué)“明天是星期幾”，則答案中含有多少信息量？情況一.你不知道今天是星期幾情況二.你知道今天是星期一例：同學(xué)對你說”你信息論與編碼原理考試通過了！”,

你得到了消息,獲得了信息嗎?

通信過程是一種消除不確定性的過程,

不確定性的消除,就獲得了信息。3.信息、消息和信號?信息是事物運動狀態(tài)或存在方式的不確定性的描述消息是信息的載體，相對具體的概念，如語言，文字，數(shù)字，圖像信號是把消息變換成適合信道傳輸?shù)奈锢砹坷?收到一封E-mail:”北京成功申辦2008年奧運會”是北京申辦2008年奧運會具體情況的描述(信息)用中文:”北京成功申辦2008年奧運會”來表述(消息)中文不能直接在Internet的傳輸信道中傳輸,中文--二進制碼--適合信道傳輸?shù)奈锢砹?信號),才能在信道中傳輸在通信系統(tǒng)中形式上傳輸?shù)氖窍?但實質(zhì)上傳輸?shù)氖切畔ⅰＵZ義信息：事物運動狀態(tài)及方式的具體含義，研究信息的主體含義。語法信息：事物的狀態(tài)和狀態(tài)改變方式本身。研究事物運動出現(xiàn)的各種可能狀態(tài)和這些狀態(tài)之間的聯(lián)系。是抽象的。（各種信息要素出現(xiàn)的可能性及各要素之間的相互關(guān)系）。語用信息：事物運動狀態(tài)、方式及其含義對觀察者的效用，研究信息客觀價值。4.信息的分類人們對客觀世界運動規(guī)律和存在狀態(tài)的認(rèn)識結(jié)果信息傳遞信息處理—再生信息傳遞信息獲取信息施用外部世界問題／環(huán)境信息運動過程語義信息語法信息語用信息二、信息論的形成和發(fā)展信息論的奠基人是誰？信息論的開創(chuàng)文章是什么？編碼理論的開創(chuàng)文章是什么？香農(nóng)的三大定理是什么？信息論的發(fā)展歷史1924年，奈奎斯特Nyquist提出信息傳輸理論；1928年，哈特萊Hartley提出信息量關(guān)系；1932年，莫爾斯Morse發(fā)明電報編碼；1946年，柯切尼柯夫提出信號檢測理論；1948年，香農(nóng)Shannon提出信息論，“通信中的數(shù)學(xué)理論

1948年，香農(nóng)在《通信的數(shù)學(xué)理論》的論文中，用概率測度和數(shù)理統(tǒng)計的方法系統(tǒng)地討論了通信的基本問題，得出了幾個重要而帶有普遍意義的結(jié)論。香農(nóng)理論的核心是：在通信系統(tǒng)中采用適當(dāng)?shù)木幋a后能夠?qū)崿F(xiàn)高效率和高可靠性的信息傳輸，并得出了信源編碼定理和信道編碼定理。

標(biāo)志著信息論的正式誕生

在前人工作基礎(chǔ)上，用概率統(tǒng)計方法研究通信系統(tǒng)揭示：通信系統(tǒng)傳遞的對象——信息提出：信息熵、信息量指出：通信系統(tǒng)的中心問題——

噪聲背景下如何有效、可靠地傳遞信息實現(xiàn)的主要方法——編碼提出了無失真信源編碼定理、信道編碼定理

給出了編碼的性能極限提供了最佳通信系統(tǒng)的理論依據(jù)從數(shù)學(xué)觀點看——都是最優(yōu)編碼的存在性定理從工程觀點看，信道編碼定理不是結(jié)構(gòu)性的無失真信源編碼定理是結(jié)構(gòu)性的——碼的平均長度～信源統(tǒng)計特性相匹配無失真信源編碼的方法1948年，香農(nóng)提出香農(nóng)編碼

1952年，費諾(Fano)提出費諾編碼

1952年，霍夫曼(D．A．Huffman)提出霍夫曼編碼，并證明它是最佳碼——有限長度的分組碼中，平均碼長最短

1982年，里斯桑內(nèi)(J．Rissanen)在多年研究的基礎(chǔ)上，與蘭登(G．G．Langdon)一起將

算術(shù)碼（非分組碼）實用化

1977年，齊弗(J．Ziv)和蘭佩爾(A．Lempel)

提出了LZ算法——一種通用編碼方法1959年，香農(nóng)發(fā)表“保真度準(zhǔn)則下的離散信源編碼定理”——Codingtheoremsforadiscretesourceatthefidelitycriterion限失真信源編碼

提出——率失真函數(shù)和率失真信源編碼定理貢獻——信源編碼的核心，壓縮編碼的理論基礎(chǔ)

連續(xù)信源在編成代碼后不可能無失真地復(fù)原——

量化有失真——最佳量化問題對于有記憶信源，條件熵必不大于無條件熵——

解除符號間的相關(guān)性可進一步壓縮碼率在研究信源編碼的同時，另外一部分科學(xué)家從事信道編碼(糾錯碼)的研究工作。這一工作已取得了很大的進展，并已經(jīng)形成一門獨立的分支——糾錯碼理論。1950年漢明(R．W．Hamming)發(fā)表的論文《檢錯碼與糾錯碼》是開拓編碼理論研究的第一篇論文。這篇論文主要考慮在大型計算機中如何糾正所出現(xiàn)的單個錯誤。

編碼理論的發(fā)展信源編碼1、無失真信源編碼：對信源進行編碼，沒有帶來信息量的損失。（適用于離散信源或數(shù)字信號）

2、限失真信源編碼：在一定準(zhǔn)則下，對信號源進行編碼。（適用于連續(xù)信源或模擬信號）信道編碼

編碼理論研究的內(nèi)容和目的

編碼理論是以信息作為主要研究對象，以信息的運動規(guī)律和利用信息的原理作為主要的研究內(nèi)容，以信息科學(xué)方法論作為主要的研究方法，以擴大人的信息功能為主要研究目的的一門新興科學(xué)。它的基本理論是信息論，控制論和系統(tǒng)論。密碼編碼學(xué)是信息安全技術(shù)的核心，密碼編碼學(xué)的主要任務(wù)是尋求產(chǎn)生安全性高的有效密碼算法和協(xié)議，以滿足對消息進行加密或認(rèn)證的要求。密碼分析學(xué)的主要任務(wù)是破譯密碼或偽造認(rèn)證信息，實現(xiàn)竊取機密信息或進行詐騙破壞活動。這兩個分支既相互對立又相互依存，正是由于這種對立統(tǒng)一關(guān)系，才推動了密碼學(xué)自身的發(fā)展。香農(nóng)在1949年發(fā)表的《保密通信的信息理論》論文中，首先用信息論的觀點對信息保密問題作了全面的論述。由于保密問題的特殊性，直至1976年迪弗(Diffe)和海爾曼(Hellman)發(fā)表了《密碼學(xué)的新方向》一文，提出了公開密鑰密碼體制后，保密通信問題才得到廣泛研究。尤其當(dāng)今，信息的安全和保密問題更加突出和重要。人們把線性代數(shù)、初等數(shù)論、矩陣等引入保密問題的研究，已形成了獨樹一幟的分支——密碼學(xué)理論。狹義信息論（經(jīng)典信息論）指香農(nóng)信息理論，研究信息測度，信道容量以及信源和信道編碼理論，是基礎(chǔ)理論一般信息論泛指通信理論，通信的數(shù)學(xué)理論，廣泛研究信息傳輸和處理的問題，除經(jīng)典信息論外還包括噪聲理論，信號濾波和預(yù)測，統(tǒng)計檢測和估值理論，調(diào)制理論，信息處理理論和保密理論廣義信息論除上述內(nèi)容外，還包括自然和社會領(lǐng)域里所有與信息有關(guān)的內(nèi)容，如模式識別，計算機翻譯，心理學(xué)，遺傳學(xué)，神經(jīng)生理學(xué)四、信息論研究的內(nèi)容狹義信息論體系結(jié)構(gòu)Shannon信息論壓縮理論有失真編碼無失真編碼等長編碼定理Shannon1948McMillan1953變長編碼定理Shannon1948McMillan1956Huffman碼(1952)、Fano碼算術(shù)碼(1968,1976,1982)LZ碼(1977,1978)率失真理論ShannonGallagerBerger壓縮編碼JPEGMPEG傳輸理論信道編碼定理網(wǎng)絡(luò)信息理論糾錯碼編碼調(diào)制理論網(wǎng)絡(luò)最佳碼1.2通信系統(tǒng)的模型通信系統(tǒng)的模型是什么？各部件的功能作用是什么？通信系統(tǒng)的性能指標(biāo)有哪些？本質(zhì)——信息的傳輸系統(tǒng)把接收方不知道的信息及時、可靠、完整、安全、經(jīng)濟地傳送給指定的接收方1、通信系統(tǒng)一、信息論研究的對象信源信源編碼u加密密鑰信道編碼信道干擾源竊聽者信道解碼解密譯碼解密密鑰信宿信源解碼加密編碼xyzZ’y’x’vkk圖1-1通信系統(tǒng)的物理模型2、通信系統(tǒng)的物理模型[說明]①不是所有的通信系統(tǒng)都采用這么全面的技術(shù)②對實際通信系統(tǒng)，還應(yīng)包括換能、調(diào)制、發(fā)射等各種變換處理③上述模型只針對1對1單向通信系統(tǒng)。還有1對多單向系統(tǒng)（廣播），1對1雙向系統(tǒng)（電話），多對多雙向系統(tǒng)（會議電視）等。加密密鑰竊聽信源信源編碼加密編碼信道信道編碼信道譯碼解密譯碼信源譯碼信宿解密密鑰干擾包括：信源、編碼器、信道、譯碼器、信宿五部分加密密鑰竊聽信源信源編碼加密編碼信道信道編碼信道譯碼解密譯碼信源譯碼信宿解密密鑰干擾包括：信源、信道、信宿三部分信源信道信宿等效無干擾信道等效信宿等效信源3、模型中各個部分的作用及需要研究的核心問題（1）信源信源是向通信系統(tǒng)提供消息u的人和機器信源輸出的是以符號形式出現(xiàn)的具體消息，它載荷信息。信源輸出的消息可歸納為兩類離散消息，例如由字母、文字、數(shù)字等符號組成的符號序列或者單個符號；連續(xù)消息，例如話音、圖像、在時間上連續(xù)變化的電參數(shù)等。

信源的核心問題它包含的信息到底有多少，怎樣將信息定量地表示出來，即如何確定信息量。（2）信宿信宿是接收消息v的人和機器信宿的核心問題信宿需要研究的問題是能收到或提取多少信息（3）信道信號從發(fā)端傳到收端的介質(zhì),信道是傳遞消息的通道，又是傳送物理信號的設(shè)施信道的中心問題主要是它能夠傳送多少信息的問題，即信道容量的大小(即研究信道的統(tǒng)計特性和傳信能力)

狹義信道——信號的傳輸媒質(zhì)(介)比如明線、電纜、波導(dǎo)、光纖、無線電波空間等。廣義信道：除狹義信道外，還包括通信系統(tǒng)某些部分。

（4）干擾源是整個通信系統(tǒng)中各個干擾的集中反映，用以表示消息在信道中傳輸時遭受干擾的情況。包括衰落，多徑，碼間干擾，非線性失真，加性噪聲，主要是統(tǒng)計特性對于任何通信系統(tǒng)而言，干擾的性質(zhì)、大小是影響系統(tǒng)性能的重要因素。（5）密鑰源是產(chǎn)生密鑰k的源信源編碼器輸出信號x經(jīng)過密鑰k的加密運算后，就把明文x變換為密文y——編碼器、譯碼器稍后講解

研究通信系統(tǒng)的目的就是要找到信息傳輸過程的共同規(guī)律，以提高信息傳輸?shù)目煽啃?、有效性、保密性和認(rèn)證性，以達(dá)到信息傳輸系統(tǒng)最優(yōu)化?？煽啃愿撸壕褪且剐旁窗l(fā)出的消息經(jīng)過信道傳輸以后，盡可能準(zhǔn)確地、不失真地再現(xiàn)在接收端。（首要目標(biāo)）有效性高：即用盡可能短的時間和盡可能少的設(shè)備來傳送盡可能多的信息量，或在每一個傳送符號內(nèi)攜帶盡可能多的信息量。(占用資源少，時間、空間、頻率等)（重要目標(biāo)）以后會看到，提高可靠性和提高有效性常常會發(fā)生矛盾，這就需要統(tǒng)籌兼顧。保密性：隱蔽和保護通信系統(tǒng)中傳送的消息，使它只能被授權(quán)接收者獲取，而不能被未授權(quán)者接收和理解。認(rèn)證性：指接收者能正確判斷所接收的消息的正確性和完整性，而不是偽造的和被篡改的。信息論所要解決的問題——可靠性、有效性、保密性和認(rèn)證性（即安全性）二、信息論研究的目的研究某一性能時的簡化框圖：信源編碼信源譯碼無噪廣義信道信源信宿信道編碼信源編碼保密譯碼信道譯碼信源譯碼保密編碼噪聲信道信源信宿

有效性研究——把保密編碼、信道編碼并入信道?？煽啃匝芯啃诺谰幋a信道譯碼信道廣義信源廣義信宿信道編碼信源編碼保密譯碼信道譯碼信源譯碼保密編碼噪聲信道信源信宿——把信源編碼、保密編碼并入信源。保密性、認(rèn)證性研究保密譯碼保密編碼無噪廣義信道廣義信源廣義信宿信道編碼信源編碼保密譯碼信道譯碼信源譯碼保密編碼噪聲信道信源信宿——把信源編碼并入信源，信道編碼并入信道。三、通信系統(tǒng)的性能指標(biāo)及相應(yīng)的編碼

問題通信系統(tǒng)主要性能指標(biāo)主要是:有效性、可靠性、安全性和經(jīng)濟性。通信系統(tǒng)優(yōu)化就是使這些指標(biāo)達(dá)到最佳。根據(jù)信息論的各種編碼定理和上述通信系統(tǒng)的指標(biāo)，編碼問題可分解為三類：信源編碼、信道編碼和密碼編碼。比如電報中的莫爾斯碼、條形碼、ISBN、計算機中的糾錯碼。。。1、信源編（譯）碼器信源編碼器的作用是把信源發(fā)出的消息變換成由二進制碼元（或多進制碼元）組成的代碼組，這種代碼組就是基帶信號；同時通過信源編碼可以壓縮信源的冗余度（即多余度），以提高通信系統(tǒng)傳輸消息的效率。信源編碼器分為兩類一類是無失真信源編碼，適用于離散信源或數(shù)字信號；另一類是限失真信源編碼，用于連續(xù)信源或模擬信號，如語音、圖像等信號的數(shù)字處理。信源編碼器的主要指標(biāo)是它的編碼效率，即理論上能達(dá)到的碼率與實際達(dá)到的碼率之比。一般來說，效率越高，編譯碼器的代價也將越大。信源譯碼器的作用是把信道譯碼器輸出的代碼組變換成信宿所需要的消息形式，它的作用相當(dāng)于信源編碼器的逆過程。2、信道編（