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

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

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

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

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

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

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

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

8、信源符號所對應(yīng)的碼元序列,即相應(yīng)的碼字。,2020/11/17,16,哈夫曼的編法并不惟一。 每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。 不同的碼元分配,得到的具體碼字不同,但碼長Ki不變,平均碼長也不變,所以沒有本質(zhì)區(qū)別； 縮減信源時,若合并后的新符號概率與其他符號概率相等,從編碼方法上來說,這幾個符號的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。 不同的編法得到的碼字長度Ki也不盡相同。,哈夫曼編碼,2020/11/17,17,m進(jìn)制哈夫曼編碼,在編m進(jìn)制哈夫曼碼時為了使平

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

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

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

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

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

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

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

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

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

18、的白游程概率,L為游程最大長度,對文件傳真L=1728， 白游程平均編碼長度應(yīng)滿足:,令 為白游程長的平均像素數(shù),P84:5-2-9,每像數(shù)的編碼比特數(shù),平均每像素的熵值,2020/11/17,33,黑游程熵：,黑游程平均編碼長應(yīng)滿足,經(jīng)過黑、白平均可得每個像素的熵值,每個像素的編碼比特數(shù),2020/11/17,34,黑、白游程分別最佳編碼后,由每個像素的熵hWB 即可得到最小比特率。 極限壓縮比,游程編碼,2020/11/17,35,對中文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,對中文A4文件,7種樣張的統(tǒng)計極限壓縮比 K0 10倍,2020/11/17,36,5.4.2 算術(shù)編碼,算術(shù)編碼是近十多年來發(fā)展迅速的一種無失真信源編碼,它與最佳的哈夫曼碼相比,理論性能稍加遜色,而實際壓縮率和編碼效率卻往往還優(yōu)于哈夫曼碼,且實現(xiàn)簡單,故很受工程上的重視。 算術(shù)編碼不同于哈夫曼碼,它是非分組(非塊)碼。它從全序列出發(fā),考慮符號之間的關(guān)系來進(jìn)行

20、編碼。 算術(shù)編碼利用了累積概率的概念。 算術(shù)碼主要的編碼方法是計算輸入信源符號序列所對應(yīng)的區(qū)間。,2020/11/17,37,算術(shù)碼的主要概念,算術(shù)碼的主要概念： 把信源輸出序列的概率和實數(shù)段0,1中的一個數(shù)C聯(lián)系起來。 設(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)信源輸出的第一個符號S1 = a1時,數(shù)C的值處在0,0.6 當(dāng)信源輸出的第一個符號S1 = a2時,數(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),隨著序列的長度不斷增加,C所在區(qū)間的長度就越短,也就可以更加精確地確定C的位置,2020/11/17,38,累積概率,設(shè)信源符號集A=a1,a2,an,其相應(yīng)概率分布為p(ai), p(ai) 0(i=1,2, ,n) 信源符號的累積概率為,顯然 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)的兩個點來表示;,P1,p1,P2,P3,P4,1,p2,p3,0,

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

