信息論與編碼(清華出版社)第5章信源編碼-Qtech

1本節(jié)內(nèi)容編碼的定義無失真信源編碼定長編碼定理變長編碼定理2第5章信源編碼

編碼分為信源編碼和信道編碼，其中信源編碼又分為無失真和限失真。一般稱無失真信源編碼定理為第一極限定理；信道編碼定理（包括離散和連續(xù)信道）稱為第二極限定理；限失真信源編碼定理稱為第三極限定理。

3第5章信源編碼由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。

4第5章信源編碼信源編碼的基本途徑有兩個：使序列中的各個符號盡可能地互相獨(dú)立，即解除相關(guān)性；使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。5第5章信源編碼信源編碼的基礎(chǔ)是信息論中的兩個編碼定理：無失真編碼定理限失真編碼定理

無失真編碼只適用于離散信源

對于連續(xù)信源，只能在失真受限制的情況下進(jìn)行限失真編碼

6第5章信源編碼本章討論離散信源編碼，首先從無失真編碼定理出發(fā)，重點(diǎn)討論以香農(nóng)碼、費(fèi)諾碼和霍夫曼碼為代表的最佳無失真碼。然后介紹限失真編碼定理。最后簡單介紹一些其它常用的信源編碼方法。75.1編碼的定義

信源編碼器信道碼表圖5-1信源編碼器示意圖85.1編碼的定義信源編碼是指信源輸出符號經(jīng)信源編碼器編碼后轉(zhuǎn)換成另外的壓縮符號；無失真信源編碼：可精確無失真地復(fù)制信源輸出地消息。95.1編碼的定義將信源消息分成若干組，即符號序列xi，

xi＝(xi1xi2…xil…xiL)，

xilA={a1，a2，…，ai，…，an}每個符號序列xi依照固定碼表映射成一個碼字yi，

yi＝(yi1yi2…yil…yiL)，

yilB={b1，b2，…，bi，…，bm}這樣的碼稱為分組碼，有時也叫塊碼。只有分組碼才有對應(yīng)的碼表，而非分組碼中則不存在碼表。

105.1編碼的定義如圖5-1所示，如果信源輸出符號序列長度L＝1，信源符號集A(a1，a2，…，an)；信源概率空間為若將信源X通過二元信道傳輸，就必須把信源符號ai變換成由0，1符號組成的碼符號序列，這個過程就是信源編碼。115.1編碼的定義碼可分為兩類：一、固定長度的碼，碼中所有碼字的長度都相同，如表5-1中的碼1就是定長碼二、可變長度碼，碼中的碼字長短不一，如表中碼2就是變長碼。

125.1編碼的定義不同的碼符號序列，如表5-1所示。

表5-1變長碼與定長碼信源符號ai信源符號出現(xiàn)概率p(ai)碼表碼1碼2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)11111135.1編碼的定義（1）奇異碼和非奇異碼

若信源符號和碼字是一一對應(yīng)的，則該碼為非奇異碼。反之為奇異碼。如表5-2中的碼1是奇異碼，碼2是非奇異碼。

145.1編碼的定義表5-2碼的不同屬性信源符號ai符號出現(xiàn)概率p(ai)碼1碼2碼3碼4a11/20011a21/411101001a31/80000100001a41/8110110000001155.1編碼的定義（2）唯一可譯碼

任意有限長的碼元序列，只能被唯一地分割成一個個的碼字，便稱為唯一可譯碼。如，{0,10,11}是唯一可譯碼。165.1編碼的定義唯一可譯碼中又分為非即時碼和即時碼：非即時碼：如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。175.1編碼的定義即時碼：只要收到符號就表示該碼字已完整，可以立即譯碼。即時碼又稱為非延長碼，任意一個碼字都不是其它碼字的前綴部分，亦叫做異前綴碼。185.1編碼的定義碼奇異碼非分組碼分組碼非奇異碼非唯一可譯碼非即時碼即時碼(非延長碼)唯一可譯碼195.1編碼的定義通?？捎么a樹來表示各碼字的構(gòu)成

01

01

01

01010101

0101010101010101二進(jìn)碼樹205.1編碼的定義012012012012012012三進(jìn)制碼樹215.1編碼的定義唯一可譯碼存在的充分和必要條件各碼字的長度Ki應(yīng)符合克勞夫特不等式：

n：信源符號數(shù)；m:進(jìn)制數(shù)。

225.1編碼的定義例：設(shè)二進(jìn)制碼樹中X(a1，a2，a3，a4)，K1＝1，K2＝2，K3＝2，K4＝3，應(yīng)用上述判斷定理：

