第1章-信息論基礎(chǔ)

不定時點到自學??！提問，平時成績計分方式最后期終考試成績占70％平時成績占20％作業(yè)：一次不交扣1分，無故缺席一次扣1分，遲到一次扣0.5分手機聲響扣1分嚴重違反課堂紀律，視情節(jié)輕重扣分課程實驗占10%第1章信息論基礎(chǔ)

第1章信息論基礎(chǔ)

內(nèi)容提要信息論是應(yīng)用近代概率統(tǒng)計方法研究信息傳輸、交換、存儲和處理的一門學科，也是源于通信實踐發(fā)展起來的一門新興應(yīng)用學科。本章首先引出信息的概念，簡述信息傳輸系統(tǒng)模型的各個組成部分，進而討論離散信源和離散信道的數(shù)學模型，簡單介紹幾種常見的離散信源和離散信道。主要內(nèi)容1、信息的概念，信息論的研究對象，目的，內(nèi)容，形成與發(fā)展。2、信源及其數(shù)學模型3、信道及其數(shù)學模型1.1信息的概念人類從產(chǎn)生那天起，就生活在信息的海洋之中。人類社會的生存和發(fā)展，一時一刻都離不開接受信息、傳遞信息、處理信息、提取和利用信息。結(jié)繩記事，烽火告警等。那么，什么是信息呢？信息不等于消息。人們常常錯誤地把信息等同于消息，認為得到了消息，就是得到了信息。消息：用文字、符號、數(shù)據(jù)、語言、音符、圖片、圖像等能夠被人們感覺器官所感知的形式，把客觀物質(zhì)運動和主觀思維活動的狀態(tài)表達出來就成為消息。香農(nóng)在1948年發(fā)表了著名的論文：AMathematicalTheoryofCommunication——通信的數(shù)學理論。他從研究通信系統(tǒng)傳輸?shù)膶嵸|(zhì)出發(fā)，對信息做了科學的定義，并進行了定性和定量的描述。香農(nóng)簡介：香農(nóng)簡介

（ClaudeElwoodShannon，1916.4.30-2001.2.26）

1938年香農(nóng)獲得電氣工程碩士學位，碩士1940年獲得數(shù)學博士學位，博士論文卻是關(guān)于人類遺傳學

。之后就職于貝爾實驗室。1948年發(fā)表《通信的數(shù)學原理》，1949發(fā)表《噪聲下的通信》。香農(nóng)博士于2001年2月26日去世，享年84歲尊崇香農(nóng)為信息論及數(shù)字通信時代的奠基人。

美國AlfredNoble協(xié)會美國工程師獎1940年

MorrisLiebmann無線電工程師協(xié)會Memorial獎?wù)?949年耶魯大學(首席科學家)1954年

StuartBallantine弗蘭克林協(xié)會獎?wù)?955年研究合作獎1956年密歇根大學,榮譽博士1961年萊斯大學榮譽獎?wù)?962年普林斯頓大學,榮譽博士1962年

MarvinJ.KellyAward1962年愛丁堡大學榮譽博士1964年匹茲堡大學榮譽博士1964年電子電氣工程師協(xié)會榮譽獎?wù)?966年美國國家科學獎?wù)?966年,由前總統(tǒng)LyndonB.約翰遜頒發(fā)

GoldenPlateAward1967年美國西北大學,榮譽博士1970年

HarveyPrize,theTechnionofHaifa,以色列1972年牛津大學榮譽博士1978年

JosephJacquard獎1978年

HaroldPender獎1978年東英格倫大學,榮譽博士1982年卡內(nèi)基梅隆大學榮譽博士1984年美國聲頻技術(shù)協(xié)會金獎1985年

KyotoPrize1985年塔夫斯大學榮譽博士1987年賓西法尼亞大學榮譽博士1991年

EduardRheinPrize1991年香農(nóng)信息的定義信息是事物運動狀態(tài)或存在方式的不確定性的描述。香農(nóng)將各種通信系統(tǒng)概括成如圖1.1所示的框圖。在各種通信系統(tǒng)中，其傳輸?shù)男问绞窍ⅰ５鬟f過程的一個最基本、最普遍卻又不十分引人注意的特點是：（1）收信者在收到消息以前是不知道消息的具體內(nèi)容的。在收到消息以前，收信者無法判斷發(fā)送者將會發(fā)來描述何種事物運動狀態(tài)的具體消息；他也更無法判斷是描述這種狀態(tài)還是那種狀態(tài)。（2）即使收到消息，由于干擾的存在，他也不能確定所得到的消息是否正確和可靠。圖1.1總之，收信者存在著“不知”，“不確定”，“疑問”。通過消息的傳遞，收信者知道了消息的內(nèi)容，原先的不知，不確定和疑問消除或部分消除了。因此，對于收信者來說，消息的傳遞過程是一個從不知到知的過程，或是從知之甚少到知之甚多的過程，或是從不確定到部分確定或全部確定的過程。所以，通信過程是一種消除不確定性的過程。不確定性的消除，就獲得了信息。原先的不確定性消除的越多，獲得的信息就越多。如果原先的不確定性全部消除了，就獲得了全部的信息；若消除了部分不確定性，就獲得了部分消息；若原先不確定性沒有任何消除，就沒有獲得任何的信息。由此可見信息是事物運動狀態(tài)或存在方式的不確定性的描述。天氣預報孫麗華教授書上對信息的定義鐘義信教授的定義鐘義信簡介鐘義信1940年2月出生,漢族，

