信息論與編碼第5章(3)方案

1、2020/11/17,1,信源編碼,第5章（第3講）,2020/11/17,2,信息通過(guò)信道傳輸?shù)叫潘薜倪^(guò)程即為通信。要做到既不失真又快速地通信，需要解決兩個(gè)問(wèn)題： 在不失真或允許一定失真條件下，如何提高信息傳輸速度-這是本章要討論的信源編碼問(wèn)題. 在信道受到干擾的情況下，如何增加信號(hào)的抗干擾能力，同時(shí)又使得信息傳輸率最大-這是下章要討論的信道編碼問(wèn)題.,2020/11/17,3,信源編碼： 無(wú)失真信源編碼第一極限定理 可逆編碼的基礎(chǔ)，只適用于離散信源，主要用于文字、數(shù)據(jù)信源的壓縮。 限失真信源編碼第三極限定理 只適用于連續(xù)信源，主要用于圖像、語(yǔ)音信源的壓縮 信道編碼 第二極限定理,2020/

2、11/17,4,一般來(lái)說(shuō)，抗干擾能與信息傳輸率二者相互矛盾。然而編碼定理已從理論上證明，至少存在某種最佳的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。 信源雖然多種多樣，但無(wú)論是哪種類(lèi)型的信源，信源符號(hào)之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率。,2020/11/17,5,信源編碼的基本途徑有兩個(gè): 一是編碼后使序列中的各個(gè)符號(hào)之間盡可能地 互相獨(dú)立，即解除相關(guān)性-方法包括預(yù)測(cè)編 碼和變換編碼. 二是使編碼后各個(gè)符號(hào)出現(xiàn)的概率盡可能相等，即均勻化分布-方法主要是統(tǒng)計(jì)編碼.,2020/11/17,6,本章主要介紹信源編碼的基本思路與主要

3、方法，以無(wú)失真編碼為主，期望通過(guò)本章學(xué)習(xí)能建立起信源壓縮編碼的基本概念。,2020/11/17,7,5.1 編碼的定義 5.2 無(wú)失真信源編碼 5.3 限失真信源編碼 5.4 常用信源編碼方法簡(jiǎn)介,主 要 內(nèi) 容,2020/11/17,8,5.2.3 最佳變長(zhǎng)編碼,最佳碼： 對(duì)于某一信源和某一碼符號(hào)集來(lái)說(shuō),若有一唯一可譯碼,其平均碼長(zhǎng)小于所有其他唯一可譯碼的平均長(zhǎng)度。 方法：將概率大的信源符號(hào)編以短的碼字。概率小的符號(hào)編以長(zhǎng)的碼字，這樣使得平均碼字長(zhǎng)度最短。 主要有： 香農(nóng)（Shannon） 費(fèi)諾（Fano） 哈夫曼（Huffma ）,2020/11/17,9,香農(nóng)編碼,香農(nóng)第一定理指出了平均

4、碼長(zhǎng)與信源之間的關(guān)系,同時(shí)也指出了可以通過(guò)編碼使平均碼長(zhǎng)達(dá)到極限值,這是一個(gè)很重要的極限定理。 香農(nóng)第一定理指出,選擇每個(gè)碼字的長(zhǎng)度Ki滿(mǎn)足下式：,或: log2 p(xi) Ki 1log2 p(xi) 就可以得到這種碼。 這種編碼方法稱(chēng)為香農(nóng)編碼,取整,2020/11/17,10,二進(jìn)制香農(nóng)碼的編碼步驟如下： 將信源符號(hào)按概率從大到小的順序排列, p(a1) p(a2) p(an) 確定滿(mǎn)足下列不等式的整數(shù)Ki , log2 p(ai) Ki 1log2 p(ai) 令p(a1)=0,用Pi表示第i個(gè)碼字的累加概率，,香農(nóng)編碼,將Pi用二進(jìn)制表示,并取小數(shù)點(diǎn)后Ki位作為符號(hào)ai的編碼。,2

5、020/11/17,11,香農(nóng)編碼方法特點(diǎn)： 由于ki總是進(jìn)一取整，香農(nóng)編碼方法不一定是最佳的； 由于第一個(gè)消息符號(hào)的累加概率總是為0，故它對(duì)應(yīng)的碼字總是0、00、000、00的式樣； 碼字集合是唯一的，且為即時(shí)碼； 先有碼長(zhǎng)再有碼字； 對(duì)于一些信源，編碼效率不高，冗余度稍大，因此其實(shí)用性受到較大限制。,結(jié)論,2020/11/17,12,費(fèi)諾編碼,費(fèi)諾編碼屬于概率匹配編碼 。 編碼步驟如下： 將概率按從大到小的順序排列,令 p(x1) p(x2) p(xn) 按編碼進(jìn)制數(shù)將概率分組,使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組,編m進(jìn)制碼就分成m組。 給每一組分配一位碼元。 將每一分組再

6、按同樣原則劃分,重復(fù)步驟2和3,直至概率不再可分為止。,2020/11/17,13,費(fèi)諾編碼特點(diǎn)： 概率大，則分解的次數(shù)?。桓怕市? 則分解的次數(shù)多。這符合最佳編碼原則。 碼字集合是唯一的。 分解完了，碼字出來(lái)了，碼長(zhǎng)也有了。 因此，費(fèi)諾編碼方法又稱(chēng)為子集分解法。 費(fèi)諾編碼方法比較適合于每次分組概率都很接近的信源，特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。,結(jié)論,r 元費(fèi)諾碼: 前面討論的費(fèi)諾碼是二元費(fèi)諾碼，對(duì)r元費(fèi)諾碼，與二元費(fèi)諾碼編碼方法相同，只是每次分組時(shí)應(yīng)將符號(hào)分成概率分布接近的r個(gè)組。,2020/11/17,14,哈夫曼編碼,哈夫曼編碼也是用碼樹(shù)來(lái)分配各符號(hào)的

