第四章無(wú)失真信源編碼第1頁(yè)，共113頁(yè)，2023年，2月20日，星期四無(wú)失真信源編碼無(wú)失真編碼概述定長(zhǎng)信源編碼變長(zhǎng)信源編碼實(shí)用的無(wú)失真信源編碼方法舉例第2頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.1無(wú)失真編碼概述－1離散、無(wú)失真、無(wú)記憶信源編碼的一般模型：

總組合數(shù)：總碼組合數(shù)：入出信源編碼取值于同一個(gè)符號(hào)集，符號(hào)集大小為n取值于同一個(gè)符號(hào)集，符號(hào)集大小為m第3頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.1無(wú)失真編碼概述－2問(wèn)題：能否進(jìn)行無(wú)失真編碼?怎樣進(jìn)行無(wú)失真編碼?

(前提：不考慮信源統(tǒng)計(jì)特性)應(yīng)滿足條件：無(wú)失真條件變換

相互矛盾！

結(jié)論：①當(dāng)n=m

時(shí)，K≥L

不有效。②當(dāng)K=L時(shí)，m≥n，亦不滿足有效性

解決辦法：引入信源統(tǒng)計(jì)特性。無(wú)失真：有效：第4頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.1無(wú)失真編碼概述－3考察無(wú)失真條件：等概條件下的消息符號(hào)熵等概條件下的碼字符號(hào)熵考慮信源的實(shí)際統(tǒng)計(jì)特性（非等概），實(shí)際消息熵為：代入無(wú)失真條件得：結(jié)論：即使m=n,只要就有可能實(shí)現(xiàn)K<L。

即無(wú)失真與有效性同時(shí)滿足。

具體實(shí)現(xiàn)方法：定長(zhǎng)與變長(zhǎng)編碼第5頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－1-描述定長(zhǎng)（等長(zhǎng)）碼信源編碼定理：

對(duì)離散，無(wú)記憶、平穩(wěn)、遍歷信源其符號(hào)序列：S=(S1S2…..SL)，可用K個(gè)符號(hào)C=(C1C2…CK)進(jìn)行等長(zhǎng)編碼，對(duì)任意ε>0,δ>0，只要滿足：

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

反之，當(dāng)

時(shí)，譯碼一定出錯(cuò)。

解釋：

定長(zhǎng)編碼定理給出了信源進(jìn)行等長(zhǎng)編碼所需碼長(zhǎng)的理論極限值。第6頁(yè)，共113頁(yè)，2023年，2月20日，星期四結(jié)論：對(duì)信源進(jìn)行二元等長(zhǎng)編碼時(shí)，每個(gè)信源符號(hào)所需碼長(zhǎng)的極限值為

結(jié)論：對(duì)于唯一可譯碼，每個(gè)信源符號(hào)至少需要用個(gè)碼符號(hào)來(lái)變換?！?.2定長(zhǎng)編碼定理－2-進(jìn)一步理解若要求所得的等長(zhǎng)碼是唯一可譯的，則必須：若L＝1，則：當(dāng)采用二元碼編碼時(shí)，m＝2，則：第7頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－2-進(jìn)一步理解每個(gè)碼字（碼序列）所能攜帶的平均信息量每個(gè)源序列所包含的平均不確定性。即：信源序列攜帶的信息量

等長(zhǎng)有效性的無(wú)失真編碼的條件：碼長(zhǎng)下限：

為實(shí)現(xiàn)有效：誤碼率任意小的方向：?結(jié)論：只要碼字能夠攜帶的信息量大于信源序列攜帶的信息量，總可以實(shí)現(xiàn)幾乎無(wú)失真編碼

考慮信源統(tǒng)計(jì)特性第8頁(yè)，共113頁(yè)，2023年，2月20日，星期四討論：第三章：在考慮符號(hào)出現(xiàn)的概率和符號(hào)間相關(guān)性前提下,每個(gè)英文符號(hào)平均攜帶的信息量是1.4bit/符號(hào)<<5bit/碼符號(hào)?！?.2定長(zhǎng)編碼定理－3-舉例例1：英文電報(bào)有32個(gè)符號(hào)（26＋6），即n=32，若m=2，L＝1（即對(duì)信源的逐個(gè)符號(hào)進(jìn)行二元編碼），則：bit解釋：每個(gè)英文電報(bào)符號(hào)至少需要用5位二元符號(hào)編碼（每位二元符號(hào)可以攜帶1bit信息，即每個(gè)英文電報(bào)符號(hào)用了可以攜帶

5bit信息的碼符號(hào)即5位二元碼表示）問(wèn)題：如何提高效率？如何體現(xiàn)有效性？結(jié)論：若不考慮信源統(tǒng)計(jì)特性等長(zhǎng)編碼效率極低!第9頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－4-進(jìn)一步理解解決方法：字母?jìng)€(gè)數(shù)為n，字母之間相關(guān)長(zhǎng)度為L(zhǎng)的英文信源，其可能的字母序列總數(shù)為；但其中大部分字母序列是無(wú)意義的字母組合，而且隨著L的增加，這種無(wú)意義序列的總數(shù)越來(lái)越大。進(jìn)行聯(lián)合編碼，即對(duì)字母序列編碼，且只對(duì)哪些有意義的字母序列編碼，即需編碼的字母序列的總數(shù)<<,則平均每個(gè)信源符號(hào)所需的碼符號(hào)個(gè)數(shù)可以大大減少，從而提高了傳輸效率?？疾欤悍椒ǎ?jiǎn)栴}：會(huì)引入一定的誤差??！但當(dāng)L足夠長(zhǎng)后，誤差可以任意小。第10頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－5－證明考察離散、隨機(jī)序列信源的統(tǒng)計(jì)特性－－漸進(jìn)等分割性（AEP）AEP描述：

