第2章信源熵本章主要內(nèi)容2.1單符號(hào)離散信源2.2多符號(hào)離散平穩(wěn)信源及熵2.3連續(xù)信源及熵2.4離散無(wú)失真信源編碼定理22.4離散無(wú)失真信源編碼定理信源涉及的重要問(wèn)題：信源輸出的信息量有多少：即信源信息量的計(jì)算問(wèn)題。如何更有效地表示信源輸出的消息：在盡量提高通信效率的前提下，對(duì)信源所發(fā)送的消息進(jìn)行變換，即信源編碼。3信源編碼包括兩個(gè)功能：（1）

將信源符號(hào)變換成適合信道傳輸?shù)姆?hào)；（2）

壓縮信源冗余度，提高傳輸效率。4{a1,a2,…,aK}為信源符號(hào)集，序列中每一個(gè)符號(hào)uml都取自信源符號(hào)集。{b1

，b2

，…，bD}是適合信道傳輸?shù)腄個(gè)符號(hào)，用作信源編碼器的編碼符號(hào)。編碼輸出碼字cm=cm1cm2…cmn，

cmk∈{b1

，b2

，…，bD}k=1,2,

…,n

，n表示碼字長(zhǎng)度，簡(jiǎn)稱(chēng)碼長(zhǎng)

信源符號(hào){a1,a2,…,aK}

信道符號(hào)（碼符號(hào)）{b1,b2,…,bD}

圖3-1信源編碼器模型

信源

信源編碼器

一般來(lái)說(shuō)，信源編碼可歸納為如圖3-1所示的模型。

消息

ui

=ui1ui2…uiL

碼字ci

=ci1ci2…cin

5

信源編碼可看成是從信源符號(hào)集到碼符號(hào)集的一種映射，即將信源符號(hào)集中的每個(gè)元素（可以是單符號(hào)，也可以是符號(hào)序列）映射成一個(gè)長(zhǎng)度為n的碼字。對(duì)于同一個(gè)信源，編碼方法是多種的。【例3.3】用{u1

，u2

，u3，u4}表示信源的四個(gè)消息，碼符號(hào)集為{0,1}，表3-1列出了該信源的幾種不同編碼。表3-1同一信源的幾種不同編碼信源消息各消息概率碼1碼2碼3碼4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)1111111000碼的分類(lèi)63.變長(zhǎng)碼若碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長(zhǎng)不都相同，稱(chēng)碼C為變長(zhǎng)碼，表3-1中列出的碼3、碼4就是變長(zhǎng)碼。2.等長(zhǎng)碼在一組碼字集合C中的所有碼字cm(m=1,2,…,M)，其碼長(zhǎng)都相同，則稱(chēng)這組碼C為等長(zhǎng)碼，表3-1中列出的碼1、碼2就碼長(zhǎng)n=2等長(zhǎng)碼。一般，可以將碼簡(jiǎn)單的分成如下幾類(lèi)：1.二元碼若碼符號(hào)集為{0，1}，則碼字就是二元序列，稱(chēng)為二元碼,二元碼通過(guò)二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最常見(jiàn)的一種碼，表3-1列出的4種碼都是二元碼。7離散信源無(wú)失真編碼

內(nèi)容提要用盡可能少的符號(hào)來(lái)傳輸信源消息，目的是提高傳輸效率，這是信源編碼應(yīng)考慮的問(wèn)題，等長(zhǎng)編碼定理給出了等長(zhǎng)編碼條件下，其碼長(zhǎng)的下限值，變長(zhǎng)編碼定理（香農(nóng)第一定理）給出了信源無(wú)失真變長(zhǎng)編碼時(shí)其碼長(zhǎng)的上、下限值。82.4離散無(wú)失真信源編碼定理信源編碼的定義：把信源輸出的原始消息變換成能夠滿足信道特性，適合信道傳輸?shù)牡姆?hào)序列（也叫碼序列）的過(guò)程，稱(chēng)為信源編碼。信源編碼的分類(lèi)無(wú)失真信源編碼：把所有的信息絲毫不差地編碼，然后傳送到接收端。離散無(wú)失真信源編碼：原始消息是多符號(hào)離散信源消息，按無(wú)失真編碼的方法，編成對(duì)應(yīng)的碼序列。限失真信源編碼：允許不對(duì)所有的信息進(jìn)行編碼，只對(duì)重要信息進(jìn)行編碼，對(duì)其它不影響視聽(tīng)的信息進(jìn)行壓縮、丟棄，但這種壓縮失真必須在一定的限度以內(nèi)，因此稱(chēng)為限失真信源編碼。離散限失真信源編碼連續(xù)限失真信源編碼9離散信源無(wú)失真編碼的基本原理原理圖

