第1章 信息論預(yù)編碼緒論

2023/2/51信息論與編碼理論

40學(xué)時(shí)張延良計(jì)算機(jī)學(xué)院ylzhang119@TEL:136139147852023/2/52教材教材：《信息論與編碼》第2版電子工業(yè)出版社十一五規(guī)劃教材陳運(yùn)主編參考書(shū)：《信息與編碼理論基礎(chǔ)》

上海大學(xué)出版社萬(wàn)旺根主編《信息論基礎(chǔ)》北京航空航天大學(xué)出版社周蔭清主編《信息論與編碼》清華大學(xué)出版社2023/2/53前續(xù)課程概率論與數(shù)理統(tǒng)計(jì)信號(hào)與系統(tǒng)后繼課程通信原理計(jì)算機(jī)網(wǎng)絡(luò)移動(dòng)通信2023/2/54主要內(nèi)容2.12345概論信源熵信道容量信息率失真函數(shù)信源編碼147信道編碼密碼學(xué)62023/2/55第1章概論主要內(nèi)容：1.1信息的一般概念1.2通信系統(tǒng)模型1.3信息論的起源、發(fā)展1.4信息論的研究?jī)?nèi)容2023/2/56第2章信源熵主要內(nèi)容：2.1單符號(hào)離散信源

2.2多符號(hào)離散平穩(wěn)信源及熵2.3連續(xù)信源及熵2023/2/57第3章信道容量主要內(nèi)容：3.1信道的數(shù)學(xué)模型與分類3.2單符號(hào)離散信道的信道容量3.3多符號(hào)離散信道的信道容量3.4連續(xù)信道及其容量2023/2/58第4章信息率失真函數(shù)主要內(nèi)容：4.1基本概念4.2

離散無(wú)記憶信源R(D)的計(jì)算4.3連續(xù)無(wú)記憶信源的R(D)的計(jì)算

