信息論與編碼第五章

信息論與編碼第五章第一頁(yè)，共一百八十五頁(yè)，2022年，8月28日第5章信源編碼5.1數(shù)據(jù)壓縮概述5.2無失真信源編碼的基本原理5.3無失真信源編碼方法

主要內(nèi)容第二頁(yè)，共一百八十五頁(yè)，2022年，8月28日第二次課第三次課第四次課第三頁(yè)，共一百八十五頁(yè)，2022年，8月28日本次課內(nèi)容:5.1數(shù)據(jù)壓縮概述5.2無失真信源編碼的基本概念

5.2.1信源編碼器5.2.2碼的類型第四頁(yè)，共一百八十五頁(yè)，2022年，8月28日

對(duì)于信源來說，有三個(gè)重要問題需要解決：1、如何構(gòu)建描述信源的模型；2、信源輸出信息量的計(jì)算，即信源熵的問題；3、如何更有效的表示信源輸出問題，即信源壓縮編碼問題。信源編碼的主要任務(wù)就是：減少冗余，提高編碼效率。

第5章信源編碼第五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

信源編碼的基本途徑有兩個(gè)：

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

具體來說，就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的辦法把信源輸出符號(hào)序列變換為最短的碼字序列。第六頁(yè)，共一百八十五頁(yè)，2022年，8月28日

但在許多情況下，并不要求在信宿精確重現(xiàn)信源的輸出，只要滿足一定的重建質(zhì)量要求即可，既允許信息傳輸中出現(xiàn)一定失真，這就是限失真信源編碼問題。例如，在電話通信中，只要能將通話內(nèi)容送達(dá)對(duì)方就可以了，對(duì)音質(zhì)并無太高要求。實(shí)際通信時(shí)，信道往往存在干擾，要完全精確地重現(xiàn)信源輸出幾乎是做不到的。這就允許接收信號(hào)有一定限度的失真。這就是限失真編碼問題,我們不做重點(diǎn)介紹。第七頁(yè)，共一百八十五頁(yè)，2022年，8月28日

5.1數(shù)據(jù)壓縮概述

數(shù)據(jù)壓縮:就是用盡可能少的比特?cái)?shù)來表示源信號(hào)（采樣和量化后數(shù)字信號(hào)），并能將其還原。壓縮的任務(wù)就是保持信源信號(hào)在一個(gè)可以接受的狀況前提下,把需要的比特?cái)?shù)減到最少程度，以達(dá)到減少存儲(chǔ)、處理和傳輸成本的目的。4.1數(shù)據(jù)壓縮概述第八頁(yè)，共一百八十五頁(yè)，2022年，8月28日

信息理論認(rèn)為：若信源編碼的熵大于信源的實(shí)際熵，則該信源中一定存在冗余度，去掉冗余不會(huì)減少信息量，仍可原樣恢復(fù)數(shù)據(jù)；但若減少了熵，數(shù)據(jù)則不能完全恢復(fù)。但在允許的范圍內(nèi)損失一定的熵，數(shù)據(jù)可以近似地恢復(fù)。4.1數(shù)據(jù)壓縮概述第九頁(yè)，共一百八十五頁(yè)，2022年，8月28日常用的壓縮編碼方法可以分為兩大類：1、無損壓縮編碼法，也稱冗余壓縮法或熵編碼法及無失真編碼；2、有損壓縮編碼法，也稱為熵壓縮法或限失真編碼。4.1數(shù)據(jù)壓縮概述第十頁(yè)，共一百八十五頁(yè)，2022年，8月28日

無損壓縮：

是利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全回復(fù)原始數(shù)據(jù)而不引起任何失真。但壓縮率是受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2:1到5:1。特殊應(yīng)用場(chǎng)合的圖像數(shù)據(jù)(如指紋圖像，醫(yī)學(xué)圖像等)的壓縮通常采用這種壓縮。由于壓縮比的限制，僅使用無損壓縮方法是不可能解決圖像和數(shù)字視頻的存儲(chǔ)和傳輸?shù)乃袉栴}。

4.1數(shù)據(jù)壓縮概述第十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日

經(jīng)常使用的無損壓縮方法有：

香農(nóng)Shannon編碼，哈夫曼Huffman編碼，游程(Run-length)編碼，LZW(Lempel-Ziv-Welch)編碼和算術(shù)編碼等。

無損壓縮優(yōu)點(diǎn)：可以做到100％的保存、沒有任何信號(hào)丟失，并且轉(zhuǎn)換方便。

無損壓縮不足：占用空間大、壓縮比不高而且缺乏硬件支持。4.1數(shù)據(jù)壓縮概述第十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日

有損數(shù)據(jù)壓縮：經(jīng)過壓縮、解壓的數(shù)據(jù)與原始數(shù)據(jù)不同,但是非常接近的壓縮方法，又稱破壞型壓縮，即將次要的信息數(shù)據(jù)壓縮掉，犧牲一些質(zhì)量來減少數(shù)據(jù)量，使壓縮比提高。如，利用人類對(duì)圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對(duì)理解原始圖像的影響縮小，卻換來了大得多的壓縮比。4.1數(shù)據(jù)壓縮概述第十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日有損壓縮廣泛應(yīng)用于語(yǔ)音，圖像和視頻數(shù)據(jù)的壓縮。

在多媒體應(yīng)用中，常見的壓縮方法有：PCM(脈沖編碼調(diào)制)，預(yù)測(cè)編碼，變換編碼，插值和外推法，統(tǒng)計(jì)編碼，矢量量化和子帶編碼等?；旌暇幋a是近年來廣泛采用的方法。4.1數(shù)據(jù)壓縮概述第十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日

有損壓縮的優(yōu)點(diǎn)：

在有些情況下能夠獲得比任何已知無損方法小得多的文件大小，同時(shí)又能滿足系統(tǒng)的需要。有損壓縮的不足：會(huì)影響圖像質(zhì)量，尤其是在仔細(xì)觀察的時(shí)候，質(zhì)量下降更加明顯。4.1數(shù)據(jù)壓縮概述第十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

5.2無失真信源編碼的基本概念

5.2.1信源編碼器

編碼的實(shí)質(zhì)：是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換，以碼字代替原始信源符號(hào)，使變換后得到的碼符號(hào)接近等概率分布，從而提高信息的傳輸有效性。4.2無失真信源編碼的基本概念第十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日4.2無失真信源編碼的基本概念信源編碼：從信源符號(hào)到碼符號(hào)的一種映射。

信源編碼器：

編碼器X=｛x1，x2…xq｝S=｛s1…sq｝

C=｛W1…Wq｝定義：信源編碼器的輸入信源符號(hào)集,是輸入消息單元也可以是未編碼的信號(hào)單元.

S的元素si，i=1，2…q叫做信號(hào)單元或消息（共有q個(gè)信源符號(hào)）。編碼器輸出的碼,W的元素Wi,i=1,2,…q叫做碼字。構(gòu)成碼字的符號(hào)集,其元素xi一般是適合信道傳輸?shù)?稱為碼元.第十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日

編碼器X=｛x1，x2…xq｝S=｛s1…sq｝

C=｛W1…Wq｝編碼器的作用：將信源符號(hào)集中的符號(hào)sj，i=1，2…q（或者長(zhǎng)為N的信源符號(hào)序列）變換成由基本符號(hào)xj,j=1,2…r組成的長(zhǎng)度為L(zhǎng)i的一一對(duì)應(yīng)的輸出符號(hào)序列,即

C=｛W1,W2，…Wq｝，