北京郵電大學教授、博士生導師、副校長、校學術(shù)委員會主席。長期從事通信理論、信息理論、信息科學、人工智能、神經(jīng)網(wǎng)絡(luò)、決策學、信息經(jīng)濟學領(lǐng)域的研究和教學工作，在上述領(lǐng)域先后出版學術(shù)著作16部，在國內(nèi)外學術(shù)刊物和學術(shù)會議上發(fā)表學術(shù)論文380多篇。代表性學術(shù)論著包括《信息科學原理》（1988年）、《信息技術(shù)通論》（1994）、《智能理論與技術(shù)—人工智能與神經(jīng)網(wǎng)絡(luò)》（1992）、《偽隨機編碼通信：原理與應(yīng)用》（1978）等。具有重要創(chuàng)新意義的學術(shù)貢獻主要包括“知識論”、“全信息理論”、“意識機模型”、“信息科學原理與信息科學方法論”、“信息基礎(chǔ)結(jié)構(gòu)理論模型”等。

1989年國務(wù)院人事部授予“有突出貢獻中青年專家”稱號

1989年國家教委授予“全國優(yōu)秀教師”稱號，

1991年國務(wù)院人事部和國家教委聯(lián)合授予“有突出貢獻的歸國留學人員”稱號，享受國務(wù)院特殊津帖，

1994年國際神經(jīng)網(wǎng)絡(luò)學會（InternationalNeuralNetworkSociety,INNS）授予“國際優(yōu)秀學術(shù)帶頭人”證書

2002年獲得亞太神經(jīng)網(wǎng)絡(luò)聯(lián)合會（Asian-PacificNeuralNetworkAssembly,APNNA）“主席獎”。曾任IEEETransactionsonNeuralNetworks副主編（1993-2005）國務(wù)院信息化工作領(lǐng)導小組辦公室專家委員會常務(wù)委員（1993-2001）

國家863計劃通信主題首屆首席專家（1992-1994）國家863計劃信息領(lǐng)域戰(zhàn)略研究負責人?，F(xiàn)在是中國人工智能學會理事長'教育部全國工程教育專業(yè)認證專家委員會副主任'

《電子學報》副主編，

《中興新通訊》雜志主編，

《20世紀中國學術(shù)大典—信息科學與通信工程卷》主編，

IEEETransactionsonNeuralNetworks雜志副主編，

IEEE北京分部執(zhí)行委員，IEEE美國紐約科學院院士。1988年，我國信息論專家鐘義信教授在《信息科學原理》給出信息的定義語法信息是事物運動狀態(tài)和狀態(tài)改變的方式的本身。所以它不涉及這些狀態(tài)的含義和效用，是最抽象最基本的層次。它只研究事物運動各種可能出現(xiàn)的狀態(tài)，以及狀態(tài)之間的關(guān)系。香農(nóng)的信息定義正是屬于這個層次，是從概率統(tǒng)計角度來研究事物運動各種可能出現(xiàn)的狀態(tài)及狀態(tài)間的關(guān)系，因此是概率性的語法信息。它能較好地解決通信工程這樣一類信息傳遞的問題。語法信息，語義信息，語用信息語義信息是事物運動狀態(tài)和方式的具體含義。這是研究各種狀態(tài)和實體間的關(guān)系，即研究信息的具體含義的。語用信息是事物運動狀態(tài)和方式及其含義對觀察者的效用，或者是相對于某種目的的效用。這是研究事物運動狀態(tài)和方式與使用者的關(guān)系，即研究信息的主觀價值。EXAMPLE我聞西方大士，為人了卻凡心。秋來明月照蓬門，香滿禪房幽徑。

屈指靈山會后，居然紫竹成林。童男童女拜觀音，仆仆何嫌榮頓？從第一個字到最后一個字每句話的第一個字所包含的意義第一字聯(lián)系在一起——“我為秋香，屈居童仆”信息的概念-小結(jié)信息是事物運動狀態(tài)或存在方式的不確定性的描述。通信系統(tǒng)中形式上傳輸?shù)氖窍?，實質(zhì)上傳輸?shù)氖切畔?，消息中包含信息，消息是信息的載體。信息論是研究信息的基本性質(zhì)及度量方法，研究信息的獲取、傳輸、存儲和處理的一般規(guī)律的學科。

思考：信息與情報、知識、信號之間的關(guān)系？物質(zhì)世界的三大要素？信息，物質(zhì)，能量信息是信息論中最基本、最重要的概念，既抽象又復雜信息在日常生活中被認為是“消息”、“知識”、“情報”等“信息”不同于消息（在現(xiàn)代信息論形成之前，信息一直被看作是通信中消息的同義詞，沒有嚴格的數(shù)學含義），消息是表現(xiàn)形式，信息是實質(zhì)；“信息”不同于情報，情報的含義比“信息”窄的多，一般只限于特殊的領(lǐng)域，是一類特殊的信息；信息不同于信號，信號是承載消息的物理量；信息不同于知識，知識是人們根據(jù)某種目的,從自然界收集得來的數(shù)據(jù)中整理、概括、提取得到的有價值的信息，是一種高層次的信息。1.2信息論的研究對象--通信系統(tǒng)模型

通信的基本問題是在彼時彼地精確地或近似地再現(xiàn)此時此地發(fā)出的消息。各種通信系統(tǒng)，一般可概括為圖1.1所示的基本模型：

