(完整word版)通信的數(shù)學理論_香農(nóng)_中文版1

1、香農(nóng)通信的數(shù)學理論近年來像PCM和PPM這些交換信號噪音比帶寬等的多種調(diào)制方法的發(fā)展已經(jīng)增強了我們對一般通信理論的興趣。這種理論的基礎(chǔ)包在重要的報紙Nyquist1 and Hartley 2中關(guān)于此學科的內(nèi)容。 在當今的報紙中我們將延伸這種理論從而包括許多新的因素，特別是噪聲通道的影響，和存儲可能的基于最初信息統(tǒng)計的結(jié)構(gòu)和基于數(shù)據(jù)的最后目的性性質(zhì)。通信的基本問題是再制造一點或者準確地或者近似地一個從別處挑選的信息。通常信息有意義；那是他們提到的或是依照一些特定物質(zhì)或概念上實體的系統(tǒng)的相互關(guān)聯(lián)。這些與語意有關(guān)的通信方面是不切題的工程問題。重要的方面是真實的信息是從一組可能的信息挑選來的。系統(tǒng)一

2、定要有計劃的操作每個可能的選擇，而不僅僅是哪一個因為在設計的時候是未知者將會被選擇。如果設備的信息數(shù)目是有限的，那么這組數(shù)字或一些具有單調(diào)功能的數(shù)字可以被當做對信息被關(guān)閉后再創(chuàng)造的測度，所有的選擇有相同的可能。像 Hartley所指出的，最自然的選擇 是對數(shù)的功能。雖然當我們考慮統(tǒng)計信息的影響力以及對信息的持續(xù)排列這個定義必須被凝 練地概括，我們將在所有情況下用一個本質(zhì)為對數(shù)的量度標準。對數(shù)的測度更方便，主要有以下多方面的理由：1 .它在實踐上更有用。工程的重要參數(shù)，像時間、帶寬、數(shù)字的分程傳遞等等，趨向 于隨可能數(shù)字的對數(shù)線性改變。舉例來說，增加一個繼電器到小組會加倍數(shù)字的可能情形。它加1到

3、以2為底的對數(shù)。加倍時間大致得到可能信息數(shù)目的平方，或加倍其對數(shù)，等等。2 .它以適當?shù)某叽缃咏覀兊闹庇X感觀。如果我們直覺地用共同的標準線性比較測量實體，它將接近相關(guān)到（1）。有一個想法，舉例來說，二張穿孔卡片與一張相比有兩倍 的信息儲藏能力，并且二個通道與一個相比有兩倍的傳輸數(shù)據(jù)的能力。3 .它在數(shù)學方面更合適。許多極限運算在對數(shù)方式下很簡單，但是在普通數(shù)字下卻需要笨拙的重述。對數(shù)底的選擇對應測量信息單位的選擇。 如果以2為底，產(chǎn)生的單位 可以叫二進位數(shù)字，或比較簡要地叫比特，一個由J.W.Tukey建議的詞。一個擁有兩個 穩(wěn)定位置的設備，像一個繼電器或一個雙穩(wěn)態(tài)多諧振蕩器，可以存儲一比特

4、的信息。N個如此的裝置能存儲 N比特的信息，因為可能情形的總數(shù)是logb a信息來源傳達者接受者目的地干擾源圖1一個常規(guī)信息系統(tǒng)原理圖并且log 2=N 。如果以10為底產(chǎn)生的單位可以叫十進制數(shù)字。因為log2 M =log10 M/log102 =3.32log 10 M 。1 一 ,Nyquist , “某些影響通報速度的因素”貝爾系統(tǒng)科技刊物，1924年4月，第324頁；“電報傳輸理論中某些總聯(lián)機程序和信息控制系統(tǒng)”,A.I.E.E. Trans.v.47,1924年4月，第617頁。Hartley, R. V. L , “信息傳輸”，貝爾系統(tǒng)科技刊物，1928年7月，第535頁2一個十

5、進制數(shù)大約31比特。書桌上的一個阿拉伯數(shù)字計數(shù)器有十個穩(wěn)定的位置并且因 3此擁有存儲十進制數(shù)字的能力。有時在綜合和區(qū)分的解析工作中底數(shù)e很有用處。以此為底的信息結(jié)果將被叫做自然對數(shù)。將底數(shù)由a改為b僅僅需要乘以10gb a。對于通信系統(tǒng)我們想要用一個系統(tǒng)的示意圖圖1闡明。它包括五個重要的部分：1 .一個制造信息或排序信息的信息源將被傳達到終端。信息可能有各種不同類型：(a)電傳打字系統(tǒng)的電報中的字母序列 ；(b)無線電話中的一個單一時間函數(shù)f(t);(c) 一個時間函數(shù)和其它應用在黑白電視機中的變量一在這里信息可能被當做一個二個空間坐標和時間的函數(shù) f(x,y,t);在點(x,y)的光強度，在

6、光的金屬板上獲得的時間t;(d)二或更多的時間函數(shù)，分別為f(t)、g(t),h(t)這是“三維”聲音傳播的情形，或者若系統(tǒng)有意維修個別多元通道；(e)一些變量的一些函數(shù)一在彩色電視機中有三個函數(shù)f(x,y,t),g(x,y,t),h(x,y,t),定義在一個三維空間的閉聯(lián)集中一我們也可能想像這三個函數(shù)作為一個定義在區(qū)域矢量場的向量分量一同樣地，個別黑白電視機消息來源是許多三個變量的函數(shù)；不同的混合物也會發(fā)生，例如在電視機中有聯(lián)合的音頻信道。2 .用一些方法操作信息以產(chǎn)生在信道上傳輸?shù)暮线m信號的傳達者。在電話制造中這種操作包括的僅僅是替換躁聲壓力為電流。在電信技術(shù)中我們有產(chǎn)生一系列點、莫爾斯電