si(i=1,2…q),Wi=(xi1,xi2,…xiL),xik∈X,(k=1,…L)L稱為碼字長(zhǎng)度或簡(jiǎn)稱碼長(zhǎng),所有這些碼字的集合C稱為碼.可見編碼就是從信源符號(hào)到碼符號(hào)的一種映射,若要實(shí)現(xiàn)無失真編碼,必須這種映射是一一對(duì)應(yīng)的,可逆的。

4.2無失真信源編碼的基本概念第十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日如：二元信道基本符號(hào)集為{0,1},將信源符號(hào)s變換成由0和1符號(hào)組成的碼符號(hào)序列(碼元),即編碼。

編碼器X=｛x1=0，x2=1｝S=｛s1…sq｝

C=｛W1…Wq｝4.2無失真信源編碼的基本概念第十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日例如，下表為信源編碼所使用的碼表，信源輸出序列的長(zhǎng)度為L(zhǎng)=1，信源共有4個(gè)符號(hào)，對(duì)應(yīng)的概率空間為信源符號(hào)xi信源符號(hào)出現(xiàn)概率p(xi)碼表碼1碼2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)111114.2無失真信源編碼的基本概念第二十頁(yè)，共一百八十五頁(yè)，2022年，8月28日以碼1為例，將信源輸出的符號(hào)按照固定的規(guī)則進(jìn)行變換，即信源編碼器輸出共有4個(gè)碼字，分別為00，01，10和11，碼字的長(zhǎng)度都為2，即li=2，（i=1，2，3，4）每個(gè)碼字都是由取值于碼符號(hào)集合{0，1}的兩位二元碼組成。也就是說，該碼表將信源輸出的每個(gè)符號(hào)映射成二元碼。4.2無失真信源編碼的基本概念信源符號(hào)xi信源符號(hào)出現(xiàn)概率p(xi)碼表碼1碼2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)11111第二十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日5.2.2碼的類型1.二元(代)碼:

碼符號(hào)集為X={0,1},所得碼字都是一些二元序列,則為二元碼.它是數(shù)字通信和計(jì)算機(jī)系統(tǒng)中最常用的一種碼。2.同價(jià)(代)碼:

若符號(hào)集X:{x1,x2,…,xr}中每個(gè)碼符號(hào)x所占的傳輸時(shí)間相同,則所得的碼C為同價(jià)碼.一般二元碼是同價(jià)碼.電報(bào)中常用的摩爾斯密碼是非同價(jià)碼，其碼符號(hào)(·)和劃(－)所占的傳輸時(shí)間不同.4.2.2碼的類型第二十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日3.定長(zhǎng)碼(固定長(zhǎng)度碼或等長(zhǎng)碼):

若一組碼中所有(碼字的)碼長(zhǎng)都相等,(即Li=L(i=1,2,…,q)),則稱為定長(zhǎng)碼。見書表5-1碼一。4.變長(zhǎng)碼:

碼中的碼字長(zhǎng)短不一.見書表5-1碼二。5.非奇異碼：一組碼中所有的碼字都不相同。即xi≠xj，wi≠wj

4.2.2碼的類型信源符號(hào)xi信源符號(hào)出現(xiàn)概率p(xi)碼表碼1碼2x1p(x1)001x2p(x2)0110x3p(x3)10101x4p(x4)11111第二十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日6.奇異碼：一組碼中有相同的碼字，即

xi≠xj，但wi=wj。見表碼1奇異，碼2非奇異。4.2.2碼的類型信源符號(hào)xi符號(hào)出現(xiàn)的概率p(xi)碼1碼2碼3碼4x11/20011x21/411101001x31/80000100001x41/8110110000001第二十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日7.唯一可譯碼：若碼的任意一串有限長(zhǎng)的碼符號(hào)序列,只能被唯一的譯成所對(duì)應(yīng)的信源符號(hào)序列,則稱為唯一可譯碼。4.2.2碼的類型第二十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

碼1:如碼符號(hào)序列為碼符號(hào)序列為0010

s1s3

唯一可譯碼si碼1碼2s1000s20101s310001s411111s1s2s1s3s1是非唯一可譯碼

碼2.0010

可能譯為4.2.2碼的類型第二十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日注:

奇異碼不是唯一可譯碼;非奇異碼有唯一可譯碼,又有非唯一可譯碼。

唯一可譯碼又分為非即時(shí)譯碼和即時(shí)碼.非即時(shí)譯碼:

接收端收到一個(gè)完整的碼字后,不能立即譯碼,而等下一碼字開始接收后才判斷是否可以碼.4.2.2碼的類型第二十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日表中碼3是非即時(shí)碼,碼4是即時(shí)碼.只要收到1就表示碼意完整。4.2.2碼的類型信源符號(hào)Xi符號(hào)出現(xiàn)的概率P(Xi)碼1碼2碼3碼4X11/20011X21/411101001X31/80000100001X41/8110110000001

即時(shí)碼(非延長(zhǎng)碼或非續(xù)長(zhǎng)碼):

任意一個(gè)碼子都不是其它碼字的前綴部分.

在延長(zhǎng)碼中有的是唯一可譯,有的不是.如碼3是唯一可譯碼。

第二十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日綜上所述，碼的分類有：（非延時(shí)碼）4.2.2碼的類型第二十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日信源符號(hào)Xi符號(hào)出現(xiàn)概率P(Xi)碼1碼2碼3碼4X11/20011X21/411101001X31/80000100001X41/8110110000001表5-2不同的碼字1是奇異碼，碼2是非奇異碼。

碼3是唯一可譯碼，碼2不是唯一可譯碼碼3是非即時(shí)碼。碼4中只要收到符號(hào)1就表示該碼字已完整，可以立即譯碼，所以碼4是即時(shí)碼,又稱為非延長(zhǎng)碼，任意一個(gè)碼字都不是其他碼字的前綴部分構(gòu).第三十頁(yè)，共一百八十五頁(yè)，2022年，8月28日上次課的內(nèi)容:第5章信源編碼5.1數(shù)據(jù)壓縮概述5.2無失真信源編碼的基本原理5.2.1信源編碼器5.2.2碼的類型第三十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日一、常用的壓縮編碼方法可以分為兩大類：1、無損壓縮編碼法，也稱冗余壓縮法或熵編碼法及無失真編碼；2、有損壓縮編碼法，也稱為熵壓縮法或有失真編碼。二、碼的分類復(fù)習(xí)第三十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日本次課的內(nèi)容5.2.3幾個(gè)基本概念5.2.4等長(zhǎng)編碼定理5.2.5變長(zhǎng)編碼定理5.3無失真信源編碼方法第三十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日1、碼樹：

通常情況下可以用碼樹來表示各個(gè)碼字的構(gòu)成，如果碼字序列符號(hào)為m進(jìn)制的，可以用m個(gè)符號(hào)的碼樹來構(gòu)造碼字，每個(gè)碼樹有一個(gè)樹根A,樹根有m個(gè)樹枝，樹枝的盡頭稱為節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)生出是樹枝的數(shù)量等于碼符號(hào)的數(shù)量m，從而形成m進(jìn)制的碼樹。幾個(gè)基本概念幾個(gè)基本概念第三十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日?qǐng)D4-3（a）二進(jìn)制碼樹圖4-3（b）圖是三進(jìn)制碼樹

A為根分為兩個(gè)支，有n=3級(jí)節(jié)點(diǎn)，其終端結(jié)點(diǎn)為23=8個(gè)表示信源符號(hào)，a圖為滿樹.

b圖為非滿樹，是一個(gè)三進(jìn)碼樹，有三個(gè)支，碼是不定長(zhǎng)的。碼樹一定是即時(shí)碼，反之，任何即時(shí)碼都是用碼樹來表示。即時(shí)碼的碼樹可以用來譯碼幾個(gè)基本概念第三十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

