門愛(ài)東教授

第4講熵編碼EntropyCoding2內(nèi)容提要Outline熵編碼原理前綴碼Huffman編碼一元碼Golomb碼Elias編碼算術(shù)編碼視頻信號(hào)的熵熵的減小熵編碼原理-無(wú)失真壓縮有失真壓縮系統(tǒng)中的無(wú)失真壓縮模塊幾乎所有的有失真壓縮系統(tǒng)都包含有一個(gè)無(wú)失真壓縮子系統(tǒng)這里僅討論無(wú)失真壓縮，后面章節(jié)再討論有失真壓縮3熵編碼原理-問(wèn)題Alice從一個(gè)有限集合中選擇了一個(gè)結(jié)果，但沒(méi)有透露她的選擇。Bob通過(guò)一系列的“是/否”的問(wèn)題來(lái)唯一地確定Alic選擇結(jié)果。游戲的目的是用平均數(shù)量盡可能少的問(wèn)題獲得結(jié)果。目標(biāo)：為Bob設(shè)計(jì)一個(gè)最好的策略。哪種方案更好？為每種結(jié)果產(chǎn)生一個(gè)二進(jìn)制編碼4熵編碼原理-問(wèn)題定長(zhǎng)碼FixedlengthcodeK個(gè)輸出結(jié)果的平均長(zhǎng)度Iav=log2K

等概結(jié)果的最優(yōu)編碼通過(guò)改變“樹(shù)”來(lái)驗(yàn)證此結(jié)論5熵編碼原理-問(wèn)題變長(zhǎng)碼

Variablelengthcode（VLC）

如果結(jié)果不是等概的：

用短碼描述高概率結(jié)果，

用長(zhǎng)碼描述低概率結(jié)果直觀感覺(jué)：

由等概結(jié)果得到的最佳的等長(zhǎng)碼樹(shù)，可以修剪為不等長(zhǎng)的碼樹(shù)，以對(duì)應(yīng)不等概率，這樣不等長(zhǎng)碼樹(shù)也獲得最優(yōu)因此，一個(gè)概率為p

的結(jié)果需要：67編碼器信源(消息集)編碼輸出集(接收端)U0={a1,a2,…,aK}Y={y1,y2,…,yK}符號(hào)集Sm={s1,s2,…,sM}編碼器模型圖

其中U0

是無(wú)記憶信源的消息集,由多個(gè)消息ak構(gòu)成（k=1,2,……,K），出現(xiàn)的概率分別為Pj（j=1,2,……,K）。Y是輸出集，由多個(gè)碼字yk構(gòu)成（k=1,2,……,K），yk與ak一一對(duì)應(yīng)。Sm是符號(hào)集，由m個(gè)碼元si構(gòu)成(i=1,2,……,M)，符號(hào)集中的碼元組成輸出碼字。熵編碼原理-信息量和信息熵8熵編碼原理-信息量和信息熵信息：是用不確定性的量度定義的信息量：從N個(gè)可能事件中選出一個(gè)事件所需要的信息度量或含量。上述消息“ak”的信息量定義為：熵:如果將信源所有可能事件信息量進(jìn)行平均就得到信息的熵(熵就是平均信息量)，單位是bits/Symbol。熵的邊界特性:熵編碼原理-信息量和信息熵非常大概率或小概率的事件不會(huì)明顯地改變熵二進(jìn)制隨機(jī)變量的熵910無(wú)失真源編碼理論[Shannon，1948]信源含有的平均信息量(熵)H(U0)，就是對(duì)符號(hào)U0進(jìn)行可解碼的變字長(zhǎng)編碼的平均碼長(zhǎng)

Iav

的下限，即無(wú)失真編碼的理論極限。相反，如果有足夠大的符號(hào)塊進(jìn)行聯(lián)合編碼，平均碼長(zhǎng)Iav

可以逼近熵H(U0)。碼的冗余定義為：R=Iav–H(U0)信源中或多或少的含有自然冗余。零冗余如果每個(gè)碼字長(zhǎng)度等于Icw(ak)=-log2(p(ak)，則碼字的平均碼長(zhǎng)等于它的熵，沒(méi)有冗余，即Iav=H(U0)，R=0。對(duì)于二進(jìn)制碼字，概率將都是二進(jìn)制分?jǐn)?shù)：熵編碼原理-信息熵和比特率11熵編碼原理-信息熵和比特率例對(duì)于等字長(zhǎng)碼，要表示4個(gè)事件，需要2bit，其平均碼長(zhǎng)為2bit/符號(hào)，冗余為0.25。對(duì)于變字長(zhǎng)碼12熵編碼原理－變字長(zhǎng)編碼定理在變字長(zhǎng)編碼中，對(duì)于出現(xiàn)概率大的信息符號(hào)，賦予短字長(zhǎng)的碼，對(duì)于出現(xiàn)概率小的信息符號(hào)，賦予長(zhǎng)字長(zhǎng)的碼。如果碼字長(zhǎng)度嚴(yán)格按照符號(hào)概率的大小的相反順序排列，則平均碼字長(zhǎng)度一定小于按任何其它符號(hào)順序排列方式得到的碼字長(zhǎng)度。最佳的平均碼字長(zhǎng)度：其中：P(ak)是信源符號(hào)ak

出現(xiàn)的概率；Ik

是符號(hào)ak

的編碼長(zhǎng)度。根據(jù)編碼方法定義規(guī)定：如果P(ai)≥P(as)，則Ii<Is

如果將ai

的碼字與as

的碼字互換，則:前綴碼Prefixcode

給定一個(gè)獨(dú)立同分布（IID）隨機(jī)過(guò)程{Xn}，由字符Ax

組成，概率密度分別為fx(x)。唯一可解碼Uniquelydecodable為每個(gè)元素x∈Ax

指定一個(gè)不同的碼字cx，這里cx

是一個(gè)長(zhǎng)度為||cx||比特的數(shù)據(jù)串，這樣即使碼流中碼字Cxn

是直接相連的，在解碼時(shí)也可以確定每個(gè)符號(hào)xn。具有上述特性的碼稱為“唯一可譯碼”前綴碼

Prefixcode一個(gè)碼字不會(huì)是其它任何碼字的前綴（前面部分）。例如，若A的編碼為0，則B的編碼不是以0開(kāi)頭的，如01、001這樣的。是唯一可解碼，符號(hào)連著符號(hào)，以自然順序0,1,2,…n,…前綴：漢語(yǔ)里指在詞根前面的構(gòu)詞成分，如“阿哥”、“阿姨”中的“阿”；英文中指一個(gè)英語(yǔ)單詞可以分為三個(gè)部分：前綴（prefix）、詞根（stem）和后綴（suffix），單詞中位于詞根前面的部分就是前綴。13前綴碼Prefixcode

非可譯碼舉例(non-decodablecode)對(duì)源符號(hào)序列進(jìn)行編碼：a0、a2、a3、a0、a1

結(jié)果的比特流：01011001對(duì)源符號(hào)序列進(jìn)行編碼：a1、a0、a3、a0、a1

結(jié)果的比特流：01011001不同的源符號(hào)序列具有相同的編碼比特流，解碼端產(chǎn)生歧義，不是唯一可解的；不是一個(gè)前綴碼14前綴碼唯一可譯性：McMillan和Kraft條件唯一可譯性的必要條件[McMillan麥克米倫]：給定一組碼字長(zhǎng)度||cx||滿足McMillan條件，相應(yīng)的前綴碼總是存在[Kraft卡夫]

因此，McMillan不等式是必要且充分的，也稱之為Kraft不等式，或Kraft-McMillan不等式