2023/2/59第5章信源編碼主要內(nèi)容：5.1離散信源最佳變長(zhǎng)編碼5.2連續(xù)信源編碼2023/2/510第6章信道編碼主要內(nèi)容：6.1信道編碼簡(jiǎn)介6.2線性分組碼6.3循環(huán)碼6.4卷積碼2023/2/511第7章密碼學(xué)主要內(nèi)容：密碼基本知識(shí)古典密碼體制現(xiàn)代密碼體制2023/2/512主要內(nèi)容2.12345概論信源熵信道容量信息率失真函數(shù)信源編碼147信道編碼密碼學(xué)6離散信源連續(xù)信源單符號(hào)離散信源多符號(hào)離散信源離散信道容量連續(xù)信道容量：信源壓縮編碼的理論基礎(chǔ)離散信源連續(xù)信源定長(zhǎng)編碼變長(zhǎng)編碼線性分組碼循環(huán)碼卷積碼2023/2/513第1章概論主要內(nèi)容：1.1信息的一般概念1.2通信系統(tǒng)模型1.3信息論的起源、發(fā)展1.4信息論的研究?jī)?nèi)容2023/2/514信息社會(huì)人類社會(huì)的生存和發(fā)展，時(shí)刻離不開(kāi)接收信息、傳遞信息、處理信息和利用信息。古代烽火臺(tái)上的狼煙，傳遞的是戰(zhàn)爭(zhēng)信息，通知人們有敵來(lái)犯?；▋洪_(kāi)放時(shí)的色彩和花香，傳遞的是信息，引誘蜜蜂蝴蝶為其授粉。天冷了，感覺(jué)到身上起雞皮疙瘩，傳遞的是冷暖信息，告訴人們?cè)撎硪路恕堎N畫(huà)像，傳遞的是人的相貌信息，用于尋人。2023/2/515信息是人們對(duì)客觀事物運(yùn)動(dòng)規(guī)律及其存在狀態(tài)的認(rèn)識(shí)結(jié)果。信息的價(jià)值在于它為人們能動(dòng)地改造外部世界提供了可能。2023/2/516信息的傳輸手段信息的傳輸手段的變革，傳輸速度的快慢，決定了一個(gè)社會(huì)的現(xiàn)代化程度和發(fā)展速度。戰(zhàn)爭(zhēng)情報(bào)（信息）：古代用烽火狼煙、快馬來(lái)報(bào)現(xiàn)代用計(jì)算機(jī)網(wǎng)絡(luò)、無(wú)線通信手段來(lái)報(bào)尋人（信息）：古代用張貼畫(huà)像現(xiàn)代用互聯(lián)網(wǎng)通緝、人肉搜索講課傳授知識(shí)（信息）：以前用板書(shū)現(xiàn)在用多媒體課件2023/2/517信息的定義通俗地理解：信息被認(rèn)為是消息、知識(shí)、情報(bào)。信息與其聯(lián)系密切，但信息的定義更深刻、廣泛。信息不等同于消息：有神秘人士告訴你兩條絕密消息：世界銀行要招副總裁比爾蓋茨要為女兒擇婿知識(shí)是一種具有普遍性和概括性的高層次的信息情報(bào)是軍事上專用的一類特定的信息信息就是信息，它既不是物質(zhì)也不是能量（1948年，維納）。信息、物質(zhì)和能量是構(gòu)成一切系統(tǒng)的三大要素。2023/2/518信息與消息的關(guān)系信息是系統(tǒng)中傳送（或存儲(chǔ)、處理）的對(duì)象，它包含在消息之中。同一信息可用不同消息形式（如語(yǔ)言、文字、圖像）來(lái)傳遞。如巴菲特、比爾蓋茨要來(lái)中國(guó)開(kāi)慈善晚宴的信息通過(guò)電視新聞、廣播、網(wǎng)絡(luò)、報(bào)紙等傳輸媒介以圖像、聲音、文字的消息形式為人所知。消息是信息的載體，是比較具體的形式，如語(yǔ)言，文字，數(shù)字，圖像。所有這些形式都是可以被人們所感覺(jué)到的。2023/2/519消息與信號(hào)的關(guān)系信號(hào)是消息的載體。是用來(lái)表示消息的物理量（聲音信號(hào)、電信號(hào)、光信號(hào)）可用不同類型的信號(hào)（如聲、光、電）傳遞同一消息。如“日軍轟炸珍珠港”的信息，用漢文“日軍轟炸珍珠港”的消息來(lái)表述，然后用電報(bào)系統(tǒng)把漢字轉(zhuǎn)化為莫爾斯碼，再轉(zhuǎn)化，調(diào)制成電信號(hào)進(jìn)行傳輸。此時(shí)電信號(hào)里載荷有漢文消息“日軍轟炸珍珠港”。2023/2/520信號(hào)攜帶消息，消息表征信息。同一信息可以用不同的信號(hào)來(lái)表示高考成績(jī)（信息）可以通過(guò)電話查詢（電信號(hào)）得到；也可以通過(guò)網(wǎng)絡(luò)查詢得到（數(shù)字信號(hào)）。同一信號(hào)在不同的情況下表示不同的信息紅綠燈信號(hào)在十字路口表示是否通行的信息在電子儀器板上，表示儀器是否正常工作的信息信號(hào)消息信息2023/2/521信息的主要特征信息是無(wú)形的，看不見(jiàn)，摸不著，不具實(shí)體性，它必須依賴一定的消息形式才能為人所獲知。信息有大小，可以度量：如考試成績(jī)：有人考的不好，估計(jì)就在50分上下，及格的概率為51%，那么這個(gè)同學(xué)一旦獲知考試及格了，會(huì)非常的興奮，會(huì)認(rèn)為這個(gè)消息包含的信息量很大。有人考的好，估計(jì)在80分上下，及格的概率為99.9%，那么這個(gè)同學(xué)如果獲知考試及格了，會(huì)很平靜，認(rèn)為在意料之中，那么這個(gè)消息包含的信息量就很小。消息在收到之前未知（以一定的概率存在），收到之后可以獲取信息，從而認(rèn)識(shí)事物。信息可以共享（互聯(lián)網(wǎng)就是一個(gè)共享各種信息的平臺(tái)）。信息可以壓縮，傳輸，接收，消失。有一定的時(shí)效性。2023/2/522信息科學(xué)信息科學(xué)是一門(mén)綜合性學(xué)科，它研究信息及其運(yùn)動(dòng)規(guī)律。研究的內(nèi)容包括：信息的本質(zhì)及其度量，信息的產(chǎn)生、獲取、傳播、存儲(chǔ)及處理。研究的目的：擴(kuò)展人們獲取信息的手段和速度，提高信息的利用能力2023/2/523信息科學(xué)帶來(lái)的信息產(chǎn)業(yè)信息產(chǎn)業(yè)是專門(mén)從事信息的生產(chǎn)、傳播、出售和服務(wù)的行業(yè)。包括：信息技術(shù)設(shè)備制造：手機(jī)生產(chǎn)、天線制造、交換機(jī)生產(chǎn)、光纜/光傳輸設(shè)備生產(chǎn)…….信息服務(wù)：手機(jī)增值業(yè)務(wù)開(kāi)發(fā)、電子出版、數(shù)據(jù)庫(kù)服務(wù)、網(wǎng)絡(luò)接入服務(wù)、網(wǎng)絡(luò)應(yīng)用服務(wù)（企業(yè)信息化建設(shè)、電子商務(wù)）、網(wǎng)絡(luò)推廣…….2023/2/524第1章概論（簡(jiǎn)介）主要內(nèi)容：1.1信息的基本概念1.2通信系統(tǒng)模型1.3信息論的起源、發(fā)展、研究?jī)?nèi)容1.4研究?jī)?nèi)容2023/2/525通信系統(tǒng)通信系統(tǒng)：信息的傳輸系統(tǒng)。如：電話、計(jì)算機(jī)系統(tǒng)2023/2/5261.2通信系統(tǒng)模型信源、信道、信宿信源是消息的來(lái)源信道是消息傳送媒介信宿是消息的目的地信源編碼器信道譯碼器信宿干擾源2023/2/527通信系統(tǒng)模型進(jìn)一步細(xì)分信源信源編碼器糾錯(cuò)編碼器調(diào)制器信道干擾源解調(diào)器信道譯碼器信源譯碼器信宿等效離散信道等效離散信源等效信宿信道編碼器信道譯碼器產(chǎn)生消息的源，消息可以是文字，語(yǔ)言，圖像?？梢噪x散，可以連續(xù)。隨機(jī)發(fā)生。研究的主要問(wèn)題是消息的統(tǒng)計(jì)特性和產(chǎn)生信息的速率對(duì)信源輸出進(jìn)行變換，重在有效性對(duì)信源編碼輸出變換，提高抗干擾性將信道編碼輸出變成適合信道傳輸?shù)姆绞叫盘?hào)從發(fā)端傳到收端的介質(zhì)信道的中心問(wèn)題是研究信道的統(tǒng)計(jì)特性和傳信能力，即信道容量系統(tǒng)各部分引入的干擾，包括衰落，多徑，碼間干擾，非線性失真，加性噪聲。這種干擾源的統(tǒng)計(jì)特性是劃分信道的重要因素，并且是決定其傳輸能力的決定因素。譯碼器：編碼器的逆變換中心問(wèn)題是研究各種可實(shí)現(xiàn)的解調(diào)和譯碼方法信息的接收者2023/2/528通信系統(tǒng)模型組成信源信宿信源編/譯碼信源編碼集中于解決傳輸?shù)挠行詥?wèn)題；去除冗余信息例：語(yǔ)音壓縮編碼Vocoder圖象壓縮編碼JPEGMEPG文本壓縮編碼Winzip