【例5.2-1】某地二月份天氣的概率分布統(tǒng)計(jì)如下：雨天的概率是1/8，雪天的概率也是1/8，陰天的概率是1/4，晴天的概率是1/2。設(shè)x1表示雨天，x2表示雪天，x3表示陰天，x4表示晴天，則其離散無記憶信源的概率空間為幾個(gè)基本概念第三十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日表5-3兩種信源編碼方案信源符號(hào)概率方案1的碼字方案2的碼字X11/800000X21/801001X31/41001X41/2111幾個(gè)基本概念采用兩種信源編碼方案編成的碼字如表下所示。繪出方案一和方案二的碼樹，試比較方案1和方案2的碼字哪個(gè)有效性更好一些？第三十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日表5-3兩種信源編碼方案信源符號(hào)概率方案1的碼字方案2的碼字X11/800000X21/801001X31/41001X41/2111幾個(gè)基本概念第三十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日編碼后的每個(gè)信源符號(hào)平均所需的碼元（碼符號(hào)）個(gè)數(shù)。單位為“碼元/信源符號(hào)”。對(duì)單個(gè)信源符號(hào)進(jìn)行編碼，設(shè)信源為2、平均碼長(zhǎng)幾個(gè)基本概念第三十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日幾個(gè)基本概念每個(gè)碼字對(duì)應(yīng)的碼長(zhǎng)為Ki（i＝1，2……q）該碼的平均碼長(zhǎng)為（碼元/信源符號(hào)）方案1的平均碼長(zhǎng)

方案2的平均碼長(zhǎng)（碼元/信源符號(hào)）（碼元/信源符號(hào)）信源符號(hào)概率方案1的碼字方案2的碼字X11/800000X21/801001X31/41001X41/2111第四十頁(yè)，共一百八十五頁(yè)，2022年，8月28日3、信息傳輸率

編碼后信息傳輸率R又稱為碼率，是指編碼后每個(gè)碼元載荷的信息量。單位為“比特/碼元”或“比特/碼符號(hào)”。（比特/碼元）碼率--平均碼長(zhǎng)H(x)—信源熵幾個(gè)基本概念第四十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日

【例4.2-1】中信源熵H(x)＝1.75比特/符號(hào)，方案1編碼后每個(gè)碼元載荷的平均信息量：方案2編碼后每個(gè)碼元載荷的平均信息量：（比特/碼元）（比特/碼元）由于每個(gè)二進(jìn)制碼元所能攜帶的最大信息量為1比特，所以方案2是一種最佳編碼。幾個(gè)基本概念信源符號(hào)概率方案1的碼字方案2的碼字X11/800000X21/801001X31/41001X41/2111第四十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日4、編碼效率編碼效率：表示編碼后實(shí)際信息量和能載荷最大信息量的比值。假設(shè)碼元為m進(jìn)制，即可取m種可能值，則每個(gè)碼元所能載荷的最大信息量為logm比特/碼元。二元編碼效率幾個(gè)基本概念第四十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日方案2編碼后每個(gè)碼元載荷的平均信息量：（比特/碼元）（比特/碼元）方案1編碼后每個(gè)碼元載荷的平均信息量：從編碼效率看，方案1的編碼效率為0.875，方案2的編碼效率為1。所以方案2比方案1的有效性要更好一些。第四十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日5、克勞夫特不等式用碼樹的概念可以推導(dǎo)出唯一可譯碼存在的充要條件，即各碼字的長(zhǎng)度Ki應(yīng)符合不等式m是進(jìn)制數(shù)，n是信源符號(hào)數(shù)

稱之為克勞夫特(Kraft)不等式幾個(gè)基本概念第四十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

該不等式指出了即時(shí)碼的碼長(zhǎng)必須滿足的條件。麥克米倫證明惟一可譯碼也滿足此不等式；在碼長(zhǎng)選擇的條件上，即時(shí)碼與唯一碼是一致的?？藙诜蛱夭坏仁浇o出了m元碼中，信源序列中的消息數(shù)n與碼字的各個(gè)碼長(zhǎng)之間的關(guān)系。說明，若三者滿足上式，至少能構(gòu)成一種這樣碼長(zhǎng)的即時(shí)碼或惟一可譯碼，否則無法構(gòu)造即時(shí)碼或惟一可譯碼。幾個(gè)基本概念第四十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日【例4.2-2】設(shè)二元碼樹中

不存在滿足這種Ki的唯一可譯碼。如碼字為{0，10，11，110}。試將碼字長(zhǎng)度改為，則此時(shí)這樣的碼就存在唯一可譯碼，如碼字為{0，10，110，111}。幾個(gè)基本概念第四十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日

010110A0101011碼字為不是唯一可譯碼

要實(shí)行上述碼必須在中間放置碼字010110A01010111111這樣就產(chǎn)生了非延長(zhǎng)碼{0，10，110，111}.幾個(gè)基本概念可以用碼樹進(jìn)行檢查第四十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日注：

碼字{0，10，010，111}雖然也滿足克勞夫特不等式，卻它并不是唯一可譯碼。這是因?yàn)椋藙诜蛱夭坏仁讲⒉荒茏鳛榕袆e一種碼是否為即時(shí)碼或唯一可譯碼的依據(jù)。例如，碼組中有長(zhǎng)度相等的兩個(gè)碼字，則這兩個(gè)碼字無論是否相同，都有可能使不等式成立，然而，當(dāng)這兩個(gè)碼字相同時(shí)，它們一定不是唯一可譯碼。因此，唯一可譯碼一定滿足克拉夫特不等式，反之，滿足克拉夫特不等式的碼不一定是唯一可譯碼。幾個(gè)基本概念第四十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日

可以用3個(gè)二進(jìn)制碼元對(duì)該信源進(jìn)行無失真編碼.即碼長(zhǎng)為K=3碼元/符號(hào)例：某信源有8種等概符號(hào)，L=1，信源序列熵達(dá)到最大值，由最大熵定理H(X)≤㏒m，Hl(X)=㏒8=3比特/符號(hào)等長(zhǎng)編碼定理第五十頁(yè)，共一百八十五頁(yè)，2022年，8月28日

