1、信源、熵率和冗余度計算和分類問題一信息論對信源的研究內容包括哪幾個方面？信息論對信源研究的內容信源的建模：用恰當的隨機過程來描述信號關心角度：信號中攜帶的信息 信源輸出信號中攜帶信息的效率的計算熵率、冗余度信源輸出信息的有效表示信源編碼問題二從信息論的角度如何為信源建模？信源的統計特性如何？如何對信源分類？各類信源如何建模？信源特性信源的統計特性1）什么是信源？信源是信息的來源，實際通信中常見的信源有：語音、文字、圖像、數據。在信息論中，信源是產生消息（符號）、消息（符號）序列以及連續消息的來源，數學上，信源是產生隨機變量X，隨機序列 和隨機過程X(t,)的源。2）信源的主要特性信源的最基本的

2、特性是具有統計不確定性，它可用概率統計特性來描述。信源的分類離散信源與連續信源離散信源單符號信源序列信源平穩&非平穩有記憶&無記憶連續信源連續信源波形信源離散信源單符號離散信源（1）它是最簡單也是最基本的信源，是組成實際信源的基本單元。這類信源可能輸出的消息數是有限的或可數的，而且每次只輸出其中一個消息。因此，可以用一個離散型隨機變量X來描述這個信源輸出的消息。這個隨機變量X的樣本空間就是符號集A；而X的概率分布就是各消息出現的先驗概率，信源的概率空間必定是一個完備集。離散信源單符號離散信源（2）當信源給定，其相應的概率空間就已給定；反之，如果概率空間給定，這就表示相應的信源已給定。所以，概率

3、空間能表征離散信源的統計特性，因此有時也把這個概率空間稱為信源空間。 在實際情況中，存在著很多這樣的信源。例如投硬幣、書信文字、計算機的代碼、電報符號、阿拉伯數字碼等等。這些信源輸出的都是單個符號(或代碼)的消息，它們符號集的取值是有限的或可數的。我們可用一維離散型隨機變量X來描述這些信源的輸出。它的數學模型就是離散型的概率空間：離散信源單符號離散信源的數學描述對單符號離散信源U有：例31：對于二進制數字信源：U=0,1，則有 離散信源離散多符號信源實際的信源輸出的消息是時間或空間上離散的一系列隨機變量。這類信源每次輸出的不是一個單個的符號，而是一個符號序列。在信源輸出的序列中，每一位出現哪個

4、符號都是隨機的，而且一般前后符號的出現是有統計依賴關系的。這種信源稱為多符號離散信源。例32： THEY ARE MY FRIENDS.離散信源多符號離散信源的數學描述多符號離散信源可用隨機矢量/隨機變量序列描述，即 X=X1X2X3信源在不同時刻的隨機變量Xi和Xi+r的概率分布P(Xi)和P(Xi+r)一般來說是不相同的，即隨機變量的統計特性隨著時間的推移而有所變化。離散信源離散平穩信源若信源輸出的隨機序列X=(，)中，每個隨機變量 Xi (i=1,2,，N)都是取值離散的離散型隨機變量，即每個隨機變量Xi的可能取值是有限的或可數的。而且隨機矢量X的各維概率分布都與時間起點無關，也就是在任

5、意兩個不同時刻隨機矢量X的各維概率分布都相同。這樣的信源稱為離散平穩信源。如中文自然語言文字，離散化平面灰度圖像都是這種離散型平穩信源。一般來說，信源輸出的隨機序列的統計特性比較復雜，分析起來也比較困難。為了便于分析，我們假設信源輸出的是平穩的隨機序列，也就是序列的統計性質與時間的推移無關。很多實際信源也滿足這個假設。離散信源平穩信源的數學模型（二維）最簡單的離散平穩信源：二維平穩信源 X=X1X2每兩個符號看做一組，每組代表信源X=X1X2的一個消息；每組中的后一個符號和前一個符號有統計關聯，這種概率性的關系與時間起點無關；假定符號序列的組與組之間是統計獨立的。設X1,X2 x1,x2,xn