因此不存在滿足這種Ki的唯一可譯碼。

235.1編碼的定義a1=1

01

01

01a2=01a3=001a4=000{1，01，001，000}

惟一可譯碼；{1，01，101，000}

不是惟一可譯碼；均滿足克勞夫特不等式245.1編碼的定義克勞夫特不等式只是用來說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。255.2無失真信源編碼

信源輸出X＝(X1X2…Xl…XL)，Xl

{a1，a2，…，ai，…，an}編碼為Y＝(Y1Y2…Yk…YkL)，Yk

{b1，b2，…，bj，…，bm}。要求能夠無失真或無差錯地譯碼，同時傳送Y時所需要的信息率最小

265.2無失真信源編碼Yk平均每個符號的最大信息量為logmKL長碼字的最大信息量為KLlogm則傳送一個信源符號需要的信息率平均為

275.2無失真信源編碼所謂信息率最小，就是找到一種編碼方式使最小。無失真信源編碼定理研究的內(nèi)容:最小信息率為多少時，才能得到無失真的譯碼？若小于這個信息率是否還能無失真地譯碼？285.2無失真信源編碼無失真的信源編碼定理定長編碼定理變長編碼定理295.2無失真信源編碼定長編碼定理

K是定值，且惟一可譯碼。30惟一可譯碼的判斷方法首先，觀察是否是非奇異碼。其次，計算是否滿克勞夫特不等式將碼畫成一棵樹圖，觀察是否滿足即時碼的樹圖的構(gòu)造，若滿足則是惟一可譯碼。計算出分組碼中所有可能的尾隨后綴集合F，觀察F中有沒有包含任一碼字，若無則為惟一可譯碼；若有則一定不是惟一可譯碼。31定長編碼定理由L個符號組成的、每個符號的熵為HL(X)的無記憶平穩(wěn)信源符號序列X1X2…Xl…XL，可用KL個符號Y1，Y2，…，Yk，…，（每個符號有m種可能值）進(jìn)行定長編碼。對任意

>0，

>0，只要 則當(dāng)L足夠大時，必可使譯碼差錯小于

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

325.2無失真信源編碼定長編碼定理說明，碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，當(dāng)然條件是L足夠大。

335.2無失真信源編碼反之，當(dāng)時，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零。時，則為臨界狀態(tài)，可能無失真，也可能有失真。345.2無失真信源編碼式中為自信息方差，

為一正數(shù)。當(dāng)和均為定值時，只要L足夠大，Pe可以小于任一正數(shù)

。即，

355.2無失真信源編碼當(dāng)信源序列長度L滿足時，能達(dá)到差錯率要求：

365.2無失真信源編碼在連續(xù)信源的情況下，由于信源的信息量趨于無限，顯然不能用離散符號序列Y來完成無失真編碼，而只能進(jìn)行限失真編碼。375.2無失真信源編碼定義

為編碼效率，即信源的平均符號熵為H(X)，采用平均符號碼長為來編碼，所得的效率。編碼效率總是小于1，且最佳編碼效率為

385.2無失真信源編碼編碼定理從理論上闡明了編碼效率接近1的理想編碼器的存在性，它使輸出符號的信息率與信源熵之比接近于1，即

L取無限長395.2無失真信源編碼例

設(shè)離散無記憶信源概率空間為比特/符號

405.2無失真信源編碼對信源符號采用定長二元編碼，要求編碼效率為90％，若取L＝1，則可算出 ＝2.5590%=2.83比特/符號每個符號用2.83比特進(jìn)行定長編碼，共有

種可能性。那么，信源符號中就有一種符號無對應(yīng)碼字。即使發(fā)生概率最小的a8,其Pe＝0.04太大！415.2無失真信源編碼若要求譯碼錯誤概率

需要同時對100M個信源符號一起編碼！425.2無失真信源編碼變長編碼定理在變長編碼中，碼長K是變化的根據(jù)信源各個符號的統(tǒng)計特性，如概率大的符號用短碼，概率小的用較長的碼，使得編碼后平均碼長降低，從而提高編碼效率。（統(tǒng)計匹配）435.2無失真信源編碼單個符號變長編碼定理：若離散無記憶信源的符號熵為H(X)，每個信源符號用m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式445.2無失真信源編碼

離散平穩(wěn)無記憶序列變長編碼定理：對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式其中

為任意小正數(shù)。455.2無失真信源編碼用變長編碼來達(dá)到相當(dāng)高的編碼效率，一般所要求的符號長度L可以比定長編碼小得多。465.2無失真信源編碼編碼效率總是小于1，可以用它來衡量各種編碼方法的優(yōu)劣。為了衡量各種編碼方法與最佳碼的差距，定義碼的剩余度為