7、碼字。 費(fèi)諾碼是從樹(shù)根開(kāi)始,把各節(jié)點(diǎn)分給某子集,若子集已是單點(diǎn)集,它就是一片樹(shù)葉而作為碼字。 哈夫曼編碼是先給每一符號(hào)一片樹(shù)葉,逐步合并成節(jié)點(diǎn)直到樹(shù)根。 哈夫曼(Huffman)編碼是一種效率比較高的變長(zhǎng)無(wú)失真信源編碼方法。,2020/11/17,15,哈夫曼編碼的步驟如下： 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 p(x1)p(x2) p(xn) 取兩個(gè)概率最小的字母分別配以0和1兩碼元,并將這兩個(gè)概率相加作為一個(gè)新字母的概率,與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)。 對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟的過(guò)程。 不斷繼續(xù)上述過(guò)程,直到最后兩個(gè)符號(hào)配以0和1為止。 從最后一級(jí)開(kāi)始,向前返回得到各個(gè)

8、信源符號(hào)所對(duì)應(yīng)的碼元序列,即相應(yīng)的碼字。,2020/11/17,16,哈夫曼的編法并不惟一。 每次對(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也不盡相同。,哈夫曼編碼,2020/11/17,17,m進(jìn)制哈夫曼編碼,在編m進(jìn)制哈夫曼碼時(shí)為了使平

9、均碼長(zhǎng)最短,必須使最后一步縮減信源有m個(gè)信源符號(hào)。 對(duì)于m進(jìn)制編碼,若所有碼字構(gòu)成全樹(shù),可分離的碼字?jǐn)?shù)必為: mk(ml),K任意非負(fù)整數(shù) 設(shè)第一次組合的概率數(shù)取 s，考慮到第二次組合就應(yīng)該使用m進(jìn)制，則s通常應(yīng)滿(mǎn)足 第一次對(duì)最小概率符號(hào)分配碼元時(shí)只取s個(gè),分別配以0,1, ,s-1,把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率,與其它符號(hào)一起重新排列 以后每次取m個(gè)符號(hào),分別配以0,1,m-1；如此下去,直至所有概率相加得1為止,即得到各符號(hào)的m進(jìn)制碼字。,2020/11/17,18,哈夫曼編碼特點(diǎn)： 由于哈夫曼編碼總是以最小概率相加的方法來(lái)“縮減”參與排隊(duì)的概率個(gè)數(shù)，因此概率越小，對(duì)縮減的貢獻(xiàn)

10、越大，其對(duì)于消息的碼字也越長(zhǎng)； 最小概率相加的方法使得編碼不具有唯一性，尤其是碰到存在幾個(gè)消息符號(hào)有著相同概率的情況，將會(huì)有多種路徑選擇，亦即具有多種可能的代碼組集合； 盡管對(duì)同一信源存在著多種結(jié)果的哈夫曼編碼，但它們的平均碼長(zhǎng)幾乎都是相等的，因?yàn)槊恳环N路徑選擇都是使用最小概率相加的方法，其實(shí)質(zhì)都是遵循最佳編碼的原則，因此哈夫曼編碼是最佳編碼。 哈夫曼編碼是一種最佳編碼，實(shí)現(xiàn)也不困難，因此到目前為止它仍是應(yīng)用最為廣泛的無(wú)失真信源編碼之一。 在實(shí)際問(wèn)題中真正使用哈夫曼編碼時(shí)，還需要進(jìn)一步研究有關(guān)誤差擴(kuò)散、速率匹配和概率匹配等問(wèn)題。,結(jié)論,2020/11/17,19,總結(jié) 香農(nóng)碼、費(fèi)諾碼、哈夫曼碼

11、都考慮了信源的統(tǒng)計(jì)特性,使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字,使信源的平均碼長(zhǎng)縮短,從而實(shí)現(xiàn)了對(duì)信源的壓縮； 香農(nóng)碼有系統(tǒng)的、惟一的編碼方法,但在很多情況下編碼效率不是很高； 費(fèi)諾碼和哈夫曼碼的編碼方法都不惟一； 費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼,費(fèi)諾碼也可以編m進(jìn)制碼,但m越大,信源的符號(hào)數(shù)越多,可能的編碼方案就越多,編碼過(guò)程就越復(fù)雜,有時(shí)短碼未必能得到充分利用； 哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒(méi)有特殊要求,編碼效率比較高,對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單,因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。,2020/11/17,20,5.3 限失真信源編碼定理,2020/11/17,21,限失真信源編碼定理

12、,在很多實(shí)際信源中,特別在模擬的連續(xù)信源中,無(wú)失真要求是完全沒(méi)有必要的,而且也是達(dá)不到的。 在實(shí)際中限失真信源是具有現(xiàn)實(shí)意義的,2020/11/17,22,限失真信源編碼定理,限失真信源編碼定理： 設(shè)離散無(wú)記憶信源X的信息率失真函數(shù)為R(D) , 當(dāng)信息率 RR(D)時(shí),只要信源序列長(zhǎng)度 L 足夠長(zhǎng),一定存在一種編碼方法,其譯碼失真小于或等于 D+,為任意小的正數(shù)； 反之,若RR(D) ,則無(wú)論采用什么樣的編碼方法,其譯碼失真必大于D。 如是二元信源,則對(duì)于任意小的0,每一個(gè)信源符號(hào)的平均碼長(zhǎng)滿(mǎn)足如下公式：,2020/11/17,23,5.4 常用信源編碼方法,2020/11/17,24,常用