而取2.55碼元/符號(hào),只有22.55=5.856種可能碼字,還有部分符號(hào)沒有對(duì)應(yīng)的碼字,一旦這些符號(hào)傳到接收端將引起譯碼錯(cuò)誤.所以定長(zhǎng)編碼一般都存在譯碼差錯(cuò),L越大差錯(cuò)越小。若信源輸出概率不相等，如p(x)={0.4，0.18，0.1，0.1，0.07，0.06，0.05，0.04｝則

比特/符號(hào)等長(zhǎng)編碼定理第五十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日例：如果有四個(gè)信源符號(hào){s1，s2，s3，s4}，采用二元編碼，KL=2，則可以編成s1=00，s2=01，s3=10，s4=11。如果我們要對(duì)信源的L次擴(kuò)展信源進(jìn)行編碼，也必須滿足，兩邊取對(duì)數(shù)得：表示平均每個(gè)信源符號(hào)所需的碼符號(hào)個(gè)數(shù)。若對(duì)信源進(jìn)行等長(zhǎng)編碼，則必須滿足其中，KL是碼長(zhǎng)，m是碼符號(hào)集中的碼元數(shù)，q信源符號(hào)個(gè)數(shù)。5.2等長(zhǎng)碼第五十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日例：對(duì)英文電報(bào)的32個(gè)符號(hào)進(jìn)行二元編碼，根據(jù)上述關(guān)系：

我們繼續(xù)討論上面得例子，我們已經(jīng)知道英文的極限熵是1.4bit,遠(yuǎn)小于5bit，也就是說，5個(gè)二元碼符號(hào)只攜帶1.4bit的信息量，實(shí)際上，5個(gè)二元符號(hào)最多可以攜帶5bit信息量。我們可以做到讓平均碼長(zhǎng)縮短，提高信息傳輸率5.2等長(zhǎng)碼第五十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日我們舉例說明：

設(shè)信源而其依賴關(guān)系為：5.2等長(zhǎng)碼第五十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日若不考慮符號(hào)間的依賴關(guān)系，對(duì)此信源作二次擴(kuò)展若考慮符號(hào)間的依賴關(guān)系，則

可見，由于符號(hào)間依賴關(guān)系的存在，擴(kuò)展后許多符號(hào)出現(xiàn)的概率為0，此信源只有4個(gè)字符，可得碼長(zhǎng)，但平均每個(gè)信源符號(hào)所需碼符號(hào)為5.2等長(zhǎng)碼第五十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

我們?nèi)砸杂⑽碾妶?bào)為例，在考慮了英文字母間的相關(guān)性之后，我們對(duì)信源作L次擴(kuò)展，在擴(kuò)展后形成的信源（也就是句子）中，有些句子是有意義的，而有些句子是沒有意義的，我們可以只對(duì)有意義的句子編碼，而對(duì)那些沒有意義的句子不進(jìn)行編碼，這樣就可以縮短每個(gè)信源符號(hào)所需的碼長(zhǎng)。等長(zhǎng)信源編碼定理給出了進(jìn)行等長(zhǎng)信源編碼所需碼長(zhǎng)的極限值。5.2等長(zhǎng)碼第五十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日定理5.3（等長(zhǎng)信源編碼定理）一個(gè)熵為H(X)的離散無記憶信源，若對(duì)其L次擴(kuò)展信源進(jìn)行等長(zhǎng)m元編碼，碼長(zhǎng)為KL，對(duì)于任意大于0，只要滿足則可以實(shí)現(xiàn)幾乎無失真編碼，反之，若：則不可能實(shí)現(xiàn)無失真編碼5.4等長(zhǎng)信源編碼定理第五十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日定理5.3的條件式可寫成：左邊表示長(zhǎng)為的碼符號(hào)所能載荷的最大信息量，而右邊代表長(zhǎng)為L(zhǎng)的序列平均攜帶的信息量。因此，只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實(shí)現(xiàn)無失真編碼。定理5.3的條件式也可寫成：令：

稱之為編碼信息率。可見，編碼信息率大于信源的熵，才能實(shí)現(xiàn)無失真編碼。5.4等長(zhǎng)信源編碼定理第五十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日最佳編碼效率為：為了衡量編碼效果，引進(jìn)稱為編碼效率。5.4等長(zhǎng)信源編碼定理第五十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日ε為一正數(shù),當(dāng)σ2(X)和ε2均為定值時(shí),只要L足夠大,pe

可以小于任一正數(shù)δ.

即信源序列長(zhǎng)度滿足

時(shí),就能達(dá)到差錯(cuò)率的要求。即

差錯(cuò)概率為

在實(shí)際情況下,要實(shí)現(xiàn)幾乎無失真的等長(zhǎng)編碼,L需要大到難以實(shí)現(xiàn)的程度。

為信源序列的自信息方差等長(zhǎng)編碼定理第六十頁(yè)，共一百八十五頁(yè)，2022年，8月28日5.2.4等長(zhǎng)編碼定理由L個(gè)符號(hào)（消息）組成的、每個(gè)符號(hào)的熵為HL(X)的無記憶平穩(wěn)信源符號(hào)序列X1,X2,…,Xl,…XL，可用KL個(gè)符號(hào)Y1,Y2…,Yk,…YKL

（每個(gè)符號(hào)有m種可能值）進(jìn)行定長(zhǎng)編碼。對(duì)任意

，只要?jiǎng)t當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于δ,反之，當(dāng)

時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。等長(zhǎng)編碼定理第六十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日

碼字長(zhǎng)度

，在定長(zhǎng)編碼中是定值，是符號(hào)個(gè)數(shù)，當(dāng)編碼器容許的輸出信息率,即每個(gè)信源符號(hào)必須輸出的碼長(zhǎng)是

時(shí)，只要

，且所取的符號(hào)數(shù)足夠大，此時(shí)這種編碼器一定可以做到幾乎無失真，即收端的譯碼差錯(cuò)概率接近于零。等長(zhǎng)編碼定理第六十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日

則(1)式可以寫為

（無失真ε=0）

左側(cè)為KL長(zhǎng)碼字所攜帶的最大信息量，右側(cè)為L(zhǎng)長(zhǎng)信源序列攜帶的信息量.

當(dāng)左側(cè)﹥右側(cè)，編碼幾乎不失真當(dāng)左側(cè)=右側(cè)，臨界狀態(tài)。當(dāng)左側(cè)<右側(cè)，不能實(shí)現(xiàn)無失真編碼等長(zhǎng)編碼定理第六十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日例:設(shè)離散無記憶信源=求信源符號(hào)序列長(zhǎng)

解：自信息方差

=3/4(log3/4)2+1/4(log1/4)2-(0.811)2=0.4715等長(zhǎng)編碼定理第六十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日則：

L≥=

=1.923×107允許錯(cuò)誤概率pe≤10-5

若對(duì)信源X采取等長(zhǎng)二元編碼,要求編碼效率η=0.96

信源序列長(zhǎng)度需長(zhǎng)達(dá)1923萬(wàn)以上，才能實(shí)現(xiàn)給定的要求，這在實(shí)際中很難實(shí)現(xiàn)。編碼效率定義最佳編碼效率等長(zhǎng)編碼定理第六十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

4.2.5變長(zhǎng)編碼定理

變長(zhǎng)編碼，編碼后碼長(zhǎng)K是變化的。如果概率大的符號(hào)用短碼，概率小的符號(hào)用較長(zhǎng)的碼，則大量信源符號(hào)編成碼后，平均每個(gè)信源符號(hào)所需的輸出符號(hào)數(shù)就可以降低，就可以提高編碼效率。變長(zhǎng)編碼定理第六十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日

單個(gè)符號(hào)變長(zhǎng)編碼定理:若一離散無記憶信源的符號(hào)熵為H(X)，每個(gè)信源符號(hào)用m進(jìn)制碼元進(jìn)行變長(zhǎng)編碼，一定存在一種無失真編碼方法，其碼字平均長(zhǎng)度

滿足下列不等式碼字的平均碼長(zhǎng)不能小于極限值H(X)/logm，否則唯一可譯碼不存在。平均碼長(zhǎng)小于上界值時(shí)，唯一可譯碼肯定存在，但并不是說大于這個(gè)上界不能夠成為唯一可譯碼，而是因?yàn)橄Ｍ骄a長(zhǎng)盡可能短。定理給出了無失真信源編碼的最短平均碼長(zhǎng)，并指出這個(gè)最短的平均碼長(zhǎng)與信源熵H(X)有關(guān)。變長(zhǎng)編碼定理第六十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日

離散平穩(wěn)無記憶序列變長(zhǎng)編碼定理（香農(nóng)第一定理）:對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足下列不等式其中ε為任意小正數(shù)。變長(zhǎng)編碼定理第六十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日要實(shí)現(xiàn)無失真的信源編碼，采用m元碼進(jìn)行編碼時(shí)，每個(gè)信源符號(hào)的平均碼長(zhǎng)的極限值就是原始信源的熵值。當(dāng)編碼的平均碼長(zhǎng)小于信源的熵值，則唯一可譯碼不存在，在譯碼時(shí)必然帶來失真或差錯(cuò)。同時(shí)還表明通過對(duì)擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，當(dāng)L→∞時(shí)，平均碼長(zhǎng)可以達(dá)到這個(gè)極限值。