說(shuō)明：（1）信源發(fā)出的消息：是多符號(hào)離散信源消息，長(zhǎng)度為L(zhǎng),可以用L次擴(kuò)展信源表示為：XL=(X1X2……XL)其中，每一位Xi都取自同一個(gè)原始信源符號(hào)集合（n種符號(hào)）：X={x1，x2，…xn}則最多可以對(duì)應(yīng)nL條消息。2.4離散無(wú)失真信源編碼定理10定長(zhǎng)無(wú)失真離散信源編碼定理要做到無(wú)失真編碼，必須使信源消息和編成的碼序列一一對(duì)應(yīng)：即每條信源消息可以編成唯一的一個(gè)碼字（碼序列）；反過(guò)來(lái)，每個(gè)碼字只能譯成一條消息。——稱(chēng)為唯一可譯碼。定長(zhǎng)編碼：信源消息編成的碼字長(zhǎng)度k是固定的。對(duì)應(yīng)的編碼定理稱(chēng)為定長(zhǎng)信源編碼定理。變長(zhǎng)編碼：信源消息編成的碼字長(zhǎng)度k是可變的。Yk=(Y1Y2……Yk)XL=(X1X2……XL)11定長(zhǎng)無(wú)失真離散信源編碼定理要做到唯一可譯，需使編成的碼序列數(shù)>=待編碼的消息數(shù)，即其中：H(X)為原始信源的單符號(hào)熵

Yk=(Y1Y2……Yk)XL=(X1X2……XL)12定長(zhǎng)無(wú)失真離散信源編碼定理定長(zhǎng)無(wú)失真離散信源編碼定理：原始信源長(zhǎng)為L(zhǎng)的平穩(wěn)無(wú)記憶離散序列信源XL=(X1X2……XL)，每個(gè)符號(hào)的熵為H(X),即平均符號(hào)熵為H(X),要想進(jìn)行無(wú)失真的信源編碼，需滿足碼字的最小長(zhǎng)度為：

13例:已知單符號(hào)離散信源消息輸出的八條消息分別用8個(gè)符號(hào)表示為：{0，1，2…7}，信道基本符號(hào)集合為：{0，1}，為了保證信源編碼無(wú)失真，求輸出碼組的最小長(zhǎng)度，并寫(xiě)出各代碼組。解：由題意知：m=2，n=8，L=1由碼長(zhǎng)公式

L=1,n=8k=?,m=2得

所以碼組為：

14例：有一個(gè)中文信源編碼器如下圖示:求每個(gè)漢字使用編碼器1的話編成的定長(zhǎng)碼長(zhǎng)至少為多少？求每個(gè)漢字對(duì)應(yīng)的二進(jìn)制碼長(zhǎng)又為多少？解：(1)設(shè)漢字集合中漢字?jǐn)?shù)為10000個(gè)，則n=10000，單符號(hào)序列，所以L=1

編碼器1：輸出為十進(jìn)制數(shù)，則m=10，碼長(zhǎng)為

k1=?,m=10L=1,n=1000015即每個(gè)漢字至少要用4位十進(jìn)制數(shù)表示

16針對(duì)編碼器2：每輸入一個(gè)十進(jìn)制數(shù)，編碼后輸出的二進(jìn)制碼組的碼長(zhǎng)為多少？

L=1,n=10k2=?,m=2k1=4,m=10L=1,n=1000017上例中，每個(gè)漢字編成長(zhǎng)為4的十進(jìn)制碼組，每個(gè)十進(jìn)制的碼元又編成長(zhǎng)為5的二進(jìn)制等重碼，因此上例屬于兩個(gè)信源編碼器的級(jí)聯(lián)，則每個(gè)漢字編成長(zhǎng)為20的二進(jìn)制碼

