無失真信源編碼定理1012下午上課

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

將信源符號變換成適合信道傳輸?shù)姆枺唬?）

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

，b2

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

cmk∈{b1

，b2

，…，bD}k=1,2,

…,n

，n表示碼字長度，簡稱碼長

信源符號{a1,a2,…,aK}

信道符號（碼符號）{b1,b2,…,bD}

圖3-1信源編碼器模型

信源

信源編碼器

一般來說，信源編碼可歸納為如圖3-1所示的模型。

消息

ui

=ui1ui2…uiL

碼字ci

=ci1ci2…cin

5

信源編碼可看成是從信源符號集到碼符號集的一種映射，即將信源符號集中的每個元素（可以是單符號，也可以是符號序列）映射成一個長度為n的碼字。對于同一個信源，編碼方法是多種的?！纠?.3】用{u1

，u2

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

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

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

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

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

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

所以碼組為：

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

編碼器1：輸出為十進制數(shù)，則m=10，碼長為

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

16針對編碼器2：每輸入一個十進制數(shù)，編碼后輸出的二進制碼組的碼長為多少？

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

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

即

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

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

由

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

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

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