第4章 無(wú)失真信源編碼-第9講

第4章無(wú)失真信源編碼第一節(jié)編碼的定義第二節(jié)定長(zhǎng)編碼定理第三節(jié)變長(zhǎng)編碼定理第四節(jié)最佳編碼引言引言

編碼分為信源編碼和信道編碼，其中信源編碼又分為無(wú)失真信源編碼和限失真信源編碼。

無(wú)失真信源編碼：適用于離散信源或數(shù)字信號(hào)。

限失真信源編碼：主要用于連續(xù)信源或模擬信號(hào)，如語(yǔ)音、圖像等信號(hào)的數(shù)字處理。香農(nóng)信息論三大定理

:1.

第一極限定理:無(wú)失真信源編碼定理.第二極限定理:信道編碼定理（包括離散和連續(xù)信道）.3.第三極限定理:限失真信源編碼定理.信源編碼的主要任務(wù)是什么?

由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。具體說(shuō)，就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號(hào)序列變換為最短的碼字序列。

信源編碼的基本途徑是什么?

信源編碼的基本途徑有兩個(gè)，一是使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；二是使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。

信源編碼的基礎(chǔ)是什么?

信源編碼的基礎(chǔ)是：兩個(gè)編碼定理，即無(wú)失真編碼定理和限失真編碼定理。

編碼定理證明：（1）必存在一種編碼方法，使代碼的平均長(zhǎng)度可任意接近但不能低于符號(hào)熵（2）達(dá)到這目標(biāo)的途徑，就是使概率與碼長(zhǎng)匹配。

說(shuō)明：（1）無(wú)失真編碼或可逆編碼只適用于離散信源。（2）對(duì)于連續(xù)信源，編成代碼后就無(wú)法無(wú)失真地恢復(fù)原來(lái)的連續(xù)值，因?yàn)楹笳叩娜≈悼捎袩o(wú)限多個(gè)。此時(shí)只能根據(jù)限失真編碼定理進(jìn)行限失真編碼。什么分組碼？設(shè):信源消息為符號(hào)序列Xi，，序列中的每個(gè)符號(hào)取自于符號(hào)集A，。而每個(gè)符號(hào)序列Xi依照固定的碼表映射成一個(gè)碼字Yi，這樣的碼稱為分組碼，有時(shí)也叫塊碼。只有分組碼才有對(duì)應(yīng)的碼表，而非分組碼中則不存在碼表。第一節(jié)編碼的定義信源編碼器L長(zhǎng)序列K長(zhǎng)碼字圖3-1-1信源編碼器設(shè):信源輸出的序列長(zhǎng)度為1，即信源符號(hào)集信源概率空間為：二元信道的信道基本符號(hào)集為{0，1}。若將信源X通過(guò)一個(gè)二元信道傳輸，就必須把信源符號(hào)xi變換成由0，1符號(hào)組成的碼符號(hào)序列，即編碼。可用不同的碼符號(hào)序列，如所示。分組碼的一些直觀屬性分組碼的一些直觀屬性碼{非分組碼分組碼{奇異碼非奇異碼{非唯一可譯碼唯一可譯碼{非即時(shí)碼即時(shí)碼（非延長(zhǎng)碼）碼樹圖

A0100000000000001111111011111二進(jìn)制碼樹2000001111122222三進(jìn)制碼樹唯一可譯碼存在的充分和必要條件

用樹的概念可導(dǎo)出唯一可譯碼存在的充分和必要條件，即各碼字的長(zhǎng)度Ki應(yīng)符合克勞夫特不等式：

(3-1-1)

式中，m是進(jìn)制數(shù)，n是信源符號(hào)數(shù)。

看書P36(例3-1-1）無(wú)失真信源編碼定理要研究的內(nèi)容

若信源輸出符號(hào)序列的長(zhǎng)度，即

變換成由KL個(gè)符號(hào)組成的碼序列（碼字)變換的要求:(1)能夠無(wú)失真或無(wú)差錯(cuò)地從Y恢復(fù)X，也就是能正確地進(jìn)行反變換或譯碼

(2)傳送Y時(shí)所需要的信息率最小

由于Yk可取m種可能值，即平均每個(gè)符號(hào)輸出的最大信息量為logm，KL長(zhǎng)碼字的最大信息量為KLlogm。用該碼字表示L長(zhǎng)的信源序列,則送出一個(gè)信源符號(hào)所需要的信息率平均為:其中是Y所能編成的碼字的個(gè)數(shù)。信息率最小，就是找到一種編碼方式使最小。無(wú)失真信源編碼定理要研究的內(nèi)容:

(1)最小信息率為多少時(shí)，才能得到無(wú)失真的譯碼？(2)若小于這個(gè)信息率是否還能無(wú)失真地譯碼？定長(zhǎng)編碼定理

由L個(gè)符號(hào)組成的、每個(gè)符號(hào)的熵為HL（X）的無(wú)記憶平穩(wěn)信源符號(hào)序列，可用KL個(gè)符號(hào)（每個(gè)符號(hào)有m種可能值）進(jìn)行定長(zhǎng)編碼。對(duì)任意，只要

則當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于；反之，當(dāng)

時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。

第二節(jié)定長(zhǎng)編碼定理

說(shuō)明（1）當(dāng)編碼器容許的輸出信息率，也就是當(dāng)每個(gè)信源符號(hào)所必須輸出的碼長(zhǎng)是時(shí)，只要，這種編碼器一定可以做到幾乎無(wú)失真，也就是收端的譯碼差錯(cuò)概率接近于零，條件是所取的符號(hào)數(shù)L足夠大。（2）將定理的條件改寫成其中：左邊：KL長(zhǎng)碼字所能攜帶的最大信息量，右邊：L長(zhǎng)信源序列攜帶的信息量。上述定理表明，只要碼字所能攜帶的信息量