23、；,算術(shù)編碼,2020/11/17,41,若輸入第二個符號為“1”,S =“01”, S =“01”所對應(yīng)的區(qū)間是在區(qū)間0, P(1) )中進(jìn)行分割； 符號序列“00”對應(yīng)的區(qū)間寬度為 A(00)=A(0) p(0)=p(0)p(0)= p(00)； 對應(yīng)的區(qū)間為0,P(S =“01”)。 符號序列“01”對應(yīng)的區(qū)間寬度為 A(01) =A(0) p(1)= p(0)p(1)= p(01) = A(0)A(00)； 對應(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、輸入符號序列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”對應(yīng)的區(qū)間是對區(qū)間P(S), P (1)進(jìn)行分割 序列S0=“010”對應(yīng)的區(qū)間寬度為 A(S =“010”)=A(S=“01”)p(0)=A(S) p(0) 其對應(yīng)的區(qū)間為P(S), P(S)+

25、 A(S) p(0)； 序列S1=“011”對應(yīng)的區(qū)間寬度為 A(S=“011”)=A(S)p(1) =A(S =“01”)A(S =“010”)= A(S)A(S0) 其對應(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)前面輸入符號序列為S,若接著輸入一個“0”, 累積概率: P(S 0)= P(S) 對應(yīng)區(qū)間寬度為： A(S0)=A(S)p(0),若接著輸入的一個符號是“1”， 累積概

26、率: P(S1)= P(S) + A(S)p(0) 對應(yīng)區(qū)間寬度為： A(S1) = A(S)p(1) =A(S)A(S0),信源符號0的區(qū)間寬度 A(0)= p(0),符號1的區(qū)間寬度 A(1)=p(1),符號“00”區(qū)間寬度 A(00)=p(00),信源符號“01”區(qū)間寬度 A(01)=p(01)=A(0)-A(00),2020/11/17,45,符號序列對應(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) 信源符號序列S所對應(yīng)區(qū)間的寬度等于符號序列S的概率p(S)。,算術(shù)編碼,2020/11/17,46,算術(shù)編

28、碼,二元信源符號序列的累積概率遞推公式,Sr表示前面信源符號序列為S,接著再輸入符號為r P(0)=0， P(1) = p(0) P(S0)= P(S) P(S1)= P(S) + p(S) p(0),信源符號序列所對應(yīng)區(qū)間的寬度遞推公式,2020/11/17,47,例：已輸入二元符號序列為S=“011”,接著再輸入符號為“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) 對應(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ù)編碼,實際應(yīng)用中,采用累積概率P(S)表示碼字C(S),符號概率p(S)表示狀態(tài)區(qū)間A(S),則有： C(S,r) = C(S)+A(S)Pr A(S,r) = A(S) pr,實際編碼時,只需兩個存儲器,起始時可令: A() =1, C() = 0 每輸入一個信源符號,存儲器C和A 就按照上式更新一次,直至信源符號輸入完畢,就可將存儲器C的內(nèi)容作為

30、該序列的碼字輸出。,2020/11/17,50,算術(shù)編碼,在編碼過程中,每輸入一個符號要進(jìn)行乘法和加法運算,所以稱為算術(shù)編碼。 通過關(guān)于信源符號序列的累積概率的計算,把區(qū)間分割成許多小區(qū)間,不同的信源符號序列對應(yīng)不同的區(qū)間為P(S), P(S) + p(S) ?？扇⌒^(qū)間內(nèi)的一點來代表這序列。,2020/11/17,51,算術(shù)編碼,編碼方法： 將符號序列的累積概率寫成二進(jìn)位的小數(shù)，取小數(shù)點后L位,若后面有尾數(shù),就進(jìn)位到第L位,這樣得到的一個數(shù)C,并使L滿足,取整,2020/11/17,52,例：設(shè)二元無記憶信源S=0,1,其p(0)=1/4,p(1)=3/4。 對二元序列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ù)測編碼,預(yù)測編碼是數(shù)據(jù)壓縮三大經(jīng)典技術(shù)（統(tǒng)計編碼、預(yù)測編碼、變換編碼）之一，它是建立在信源數(shù)據(jù)相關(guān)性之上的。由信息理論可知，對于相關(guān)性很強(qiáng)的信源，條件熵可遠(yuǎn)小于無條件熵，因此人們常采用盡量解除相關(guān)性的辦法，使信源輸出轉(zhuǎn)化為獨立序列，以利于進(jìn)一步壓縮碼率。 常用的解除相關(guān)性的措施是預(yù)測和變換，其實質(zhì)都是進(jìn)行序列的一種映射。一般來說，預(yù)測編碼有可能完全解除序列的相關(guān)性，但必需確知序列的概率特性；變換編碼一般只解除矢量內(nèi)部的相關(guān)性，但它可有許多可供選擇的變換方法，以適應(yīng)不同的信源特性。下面介紹預(yù)測編碼的

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

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

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

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

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

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

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

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

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

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