6、,矢量Xx1x1, x1xn,x2x1, ,x2xn, xnx1, ,xnxn 令X的數學模型離散信源離散平穩無記憶信源在某些簡單的離散平穩信源情況下，信源先后發出的一個個符號彼此是統計獨立的。也就是說信源輸出的隨機矢量X=(XXX）中，各隨機變量Xi (i=1,2,N)之間是無依賴的、統計獨立的，則N維隨機矢量的聯合概率分布滿足P(X)=P（）P（）P（）我們稱由信源空間X，P(x)描述的信源X為離散無記憶信源。這信源在不同時刻發出的符號之間是無依賴的，彼此統計獨立的。離散信源離散無記憶信源的N次擴展信源離散無記憶信源X= x1,x2,xn，對它的輸出消息序列，可以用一組組長度為N的序列來表

7、示它。這時它就等效成了一個新信源；新信源輸出的符號是N長的消息序列，用N維離散隨機矢量來描述。ai=(xi1xi2xiN) i=1,2, ,n 每個分量xik (k=1,2,N)都是隨機變量，都取值于同一信源X，并且分量之間統計獨立。由隨機矢量X組成的新信源稱為離散無記憶信源X的N次擴展信源。離散無記憶信源的N次擴展信源的數學模型是X信源空間的N重空間。 A B D A C B B A C C D X1 0 0 0 0 0 0 0 0 0 0 0X2 1 1 1 1 1 1 1 1 1 1 1 X3 0 0 0 0 0 0 0 0 0 0 0 X4 0 0 0 0 0 0 0 0 0 0 0

8、X5 0 0 0 0 0 0 0 0 0 0 0 X6 0 0 1 0 0 0 0 0 0 0 1 X7 0 1 0 0 1 1 1 0 1 1 0 X8 1 0 0 1 1 0 0 1 1 1 0 X 1 、X 2、X8 ,均為單符號隨機變量信源X=0,1，P( X 1 X 2X8 ) 與時間起點無關平穩P( X 1 X 2X8 ) P(X 1)P(X 2)P(X8 )無記憶信源例33：電文： 女 孩 兒 在 哭X CHUYJ KOIUY HSFRT NHYTF SGTRW X1 C K H N SX2 H 0 S H GX3 U I F Y TX4 Y U R T RX5 J Y T F

9、W X1,X2,X3,X4,X5均為單符號隨機變量XA、B、CZP(X1X2X3X4X5)=P (X1)P(X2)P(X3)P(X4)P(X5) 且與時間起點無關，X為一無記憶平穩信源例34：離散信源二進制無記憶信源的N次擴展信源把信源輸出的序列看成是一組一組發出的。電報系統中，可以認為每二個二進制數字組成一組。這樣信源輸出的是由二個二進制數字組成的一組組符號。這時可以將它們等效看成一個新的信源，它由四個符號00，01，10，11組成，把該信源稱為二進制無記憶信源的二次擴展。如果把每三個二進制數字組成一組，這樣長度為3的二進制序列就有8種不同的序列，可等效成一個具有8個符號的信源，把它稱為二進

10、制無記憶信源的三次擴展信源。二進制無記憶信源的N次擴展：把每N個二進制數字組成一組，則信源等效成一個具有2N個符號的新信源，把它稱為二進制無記憶信源的N次擴展信源。離散信源離散平穩有記憶信源 一般情況下，信源在不同時刻發出的符號之間是相互依賴的。也就是信源輸出的平穩隨機序列X中，各隨機變量Xi之間是有依賴的。例如，在漢字組成的中文序列中，只有根據中文的語法、習慣用語、修辭制約和表達實際意義的制約所構成的中文序列才是有意義的中文句子或文章。所以，在漢字序列中前后文字的出現是有依賴的，不能認為是彼此不相關的。其他如英文，德文等自然語言都是如此。這種信源稱為有記憶信源。我們需在N維隨機矢量的聯合概率

11、分布中，引入條件概率分布來說明它們之間的關聯。女孩兒在哭 X THIS GIRL IS CRYING X1 T G I C X2 H I S R X3 I R Y X4 S L I X5 N X6 GX1,X2,X3,X4,X5均為單符號隨機變量XA、B、CZP(X1X2X3X4X5)P (X1)P(X2)P(X3)P(X4)P(X5)與時間起點無關， X是一有記憶平穩信源例35：離散信源馬爾可夫信源表述有記憶信源要比表述無記憶信源困難得多。實際上信源發出的符號往往只與前若干個符號的依賴關系強，而與更前面的符號依賴關系弱。為此，可以限制隨機序列的記憶長度。當記憶長度為m+1時，稱這種有記憶信源

12、為m階馬爾可夫信源。也就是信源每次發出的符號只與前m個符號有關，與更前面的符號無關。離散信源時齊馬爾可夫信源設馬爾可夫信源各時刻隨機變量的取值為xk，xkXk，k=1,2,，i-1,i,i+1,N，則描述隨機序列中各隨機變量之間依賴關系的條件概率為 P(xi|xi+2xi+1xi-1xi-2xi-3xi-mx1） =（xi|xi-1xi-2x-3xi-m） （i=1,2,N）如果上述條件概率與時間起點i無關，即信源輸出的符號序列可看成為時齊馬爾可夫鏈，則此信源稱為時齊馬爾可信源。1. 各字母等概、字母間不相關（字符獨立） XFOML RXKHRJFFJUJ LPWCFWKCYFFJEYVKC

13、QSGHYDQPAAMKBZAACIBZLHJQD.2. 字母出現概率按照英文文本統計，字母間不相關（字符獨立） OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVANAH 3. 字母出現概率按照英文文本統計，字母間存在二維相關性（兩兩相鄰字母相關 ） ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIN D ILONASIVETUCOOWEAT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.信源建模信源建模4.字母出現概率按照

14、英文文本統計，字母間存在三維相關性 IN NO IST LAT WHEY CRATICT FROUREBIRSGROCIDPONDENOME OF DEMONSTURESOF THE REPTAGIN IS REGOACTIONA OF CRE.5.字母出現概率按照英文文本統計，字母間存在N維相關性 REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURALHERE HE THE A IN CAME THE TOOF TO EXPERT GRAY COME TO FURNISHESTHE LINE MESSAGE

15、 HAD BE THESE.6.單詞間存在相關性（依據語法）. THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED. 模型復雜度越高，越逼近實際。一個足夠復雜的隨機序列模型能夠滿意地表示自然語言的信源。離散序列信源總結 模擬信源模擬信源又可根據時間是否離散分為連續信源和波

16、形信源。連續信源是時間離散而取值連續的一類信源，波形信源是指取值連續時間也連續的一類信源。由于模擬信源的情況比較復雜，限于學時，我們只對單變量連續信源的信息測度進行討論。連續信源單變量連續信源（1）有的信源雖輸出是單個符號(代碼)的消息，但其可能出現的消息數是不可數的無限值，即輸出消息的符號集A的取值是連續的，或取值是實數集(-，)。例如，遙控系統中有關電壓、溫度、壓力等測得的連續數據。這些數據取值是連續的，但又是隨機的。我們可用一維的連續型隨機變量X來描述這些消息。這種信源稱為連續信源，其數學模型是連續型的概率空間。 連續信源單變量連續信源的描述 單變量連續信源的輸出是取值連續的隨機變量。可

17、用變量的概率密度、變量間的條件概率密度和聯合概率密度描述。 一維概率密度函數 條件概率密度和聯合概率密度函數其中：波形信源更一般地說，實際信源輸出的消息常常是時間和取值都是連續的。例如，語音信號X(t)、熱噪聲信號n(t)、場景圖像信號X(x0,y0,t)等時間連續函數。在某一固定時間t，它們的可能取值又是連續的和隨機的。對于這種信源輸出的消息，可用隨機過程來描述。稱這類信源為隨機波形信源。波形信源分析一般隨機波形信源比較復雜和困難。常見的隨機波形信源輸出的消息是時間、頻帶受限的隨機過程。 根據取樣定理，可以把這樣的隨機過程用一系列時間(或頻率)域上離散的取樣值來表示，而每個取樣值都是連續型隨

18、機變量。隨機過程轉換成時間(或頻率)上離散的隨機序列。在某種條件下可以轉換成隨機變量間統計獨立的隨機序列。平穩的隨機過程可轉換成平穩的隨機序列。隨機波形信源轉換成連續平穩信源。若對每個取樣值(連續型的)經過分層(量化)，就可將連續的取值轉換成有限的或可數的離散值。連續信源轉換成了離散信源。 波形信源（時間連續、取值連續） 連續信源（時間離散、取值連續） 離散信源（時間離散、取值離散）采樣量化實際信源實際信源在離散情況下是消息序列信源，在連續情況下是隨機過程信源，它們分別代表數字與模擬信源。實際信源離散序列信源(1)其中，i=1,2,n為每個消息（符號）取值的種類數 l=1,2,L為消息（符號）

19、序列的長度應注意的是i和l是代表兩個不同范疇的變量，表示不同的概念，切勿混淆。如：五碼英文報：i=26+1，l=5i=1,2,nl=1,2,L實際信源離散序列信源(2)信源輸出是一組隨機序列（矢量）：其樣值為：對應概率為：由于每個隨機變量U=1,2,n有n種取值，則 有 種可能取值。如：五碼英文報：i=26+1，l=5 ， 共有275種取值實際信源離散序列信源(3)例36：最簡單L=3的三位PCM信源：這時L=3, n=2, 即i=0,1，則有：實際信源連續波形信源（1）在實際的連續波形信源中，可以采用兩種方法進行分析一類是將連續波形信源轉化為隨機序列信源另一類是仍然采用隨機過程來分析什么樣的

20、信源可以進行離散化處理？實際上，只要滿足一個非常寬松的條件，即滿足限時(T)、限頻(F)的連續消息信源，即滿足物理可實現條件下，均可離散化為隨機序列。實際信源連續波形信源（2）圖像信源圖像信源一般可以引用一個四元的隨機場來表示： （簡化）主要統計特性： 初步可以認為是一個近似的平穩遍歷過程實際信源連續波形信源（3）語音信源 語音信源可以近似用一個一維隨機過程U(, t)表示。嚴格的講，它是一個非平穩過程，但是對于短時段(5-50ms)可認為是平穩的，且某些是隨機噪聲（清輔音），而某些時段則呈現周期性特征（濁音），還有一些短時段是二者的混合，但是對于短時段(5-50ms)可認為是平穩的。信源輸出

21、信號中攜帶信息如何度量？（以離散信源為例）問題三信源輸出信號中攜帶信息的度量單符號信源的熵離散無記憶平穩信源的熵無記憶平穩信源的N次擴展信源的熵有記憶平穩信源的熵率離散無記憶平穩信源的N次擴展信源的熵因為是無記憶的/統計獨立 若ai =(xi1xi2xi3xiN) 則p(ai)=p(xi1)p(xi2) p(xiN) 其中i1,i2,iN1,2,n 根據信息熵的定義，N次擴展信源的熵可以證明：離散無記憶信源X的N次擴展信源的熵等于離散信源X的熵的N倍，即H(X)=H(XN)=NH(X)例37有一離散無記憶信源求這個離散無記憶信源的二次擴展信源，擴展信源的每個符號是信源X的輸出長度為2的符號序列

22、。因為信源X共有3個不同符號，所以由信源X中每兩個符號組成的不同排列共有32=9種，得二次擴展信源共有9個不同的符號。因為信源X是無記憶的，則有可以算得H(X)=1.5 比特/符號（此處的符號是指X信源的輸出符號xi）H(X)=H(X2)=H(A)=3 比特/符號（此處的符號是指擴展信源的輸出符號ai ，它是由二個xi符號組成） 所以 H(X)=2H(X)對上述結論的解釋： 因為擴展信源XN的每一個輸出符號ai是由N個xi所組成的序列，并且序列中前后符號是統計獨立的。現已知每個信源符號xi含有的平均信息量為H(X)，那么，N個xi組成的無記憶序列平均含有的信息量就為NH(X)（根據熵的可加性）

23、。因此信源XN每個輸出符號含有的平均信息量為NH(X)。 離散無記憶平穩信源的熵當隨機變量X1和X2相互統計獨立時，則因此結論：隨機變量X1和X2統計獨立時，二維離散平穩無記憶信源X =X1X2的熵H(X)等于X1的熵H(X1)和X2的熵H(X2)之和。當X1和X2取值于同一集合時， H(X1)=H(X2)=H(X)， H(X)= H(X2)=2H(X)，與離散無記憶信源二次擴展信源的情況相同。可以把離散無記憶平穩信源的二次擴展信源看成是二維離散無記憶平穩信源的特例；離散平穩有記憶信源的信源熵N維離散平穩有記憶信源的熵H(X)= H(X1)+ H(X2/X1)+ H(X3/X1X2)+ H(X

24、N/X1X2XN-1)證明：（略） 結論：多符號離散平穩有記憶信源X的熵H(X)是X中起始時刻隨機變量X1的熵與各階條件熵之和。由于信源是平穩的，這個和值與起始時刻無關。離散平穩有記憶信源的條件熵的非遞增性條件熵H(XN /X1X2XN-1)隨N的增加是非遞增的，即H(XN /X1X2XN-1) H(XN /X1X2XN-2)證明 前面已證明： H(X2/X1) H(X2)， 同理可證： H(X3/X1X2) H(X3/X2)， 由于信源是平穩的，所以 H(X3/X2)= H(X2/X1)， 故得 H(X3/X1X2) H(X2/X1) H(X1) 對于平穩信源遞推 H(XN /X1X2XN-

25、1) H(XN-1 /X1X2XN-2 ) H(XN-2 /X1X2XN-3 ) H(X3/X1X2) H(X2/X1) H(X1)離散平穩有記憶信源的平均符號熵H(X)/矢量熵= H(X1X2XN-1XN)/聯合熵表示平均發一個消息（由N個符號組成）提供的信息量。平均符號熵：信源平均每發一個符號提供的信息量為離散平穩有記憶信源的 熵率（極限熵）對于離散平穩信源，考察其輸出信息量例38XP（x） 0 1 211/36 4/9 1/4ajai01201/41/18011/181/31/18201/187/36ajai01209/111/8012/113/42/9201/87/9P(ai,aj)P

26、(ai/aj)當信源符號間無依賴性時：當考慮信源符號間的一維依賴性時：條件熵：聯合熵：可見：且：考察信源符號間有依賴性時聯合信源的平均符號熵：可見：比特/符號比特/符號比特/二個符號比特/符號分析：結論：符號間的相關性使得信源的平均符號熵減少，即 每個符號平均攜帶的信息量減少。問題：H2(X)和H(X2|X1)哪一個值更能接近實際二維平穩 信源的熵？即：用哪一個值來表示二維平穩信源 每個符號平均攜帶的信息量比特/符號考察：離散平穩有記憶信源符號之間的依賴長度為N的信源定義：N長的信源符號序列的平均符號熵即平均每個信源符號 所攜帶的信息量為比特/符號當 時，存在以下性質：條件熵 隨N的增加是非遞

27、增的平均符號熵 隨N的增加是非遞增的N給定時，平均符號熵=條件熵。即： 存在，且：結論：對于有限記憶長度的平穩信源可用有限記憶長度的條件熵來對平穩信源進行信息測度。熵率對于離散平穩信源，考察其輸出信息量假設字母序列長度為N，則有限長度的序列的熵可看成隨機矢量（ ）的熵，可用聯合熵表示，平均每個字母的熵 可以表示為 當 時，若 存在，則：定義： 為該平穩信源的熵率，又稱平穩信源的極限熵或極限信息量對于一般的平穩信源，可以證明，極限 一定存在。 結 論熵率的含義：代表了一般離散平穩有記憶信源平均每發一個符號提供的信息量。多符號離散平穩信源實際上就是原始信源在不斷地發出符號，符號之間的統計關聯關系也

28、并不僅限于長度N之內，而是伸向無窮遠。所以要研究實際信源，必須求出熵率H，才能確切地表達多符號離散平穩有記憶信源平均每發一個符號提供的信息量。熵率的計算：必須測定信源的無窮階聯合概率和條件概率分布，這是相當困難的。有時為了簡化分析，往往用條件熵或平均符號熵作為熵率的近似值。在有些情況下，即使N值并不大，這些熵值也很接近H，例如馬爾可夫信源。問題四信源輸出信號的信息攜帶效率如何表示？信源輸出信號的信息攜帶效率的表示冗余度與信源效率它表征信源信息率的多余程度，是描述信源客觀統計特性的一個物理量。 由廣義Shannon不等式有： 冗余度1可見對于有記憶信源，最小單個消息熵應為 ，即從理論上看，對有記

29、憶信源只需傳送 即可。但是這必需要掌握信源全部概率統計特性。這顯然是不現實的。實際上，往往只能掌握有限的維，這時需傳送 ，那么與理論值 相比，就多傳送了 。冗余度2 為了定量描述信源有效性，可定義： 信源效率： 信源冗余度： （相對剩余）或者定義： 冗余度： 信源效率： 相對冗余度：冗余度3正由于信源存在著冗余度，即存在著不必要傳送的信息，因此信源也就存在進一步壓縮信息率的可能性。冗余度越大，壓縮潛力也就越大。可見它是信源編碼、數據壓縮的前提與理論基礎。 字母 字母 字母 空格ETOANIR0.20.1050.0720.06540.0630.0590.0550.054SHDLCF.UMP0.05020.0470.0350.0290.0230.0225 0.0210.0175Y.WGBVKXJ.QZ0.0120.0110.01050.0080.0030.0020.0010.001冗余度4例39：計算英文文字信源的冗余度）首先給出英文字母（含空格）出現概率如下：冗余度5首先求得獨立等概率情況H0 ，即其次，計算獨立不等概率情況H1 ，再次，若僅考慮字母有一維相關性，求H2 ，最后實際熵H，利用統計推斷方法求出。由于采用的逼近的方法和所取的樣本的不