漸進(jìn)等分割定理：（熵定理，遍歷性定理）設(shè)是離散無(wú)記憶信源輸出的一個(gè)特定序列，則任給和，總可以找到一個(gè)整數(shù)，使當(dāng)時(shí)，有：引入：漸進(jìn)等分割性（AEP:AsymptoticEquipartitionProperty

）特定序列的平均符號(hào)自信息隨機(jī)矢量的平均符號(hào)熵第11頁(yè)，共113頁(yè)，2023年，2月20日，星期四任何一個(gè)離散隨機(jī)序列信源當(dāng)序列長(zhǎng)度L→∞時(shí),信源序列會(huì)產(chǎn)生兩極分化.小概率事件集合與大概率事件集合,即nL=∪對(duì)于有性質(zhì):

對(duì)于有性質(zhì):

由此可見(jiàn)，信源編碼只需對(duì)信源中少數(shù)落入典型大概率事件的集合的符號(hào)進(jìn)行編碼即可。而對(duì)大多數(shù)屬于非典型小概率事件集合中的信源符號(hào)無(wú)需編碼.§4.2定長(zhǎng)編碼定理－6－AEP物理意義信源序列集合①②信源熵大概率事件熵③第12頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－7－AEP證明集合和中的序列分別稱為典型序列和非典型序列表示中所有典型序列的集合表示集合中序列的個(gè)數(shù)可以證明：對(duì)于任意小的正數(shù)，，當(dāng)L足夠大時(shí)，第13頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－7－AEP證明還可以證明：對(duì)于任意小的正數(shù)，，當(dāng)L足夠大時(shí)，表示序列出現(xiàn)的概率由切比雪夫不等式可得：表示S中每個(gè)符號(hào)攜帶的信息量的方差第14頁(yè)，共113頁(yè)，2023年，2月20日，星期四第15頁(yè)，共113頁(yè)，2023年，2月20日，星期四例2p(1)=p,p(0)=q,統(tǒng)計(jì)獨(dú)立L長(zhǎng)的序列:

當(dāng)L＝8時(shí)，序列11000101和序列011100101的概率為和顯然，這兩個(gè)序列不等概,當(dāng)L→時(shí)，有一些序列1出現(xiàn)的次數(shù)接近Lp，這些序列的概率為且這些序列近似等概分布?！?.2定長(zhǎng)編碼定理－8－AEP舉例L長(zhǎng)的序列，對(duì)于任意小的正數(shù)滿足式的序列稱為典型序列即：典型序列集是哪些平均自信息任意小地接近信源熵的N長(zhǎng)序列的集合第16頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－9-AEP應(yīng)用AEP結(jié)論：當(dāng)L足夠大時(shí)，所有典型序列出現(xiàn)的概率近似相等，即典型序列為漸進(jìn)等概序列可粗略認(rèn)為典型序列出現(xiàn)的概率為所有典型序列的概率和接近為1，即典型序列總數(shù)占信源序列的總數(shù)第17頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－9-AEP應(yīng)用AEP應(yīng)用：提出、證明都是基于離散無(wú)記憶序列信源平穩(wěn)遍歷信源有類似結(jié)果體現(xiàn)信源統(tǒng)計(jì)特性用以證明定長(zhǎng)編碼定理第18頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－10－證明定長(zhǎng)編碼定理證明思路：將取自S，長(zhǎng)為L(zhǎng)的信源符號(hào)序列分為集合和

幾個(gè)概念：

編碼信息率：編碼后對(duì)應(yīng)于每個(gè)信源符號(hào)平均能載荷的最大信息量

編碼效率：編碼前后平均每個(gè)信源符號(hào)能載荷的最大信息量之比只對(duì)集合中的序列進(jìn)行一一對(duì)應(yīng)的等長(zhǎng)編碼此時(shí)的誤差為，計(jì)算誤差證明當(dāng)，且(K/L)logm≥H(S)+ε

時(shí)，第19頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－11（物理意義）結(jié)論：可推廣至離散、非平穩(wěn)無(wú)記憶信源和有記憶信源（即H(S)=H∞(S)）情況只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實(shí)現(xiàn)幾乎無(wú)失真編碼二元碼時(shí)，m＝2：最佳等長(zhǎng)碼時(shí)：第20頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－12（實(shí)際應(yīng)用問(wèn)題）編譯碼同步問(wèn)題問(wèn)題：如何使譯碼端知道碼字起點(diǎn)解決辦法：1、每個(gè)碼字加短同步前綴

2、每若干碼字加較長(zhǎng)同步前綴

分組長(zhǎng)度與編譯碼復(fù)雜性、編譯碼延時(shí)等的關(guān)系問(wèn)題：要實(shí)現(xiàn)有效，源序列分組很長(zhǎng)，使得編譯碼復(fù)雜性和延時(shí)增加解決辦法：目前沒(méi)有理想的解決辦法

定長(zhǎng)信源編碼的理論意義遠(yuǎn)大于其實(shí)用價(jià)值第21頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.2定長(zhǎng)編碼定理－13（舉例)例3：設(shè)有一簡(jiǎn)單離散信源：L=1,n=2