7、碼、空間等相關(guān)信息信道的編碼、譯碼的操作。在一個多元的PCM系統(tǒng)不同的語音函數(shù)必須被取樣壓縮，量子化和編碼，而且最后完全交叉存取地構(gòu)造信號。聲音傳播機系統(tǒng)、電視和頻率調(diào)制器是其他的聯(lián)合體操作應用于信息以獲取信號的例子。3 .信道只是用來從傳達者到接收者傳送信號的媒介。它可能是一雙電線、一個同橋電纜、一 條無線電電波，一個光束，等等。4 .接收者通常完成由傳達者做的反運算，重建來自信號的信息。5 .目的地是信息對其有意的人 (或者事物)。我們希望考慮特定的一般問題用于信息系統(tǒng)。這 首先需要描述不同數(shù)學實體的相關(guān)原理，將他們的物理副本合理的理想化。我們大致把通信系統(tǒng)分為三大類：離散的，連續(xù)的和混和

8、的。離散系統(tǒng)對于我們就意味著信息和信號是一系 列的離散符號。一個典型的情形是在電信技術(shù)中消息是一系列的字母和信號點、莫爾斯電碼及空間。連續(xù)型的系統(tǒng)就是一個信息和信號都被看作是連續(xù)函數(shù)的系統(tǒng)，例如無線電通信或電視機?；旌舷到y(tǒng)中既有離散的又有連續(xù)的變量，例如PCM語言傳輸。我們首先考慮離散的情形。這種情形不僅應用于通信理論，而且應用于計算機理論，電話局和其他領(lǐng)域的設計。 另外離散的情形構(gòu)成在下半頁要處理的連續(xù)和混合情形的基礎(chǔ)。第一部分：離散的無噪聲系統(tǒng)1 .離散的無噪聲信道電傳打字機和電信技術(shù)是離散信道上信息傳輸?shù)膬蓚€簡單例子。一般來講，一個離散信道就意味著一個系統(tǒng)怎么從可以從一個點傳到另一個點被

9、傳輸?shù)挠邢藜显胤朣),.,Sn選擇次序。每一個符號Si被假定有確定的連續(xù)時間ti秒(對于不同的Si沒必要相同，例如電信技術(shù)中的點和莫爾斯電碼)。這不需要有可能傳輸?shù)较到y(tǒng)的Si的所有可能排序，確定次序僅僅是可能被允許。這將在信道產(chǎn)生可能的信號。這樣在電信技術(shù)中可以推想符號有：(1) 一個點，包括一個單位時間的關(guān)閉和一個單位時間的線性開啟；(2) 一個莫爾斯電碼，包括三個單位時間的關(guān)閉和一個單位時間的開啟；(3) 一個包括三個單位時間線性開啟的字母空間；(4) 一個包括六個單位時間線性開啟的詞空間。我們可能放置約束在允許的無間隔的次序(因為如果兩個字母的間隔是接近的，它同一個字空間是一樣的)

10、。我們現(xiàn)在要考慮 的問題是如何測量這樣一個信道傳輸信息的能力。在電傳打字的情況下所有符號有同樣的持續(xù)時間，并且32個符號任何排序答案是簡單的。每個符號擁有5比特的信息量。如果系統(tǒng)每秒傳輸 n個字符，那么自然來說信道有一個 每秒5n比特的傳輸能力。這并不意味電傳打字信道總是這個傳輸速度，這是可能的最大值 并且實際比率能否達到最大值取決于進入信道不久將會出現(xiàn)的信息源。在不同長度的符號和約束的允許序列的更普通情形中，我們作以下定義：定義：一個離散信道容量 C由此公式給出：C = Lim log N(T)tt：T其中N(T)是持續(xù)時間為T時允許信號數(shù)目。很容易看出在電傳打字的情形下降低了當前的結(jié)果?？?/p>

11、以看出問題中的極限在多數(shù)情況的影響下存在一個最終的數(shù)目。假使所有符號的次序 S,，Sn都可能發(fā)生，并且這些符號的持續(xù)時間為ti,tn。信道容量是多少？如果N(T)代表為期t的次序數(shù)目，我們就有N(t)=N(t- t 1)+N(t-t 2)+.+N(t-t n).總數(shù)目等于以Si,，Sn為結(jié)尾的序列數(shù)目的總和并且是N(t- ti),N(t-t 2),N(t-t n)。根據(jù)一個著名的有限差結(jié)果，N(t)于是漸進大數(shù)t到X0t,其中Xo是特征方程式的最大解：X-t1 +X* +.X 上=1 因止匕 C=logX 0.在允許序列受限制的情況下我們也有一個此種類型的不同方程式并且從特征方程式中得到Co在

12、以上提到的電信技術(shù)我們知道依照最后或幾乎最后出現(xiàn)的序列計算符號序列。N(t)=N(t- 2)+N(t-4)+N(t-5)+N(t- 7)+N(t-8 )+N(t-10)因此C等于log與。其中%是方程1 =卜2 +卜4+卜5+卜7+卜8+川°的根。我們可以解得C=0.539。一個置于允許序列約束的普通類型如下：我們想象一個可能的數(shù)字序列 ai,a2,.,am。對于每一種情形僅僅設置S,S2,., Sn中的某些符號可以被傳輸(不同的子集有不同的情形)。當其中之一被傳輸，就產(chǎn)生一個取決于老狀態(tài)和當前傳輸信號的新狀態(tài)。發(fā)電報就是這其中的一個簡單例子。存在兩個取決于是否是一個空間最后傳輸信號