475.2無失真信源編碼例 設(shè)離散無記憶信源的概率空間為485.2無失真信源編碼若用二元定長編碼(0，1)來構(gòu)造一個即時碼：。平均碼長＝1二元碼符號/信源符號495.2無失真信源編碼編碼效率為輸出的信息效率為R＝0.811比特/二元碼符號505.2無失真信源編碼長度為2的信源序列進(jìn)行變長編碼（編碼方法后面介紹），其即時碼如下表aip(ai)即時碼a1a19/160a1a23/1610a2a13/16110a2a21/16111515.2無失真信源編碼二元碼符號/信源序列二元碼符號/信源符號525.2無失真信源編碼編碼效率信息效率R2＝0.961比特/二元碼符號535.2無失真信源編碼信源序列長度增加：L＝3時R3＝0.985比特/二元碼符號

L＝4時R4＝0.991比特/二元碼符號

545.2無失真信源編碼若采用定長二元碼編碼，要求編碼效率達(dá)到96％時，允許譯碼錯誤概率

55L求解的解釋：根據(jù)式(5-2-7)求得：將其代入式（5-2-6），得到：56575.2無失真信源編碼最佳變長編碼

凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼。

585.2無失真信源編碼能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）費(fèi)諾（Fano）哈夫曼（Huffman）等

595.2無失真信源編碼香農(nóng)（Shannon）編碼1.將信源消息符號按其出現(xiàn)的概率大小依次排列2.確定滿足下列不等式的整數(shù)碼長Ki。605.2無失真信源編碼為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號的二進(jìn)制碼字。615.2無失真信源編碼例設(shè)信源共7個符號消息，其概率和累加概率如下表所示。

625.2無失真信源編碼信源消息符號ai符號概率(ai)累加概率Pi-logp(ai)碼字長度Ki碼字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110635.2無失真信源編碼以i=4為例，645.2無失真信源編碼碼元/符號比特/碼元

655.2無失真信源編碼費(fèi)諾編碼方法費(fèi)諾編碼屬于概率匹配編碼(1)將信源消息符號按其出現(xiàn)的概率大小依次排列：(2)將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進(jìn)制碼元“0”和“1”。665.2無失真信源編碼(3)將每一大組的信源符號進(jìn)一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組一個二進(jìn)制符號“0”和“1”。(4)如此重復(fù)，直至每個組只剩下一個信源符號為止。(5)信源符號所對應(yīng)的碼字即為費(fèi)諾碼。675.2無失真信源編碼例對以下信源進(jìn)行費(fèi)諾編碼。

消息符號ai各個消息概率p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114685.2無失真信源編碼

碼元/符號

bit/符號

695.2無失真信源編碼

哈夫曼編碼方法(1)將信源消息符號按其出現(xiàn)的概率大小依次排列，(2)取兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進(jìn)符號的字母重新排隊。705.2無失真信源編碼(3)對重排后的兩個概率最小符號重復(fù)步驟(2)的過程。(4)不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。(5)從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。715.2無失真信源編碼例對以下信源進(jìn)行哈夫曼編碼

信源符號ai概率p(ai)碼字Wi碼長Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114725.2無失真信源編碼0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.01010101010101735.2無失真信源編碼

碼元/符號

bit/符號

745.2無失真信源編碼哈夫曼編碼方法得到的碼并非唯一的每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1是可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度。755.2無失真信源編碼對信源進(jìn)行縮減時，兩個概率最小的符號合并后的概率與其它信源符號的概率相同時，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。765.2無失真信源編碼例設(shè)有離散無記憶信源775.2無失真信源編碼信源符號ai概率p(ai)碼字Wi1碼長Ki1碼字Wi2碼長K’i2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113

其有兩種哈夫曼編碼方法：785.2無失真信源編碼0.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10101010101010101795.2無失真信源編碼

碼元/符號

805.2無失真信源編碼815.2無失真信源編碼

進(jìn)行哈夫曼編碼時，為得到碼方差最小的碼，應(yīng)使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。

825.2無失真信源編碼哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；縮減信源的最后二個碼字總是最后一位不同，從而保證了哈夫曼碼是即時碼。835.3限失真信源編碼定理

信息率失真函數(shù)給出了失真小于D時所必須具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的失真小于D。845.3限失真信源編碼定理限失真信源編碼定理：設(shè)離散無記憶信源X的信息率失真函數(shù)R(D)，則當(dāng)信息率R>R(D)，只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D＋

，