13、信源編碼,香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對(duì)無(wú)記憶信源，屬于無(wú)失真信源編碼； 當(dāng)信源有記憶時(shí)上述編碼效率不高； 游程編碼 算術(shù)編碼 預(yù)測(cè)編碼 變換編碼 其它幾種限失真信源編碼,2020/11/17,25,5.4.1 游程編碼,游程： 數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。 二元序列的游程：只有“0”和“1”兩種符號(hào)。 連“0”這一段稱(chēng)為“0”游程,它的長(zhǎng)度稱(chēng)為游程長(zhǎng)度L(0)； 連“1”這一段稱(chēng)為“1”游程,它的游程長(zhǎng)度用L(1)表示。,2020/11/17,26,游程編碼,二元獨(dú)立序列游程長(zhǎng)度概率 若規(guī)定二元序列總是從“0”開(kāi)始,第一個(gè)游程是“0”游程,則第二個(gè)游程必為“1”游程,第三個(gè)又

14、是“0”游程。 對(duì)于隨機(jī)序列,游程長(zhǎng)度是隨機(jī)的其取值可為1,2,3,，直至無(wú)窮。 游程長(zhǎng)度序列/游程序列：用交替出現(xiàn)的“0”游程和“1”游程長(zhǎng)度表示任意二元序列。 游程變換： 是一種一一對(duì)應(yīng)的變換,也是可逆變換。 例如：二元序列000101110010001 可變換成如下游程序列 31132131,2020/11/17,27,游程變換減弱了原序列符號(hào)間的相關(guān)性。 游程變換將二元序列變換成了多元序列； 這樣就適合于用其他方法,如哈夫曼編碼,進(jìn)一步壓縮信源,提高通信效率。 編碼方法： 首先測(cè)定“0”游程長(zhǎng)度和“1”游程長(zhǎng)度的概率分布,即以游程長(zhǎng)度為元素,構(gòu)造一個(gè)新的信源； 對(duì)新的信源(游程序列)進(jìn)

15、行哈夫曼編碼。,游程編碼,2020/11/17,28,傳真編碼,文件傳真的基本特性 文字傳真:黑、白兩個(gè)灰度級(jí) 圖像傳真:有比較豐富的灰度的圖片、圖像 數(shù)字式文件傳真把一頁(yè)文件分為nm個(gè)像素 Xij表示第i行(i=l,2n)第j列(j=l,2m)的像素 由于文件傳真是二值電平的,即只有兩個(gè)灰度值, Xij,0(白色) 1(黑色),2020/11/17,29,傳真編碼,直接編碼： 每一個(gè)像素用一位二進(jìn)碼(0或1)代表 一頁(yè)文件的碼元數(shù)就等于該頁(yè)二值圖像的像素?cái)?shù) X3 =1111 0010 0011 0001 1111,分辨率： 單位長(zhǎng)度(lmm)包含的像素?cái)?shù)。 分辨率愈高,文件細(xì)節(jié)愈清晰,文件質(zhì)

16、量也就愈高。但是表示一頁(yè)文件的比特?cái)?shù)就愈多。,2020/11/17,30,例如一頁(yè)A4文件,分辨率為5點(diǎn)/mm。 直接編碼時(shí)需傳送： 21029752=1.5Mbit 用2400bit/s的數(shù)碼率傳送約需11分鐘 如果希望達(dá)到CCITT（國(guó)際電報(bào)電話(huà)咨詢(xún)委員會(huì)）的第3類(lèi)文件傳真機(jī)的標(biāo)準(zhǔn),即用市話(huà)網(wǎng)作信道,1分鐘內(nèi)傳輸一頁(yè)A4文件,那么我們就需要找到一種編碼方法,把數(shù)碼壓縮到原來(lái)的1/11。 某一種編碼的壓縮比為：,2020/11/17,31,CCITT建議使用兩種分辨率： 1728像素/行(8樣點(diǎn)/mm),3.85行/mm(4行/mm) 1728像素/行(8樣點(diǎn)/mm),7.7行/mm (8行

17、/mm) 根據(jù)漢字的特點(diǎn),對(duì)傳真用的七種試用樣張進(jìn)行了統(tǒng)計(jì),測(cè)得下列平均值： p(白) = pW = 93.3 ， p(黑) = pB = 6.7 測(cè)試結(jié)果表明： 50% LW小于18個(gè)像素 80% LW小于61個(gè)像素 50% LB小于4個(gè)像素 80% LB小于6個(gè)像素,LW白游程長(zhǎng)度 LB 黑游程長(zhǎng)度,有了上述游程的概率分布,對(duì)不同的游程長(zhǎng)度,按其不同的發(fā)生概率,可以分配不同的碼字,這種編碼方式稱(chēng)為游程編碼。 游程編碼既可以將白、黑游程分別按其概率進(jìn)行分別編碼,也可以將白長(zhǎng)與黑長(zhǎng)混起來(lái)統(tǒng)一編碼。,2020/11/17,32,黑、白分開(kāi)編碼時(shí) 白游程熵：,其中LW為白游程長(zhǎng)度,p(LW)為對(duì)應(yīng)