如果僅使用前綴碼，是無(wú)損的；前綴碼的編碼結(jié)果不是唯一的。前綴碼還具有即時(shí)可譯性，以及易于構(gòu)造，因此，實(shí)際中使用的變字長(zhǎng)碼都是前綴碼。15前綴碼前綴解碼16前綴碼二叉樹(shù)（BinaryTree）通過(guò)從根到樹(shù)葉的遍歷，任何二叉樹(shù)樹(shù)都可以轉(zhuǎn)換成前綴碼對(duì)應(yīng)于二叉樹(shù)樹(shù)的任何前綴碼都滿足McMillan等式條件：17前綴碼二叉樹(shù)增加兩個(gè)新節(jié)點(diǎn)不會(huì)改變McMillan之和修剪二叉樹(shù)不會(huì)改變McMillan之和最簡(jiǎn)單的二叉樹(shù)的McMillan之和1819Huffman編碼Huffman于1952發(fā)明了整數(shù)碼的最佳變字長(zhǎng)編碼，利用了上述熵、熵編碼和變字長(zhǎng)編碼概念。所謂的整數(shù)碼是指每個(gè)符號(hào)所對(duì)應(yīng)的碼字的位數(shù)都是整數(shù)。由DavidHuffman提出：MIT’sRobertFano的信息論作業(yè)Shannon-Fano編碼的改進(jìn)，Shannon-fano碼是第一個(gè)基于Shannon理論的次優(yōu)碼，Huffman改進(jìn)成了最優(yōu)碼。最優(yōu)Huffman碼的條件出現(xiàn)概率越高的符號(hào)的碼長(zhǎng)應(yīng)該越短出現(xiàn)概率最低的兩個(gè)符號(hào)其長(zhǎng)度應(yīng)該相等最優(yōu)碼的碼樹(shù)，每個(gè)中間節(jié)點(diǎn)必有兩個(gè)分支假設(shè)通過(guò)合并所有的葉子節(jié)點(diǎn)，把一個(gè)中間節(jié)點(diǎn)變成了葉子節(jié)點(diǎn)，遞減了字符集合，那么，如果原始碼樹(shù)對(duì)原始字符集合是最優(yōu)的，則裁剪的碼樹(shù)對(duì)遞減的符號(hào)集合也是最優(yōu)的概率最低的兩個(gè)符號(hào)對(duì)應(yīng)的碼字只在最后1bit有差別，一個(gè)最后1位是0，另一個(gè)是1，其它位相同。(1925-1999)20Huffman編碼Huffman碼碼樹(shù)形成步驟①合并：把信源符號(hào)按概率大小順序排列，出現(xiàn)概率最小的兩個(gè)符號(hào)的概率相加，得到一個(gè)新的合并概率。②置換：把這個(gè)合并概率看成是一個(gè)新組合符號(hào)的概率，重新排序。③類推：重復(fù)上述做法直到最后只剩下兩個(gè)符號(hào)概率為止。④賦值和反推：把上述碼樹(shù)轉(zhuǎn)換為前綴碼。完成以上概率順序排列后，再反過(guò)來(lái)逐步向前進(jìn)行編碼，每一步有兩個(gè)分支各賦予一個(gè)二進(jìn)制碼，可以對(duì)概率大的賦為“1”，概率小的賦為“0”。21Huffman編碼比特?cái)?shù)223344440101010101010122例：信源有四個(gè)符號(hào)：

Xa1a2a3a41/21/41/81/8信息熵：Huffman編碼Huffman（二進(jìn)制編碼）a1a2a3a4010110111

平均碼長(zhǎng)：Iav=(1/2)1+(1/4)2+(1/8)6=1.75bit/字符編碼效率：=1.75/1.75=100%

編碼冗余：R=0a11/2a21/4a31/8a41/800011/211/41010110111234個(gè)符號(hào)的等長(zhǎng)碼：

B=log24=2bita1a2a3a400011011L=2Pi

=2

編碼效率：=H(X)/L=1.75/2=87.5%碼表Huffman編碼此例子中的碼表Huffman編碼舉例：原信源輸出序列：a1

a2a1a3a2

a1a1

a4…..

編碼后的序列：01001101000111...24構(gòu)建Huffman樹(shù)字母概率碼字a0.2000b0.41c0.201d0.10011e0.10010abecd00010.20.6011.0熵H

=-s=a..eP(s)log2P(s)=2.122

bits/symbol平均碼長(zhǎng)l

av=0.4×1+0.2×2+0.2×3+0.1×4+0.1×4=2.2

bits/symbol冗余l(xiāng)

av-H=0.078

bits/symbol25另一棵Huffman樹(shù)bed010.2ac0.20.2010.40.60101平均碼長(zhǎng)lav

=0.4×1+(0.2+0.2+0.1+0.1)×3=2.2bits/symbol字母概率碼字a0.2000b0.41c0.2001d0.1011e0.101026再一棵Huffman樹(shù)bed010.2ac0.20.2010.40.60101平均碼長(zhǎng)lav

=0.4x2+(0.2+0.2)x2+(0.1+0.1)x3=2.2bits/symbol字母概率碼字a0.200b0.411c0.201d0.1101e0.110027最小方差Huffman樹(shù)Huffman編碼不惟一但所有編碼的平均碼長(zhǎng)相同應(yīng)該選擇哪一個(gè)呢？答案：方差最小者為佳（碼字長(zhǎng)度方差最小)，即高度最小的樹(shù)為什么？編碼流中的編碼長(zhǎng)度變化最小，即碼率大小變化最小怎樣達(dá)到？在排序時(shí)，將較小的集合（元素?cái)?shù)目少）盡可能放在上面也可以將新合并的集合盡可能放在下面（即認(rèn)為它們的碼長(zhǎng)應(yīng)該更短一些）碼字長(zhǎng)度的方差σ2：每個(gè)碼字長(zhǎng)度li

與平均碼長(zhǎng)lav

之差的平方的數(shù)學(xué)期望，即28最小方差Huffman樹(shù)碼樹(shù)1的碼字長(zhǎng)度方差：abecd00010.20.6011.0碼樹(shù)2的碼字長(zhǎng)度方差：bed010.2ac0.20.2010.40.60101bed010.2ac0.20.2010.40.60101碼樹(shù)3的碼字長(zhǎng)度方差：采用第三種編碼方法：碼長(zhǎng)變化較?。ū容^接近于平均碼長(zhǎng)）第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；第三種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；顯然，第三種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)。29最小方差Huffman樹(shù)由于碼位要以固定的速率傳輸，所以編碼器要用緩沖器平滑比特產(chǎn)生的碼率變化。碼字的方差越大，碼位進(jìn)入緩沖器的速率越不穩(wěn)定，因而編碼器需要的緩沖器也越大。例如：假設(shè)傳輸字符的速率固定，如10,000字符/秒，平均碼長(zhǎng)為2.2bits/字符，則接收方每秒將平均收到22,000比特。幾秒內(nèi)一直產(chǎn)生包含e、d的字符串采用第一種編碼方式，ed用4bit/字符表示，這樣產(chǎn)生的比特率為40,000比特/秒，緩沖區(qū)每秒需保存(40000-22000)=18,000比特。采用第三種編碼方式，比特率為30,000比特/秒，緩沖區(qū)每秒需保存8,000比特。幾秒內(nèi)一直產(chǎn)生包含b的字符串采用第一種編碼方式，這樣產(chǎn)生的比特率為10,000比特/秒，傳輸帶寬浪費(fèi)12,000比特/秒采用第三種編碼方式，比特率為20,000比特/秒，傳輸帶寬浪費(fèi)2000比特/秒abecd00010.20.6011.0bed010.2ac0.20.2010.40.60101方差大的代碼將導(dǎo)致編碼器的輸出碼率不斷變化，緩沖區(qū)的設(shè)計(jì)變得更難30Huffman解碼Huffman碼是非歧義的，在解碼過(guò)程中，對(duì)某個(gè)碼字的解釋是唯一的。在開(kāi)始?jí)嚎s之前，編碼器必須根據(jù)符號(hào)的概率（或出現(xiàn)的概率）確定碼字。解碼器利用這些信息對(duì)壓縮流進(jìn)行解碼，所以應(yīng)該將這些信息也寫(xiě)入壓縮流中，以便解碼器能解碼該壓縮流。變長(zhǎng)碼：不好，因?yàn)榇a長(zhǎng)不同。寫(xiě)入概率/概率：將概率/概率標(biāo)定為整數(shù)，然后解碼器利用該概率信息構(gòu)造Huffman樹(shù)通常只會(huì)在壓縮流中增加幾百字節(jié)。寫(xiě)入Huffman樹(shù)：比只寫(xiě)概率花費(fèi)的字節(jié)數(shù)更多。31Huffman解碼方法1：比特串行解碼固定輸入比特率——可變輸出符號(hào)率，假定二進(jìn)制碼樹(shù)在解碼器端可得逐個(gè)比特讀入輸入壓縮流，并遍歷樹(shù)，直到到達(dá)一個(gè)葉節(jié)點(diǎn)。當(dāng)?shù)竭_(dá)葉節(jié)點(diǎn)時(shí)，Huffman解碼器輸出葉節(jié)點(diǎn)處的符號(hào)，即完成該符號(hào)的解碼。輸入流的每個(gè)比特用過(guò)后即丟棄。重復(fù)步驟1和2，直到所有的輸入都解完。由于所有碼字長(zhǎng)度不同，解碼比特率對(duì)所有符號(hào)并不相同。例如：原信源輸出序列：a1a2a1a3a2a1a1a4…..，編碼后的序列：01001101000111...當(dāng)接收端收到碼流01001101000111……時(shí)，順著碼樹(shù)解碼，樹(shù)根→樹(shù)干→樹(shù)枝→樹(shù)葉，以0開(kāi)頭的碼字只有0，因此，解出第1個(gè)符號(hào)為a1；去掉已解碼的0后，碼流剩下1001101000111，以1開(kāi)頭，第2比特是0，因此，碼字是10，因此，解出第2個(gè)符號(hào)為a2；00010a110a2110a3111a41132方法2：基于查找表的解碼，對(duì)所有符號(hào)解碼率恒定在解碼端從符號(hào)—碼字映射表中構(gòu)建查找表。如果表中的最長(zhǎng)碼字為l比特，則需要一個(gè)2l個(gè)入口的查找表?？臻g限制：圖象/視頻最長(zhǎng)的l=16~20構(gòu)造查找表：設(shè)xi