干擾源

信道信道譯碼器信道編碼器信源譯碼器信源編碼器信宿信源等效信源等效信宿等效無干擾信道-研究信息傳輸?shù)挠行詧D1-1通信系統(tǒng)模型

通信系統(tǒng)模型主要包括五個部分1.信源信源是產(chǎn)生消息和消息序列的源。它可以是人、生物、機器或其他的事物。它是事物各種運動狀態(tài)或存在狀態(tài)的集合。例如，籃球比賽的實況，各種氣象狀態(tài)等客觀存在是信源。人的大腦活動也是一種信源。2.編碼器2.編碼器編碼是把消息變換成信號的措施，而譯碼就是編碼的反變換。編碼器輸出的是適合信道傳輸?shù)男盘枺盘枖y帶者消息，它是信息的載荷者。編碼器可分為兩種：即信源編碼器和信道編碼器。信源編碼實際上是對信源的原始符號按一定的數(shù)學規(guī)則進行的一種代碼變換，目的是為了提高信息傳輸?shù)男?。而信道編碼是為了提高信息傳輸?shù)目煽啃远鴮ο⑦M行的變化和處理。

3.信道3.信道信道是指通信系統(tǒng)把載荷消息的信號從甲地傳輸?shù)揭业氐拿浇椤Ｈ?，光纖，電纜，無線電波，磁盤，書籍等。信道上不可避免地存在各種干擾，比如來源于無線發(fā)射機的無線電干擾，電氣設(shè)備的工業(yè)干擾，以及宇宙射線的天電干擾及電子器件的內(nèi)部干擾等。為了分析方便，我們將系統(tǒng)其它部分產(chǎn)生的各種干擾都等效地折合成信道干擾。信道輸出的已是疊加了干擾的信號。由于干擾或噪聲往往具有隨機性，所以信道的特性也可以用概率空間來描述。4.譯碼器4.譯碼器譯碼就是把信道輸出（已疊加了干擾）的編碼信號進行反變換。要從受干擾的編碼信號中最大限度地提取出有關(guān)信源輸出的信息。譯碼器也可分為信源譯碼器和信道譯碼器。信源譯碼器就是將信道中傳輸?shù)母鞣N信號還原成收信者能感知的消息。信道譯碼就是從受干擾的信號中盡可能地糾正其中的錯誤，再現(xiàn)信源編碼器的輸出。5.信宿5.信宿信宿是消息傳送的對象，消息的接受者，即接受消息的人或機器。信源和信宿可處于不同地點和不同時刻。模型五個部分概括：3.信道信道是信息傳輸和存儲的媒介。4.譯碼器譯碼是編碼的逆變換，分為信道譯碼和信源譯碼。5.信宿信宿是消息的接收者。2.編碼器編碼器是將消息變成適合于信道傳送的信號的設(shè)備。1.信源信源是產(chǎn)生消息的源。編碼器信源編碼器，提高傳輸效率信道編碼器，提高傳輸可靠性2信息論的研究目的研究概括性強的通信系統(tǒng)，其目的：要找到信息傳輸過程的共同規(guī)律，以提高信息傳輸?shù)目煽啃浴⒂行?、保密性和認證性，使達到信息傳輸系統(tǒng)最優(yōu)化。有效性：所謂有效性高，就是經(jīng)濟效益好，即用盡可能短的時間和盡可能少的設(shè)備來傳送一定數(shù)量的信息?？煽啃裕核^可靠性高，就是要使信源發(fā)出的消息經(jīng)過信道傳輸以后，盡可能準確地不失真地再現(xiàn)在接收端。有效性和可靠性兩者往往相互矛盾，要提高有效性，就要減少信源的冗余度，縮短每個數(shù)據(jù)碼元所占的時間，這樣勢必使波形變窄，能量減少，從而使受到干擾后產(chǎn)生錯誤的可能性增加，傳遞消息的可靠性降低；若要求可靠，就要增加糾錯檢錯碼元，這樣增加了信道的冗余度，從而使傳遞消息的效率變慢。例如上例中，若發(fā)電報“奧運會”，當我們收到電報“X運會”時，無法判斷所發(fā)電報是“奧運會”、“亞運會”，還是“農(nóng)運會”等，可見，所發(fā)電文雖然冗余度很小，但容錯能力較差；而如果發(fā)電報“奧林匹克運動會”，當收到電報“X林匹克運動會”時，我們很容易糾正電文的錯誤.前面已講了有效性和可靠性保密性：所謂保密性就是隱藏和保護通信系統(tǒng)中傳送的消息，使它只能被授權(quán)接受者獲取，而不能被未授權(quán)者接收和理解。傳送的消息只被預定的接收者獲??；認證性：所謂認證性是指接收者能正確判斷所接收的消息的正確性，驗證消息的完整性，而不是偽造的和被竄改的。正確判斷所接收消息是預定發(fā)送者發(fā)送的。根據(jù)信息傳輸?shù)囊蟛煌?，信息傳輸系統(tǒng)模型不是不變的。研究有效性，可只考慮信源和信宿之間的信源編(譯)碼，將信道編碼器、信道譯碼器和信道組合起來，等效為一個無干擾信道，這樣信源編碼器的研究只和信源、信宿有關(guān)；研究可靠性，在研究信息傳輸?shù)目煽啃詴r，可將信源譯碼器和信宿等效為信宿，將信源和信源編碼器等效為一個對于信道編碼器而言的信源，這樣信道編碼的研究只和信道有關(guān)，與信源、信宿無關(guān)。研究保密性和認證性，將信源和信源編碼等效成一信源；將信道編碼、信道、噪聲源和信道譯碼等效成一無干擾信道；而將信源譯碼和信宿等效為一信宿。1.4.信息論的研究內(nèi)容目前，對信息論研究的內(nèi)容一般有以下三種理解。1、狹義信息論，也稱經(jīng)典信息論它主要研究信息的測度，信道容量及信源和信道編碼理論等問題。這部分內(nèi)容是信息論的基礎(chǔ)理論，又稱香農(nóng)基本理論。2.一般信息論也稱工程信息論它主要是研究信息傳輸和處理問題。除了香農(nóng)理論以外，還包括編碼理論、噪聲理論、信號濾波和預測理論，統(tǒng)計檢測與估計理論、調(diào)制理論，信息處理理論及保密理論等。后一部分內(nèi)容是以美國科學家維納為代表，其中最有貢獻的是維納和蘇聯(lián)科學家柯爾莫哥洛夫。3.廣義信息論它是一門綜合性的新興學科，它不僅包括上述兩方面的內(nèi)容，而且包括所有與信息有關(guān)的自然科學和社會科學領(lǐng)域，如模式識別，計算機翻譯，心理學，遺傳學，生物學，神經(jīng)生理學，語言學，語義學，甚至包括社會學，人文學和經(jīng)濟學中有關(guān)信息的問題，它也是新興的信息科學理論。