18、的白游程概率,L為游程最大長(zhǎng)度,對(duì)文件傳真L=1728， 白游程平均編碼長(zhǎng)度應(yīng)滿(mǎn)足:,令 為白游程長(zhǎng)的平均像素?cái)?shù),P84:5-2-9,每像數(shù)的編碼比特?cái)?shù),平均每像素的熵值,2020/11/17,33,黑游程熵：,黑游程平均編碼長(zhǎng)應(yīng)滿(mǎn)足,經(jīng)過(guò)黑、白平均可得每個(gè)像素的熵值,每個(gè)像素的編碼比特?cái)?shù),2020/11/17,34,黑、白游程分別最佳編碼后,由每個(gè)像素的熵hWB 即可得到最小比特率。 極限壓縮比,游程編碼,2020/11/17,35,對(duì)中文A4文件七種樣張的平均值： 分辨率88 分辨率84 pW =0. 9326 0.933 ; pB = 0.0674 0.0670 LW = 85.99 8

19、6.44 像素(pel) LB = 5.73 5.72 像素(pel) HW = 5.89 5.87 b/run HB = 3.14 3.14 b/run hWB= 0.1003 0.0997 b/ pel K0 =9.97 10.03,對(duì)中文A4文件,7種樣張的統(tǒng)計(jì)極限壓縮比 K0 10倍,2020/11/17,36,5.4.2 算術(shù)編碼,算術(shù)編碼是近十多年來(lái)發(fā)展迅速的一種無(wú)失真信源編碼,它與最佳的哈夫曼碼相比,理論性能稍加遜色,而實(shí)際壓縮率和編碼效率卻往往還優(yōu)于哈夫曼碼,且實(shí)現(xiàn)簡(jiǎn)單,故很受工程上的重視。 算術(shù)編碼不同于哈夫曼碼,它是非分組(非塊)碼。它從全序列出發(fā),考慮符號(hào)之間的關(guān)系來(lái)進(jìn)行

20、編碼。 算術(shù)編碼利用了累積概率的概念。 算術(shù)碼主要的編碼方法是計(jì)算輸入信源符號(hào)序列所對(duì)應(yīng)的區(qū)間。,2020/11/17,37,算術(shù)碼的主要概念,算術(shù)碼的主要概念： 把信源輸出序列的概率和實(shí)數(shù)段0,1中的一個(gè)數(shù)C聯(lián)系起來(lái)。 設(shè)信源字母表為a1, a2,其概率p(a1)=0.6, p(a2)=0.4 將0,1分成與概率比例相應(yīng)的區(qū)間,0,0.6 0.6,l,p(a1),p(a2),0 0.6 1,設(shè)信源輸出序列S=S1S2S3Sn 當(dāng)信源輸出的第一個(gè)符號(hào)S1 = a1時(shí),數(shù)C的值處在0,0.6 當(dāng)信源輸出的第一個(gè)符號(hào)S1 = a2時(shí),數(shù)C的值處在0.6,l,根據(jù)信源S1的情況,把C所在的段再次按概

21、率比例劃分,0 0.36 0.6 0.84 1,p(a1a1),p(a1a2),p(a2a1),p(a2a2),隨著序列的長(zhǎng)度不斷增加,C所在區(qū)間的長(zhǎng)度就越短,也就可以更加精確地確定C的位置,2020/11/17,38,累積概率,設(shè)信源符號(hào)集A=a1,a2,an,其相應(yīng)概率分布為p(ai), p(ai) 0(i=1,2, ,n) 信源符號(hào)的累積概率為,顯然 P1= 0; P2= p1 ; P3= p1+p2 ; 而且 pr = Pr+1 Pr,2020/11/17,39,累積概率Pr+1和Pr都是小于1的正數(shù),可用0,1區(qū)間內(nèi)的兩個(gè)點(diǎn)來(lái)表示;,P1,p1,P2,P3,P4,1,p2,p3,0,

22、pr就是這兩點(diǎn)間的小區(qū)間的長(zhǎng)度,如圖:,當(dāng)A=0,1二元信源時(shí)： P(0)= 0 ; P(1) = p(0),P(0),P(1),0,1,p(0),p(1),2020/11/17,40,計(jì)算二元無(wú)記憶信源序列的累積概率 初始時(shí)：在0,1)區(qū)間內(nèi)由P(1)劃分成二個(gè)子區(qū)間0, P1 )和P1 ,1) , P(1) = p(0) 。 子區(qū)間0, P1 )的寬度為A(0)= p(0) ,對(duì)應(yīng)于信源符號(hào)“0”； 子區(qū)間P1 ,1)的寬度為A(1)= p(1) ,對(duì)應(yīng)于信源符號(hào)“1”; 若輸入符號(hào)序列的第一個(gè)符號(hào)為S =“0”,落入0, P1 )區(qū)間,得累積概率 P (S =“0”)= P(0) = 0

23、；,算術(shù)編碼,2020/11/17,41,若輸入第二個(gè)符號(hào)為“1”,S =“01”, S =“01”所對(duì)應(yīng)的區(qū)間是在區(qū)間0, P(1) )中進(jìn)行分割； 符號(hào)序列“00”對(duì)應(yīng)的區(qū)間寬度為 A(00)=A(0) p(0)=p(0)p(0)= p(00)； 對(duì)應(yīng)的區(qū)間為0,P(S =“01”)。 符號(hào)序列“01”對(duì)應(yīng)的區(qū)間寬度為 A(01) =A(0) p(1)= p(0)p(1)= p(01) = A(0)A(00)； 對(duì)應(yīng)的區(qū)間為P(S =“01”),P(1)。 累積概率: P(S =“01”)=p(00)= p(0)p(0),2020/11/17,42,P(0),0,P(1),1,p(0),設(shè)