對(duì)應(yīng)的碼字為wi

，假定wi有l(wèi)i

比特。構(gòu)造一個(gè)l比特地址，前l(fā)i個(gè)比特是wi

，后l-li

個(gè)比特取任意0和1的組合。所以，對(duì)符號(hào)xi有2l-li個(gè)地址。在每個(gè)入口形成（xi,li）。解碼步驟：從壓縮輸入比特流中，讀l個(gè)比特到緩沖區(qū)中;將緩沖區(qū)中的l比特字作為查找表中的地址，得到對(duì)應(yīng)的符號(hào)xk。令碼字長(zhǎng)度為lk，即解碼一個(gè)符號(hào)。移出緩沖區(qū)中的前l(fā)k個(gè)比特，再移入若干比特，使得緩沖區(qū)重新為l個(gè)比特。重復(fù)步驟2和3，直到所有的符號(hào)都解碼。Huffman解碼33自適應(yīng)Huffman編碼Huffman編碼需要各符號(hào)的概率。概率來(lái)源：靜態(tài)概率模型：根據(jù)訓(xùn)練數(shù)據(jù)得到，然后不同信源利用同一個(gè)概率表無(wú)需傳送Huffman碼表/碼樹(shù)H.263視頻編碼器半自適應(yīng)統(tǒng)計(jì)模型：必須傳送Huffman碼表和壓縮流需2遍掃描但在很多情況下不實(shí)用：如壓縮網(wǎng)絡(luò)傳輸自適應(yīng)/動(dòng)態(tài)概率模型：1遍掃描開(kāi)始時(shí)認(rèn)為是等概率根據(jù)前k(k=1,2,…)個(gè)符號(hào)統(tǒng)計(jì)重新產(chǎn)生碼字并編碼第k+1st

個(gè)字符Unix系統(tǒng)對(duì)程序的壓縮：基于單詞的自適應(yīng)Huffman編碼34自適應(yīng)Huffman編碼思想如果信源的統(tǒng)計(jì)特性事先不知道，可以采用自適應(yīng)Huffman編碼，以與真實(shí)數(shù)據(jù)統(tǒng)計(jì)特性相匹配前向自適應(yīng)編碼器分析輸入數(shù)據(jù)，測(cè)量信源統(tǒng)計(jì)特性在壓縮比特率的前頭傳輸Huffman碼表JPEG采用了此方式（盡管傳輸?shù)慕?jīng)常是缺省碼表）后向自適應(yīng)編解碼端對(duì)相同的已解碼的數(shù)據(jù)統(tǒng)計(jì)信源特性；發(fā)送端和接收端定期產(chǎn)生相同的Huffman碼表；節(jié)省了前向自適應(yīng)的額外開(kāi)銷，但碼表一般較差，因?yàn)榛谶^(guò)去的數(shù)據(jù)；由于增加了解碼器的計(jì)算負(fù)擔(dān)，不常用35自適應(yīng)Huffman編碼自適應(yīng)Huffman編碼算法更新流程更新舉例36自適應(yīng)Huffman編碼自適應(yīng)Huffman算法編碼流程37自適應(yīng)Huffman編碼自適應(yīng)Huffman算法解碼流程38非二進(jìn)制Huffman編碼與二進(jìn)制Huffman碼類似出現(xiàn)概率越高的符號(hào)的碼長(zhǎng)應(yīng)該越短出現(xiàn)概率最低的m個(gè)符號(hào)其長(zhǎng)度應(yīng)該相等概率最低的m個(gè)符號(hào)對(duì)應(yīng)的碼字只在最后1bit有差別，一個(gè)最后1位是0，另一個(gè)是1，其它位相同。39Huffman碼的局限性當(dāng)符號(hào)集較大且概率分布不是很懸殊時(shí)，Huffman的平均碼長(zhǎng)可接近于熵。對(duì)于概率分布懸殊的消息集合，上限可能很大，意味著編碼冗余度較大一個(gè)極端的例子：黑白傳真采用Huffman編碼，得到W={0,1}，都需要l=1位，沒(méi)起到壓縮的作用。編碼效率僅為這是因?yàn)镠uffman編碼只能為每個(gè)信源符號(hào)分配整數(shù)個(gè)比特，只有當(dāng)每個(gè)符號(hào)的概率是2的負(fù)整數(shù)倍時(shí)，才能達(dá)到熵值。40Huffman碼的局限性Huffman碼的冗余0≤R<1bit/symbol對(duì)于任何分布，Huffman碼的平均碼長(zhǎng)滿足平均碼長(zhǎng)界定定理：證明：

左邊不等式：Shannon無(wú)失真編碼理論右邊不等式：

選擇碼字長(zhǎng)度

結(jié)果碼率41Huffman碼的局限性對(duì)Huffman編碼，更緊致的上界：令pmax

表示最大概率，若pmax≥0.5，則平均碼長(zhǎng)滿足：若pmax<0.5，則平均碼長(zhǎng)滿足：所以最大概率比較大（概率不均衡）時(shí)，上界離熵值相差較大，編碼效率不高。42Vector

Huffman編碼考慮信源：A={a,b,c},P(a)=0.8,P(b)=0.02,P(c)=0.18H=0.816

bits/symbolHuffman編碼：a 0b 11c 10lav=1.2

bits/symbol冗余=0.384b/sym(47%!)Q：對(duì)概率變化劇烈或者H(X)<<1bit/symbol的信源，Huffman編碼效率很低，能否做得更好嗎？

A：把k個(gè)連續(xù)符號(hào)組成一個(gè)新的“塊符號(hào)”(block-symbol)，或者“矢量”(vector)，然后對(duì)這個(gè)“塊符號(hào)”進(jìn)行Huffman編碼。43Vector

Huffman編碼(2)思想考慮對(duì)兩個(gè)字母序列編碼，而不是單個(gè)字母合并信源符號(hào)（聯(lián)合熵），利用符號(hào)間的相關(guān)性有的書(shū)上稱為擴(kuò)展Huffman編碼字母概率碼字aa0.64000ab0.016010101ac0.144011ba0.0160101000bb0.000410100101bc0.00361010011ca0.1440100cb0.003610100100cc0.03241011lav=1.7228/2=0.8614冗余