若信源發(fā)“中國(guó)”，則

即

k1=4,m=10L=1,n=10000k2=5,m=218信源編碼速率由以上的離散無(wú)失真信源的定長(zhǎng)編碼定理得：顯然，不等式的右邊是編碼前的平均符號(hào)熵。不等式的左邊則是編碼后的平均符號(hào)熵：表示編碼后，傳送一個(gè)信源符號(hào)所需的信息量，稱(chēng)為信源編碼速率，記作R：bit/符號(hào)19信源編碼速率bit/符號(hào)信源編碼器20信源編碼速率根據(jù)信源編碼速率的定義：即編碼后，傳送一個(gè)信源符號(hào)所需的信息量，得到離散無(wú)失真信源的定長(zhǎng)編碼所對(duì)應(yīng)的信源編碼速率為：那么，若是離散無(wú)失真信源的變長(zhǎng)編碼，所對(duì)應(yīng)的信源編碼速率應(yīng)該是？bit/符號(hào)21信源編碼效率由以上的離散無(wú)失真信源的定長(zhǎng)編碼定理得：表示信源熵H(X)是個(gè)臨界值：要進(jìn)行無(wú)失真信源編碼（譯碼），編碼速率需>=H(X);否則，當(dāng)信源編碼器的輸出速率小于這個(gè)臨界值后，就無(wú)法進(jìn)行無(wú)失真的譯碼。因此把二者的比值稱(chēng)為信源的編碼效率，記作η：bit/符號(hào)22信源編碼效率信源編碼效率分析：23注意：二進(jìn)制編碼時(shí)，有R=,同時(shí)。所以信源無(wú)失真編碼速率的上下限為編碼碼長(zhǎng)K越長(zhǎng)，編碼速率R越大，但編碼效率越小。信源編碼速率：也就是信源編碼以后在信道中傳輸?shù)乃俾省＃▎挝唬篵it/符號(hào)）24例：已知離散無(wú)記憶信源X={x1,x2},且p(x1)=1/4，p(x2)=3/4，求以下兩種情況的編碼效率：（1）信源發(fā)單符號(hào)離散消息：x1,x2，且編成x1—>0，x2—>1解：（1）因?yàn)槭菃畏?hào)消息，一個(gè)符號(hào)表示一條消息，所以L=1因?yàn)榫幊傻拇a字是二進(jìn)制的，所以m=2因?yàn)榫幊傻拇a字長(zhǎng)度都是1，所以平均碼長(zhǎng)k=125（2）信源發(fā)2重符號(hào)序列消息，無(wú)記憶：x1x1，x1x2，x2x1，x2x2，且編成x1x1—>111，x1x2—>110，x2x1—>10，x2x2—>0解：說(shuō)明：發(fā)L重符號(hào)序列的信源編碼器效率要高于單符號(hào)離散無(wú)記憶信源，但同時(shí)也增加了編碼和解碼的復(fù)雜度。26定長(zhǎng)無(wú)失真離散信源編碼定理已知：定長(zhǎng)無(wú)失真離散信源編碼定理：原始信源長(zhǎng)為L(zhǎng)的平穩(wěn)無(wú)記憶離散序列信源XL=(X1X2……XL)，每個(gè)符號(hào)的熵為H(X),即平均符號(hào)熵為H(X),要想進(jìn)行無(wú)失真的信源編碼，需滿足碼字的最小長(zhǎng)度為：