信道編/譯碼信道編碼集中于解決抗信道干擾和失真問(wèn)題，即解決傳輸?shù)目煽啃詥?wèn)題。需要添加冗余信息例：卷積碼、級(jí)聯(lián)碼、Turbo碼調(diào)制/解調(diào)電波輻射傳播多址接入信道復(fù)接躲避和抑制干擾信道加性噪聲乘性衰落2023/2/529信息傳輸系統(tǒng)的性能要求可靠性：使信源發(fā)出的消息經(jīng)信道傳輸后，盡可能準(zhǔn)確地、不失真地在接收端重現(xiàn)。有效性：用盡可能短的時(shí)間和盡可能少的設(shè)備來(lái)傳輸一定數(shù)量的信息。保密性：隱蔽或保護(hù)通信系統(tǒng)中傳輸?shù)男畔ⅲ顾荒鼙皇跈?quán)接收者獲取，非授權(quán)接收者不能接收和理解。認(rèn)證性：接收者能夠正確判斷接收到的消息的正確性。驗(yàn)證消息的完整性，判定不是偽造或篡改的。可靠性、有效性、保密性和完整性共同構(gòu)成現(xiàn)代通信傳輸系統(tǒng)的全面要求。2023/2/530第1章概論（簡(jiǎn)介）主要內(nèi)容：1.1信息的基本概念1.2通信系統(tǒng)模型1.3信息論的起源、發(fā)展1.4研究?jī)?nèi)容2023/2/5311948年以前信息論的發(fā)展Telegraph(Morse,1830’s);Telephone(Bell,1876);WirelessTelegraph(Marconi,1887);AMRadio(early1900’s)Single-SidebandModulation(Carson,1922);1924年H.Nyquist：信號(hào)帶寬與信息速率的關(guān)系。指出如果以一定的速率來(lái)傳輸信號(hào)，則需要一定的帶寬，將信息率和帶寬聯(lián)系起來(lái)了。Television(1925-1927);1928年，R.V.Hartley：提出用對(duì)數(shù)度量信息。Teletype(1931);FrequencyModulation(Armstrong,1936)：增大帶寬，可以提高抗干擾能力?；诖怂枷耄岢鰧掝l移調(diào)制。Pulse-CodeModulation(PCM)(Reeves,1937-1939);Vocoder(Dudley,1939)：廣泛應(yīng)用于廣播、電視。提出了通信帶寬>=傳送的消息帶寬SpreadSpectrum(1940’s).2023/2/532控制論之父——維納N.Winner（維納）20世紀(jì)30年代“廣義諧波分析理論”，首次對(duì)信息系統(tǒng)中的隨機(jī)過(guò)程進(jìn)行譜分析。20世紀(jì)40年代：將隨機(jī)過(guò)程和數(shù)理統(tǒng)計(jì)的觀點(diǎn)引入通信和控制領(lǐng)域，揭示信息傳輸和處理過(guò)程的統(tǒng)計(jì)本質(zhì)。20世紀(jì)50年代：提出干擾作用下的最佳濾波定理。2023/2/533信息論鼻祖——香農(nóng)Shannon1948年“通信的數(shù)學(xué)理論”（“Amathematicaltheoryofcommunication”）文章的發(fā)表，標(biāo)志著信息論的正式誕生。指明通信的實(shí)質(zhì)：“Thefundamentalproblemofcommunicationisthatofreproducingatonepointeitherexactlyorapproximatelyamessageselectedatanotherpoint.”提出無(wú)失真信源編碼定理，給出了簡(jiǎn)單的編碼方法（香農(nóng)編碼）2023/2/534無(wú)失真信源編碼的發(fā)展1956年，麥可米倫（B.Mcmillan）首先證明了唯一可譯變長(zhǎng)碼的克拉夫特（Craft）不等式。1952年，費(fèi)諾（Fano）提出了一種費(fèi)諾碼。1952年，哈夫曼（D.A.Huffman）首先構(gòu)造了一種哈夫曼編碼方法，并證明為最佳碼。1977年，通用信源編碼算法-LZ碼由齊弗(J.Ziv)和蘭佩爾（A.Lempel）提出.1978年，他們又提出了改進(jìn)算法，并證明此方法可以達(dá)到信源的熵值。1990年，貝爾（Bell）又對(duì)LZ算法進(jìn)行了一系列的變化和改進(jìn)。目前，LZ廣泛應(yīng)用于文本的數(shù)據(jù)壓縮。語(yǔ)音編碼標(biāo)準(zhǔn):MP3,MP4圖象編碼標(biāo)準(zhǔn):MPEG42023/2/535信道編碼理論的發(fā)展60年代起，信道編碼技術(shù)有了長(zhǎng)足發(fā)展。1950年，出現(xiàn)了漢明碼（HammingCode）和循環(huán)碼（CyclicCode），把代數(shù)方法引入糾錯(cuò)碼的研究，形成了代數(shù)編碼理論。但代數(shù)編碼的漸進(jìn)性較差，無(wú)法實(shí)現(xiàn)香農(nóng)信道編碼定理所指出的結(jié)果。1960年左右，提出了卷積碼（ConvolutionCode）的概率譯碼。形成一系列概率譯碼理論。幾十年來(lái)，相繼出現(xiàn)很多編碼算法，性能與香農(nóng)限相差甚遠(yuǎn)，以致人們認(rèn)為香農(nóng)限是不可能達(dá)到的。1993年，法國(guó)學(xué)者C.Berrou等人提出了Turbo碼的并行級(jí)聯(lián)卷積碼，其性能與香農(nóng)限非常接近(誤碼率達(dá)10-5)，且復(fù)雜度較低可以實(shí)現(xiàn)，為信道編碼領(lǐng)域帶來(lái)一場(chǎng)革命。2023/2/536限失真信源編碼定理的發(fā)展限失真信源編碼的研究較信道編碼和無(wú)失真信源編碼晚了近十年。香農(nóng)在1948年的論文中已體現(xiàn)了率失真函數(shù)的思想。1959年，香農(nóng)發(fā)表了“保真度準(zhǔn)則下的離散信源編碼定理”（“Codingtheoremsforadiscretesourcewithafidelitycriterion”），首先提出了率失真函數(shù)和率失真信源編碼定理。從此，發(fā)展成為信息率失真編碼理論。1971年，伯格爾（T.Beger）給出了更一般信源的率失真編碼定理。率失真信源編碼定理是信源編碼的核心問(wèn)題，是頻帶壓縮、數(shù)據(jù)壓縮（信源壓縮編碼）的理論基礎(chǔ)。2023/2/537網(wǎng)絡(luò)信息論的發(fā)展1961年，香農(nóng)發(fā)表的論文“雙路通信信道”開(kāi)拓了多用戶信息理論。隨著衛(wèi)星通信、計(jì)算機(jī)通信網(wǎng)的迅速發(fā)展，多用戶理論的研究取得了突破性的進(jìn)展。20世紀(jì)70年代以后，人們從經(jīng)典的香農(nóng)單向通信的信息論推廣到多用戶信息理論。多用戶信息理論成為當(dāng)前信息論的中心研究課題之一。2023/2/538第1章概論（簡(jiǎn)介）主要內(nèi)容：1.1信息的基本概念1.2通信系統(tǒng)模型1.3信息論的起源、發(fā)展1.4研究?jī)?nèi)容2023/2/5391.4信息論研究的內(nèi)容狹義信息論（經(jīng)典信息論）即Shannon信息論研究信息測(cè)度，信道容量以及信源和信道編碼理論信息的度量信道的容量信息率失真函數(shù)信源編碼信道編碼2023/2/540Shannon信息論的中心問(wèn)題信息傳輸中出現(xiàn)的問(wèn)題：