=0.0045

比特/字符44Vector

Huffman編碼(3)舉例：離散無(wú)記憶信源

X： x1 x2 P(X): 0.2 0.8

則熵為

H(X)=－0.2log0.2－0.8log0.8＝0.7219比特/信符用二進(jìn)制符號(hào)集A:{0，1}進(jìn)行無(wú)失真信源編碼：

x1→w1＝0； x2→w2＝1；45Vector

Huffman編碼(4)對(duì)其二次擴(kuò)展信源進(jìn)行編碼：

X2

p(wi) wi x1x1 1/25 000 x1x2 4/25 001 x2x1 4/25 01 x2x2 16/25 146Vector

Huffman編碼(5)該思想還可以擴(kuò)展考慮所有mk

的序列，m為符合集合中符號(hào)的個(gè)數(shù)，例如{a,b,c}的m=3，k為合并符號(hào)長(zhǎng)度，例如k=2，ab,bc,ac,cb,…..。設(shè)碼符號(hào)集信源符號(hào)的k次擴(kuò)展：Xk={x1,x2,…,xk}Huffman碼Wk={w1,w2,…,wk}，其k次擴(kuò)展的平均長(zhǎng)度為lk如果要求Wk

為唯一可譯碼，則每個(gè)信源符號(hào)的平均碼長(zhǎng)lav=lk/k當(dāng)k足夠大時(shí)，平均碼長(zhǎng)lav

可以無(wú)限接近下界值，從而在一定程度上提高了編碼的有效性47Vector

Huffman編碼(6)理論上，通過(guò)考慮更長(zhǎng)序列可以提高編碼性能考慮組合長(zhǎng)度為k的所有可能的mk

序列，例如前面{abc}的32種組合符號(hào)。實(shí)際中，字母表隨序列長(zhǎng)度指數(shù)增長(zhǎng)使得它不現(xiàn)實(shí)例如，對(duì)組合長(zhǎng)度為3的ASCII（256個(gè)符號(hào)）序列：2563=224=16M。需要對(duì)長(zhǎng)度為k的所有序列產(chǎn)生碼本，而大多數(shù)序列的出現(xiàn)概率為0，或者很小。例如：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symbol，l1=1.05,l2=0.611,…當(dāng)k=8時(shí)編碼性能才變得可接受但此時(shí)|alphabet|=38=6561!!!因此，概率分布嚴(yán)重不對(duì)稱是真正的大問(wèn)題，需要找到克服的方法。 需要其他方法：算術(shù)編碼是從另一種角度對(duì)很長(zhǎng)的信源符號(hào)序列有效編碼的方法。截?cái)嗟腍uffman碼思路：通過(guò)只對(duì)最大概率的符號(hào)進(jìn)行編碼，減少Huffman碼表的大小和最大Huffman碼字的長(zhǎng)度。

字符集中有K

個(gè)字符，把其中概率最小的J

個(gè)字符組合為一個(gè)輔助符號(hào)ESC；對(duì)剩余的(K–J)個(gè)最大概率符號(hào)和輔助符號(hào)ESC進(jìn)行Huffman編碼；

如果是ESC編碼，則隨后跟著log2(J)個(gè)比特，以確切說(shuō)明是ESC中哪一個(gè)小概率的符號(hào)；結(jié)果是增加了平均碼字長(zhǎng)度，但通過(guò)選擇J，可以更好地平衡復(fù)雜性和效率4849Huffman編碼的應(yīng)用在實(shí)際應(yīng)用中，Huffman編碼通常與其他編碼技術(shù)一起使用例：無(wú)損圖像壓縮Grayimages(0~255),Imagesize:256*256SenaEarthSensinOmaha50Huffman編碼在圖像壓縮中的應(yīng)用壓縮率不是很高，平均每個(gè)像素約減少1比特更實(shí)用的技術(shù)：與預(yù)測(cè)模型一起使用ImageNameBits/PexelTotalSize(bytes)CompressionRatioSena7.0157,5041.14Sensin7.4961,4301.07Earth4.9440,5341.62Omaha7.1258.3741.12直接對(duì)像素用Huffman編碼進(jìn)行壓縮51Huffman編碼在音頻壓縮中的應(yīng)用CD質(zhì)量的音頻：采樣頻率：44.1kHz；每個(gè)樣本16比特?cái)?shù)據(jù)量巨大FileNameOriginalFileSize(Bytes)Entropy(bits)EstimatedCompressionFileSize(bytes)CompressionRatioMozart939,86212.8725,4201.30Cohn402,44213.8349,3001.15Mir884.02013.7759,5401.16對(duì)16比特的CD質(zhì)量音頻用Huffman編碼進(jìn)行壓縮52Huffman碼特點(diǎn)Huffman編碼字長(zhǎng)參差不齊，是變字長(zhǎng)整數(shù)碼，輸出碼率是變化的。因此，對(duì)于恒定碼率信道，需要增加輸出緩存器來(lái)平滑。Huffman編碼在信源編碼概率分布不均勻時(shí)效率高，所以概率比較均勻時(shí)或很不均勻時(shí)，Huffman碼性能不好。Huffman編碼表可以缺省，好處是對(duì)稱性，降低編碼時(shí)間。編碼方法不惟一，碼長(zhǎng)方差較小的編碼更好。對(duì)同一個(gè)信源所構(gòu)成的Huffman碼不是唯一的，但它的平均碼長(zhǎng)是一樣。因?yàn)橐粋€(gè)節(jié)點(diǎn)的上下兩個(gè)分支既可以賦0（或1），也可以賦1（或0）；同時(shí)，對(duì)概率相同的兩個(gè)事件的排列順序也是隨便選擇的。Huffman碼是前綴碼，解碼是非歧義的，即在解碼過(guò)程中，對(duì)某個(gè)碼字的解釋是唯一的。Huffman碼的上下界：靜態(tài)/半自適應(yīng)/自適應(yīng)動(dòng)態(tài)Huffman編碼，概率模型和信源越匹配越好，實(shí)際概率模型和Huffman編碼時(shí)假設(shè)的概率模型有差異時(shí)，編碼效率會(huì)下降。非二進(jìn)制Huffman編碼擴(kuò)展Huffman編碼，更長(zhǎng)的組合長(zhǎng)度可以提高編碼性能壓縮率為1~2倍，自適應(yīng)時(shí)2~4倍，通常與預(yù)測(cè)編碼一起使用。一元編碼（Unarycoding)一元碼（Unarycode）是變長(zhǎng)碼，它把一個(gè)非負(fù)整數(shù)用n個(gè)1和一個(gè)0表示（或者n個(gè)0和一個(gè)1，n≥1）。在什么情況下是最佳碼？當(dāng)概率為1/2、1/4、1/8、1/16、1/32…此時(shí)Huffman碼就是一元碼，或者說(shuō)，一元碼是Huffman碼的特例。53一邊樹(shù)葉一元編碼（Unarycoding)“幾何”信源(GeometricSource)符號(hào)集為非負(fù)整數(shù)：概率密度函數(shù)服從“幾何分布”(GeometricDistribution,GD)：在Bernoulli實(shí)驗(yàn)（在同樣的條件下重復(fù)地、各次之間相互獨(dú)立地進(jìn)行的一種試驗(yàn)）中，在第一次成功之前失敗次數(shù)為x的概率，失敗的概率為ρ。當(dāng)參數(shù)ρ≤1/2時(shí)，即快速衰落的幾何信源，一元碼為最佳前綴碼當(dāng)ρ=1/4，p(x)：0.75,0.19,0.05,0.01,0.003,….Huffman編碼：不需要重新排序等價(jià)于一元碼一元碼為最佳前綴碼，但效率不高

當(dāng)ρ=1/2時(shí)平均長(zhǎng)度等于熵一元碼不僅是最佳前綴碼，且是所有熵編碼中最佳的(包括算術(shù)編碼)當(dāng)ρ=3/4，p(x)：0.25,0.19,0.14,0.11,0.008,….