13、的狀態(tài)。如果這樣的話，那么僅僅一個點或一個莫爾斯電碼可以被發(fā)送并且狀態(tài)經(jīng)常改變。如果不是的話，一些信號可以傳輸并且若空間被發(fā)送狀態(tài)將改變，否則它保持不變。這種情形可以在線狀圖圖2中闡明。莫爾斯電碼母空”/莫爾斯電碼司空間圖2 電報符號約束的圖表狀態(tài)和線相應的那些連接點指示著狀態(tài)中的可能符號和結(jié)果狀態(tài)。在附錄1中可以看出如果允許序列的條件可以被描述在形態(tài)C中，結(jié)果將存在并且計算出它與以下結(jié)果一致：定理1：以bijs)為從狀態(tài)i到狀態(tài)j的允許符號sth的周期。那么信道容量 C等于logW ,其中W是行列式方程式白最大實根：4 w對) _、可| =0s其中若i=j則aj =1,否則樂=0 O ,一

14、，-1(W2 +W”)例如，在電報情形(圖 2)中行列式是：=0。(W +W) (W +W-1)在擴充式中這將導出以上這種情形所給的方程式。2.信息的離散信源我們已經(jīng)看到在普通情況下可能信號的數(shù)目的對數(shù)在離散信道中隨時間線性增長。信道容量可以由給出的增長率說明，每秒的比特數(shù)目需要詳細說明所用的特殊符號。我們現(xiàn)在考慮信息源。如何將信息源用數(shù)學方式描述，在所給信源每秒產(chǎn)生多少信息位 呢？這個問題的關(guān)鍵是關(guān)于降低信源必需的信道容量的統(tǒng)計知識的影響，通過利用適當?shù)男畔⒕幋a。在電信技術(shù)中，例如，包括字母序列的被傳輸信息。然而，這些序列并不是完全隨 意的。一般而言，他們組成句子并且有所謂英文的統(tǒng)計結(jié)構(gòu)。字

15、母 E比字母F出現(xiàn)的頻繁， 序列TH比序列XP出現(xiàn)的頻繁，等等。這個結(jié)構(gòu)的存在通過適當?shù)鼐幋a信息序列到信號序 列能節(jié)省時間(或信道容量)。這已經(jīng)被用來通過利用最短的符號信道、點、最常見的英文 字母E限制寬度，然而少見的字母 Q, X, Z用長點的點和莫爾斯電碼表示。這個方法還被廣泛應用于商業(yè)編碼，其中常見字和短語是由極大地縮短平均時間的4或5位信碼群表示?，F(xiàn)在運用的標準問候和周年紀念電報擴充這一點到編碼一到兩個句子為 相關(guān)的短的數(shù)字序列。我們可以考慮一個離散信源作為由符號產(chǎn)生的信息、符號。它通過某些可能的依靠選 擇連續(xù)的符號，一般的，在前述的選擇，像問題中的特殊符號。一個物理系統(tǒng)，或是一個產(chǎn)

16、生由可能集合支配的符號序列的系統(tǒng)的數(shù)學模型，叫做隨機過程。3我們可以考慮一個離散信源，因此，將通過一個隨機過程描述。相反地，有一些隨機過程，它們產(chǎn)生離散的選自被 認為是離散信源的有限集的符號序列。這將包括如下情形：1 .自然書寫語言如英語、德語、漢語。2 .由量子化過程離散呈遞的連續(xù)信息源。例如由 PCM發(fā)射機發(fā)送的量子化演說，或 者一個量化電視信號。3 .在數(shù)學情形中我們僅僅定義抽象的產(chǎn)生符號序列的隨機過程。如下是最終資源類型的例子。(A)假設我們有5個都以0.2的可能性被選擇的字母 A、RC、D、E連續(xù)選擇是不受約束的。這將產(chǎn)生一個序列，如下就是一個典型例子。它利用隨機數(shù)字表格構(gòu)造的。4B

17、 D C B C E C C C A D C B D D A A E C E E AA B B D A E E C A C E E B A E E C B C E A D3See,例如，S. Chandrasekhar,物理學和天文學中隨機問題 ，現(xiàn)代物理學的回顧，v.15,No.1,1943年一月， 第一頁.4 .Kendall and Smith，隨機取樣數(shù)子的表格，劍橋,1939.(B)用五個發(fā)生概率分別為0.4,0.1,0.2,020.1的同樣字母，連續(xù)選擇是不受約束的。一個來自信源的典型如下：A A A C D C B D C E A A D A D A C E D AE A D C

18、 A B E D A D D C E C A A A A A D 。(C)如果連續(xù)的符號沒有被獨立地選擇，但是他們的概率取決于在前的字母，一個更復雜的 結(jié)構(gòu)將會獲得。在簡單的情況下，這種類型的選擇取決于在前的字母并且不是它們之前的。統(tǒng)計結(jié)構(gòu)然后就通過一個躍進概率集合Pi (j)描述，字母j的發(fā)生概率在i之后。復數(shù)i和jp(i, j),也就是兩涉及所有的可能符號。第二個相等方法的指定結(jié)構(gòu)是給出兩個字母的概率Pi(j)和連字概率p(i,j)個字母i,j的相關(guān)概率。字母頻率 p(i),(字母i的概率)，躍進概率 有如下公式的關(guān)系：P(i) = P(i, j) = P( j,i)=" P(

19、j)P j(i)P(i, j)=P( i)Pi(j)Pi(j)八P(i)- p(i, j) =1.i,j舉一個具體的例子，假設有三個如下概率表所示的字母A,B,C:Pi(j)P(i)P(i, j)ABC512210271627227827 12715827413515135一個消息源的典型信息如下：A B B A B A B A B A B A B A B B B A B B B B B A B A B A B A B A B B B A C A C A BB A B B B B A B B A B A C B B B A B A.其次，復雜性的增加將包括最多三組字母的頻率。字母的選擇將依賴在

20、前的兩個字母而不是之前的信息點。一個三組字母頻率p(i,j,k)的集合或者等同的蛻變概率pj (k)的集合是必需n元情形中用一個 n的。這種方法持續(xù)進行將獲得更多持續(xù)的復雜的隨機過程。在普通的 元概率P(i1,i2,in)或者轉(zhuǎn)變概率Pi1,i2,.,in-1(in)的集合來指定統(tǒng)計結(jié)構(gòu)是必需的。(D)隨機過程也可以由產(chǎn)生一段包括序列“字”的正文來定義。假設有語言中的五個字母A, B, C, D, E和16個“字”，且它們的聯(lián)合概率如下:10 A16 BEBE11CABED04DEB04ADEB05ADEE01BADD04BED02BEED05CA05CEED08DAB04DAD15DEED0