對(duì)其進(jìn)行近似于無(wú)失真的等長(zhǎng)編碼，若要求其編碼效率為96%，差錯(cuò)率低于10-5，試求符號(hào)聯(lián)合編碼長(zhǎng)度L=？解：由編碼效率：而：則：且：則：結(jié)論：可見(jiàn),需要4100萬(wàn)個(gè)信源符號(hào)聯(lián)合編碼,才能達(dá)到上述要求,這顯然是不現(xiàn)實(shí)的.一般來(lái)說(shuō)：當(dāng)L有限時(shí)，高傳輸效率的等長(zhǎng)碼往往要引入一定的失真和錯(cuò)誤，它不能象變長(zhǎng)編碼那樣可以實(shí)現(xiàn)真正的無(wú)失真編碼第22頁(yè)，共113頁(yè)，2023年，2月20日，星期四改變信源定長(zhǎng)編碼無(wú)失真信源編碼實(shí)現(xiàn)方法一無(wú)失真信源編碼實(shí)現(xiàn)方法二適應(yīng)信源變長(zhǎng)編碼大概率短碼；小概率長(zhǎng)碼第23頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-1幾個(gè)碼類的概念非奇異碼（單義碼）唯一可譯碼前綴碼（即時(shí)碼、非延長(zhǎng)碼、異前置碼）最佳碼（緊致碼）Kraft定理－－－即時(shí)碼碼長(zhǎng)必須滿足的條件唯一可譯碼存在定理變長(zhǎng)編碼定理（香農(nóng)第一定理）第24頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-2(幾個(gè)碼類的概念)非奇異碼（單義碼）：每一個(gè)碼字僅對(duì)應(yīng)信源中的一個(gè)信源符號(hào)（序列）。編碼是單義的。反之為奇異碼或非單義碼。第25頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-3(幾個(gè)碼類的概念)唯一可譯碼編碼單義、譯碼單義對(duì)任何一個(gè)有限長(zhǎng)度的信源字母序列，如果編碼得到的碼字母序列不與其他任何信源字母序列所對(duì)應(yīng)的碼字母序列相同。非奇異碼=唯一可譯碼？第26頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-4(幾個(gè)碼類的概念)前綴碼是唯一可譯碼中的一類在一個(gè)變長(zhǎng)碼中，沒(méi)有任何一個(gè)碼字是其他碼字的前綴。譯碼時(shí)無(wú)需參考后續(xù)的碼符號(hào)就能立即作出判斷，進(jìn)行無(wú)延時(shí)譯碼。又稱即時(shí)碼、非延時(shí)碼例如逗點(diǎn)碼：1，01，001，0001第27頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-5(幾個(gè)碼類的概念)最佳碼唯一可譯碼的一類其平均碼長(zhǎng)小于其他唯一可譯碼的平均長(zhǎng)度所有的碼非奇異碼唯一可譯碼前綴碼最佳碼第28頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-6（幾種類型的信源編碼舉例）

例4：信源概率pi

編碼Ⅰ編碼Ⅱ編碼Ⅲ編碼Ⅳ編碼ⅤU11/2000000U21/401010110U31/810100011110U41/81110110111111定長(zhǎng)唯一可譯奇異非奇異前綴唯一可譯第29頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-7(Kraft定理)引出碼樹(shù)－－構(gòu)造即時(shí)碼方法Kraft定理描述－－即時(shí)碼碼長(zhǎng)須滿足的條件Kraft定理證明－－略第30頁(yè)，共113頁(yè)，2023年，2月20日，星期四

實(shí)時(shí)唯一可譯、可分離A0B10C110D1110E11110ABABBBBBAACDDED100010111010111101010111001001101110要求：須嚴(yán)格同步第31頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-8(Kraft定理引出)問(wèn)題：尋求實(shí)時(shí)唯一可譯碼方法：研究實(shí)時(shí)唯一可譯碼的碼字可分離條件簡(jiǎn)單信源：“碼樹(shù)”概念（直觀）一般信源：通過(guò)Kraft定理給出實(shí)時(shí)唯一可譯碼（前綴碼）存在的條件第32頁(yè)，共113頁(yè)，2023年，2月20日，星期四碼樹(shù)－－變長(zhǎng)碼的樹(shù)圖表示將變長(zhǎng)碼與碼樹(shù)建立“一一對(duì)應(yīng)”關(guān)系：樹(shù)根碼字起點(diǎn)樹(shù)枝數(shù)碼的進(jìn)制數(shù)節(jié)點(diǎn)碼字或碼字的一部分終止節(jié)點(diǎn)碼字節(jié)數(shù)碼長(zhǎng)非滿樹(shù)變長(zhǎng)碼滿樹(shù)等長(zhǎng)碼

第33頁(yè)，共113頁(yè)，2023年，2月20日，星期四利用碼樹(shù)構(gòu)造前綴碼源符號(hào)概率前綴碼s1s2s3s4011100010110111s10.04s4s30.160.64s20.16第34頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-9(Kraft定理)問(wèn)題：比較簡(jiǎn)單信源，碼樹(shù)方法可直接且直觀構(gòu)造前綴碼較復(fù)雜信源，直接畫碼樹(shù)復(fù)雜且困難解決方法：為便于分析，特別對(duì)含有很多符號(hào)種類的復(fù)雜信源，尋找一種與上述“樹(shù)圖”等效的解析式表達(dá)式----Kraft不等式。結(jié)論：

Kraft定理給出碼字可分離或前綴碼存在的充要條件第35頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-10(Kraft定理)kraft定理：長(zhǎng)度為Ki（i=1,2,…,n）的m

（碼字母表長(zhǎng)度）進(jìn)制前綴碼存在的充要條件為：證明：略物理意義：給定信源個(gè)數(shù)N和碼字母數(shù)m，只要允許碼字長(zhǎng)度可以足夠長(zhǎng)，就總可以滿足Kraft不等式，從而得到前綴碼。只要適當(dāng)選取碼長(zhǎng)，碼字一定可以即時(shí)分離。第36頁(yè)，共113頁(yè)，2023年，2月20日，星期四(a)10(0.8)(0.2)(b)10(0.2)(0.64)(0.16)10(c)10(0.2)(0.512)(0.16)10(0.128)10例5：32104個(gè)葉子:代表序列

1,01,001

和

000是前綴碼

