離散信源的無失真編碼

第2章信源熵本章主要內容2.1單符號離散信源2.2多符號離散平穩(wěn)信源及熵2.3連續(xù)信源及熵2.4離散無失真信源編碼定理

學會忘記痛苦，為陽光記憶騰出空間。

——耶魯大學勵志語錄

22.4離散無失真信源編碼定理信源涉及的重要問題：信源輸出的信息量有多少：即信源信息量的計算問題。如何更有效地表示信源輸出的消息：在盡量提高通信效率的前提下，對信源所發(fā)送的消息進行變換，即信源編碼。32.4離散無失真信源編碼定理信源編碼的定義：把信源輸出的原始消息變換成能夠滿足信道特性，適合信道傳輸的的符號序列（也叫碼序列）的過程，稱為信源編碼。信源編碼的分類無失真信源編碼：把所有的信息絲毫不差地編碼，然后傳送到接收端。離散無失真信源編碼：原始消息是多符號離散信源消息，按無失真編碼的方法，編成對應的碼序列。限失真信源編碼：允許不對所有的信息進行編碼，只對重要信息進行編碼，對其它不影響視聽的信息進行壓縮、丟棄，但這種壓縮失真必須在一定的限度以內，因此稱為限失真信源編碼。4離散信源無失真編碼的基本原理原理圖

說明：（1）信源發(fā)出的消息：是多符號離散信源消息，長度為L,可以用L次擴展信源表示為：XL=(X1X2……XL)其中，每一位Xi都取自同一個原始信源符號集合（n種符號）：X={x1，x2，…xn}則L次擴展信源最多可以對應nL條消息。2.4離散無失真信源編碼定理5（2）信源編碼后，編成的碼序列長度為k,稱為k次擴展信宿，表示為：

Yk=(Y1Y2……Yk)稱為碼字/碼組其中，每一位Yi都取自同一個原始信宿符號集合Y：Y={y1，y2，…ym}又叫信道基本符號集合（其中的每個符號稱為碼元，易看出，信宿是m進制的）

則最多可編成mk個碼序列，它應該和mk條信源消息一一對應。6定長無失真離散信源編碼定理要做到無失真編碼，必須使信源消息和編成的碼序列一一對應：即每條信源消息編成唯一的一個碼字（碼序列）；反過來，每個碼字只能譯成一條消息?！Q為唯一可譯碼。定長編碼：信源消息編成的碼字長度k是固定的。對應的編碼定理稱為定長信源編碼定理。變長編碼：信源消息編成的碼字長度k是可變的。Yk=(Y1Y2……Yk)XL=(X1X2……XL)7定長無失真離散信源編碼定理要做到唯一可譯，需使編成的碼序列數>=待編碼的消息數，即其中：H(X)為原始信源的單符號熵

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

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

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

所以碼組為：

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

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

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

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

L=1,n=10k2=?,m=2k1=4,m=10L=1,n=10000實際為了抗干擾，k2

取513上例中，每個漢字編成長為4的十進制碼組，每個十進制的碼元又編成長為5的二進制等重碼，因此上例屬于兩個信源編碼器的級聯，則每個漢字編成長為20的二進制碼

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

即

k1=4,m=10L=1,n=10000k2=5,m=214信源編碼速率由以上的離散無失真信源的定長編碼定理得：顯然，不等式的右邊是編碼前的平均符號熵。不等式的左邊則是編碼后的平均符號熵：表示編碼后，傳送一個信源符號所需的信息量，稱為信源編碼速率，記作R：bit/符號15信源編碼速率bit/符號信源編碼器16信源編碼速率根據信源編碼速率的定義：即編碼后，傳送一個信源符號所需的信息量，得到離散無失真信源的定長編碼所對應的信源編碼速率為：那么，若是離散無失真信源的變長編碼，所對應的信源編碼速率應該是？bit/符號17信源編碼效率由以上的離散無失真信源的定長編碼定理得：表示信源熵H(X)是個臨界值：要進行無失真信源編碼（譯碼），編碼速率需>=H(X);否則，當信源編碼器的輸出速率小于這個臨界值后，就無法進行無失真的譯碼。因此把二者的比值稱為信源的編碼效率，記作η：bit/符號18信源編碼效率信源編碼效率分析：19定長無失真離散信源編碼定理

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

20離散無記憶信源的變長編碼因此：離散無記憶信源的變長編碼定理為：信源為長L的擴展信源，發(fā)出的第i條消息出現的概率為pi，對信源符號進行m進制的變長編碼，該消息無失真編碼后對應的碼字長度為ki，則無失真變長編碼時的平均碼長滿足下式：其中，第i條消息對應的碼長ki為信源每條消息包含的信息量信源第i條消息包含的信息量21若為單符號離散信源的無失真變長編碼，則L=1,因此編碼定理化簡為:因為22注意：二進制編碼時，有R=。因為R>=H(X),同時為了滿足信道編碼定理的無失真?zhèn)鬏?，需使。所以信源無失真編碼速率的上下限為編碼碼長K越短，編碼速率R越小，但編碼效率越大。信源編碼速率：也就是信源編碼以后在信道中傳輸的速率。（單位：bit/符號）23例：已知離散無記憶信源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=124（2）信源發(fā)2重符號序列消息，無記憶：x