21、1EAB05EE假設連續(xù)的“字”被獨立地選擇并且被空間隔離。一個典型可能信息為:DAB EE A BEBE DEED DEB ADEE ADEE EE DEB BEBE BEBE BEBE ADEE BED DEED DEED CEED ADEE A DEED DEED BEBE CABED BEBE BED DAB DEED ADEB 。 如果所有的字長度有限，這個過程就相當于前述類型的其中之一，但是如果按照字結(jié)構(gòu)和概率描述可以更簡單。我們也在此歸納并且介紹字之間的蛻變概率，等等。人工語言在構(gòu)造簡單的問題和說明不同可能性的例子是有用的。我們也可以通過一系列簡單的人造語言的方法接近自然語言。零

22、號近似值可以通過等可能并且獨立地選擇字母來獲得。一號近似值可以通過獨立地選擇連續(xù)的字母獲得，但是每個字母像自然語言5那樣擁有同等的發(fā)生概率。這樣在一號近似值中對于英語來說，E以0.12（它在標準英語中出現(xiàn)的頻率）的概率被選擇并且 W的發(fā)生概率為 0.02,但是鄰接字母之間沒有影響并且沒有形成像 TH, ED這樣的首選連字，等等。在二號近似值中介紹了連字結(jié)構(gòu)。一個字母被選擇后，下 一個字母與頻率被一致地選擇，其中不同的字母跟隨第一個字母。這需要一個連字頻率Pi（j）的表格。在三號近似值中介紹了三組字母結(jié)構(gòu)。每個字母被等可能選擇并且取決于前兩個字母。3.英文近似值的連續(xù)性給一個這個系列過程如何接近

23、一門語言的形象想法，英文近似值的典型序列已經(jīng)被構(gòu)造并且在下面給出。在所有情形中我們假定一個27字符的“字母表” ，26個字母和一個空格。1 .零號近似值（符號獨立且等可能出現(xiàn)）XFOML RXKHRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD QPAAMKBZAACIBZL- HJQD.2 . 一號近似值（符號獨立但是以英語原文的頻率出現(xiàn)）OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL.3 .二號近似值（英語中的連字結(jié)構(gòu)）ON IE ANTSOUTINYS ARE T INC

24、TORE ST BE S DEAMY ACHIN D ILONASIVE TUCOOWEAT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.4 .三號近似值（英語中的三組字母結(jié)構(gòu)）IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.5 .一號字近似值。勝于連續(xù)的四個字母，.，n元結(jié)構(gòu)更簡單并且更好地接受點到字單元，在此字被獨立地選擇，不過是以它們適當?shù)念l率被選擇。REPRESENTING

25、AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURALHERE HE THE A IN CAME THE TOOF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.6 .二號字近似值。字蛻變概率是恰當?shù)模遣话ǜ畹慕Y(jié)構(gòu)。THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTEROF THIS POINT IS THEREFORE ANOTHER METHOD FOR TH

26、E LETTERS THATTHE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.普通英語原文的類同之處在以上每步顯著增加。注意這些樣品有適度優(yōu)良的結(jié)構(gòu)， 計算它們的造句，表現(xiàn)出兩倍的范圍。這樣在 （3）中對于兩字母次序統(tǒng)計過程確保了合理的原文 ，但是5 、 一 .、 一 .一 、一 ,一 、. . 一一 、,一字母，連字和二組字母頻率在 1939年由Fletcher Pratt, Blue Ribbon Books 所著的緊急秘密。字頻率在由G. Dewey所著、哈佛大學出版社印刷的英語語言的相關(guān)頻率中被列成表格。樣品中四字母次序通常

27、適用于好句子。在(6)中四個或更多的字可以很容易地放在句子中而沒有不平常的、做作的句子。十個詞的詳細次序 “"attack on an English writer that the character of this (抨擊這種特征的英國作家)”根本不合理。由此看來一個十分復雜的隨機過程將會 給離散信源一個滿意的表示法。頭兩個例子是應用隨意數(shù)字的一本書構(gòu)造的，其中隨意數(shù)字關(guān)聯(lián)一個字母頻率表格(對于例2)。這種方法可能已經(jīng)延續(xù)到(3), (4)和(5),雖然連字、三組字母和字母頻率表格是有用的，但是一個更簡單的等價方法正被應用。比如構(gòu)造(3)，一個人隨機地才T開一本書，并且在該頁隨機

28、地選擇一個字母。 將此字母記錄。然后打開該書的另外一頁并且讀到這個字母出現(xiàn)時， 隨后的字母然后被記錄。翻到另外一頁找到第二個字母并隨后記錄，等等。一個簡單的過程被用在(4),(5)(6)中。如果深一層近似值被構(gòu)造，那將會是有趣的。但是下一階段相關(guān)的詳細 分析變得龐大。4 .一個馬爾可夫過程的圖形表示法以上描述的這種類型的隨機過程在數(shù)學中叫做離散的馬爾可夫過程，并且在文獻6中廣闊地研究。大體情況可以描述為如下：存在一個有限個數(shù)的系統(tǒng)的可能狀態(tài)；S1,S2,.,Sn。另外有一套蛻變概率，如果此刻系統(tǒng)狀態(tài)是 Si,將達到狀態(tài)Sj的概率是Pi(j)。要將馬爾可夫過程轉(zhuǎn)變?yōu)樾畔⒃次覀儍H僅需要假定字母是由

