離散信源的無(wú)失真編碼

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

學(xué)會(huì)忘記痛苦，為陽(yáng)光記憶騰出空間。

——耶魯大學(xué)勵(lì)志語(yǔ)錄

22.4離散無(wú)失真信源編碼定理信源涉及的重要問(wèn)題：信源輸出的信息量有多少：即信源信息量的計(jì)算問(wèn)題。如何更有效地表示信源輸出的消息：在盡量提高通信效率的前提下，對(duì)信源所發(fā)送的消息進(jìn)行變換，即信源編碼。32.4離散無(wú)失真信源編碼定理信源編碼的定義：把信源輸出的原始消息變換成能夠滿足信道特性，適合信道傳輸?shù)牡姆?hào)序列（也叫碼序列）的過(guò)程，稱為信源編碼。信源編碼的分類無(wú)失真信源編碼：把所有的信息絲毫不差地編碼，然后傳送到接收端。離散無(wú)失真信源編碼：原始消息是多符號(hào)離散信源消息，按無(wú)失真編碼的方法，編成對(duì)應(yīng)的碼序列。限失真信源編碼：允許不對(duì)所有的信息進(jìn)行編碼，只對(duì)重要信息進(jìn)行編碼，對(duì)其它不影響視聽(tīng)的信息進(jìn)行壓縮、丟棄，但這種壓縮失真必須在一定的限度以內(nèi)，因此稱為限失真信源編碼。4離散信源無(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}則L次擴(kuò)展信源最多可以對(duì)應(yīng)nL條消息。2.4離散無(wú)失真信源編碼定理5（2）信源編碼后，編成的碼序列長(zhǎng)度為k,稱為k次擴(kuò)展信宿，表示為：

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

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

Yk=(Y1Y2……Yk)XL=(X1X2……XL)8定長(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)度為：

9例:已知離散信源消息輸出的八條消息分別用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得

所以碼組為：

10例：有一個(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=1000011即每個(gè)漢字至少要用4位十進(jìn)制數(shù)表示

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

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

取513上例中，每個(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=214信源編碼速率由以上的離散無(wú)失真信源的定長(zhǎng)編碼定理得：顯然，不等式的右邊是編碼前的平均符號(hào)熵。不等式的左邊則是編碼后的平均符號(hào)熵：表示編碼后，傳送一個(gè)信源符號(hào)所需的信息量，稱為信源編碼速率，記作R：bit/符號(hào)15信源編碼速率bit/符號(hào)信源編碼器16信源編碼速率根據(jù)信源編碼速率的定義：即編碼后，傳送一個(gè)信源符號(hào)所需的信息量，得到離散無(wú)失真信源的定長(zhǎng)編碼所對(duì)應(yīng)的信源編碼速率為：那么，若是離散無(wú)失真信源的變長(zhǎng)編碼，所對(duì)應(yīng)的信源編碼速率應(yīng)該是？bit/符號(hào)17信源編碼效率由以上的離散無(wú)失真信源的定長(zhǎng)編碼定理得：表示信源熵H(X)是個(gè)臨界值：要進(jìn)行無(wú)失真信源編碼（譯碼），編碼速率需>=H(X);否則，當(dāng)信源編碼器的輸出速率小于這個(gè)臨界值后，就無(wú)法進(jìn)行無(wú)失真的譯碼。因此把二者的比值稱為信源的編碼效率，記作η：bit/符號(hào)18信源編碼效率信源編碼效率分析：19定長(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)度為：

20離散無(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條消息包含的信息量21若為單符號(hào)離散信源的無(wú)失真變長(zhǎng)編碼，則L=1,因此編碼定理化簡(jiǎn)為:因?yàn)?2注意：二進(jìn)制編碼時(shí)，有R=。因?yàn)镽>=H(X),同時(shí)為了滿足信道編碼定理的無(wú)失真?zhèn)鬏?，需使。所以信源無(wú)失真編碼速率的上下限為編碼碼長(zhǎng)K越短，編碼速率R越小，但編碼效率越大。信源編碼速率：也就是信源編碼以后在信道中傳輸?shù)乃俾?。（單位：bit/符號(hào)）23例：已知離散無(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=124（2）信源發(fā)2重符號(hào)序列消息，無(wú)記憶：x