變長(zhǎng)編碼定理第六十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日已知平均輸出信息率：

設(shè)用m進(jìn)制碼元作變長(zhǎng)編碼，序列長(zhǎng)度為L(zhǎng)個(gè)信源符號(hào)，則上個(gè)定理，可以得到平均碼長(zhǎng)

滿足下列不等式兩個(gè)定理關(guān)系：變長(zhǎng)編碼定理第七十頁(yè)，共一百八十五頁(yè)，2022年，8月28日化簡(jiǎn)有：則

變長(zhǎng)編碼定理當(dāng)L足夠大時(shí),可使

,則上式可寫為:第七十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日

用變長(zhǎng)編碼來達(dá)到相當(dāng)高的編碼效率,一般所要求的符號(hào)長(zhǎng)度可以比定長(zhǎng)編碼小得多,由前式得編碼效率的下界：變長(zhǎng)編碼定理第七十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日

如上次的例子:m=2,logm=1,H(x)=0.811比特/符號(hào)要求編碼效率η=0.96定長(zhǎng)編碼符號(hào)序列長(zhǎng)為：

L=1.923×107變長(zhǎng)編碼定理第七十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日

編碼效率總是小于1,用此衡量各種編碼方法的優(yōu)劣,為了衡量各種編碼方法與最佳碼的差距,定義碼的剩余度為:變長(zhǎng)編碼定理第七十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日

例

設(shè)離散無記憶信源的概率空間為

求:用二元碼符號(hào)(0,1)來構(gòu)成一個(gè)即時(shí)碼時(shí)的信息傳輸率。變長(zhǎng)編碼定理第七十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

信源熵為H(X)=解：=0.81比特/符號(hào)用二進(jìn)制符號(hào)(0,1)來構(gòu)成一個(gè)即時(shí)碼，

x10,x21平均碼長(zhǎng)：變長(zhǎng)編碼定理第七十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日信息傳輸率為：

根據(jù)香農(nóng)第一定理可對(duì)信源X的二次擴(kuò)展信源X2進(jìn)行編碼,即L=2的信源進(jìn)行變長(zhǎng)編碼,即時(shí)碼表如表：編碼效率為：1111/16X2X21103/16X2X1103/16X1X209/16X1X1即時(shí)碼序列概率序列變長(zhǎng)編碼定理第七十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日碼的平均長(zhǎng)度：信源中每一個(gè)單個(gè)符號(hào)的平均碼長(zhǎng)：信息傳輸率:編碼效率：1111/16X2X21103/16X2X1103/16X1X209/16X1X1即時(shí)碼序列概率序列變長(zhǎng)編碼定理第七十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日

由此可見編碼效率越復(fù)雜,傳輸率越高.

若用定長(zhǎng),當(dāng)編碼效率η=96%,編碼錯(cuò)誤概率δ≤105,則信源序列長(zhǎng)度

L＞4.13×107用同樣的方法進(jìn)行三次，四次信源擴(kuò)展即

L=3，L=4，得η3=0.985=R3η4=0.991=R4η1=0.81=R1η2=0.962變長(zhǎng)編碼定理第七十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日

2.變長(zhǎng)碼,L不需太長(zhǎng),則可達(dá)到相當(dāng)高的編碼效率,且可以實(shí)現(xiàn)無失真編碼,隨著L增加,η

越接近1,編碼后的信息傳輸率R也越來越接近無噪無損二元對(duì)稱信道的容量,使信道得到充分的利用。1.定長(zhǎng)碼需要信源序列長(zhǎng),且總存在譯碼差錯(cuò)。結(jié)論：變長(zhǎng)編碼定理第八十頁(yè)，共一百八十五頁(yè)，2022年，8月28日4.3無失真信源編碼方法4.3.1香農(nóng)編碼香農(nóng)編碼方法又稱最佳變長(zhǎng)編碼方法。最佳變長(zhǎng)編碼:

能載荷一定信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合。對(duì)于某一信源和某一碼元集來說，如果有一個(gè)唯一可譯碼的平均碼長(zhǎng)不大于其他的唯一可譯碼的平均碼長(zhǎng)，則稱此碼為最佳碼或稱為緊致碼。香農(nóng)編碼第八十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日

最佳碼兩個(gè)特點(diǎn)：1、概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的對(duì)應(yīng)于長(zhǎng)碼，充分利用了短碼；2、對(duì)于二元最佳碼，所對(duì)應(yīng)的縮減信源的兩個(gè)最小概率的信源符號(hào)所對(duì)應(yīng)的碼字具有相同的碼長(zhǎng)，且總是最后一位不同，保證是即時(shí)碼。

最佳變長(zhǎng)編碼的方法主要有：

香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。香農(nóng)編碼第八十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日設(shè)離散無記憶信源：二進(jìn)制香農(nóng)編碼步驟如下：香農(nóng)編碼第八十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日1.將信源符號(hào)按概率從大到小的順序排列

p(x1)≥p(x2)≥p(xn)2.確定下列不等式的整數(shù)碼長(zhǎng)Ki-logp(xi)≤Ki＜-logp(Xi)+13.令P(x0)=0,為編成唯一可譯碼,計(jì)算第i個(gè)信息的累加概率4.將累加概率pi變成二進(jìn)制數(shù);5.取pi二進(jìn)制數(shù)的小數(shù)點(diǎn)后Ki位即為該消息的二進(jìn)制碼字。香農(nóng)編碼第八十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日【例4.3-1】設(shè)信源共7個(gè)符號(hào)消息,其數(shù)學(xué)模型如下

香農(nóng)編碼第八十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日6.660.01x73.340.10x62.740.15x52.560.17x42.480.18x32.410.19x22.340.2x1碼字碼字長(zhǎng)度Ki-logp(xi)累加概率符號(hào)概率p(xi)信源消息符號(hào)xi香農(nóng)編碼過程如下：1.p(xi)排隊(duì)，

-logp(xi)≤Ki

＜-logp(Xi)+12.確定下列不等式的整數(shù)碼長(zhǎng)KiiP3333347香農(nóng)編碼第八十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日6.660.01x73.340.10x62.740.15x52.560.17x432.480.18x32.410.19x22.340.2x1碼字碼字長(zhǎng)度Ki-logp(xi)累加概率符號(hào)概率p(xi)信源消息符號(hào)xi33347

300.390.570.740.890.990.23.累加概率香農(nóng)編碼第八十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日4,將pi

變成二進(jìn)制數(shù)，以x3

為例∵K3取3,故碼字為0110.39×2=0.78…00.78×2=1.56…10.56×2=1.12…10.12×2=0.24…001106.660.01x73.340.10x62.740.15x52.560.17x432.480.18x32.410.19x22.340.2x1碼字碼字長(zhǎng)度Ki-logp(xi)累加概率符號(hào)概率p(xi)信源消息符號(hào)xi33347

300.390.570.740.890.990.211111101110101000001011100共有5個(gè)三位代碼組,各代碼組之間至少有一個(gè)數(shù)不同是唯一可譯碼，可看出這七個(gè)代碼組都不是延長(zhǎng)碼,均屬于即時(shí)碼?！週=1，