29、每次從一個狀態(tài)轉(zhuǎn)變到另一個狀態(tài)時產(chǎn)生 的。狀態(tài)符合來自前述字母的“剩余物的影響”。該情形可以被描述為圖表，在圖3, 4和5中顯示。圖3一個符合例B中信源的圖表此狀態(tài)是圖中的連接點， 并且概率和字母產(chǎn)生的轉(zhuǎn)變在旁邊的相應直線給出。 圖3對應 第2部分的例Bo而圖4符合例C。在圖3中，因為連續(xù)字母不受約束，只有一個狀態(tài)。圖4一一個符合例C中消息源的圖表在圖4中有字母數(shù)目相等數(shù)目的狀態(tài)。如果構(gòu)造一個三組字母的例子，將出現(xiàn)至多n2個狀態(tài)，符合前述被選擇的可能出現(xiàn)的字母對。圖5是一個說明在例 D中詞結(jié)構(gòu)情形的曲6 了解詳細的處理見 M.Frechet,數(shù)據(jù)加密，巴黎，高塞爾 -維拉斯，1938年8月線圖

30、。這里S代表“間隔”符號。5 .遍歷信源和混合信源正如我們以上已經(jīng)說明的，按我們意原的離散信源可以被看作是由馬爾可夫過程描述。在可能的離散馬爾可夫過程中有一個在通信理論中有意義的特殊性質(zhì)的組。特殊類包括“遍歷”過程，我們把相應的信源叫做遍歷信源。盡管一個遍歷過程的嚴格定義有些棘手，其常規(guī)思想是簡單的。在一個遍歷過程中由此過程產(chǎn)生的序列的統(tǒng)計特性是相同的。這樣的字母頻率、連字頻率等等從特殊序列在獲得，將隨著序列長度的增加，接近不受特殊序列約束的確定極限。事實上這對每個序列并不全對，但是錯誤的概率幾乎為零。大致上遍歷性意味著統(tǒng)計一致性。以上所給的所有人工語言的例子是遍歷的。這種特性涉及到相應圖表的

31、結(jié)構(gòu)。如果圖表有如下兩個性質(zhì)7 ,相應過程將被遍歷：1 .這個圖表不包括兩個獨立的部分A和B,這樣就不可能順著圖中曲線的箭頭方向從A部分的連接點到B部分的連接點，也不可能從 B部分的連接點到 A部分的連接點。2 .圖表中的封閉譜線系伴隨線上的所有箭頭指向同樣的方位叫做一個“回路”?；芈返摹伴L 度”是其中直線數(shù)目的個數(shù)。這樣在圖5中系列BEBES是長度為5的回路。第二個需要的特性是圖表中所有回路長度的最大公約數(shù)是一。圖5一個符合例D中消息源的圖表如果滿足第一個條件，但是由于最大公約數(shù)等于d>1而不滿足第二個條件，序列將有一個確定的周期結(jié)構(gòu)類型。不同的序列分成d種類型，它們統(tǒng)計上相同，除了起

32、源的變化（也 就是，序列中的字母被叫做字母1）。通過從0到d-1的移位一些序列可以統(tǒng)計上等于其它的構(gòu)造。d=2時的一個簡單例子如下：有三個可能的字母a,b,c。a后出現(xiàn)b或c的可能性分1一2別為1和2。a后面跟隨著b或c。這樣的一個典型序列是33a b a c a c a c a b a c a b a b a c a c °這種情形的類型對我們的工作不太重要。這些根據(jù)在Fr'echet中給出的圖表條件被重述如果不滿足第一種條件，圖表可能被分成一系列滿足第一種條件的子圖。我們假定每個子圖也滿足第二種條件。 我們有這種由許多純粹成分組成的叫做“混合”信源的情形。其成分符合各種各

33、樣的子圖。如果 Ll,L2,L3是信源成分，我們可以寫出L = p1L1 + p2L2 + p3L3 + 其中Pi是信源成分Li的概率。自然的描繪情形如下：有幾個不同的信源Li, L2,L3每個都有同類的統(tǒng)計結(jié)構(gòu)(也就是,它們是遍歷的)。我們不知道預先將被用到的，但是一旦序列以所給的純信源成分Li開始，它依照那種成分的統(tǒng)計結(jié)構(gòu)不確定地延續(xù)。作為一個例子我們可以獲得兩個以上定義的過程，并且假定p1 = 0.2, p2 = 0.8。一個來自混合信源的序列 L =0.2Li +0.8L2將通過首先以0.2和0.8的概率選擇L1和L2此選擇 之后產(chǎn)生來自任意一個被選擇的序列。除了當反面是一定的， 我們

34、設想信源將被遍歷。 假設能夠讓我們順著一個伴隨全體可能 序列平均數(shù)(差異的概率為零)的序列確定平均數(shù)。例如在一個特殊無限字母序列中A的相關(guān)概率將可能等于序列全體中它的相關(guān)頻率。如果P是狀態(tài)i的發(fā)生概率并且 pi (j)是到狀態(tài)j的蛻變概率，然后過程將會固定，顯然P必須滿足均衡條件：Pj =£ PPi(j)。在遍歷情形中可以看出伴隨著一些起動條件狀態(tài)j在N個符號后的概率是 R(N),當Nt空時逼近平衡價值。6.選擇、不確定性和嫡我們已經(jīng)將離散信源描繪為一個馬爾可夫過程。我們能否定義一個參量，它在某種意義上測量這樣一個過程或字母產(chǎn)生多少信息，以什么樣的比率產(chǎn)生信息。假如我們有一組發(fā)生概率

35、為pi, P2,，Pn的可能事件。這些概率是知道的，但是那是我們所有知道的關(guān)于將發(fā)生的事件。我們能否找到一個相關(guān)事件有多少“選擇”或結(jié)果有多少不確定性的量度標準呢？如果有這樣一個量度標準，比方說 H ( Pi, P2,，Pn),如下所需的性質(zhì)是合理的：1 .在概率Pi下H是連續(xù)的。12 .如果所有的概率 P1等于一，那么H應該是一個關(guān)于n的單倜遞增函數(shù)。當存在更多可能 n的事件時，等可能事件有更多選擇或不確定性。3 .如果一個選擇被分為兩個連續(xù)的選擇，最初的H應該是H的個體價值的加權(quán)和。 這句話的1 11思義會在圖6中舉例說明，在左圖中我們有二個概率P1 = , P2 =, P3 =。在右圖我