24、輸入符號(hào)序列S = 011,p(1),P(0),P(1),p(00),P(01),p(01),P(01),P(1),P(011),p(010),p(011),p(0)= p(00)+p(01) p(01)= p(010)+p(011) 歸一律,P(0)= 0 P(01)= p(00) P(011)= P(01)+p(010),2020/11/17,43,011S1, S=01 輸入序列S1=“011”對(duì)應(yīng)的區(qū)間是對(duì)區(qū)間P(S), P (1)進(jìn)行分割 序列S0=“010”對(duì)應(yīng)的區(qū)間寬度為 A(S =“010”)=A(S=“01”)p(0)=A(S) p(0) 其對(duì)應(yīng)的區(qū)間為P(S), P(S)+

25、 A(S) p(0)； 序列S1=“011”對(duì)應(yīng)的區(qū)間寬度為 A(S=“011”)=A(S)p(1) =A(S =“01”)A(S =“010”)= A(S)A(S0) 其對(duì)應(yīng)的區(qū)間為P(S)+ A(S) p(0),P(1)；,2020/11/17,44,P(0),0,P(1),1,p(0),p(1),P(0),P(1),p(00),P(S) S=01,p(01),P(S),P(1),P(S1),p(010),p(011),當(dāng)前面輸入符號(hào)序列為S,若接著輸入一個(gè)“0”, 累積概率: P(S 0)= P(S) 對(duì)應(yīng)區(qū)間寬度為： A(S0)=A(S)p(0),若接著輸入的一個(gè)符號(hào)是“1”， 累積概

26、率: P(S1)= P(S) + A(S)p(0) 對(duì)應(yīng)區(qū)間寬度為： A(S1) = A(S)p(1) =A(S)A(S0),信源符號(hào)0的區(qū)間寬度 A(0)= p(0),符號(hào)1的區(qū)間寬度 A(1)=p(1),符號(hào)“00”區(qū)間寬度 A(00)=p(00),信源符號(hào)“01”區(qū)間寬度 A(01)=p(01)=A(0)-A(00),2020/11/17,45,符號(hào)序列對(duì)應(yīng)的區(qū)間寬度 A(S=“0”) = p(0) A(S=“1”) = 1A(S=“0”)=p(1) A(S=“00”) = p(00) = A(0) p(0) = p(0) p(0) A(S=“01”) = A(S=“0”)A(S=“00

27、”) = p(01)= A(0) p(1) = p(0) p(1) A(S=“10”) = p(10)=A(1) p(0) = p(1) p(0) A(S=“11”) = A(S=“1”)A(S=“10”) =p(11)=A(S=“1”)p(1)=p(1) p(1) A(S=“010”) = A(S=“01”)p(0)=p(01) p(0)p(010) A(S=“011”) = A(S=“01”)A(S=“010”) = A(S=“01”)p(1)= p(01) p(1)= p(011) 信源符號(hào)序列S所對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列S的概率p(S)。,算術(shù)編碼,2020/11/17,46,算術(shù)編

28、碼,二元信源符號(hào)序列的累積概率遞推公式,Sr表示前面信源符號(hào)序列為S,接著再輸入符號(hào)為r P(0)=0， P(1) = p(0) P(S0)= P(S) P(S1)= P(S) + p(S) p(0),信源符號(hào)序列所對(duì)應(yīng)區(qū)間的寬度遞推公式,2020/11/17,47,例：已輸入二元符號(hào)序列為S=“011”,接著再輸入符號(hào)為“1”, 得序列累積概率為： P(S1)=P(0111)=P(S=“011”)+p(011)p(0) =P(S=“01”)+p(01)p(0)+p(011)p(0) =P(S=“0”)+p(0)p(0)+p(01)p(0)+p(011)p(0) =0 +p(00)+p(010

29、)+p(0110) 對(duì)應(yīng)的區(qū)間寬度為 A(S1)=p(S=“011”) p(1)= p(011) p(1)= p(0111),2020/11/17,48,算術(shù)編碼,一般多元信源序列的累積概率遞推公式,序列的概率公式,2020/11/17,49,算術(shù)編碼,實(shí)際應(yīng)用中,采用累積概率P(S)表示碼字C(S),符號(hào)概率p(S)表示狀態(tài)區(qū)間A(S),則有： C(S,r) = C(S)+A(S)Pr A(S,r) = A(S) pr,實(shí)際編碼時(shí),只需兩個(gè)存儲(chǔ)器,起始時(shí)可令: A() =1, C() = 0 每輸入一個(gè)信源符號(hào),存儲(chǔ)器C和A 就按照上式更新一次,直至信源符號(hào)輸入完畢,就可將存儲(chǔ)器C的內(nèi)容作為