綜上所述，信息論是一門應(yīng)用概率論、隨機過程、數(shù)理統(tǒng)計和近代代數(shù)的方法，來研究廣義的信息傳輸、提取和處理系統(tǒng)中一般規(guī)律的學科；它主要目的是提高信息系統(tǒng)的可靠性、有效性、保密性和認證性，以便達到系統(tǒng)最優(yōu)化；它主要內(nèi)容（或分支）包括香農(nóng)理論、編碼理論、維納理論、檢測和估計理論、信號設(shè)計和處理理論、調(diào)制理論、隨機噪聲理論和密碼學理論等。由于信息論研究的內(nèi)容極為廣泛，而各分支又有一定的相對獨立性，因此本書僅論述信息論的基礎(chǔ)理論即香農(nóng)信息理論及編碼理論的基本內(nèi)容。信息論的研究小結(jié)：廣義信息論，包括信息論在自然和社會中的新的應(yīng)用，如模式識別、機器翻譯、自學習自組織系統(tǒng)、心理學、生物學、經(jīng)濟學、社會學等一切與信息問題有關(guān)的領(lǐng)域。實用信息論，研究信息傳輸和處理問題，也就是狹義信息論方法在調(diào)制解調(diào)、編碼譯碼以及檢測理論等領(lǐng)域的應(yīng)用。狹義信息論，即通信的數(shù)學理論，主要研究狹義信息的度量方法，研究各種信源、信道的描述和信源、信道的編碼定理。1.5信息論的形成與發(fā)展1.5.1電信系統(tǒng)的形成與發(fā)展一、有線通信系統(tǒng)二、無線電通信系統(tǒng)三、微波通信系統(tǒng)（波長在0.1mm---1m）四、光纖通信系統(tǒng)（波長在0.8μm---1.8μm）1.5.2通信理論的發(fā)展一、信息理論二、信號檢測與估計理論三、信源編碼理論四、信道編碼理論一、有線通信系統(tǒng)

1831年英國法拉第(Faraday)發(fā)現(xiàn)電磁感應(yīng)的基本規(guī)律。1844年美國莫爾斯(Morse)建立起了電報系統(tǒng)(數(shù)據(jù))。1875年蘇格蘭青年亞歷山大·貝爾(Bell)發(fā)明了世界上第一臺電話機(語音)。二、無線電通信系統(tǒng)1864年英國麥克斯韋(Maxwell)預言了電磁波的存在。1888年德國赫茲(Hertz)用實驗證明了電磁波存在這一預言。1895年意大利的馬可尼(Marconi)發(fā)明了無線電通信，通信距離近百米。1901年馬可尼成功地進行了跨越大西洋的遠距離無線電通信。1904年英國工程師弗萊明(Fleming)發(fā)明了真空二極管。具有更高的性能和靈敏度，大大提高了無線電通信的功能。1906年美國福雷斯特(Forest)制成了世界上第一只真空三極管。起到放大電信號的作用,大大提高了無線電通信的距離和可靠性。1925-1927,大功率超高頻電子管發(fā)明以后,電視系統(tǒng)(圖像)建立起來了。1925年蘇格蘭人貝爾德(Baird)和美國人斯福羅金(Zworykin)發(fā)明了電視系統(tǒng)（圖像）。前者稱做機械式，后者稱為電子式電視。三、微波通信系統(tǒng)（波長在0.1mm---1m）微波電子管是隨著微波波段的開發(fā)利用而發(fā)展起來的，它的應(yīng)用領(lǐng)域已擴展到微波中繼通信、衛(wèi)星通信、地面電視廣播、衛(wèi)星電視廣播、導航、能量傳輸、工業(yè)和民用加熱、科學研究等方面。五十年代后期發(fā)明了量子放大器，微波放大的裝置,這種放大器是噪聲最低的一種微波放大器,而且工作穩(wěn)定、線性度好。四、光纖通信系統(tǒng)（波長在0.8μm---1.8μm）世界上第一臺激光器誕生于1960年，我國于1961年研制出第一臺激光器,使人類進入了光纖通信的時代。1966年，英籍華人高錕最先提出用玻璃纖維進行遠距離激光通信的設(shè)想。1973年，美國康寧公司制成每千米傳輸損耗只有20分貝的光纖。同年，美國貝爾實驗室研制出能在常溫下連續(xù)工作的半導體激光器。這兩項技術(shù)突破為光纖通信的實現(xiàn)鋪平了道路。1976年，美國在芝加哥兩個相距7千米的電話局間首次進行了光纖通信試驗,實現(xiàn)了一根光纖能夠同時容納8000對人通話。1.5.2通信理論的發(fā)展一、信息理論1885年凱爾文(Kelvin)曾經(jīng)研究過一條電纜的極限傳信率問題。