問(wèn)題一：信源消息常常不能夠完全發(fā)送。（否則發(fā)送量巨大，比如：信源消息是一片無(wú)盡的天空。因此優(yōu)先揀有用的發(fā)送。什么是有用的？就是信息量大的。什么是信息量大的？）問(wèn)題二：信道因干擾而出現(xiàn)差錯(cuò)，必須進(jìn)行檢錯(cuò)和糾錯(cuò)。（否則所收到的消息無(wú)法識(shí)別。）

信源信道信宿2023/2/541Shannon信息論針對(duì)以上問(wèn)題的解決方法：?jiǎn)栴}一：如何揀有用的信源信息來(lái)發(fā)送。通過(guò)信源編碼，去掉冗余的信息，提高有效性。問(wèn)題二：如何抵抗或抵消傳輸中遇到的干擾引起的誤碼。通過(guò)信道編碼，增加多余的信息，使各符號(hào)間相互存在一定的牽連關(guān)系，提高可靠性。如：傳輸用戶的密碼信息：aqv分析：26種符號(hào)每個(gè)符號(hào)最少用5位二進(jìn)制來(lái)進(jìn)行信源編碼000000101001110想增加抗干擾能力，最簡(jiǎn)單的信道編碼時(shí)奇偶校驗(yàn)碼，即增加一位，使和其它各位相加后結(jié)果為0：0000000101000111012023/2/542狹義信息論體系結(jié)構(gòu)Shannon信息論壓縮理論有失真編碼無(wú)失真編碼等長(zhǎng)編碼定理Shannon1948McMillan1953變長(zhǎng)編碼定理Shannon1948McMillan1956Huffman碼(1952)、Fano碼算術(shù)碼(1976,1982)LZ碼(1977,1978)率失真理論ShannonGallagerBerger壓縮編碼JPEGMPEG傳輸理論信道編碼定理網(wǎng)絡(luò)信息理論糾錯(cuò)碼編碼調(diào)制理論網(wǎng)絡(luò)最佳碼2023/2/5431.4信息論的研究?jī)?nèi)容