Huffman編碼需要重新排序，一元碼不是最佳前綴碼54一元編碼（Unarycoding)為什么用幾何分布作為信源模型？幾何分布符合實(shí)際情況，對(duì)圖像/視頻壓縮很有用例1：游程編碼對(duì)壓縮非常有效i.i.d.分布的二值序列，其中ρ=p(0)即0出現(xiàn)的概率，假如序列為0000010000000010000110000001游程r表示每個(gè)幅度值（此例中為1）之前連0的個(gè)數(shù)：5，8，4，0，6。

游程r的概率分布：

n個(gè)0接著一個(gè)1

參數(shù)為ρ的單邊幾何分布例2：預(yù)測(cè)編碼大多數(shù)的e(n)值都很小，在0附近可用雙邊幾何分布建模55一元編碼（Unarycoding)為什么用幾何分布作為信源模型？雙邊幾何分布可用單邊幾何近似

減少自適應(yīng)熵編碼中上下文的數(shù)目將負(fù)數(shù)映射成正數(shù)：映射可能不止一個(gè)在JPEG-LS中有應(yīng)用單邊幾何分布是對(duì)指數(shù)分布的離散近似，

指數(shù)分布為：雙邊幾何分布為L(zhǎng)aplacian分布（亦稱為雙邊指數(shù)分布）的離散近似。Laplacian分布為：56Golomb編碼對(duì)于具有慢衰落的幾何信源，怎樣構(gòu)造最佳一元碼？思路：轉(zhuǎn)化為ρ≤1/2的幾何分布(盡可能接近)怎樣轉(zhuǎn)化？將信源X中的m個(gè)符號(hào)組成一組，每組大小相等表示為Golomb(m)或Golomb-m碼字的構(gòu)成：(一元碼，固定長(zhǎng)度的二進(jìn)制碼）組號(hào)：一元碼每組內(nèi)的索引編號(hào)：固定長(zhǎng)度碼S.Golomb,Run-lengthencodings,IEEETrans.InformationTheory,Vol.12,No.3,Jul1966,pp.399-401.57Golomb編碼m個(gè)符號(hào)分組的具體實(shí)現(xiàn)把每個(gè)x

表示為

58商xq：用一元碼表示余數(shù)xr：“固定長(zhǎng)度”二進(jìn)制碼當(dāng)m=2k

時(shí)，k比特二進(jìn)制m=8：000,001,…,111當(dāng)m≠2k

時(shí)，k=log2m≤2k–m時(shí)，k-1比特>2k-m時(shí)，k比特，以k個(gè)1結(jié)束。m=5：00,01,10,110,111Golomb編碼Golomb編碼選擇整數(shù)因子ρ≈1/2采用一元碼對(duì)商xq

進(jìn)行最佳編碼采用修正的二進(jìn)制碼對(duì)余數(shù)xr

進(jìn)行編碼，碼字長(zhǎng)度為連接xq和xr的比特在實(shí)際中，常用m=2k，

因此，用固定碼字長(zhǎng)度log2m對(duì)余數(shù)xr編碼Golomb碼舉例59Golomb編碼Golomb碼舉例m=5的Golomb碼（Golomb-5）60一元碼定長(zhǎng)碼第一組第二組第三組Golomb編碼Golomb碼舉例

m較小，Golomb碼初始很短，但增長(zhǎng)很快，適合RLE中ρ較小，即大游程很少的情況，此時(shí)小游程多，對(duì)應(yīng)著開(kāi)始時(shí)較短的Golomb碼。m較大，初始Golomb碼很長(zhǎng)，但增長(zhǎng)很慢，適合RLE中ρ較大，即大游程較多的情況，對(duì)應(yīng)著開(kāi)始時(shí)就較長(zhǎng)的Golomb碼，平均碼長(zhǎng)短。61xm=1m=2m=3m=411001010001211010001101031110101100011411110110010101000511111011011011100161111110111001100101071111111011101110101011811111111011110011011110

00911111111101111011110011001Golomb-Rice碼特定的Golomb碼：m=2k余數(shù)r為n的k個(gè)低位比特m=8：62指數(shù)Golomb碼（Exp-Golomb）Golomb碼將符號(hào)分為等大小的組在Exp-Golomb碼中，組的大小呈指數(shù)增長(zhǎng)，但碼字仍然包括兩部分：（一元碼，固定長(zhǎng)度碼）63Golomb編碼Golomb參數(shù)的確定針對(duì)ρ>1/2的幾何信源，為了得到最佳一元碼，前述把每個(gè)x

表示為

新的隨機(jī)變量xq采用一元碼編碼，xq的分布為對(duì)比x

的幾何分布，新變量xq

是參數(shù)為ρm

的幾何分布，因此，若ρm≤1/2，則一元碼是xq的最佳碼。64Golomb編碼Golomb參數(shù)的估計(jì)實(shí)際中對(duì)于給定的數(shù)據(jù)，怎樣找到最佳的參數(shù)m，使得ρm≤1/2?

根據(jù)過(guò)去的數(shù)據(jù)估計(jì)幾何分布參數(shù)ρ：65Golobm碼最佳性能準(zhǔn)則對(duì)每個(gè)像素來(lái)講，需要兩個(gè)對(duì)數(shù)和一個(gè)除法運(yùn)算，計(jì)算代價(jià)太大。JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPractice，p54Golomb編碼Golomb參數(shù)估計(jì)的簡(jiǎn)化當(dāng)E(X)>>1時(shí)，即假設(shè)ρ≈1，1-ρ≈0，則近似66Golobm碼最佳性能準(zhǔn)則合理設(shè)置，即使E[X]>>1不成立自適應(yīng)Golomb編碼自適應(yīng)Golomb編碼在JPEG-LS中的應(yīng)用JPEG-LS:無(wú)失真JPEG（LosslessJPEG）JPEG中也有無(wú)失真算法，但沒(méi)有被廣泛采用67采用的技術(shù)：預(yù)測(cè)自適應(yīng)Golomb碼上下文自適應(yīng)編碼游程編碼Elias編碼Huffman碼的局限性信源符號(hào)的概率嚴(yán)重不對(duì)稱時(shí)，Huffman碼效率變得不高，采用Huffman矢量(擴(kuò)展)碼解決此問(wèn)題，但也受限于指數(shù)增加的實(shí)現(xiàn)復(fù)雜度。另外，當(dāng)信源的統(tǒng)計(jì)特性不知道或者是可變的，對(duì)實(shí)時(shí)應(yīng)用來(lái)講，自適應(yīng)Huffman碼太復(fù)雜。因此，希望找到一種編碼方法，它的平均碼長(zhǎng)接近熵，并提供簡(jiǎn)單的機(jī)制來(lái)處理非平穩(wěn)信源，它的復(fù)雜度和編碼符號(hào)數(shù)量成線性關(guān)系。

流行的算術(shù)編碼具有上述特性最初的算術(shù)編碼思想源自PeterElias，稱為Elias編碼。（

也是Fano在MIT第一個(gè)信息論課程的學(xué)生，還有Huffman）Pasco和Rissanen于1976年提出了第一個(gè)實(shí)用的現(xiàn)代算術(shù)編碼方法，解決了有限精度問(wèn)題。68Elias編碼Eliascoding(伊萊亞斯編碼)一種對(duì)概率（條件概率）事件x

的熵編碼算法x用單位區(qū)間[0,1]的某個(gè)子區(qū)間表示子區(qū)間的寬度約等于概率p(x)x

的子區(qū)間可由遞歸的細(xì)分算法確定，當(dāng)前符號(hào)的

子區(qū)間一定落在前一個(gè)符號(hào)的區(qū)間內(nèi)。x由子區(qū)間內(nèi)最短的二進(jìn)制分?jǐn)?shù)表示0.b0b1…bL-1二進(jìn)制分?jǐn)?shù)一定落在寬度為p(x)的子區(qū)間內(nèi)，分?jǐn)?shù)的長(zhǎng)度為二進(jìn)制小數(shù)點(diǎn)后L比特：Elias碼字可迭代構(gòu)造69SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzElias編碼無(wú)記憶二進(jìn)制信源的Elias編碼70編碼起始點(diǎn)(區(qū)間下限）編碼結(jié)束點(diǎn)(區(qū)間上限）區(qū)間寬度anElias編碼無(wú)記憶三元信源的Elias編碼71Elias編碼子區(qū)間中二進(jìn)制分?jǐn)?shù)的選擇用一個(gè)二進(jìn)制分?jǐn)?shù)唯一地標(biāo)識(shí)區(qū)間[cN,cN+aN]比特串的長(zhǎng)度Ln