m=2該編碼的平均碼長(zhǎng)為：∑p(xi)Ki=(0.2+0.19+0.18+0.17+0.15)×3+0.1×4+0.01×7=0.89×3+0.4+0.07=3.14碼元/符號(hào)香農(nóng)編碼第八十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日平均信息速率：=-[0.2log0.2+0.19log0.19+0.18log0.18+0.17log0.17+0.15log0.15+0.1log0.1+0.01log0.01］/3.14=0.813比特/碼元=2.61/3.14香農(nóng)編碼第八十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日編碼效率:

上述信源若采用定長(zhǎng)編碼，要做到無失真譯碼，每個(gè)符號(hào)至少要用三個(gè)比特來表示，比較起來香農(nóng)編碼無疑對(duì)信源進(jìn)行了壓縮，但編碼效率并不是很高。香農(nóng)編碼第九十頁(yè)，共一百八十五頁(yè)，2022年，8月28日6.660.01x73.340.10x62.740.15x52.560.17x432.480.18x32.410.19x22.340.2x1碼字碼字長(zhǎng)度Ki-logp(xi)累加概率符號(hào)概率p(x)信源消息符號(hào)xi33347

300.390.570.740.890.990.2練習(xí)畫樹:11101010000010111001111110練習(xí)題第九十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日上次課的內(nèi)容4.2.3幾個(gè)基本概念4.2.4等長(zhǎng)編碼定理4.2.5變長(zhǎng)編碼定理4.3無失真信源編碼方法4.3.1香農(nóng)編碼方法第九十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日2、在定長(zhǎng)編碼中，碼長(zhǎng)K是定值3、編碼效率：表示編碼后實(shí)際信息量和能載荷最大信息量的比值復(fù)習(xí)1、最佳變長(zhǎng)編碼:能載荷一定信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合。二元編碼效率信息傳輸率第九十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日4、碼樹:碼樹有一個(gè)樹根A,樹根有m個(gè)樹枝，樹枝的盡頭稱為節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)生出是樹枝的數(shù)量等于碼符號(hào)的數(shù)量m，從而形成m進(jìn)制的碼樹。5、平均碼長(zhǎng):

編碼后的每個(gè)信源符號(hào)平均所需的碼元（碼符號(hào)）個(gè)數(shù)。第九十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日(1)要求信源符號(hào)Xi,與碼字Yi一一對(duì)應(yīng);(2)與碼字組成的碼符號(hào)序列的逆變換也是唯一的

(能被唯一的譯成所對(duì)應(yīng)的信源符號(hào)序列).6、要想實(shí)現(xiàn)無失真編碼:

用定長(zhǎng)編碼若想實(shí)現(xiàn)無失真編碼,L需足夠長(zhǎng),不容易實(shí)現(xiàn),現(xiàn)討論變長(zhǎng)碼,尋求是小的K值。第九十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日1.將信源符號(hào)按概率從大到小的順序排列

p(x1)≥p(x2)≥p(xn)2.確定下列不等式的整數(shù)碼長(zhǎng)Ki-logp(xi)≤Ki＜-logp(Xi)+13.令P(x0)=0,為編成唯一可譯碼,計(jì)算第i個(gè)信息的累加概率4.將累加概率pi變成二進(jìn)制數(shù);5.取pi二進(jìn)制數(shù)的小數(shù)點(diǎn)后Ki位即為該消息的二進(jìn)制碼字。7、香農(nóng)編碼步驟第九十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日本次課內(nèi)容4.3.2費(fèi)諾編碼方法4.3.3哈夫曼編碼方法4.3.4游程(Run-length)編碼第九十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日編碼步驟:

1.

將信源消息符號(hào)按其出現(xiàn)概率大小依次排列：

p(x1)≥p(x2)….p(xn)。

2.將依次排列的信源符號(hào)按概率值分兩大組,并對(duì)各組賦予一個(gè)二進(jìn)制元碼0、1。4.3.2費(fèi)諾編碼

費(fèi)諾（Fano）編碼（簡(jiǎn)稱費(fèi)諾碼）屬于概率匹配編碼.不是最佳編碼。

3.將每一大組的信源符號(hào)進(jìn)一步分組,使劃分后的兩組概率和近于相同并又賦兩組0,1。

4.如此重復(fù),至兩組只剩下一個(gè)信源符號(hào)為止。

5.信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼.4.3.2費(fèi)諾編碼第九十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日4.3.2費(fèi)諾編碼41111

10.01x741110

0

10.1x63110

0

10.15x5210

0

10.17x43011

10.18x33010

0

10.19x2200

000.2x1碼長(zhǎng)Ki二元碼第五次分組第四次分組第三次分組第二次分組第一次分組各消息概率信源符號(hào)xi平均碼長(zhǎng)：=(0.2+0.17)×2+(0.19+0.18+0.15)×3(0.1+0.01)×4=0.74+1.56+0.44=2.94碼元/符號(hào)費(fèi)諾碼編碼過程如下：第九十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日信息傳輸率：編碼效率：η

=95.3%費(fèi)諾編碼比香農(nóng)碼平均碼長(zhǎng)短,R大,效率高。4.3.2費(fèi)諾編碼第一百頁(yè)，共一百八十五頁(yè)，2022年，8月28日4.3.2費(fèi)諾編碼41111

10.01x741110

0

10.1x63110

0

10.15x5210

0

10.17x43011

10.18x33010

0

10.19x2200

000.2x1碼長(zhǎng)Ki二元碼第五次分組第四次分組第三次分組第二次分組第一次分組各消息概率信源符號(hào)xi碼樹：A010101011100000100111101011101111第一百零一頁(yè)，共一百八十五頁(yè)，2022年，8月28日香農(nóng)編碼和費(fèi)諾編碼.在R、?方面,費(fèi)諾編碼強(qiáng)于香農(nóng)編碼。香農(nóng)編碼：?=0.813費(fèi)諾編碼：?=0.953

4.3.2費(fèi)諾編碼第一百零二頁(yè)，共一百八十五頁(yè)，2022年，8月28日4.3.3哈夫曼編碼一、編碼方法1952年，哈夫曼提出了一種構(gòu)造最佳碼的方法。所得的碼字是即時(shí)碼，而且在所有唯一可譯碼中，它的平均碼長(zhǎng)最短，是一種最佳變長(zhǎng)碼。哈夫曼（Huffman）編碼方法的編碼步驟：哈夫曼編碼第一百零三頁(yè)，共一百八十五頁(yè)，2022年，8月28日

(1)將n個(gè)信源消息符號(hào)按其出現(xiàn)的概率大小依次排列,p(x1)≥p(x2)≥…≥p(xn)

(2)取兩個(gè)概率最小的字母分別配以0和1兩碼元,

并將這兩個(gè)概率相加作為一個(gè)新字母的概率,與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)。(3)重復(fù)步驟(2)的過程,直到最后兩個(gè)符號(hào)配以0

和1為止;(4)從最后一級(jí)開始,向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列。哈夫曼編碼第一百零四頁(yè)，共一百八十五頁(yè)，2022年，8月28日【例4.3-3】設(shè)信源共7個(gè)符號(hào)消息,其數(shù)學(xué)模型如下

哈夫曼編碼第一百零五頁(yè)，共一百八十五頁(yè)，2022年，8月28日0.110.200.190.180.170.15010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.39哈夫曼編碼第一百零六頁(yè)，共一百八十五頁(yè)，2022年，8月28日101100000101001100111該哈夫曼碼的平均碼長(zhǎng)為：信息傳輸速率：香農(nóng)編碼：?=0.813費(fèi)諾編碼：?=0.953

由此可見,哈夫曼碼的平均碼長(zhǎng)最小,消息傳輸速率最大,編碼效率最高。哈夫曼編碼第一百零七頁(yè)，共一百八十五頁(yè)，2022年，8月28日

1、每次對(duì)信源縮減時(shí),賦予信源最后兩個(gè)概率最小的符號(hào),用0和1是可以任意的,所以可以得到不同的哈夫曼碼,但不會(huì)影響碼長(zhǎng)。