1922年卡遜(Carson)研究了調(diào)幅信號頻譜結(jié)構(gòu)，提出了邊帶概念。

1924年奈奎斯特(Nyquist)和屈夫繆勒(Küpfmüller)解釋了信號帶寬和信息率之間的關(guān)系。

1928年哈特萊(Hartley)提出信息量等于可能消息數(shù)的對數(shù)。1936年阿姆斯特朗(Armstrong)提出在傳輸過程中增大帶寬可以增強抑制干擾的能力。1939年，瑞弗(Reeve)提出了具有強干擾能力的脈沖調(diào)制。上述理論工作的一個主要弱點：是把消息看成是一個確定性的過程，這與許多實際情況不相符合。所依靠的數(shù)學工具主要是經(jīng)典的傅里葉分析方法，這是有局限性的。

1945年萊斯(Rice)對噪聲進行了全面研究總結(jié),抗干擾取代了抗失真。1948年香農(nóng)在貝爾系統(tǒng)技術(shù)雜志上發(fā)表了兩篇有關(guān)“通信的數(shù)學理論”的文章。香農(nóng)第一定理：變長無失真信源編碼定理香農(nóng)第二定理：有噪信道編碼定理195l年美國IRE成立了信息論組，1955年出版了匯刊。此間，范恩斯坦(Foinstein)等科學家論證和推廣了香農(nóng)理論。1959年香農(nóng)發(fā)表了“保真度準則下的離散信源編碼定理(香農(nóng)第三定理)”，系統(tǒng)地提出了信息率失真理論。1961年香農(nóng)論文“雙路通信信道”開拓了多用戶信息論研究。二、信號檢測與估計理論1942年維納(Wiener)建立了最少均方誤差準則的維納濾波理論；1943年諾思(North)提出了最大輸出信噪比準則的匹配濾波器理論。1946年科捷利尼科夫(Kotelnikov)提出了最大后驗概率準則(或稱最小錯誤概率)的理想接收機。1950年伍德沃德(Woodword)將信息量的概念用于雷達信號檢測，提出一系列綜合最優(yōu)雷達系統(tǒng)的新概念。1953年米德爾登(Middleten)等人用最小平均風險準則(貝葉斯準則)來處理最佳接收問題，并使各種準則統(tǒng)一于風險(比錯誤更廣泛的概念)理論。五十年代末卡龐(Capon)提出了采用非參數(shù)統(tǒng)計判斷方法。六十年代初卡爾曼(Kalman)和布西(Bucy)提出了卡爾曼濾波理論。1965年以來信號估計廣泛采用自適應(yīng)濾波器。70年代以后卡拉思(Kailath)等人發(fā)展了新息過程理論。

信號檢測參數(shù)檢測法非參數(shù)檢測法魯棒檢測法自適應(yīng)檢測法信號估計維納濾波器卡爾曼-布什濾波器自適應(yīng)濾波器相關(guān)估計法無偏估計法三、信源編碼理論1832年莫爾斯系統(tǒng)使用莫爾斯電碼。1939年達得利(Dudley)發(fā)明了聲碼器(參數(shù)編碼)。1948年香農(nóng)給出了簡單的編碼方法(香農(nóng)編碼)。1952年費諾(Fano)提出了一種費諾碼。同年霍夫曼(Huffman)構(gòu)造了一種霍夫曼編碼方法，并證明了它是最佳碼。1968年前后，埃利斯(P.Elias)發(fā)展了香農(nóng)―費諾碼，提出了算術(shù)編碼的初步思路。而里斯桑內(nèi)(J.Rissanen)在1976年給出和發(fā)展了算術(shù)編碼，1982年他和蘭登(G.G.Langdon)一起將算術(shù)編碼系統(tǒng)化，并省去了乘法運算，使其更為簡化、易于實現(xiàn)。