27離散無(wú)記憶信源的變長(zhǎng)編碼因此：離散無(wú)記憶信源的變長(zhǎng)編碼定理為：信源為長(zhǎng)L的擴(kuò)展信源，發(fā)出的第i條消息出現(xiàn)的概率為pi，對(duì)信源符號(hào)進(jìn)行m進(jìn)制的變長(zhǎng)編碼，該消息無(wú)失真編碼后對(duì)應(yīng)的碼字長(zhǎng)度為ki，則無(wú)失真變長(zhǎng)編碼時(shí)的平均碼長(zhǎng)滿足下式：其中，第i條消息對(duì)應(yīng)的碼長(zhǎng)ki為證明：略（利用下式）信源每條消息包含的信息量信源第i條消息包含的信息量28若為單符號(hào)離散信源的無(wú)失真變長(zhǎng)編碼，則L=1,因此編碼定理化簡(jiǎn)為:因?yàn)?9總結(jié)無(wú)失真信源編碼定理從理論上闡明了編碼效率接近于1的理想編碼器的存在性，它使輸出符號(hào)的信息率與信源熵之比接近于1，但要在實(shí)際中實(shí)現(xiàn)，則要求信源符號(hào)序列的L非常大進(jìn)行統(tǒng)一編碼才行，這往往是不現(xiàn)實(shí)的。302、編碼效率：最佳編碼效率為1、編碼信息率：對(duì)于定長(zhǎng)編碼，定義：等長(zhǎng)編碼可表述為，若平均每個(gè)碼符號(hào)所能攜帶的最大信息量設(shè)U=X31結(jié)論：①當(dāng)n=m時(shí)，K≥L不有效。②當(dāng)K=L時(shí)，m≥n，亦不滿足有效性。

由

解決辦法：引入信源統(tǒng)計(jì)特性。例：英文電報(bào)：32字符（26個(gè)字母及6個(gè)字符）即n=32，m=2，L=1得：H(S)=1.4bit每5bit碼字只載荷1.4bit信息量---效率低這時(shí)，我們可以修改①式為：

K/L≥H(U)/logm----②

即考慮信源不等概率，而碼字為等概率，----①這樣即使n=m,只要滿足就有可能實(shí)現(xiàn)K<L32例題：設(shè)離散無(wú)記憶信源概率空間為信源熵為自信息方差為33對(duì)信源符號(hào)采用定長(zhǎng)二元編碼，要求編碼效率無(wú)記憶信源有因此可以得到如果要求譯碼錯(cuò)誤概率則由此可見(jiàn)，在對(duì)編碼效率和譯碼錯(cuò)誤概率的要求不是十分苛刻的情況下，就需要個(gè)信源符號(hào)一起進(jìn)行編碼，這對(duì)存儲(chǔ)和處理技術(shù)的要求太高，目前還無(wú)法實(shí)現(xiàn)。等長(zhǎng)編碼時(shí)34一般說(shuō)來(lái)，當(dāng)L有限時(shí)，高傳輸效率的定長(zhǎng)碼往往要引入一定的失真和譯碼錯(cuò)誤。解決的辦法是可以采用變長(zhǎng)編碼。35變長(zhǎng)編碼定理在變長(zhǎng)編碼中，碼長(zhǎng)是變化的。對(duì)同一信源，究竟哪一種好呢？從高速傳輸信息的觀點(diǎn)來(lái)考慮，當(dāng)然希望選擇由短的碼符號(hào)組成的碼字，就是用碼長(zhǎng)來(lái)作為選擇準(zhǔn)則，為此我們引入碼的平均長(zhǎng)度。設(shè)信源為編碼后的碼字為其碼長(zhǎng)分別為因?yàn)閷?duì)唯一可譯碼來(lái)說(shuō)，信源符號(hào)與碼字是一一對(duì)應(yīng)的，所以有一變長(zhǎng)編碼的基本參數(shù)1、碼的平均長(zhǎng)度36則這個(gè)碼的平均長(zhǎng)度為它是每個(gè)信源符號(hào)平均需用的碼元數(shù)。對(duì)某一信源來(lái)說(shuō)，若有一個(gè)唯一可譯碼，其平均長(zhǎng)度小于所有其它的唯一可譯碼的平均長(zhǎng)度，則該碼稱(chēng)為緊致碼，或稱(chēng)最佳碼。無(wú)失真變長(zhǎng)信源編碼的基本問(wèn)題就是要找最佳碼。2.平均每個(gè)碼元攜帶的信息量---即編碼后信道的信息傳輸速率為3.編碼后每秒鐘信道的信息傳輸速率為37二、單個(gè)符號(hào)變長(zhǎng)編碼定理（平均碼長(zhǎng)界定定理）：1.定理:若一離散無(wú)記憶信源的符號(hào)熵為H(X)，