——續(xù)一般信息論研究信息傳輸和處理問(wèn)題，除經(jīng)典信息論外還包括噪聲理論，信號(hào)濾波和預(yù)測(cè)，統(tǒng)計(jì)檢測(cè)和估值理論，調(diào)制理論，信息處理理論和保密理論一般信息論：香農(nóng)信息論+Winner的濾波理論Shannon

：研究的對(duì)象是信源到信宿的傳輸全過(guò)程，是收發(fā)端聯(lián)合優(yōu)化問(wèn)題。解決的方法是編碼。Winner：研究消息在傳輸中受到干擾時(shí)，如何在接收端將消息從干擾中提取出來(lái)。包括解決方法是濾波。重點(diǎn)在接收端。2023/2/544廣義信息論：用信息基本理論來(lái)研究一切可以抽象為廣義通信系統(tǒng)模型的過(guò)程或系統(tǒng)。除一般信息論研究的內(nèi)容外，還包括自然和社會(huì)領(lǐng)域有關(guān)信息的內(nèi)容，如模式識(shí)別，計(jì)算機(jī)翻譯，心理學(xué)，遺傳學(xué)，神經(jīng)生理學(xué)1.4信息論的研究?jī)?nèi)容

——續(xù)2023/2/545克勞德.艾爾伍德.香農(nóng)（ClaudeElwoodShannon）

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