四、信道編碼理論與此同時，另外一部分科學家從事尋找最佳編碼（糾錯碼）的研究工作。早在五十年代初，漢明碼出現(xiàn)后，人們把代數(shù)方法引入到糾錯碼的研究，形成了代數(shù)編碼理論。由此找到了大量可糾正多個錯誤的好碼，而且提出了可實現(xiàn)的編、譯碼方法。于六十年代提出了卷積碼和概率譯碼，并逐步形成了一系列概率譯碼理論。尤其，以維特比(Viterbi)譯碼為代表的譯碼方法被美國衛(wèi)星通信系統(tǒng)所采用，使香農(nóng)理論成為真正具有實用意義的科學理論。糾錯碼在工程方面的應(yīng)用將隨著微電子學的進展而得到迅速發(fā)展。近期，人們提出一種糾錯碼——籬碼（Trelliscode），它是將編碼器和調(diào)制器結(jié)合在一起考慮的最優(yōu)碼。尋找最優(yōu)碼的方法仍是有待今后繼續(xù)研究的課題。2信源及其數(shù)學模型正如前面所述，在通信系統(tǒng)中收信者在未收到消息以前，對信源發(fā)出什么消息是不確定的，是隨機的，所以可用隨機變量、隨機矢量或隨機過程來描述信源輸出的消息?；蛘哒f，用一個樣本空間及其概率測度—概率空間來描述信源。1、樣本空間X某事物所有可能出現(xiàn)的不同狀態(tài)(或不同消息)的集合。2、概率測度P對于每個可能選擇的消息指定一個概率。3、消息概率空間[X,P]：消息的樣本空間X和它的概率測度P。離散情況下概率空間為概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系⑴⑵⑶概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系⑷⑸⑹

單符號離散信源的數(shù)學模型

(1)信源的描述方法(2)單符號離散信源(3)單符號離散信源數(shù)學模型

（1）信源的描述方法

信源是信息的來源，是產(chǎn)生消息或消息序列的源泉。在通信系統(tǒng)中收信者在未收到消息以前，對信源發(fā)出什么消息是不確定的。①離散信源：輸出的消息常常是以一個個符號形式出現(xiàn)，這些符號的取值是有限的或可數(shù)的。單符號離散信源：只涉及一個隨機事件，可用隨機變量描述。多符號離散信源：每次輸出是一個符號序列，序列中每一位出現(xiàn)哪個符號都是隨機的，而且一般前后符號之間是有依賴關(guān)系的?？捎秒S機矢量描述。②連續(xù)信源：輸出連續(xù)消息，可用隨機過程描述。（2）單符號離散信源如果信源發(fā)出的消息是離散的、有限或無限可列的符號或數(shù)字，且一個符號代表一條完整的消息，則稱這種信源為單符號離散信源。單符號離散信源的實例擲骰子每次只能是1,2,3,4,5,6中的某一個；天氣預報可能是晴、陰、雨、雪、風、冰雹…中的一種；二進制通信中傳輸?shù)闹皇?、0兩個數(shù)字；投硬幣等等。這種符號或數(shù)字都可以看作某一集合中的事件，每個符號或數(shù)字（事件）都是信源中的元素，它們的出現(xiàn)往往具有一定的概率。因此，信源又可以看作是具有一定概率分布的某一符號集合。若信源的輸出是隨機事件X，其出現(xiàn)概率為P(X)，則它們所構(gòu)成的集合，稱為信源的概率空間或簡稱為信源空間。(3)單符號離散信源數(shù)學模型

單符號離散信源的數(shù)學模型就是離散型的概率空間：X代表隨機變量，指的是信源整體xi代表隨機事件的某一結(jié)果或信源的某個元素p(xi)=P(X=xi)，表示隨機事件X發(fā)生某一結(jié)果xi的概率。n是有限正整數(shù)或可數(shù)無限大信源分類根據(jù)樣本空間X取值分布的不同情況，信源可分為以下類型。離散信源：消息集X為離散集合。即時間和幅度取值都離散的信源。連續(xù)信源：時間離散而幅度取值連續(xù)的信源，如溫度，壓力等；波形信源：時間和幅度取值連續(xù)的信源，如語言、圖像信源等。連續(xù)信源和波形信源輸出的消息都可以經(jīng)過抽樣和量化分別處理成時間和幅度取值都離散的消息，因此，本書中主要討論離散信源的情況。--像數(shù)學中的sin，cos

根據(jù)信源的統(tǒng)計特性，信源又可分為兩種類型無記憶信源：X各時刻的取值相互獨立。有記憶信源：X各時刻的取值互相有關(guān)聯(lián)，如中文句子中前后文字的出現(xiàn)是有依賴性的。英文字，T后面出現(xiàn)H，R的可能性較大，出現(xiàn)J，K，L，M，N的可能性極小，而根本不會出現(xiàn)字母Q，F(xiàn)，X。有記憶信源的數(shù)學模型通常采用聯(lián)合概率空間來描述。2.1離散無記憶信源

1.離散無記憶信源(DiscreteMemorylessSource，簡記為DMS)，其輸出的是單個符號的消息，不同時刻發(fā)出的符號之間彼此統(tǒng)計獨立，而且符號集中的符號數(shù)目是有限的或可數(shù)的。離散無記憶信源的數(shù)學模型為離散型的概率空間，即：

p(ai)：信源輸出符號消息ai的先驗概率;滿足：0

p(ai)1，1

iq

例子1.二進制對稱信源只能輸出符號0或1，輸出0的概率為p，輸出1的概率為1-p，其概率空間可描述為2.隨機擲一個無偏骰子，可能出現(xiàn)的點數(shù)與其概率分布為實際情況下，信源輸出的消息往往不是單個符號，而是由許多不同時刻發(fā)出的符號所組成的符號序列。設(shè)序列由N個符號組成，若這N個符號取自同一符號集{

a1,a2,…,aq}，并且先后發(fā)出的符號彼此間統(tǒng)計獨立，我們將這樣的信源稱作離散無記憶的N維擴展信源。其數(shù)學模型為N維概率空間：

每個符號是對應(yīng)于某一有N個ai組成的序列（各種長為N的符號序列），x