消息符號(hào)概率碼字序號(hào)編碼a0.201b0.16101c0.1282001d0.5123000第37頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)信源編碼-11(唯一可譯碼定理)Kraft不等式給出的限制也是所有唯一可譯碼都必須滿足的。定理描述：任何唯一可譯碼均滿足Kraft不等式。結(jié)論：唯一可譯碼一定滿足kraft不等式滿足kraft不等式的碼不一定是唯一可譯碼，但一定存在至少一種唯一可譯碼對(duì)任何唯一可譯碼均可在不改變碼字長(zhǎng)度的條件下得到相應(yīng)的前綴碼第38頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)編碼定理－12問(wèn)題：對(duì)于已知信源S可用碼符號(hào)集X進(jìn)行變長(zhǎng)編碼，而且對(duì)同一信源編成同一碼符號(hào)的前綴碼或惟一可譯碼可有許多種。究竟哪一種最好呢?從高速度傳輸信息的觀點(diǎn)來(lái)考慮，當(dāng)然希望選擇由短的碼符號(hào)組成的碼字，就是用碼長(zhǎng)作為選擇準(zhǔn)則。引入：碼的平均長(zhǎng)度。離散無(wú)記憶平穩(wěn)信源

信源熵率為，碼字個(gè)數(shù)為M，信源符號(hào)對(duì)應(yīng)碼長(zhǎng)分別為：ki,i=1,2,….n則前綴碼平均碼長(zhǎng)：第39頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)編碼定理－13定理：離散無(wú)記憶平穩(wěn)信源S，其熵為，并有碼符號(hào)集C={c1,…,cm}。對(duì)信源S進(jìn)行編碼,總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使信源S中每個(gè)信源符號(hào)所需的平均碼長(zhǎng)滿足:

另一方面,必可以找到前綴碼，使其平均碼長(zhǎng)滿足

對(duì)于給定的信源和碼符號(hào)集，若有一個(gè)唯一可譯碼，其平均長(zhǎng)度小于所有其他唯一可譯碼，則稱這種碼為緊致碼或最佳碼。

唯一可譯碼存在性緊致碼的存在性第40頁(yè)，共113頁(yè)，2023年，2月20日，星期四證明：第41頁(yè)，共113頁(yè)，2023年，2月20日，星期四Jensen不等式第42頁(yè)，共113頁(yè)，2023年，2月20日，星期四平均碼長(zhǎng)=下限值第43頁(yè)，共113頁(yè)，2023年，2月20日，星期四第44頁(yè)，共113頁(yè)，2023年，2月20日，星期四由右邊不等式第45頁(yè)，共113頁(yè)，2023年，2月20日，星期四

香農(nóng)第一定理（變長(zhǎng)無(wú)失真信源編碼定理）：設(shè)離散無(wú)記憶信源的熵為H(S)，它的N次擴(kuò)展信源為，對(duì)擴(kuò)展信源進(jìn)行編碼?？偪梢哉业揭环N編碼方法，構(gòu)成唯一可譯碼，使平均碼長(zhǎng)滿足：其中

當(dāng)時(shí)，有第46頁(yè)，共113頁(yè)，2023年，2月20日，星期四

當(dāng)時(shí)，有代表平均到每個(gè)信源符號(hào)所需的碼長(zhǎng)

當(dāng)時(shí)，每個(gè)碼符號(hào)能夠攜帶的信息量為：第47頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)編碼定理－14物理意義：又稱無(wú)噪信道編碼定理編碼后的碼符號(hào)信源盡可能為等概分布，使每個(gè)碼符號(hào)平均所含的信息量達(dá)到最大要做到無(wú)失真編碼，變換每個(gè)信源符號(hào)平均所需最少的m元碼元數(shù)就是信源的熵率（以m進(jìn)制信息量單位測(cè)度，對(duì)應(yīng)離散無(wú)記憶信源）信源的熵率是描述每個(gè)信源符號(hào)平均所需最少的比特?cái)?shù)定理說(shuō)明：是存在性定理－－具有理論指導(dǎo)意義是構(gòu)造性定理－－設(shè)計(jì)出多種具體編碼方法第48頁(yè)，共113頁(yè)，2023年，2月20日，星期四構(gòu)造：1、擴(kuò)展信源至2、取3、則：k(s)滿足kraft不等式，存在前綴碼4、用樹(shù)圖法構(gòu)造前綴碼－香農(nóng)編碼第49頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)編碼定理－15－編碼效率變長(zhǎng)碼編碼效率：衡量各種編碼方法的優(yōu)略，判斷是否最佳碼。編碼前平均每個(gè)信源符號(hào)攜帶的信息量為：編碼后平均每個(gè)信源符號(hào)攜帶的最大的信息量為：定義變長(zhǎng)碼編碼效率為：另一種理解：最佳碼（極限時(shí)）每個(gè)信源符號(hào)的平均碼長(zhǎng)為：

某一方法得到的每個(gè)信源符號(hào)的平均碼長(zhǎng)為：定義變長(zhǎng)碼編碼效率為：第50頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.3變長(zhǎng)編碼定理－16－編碼效率比較：定長(zhǎng)編碼的編碼效率：變長(zhǎng)編碼的編碼效率：注意到：

是指平均到每個(gè)信源符號(hào)所需的碼長(zhǎng)，而也是平均到每個(gè)信源符號(hào)的碼長(zhǎng)，所以它們是一致的，均表示無(wú)失真信源編碼的效率。第51頁(yè)，共113頁(yè)，2023年，2月20日，星期四例6：一離散無(wú)記憶信源其熵為：用二元符號(hào)（0，1；m=2）構(gòu)造一個(gè)前綴碼：此時(shí)每個(gè)信源符號(hào)平均碼長(zhǎng)為：編碼效率為：為提高編碼效率，對(duì)S的2次擴(kuò)展信源進(jìn)行2維聯(lián)合編碼：第52頁(yè)，共113頁(yè)，2023年，2月20日，星期四構(gòu)造一個(gè)擴(kuò)展信源S2的前綴碼：前綴碼s1s19/16