30、該序列的碼字輸出。,2020/11/17,50,算術(shù)編碼,在編碼過(guò)程中,每輸入一個(gè)符號(hào)要進(jìn)行乘法和加法運(yùn)算,所以稱(chēng)為算術(shù)編碼。 通過(guò)關(guān)于信源符號(hào)序列的累積概率的計(jì)算,把區(qū)間分割成許多小區(qū)間,不同的信源符號(hào)序列對(duì)應(yīng)不同的區(qū)間為P(S), P(S) + p(S) ?？扇⌒^(qū)間內(nèi)的一點(diǎn)來(lái)代表這序列。,2020/11/17,51,算術(shù)編碼,編碼方法： 將符號(hào)序列的累積概率寫(xiě)成二進(jìn)位的小數(shù)，取小數(shù)點(diǎn)后L位,若后面有尾數(shù),就進(jìn)位到第L位,這樣得到的一個(gè)數(shù)C,并使L滿(mǎn)足,取整,2020/11/17,52,例：設(shè)二元無(wú)記憶信源S=0,1,其p(0)=1/4,p(1)=3/4。 對(duì)二元序列11111100做算術(shù)

31、編碼。,P(S) = p(00000000) + p(00000001) + p(00000010) + + p(11111011) = 1 p(11111111) p(11111110) p(11111101) p(11111100) = 1 p(111111) = 1(3/4)6= 0.110100100111,得 C = 0.1101010 S的碼字為 1101010,解：p(S=11111100) = p2(0)p6(1) = (1/4)2 (3/4)6,2020/11/17,53,+,=,p(1)=3/4=(0.11)2,p(11)=(3/4)2=(0.1001)2,+,=,p(0)

32、=(1/4)=2-2 p(S)p(0)p(S)右移2位,2020/11/17,54,5.4.3 預(yù)測(cè)編碼,預(yù)測(cè)編碼是數(shù)據(jù)壓縮三大經(jīng)典技術(shù)（統(tǒng)計(jì)編碼、預(yù)測(cè)編碼、變換編碼）之一，它是建立在信源數(shù)據(jù)相關(guān)性之上的。由信息理論可知，對(duì)于相關(guān)性很強(qiáng)的信源，條件熵可遠(yuǎn)小于無(wú)條件熵，因此人們常采用盡量解除相關(guān)性的辦法，使信源輸出轉(zhuǎn)化為獨(dú)立序列，以利于進(jìn)一步壓縮碼率。 常用的解除相關(guān)性的措施是預(yù)測(cè)和變換，其實(shí)質(zhì)都是進(jìn)行序列的一種映射。一般來(lái)說(shuō)，預(yù)測(cè)編碼有可能完全解除序列的相關(guān)性，但必需確知序列的概率特性；變換編碼一般只解除矢量?jī)?nèi)部的相關(guān)性，但它可有許多可供選擇的變換方法，以適應(yīng)不同的信源特性。下面介紹預(yù)測(cè)編碼的

33、一般理論與方法。,2020/11/17,55,預(yù)測(cè)編碼的基本思想是通過(guò)提取與每個(gè)信源符號(hào)有關(guān)的新信息，并對(duì)這些新信息進(jìn)行編碼來(lái)消除信源符號(hào)之間的相關(guān)性。實(shí)際中常用的新信息為信源符號(hào)的當(dāng)前值與預(yù)測(cè)值的差值，這里正是由于信源符號(hào)間存在相關(guān)性，所以才使預(yù)測(cè)成為可能，對(duì)于獨(dú)立信源，預(yù)測(cè)就沒(méi)有可能。 預(yù)測(cè)的理論基礎(chǔ)主要是估計(jì)理論。所謂估計(jì)就是用實(shí)驗(yàn)數(shù)據(jù)組成一個(gè)統(tǒng)計(jì)量作為某一物理量的估值或預(yù)測(cè)值。若估值的數(shù)學(xué)期望等于原來(lái)的物理量，就稱(chēng)這種估計(jì)為無(wú)偏估計(jì)；若估值與原物理量之間的均方誤差最小，就稱(chēng)之為最佳估計(jì)，基于這種方法進(jìn)行預(yù)測(cè)，就稱(chēng)為最小均方誤差預(yù)測(cè)，所以也就認(rèn)為這種預(yù)測(cè)是最佳的。 要實(shí)現(xiàn)最佳預(yù)測(cè)就是要找

34、到計(jì)算預(yù)測(cè)值的預(yù)測(cè)函數(shù)。,2020/11/17,56,設(shè)有信源序列 ，k階預(yù)測(cè)就是由 的前k個(gè)數(shù)據(jù)來(lái)預(yù)測(cè) 。 可令預(yù)測(cè)值為： 式中 是待定的預(yù)測(cè)函數(shù)。要使預(yù)測(cè)值具有最小均方誤差，必須確知k個(gè)變量的聯(lián)合概率密度函數(shù) ，這在一般情況下較難得到，因而常用比較簡(jiǎn)單的線(xiàn)性預(yù)測(cè)方法。 線(xiàn)性預(yù)測(cè)是取預(yù)測(cè)函數(shù)為各已知信源符號(hào)的線(xiàn)性函數(shù)，即取 的預(yù)測(cè)值為： 其中 為預(yù)測(cè)系數(shù)。,2020/11/17,57,最簡(jiǎn)單的預(yù)測(cè)是令 稱(chēng)為前值預(yù)測(cè)，常用的差值預(yù)測(cè)就屬于這類(lèi)。 利用預(yù)測(cè)值來(lái)編碼的方法可分為兩類(lèi)： 一類(lèi)是對(duì)實(shí)際值與預(yù)測(cè)值之差進(jìn)行編碼，也叫差值預(yù)測(cè)編碼。 另一類(lèi)方法是根據(jù)差值的大小，決定是否需傳送該信源符號(hào)。例如