36、們2 361/21/21/31/61/2, 2/3 -1/21/31/3 1/6圖6三個可能選擇事件的分解,1,一一 * 八,2 1, ，一 先以-的概率選擇兩個可能事件，如果第二步以-,-的概率做另一步選擇。最后的結(jié)果有23 3同以前同樣的概率。我們在這種特殊情況下得出1111112 1H （一，一，一）= H （ 一，一）十 H （一，一）。2 3 62 223 2一，1 1系數(shù)-是因為第二個選擇以一半的時間發(fā)生。在附錄2,有如下確定結(jié)果:2n定理2：滿足以上三個假設的 H有如此形式：H = -KZ pi log pi i/其中K是一個確定的常數(shù)。這個理論，和對其進行證明所需的假設，對于當

37、前理論并不需要。這首先給出一些我 們稍后定義的有確定理由的參與。然而這些定義的真正理由隱藏在暗示中。形態(tài)H = -£ pi log pi的數(shù)量（恒量 k僅僅等于度量單位的選擇）作為信息、選擇和不確定性的測度在情報理論中起到了一個中心的作用。形態(tài)H被認作是嫡，作為定義在一如H是Boltzmann的著名的的嫡。如果x是一個機遇數(shù),定的用公式表示的統(tǒng)計力學 8,其中pi是它的拓撲空間中系統(tǒng)處于單元i的概率。然后，例H定理。我們把H = £ pi log pi叫做一系列概率p1, p2,，pnH（x）是它的嫡，這樣的x不是一個函數(shù)的自變量而是一個數(shù)字標志，區(qū)別于 H（y）來說是概率

38、y的嫡。嫡的兩種情形的概率分別為p和q =1 - p ,即H =-（plog p+qlogq）作為p的一個函數(shù)在圖7中繪出。H值有許多有趣的性質(zhì)，更深層地證實它是一個衡量選擇和信息的合理量度標準。1.如果除了一個pi,所有的概率都為 0,那么H=0,這個pi具有聯(lián)合價值。這樣僅僅是當我們確定H為0結(jié)果，否則H是正的。1 12 .對于一個給出的n,H在所有pi相等,也就是（一，一）時取得最大值logn。這也是一個直 nn觀的最不確定的情形。3 .假設有兩個事件x和y,問題中前者有m種可能，后這有n種可能。若事件一發(fā)生的概率是i ,事件二發(fā)生的概率是 j ,其聯(lián)合事件的概率是p（i, j）,那么聯(lián)

39、合事件的嫡是8審視，實例R. C. Tolman ,統(tǒng)計力學原理牛津大學出版部，19380.10圖7一兩種概率分別為p和q =1- p的情形的嫡H(x,y) = p(i, j)log p(i, j)i.jH(x)二一"p(i,j)log% p(i,j)i.jH(y) =，p(i,j)log% p(i,j)i. j很容易知道H ( x, y)三 H ( X )H(Y)僅僅當事件獨立時等號成立(也就是p(i, j) = p(i)p(j)。聯(lián)合事件的不確定性小于等于個體不確定性的總和。4 .對均等概率 R, p2,. pn的一些改變會使 H增大。這樣如果pi < p2并且我們等量地增

40、加pi和p2 ,從而使 pi和p2更接近，那么 H將會增大。一般地，如果我們執(zhí)行形態(tài)r =£ aij pj中均衡pi的操作，其中工 間=工jaj =1，并且所有的aj之0,那么H將 j會增大。(除了轉(zhuǎn)變總數(shù)不超過pj的排列伴隨著H保持不變的特殊情形)。5 .假設有兩個像3中的可能事件x和y,而且它們沒必要獨立。對任何事件x的值i ,可以假定有一個條件概率pi(j),其中事件y的值為j 。這由等式pi(j)= p(i,j)給出。1p(i,j)我們定義y的條件嫡Hx(y)作為對于每一個 x值，y的嫡的平均數(shù)，通過獲得特殊事件x 的概率權(quán)衡。即 Hx(y)=£ p(i, j)lo

41、gi(j)。i.j這個量測試當我們知道事件x時y的平均值的不確定性。取代pi(j)的值我們得到Hx(y)=，p(i, j)log p(i, j) % p(i,j)log" p(i,j) i.ji.jj= H(x, y卜 H(x)或 H (x, y” H( x) xH (oy)聯(lián)合事件x, y的不確定性(或嫡)等于事件x的不確定性加上當知道事件x時事件y的不確定性。6 .從 3 至U 5 我們得出 H(x)+H(y)至 H(x,y)= H(x)+H x(y)因此 H(y) >Hx(y) o事件y的不確定性不會由于知道事件x而增加。除非事件x和y是獨立事件這種不確定性不變的情形，它

42、將會減少。7、信源嫡考慮一個有限離散信源的所有情況，對于每一個可能的狀態(tài)i ,會有一系列可能發(fā)生 j的概率為pi(j)。由此得到對于每一個可能的狀態(tài) i下的嫡Hi ,對所有發(fā)生的狀態(tài)的嫡 Hi進 行加權(quán)平均得到該信源的信源嫡為：H八PH一 Pi pi(j)10gpi(j)i.j這是符號集里每個符號所攜帶的信息量，如果馬爾科夫過程在單位時間內(nèi)發(fā)生，則它為每秒的平均信息量., - -一 ，一 . H =£ 1Hi ( 左為狀態(tài)i出現(xiàn)的平均概率)顯然有：H ' = mH (m為平均每秒鐘產(chǎn)生的符號數(shù))H(H )表示信源平均每個符號(每秒)產(chǎn)生的信息量。如果選取以2為基數(shù)，則單位為比