0s1s23/1610s2s13/16110s2s21/16111此時(shí)平均碼長(zhǎng)為：此時(shí)信源S中每個(gè)符號(hào)對(duì)應(yīng)的平均碼長(zhǎng)為：編碼效率為：同樣可得：第53頁(yè)，共113頁(yè)，2023年，2月20日，星期四定長(zhǎng)編碼與變長(zhǎng)編碼效率比較：例6與例3相比：同一個(gè)信源，當(dāng)要求編碼效率達(dá)到96％時(shí)，

等長(zhǎng)碼需要4100萬(wàn)個(gè)信源符號(hào)聯(lián)合編碼；

變長(zhǎng)碼只需2個(gè)符號(hào)（二次擴(kuò)展信源）聯(lián)合編碼；結(jié)論：采用變長(zhǎng)編碼，L不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實(shí)現(xiàn)無(wú)失真編碼。且隨著L的增大，編碼效率越來(lái)越接近于1。第54頁(yè)，共113頁(yè)，2023年，2月20日，星期四無(wú)失真信源編碼等長(zhǎng)編碼變長(zhǎng)編碼完全無(wú)失真效率差較好的效率、一定的誤差可實(shí)現(xiàn)、有實(shí)用難實(shí)現(xiàn)、無(wú)實(shí)用無(wú)失真、較好的效率可實(shí)現(xiàn)、有實(shí)用總結(jié)：第55頁(yè)，共113頁(yè)，2023年，2月20日，星期四定長(zhǎng)編碼定理－近似無(wú)失真等長(zhǎng)編碼的條件有效性、無(wú)失真性無(wú)法兼得考察信源統(tǒng)計(jì)特性利用信源序列的AEP特性定長(zhǎng)編碼定理研究思路變長(zhǎng)編碼定理研究思路無(wú)失真－唯一可譯碼工程可實(shí)現(xiàn)－前綴碼碼樹(shù)－構(gòu)造簡(jiǎn)單前綴碼KRAFT不等式－前綴碼存在條件香農(nóng)定理－最佳碼存在條件第56頁(yè)，共113頁(yè)，2023年，2月20日，星期四定長(zhǎng)編碼定理變長(zhǎng)編碼定理1、存在碼長(zhǎng)為K的定長(zhǎng)編碼方法2、L足夠大時(shí)，幾乎無(wú)失真條件1、存在無(wú)失真的變長(zhǎng)編碼方法2、最佳碼的碼長(zhǎng)上界：條件結(jié)論結(jié)論第57頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.4最優(yōu)編碼定理1:對(duì)每一給定的離散無(wú)記憶信源,存在一個(gè)最優(yōu)的二元前綴碼.這個(gè)碼中最少發(fā)生的兩個(gè)碼字必具有相同的長(zhǎng)度,且碼中相同長(zhǎng)度的碼字有兩個(gè)或兩個(gè)以上時(shí),其中必有兩個(gè)碼字的差別只在最后一位.第58頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.4最優(yōu)編碼定理說(shuō)明沒(méi)給出編碼全過(guò)程最優(yōu)二元前綴碼，兩個(gè)最小概率信源字母對(duì)應(yīng)的碼字等長(zhǎng)，且差別在最后一位。兩個(gè)最小概率信源字母對(duì)應(yīng)的碼字相同部分的最后一位可以通過(guò)縮減信源的方法得到。縮減方法：原信源縮減信源第59頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.4最優(yōu)編碼定理2:設(shè)C’是某信源經(jīng)縮減后所得的縮減信源的最優(yōu)前綴碼，將C’中由原信源中的最小概率的兩個(gè)字母縮減得到的字母所對(duì)應(yīng)的碼字后各加0和1,作為原信源的最小概率的兩個(gè)碼字,而其余碼字不變,則這樣得到的碼C對(duì)原信源也是最優(yōu)的.第60頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.5實(shí)用的無(wú)失真信源編碼方法舉例香農(nóng)（Shannon)碼費(fèi)諾（Fano）碼霍夫曼（Huffman）編碼編碼方法特點(diǎn)應(yīng)用問(wèn)題第61頁(yè)，共113頁(yè)，2023年，2月20日，星期四思路：平均碼長(zhǎng)與信源特性相匹配適用數(shù)據(jù)源：離散無(wú)記憶信源－香農(nóng)編碼、費(fèi)諾編碼、霍夫曼編碼§4.5實(shí)用的無(wú)失真信源編碼方法舉例第62頁(yè)，共113頁(yè)，2023年，2月20日，星期四－香農(nóng)編碼步驟以二進(jìn)制香農(nóng)碼為例：排序?qū)⑿旁捶?hào)按概率從大到小的順序排列，為方便起見(jiàn)，令

p(x1)≥p(x2)≥…≥p(xn)概率累加

令p(x0)=0，設(shè)i=0,1,…n-1,用pa(xj)，j=i+1表示前i個(gè)碼字的累加概率，則：確定碼長(zhǎng)求滿足下列不等式的整數(shù)ki，并令ki為第i個(gè)碼字的長(zhǎng)度－log2

p(xi)≤ki<1－log2

p(xi)編碼將pa(xj)用二進(jìn)制表示，并取小數(shù)點(diǎn)后ki

位作為符號(hào)xi的編碼。§4.5實(shí)用的無(wú)失真信源編碼方法舉例第63頁(yè)，共113頁(yè)，2023年，2月20日，星期四[例7]有一單符號(hào)離散無(wú)記憶信源對(duì)該信源編二進(jìn)制香農(nóng)碼。其編碼過(guò)程如下表所示。香農(nóng)編碼舉例－1第64頁(yè)，共113頁(yè)，2023年，2月20日，星期四二進(jìn)制香農(nóng)編碼xi