是滿足2-Ln<an

的任何整數(shù)，即比特串72JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPractice，p39Elias編碼無(wú)記憶信源的Elias編碼算法73編碼算法EncodingAlgorithm給定N個(gè)符號(hào)的序列{x0,…,xN-1}迭代初始化，區(qū)間寬度a0=1，區(qū)間下邊界c0=0對(duì)每個(gè)n=0,1,…,N-1，更新參數(shù)

區(qū)間寬度：an+1=anpX(xn)

區(qū)間起始：cn+1=cn+anPX(xn)計(jì)算碼字長(zhǎng)度L

=-log2aN+1傳輸L個(gè)比特的碼字b(L)，表示v=cN2L2-L

的小數(shù)部分。

Elias編碼非平穩(wěn)信源的Elias編碼74Markov隨機(jī)過(guò)程的Elias編碼Elias編碼75Elias編碼解碼從第一個(gè)符號(hào)開(kāi)始，Elias碼字可以一個(gè)符號(hào)接著一個(gè)符號(hào)地解碼.76解碼算法DecodingAlgorithm接收到一個(gè)L比特的碼字b(L)={b0,…,bL-1}確定區(qū)間表示迭代初始化，區(qū)間寬度a0=1，區(qū)間下邊界c0=0對(duì)每個(gè)n=0,1,…,N-1，更新參數(shù)對(duì)每個(gè)符號(hào)xi，確定區(qū)間In+1(xi)

區(qū)間寬度：an+1(xi)=anp(xi)

區(qū)間起始：cn+1(xi)=cn+anP(xi)選擇v∈In+1(xi)的符號(hào)xi∈Xn

，

并置an+1=an+1(xi),cn+1=cn+1(xi)自適應(yīng)Elias編碼Elias編解碼器采用了相同的區(qū)間迭代細(xì)化算法，因此，Elias編碼提供了簡(jiǎn)單的機(jī)制去適應(yīng)未知或非平穩(wěn)特性的信源。概念上，對(duì)于每個(gè)信源符號(hào)xn，編解碼器都可同時(shí)基于已編碼的符號(hào)x0~xn-1

估計(jì)概率函數(shù)p(xn|x0,…xn-1)信源可以建模為一個(gè)獨(dú)立隨機(jī)變量過(guò)程或Markov過(guò)程對(duì)于簡(jiǎn)單的獨(dú)立隨機(jī)變量過(guò)程，特定符號(hào)xn

的概率函數(shù)p(xn)可以近似為前Nw

個(gè)已編碼符號(hào)序列內(nèi)出現(xiàn)的相對(duì)頻率。間隔大小Nw

在快速適應(yīng)和精確概率估計(jì)之間折中同樣的方法也可應(yīng)用于高階概率模型，例如馬爾可夫模型。在這種情況下，條件概率密度函數(shù)pdf近似相應(yīng)的相對(duì)條件頻率。77Elias編碼Elias編碼效率每個(gè)符號(hào)的平均碼字長(zhǎng)度為利用不等式x≥x

和x

<x+1，可得如果編碼符號(hào)的數(shù)量N趨于無(wú)窮大，則平均碼長(zhǎng)逼近熵率注意：Elias碼并不保證是前綴獨(dú)立（prefixfree），即一個(gè)特定符號(hào)序列的碼字可能是其它符號(hào)序列的碼字前綴。因此，上述Elias碼只能用于解碼端已知碼字長(zhǎng)度的情況下。如果所有的碼字長(zhǎng)度增加1，就可以構(gòu)造前綴的Elias碼，即78SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，p4979算術(shù)編碼Elias編碼對(duì)長(zhǎng)符號(hào)串不切實(shí)際：區(qū)間寬度和邊界表示需要的算術(shù)精度隨著字符串的長(zhǎng)度而增長(zhǎng)，且沒(méi)上限。算術(shù)編碼(arithmeticcoding)Elias碼的有限（固定）精度實(shí)現(xiàn)算術(shù)編碼和解碼過(guò)程都只涉及算術(shù)運(yùn)算（加、減、乘、除）算術(shù)編碼是另一種常用的變字長(zhǎng)編碼也是利用信源概率分布特性、能夠趨近熵極限的編碼方法。它與Huffman一樣，也是對(duì)出現(xiàn)概率大的符號(hào)賦予短碼，對(duì)概率小的符號(hào)賦予長(zhǎng)碼。但它的編碼過(guò)程與Huffman編碼卻不相同，而且在信源概率分布比較均勻或非常劇烈的情況下其編碼效率高于Huffman編碼。它和Huffman編碼最大的區(qū)別在于它不是使用整數(shù)碼。算術(shù)編碼越來(lái)越流行（在很多標(biāo)準(zhǔn)中被廣泛采用），適合的場(chǎng)合：小字母表：如二進(jìn)制信源概率分布不均衡建模與編碼分開(kāi)算術(shù)編碼算術(shù)編碼的有限精度表示假設(shè)概率密度函數(shù)p(a)和累積概率密度函數(shù)P(a)都用二進(jìn)制小數(shù)點(diǎn)后V個(gè)比特表示，即

pV(a)和PV(a)是V比特正整數(shù)設(shè)計(jì)一個(gè)算術(shù)編碼的關(guān)鍵是當(dāng)區(qū)間寬度aN+1

滿足下式時(shí)，Elias碼仍是可譯碼的：保證第In+1

個(gè)區(qū)間處于第In個(gè)區(qū)間之內(nèi)上述保證第In+1

個(gè)區(qū)間的寬度小于第In個(gè)區(qū)間第In+1

個(gè)區(qū)間的起始位置位于第In個(gè)區(qū)間之內(nèi)，因此有結(jié)論：如果在每次迭代中向零方向舍入，用有限精度表示區(qū)間寬度an，則Elias碼仍是可譯的。80SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz兩個(gè)概率之和一定位于單位區(qū)間內(nèi)，即小于等于1.本來(lái)應(yīng)該an+1=anp(xn)，由于要用有限精度表示，做向零舍入，變?yōu)樾∮诘扔?。算術(shù)編碼算術(shù)編碼的有限精度表示用U比特整數(shù)An

表示區(qū)間寬度an：

整數(shù)zn

≥UAn

嚴(yán)格限制在范圍：2U-1

≤An<2U為適當(dāng)近似a0=1，取A0=2U-1，z0=U區(qū)間寬度an

最大精度是U比特區(qū)間寬度an細(xì)分的迭代公式

yn

是簡(jiǎn)單的比特右移參數(shù)0≤yn

≤V為滿足2U-1

≤An<2U

的約束，比特位移參數(shù)yn

選擇為yn

的值可通過(guò)一系列的比較運(yùn)算來(lái)確定上述迭代公式保證滿足上頁(yè)中的基本規(guī)則0<an+1

≤an.p(xn)上式中運(yùn)算符x.2-y是對(duì)二進(jìn)制數(shù)x

進(jìn)行簡(jiǎn)單的二進(jìn)制右移y位81算術(shù)編碼有限精度算術(shù)編碼用有限精度表示區(qū)間寬度an

，其對(duì)區(qū)間下邊界cn

的影響如何？二進(jìn)制小數(shù)點(diǎn)后有(zn-U)個(gè)0比特，隨后是（U+V）比特的整數(shù)，表示AnPv(xn)部分。區(qū)間寬度用U比特精度表示，下舍入。累計(jì)概率用V比特精度近似82至多(U+V)個(gè)LSB發(fā)生變化，進(jìn)位位可能會(huì)影響到MSB。