43、特每符號(每秒)。如果所有的符號相互獨立，則H可簡單的表示為-Z pi 10gpi(pi為i發(fā)生的概率)。理所當然，在這種情況下，我們考慮一個由N個符號組成的長序列信息，它由出現(xiàn)概率相對高的字符組成，其第一個字符出現(xiàn)的次數(shù)為p1N ,第二個字符出現(xiàn)的次數(shù)為p2N這種信息出現(xiàn)的概率為:PiNp r 6p2NpnNp2 pnlog p : N" Pi log Pilog p : -NHu log1/p HN即H大約等于這一序列信息的概率的倒數(shù)的對數(shù)除以序列的符號個數(shù)，且對任意的信源都有這一結(jié)果。更精確的表達如下(見附錄3):定理3:對任意給點的e>0和6>0,存在N0,使得當

44、這一序列信息的長度 N > N0 時有如下兩點成立：1、其發(fā)生的概率小于e；2、所有的參數(shù)滿足不等式叱-H <6N也就是說當N足夠大時，可以確定10g P 可以無限的接近 H。N大量序列的不同概率會無限的接近某個結(jié)果，再考慮序列的長度N ,對它們按概率的遞減順序進行排列。我們定義 n(q)為的那些序列中最有可能發(fā)生的概率且用來計算。定理4:當q不等于0或i時，有Lim 10g n(q) = HN N當我們只考慮最有可能發(fā)生序列的總概率q時，我們可以將n(q)解釋為指定某序列時所需要的比特數(shù)，因此10g n(q)即為平均每個符號所需要的比特數(shù)，這定理表明對于較大N的數(shù)N ,發(fā)生概率q

45、和嫡H相互獨立。所有可能序列數(shù)的對數(shù)的增長率由N確定，與發(fā)生的可能性無關(guān)。結(jié)果的證明過程在附錄 3中。對于長序列中，僅有2HN個是最常用的，每一個被使用的概率為2*N。下面的兩個定理表明 H和H 可以通過信息序列的統(tǒng)計數(shù)據(jù)直接算出來，不涉及狀態(tài)轉(zhuǎn)移概率。定理5：設：p(Bi)為消息中符號序列 Bi的發(fā)生概率，1Gn = -Z p(Bi)log p(Bi),(求和中要遍及所有含 N個符號的序列Bi) N i則：Gn關(guān)于n單調(diào)遞減，且(imGN=H。定理 6：設：p(Bi,Sj)為 Bi,Bj 同時發(fā)生的概率,PBi(Sj) = P(Bi,Sj)/ p(Bi)為在 Bi條件下Sj發(fā)生的概率。設(求

46、和中要遍及所有含 N -1個符號白序列Bi和Sj )Fnp(Bi,Sj)logpBi(Sj)i.j= NGn -(N -1)Gn,1 NFn，N n 4-Gn,則：Fn關(guān)于N單調(diào)遞減，F(xiàn)nGnFnUm Fn =H上述結(jié)果的證明過程在附錄3中，這表明一系列近似計算 H的方法可以通過僅考慮序列中的第1、2、N個符號的統(tǒng)計數(shù)值表得到，F(xiàn)n是一個比較精確的近似值。實際上，F(xiàn)n為所有信源類型的 N個次序的近似值，也就是說下一個字符的產(chǎn)生只與前面的N - 1個符號相關(guān)，與再前面的符號無關(guān)，則Fn = H。Fn即為下一個符號產(chǎn)生的條件嫡，當前面 的N -1個符號已確定時， Gn則為N個符號中平均每個符號的嫡

47、。當重復出現(xiàn)相同的字符時，信源嫡的比率得到最大值，叫做相對嫡。這就是對字母進行 編碼時的最大壓縮。不考慮超過8個字母長度的統(tǒng)計數(shù)值表，普通英語的冗余度大約為 50% 這也就是當我們寫英語時，我們所寫的一半被語言結(jié)構(gòu)所決定，另一半可以自由選擇。50%的數(shù)字是通過相鄰的結(jié)果再利用一些獨立的方法得到。一是通過計算英文的近似嫡；第二種方法是從一個簡單的英文文章中刪掉一些確定的字母片，然后嘗試恢復它們，如果刪掉的 50%TB能被恢復出來，則冗余度就會大于50%第三種方法是依靠密碼系統(tǒng)的已知結(jié)果。英語散文的兩種極端冗余度代表為基礎(chǔ)英語和詹姆斯喬伊斯的書“芬尼根的蘇醒”。基礎(chǔ)英語詞匯限制在 850個單詞，且

48、冗余度較高。當一段落翻譯成基礎(chǔ)英語時會出現(xiàn)反射性 的擴充。喬伊斯在另一方面擴充詞匯，并且聲明實現(xiàn)壓縮的內(nèi)容。語言的冗余度與縱橫字謎的存在有關(guān)，若冗余度為0,字母的任何次序在語言中都時合理的正文，并且任意的二維字符排列形成一個縱橫字謎。如果冗余度太高，這語言就可能會為比較多的縱橫字謎強派大量的約束，通過更多的明細分析得出：如果我們被語言強行約束會更加混亂、更無規(guī)則。當冗余度為50%寸，大的縱橫字謎游戲僅僅成為可能，如果冗余度為33%三位的字謎游戲就可成為可能。8.表小編碼和解碼的運算我們?nèi)匀恍枰镁幋a和解碼信息給傳輸者和接受者表示數(shù)學操作。它們中的任何一個都將被稱作傳感器。一連串的輸入標號被輸入