35、，可規(guī)定某一閾值T，當(dāng)差值小于T時(shí)可不傳送，對(duì)于相關(guān)性很強(qiáng)的信源序列，常有很長(zhǎng)一串符號(hào)的差值可以不傳送，此時(shí)只需傳送這串符號(hào)的個(gè)數(shù)，這樣能大量壓縮碼率。這類(lèi)方法一般是按信宿要求來(lái)設(shè)計(jì)的，也就是壓縮碼率引起的失真應(yīng)能滿(mǎn)足信宿需求。,2020/11/17,58,下面簡(jiǎn)單介紹差值預(yù)測(cè)編碼系統(tǒng)。如果信源的相關(guān)性很強(qiáng)，則采用差值編碼可得較高的壓縮率。由于相關(guān)性很強(qiáng)的信源可較精確地預(yù)測(cè)待編碼的值，使得這個(gè)差值的方差將遠(yuǎn)小于原來(lái)的信源取值，所以在同樣失真要求下，量化級(jí)數(shù)可大大減少，從而較顯著地壓縮碼率。 差值預(yù)測(cè)編碼系統(tǒng)的框圖如下圖所示，在編碼端主要由一個(gè)符號(hào)編碼器和一個(gè)預(yù)測(cè)器組成，在解碼端主要由一個(gè)符號(hào)解

36、碼器和一個(gè)預(yù)測(cè)器組成。,2020/11/17,59,編碼器,解碼器,2020/11/17,60,當(dāng)輸入信源序列逐個(gè)進(jìn)入編碼器時(shí)，預(yù)測(cè)器根據(jù)若干個(gè)過(guò)去的輸入產(chǎn)生對(duì)當(dāng)前輸入像素的估計(jì)值。預(yù)測(cè)器的輸出舍入成最近的整數(shù)，并被用來(lái)計(jì)算預(yù)測(cè)誤差： 在解碼器中根據(jù)接收到的變長(zhǎng)碼字重建 ，并執(zhí)行下列操作： 而 可通過(guò)式 進(jìn)行預(yù)測(cè)得到。,2020/11/17,61,差值編碼的特點(diǎn)： 在差值編碼中所能取得的壓縮率與預(yù)測(cè)誤差序列所產(chǎn)生的熵的減少量直接有關(guān)。 通過(guò)預(yù)測(cè)可消除相關(guān)，所以預(yù)測(cè)誤差的概率分布一般在零點(diǎn)附近有一個(gè)高峰，并且與輸入信源分布相比其方差較小。 預(yù)測(cè)編碼的基本類(lèi)型 DPCM（差分脈碼調(diào)制） PCM型

37、噪聲反饋編碼(NFC) 預(yù)測(cè)誤差門(mén)限型,2020/11/17,62,5.4.4 變 換 編 碼,眾所周知，信源序列往往具有很強(qiáng)的相關(guān)性，要提高信源的效率首先要解除信源的相關(guān)性。解除相關(guān)性可以在時(shí)域上進(jìn)行(這就是上節(jié)中介紹的預(yù)測(cè)編碼)，也可以在頻域，甚至在廣義頻域內(nèi)進(jìn)行，這就是要在本節(jié)中介紹的域變換編碼。,在信號(hào)分析中，對(duì)連續(xù)的模擬信號(hào)，如果它是周期性的,則可采用傅氏級(jí)數(shù)展開(kāi)，若是非周期性的,則可采用傅氏積分(變換)來(lái)表示，但無(wú)論是級(jí)數(shù)還是積分,都屬于一類(lèi)正交變換，是從時(shí)域展開(kāi)成頻域的變換。同理,對(duì)離散的數(shù)據(jù)序列信號(hào)也可引入同樣的離散傅氏變換。而且，還可以進(jìn)一步將其推廣為廣義的頻域變換。,202

38、0/11/17,63,上一節(jié)討論的在空間和時(shí)間域上壓縮信源數(shù)據(jù)冗余量的預(yù)測(cè)編碼的最大特點(diǎn)是直觀、簡(jiǎn)潔、易于實(shí)現(xiàn)，特別是容易設(shè)計(jì)出具有實(shí)時(shí)性的硬件結(jié)構(gòu)。但是預(yù)測(cè)編碼的不足在于壓縮能力有限。具有更高壓縮能力的方法和目前最為成熟的方法是變換編碼，特別是正交變換編碼方法和目前尚處于研究階段的小波變換編碼，這兩種方法都具有很強(qiáng)的數(shù)據(jù)壓縮能力。 變換編碼的基本原理就是將原來(lái)在空間域上描述的信號(hào)，通過(guò)一種數(shù)學(xué)變換(例如，傅里葉變換、正交變換等)變換到變換域(如頻率域、正交矢量空間)中進(jìn)行描述。簡(jiǎn)單地講，即把信號(hào)由空間域變換到變換域中，用變換系數(shù)來(lái)描述。這些變換系數(shù)之間的相關(guān)性明顯下降，并且能量常常集中于低頻