算術(shù)編碼有限精度算術(shù)編碼區(qū)間下邊界的表示分為4類尾比特(trailingbits)：小數(shù)點(diǎn)后(zn+V)個(gè)比特后面的那些0，但可能被隨后的區(qū)間更新修改；活性比特

(activebits)：由區(qū)間邊界更新cn+1=cn+anP(xn)直接修改；未定比特(outstandingbits)：由0或多個(gè)1組成（若是多個(gè)1，以0比特為先導(dǎo)），它可能被activebits的進(jìn)位位修改，故還未確定最終數(shù)值；確定比特(settledbits)：小數(shù)點(diǎn)后的(zn–rn-U)個(gè)比特在后面的區(qū)間更新中不再修改，甚至產(chǎn)生最終碼字的舍入處理也不能改變這些比特，因?yàn)閚后所有的區(qū)間In+k都位于區(qū)間In

內(nèi)。

最終輸出碼字的比特長(zhǎng)度為輸出碼字的長(zhǎng)度大于等于“確定比特”的位數(shù)（zn-U–rn），因此，一旦成為了“確定比特”就可立即傳輸它們。為了表示區(qū)間的下邊界cn，存儲(chǔ)“活性比特”和“未定比特”就足夠了。8384算術(shù)編碼算術(shù)編碼：從另一種角度對(duì)很長(zhǎng)的信源符號(hào)序列進(jìn)行有效編碼對(duì)整個(gè)序列信源符號(hào)串產(chǎn)生一個(gè)唯一的標(biāo)識(shí)（

tag）直接對(duì)序列進(jìn)行編碼（不是碼字的串聯(lián)）：非分組碼不用對(duì)該長(zhǎng)度所有可能的序列編碼標(biāo)識(shí)是[0,1)之間的一個(gè)數(shù)（二進(jìn)制小數(shù)，可作為序列的二進(jìn)制編碼）原理：算術(shù)編碼是把各符號(hào)出現(xiàn)的概率表示在單位概率[0，1]區(qū)間之中，區(qū)間的寬度代表概率值的大小。符號(hào)出現(xiàn)的概率越大對(duì)應(yīng)于區(qū)間愈寬；符號(hào)出現(xiàn)概率越小對(duì)應(yīng)于區(qū)間愈窄。

符號(hào)對(duì)應(yīng)的區(qū)間由一個(gè)“標(biāo)識(shí)”來(lái)識(shí)別，區(qū)間中的任意數(shù)值都可以作為“標(biāo)識(shí)”，通常選擇區(qū)間的低端或者中點(diǎn)作為“標(biāo)識(shí)”。算術(shù)編碼包括生成“標(biāo)識(shí)”和對(duì)“標(biāo)識(shí)”進(jìn)行二進(jìn)制編碼兩個(gè)過(guò)程，在實(shí)際中，這兩個(gè)過(guò)程可能合成一個(gè)來(lái)完成。85算術(shù)編碼－原理符號(hào)序列S3S3S2S4……為例S1S2S3S4S1S2S3S4S1S2S3S401/83/87/81.000.0010.0110.1111.00.0110.1110.01110.10010.1101在算術(shù)編碼中通常采用二進(jìn)制分?jǐn)?shù)表示概率，每個(gè)符號(hào)所對(duì)應(yīng)的概率區(qū)間都是半開(kāi)區(qū)間，即該區(qū)間包括左端點(diǎn)，而不包括右端點(diǎn)，如S1對(duì)應(yīng)[0,0.001)，S2

對(duì)應(yīng)[0.001,0.01)等。86算術(shù)編碼－原理符號(hào)序列S3S3S2S4……的第一個(gè)符號(hào)S3用指向第3個(gè)子區(qū)間的標(biāo)識(shí)（指針）來(lái)代表，可以用這個(gè)區(qū)間內(nèi)的任意一個(gè)小數(shù)來(lái)表示這個(gè)標(biāo)識(shí)（指針），這里約定這個(gè)區(qū)間的左端點(diǎn)代表這個(gè)指針，因此得到第一個(gè)碼字.011。后續(xù)的編碼將在前面編碼指向的子區(qū)間內(nèi)進(jìn)行，將[.011,.111]區(qū)間再按概率大小劃分為4份，第二個(gè)符號(hào)S3

指向.1001(S3

區(qū)間的左端），輸出碼字變?yōu)?1001。然后，S3

對(duì)應(yīng)的子區(qū)間又被劃分為4份，開(kāi)始對(duì)第三個(gè)符號(hào)S2

進(jìn)行編碼，…….算術(shù)編碼產(chǎn)生的碼字實(shí)際上是一個(gè)二進(jìn)制數(shù)值的標(biāo)識(shí)（指針），指向所編的符號(hào)對(duì)應(yīng)的概率區(qū)間。87算術(shù)編碼－基本法則兩個(gè)參量：編碼點(diǎn)（指針?biāo)柑帲〤和區(qū)間寬度A。初始狀態(tài)編碼點(diǎn)（指針?biāo)柑帲〤=0

區(qū)間寬度A=1.0新編碼點(diǎn)C=原編碼點(diǎn)C＋原區(qū)間A×Pi

新區(qū)間A=原區(qū)間A×pi

序列S3S3S2S4……的編碼過(guò)程：第1個(gè)符號(hào)(S3):C=0+1×.011=.011

A=1×.1=.1

第2個(gè)符號(hào)(S3):C=.011+.1×.011=.1001

A=.1×.1=.01第3個(gè)符號(hào)(S2):C=.1001+.01×.001=.10011A=.01×.01=.0001第4個(gè)符號(hào)(S4):C=.10011+.0001×.111=.1010011（輸出的碼字）

A=.0001×.001=.0000001符號(hào)Si

對(duì)應(yīng)的累積概率符號(hào)Si

對(duì)應(yīng)的概率最后區(qū)間的一個(gè)數(shù)輸出88算術(shù)編碼－解碼算法解碼采取與編碼過(guò)程相反的步驟把接收到的碼字串指向其對(duì)應(yīng)的子區(qū)間，得到此子區(qū)間對(duì)應(yīng)的符號(hào)，即為解碼后的符號(hào)。即從碼字串中減去已解碼符號(hào)的子區(qū)間的左端點(diǎn)的數(shù)值（累積概率），并將差值除以該子區(qū)間的寬度（概率值），得到新的碼字串。上述例子當(dāng)收到字碼串(.1010011)時(shí)，其指向子區(qū)間[.011,.111]，對(duì)應(yīng)于S3，因此，得到第1個(gè)符號(hào)為S3。新碼字串：（.1010011-.011)÷(.1)=0.100011，新碼字串仍然指向子區(qū)間[.011,.111]，因此，第2個(gè)符號(hào)仍為S3。其它符號(hào)依次類推注意：算術(shù)編碼中的進(jìn)位在Huffman編碼中，后續(xù)符號(hào)產(chǎn)生的碼字只是簡(jiǎn)單地附加到先前的碼字串之后，并不改變已有的碼字串。在算術(shù)編碼中，由于新編碼點(diǎn)C表達(dá)式中乘法、加法運(yùn)算而產(chǎn)生進(jìn)位，從而與Huffman不同。例如上述的第3個(gè)符號(hào)后碼字串為.10011，但第4個(gè)符號(hào)后碼字串變?yōu)?1010011，二進(jìn)制算術(shù)編碼二進(jìn)制算術(shù)編碼