香農(nóng)（1916—2001）：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年。1956年他成為麻省理工學(xué)院（MIT）客座教授，并于1958年成為終生教授，1978年成為名譽(yù)教授。香農(nóng)博士于2001年2月26日去世，享年84歲。返回2023/2/546維納維納是美國(guó)數(shù)學(xué)家，控制論的創(chuàng)始人。維納1894年11月26日生于密蘇里州的哥倫比亞，1964年3月18日卒于斯德哥爾摩。

維納認(rèn)為他父親是天生的學(xué)者，集德國(guó)人的思想、猶太人的智慧和美國(guó)人的精神于一身。從童年到青年，維納一直在他的熏陶下生活，并逐步成長(zhǎng)為一個(gè)學(xué)者。2023/2/547維納趣事20世紀(jì)著名數(shù)學(xué)家諾伯特·維納，從小就智力超常，三歲時(shí)就能讀寫(xiě)，十四歲時(shí)就大學(xué)畢業(yè)了。幾年后，他又通過(guò)了博士論文答辯，成為美國(guó)哈佛大學(xué)的科學(xué)博士。在博士學(xué)位的授予儀式上，執(zhí)行主席看到一臉稚氣的維納，頗為驚訝，于是就當(dāng)面詢問(wèn)他的年齡。維納不愧為數(shù)學(xué)神童，他的回答十分巧妙：“我今年歲數(shù)的立方是個(gè)四位數(shù)，歲數(shù)的四次方是個(gè)六位數(shù)，這兩個(gè)數(shù)，剛好把十個(gè)數(shù)字0、1、