39、或低序系數(shù)區(qū)域中，這樣就容易實(shí)現(xiàn)碼率的壓縮，而且還大大降低了實(shí)現(xiàn)的難度。,2020/11/17,64,5.4.5 其它限失真信源編碼,標(biāo)量量化: 連續(xù)信源限失真編碼的主要方法是量化，就是把連續(xù)的樣值離散化為某些量化級(jí)數(shù)，所以量化也可稱(chēng)為數(shù)字化。量化后的信號(hào)也可稱(chēng)為數(shù)字信號(hào)，這種轉(zhuǎn)換必將引入失真，量化時(shí)必須使這些失真最小。常用的量化方法有標(biāo)量量化和矢量量化兩種，所謂標(biāo)量量化是指每次只量化一個(gè)模擬樣本值，故又叫做零記憶量化。 矢量量化: 要想得到性能好的編碼，僅采用標(biāo)量量化是不可能的。在最佳編碼中，如將離散信源的多個(gè)符號(hào)進(jìn)行聯(lián)合編碼可提高效率，這對(duì)連續(xù)信源也是如此。當(dāng)把多個(gè)信源符號(hào)聯(lián)合起來(lái)形成多維

40、矢量，再對(duì)矢量進(jìn)行標(biāo)量量化時(shí)，自由度將更大，同樣的失真下，量化級(jí)數(shù)可進(jìn)一步減少，碼率可進(jìn)一步壓縮。這種量化叫做矢量量化。,2020/11/17,65,語(yǔ)音壓縮編碼 語(yǔ)音壓縮編碼可分為波形編碼、參量編碼和混合編碼三大類(lèi)型。 波形編碼的目的是在接收端恢復(fù)發(fā)端原語(yǔ)音的波形，并以波形的保真度即自然度為主要度量指標(biāo)。 參量編碼不同于波形編碼，它主要跟蹤波形產(chǎn)生的過(guò)程，并且僅傳送反映波形變化的主要參量，在接收端根據(jù)語(yǔ)音產(chǎn)生過(guò)程，利用這些參量恢復(fù)語(yǔ)音。它又稱(chēng)為聲碼器，其主要度量指標(biāo)是可懂度。 混合編碼則介于波形編碼與參量編碼之間，即在參量編碼的基礎(chǔ)上，引入了波形編碼的特征，以達(dá)到改善自然度的目的，因此，它一

41、般也稱(chēng)混合編碼為軟聲碼器。由于語(yǔ)音信源是屬于連續(xù)的限失真信源,可以根據(jù)R(D)函數(shù)理論探討波形編碼的理論壓縮極限。,2020/11/17,66,圖像壓縮編碼,在20世紀(jì)90年代，計(jì)算機(jī)技術(shù)、微電子技術(shù)和通信技術(shù)得到迅猛發(fā)展。多媒體計(jì)算機(jī)、多媒體數(shù)據(jù)庫(kù)、多媒體通信、多媒體表現(xiàn)技術(shù)等多媒體研究領(lǐng)域也成為計(jì)算機(jī)和通信發(fā)展中的一個(gè)重要研究熱點(diǎn)。其中面臨最大的問(wèn)題是數(shù)據(jù)量巨大的“爆炸”。文件、表格、工程圖紙等二值圖像的數(shù)據(jù)已較大。 但相比之下，語(yǔ)音信號(hào)、靜止灰值圖像、彩色靜止圖像電視圖像、高清晰電視圖像等的數(shù)據(jù)量更是巨大。特別是高清晰電視圖像。一般電視圖像的數(shù)據(jù)量要比語(yǔ)音的數(shù)據(jù)量大上千倍。因此，研究有效

42、的數(shù)據(jù)壓縮和解壓縮的技術(shù)成為重要的、關(guān)鍵的研究方向。信息率失真理論從理論上指出，解決這種問(wèn)題的途徑是存在的、可能的。,2020/11/17,67,靜止圖像壓縮編碼 新聞圖片、醫(yī)療圖片、衛(wèi)星圖片以及圖像文獻(xiàn)資料等均屬于靜止圖像。這類(lèi)靜止圖片的壓縮，對(duì)傳輸和存儲(chǔ)都具有重要的應(yīng)用價(jià)值。靜止圖像壓縮編碼一般可劃分為無(wú)失真編碼與限失真編碼兩大類(lèi)。對(duì)無(wú)失真編碼一般采用霍夫曼編碼或者算術(shù)編碼。限失真編碼主要有：幀內(nèi)、幀間的預(yù)測(cè)編碼；二維變換編碼：KLT、DFT、DCT、HRT、SLT等等，以及子帶編碼、分層編碼、輪廓編碼、分形編碼、小波變換等等，但主要以預(yù)測(cè)編碼和正交變換編碼為主,JPEG標(biāo)準(zhǔn)是用于多個(gè)灰度及色度連續(xù)變化的靜止圖像編碼的國(guó)際標(biāo)準(zhǔn)。,2020/11/17,68,活動(dòng)圖像壓縮編碼 廣播電視、會(huì)議電視和可視電話(huà)等運(yùn)動(dòng)圖像信號(hào)，除幀內(nèi)像素間有相關(guān)性而外，幀與幀之間也有很強(qiáng)的相關(guān)性，所以對(duì)這類(lèi)信號(hào)的處理常用幀間預(yù)測(cè)技術(shù)。幀間預(yù)測(cè)不僅要利用本行的前幾個(gè)樣值和前幾行的相鄰取樣值，而且要利用上一幀或前幾幀的取樣值來(lái)估計(jì)當(dāng)前幀內(nèi)的像素值，因此幀間預(yù)測(cè)是一種三維預(yù)測(cè)方法。它在幀內(nèi)預(yù)測(cè)的基礎(chǔ)上，再利用幀間的時(shí)間相關(guān)性進(jìn)一步消除圖像信號(hào)的冗余度，提高壓縮比。,2020/11/17,69,視頻壓縮編碼 電視信號(hào)具有很強(qiáng)的相關(guān)性和巨大