輸入的字符只有兩種，如果信源字符集內(nèi)包含有多個(gè)字符，則先將這些字符經(jīng)過(guò)二進(jìn)判決，變成二進(jìn)制字符串。這個(gè)轉(zhuǎn)換過(guò)程稱為二值化(binarization)，二進(jìn)制序列稱為bins。圖像和視頻中最流行的算術(shù)編碼類型減少了復(fù)雜度便于自適應(yīng)編碼，因?yàn)槎M(jìn)制概率密度函數(shù)估計(jì)簡(jiǎn)單，相比于多進(jìn)制著名的應(yīng)用實(shí)例：JPEG2000的MQ-coder，H.264/AVC的M-coder兩個(gè)符號(hào)構(gòu)成的序列的編碼與算術(shù)編碼原理相同，仍是不斷劃分概率子區(qū)間的遞歸過(guò)程。在兩個(gè)輸入字符中，出現(xiàn)概率較大的為MPS(MoreProbableSymbol)，MPS的概率為Pe；出現(xiàn)概率較小的為L(zhǎng)PS(LessProbableSymbol)，LPS的概率為Qe，Pe=1-Qe。編碼初始化子區(qū)間為[0，1]，MPS與LPS分配如圖所示89QePeLPSMPS90編碼時(shí)，設(shè)置兩個(gè)專用寄存器（C，A）

C寄存器的值為編碼點(diǎn)（指針?biāo)柑帲?/p>

A寄存器的值為子區(qū)間的寬度(該寬度恰好是已輸入符號(hào)串的概率)初始化時(shí)：C=0A=1隨著被編碼數(shù)據(jù)源輸入，C和A的內(nèi)容按以下編碼規(guī)則修正：

當(dāng)?shù)透怕史?hào)LPS到來(lái)時(shí)：(LPS的概率為Qe，累積概率為0)C=CA=AQe

當(dāng)高概率符號(hào)MPS到來(lái)時(shí)：(LPS的概率為Pe，累積概率為Qe)C=C+AQeA=Ape=A（1-Qe）二進(jìn)制算術(shù)編碼－編碼規(guī)則算術(shù)編碼的基本法則：新編碼點(diǎn)C=原編碼點(diǎn)C＋原區(qū)間A×Pi

新區(qū)間A=原區(qū)間A×pi符號(hào)Si

對(duì)應(yīng)的累積概率符號(hào)Si

對(duì)應(yīng)的概率QePeLPSMPS91第1個(gè)符號(hào)1為MPS

C=C+AQe=0+10.001=0.001

A=APe=10.111=0.1110.0010.111二進(jìn)制算術(shù)編碼－編碼舉例例:信源符號(hào)序列110111110為L(zhǎng)PSQe=1/8=（0.001）b1為MPSPe=7/8=（0.111）b初始狀態(tài)：C=0(子區(qū)間起始位置)A=1（子區(qū)間寬度）第2個(gè)符號(hào)1仍為MPS

C=C+AQe=0.001+0.1110.001=0.001111

A=APe=0.1110.111=0.1100010.0011110.1100010192第3個(gè)符號(hào)0為L(zhǎng)PSC=C=0.001111A=AQe=0.1100010.001=0.000110001繼續(xù)下去…….最后得C=0.000001A=0.000011結(jié)果二進(jìn)制算術(shù)編碼－編碼舉例0.0011110.000110001頭CA尾頭0.000001（C）+0.000011（A）尾0.000000頭<0.0101<尾傳送碼字為0101編碼輸出可以是最后一個(gè)編碼區(qū)間中的任意數(shù)值，但為了取得最好的編碼效率，選擇的小數(shù)應(yīng)有最短的比特長(zhǎng)度，但要是唯一的“標(biāo)識(shí)”。93二進(jìn)制算術(shù)編碼－編碼舉例上述算術(shù)編碼過(guò)程94解碼：按Qe、Pe

分成兩個(gè)子區(qū)間，判斷被解碼的碼字落在哪個(gè)區(qū)間，并賦予對(duì)應(yīng)符號(hào)。設(shè)c’=（0.0101)b

是被解碼的值，初始值A(chǔ)=1Qe=0.001二進(jìn)制算術(shù)編碼－解碼當(dāng)c’落在QeA~A之間，解碼符號(hào)為D=1C’=C’-QeAA=A（1-Qe）當(dāng)c’落在0~QeA之間，解碼符號(hào)為D=0C’=C’A=QeA

c’=0.0101

落在QeA-A之間，解碼符號(hào)為D=1

c’=c’-QeA=0.0101-0.001=0.0011A=A（1-Qe）=0.111

c’=0.0011

落在QeA-A之間，解碼符號(hào)為D=1

c’=c’-QeA=0.0011-0.000111=0.000101A=A（1-Qe）=0.1110.111=0.110001

c’=0.000101

落在0-QeA之間，解碼符號(hào)為D=0c’=c’=0.000101A=AQe=0.1100010.001=0.000110001

95二進(jìn)制算術(shù)編碼－解碼96算術(shù)編碼的唯一性和效率算術(shù)編碼產(chǎn)生的標(biāo)識(shí)可以唯一表示一個(gè)序列，這意味著該標(biāo)識(shí)的二進(jìn)制表示為序列的唯一二進(jìn)制編碼二進(jìn)制表示的精度可以是無(wú)限長(zhǎng)：保證唯一性但不夠有效為了保證有效性，可以截?cái)喽M(jìn)制表示，但如何保證唯一性？答案：為了保證唯一性和有效性，需取小數(shù)點(diǎn)后LN

位數(shù)字作為信源序列的碼字，其中注意：aN

為最后區(qū)間的寬度，也是該符號(hào)串的概率符合概率匹配原則：出現(xiàn)概率較大的符號(hào)取較短的碼字，而對(duì)出現(xiàn)概率較小的符號(hào)取較長(zhǎng)的碼字97算術(shù)編碼的唯一性和效率長(zhǎng)度為N的序列的算術(shù)編碼的平均碼長(zhǎng)為：算術(shù)編碼的效率高：當(dāng)信源符號(hào)序列很長(zhǎng)，平均碼長(zhǎng)接近信源的熵(獨(dú)立同分布(iid)信源)H(XN)=NH(X)算術(shù)編碼的唯一性和效率有限精度算術(shù)編碼的效率損失對(duì)同一個(gè)序列進(jìn)行編碼，相比于Elias編碼，使用有限精度表示的算術(shù)編碼增加了碼字長(zhǎng)度，增加的碼率為假設(shè)在算術(shù)編碼中，令pmin

表示最小的真實(shí)概率p(x)，真實(shí)的概率p(x)用V比特近似，區(qū)間寬度an

用U比特近似，則可以證明[Wiegand]，每個(gè)符號(hào)的碼字長(zhǎng)度增加的上限為：例如：N=1000個(gè)符號(hào)，U=12，V=16，pmin=0.02，

相對(duì)于Elias編碼，算術(shù)編碼每個(gè)符號(hào)增加的碼字長(zhǎng)度保證小于0.003bit/symbol。98SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz99自適應(yīng)算術(shù)編碼統(tǒng)計(jì)編碼技術(shù)需要利用信源符號(hào)的概率，獲得這個(gè)概率的過(guò)程稱為建模。不同準(zhǔn)確度（通常也是不同復(fù)雜度）的模型會(huì)影響算術(shù)編碼的效率。建模的方式：靜態(tài)建模：在編碼過(guò)程中信源符號(hào)的概率不變。但一般來(lái)說(shuō)事先知道精確的信源概率是很難的，而且是不切實(shí)際的。自適應(yīng)動(dòng)態(tài)建模：信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改。當(dāng)壓縮序列時(shí)，不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過(guò)程中估算概率。算術(shù)編碼很容易與自適應(yīng)建模相結(jié)合。100自適應(yīng)算術(shù)編碼后向自適應(yīng)算術(shù)編碼：在編碼之前，假設(shè)每個(gè)信源符號(hào)的概率相等（如都等于1），并計(jì)算累積概率從輸入流中讀入一個(gè)字符，并對(duì)該符號(hào)進(jìn)行算術(shù)編碼更新該符號(hào)的概率，并更新累積概率由于在解碼之前，解碼器不知道是哪個(gè)信源符號(hào)，所以概率更新應(yīng)該在解碼之后進(jìn)行對(duì)應(yīng)的，編碼器也應(yīng)在編碼后進(jìn)行概率更新為了提高解碼器的搜索效率，信源符號(hào)的概率、累積概率表按符號(hào)出現(xiàn)概率降序排列在自適應(yīng)算術(shù)編碼中，可以用平衡二叉樹(shù)來(lái)快速實(shí)現(xiàn)對(duì)概率和