2、對(duì)信源進(jìn)行縮減時(shí),兩個(gè)概率最小的符號(hào)合并后的概率與其它信源符號(hào)的概率相同時(shí),這兩者在縮減信源中進(jìn)行概率排序,其位置放置次序是可以任意的,故會(huì)得到不同的哈夫曼碼.注:此碼并非是唯一的.

原因是：

2點(diǎn),將影響碼字的長(zhǎng)度,一般將合并的概率放在上面,這樣可獲得較小的碼方差。101100000101001100111第一百零八頁(yè)，共一百八十五頁(yè)，2022年，8月28日哈夫曼編碼【例4.3-4】設(shè)有離散無記憶信源

用兩種方法編寫哈夫曼編碼10

0.20.40.20.2010.40.40.20.60.41A1010110000011000100011哈夫曼樹：第一百零九頁(yè)，共一百八十五頁(yè)，2022年，8月28日哈夫曼編碼哈夫曼樹：A01000010111100101011第一百一十頁(yè)，共一百八十五頁(yè)，2022年，8月28日哈夫曼樹：哈夫曼編碼第一百一十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日由計(jì)算可得方法1、方法2的平均碼長(zhǎng)相等編碼效率均為但兩種碼的質(zhì)量不完全相同哈夫曼編碼第一百一十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日

第二種方差小些。即：將新合并的等概率消息排列到上支路，將有利于縮短碼長(zhǎng)的方差，即編出的碼更接近于等長(zhǎng)碼。所以說第二種碼的質(zhì)量?jī)?yōu)于第一種碼的質(zhì)量。用碼差表示:方法1:方法2:哈夫曼編碼第一百一十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日上面討論了哈夫曼編碼的方法和一些性質(zhì)，在實(shí)際問題中真正應(yīng)用哈夫曼編碼方法時(shí)，還需進(jìn)一步研究有關(guān)誤差擴(kuò)散，速率匹配和概率匹配等問題。二、工程上注意的三個(gè)問題哈夫曼編碼第一百一十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日

哈夫曼碼是一類無失真信源最佳變長(zhǎng)碼,在研究這類無失真信源編碼時(shí)認(rèn)為信道傳輸是理想的,是不產(chǎn)生誤差的,然而實(shí)際信道中總是存在噪聲,噪聲引入必將要破壞變長(zhǎng)碼的結(jié)構(gòu),同時(shí)變長(zhǎng)碼是不加同步的碼,無法自動(dòng)清洗所產(chǎn)生的影響,所以必然要產(chǎn)生誤差的擴(kuò)散,就是說噪聲所影響的不僅是被干擾的碼元,而是一直擴(kuò)散下去,影響后面一系列碼元,以至在低信噪比下無法正常工作。1、誤差擴(kuò)散哈夫曼編碼第一百一十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日

目前對(duì)這類誤差擴(kuò)散還沒有特別有效的克服方法.在工程上,一般哈夫曼碼能適合于高信噪比的優(yōu)質(zhì)信道,如誤碼率﹤10-6.同時(shí)工程上還常常采用定期清洗方法,比如在文件和報(bào)紙傳真中采用按行清洗的方式,以犧牲編碼效率來達(dá)到限制誤差擴(kuò)散的目的.另一種方法是加檢錯(cuò)糾錯(cuò)碼。哈夫曼編碼第一百一十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日

由于絕大多數(shù)信源其消息是不等概率的，因而編成的變長(zhǎng)碼長(zhǎng)度也是不相等的,這必然導(dǎo)致信源輸出速率的變化,而在實(shí)際信道中傳送的信息率是固定不變的,就是說信源給出的是變速的,而信道傳送則是恒速的,因而信源與信道之間必然存在一個(gè)速率匹配問題。2、速率匹配哈夫曼編碼第一百一十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日在工程上一般采用緩沖存儲(chǔ)器方法，這個(gè)緩沖器起到類似水庫(kù)的作用，變速輸入，恒速輸出，緩沖器容量的選擇與信源統(tǒng)計(jì)特性，編碼方法，輸出速率相關(guān)，容量大浪費(fèi)設(shè)備，小達(dá)不到效果。經(jīng)概率運(yùn)算得存儲(chǔ)器容量

N表示在T秒內(nèi)N個(gè)信源符號(hào)輸出,σ為單符號(hào)方差。哈夫曼編碼第一百一十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日

變長(zhǎng)碼本身就是與信源統(tǒng)計(jì)特性相匹配的無失真信源編碼,因此信源統(tǒng)計(jì)特性的變化對(duì)變長(zhǎng)碼影響很大,主要體現(xiàn)在：

3、信源統(tǒng)計(jì)特性匹配

(1)與信源消息種類多少的關(guān)系;一般變長(zhǎng)碼更適合于大的消息集,而不適合小且概率分布相差很大的集合。（2）變長(zhǎng)碼是在信源概率特性已知的情況下實(shí)現(xiàn)統(tǒng)計(jì)匹配的。哈夫曼編碼第一百一十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日

下面,進(jìn)一步研究小消息集合如何實(shí)現(xiàn)統(tǒng)計(jì)匹配的變長(zhǎng)碼.

基本思想是擴(kuò)張信源,以實(shí)現(xiàn)統(tǒng)計(jì)匹配。哈夫曼編碼第一百二十頁(yè)，共一百八十五頁(yè)，2022年，8月28日從簡(jiǎn)單的例子入手：平均碼長(zhǎng)：信源消息概率編碼s1P(s1)=2/30s2P(s2)=1/31【例4.3-5】信源消息熵：哈夫曼編碼第一百二十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日編碼效率：

對(duì)上述信源進(jìn)行二次擴(kuò)展,即每次取兩個(gè)消息,可組成新的聯(lián)合信源。哈夫曼編碼第一百二十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日信源概率編碼碼字碼長(zhǎng)

s1s1

11

s1s2012

s2s10003

s2s200130110013/92/94/95/94/91對(duì)上述信源進(jìn)行二次擴(kuò)展,即每次取兩個(gè)消息,組成聯(lián)合信源哈夫曼編碼第一百二十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日

碼字碼長(zhǎng)

11

01200030013哈夫曼編碼第一百二十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日進(jìn)行三次擴(kuò)展：信源消息概率編碼Kis1s1s1012s1s1s20003s1s2s10013s1s2s21003s2s1s11103s2s1s21113s2s2s110104s2s2s210114哈夫曼編碼第一百二十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日哈夫曼編碼第一百二十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日

還可以一直擴(kuò)展下去,以不斷擴(kuò)大信源消息集,以達(dá)到逐步實(shí)現(xiàn)完全統(tǒng)計(jì)匹配的目的,但擴(kuò)展階數(shù)越高,設(shè)備越復(fù)雜,所以在工程上只能在效率和復(fù)雜性方面作一折中。哈夫曼編碼第一百二十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日

前面介紹的均為二進(jìn)制哈夫曼碼,很容易推廣到m進(jìn)制的情況,只是編碼過程中過程縮減信源時(shí),每次都是將m個(gè)概率最小的符號(hào)合并,并分別用０、１、…m-1碼符號(hào)表示,為了充分利用短碼,使哈夫曼的平均碼長(zhǎng)最短,必須使最后一個(gè)縮減源有m個(gè)信源符號(hào).三、m進(jìn)制哈夫曼碼哈夫曼編碼第一百二十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日故對(duì)m元哈夫曼編碼信源Ｓ符號(hào)個(gè)數(shù)q必須滿足q=(m-1)θ+m,θ表示信源縮減的次數(shù),如m＝２的二元碼,信源Ｓ的符號(hào)個(gè)數(shù)q必須滿足