=x1x2…xN

，xi

{a1,a2,…,ak

}，1

i

N，序列集X={a1a1…a1,a1a1…a2,…,akak…ak

}，共有kN種序列，x

X。

序列的概率q(x)=q(x1x2

…xN)=2.離散無記憶的擴展信源例子書上例子P72.2

離散有記憶信源

漢字或英文字母組合成中、英文句子時，往往要受到語法、習慣用語、修辭等的制約，因此中、英文句子中前后出現(xiàn)的漢字、字母往往是有依賴性的。如英文字母T后面最常出現(xiàn)H和R，而根本不會出現(xiàn)Q，F(xiàn)，X。這種依賴性我們稱作有記憶。用聯(lián)合概率空間{X,q(X

)}來描述離散有記憶信源的輸出。信源在i時刻發(fā)出什么符號與i時刻以前信源所發(fā)出的符號有關(guān)，即由條件概率p(xixi-1

xi-2…)確定。多數(shù)有記憶信源的記憶長度是有限的，即某一時刻信源發(fā)出的符號只與前面已發(fā)出的若干個符號有關(guān)。為了描述這種有限的記憶關(guān)系，常引入“狀態(tài)”的概念。

這樣，信源發(fā)出的符號與信源的所處的狀態(tài)有關(guān)。1.3.2馬爾可夫信源馬爾可夫信源一類相對簡單的離散平穩(wěn)信源該信源在某一時刻發(fā)出字母的概率除與該字母有關(guān)外,只與此前發(fā)出的有限個字母有關(guān)m階馬爾可夫信源：信源輸出某一符號的概率僅與以前的m個符號有關(guān)，而與更前面的符號無關(guān)。條件概率馬氏鏈的基本概念一階馬爾可夫信源：若把有限個字母記作一個狀態(tài)S，則信源發(fā)出某一字母的概率除與該字母有關(guān)外，只與該時刻信源所處的狀態(tài)有關(guān)。信源將來的狀態(tài)及其送出的字母將只與信源現(xiàn)在的狀態(tài)有關(guān)，而與信源過去的狀態(tài)無關(guān)。馬氏鏈的基本概念令si

=(xi1,

xi2,

…xim)xi1,,xi2,

…xim

∈(a1,

a2,

…an)狀態(tài)集S={s1,s2,…,sQ}Q=nm信源輸出的隨機符號序列為：x1,x2,…xi-1,xi…信源所處的隨機狀態(tài)序列為：s1,s2,…si-1,si,…例：二元序列為…01011100…考慮m=2，Q=nm=22=4s1=00s2=01s3=10s4=11變換成對應(yīng)的狀態(tài)序列為

…s2s3s2s4s4s3s1…馬爾可夫信源設(shè)信源在時刻m處于si狀態(tài),它在下一時刻(m+1)狀態(tài)轉(zhuǎn)移到sj的轉(zhuǎn)移概率為：

pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}pij(m)：基本轉(zhuǎn)移概率（一步轉(zhuǎn)移概率）若pij(m)與m的取值無關(guān),則稱為齊次馬爾可夫鏈

pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}pij具有下列性質(zhì)：

pij≥0若信源處于某一狀態(tài)si,當它發(fā)出一個符號后,所處狀態(tài)就變了,任何時候信源處于什么狀態(tài)完全由前一時刻的狀態(tài)和發(fā)出符號決定。系統(tǒng)在任一時刻可處于狀態(tài)空間S={s1,s2,…,sQ}中的任意一個狀態(tài),狀態(tài)轉(zhuǎn)移時,轉(zhuǎn)移概率矩陣符號條件概率矩陣例2-1，如圖所示是一個相對碼編碼器,輸入的碼Xr(r=1,2,…)是相互獨立的，取值0或1，且已知P(X=0)=p,P(X=1)=1－p=q，輸出的碼是Yr，顯然TXrYrYr-1+Yr是一個馬氏鏈,Yr確定后,Yr+1概率分布只與Yr有關(guān),與Yr-1

、Yr-2…等無關(guān),且知Yr序列的條件概率sos1pqqpp00=P(Y2=0/Y1=0)=P(X=0)=pp01=P(Y2=1/Y1=0)=P(X=1)=qp10=P(Y2=0/Y1=1)=P(X=1)=qp11=P(Y2=1/Y1=1)=P(X=0)=p

馬爾可夫信源狀態(tài)轉(zhuǎn)移圖齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖(香農(nóng)線圖)表示每個圓圈代表一種狀態(tài)

狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移有向線一側(cè)的符號和數(shù)字分別代表發(fā)出的符號和條件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.7時齊馬爾可夫信源它是滿足方程組的唯一解；Wj

：馬爾可夫鏈的一個平穩(wěn)分布，

Wj[p(sj)]就是系統(tǒng)此時處于狀態(tài)sj的概率。sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例1例2：有一個二元二階馬爾可夫信源,其信源符號集為{0，1}，已知符號條件概率：p(0|00)=1/2p(1|00)=1/2p(0|01)=1/3p(1|01)=2/3p(0|10)=1/4p(1|10)=3/4p(0|11)=1/5p(1|11)=4/5求：⑴信源全部狀態(tài)及狀態(tài)轉(zhuǎn)移概率⑵畫出完整的二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖。⑶求平穩(wěn)分布概率