p(xi)

pa(xj)

pa(xj)2

ki

碼字x10.25x20.25x30.20x40.15x50.10x60.050.250.000.500.700.850.95(0.000)2(0.010)2(0.100)2(0.101)2(0.1101)2(0.11110)22233450001100101110111110第65頁(yè)，共113頁(yè)，2023年，2月20日，星期四編碼效率離散無(wú)記憶信源的熵：平均碼長(zhǎng)：采用香農(nóng)編碼后的信息率：編碼效率：結(jié)論：

1、香農(nóng)編碼對(duì)信源進(jìn)行了壓縮。若對(duì)該信源采用等長(zhǎng)編碼，要做到無(wú)失真譯碼，每個(gè)符號(hào)至少要用3個(gè)比特表示。

2、編碼效率并不是很高。香農(nóng)編碼舉例－2第66頁(yè)，共113頁(yè)，2023年，2月20日，星期四

以二進(jìn)制費(fèi)諾編碼為例，編碼步驟如下：排序：將概率按從大到小的順序排列，令p(x1)≥p(x2)≥…≥p(xn)分組：按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。編碼：給每一組分配一位碼元。重復(fù)：將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。－費(fèi)諾編碼步驟§4.5實(shí)用的無(wú)失真信源編碼方法舉例第67頁(yè)，共113頁(yè)，2023年，2月20日，星期四[例8]設(shè)有一單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。編碼過(guò)程如下表所示。費(fèi)諾編碼舉例－1010101010100011011011101111222344第68頁(yè)，共113頁(yè)，2023年，2月20日，星期四編碼效率該信源的熵:平均碼長(zhǎng):編碼效率:結(jié)論：費(fèi)諾碼比較適合于每次分組概率都很接近的信源。特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。費(fèi)諾編碼舉例－3第69頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.5實(shí)用的無(wú)失真信源編碼方法舉例－霍夫曼編碼編碼規(guī)則：

1)排序：將信源消息U按概率大小排序（由大至小）p(x1)≥p(x2)≥…≥p(xn)2)定規(guī)則并編碼：從最小概率的兩個(gè)符號(hào)開(kāi)始編碼，并賦予一定規(guī)則，如下支路小概率為“1”，上支路大概率為“0”。若兩支路概率相等，仍為下支為“1”上支為“0”。3)概率合并：將已編碼兩支路概率合并，重新排隊(duì)，編碼。4)重復(fù)：重復(fù)步驟3）直至合并概率歸一時(shí)為止。5)確定最終碼子：從概率歸一端沿樹(shù)圖路線逆行至對(duì)應(yīng)消息編碼。第70頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：0101011001010110第71頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：010101100101011011第72頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：010101100101011011000第73頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：010101100101011011000001第74頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：010101100101011011000001010第75頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：0101011001010110110000010100110第76頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：010101100101011011000001010011001110第77頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－1例9：01010110010101101100000101001100111001111第78頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－2特點(diǎn)：編碼不是唯一的保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，而且短碼得到充分利用每次縮減信源的最后二個(gè)碼字總是最后一位碼元不同，前面各位碼元相同（二元碼情況）每次縮減信源的最長(zhǎng)兩個(gè)碼字具有相同碼長(zhǎng)后三個(gè)特點(diǎn)保證了所得到的huffman碼一定是最佳碼（證明見(jiàn)李亦農(nóng)《信息論基礎(chǔ)教程》2005年1月第一版p114）第79頁(yè)，共113頁(yè)，2023年，2月20日，星期四每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)ki不變，平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別；縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度ki也不盡相同?；舴蚵幋a舉例－3第80頁(yè)，共113頁(yè)，2023年，2月20日，星期四例[10]單符號(hào)離散無(wú)記憶信源用兩種不同的方法對(duì)其編二進(jìn)制哈夫曼碼。方法一：合并后的新符號(hào)排在其它相同概率符號(hào)的后面。霍夫曼編碼舉例－4對(duì)應(yīng)該圖畫出樹(shù)圖第81頁(yè)，共113頁(yè)，2023年，2月20日，星期四

霍夫曼編碼舉例－6xiP(xi)碼字碼長(zhǎng)x10.411x20.2012x30.20003x40.100104x50.100114第82頁(yè)，共113頁(yè)，2023年，2月20日，星期四方法二：合并后的新符號(hào)排在其它相同概率符號(hào)的前面?；舴蚵幋a舉例－7第83頁(yè)，共113頁(yè)，2023年，2月20日，星期四霍夫曼編碼舉例－8xiP(xi)碼字碼長(zhǎng)x10.4002x20.2102x30.2112x40.10103x50.101130001011x5x4x3x2x11第84頁(yè)，共113頁(yè)，2023年，2月20日，星期四單符號(hào)信源編二進(jìn)制哈夫曼碼，編碼效率主要決定于信源熵和平均碼長(zhǎng)之比。對(duì)相同的信源編碼，其熵是一樣的，采用不同的編法，得到的平均碼長(zhǎng)可能不同。平均碼長(zhǎng)越短，編碼效率就越高。編法一的平均碼長(zhǎng)為編法二的平均碼長(zhǎng)為可見(jiàn)，本例兩種編法的平均碼長(zhǎng)相同，所以編碼效率相同?；舴蚵幋a舉例－9思考題：哪種方法更好？第85頁(yè)，共113頁(yè)，2023年，2月20日，星期四討論：1)兩種方法平均碼長(zhǎng)相等。2)計(jì)算兩種碼的碼長(zhǎng)方差：第二種方法編出的碼碼字長(zhǎng)度變化較小，便于實(shí)現(xiàn)。第86頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.5實(shí)用的無(wú)失真信源編碼方法舉例－霍夫曼編碼應(yīng)用考察例6和下例：例12：對(duì)以下平穩(wěn)信源進(jìn)行霍夫曼編碼信源字母概率碼字編碼過(guò)程a1a2a3a41/21/41/81/8010110111010101編碼效率：第87頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.5實(shí)用的無(wú)失真信源編碼方法舉例－霍夫曼編碼應(yīng)用結(jié)論：