49、進傳感器并且一連串的輸出標號被傳感器輸出。這個傳感器可能有一個內(nèi)存輸出，不但依靠當前的輸入標號，而且依靠過去的標號。 我們假設內(nèi)存有限，例如：存在一個有限的m代表傳感器，然后輸出一個函數(shù)表示當前的狀態(tài)和當前的標號。下一個狀態(tài)將有第二個函數(shù)和兩個變量。因此，這個傳感器可以用如下的兩個函數(shù)描述：yn f （xn , yn ）an 1 = g（Xn, yn）這里：Xn代表nth的輸入標號，an代表nth的提出的輸入標號的傳感器狀態(tài)，yn代表如果狀態(tài)是an的已知Xn的輸出標號（或者一連串的輸出標號）。如果這個傳感器的輸出標號可以在一秒內(nèi)辨認出輸入標號，它們可以連接到的結(jié)果也是一個傳感器。如果存在第二個

50、傳感器，它操作輸出第一個并恢復原有的輸入，那么第一個傳感器將被稱作反向的。定理7：被一個有限狀態(tài)統(tǒng)計資源促使的有限狀態(tài)傳感器的輸出是一個有限的狀態(tài)統(tǒng)計 資源，嫡（每單位時間）少于或者等于輸入。如果這個傳感器是單個的，那么它們相等。讓口代表資源的狀態(tài)，它產(chǎn)生一連串的標號Xi ；讓P代表狀態(tài)統(tǒng)計資源，它產(chǎn)生、輸出封閉的標號yj。這個鏈接的系統(tǒng)可以被“生產(chǎn)狀態(tài)區(qū)間”的“（G,P ）”所代表。這兩點的區(qū)間（, 3）和（三邛2）被一條線連接，如果 巴可以得出X,從久到良，這條線是 給出的在這種情況下可能的X。這條線是一個標簽的標號yj。這個輸出的嫡可以像重量和等狀態(tài)那樣被計算出來。如果這個和的結(jié)果P少于

51、或者等于a ,那么嫡不會增加。如果這 一 、 一 一 _ _ ' _ _ ' '個傳感器不是單個的，它輸出與反向的傳感器相一致。如果 Hi , H2和H3是輸出的這個資源的嫡，那么 Hi - H2 - H3 = Hi,所以H1 = H2。假如我們有一個約束可能序列的系統(tǒng)，其類型由像圖2的線狀圖描述。如果概率p（s）被分配到多樣的連接狀態(tài)i到狀態(tài)j的線條，這將變?yōu)橐粋€信源。存在一個使嫡結(jié)果取得最大 值的特殊分配（見附錄 4）。定理8：將約束系統(tǒng)考慮為一個容量為C = logW的信道。如果我們指派心 Bi一個）此一p s） =W j 其中：.：）是符號sth從狀態(tài)i到狀態(tài)j

52、的周期，并且Bi滿足BijBi =£ BjW j 然后H取得最大值并且等于 C。 s, j通過蛻變概率的適當指派，一個信道的符號嫡可以在信道容量上取得最大值。9.無躁聲信道的基本原理我們現(xiàn)在證明對 H的解釋正如通過證明 H確定信道容量需要用最有效的譯碼產(chǎn)生信 息的比率。定理9:取一個嫡值為 H （比特每符號）的信源和一個容量為C （比特每秒）的信道。C而后就有可能編碼信源的輸出，在信道上以這樣一種名符號每秒的平均傳輸速率傳輸，HC其中名是一個任意小的域。不可能以大于 C的速率傳輸。HC定理的相反部分， C不可能被超越，可以記錄每秒輸入的信道嫡等于信源來證明，因H為傳達者必須是非單一的

53、，并且嫡不能超越信道容量。因此 H MC,并且每秒的符號數(shù)目等于 H / H EC /H。定理的第一部分將以兩種不同的方法證明。第一種方法是考慮一系列由信源產(chǎn)生的N個字符的所有序列。對一個大數(shù)N,我們可以分成兩組，一組包括少于2（H*）N個成員，另一組包括少于2RN個成員（其中R是不同符號數(shù)目的對數(shù)），并且有一個小于 N的總概率。隨著N的增加”和N趨向于0。信道中信號數(shù)目的周期 T大于2（C-aT , T大的時候日小。如H果我們選擇T=（H-）NC然后當N和T充分大（盡管 人很小）且有一些增量時對于高概率的組將有足夠的信道 符號的序列數(shù)目。高概率組任意的一對一的方式編碼到集合。保留序列被大的序

54、列描述，以不被用在高概率組的一個序列開始和結(jié)束。這個特殊序列為一個不同的編碼擔當起始和結(jié)束的信號。在中間一個充分的時間被允許對所有低概率信息給出足夠不同的序列。這需要T1 =（ ）NC其中邛很小。符號信息每秒的平均傳輸速度將會大于（1 -）TT廣二（1 - '）（H） , （R ：）"N NCC當N增加時，6,九和平趨向于0且速度趨向于 C。H還有另一個履行譯碼的方法，因此定理的證明可以描述如下：以概率遞減的順序安排長度為N的信息，且假設它們的概率是 p1 > p2 > p3.,> pnos取PS =£ 1 Pi ,也就是Ps是累積概率的結(jié)果，但不

55、包括PS。我們首先編碼成一個二進制數(shù)，信息s的二進制碼是通過展開 PS為二進制數(shù)獲得的。 擴展式被執(zhí)行到 ms位，其中ms是11整數(shù)且滿足：log 2 Wms<1+log2。PsPs這樣高概率的信息由短代碼描述，而低概率的信息由長代碼描述。從這些不等式我們有1 ,1-ms- - ps ：- -ms L2 2 一1在一個或更多的 ms位，Ps的編碼將不同于所有繼后編碼，因為所有剩余P至少 二2這么大，并且它們的二進制擴展因此在第一個ms處不同。從而所有的編碼是不同的，并且有可能從它的編碼重新獲得信息。如果信道序列還不是二進制數(shù)字序列，它們可以以任意的方式被歸因于二進制數(shù)，并且這樣二進制碼就轉(zhuǎn)化為適合信道的信號。二進制數(shù)字所用原始信息的每個符號的平均數(shù)目H是容易估計的。我們有.1 H =一m msP