q=θ+2若不滿足,用虛設(shè)方法,增補(bǔ)一些概率為信源符號(hào)滿足上式,這樣得到的m元哈夫曼碼一定是緊致碼。哈夫曼編碼第一百二十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日設(shè)離散無記憶信源碼符號(hào)集X=(0、1、2)【例4.3-6】設(shè)無記憶信源試構(gòu)造一種三進(jìn)制哈夫曼碼信源,哈夫曼編碼第一百三十頁(yè)，共一百八十五頁(yè)，2022年，8月28日0S930110.05S830100.05S72220.05S62210.05S52200.1S42020.1S32000.2S2110.4S1KiWi編碼過程P(si)信源符號(hào)0.20.10.10.10.050.050

120

120.40.20.20.10.10.40.40.20120121.0S9是增補(bǔ),令其概率為0,0.4q=(m-1)θ+m平均碼長(zhǎng)：哈夫曼編碼第一百三十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日0S930110.05S830100.05S72220.05S62210.05S52200.1S42020.1S32000.2S2110.4S1KiWi編碼過程P(si)信源符號(hào)0.20.10.10.10.050.050

120

120.40.20.20.10.10.40.40.20120121.00.4q=(m-1)θ+mA01201201200010011120022122碼樹:哈夫曼編碼第一百三十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日注:編碼效率、編碼信息率、編碼后信息傳輸率之間關(guān)系編碼信息率(信源符號(hào)的平均碼長(zhǎng))：編碼效率：編碼后信息傳輸率：碼字平均長(zhǎng)二進(jìn)制單個(gè)符號(hào)時(shí)L信源符號(hào)長(zhǎng)度三進(jìn)制單個(gè)符號(hào)時(shí)第一百三十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日4.4常用信源編碼方法簡(jiǎn)介指數(shù)學(xué)序列中連續(xù)出現(xiàn)相同符號(hào)的一段．游程編碼游程碼：

在二元序列中,只有兩種符號(hào),即“0”和“1”,這些符號(hào)可連續(xù)出現(xiàn),連“0”這一段稱為“0”游程,連“1”這一段稱為“1”游程.它們的長(zhǎng)度分別稱為游程長(zhǎng)度L(0)和L(1).“0”游程和“1”游程是總是交替出現(xiàn)的,如規(guī)定某二元序列是從“０”開始,第一個(gè)游程是“0”第二個(gè)是“1”第三個(gè)是“0”等等,對(duì)于隨機(jī)二元序列,各游程長(zhǎng)度是隨機(jī)變量.取值為……無限,將二元序列換成游程長(zhǎng)度序列.這種編碼是一一對(duì)應(yīng)的,是可逆的．游程編碼第一百三十四頁(yè)，共一百八十五頁(yè)，2022年，8月28日例:０００１０００１１１０１１１１１００００３若二元序列是從“０”起始,上面的游程序列很容易恢復(fù)成原來的二元序列.游程編碼仍是變長(zhǎng)碼,游程長(zhǎng)度越長(zhǎng),概率越?。?/p>

缺點(diǎn)：需大量的緩沖和優(yōu)質(zhì)的信道，只適用于二元序列，對(duì)于多元信源,一般不能直接利用游程編碼133154游程編碼第一百三十五頁(yè)，共一百八十五頁(yè)，2022年，8月28日4-1以下以碼字集合的形式給出5種不同的編碼，第一個(gè)碼的符號(hào)集合為{a,b,c},其他4個(gè)碼都是二進(jìn)制碼。{aa,ac,b,cc,abc}{000,10,00,11}{100,101,0,11}{01,100,011,00,111,1010,1011,1101}{01,111,011,00,010,110}對(duì)于上面列出的5種編碼，分別回答下述問題：⑴此碼的平均碼長(zhǎng)是多少？⑵畫出此碼的樹圖，并判斷此碼是否是即時(shí)碼？⑶此碼的碼長(zhǎng)分布是否滿足克勞夫特不等式，并判斷此碼是否是唯一可譯碼？練習(xí)題第一百三十六頁(yè)，共一百八十五頁(yè)，2022年，8月28日4-5某信源有8個(gè)符號(hào)，概率分別為1/2,1/4,1/8,1/16,1/32,1/64,1/128,1/128，編成這樣的碼：000，001，010，011，100，101，110，111.計(jì)算：⑴信源的符號(hào)熵H（S）；⑵出現(xiàn)一個(gè)“1”或“0”的概率；⑶這種碼的編碼效率；⑷相應(yīng)的香農(nóng)碼和費(fèi)諾碼；⑸相應(yīng)的香農(nóng)碼和費(fèi)諾碼的編碼效率。練習(xí)題第一百三十七頁(yè)，共一百八十五頁(yè)，2022年，8月28日上次課內(nèi)容4.3.2費(fèi)諾編碼方法4.3.3哈夫曼編碼方法4.3.4游程(Run-length)編碼第一百三十八頁(yè)，共一百八十五頁(yè)，2022年，8月28日編碼步驟:

1.

將信源消息符號(hào)按其出現(xiàn)概率大小依次排列：

p(x1)≥p(x2)….p(xn)。

2.將依次排列的信源符號(hào)按概率植分兩大組,并對(duì)各組賦予一個(gè)二進(jìn)制元碼0、1。一、費(fèi)諾（Fano）編碼（簡(jiǎn)稱費(fèi)諾碼）屬于概率匹配編碼.不是最佳編碼

3.將每一大組的信源符號(hào)進(jìn)一步分組,使劃分后的兩組概率和近于相同并又賦兩組0,1。

4.如此重復(fù),至兩組只剩下一個(gè)信源符號(hào)為止。

5.信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼.復(fù)習(xí)第一百三十九頁(yè)，共一百八十五頁(yè)，2022年，8月28日

(1)將n個(gè)信源消息符號(hào)按其出現(xiàn)的概率大小依次排列,p(x1)≥p(x2)≥…≥p(xn)

(2)取兩個(gè)概率最小的字母分別配以0和1兩碼元,

并將這兩個(gè)概率相加作為一個(gè)新字母的概率,與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)。(3)重復(fù)步驟(2)的過程,直到最后兩個(gè)符號(hào)配以0

和1為止;(4)從最后一級(jí)開始,向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列。二、哈夫曼編碼步驟復(fù)習(xí)第一百四十頁(yè)，共一百八十五頁(yè)，2022年，8月28日三、工程上注意的三個(gè)問題1、誤差擴(kuò)散2、速率匹配3、信源統(tǒng)計(jì)特性匹配四、游程碼：指數(shù)學(xué)序列中連續(xù)出現(xiàn)相同符號(hào)的一段。復(fù)習(xí)第一百四十一頁(yè)，共一百八十五頁(yè)，2022年，8月28日

本次課內(nèi)容4.3.5算術(shù)編碼4.4*限失真信源編碼定理4.5*限失真信源編碼方法第一百四十二頁(yè)，共一百八十五頁(yè)，2022年，8月28日4.3.5算術(shù)編碼

算術(shù)編碼不同于哈夫曼碼,是非分組碼,是運(yùn)用復(fù)雜模型來使得優(yōu)良的壓縮性成為可能的一種壓縮技術(shù),在某種意義上講算術(shù)編碼是最優(yōu)編碼,但算術(shù)編碼掌握有些困難,但目前發(fā)展很快,工程應(yīng)用較多.4.3.5算術(shù)編碼第一百四十三頁(yè)，共一百八十五頁(yè)，2022年，8月28日

既，從全序列出發(fā),將各信源序列的概率映射到[0,1]區(qū)間上,使每個(gè)序列對(duì)應(yīng)這區(qū)間內(nèi)的一點(diǎn),也就是一