第1章 信息論預編碼緒論

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

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

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

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

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

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

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

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

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

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

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

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

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

香農(nóng)（1916—2001）：1916年4月30日出生于美國密歇根州的加洛德（Petoskey）1936年畢業(yè)于密歇根大學并獲得數(shù)學和電子工程學士學位1940年獲得麻省理工學院（MIT）數(shù)學博士學位和電子工程碩士學位1941年他加入貝爾實驗室數(shù)學部，工作到1972年。1956年他成為麻省理工學院（MIT）客座教授，并于1958年成為終生教授，1978年成為名譽教授。香農(nóng)博士于2001年2月26日去世，享年84歲。返回2023/2/546維納維納是美國數(shù)學家，控制論的創(chuàng)始人。維納1894年11月26日生于密蘇里州的哥倫比亞，1964年3月18日卒于斯德哥爾摩。

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