狀態(tài)轉(zhuǎn)移概率矩陣符號條件概率矩陣(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/5穩(wěn)態(tài)分布概率穩(wěn)態(tài)后的符號概率分布2.2.3波形信源

波形信源輸出的消息在時間和幅度取值上都是連續(xù)的，如語音、圖像信號。對于這種信源輸出的消息，可用隨機過程來描述。常見的波形信源輸出的消息是時間上或頻率上有限的隨機過程，對于這種隨機過程，可通過取樣、量化將其變換成時間、取值都離散的離散信號，這樣波形信源就可轉(zhuǎn)換成離散信源來處理。連續(xù)信源的數(shù)學模型是連續(xù)型的概率空間，即滿足

信源的分類及其數(shù)學模型-小結(jié)T3信道及其數(shù)學模型信道是信息傳輸?shù)耐ǖ溃鐖D3-1，信道可看作一個變換器，它將輸入消息x變換成輸出消息y，以信道轉(zhuǎn)移概率p(yx)來描述信道的統(tǒng)計特性。

信道p(y

x)xy圖3-1信道模型

無記憶信道信道的輸出y只與當前時刻的輸入x有關(guān)。有記憶信道信道的輸出y不僅與當前時刻的輸入有關(guān)，還與以前的輸入有統(tǒng)計關(guān)系

。信道可以按不同的特性進行分類，根據(jù)輸入和輸出信號的特點可分為：波形信道信道的輸入和輸出都是時間上連續(xù)，并且取值也連續(xù)的隨機信號。

半連續(xù)信道輸入序列和輸出序列一個是離散的，而另一個是連續(xù)的。連續(xù)信道信道的輸入和輸出都是時間上離散、取值連續(xù)的隨機序列，又稱為模擬信道離散信道信道的輸入和輸出都是時間上離散、取值離散的隨機序列。離散信道有時也稱為數(shù)字信道。根據(jù)統(tǒng)計特性，即轉(zhuǎn)移概率p(yx)的不同，信道又可分類為：

根據(jù)信道的用戶多少，可以分為（1）兩端（單用戶）信道。它是只有一個輸入端和一個輸出端的單向通信的信道，如圖所示。它是多用戶信道的基礎(chǔ)。（2）多段（多用戶）信道。它是在輸入端或輸出端中至少有一端有兩個以上的用戶，并且還可以雙向通信的信道。實際通信系統(tǒng)，如計算機通信，衛(wèi)星通信，廣播通信，移動通信等，這些系統(tǒng)中的信道都屬于多用戶信道。根據(jù)信道輸入端和輸出端的關(guān)聯(lián)，可以分為（1）無反饋信道。信道輸出端無信號反饋到輸入端，即輸出端信號對輸入端信號無影響、無作用。（2）反饋信道。信道輸出端的信號反饋到輸入端，對輸入端的信號起作用，影響輸入端信號發(fā)生變化。根據(jù)信道的統(tǒng)計特性是否隨時間變化分為：①恒參信道（平穩(wěn)信道）：信道的統(tǒng)計特性不隨時間變化。衛(wèi)星通信信道在某種意義下可以近似為恒參信道。②隨參信道（非平穩(wěn)信道）：信道的統(tǒng)計特性隨時間變化。如短波通信中，其信道可看成隨參信道。按輸入/輸出信號之間的關(guān)系是否確定關(guān)系分為有噪聲信道和無噪聲信道。3.1離散無記憶信道（DMC）

離散無記憶信道的輸入和輸出消息都是離散無記憶的單個符號，輸入符號xi

{a1,a2,…,ak}，1

i

k，輸出符號yj

{b1,b2,…,bD

}，1

j

D，信道的特性可表示為轉(zhuǎn)移概率矩陣：p(yjxi

)表示已知輸入符號為xi，而輸出符號為yj時的信道轉(zhuǎn)移概率，滿足0

p(yjxi

)1，且

信道矩陣的每一行之和等于1將信道特性表示成圖3-2所示的線狀圖形式：

p(y1

x1)x1x2y1y2xkyDp(yD

xk

)圖3-2單符號離散無記憶信道1.二元對稱信道(BinarySymmetricChannel，簡記為BSC)這是一種很重要的信道，它的輸入符號x{0,1}，輸出符號y{0,1}，轉(zhuǎn)移概率p(yx)如圖3-3所示信道特性可表示為信道矩陣，其中p稱作信道錯誤概率。下面列舉幾種常見的離散無記憶信道：圖3-3二進制對稱信道1-p0

p

1011-p

p

圖3-4無干擾信道2100111122.無干擾信道這是一種最理想的信道，也稱作無噪信道，信道的輸入和輸出符號間有確定的一一對應(yīng)關(guān)系，p(yx)=如圖3-4三元無干擾信道中，x,y{0,1,2}，對應(yīng)信道矩陣是單位矩陣

3.二元刪除信道

對于接收符號不能作出肯定或否定判決時，引入刪除符號，表示對該符號存有疑問，作為有誤或等待得到更多信息時再作判決。二元刪除信道如圖3-5所示，輸入符號x{0,1}，輸出符號y{0,e,1}，轉(zhuǎn)移概率矩陣為4.二元Z信道

二元Z信道如圖3-6所示，信道輸入符號x{0,1}，輸出符號y{0,1}轉(zhuǎn)移概率矩陣為

101011-p

p1-p0

p1011-p

p

e圖3-5二元刪除信道

圖3-6二元Z信道

3.2離散無記憶的擴展信道

N維離散擴展信道的輸入和輸出都是長為N的消息