為任意小的正數(shù)。反之，若R<R(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。855.3限失真信源編碼定理如果是二元信源，對于任意小的

，每一個信源符號的平均碼長滿足如下公式

865.3限失真信源編碼定理在失真限度內(nèi)使信息率任意接近R(D)的編碼方法存在。然而，要使信息率小于R(D)，平均失真一定會超過失真限度D。對于連續(xù)平穩(wěn)無記憶信源，無法進(jìn)行無失真編碼，在限失真情況下，有與上述定理一樣的編碼定理。875.3限失真信源編碼定理限失真信源編碼定理只能說明最佳編碼是存在的，而具體構(gòu)造編碼方法卻一無所知。因而就不能象無損編碼那樣從證明過程中引出概率匹配的編碼方法。一般只能從優(yōu)化的思路去求最佳編碼。迄今尚無合適的可實現(xiàn)的編碼方法可接近R(D)這個界。885.4常用信源編碼方法簡介游程編碼在二元序列中，連0段稱為0游程連1段稱為1游程000101110010001可變換成下列游程序列：3113213895.4常用信源編碼方法簡介若已知二元序列以0起始，從游程序列很容易恢復(fù)成原來的二元序列；游程序列是多元序列，各長度可按霍夫曼編碼或其它方法處理以達(dá)到壓縮碼率的目的。905.4常用信源編碼方法簡介多元序列也存在相應(yīng)的游程序列；多元序列變換成游程序列再進(jìn)行壓縮編碼沒有多大意義；游程編碼只適用于二元序列，對于多元信源，一般不能直接利用游程編碼。915.4常用信源編碼方法簡介冗余位編碼，——游程編碼在多元信源的應(yīng)用925.4常用信源編碼方法簡介如下多元序列x1，x2，…，xm1，y，y，…，y，xm1+1，xm1+2，…x

m2，y，y，…X為信息位，取值于m元符號集；y為冗余位，可全為0，無需傳送在接收端也可恢復(fù)。此多元序列可以用下面序列表示：

111，…，100，…，000111，…，111000x1，x2，…，xm1，x

m1+1，x

m1+2…x

m2，…1表示信息位，0表示冗余位935.4常用信源編碼方法簡介算術(shù)編碼非分組碼的編碼方法之一——算術(shù)碼94算術(shù)編碼研究的目的和意義各種媒體信息（圖像，動態(tài)視頻等）數(shù)據(jù)量非常之大。例如：一幅640x480分辨率的24位真彩色圖像的數(shù)據(jù)量約力900kb；一個100Mb的硬盤只能存儲約l00幅靜止圖像畫面。數(shù)據(jù)量不僅超出了計算機(jī)的存儲和處理能力，更是當(dāng)前通信信道的傳輸速率所不及的。為了存儲、處理和傳輸多媒體數(shù)據(jù)，必須進(jìn)行壓縮。語音的數(shù)據(jù)量較小，且基本壓縮方法己經(jīng)成熟；目前的數(shù)據(jù)壓縮研究主要集中于圖像和視頻信號的壓縮方面。圖像壓縮技術(shù)、視頻技術(shù)與網(wǎng)絡(luò)技術(shù)相結(jié)合的應(yīng)用前景十分可觀。研究算術(shù)編碼以更好的利用它是非常必要的。算術(shù)編碼作為一種高效的數(shù)據(jù)編碼方法在文本，圖像，音頻等壓縮中有廣泛的應(yīng)用。95算術(shù)編碼研究的目的和意義根據(jù)解碼后數(shù)據(jù)與原始數(shù)據(jù)是否完全一致進(jìn)行分類，數(shù)據(jù)壓縮方法一般分為兩類：①無損壓縮，即解碼圖像與原始圖像嚴(yán)格相同，壓縮比大約在2：1－5：1之間，如霍夫曼編碼，算術(shù)編碼等；②有損編碼，即還原圖像與原始圖像存在一定的誤差，但視覺效果一般可以接受，壓縮比可以從幾倍到上百倍，如：PCM編碼，預(yù)測編碼、變換編碼等。算術(shù)編碼作為一種高效的數(shù)據(jù)編碼方法在文本，圖像，音頻：等壓縮中有廣泛的應(yīng)用。它是一種到目前為止編碼效率最高的統(tǒng)計熵編碼方法,它比著名的Huffman編碼效率提高10％左右。96算術(shù)編碼的原理根據(jù)信源可能發(fā)現(xiàn)的不同符號序列的概率，把[0，1]區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好是各符號序列的概率；信源發(fā)出的不同符號序列將與各子區(qū)間一一對應(yīng)；每個子區(qū)間內(nèi)的任意一個實數(shù)都可以用來表示對應(yīng)的符號序列，這個數(shù)就是該符號序列所對應(yīng)的碼字。975.4常用信源編碼方法簡介把區(qū)間[0，1)分割成許多小區(qū)間，每個小區(qū)間的長度等于各序列的概率pr，小區(qū)間內(nèi)的任一點(diǎn)可用來代表這序列;

0(P1)P2P3P4P5……1

……p1

p2p3p4985.4常用信源編碼方法簡介0(P1)P2P3P4P5……1

……p1

p2p3p4

代表大于或等于的最小整數(shù)。把累積概率P(S)寫成二進(jìn)位的小數(shù)，取其前L位;如果有尾數(shù)，就進(jìn)位到第L位，這樣得到一個數(shù)C；

995.4常用信源編碼方法簡介例如P(S)＝0.10110001，p(S)=1/17，則L＝5（？）， 得C＝0.10111這個C就可作為S的碼字編碼效率很高，當(dāng)序列很長時，可達(dá)到概率匹配。平均代碼長度接近S的熵值。可以唯一地譯碼

1005.4常用信源編碼方法簡介采用累積概率P(S)表示碼字C(S)，符號概率p(S)表示狀態(tài)區(qū)間A(S)S：符號序列；pr:某一區(qū)間的概率；

0(P1)P2P3P4P5……1

……p1

p2p3p41015.4常用信源編碼方法簡介符號符號概率pi符號累積概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例有四個符號a，b，c，d構(gòu)成簡單序列S＝abda，各符號及其對應(yīng)概率如下表，算術(shù)編解碼過程如下：1025.4常用信源編碼方法簡介設(shè)起始狀態(tài)為空序列

，則A(

)＝1，C(

)＝0（定義）。1035.4常用信源編碼方法簡介1045.4常用信源編碼方法簡介C(abda)即為編碼后的碼字0101111055.4常用信源編碼方法簡介A(

)A(a)abcdA(a,b)abcdabcdA(a,b,d)C(

)0(Pa)pa

PbpbPcpcPdpd1C(0)C(a,b,d)C(a,b)算術(shù)編碼過程1065.4常用信源編碼方法簡介譯碼（逆過程）C(abda)=0.010111<0.1

[0,0.1]

第一個符號為a

放大至[0,1](×pa-1)：C(abda)×21＝0.10111

[0.1,0.110]

第二個符號為b

去掉累積概率Pb：0.10111-0.1=0.001111075.4常用信源編碼方法簡介放大至[0,1](×pb-1)：

0.00111×22=0.111

[0.111,1]

第三個符號為d

去掉累積概率Pd：0.111-0.111=0

放大至[0,1](×pd-1)：0×24＝0

[0,0.1]第四個符號為a108算術(shù)編碼譯碼步驟先將碼字變成小數(shù)形式判斷所得值落在所劃分的哪個區(qū)域內(nèi)減去所對應(yīng)的累積概率除以相應(yīng)的符號概率1095.4常用信源編碼方法簡介算術(shù)編碼從性能上看具有許多優(yōu)點(diǎn)，特別是由于所需的參數(shù)很少，不象哈夫曼編碼那樣需要一個很大的碼表，常設(shè)計成自適應(yīng)算術(shù)編碼來針對一些信源概率未知或非平穩(wěn)情況。1105.4常用信源編碼方法簡介但是在實際實現(xiàn)時還有一些問題，如計算復(fù)雜性、計算的精度以及存儲量等，隨著這些問題的逐漸解決，算術(shù)編碼正在進(jìn)入實用階段，但要擴(kuò)大應(yīng)用范圍或進(jìn)一步提高性能，降低造價，還需進(jìn)一步改進(jìn)。作業(yè)P115:5-3；5-5；5-11.111112算術(shù)編碼過程算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如JPEG，JBIG）中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號壓縮后的輸出。113算術(shù)編碼過程編碼編碼時首先輸入的符號是c，找到它的編碼范圍是[0.5,0.7)。由于消息中第二個符號a的編碼范圍是[0,0.1)，因此它的間隔就取[0.5,0.7)的第一個十分之一作新間隔[0.5,0.52)。假設(shè)信源符號為{a,b,c,d}，這些符號的概率分別為:p(a)=0.1,p(b)=0.4,p(c)=0.2,p(d)=0.3。如果消息序列的輸入:cadacdb。

114算術(shù)編碼過程1c[0.5,0.7)符號的間隔范圍[0.5,0.7)

2a[0.5,0.52)[0.5,0.7)間隔的第一個1/10

3d[0.514,0.52)[0.5,0.