各信源字母的概率剛好取的形式時(shí)，霍夫曼編碼取得理想的壓縮效果

各信源字母的概率不能取的形式時(shí)，霍夫曼編碼壓縮效率不理想

擴(kuò)展信源，可以提高壓縮效率，當(dāng)時(shí)達(dá)到理想的壓縮第88頁(yè)，共113頁(yè)，2023年，2月20日，星期四－霍夫曼編碼應(yīng)用應(yīng)用:在不同領(lǐng)域得到廣泛應(yīng)用。例：Internationaldigitalfacsimilecodingstandard(1980)US、MPEG1、2問(wèn)題：誤差擴(kuò)散速率匹配統(tǒng)計(jì)匹配（1、一般變長(zhǎng)編碼更適合大的消息集，而不大適合小且概率分布相差很大的集合；小消息集只有在很特殊情況下才能實(shí)現(xiàn)統(tǒng)計(jì)匹配2、要求了解信源的統(tǒng)計(jì)分布；）算法復(fù)雜度隨著信源符號(hào)串長(zhǎng)度的增加而迅速增長(zhǎng)?！?.5實(shí)用的無(wú)失真信源編碼方法舉例第89頁(yè)，共113頁(yè)，2023年，2月20日，星期四－霍夫曼編碼應(yīng)用解決：工程上克服誤差擴(kuò)散的方法有兩種：一是限制哈夫曼碼僅能應(yīng)用于優(yōu)質(zhì)信道（<=10-6）以限制擴(kuò)散的可能性；二是采用定期清洗，防止擴(kuò)散區(qū)域增大。但是它是靠犧牲有效性換取的。一是選擇碼長(zhǎng)方差小的編碼方法，工程上解決速率匹配問(wèn)題的方法是在兩者之間加一個(gè)類似于水庫(kù)的緩存器，它變速入，恒速出，以解決兩者速率的匹配。小消息信源的匹配通過(guò)不斷擴(kuò)展信源實(shí)現(xiàn)；統(tǒng)計(jì)特性未知時(shí)可采用所謂通用編碼的方法來(lái)解決算法復(fù)雜度問(wèn)題考慮采用算術(shù)編碼方法解決。§4.5實(shí)用的無(wú)失真信源編碼方法舉例第90頁(yè)，共113頁(yè)，2023年，2月20日，星期四§4.5實(shí)用的無(wú)失真信源編碼方法舉例－算術(shù)碼引出:Huffman碼應(yīng)用存在的問(wèn)題：分組編碼，碼字分離錯(cuò)誤將導(dǎo)致錯(cuò)誤擴(kuò)散提高編碼效率不斷擴(kuò)展信源編、譯碼復(fù)雜度提高引入算術(shù)碼與擴(kuò)展信源不同的角度解決小消息集合統(tǒng)計(jì)匹配及提高編碼效益問(wèn)題

算術(shù)碼是一種非分組編碼算法。它是從全序列出發(fā)，采用遞推形式的連續(xù)編碼。它不是將單個(gè)的信源符號(hào)映射成一個(gè)碼字，而是將整個(gè)輸入序列的符號(hào)依據(jù)它們的概率映射為實(shí)數(shù)軸上[0,1)區(qū)間內(nèi)的一個(gè)小區(qū)間，再在該小區(qū)間內(nèi)選擇一個(gè)代表性的二進(jìn)制小數(shù)，作為實(shí)際的編碼輸出。它比霍夫曼編碼、游程編碼等編碼算法都復(fù)雜，但它不需要傳送像霍夫曼碼表一類的編碼表。算術(shù)編碼具有自適應(yīng)的能力，它的編碼效率優(yōu)于Huffman編碼，所以算術(shù)編碼是實(shí)現(xiàn)高效數(shù)據(jù)壓縮的有力工具。第91頁(yè)，共113頁(yè)，2023年，2月20日，星期四000→0×20+0×21+0×22→0→0→0×2–1+0×2-2+0×2-3001→1×20+0×21+0×22→1→1/8→0×2–1+0×2–2+1×2–3010→0×20+1×21+0×22→2→2/8→0×2–1+1×2–2+0×2–3011→1×20+1×21+0×22→3→3/8→0×2–1+1×2–2+1×2–3100→0×20+0×21+1×22→4→4/8→1×2–1+0×2–2+0×2–3101→1×20+0×21+1×22→5→5/8→1×2–1+0×2–2+1×2–3110→0×20+1×21+1×22→6→6/8→1×2–1+1×2–2+0×2–3111→1×20+1×21+1×22→7→7/8→1×2–1+1×2–2+1×2-3PCM碼編碼公式對(duì)應(yīng)量化層歸一化編碼公式§4.5實(shí)用的無(wú)失真信源編碼方法舉例

－算術(shù)碼編碼－1第92頁(yè)，共113頁(yè)，2023年，2月20日，星期四

上面例子是一個(gè)簡(jiǎn)單的三位PCM的例子其編碼可表示為：（簡(jiǎn)單算術(shù)表達(dá)式）三位碼共有八層:

如：碼字110A1=1,A2=1,A3=0;§4.5實(shí)用的無(wú)失真信源編碼方法舉例－算術(shù)碼編碼－2第93頁(yè)，共113頁(yè)，2023年，2月20日，星期四則：碼字110可見(jiàn)，這時(shí)信源編碼過(guò)程就可以看作是上述對(duì)應(yīng)二進(jìn)制小數(shù)作移位相加的過(guò)程。故稱它為算術(shù)編碼。§4.5實(shí)用的無(wú)失真信源編碼方法舉例

－算術(shù)碼編碼－3第94頁(yè)，共113頁(yè)，2023年，2月20日，星期四分析：上述例子僅是一個(gè)特例，因?yàn)樗鼪](méi)有考慮信源的統(tǒng)計(jì)特性，（它認(rèn)為信源是遵從等概率分布的）所以編出的碼字是等長(zhǎng)碼，而對(duì)應(yīng)的算術(shù)運(yùn)算則是簡(jiǎn)單的整數(shù)項(xiàng)相加。（即Ki為整數(shù)）?！?.5實(shí)用的無(wú)失真信源編碼方法舉例

－算術(shù)碼編碼－4問(wèn)題：對(duì)一般的具有統(tǒng)計(jì)特性的信源的算術(shù)編碼問(wèn)題。方法：將上述算術(shù)編碼方式進(jìn)一步拓廣，其中最關(guān)鍵的是要將算術(shù)編碼與信源的符號(hào)概率及累積概率建立一一對(duì)應(yīng)關(guān)系，進(jìn)而將累計(jì)概率與區(qū)間的一個(gè)數(shù)C聯(lián)系起來(lái)。新的問(wèn)題：在引入統(tǒng)計(jì)特性后的算術(shù)編碼中，每次移位的位數(shù)可以是非整數(shù)（精度有限的有理數(shù)），正是由于這種非整數(shù)的引入使算數(shù)編碼變成了非分組碼（當(dāng)然，算術(shù)編碼從全序列出發(fā)，考慮符號(hào)間的依賴關(guān)系來(lái)編碼）。第95頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼－5信源符號(hào)序列的累積分布函數(shù)設(shè)信源符號(hào)集：其相應(yīng)的概率分布為：信源符號(hào)累積分布函數(shù)：對(duì)二元信源第96頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼－6舉例說(shuō)明，二元無(wú)記憶信源為例。區(qū)間由F(1)劃分成兩個(gè)子區(qū)間：寬度A（0）=P（0）寬度A（1）=P（1）若輸入第一個(gè)符號(hào)為S=“0”,即落入相應(yīng)的區(qū)間得

若輸入第二個(gè)符號(hào)為1，S=“01”,相應(yīng)的區(qū)間是在進(jìn)行分割，符號(hào)“00”對(duì)應(yīng)的區(qū)間寬度為

符號(hào)“01”對(duì)應(yīng)的區(qū)間寬度為01F(1)第97頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼－7符號(hào)S=“00”對(duì)應(yīng)的區(qū)間為符號(hào)S=“01”對(duì)應(yīng)的區(qū)間為

是符號(hào)序列“01”對(duì)應(yīng)區(qū)間的下界值（對(duì)應(yīng)符號(hào)序列的累積分布函數(shù)）01F(1)第98頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼－7若輸入第三個(gè)符號(hào)為1，S=“011”可以記作S+1=S1,相應(yīng)的區(qū)間是在進(jìn)行分割，符號(hào)S0=“010”對(duì)應(yīng)的區(qū)間寬度為對(duì)應(yīng)的區(qū)間為符號(hào)S1=“011”對(duì)應(yīng)的區(qū)間寬度為對(duì)應(yīng)的區(qū)間為符號(hào)序列s1=“011”的累積分布函數(shù)若輸入第三個(gè)符號(hào)為0，S=“010”下界仍為F(s),序列S0的累積分布函數(shù)為第99頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼－8信源符號(hào)序列的累積分布函數(shù)迭代公式已知當(dāng)前輸入符號(hào)序列為S，若接著再輸入一個(gè)0，序列S0累積分布函數(shù)：區(qū)間寬度為已知當(dāng)前輸入符號(hào)序列為S，若接著再輸入一個(gè)1，序列S1累積分布函數(shù)：區(qū)間寬度為

第100頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼－9舉例說(shuō)明S=“011”,接著輸入1對(duì)應(yīng)區(qū)間寬度為第101頁(yè)，共113頁(yè)，2023年，2月20日，星期四102第102頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼－10信源符號(hào)序列的累積分布函數(shù)樹(shù)圖計(jì)算法已知當(dāng)前輸入符號(hào)序列為S=(s1s2…sn)，另一二元序列串為Y=(y1y2…yn)對(duì)第一個(gè)i有si=1,yi=0,則S>Y。把符號(hào)序列看成二進(jìn)制小數(shù)0.S和0.Y，對(duì)第一個(gè)i有si>yi,則0.S>0.Y將二元符號(hào)序列排成一棵n階二元整樹(shù)。可見(jiàn)所有小于S的序列都在同一階S節(jié)點(diǎn)的左側(cè)。111001第103頁(yè)，共113頁(yè)，2023年，2月20日，星期四S=110101C0.01111001P(S)=(3/4)3(1/4)C=1000(有尾數(shù)時(shí)進(jìn)位）11010.100101000.00011011算術(shù)碼編碼舉例－1例14：P(S)=(3/4)3(1/4)第104頁(yè)，共113頁(yè)，2023年，2月20日，星期四1110算術(shù)碼編碼舉例－2第105頁(yè)，共113頁(yè)，2023年，2月20日，星期四算術(shù)碼編碼過(guò)程：：累積概率碼字：區(qū)間長(zhǎng)度（符號(hào)所落區(qū)間）例：算術(shù)碼編碼舉例－3第106頁(yè)，共113頁(yè)，2023年，2月20日，