信息論及編碼第5章

1、第五章信源編碼（第十講）（2課時(shí)）主要內(nèi)容：（1）編碼的定義（2）無(wú)失真信源編碼重點(diǎn)：定長(zhǎng)編碼定理、變長(zhǎng)編碼定理、最佳變長(zhǎng)編碼。難點(diǎn)：定長(zhǎng)編碼定理、哈夫曼編碼方法。作業(yè)：5。2，5。4，5。6；說(shuō)明：本堂課推導(dǎo)內(nèi)容較多，枯燥平淡，不易激發(fā)學(xué)生興趣，要注意多討論用途。另外，注意，解題方法。多加一些內(nèi)容豐富知識(shí)和理解。通信的實(shí)質(zhì)是信息的傳輸。而高速度、高質(zhì)量地傳送信息是信息傳輸?shù)幕締?wèn)題。將信源信息通過(guò)信道傳送給信宿，怎樣才能做到盡可能不失真而又快速呢？這就需要解決兩個(gè)問(wèn)題：第一，在不失真或允許一定失真的條件下，如何用盡可能少的符號(hào)來(lái)傳送信源信息；第二，在信道受干擾的情況下，如何增加信號(hào)的抗干擾能

2、力，同時(shí)又使得信息傳輸率最大。為了解決這兩個(gè)問(wèn)題，就要引入信源編碼和信道編碼。一般來(lái)說(shuō)，提高抗干擾能力（降低失真或錯(cuò)誤概率）往往是以降低信息傳輸率為代價(jià)的；反之，要提高信息傳輸率常常又會(huì)使抗干擾能力減弱。二者是有矛盾的。然而在信息論的編碼定理中，已從理論上證明，至少存在某種最佳的編碼或信息處理方法，能夠解決上述矛盾，做到既可靠又有效地傳輸信息。這些結(jié)論對(duì)各種通信系統(tǒng)的設(shè)計(jì)和估價(jià)具有重大的理論指導(dǎo)意義。§3.1編碼的定義編碼實(shí)質(zhì)上是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換。討論無(wú)失真信源編碼，可以不考慮干擾問(wèn)題，所以它的數(shù)學(xué)描述比較簡(jiǎn)單。圖3.1是一個(gè)信源編碼器，它的輸入是信源符

3、號(hào)Ss1,s2,sq，同時(shí)存在另一符號(hào)Xx1,x2,xr，一般來(lái)說(shuō)，元素xj是適合信道傳輸?shù)?，稱為碼符號(hào)（或者碼元）。編碼器的功能就是將信源符號(hào)集中的符號(hào)Si（或者長(zhǎng)為N的信源符號(hào)序列）變換成由xj（j=1,2,3,r）組成的長(zhǎng)度為li的一一對(duì)應(yīng)的序列。輸出的碼符號(hào)序列稱為碼字，長(zhǎng)度li稱為碼字長(zhǎng)度或簡(jiǎn)稱碼長(zhǎng)?？梢?jiàn)，編碼就是從信源符號(hào)到碼符號(hào)的一種映射。若要實(shí)現(xiàn)無(wú)失真編碼，則這種映射必須是一一對(duì)應(yīng)的，并且是可逆的。碼符號(hào)的分類：下圖是一個(gè)碼分類圖下面，我們給出這些碼的定義。1. 二元碼若碼符號(hào)集為X=0;1，所有碼字都是一些二元序列，則稱為二元碼。二元碼是數(shù)字通信和計(jì)算機(jī)系統(tǒng)中最常用的一種碼。

4、2. 等長(zhǎng)碼：若一組碼中所有碼字的碼長(zhǎng)都相同，即li=l（i=1,2,q），則稱為等長(zhǎng)碼。3. 變長(zhǎng)碼：若一組碼組中所有碼字的碼長(zhǎng)各不相同，則稱為變長(zhǎng)碼。4. 非奇異碼：若一組碼中所有碼字都不相同，則稱為非奇異碼。5. 奇異碼：若一組碼中有相同的碼字，則稱為奇異碼。6. 唯一可譯碼：若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能唯一地被譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱為唯一可譯碼，否則就稱為非唯一可譯碼。7. 非即時(shí)碼和即時(shí)碼：如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，還要等下一個(gè)碼字開(kāi)始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時(shí)碼。如果收到一個(gè)完整的碼字以后，就可以立即譯碼，則叫做即時(shí)碼。即

5、時(shí)碼要求任何一個(gè)碼字都不是其他碼字的前綴部分，也叫做異前綴碼。碼樹(shù)：即時(shí)碼的一種簡(jiǎn)單構(gòu)造方法是樹(shù)圖法。對(duì)給定碼字的全體集合C=W1,W2,Wq來(lái)說(shuō),可以用碼樹(shù)來(lái)描述它。所謂樹(shù)，就是既有根、枝，又有節(jié)點(diǎn)，如圖5.2（80業(yè)）所示，圖中，最上端A為根節(jié)點(diǎn)，A、B、C、D、E皆為節(jié)點(diǎn)，E為終端節(jié)點(diǎn)。A、B、C、D為中間節(jié)點(diǎn)，中間節(jié)點(diǎn)不安排碼字，而只在終端節(jié)點(diǎn)安排碼字，每個(gè)終端節(jié)點(diǎn)所對(duì)應(yīng)的碼字就是從根節(jié)點(diǎn)出發(fā)到終端節(jié)點(diǎn)走過(guò)的路徑上所對(duì)應(yīng)的符號(hào)組成，如圖5.2中的終端節(jié)點(diǎn)E,走過(guò)的路徑為ABCDE，所對(duì)應(yīng)的碼符號(hào)分別為0、0、0、1，則E對(duì)應(yīng)的碼字為0001?？梢钥闯觯礃?shù)圖法構(gòu)成的碼一定滿足即時(shí)碼的定

6、義（一一對(duì)應(yīng)，非前綴碼）。從碼樹(shù)上可以得知，當(dāng)?shù)趇階的節(jié)點(diǎn)作為終端節(jié)點(diǎn)，且分配碼字，則碼字的碼長(zhǎng)為i任一即時(shí)碼都可以用樹(shù)圖法來(lái)表示。當(dāng)碼字長(zhǎng)度給定后，用樹(shù)圖法安排的即時(shí)碼不是唯一的。如圖3.2中，如果把左樹(shù)枝安排為1，右樹(shù)枝安排為0，則得到不同的結(jié)果。對(duì)一個(gè)給定的碼，畫出其對(duì)應(yīng)的樹(shù)，如果有中間節(jié)點(diǎn)安排了碼字，則該碼一定不是即時(shí)碼。每個(gè)節(jié)點(diǎn)上都有r個(gè)分支的樹(shù)稱為滿樹(shù)，否則為非滿樹(shù)。即時(shí)碼的碼樹(shù)圖還可以用來(lái)譯碼。當(dāng)收到一串碼符號(hào)序列后，首先從根節(jié)點(diǎn)出發(fā)，根據(jù)接收到的第一個(gè)碼符號(hào)來(lái)選擇應(yīng)走的第一條路徑，再根據(jù)收到的第二個(gè)符號(hào)來(lái)選擇應(yīng)走的第二條路徑，直到走到終端節(jié)點(diǎn)為止，就可以根據(jù)終端節(jié)點(diǎn)，立即判斷出

7、所接收的碼字。然后從樹(shù)根繼續(xù)下一個(gè)碼字的判斷。這樣，就可以將接收到的一串碼符號(hào)序列譯成對(duì)應(yīng)的信源符號(hào)序列?？死蛱兀↘raft）不等式定理3.1對(duì)于碼符號(hào)為X=Xi,X2,Xr的任意唯一可譯碼，其碼字為Wl,W2,Wq，所對(duì)應(yīng)的碼長(zhǎng)為ll,|2lq,則必定滿足克拉夫特不等式反之，若碼長(zhǎng)滿足上面的不等式，則一定存在具有這樣碼長(zhǎng)的即時(shí)碼。注意：克拉夫特不等式只是說(shuō)明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)（可以排除，不能肯定）。如0，10，010，111滿足克拉夫特不等式，但卻不是唯一可譯碼。例題：設(shè)二進(jìn)制碼樹(shù)中X=X1,X2,X3,X4，對(duì)應(yīng)的I1=1,12=2,13=2,14=3，由上述

8、定理，可得因此不存在滿足這種碼長(zhǎng)的唯一可譯碼?？梢杂脴?shù)碼進(jìn)行檢查。唯一可譯碼的判斷法（變長(zhǎng)）：將碼C中所有可能的尾隨后綴組成一個(gè)集合F，當(dāng)且僅當(dāng)集合F中沒(méi)有包含任一碼字，則可判斷此碼C為唯一可譯碼。集合F的構(gòu)成方法：首先，觀察碼C中最短的碼字是否是其它碼字的前綴，若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又有可能是某些碼字的前綴，再將這些尾隨后綴產(chǎn)生的新的尾隨后綴列出，然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產(chǎn)生的尾隨后綴列出，依此下去，直到?jīng)]有一個(gè)尾隨后綴是碼字的前綴為止。這樣，首先獲得了由最短的碼字能引起的所有尾隨后綴，接著，按照上述步驟將次短碼字、等等所有碼字可能產(chǎn)生

9、的尾隨后綴全部列出。由此得到由碼C的所有可能的尾隨后綴的集合F。例題：設(shè)碼C=0,10,1100,1110,1011,1101，根據(jù)上述測(cè)試方法，判斷是否是唯一可譯碼。解：1.先看最短的碼字：“0”，它不是其他碼字前綴，所以沒(méi)有尾隨后綴。2.再觀察碼字“10”，它是碼字“1011的”前綴，因此有尾隨后綴。所以，集合F=11，00，10，01，其中“10”為碼字，故碼C不是唯一可譯碼。§3.2定長(zhǎng)編碼定理前面已經(jīng)說(shuō)過(guò)，所謂信源編碼，就是將信源符號(hào)序列變換成另一個(gè)序列（碼字）。設(shè)信源輸出符號(hào)序列長(zhǎng)度為L(zhǎng),碼字的長(zhǎng)度為Kl,編碼的目的，就是要是信源的信息率最小，也就是說(shuō)，要用最少的符號(hào)來(lái)代

10、表信源。在定長(zhǎng)編碼中，對(duì)每一個(gè)信源序列，Kl都是定值，設(shè)等于K，我們的目的是尋找最小K值。要實(shí)現(xiàn)無(wú)失真的信源編碼，要求信源符號(hào)Xi（i=1,2,q）與碼字是一一對(duì)應(yīng)的，并求由碼字組成的符號(hào)序列的逆變換也是唯一的（唯一可譯碼）。定長(zhǎng)編碼定理：由L個(gè)符號(hào)組成的、每個(gè)符號(hào)熵為Hl(X)的無(wú)記憶平穩(wěn)信源符號(hào)序列X1X2X3Xl用Kl個(gè)符號(hào)Y1Y2Ykl(每個(gè)符號(hào)有m種可能值)進(jìn)行定長(zhǎng)變碼。對(duì)任意0,0,只要KllogmLHl(X)則當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于；反之，當(dāng)時(shí)，譯碼差錯(cuò)一定是有限值，當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。式中，左邊是輸出碼字每符號(hào)所能載荷的最大信息量所以等長(zhǎng)編碼定理告訴我們，

11、只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實(shí)現(xiàn)幾乎無(wú)失真的編碼。條件時(shí)所取得符號(hào)數(shù)L足夠大。設(shè)差錯(cuò)概率為P，信源序列的自方差為貝U有：22當(dāng)(X)和均為定值時(shí)，只要L足夠大，P可以小于任一整數(shù)，即此時(shí)要求：只要足夠小，就可以幾乎無(wú)差錯(cuò)地譯碼，當(dāng)然代價(jià)是L變得更大。令為碼字最大平均符號(hào)信息量。定義編碼效率為：最佳編碼效率為無(wú)失真信源編碼定理從理論上闡明了編碼效率接近于1的理想編碼器的存在性，它使輸出符號(hào)的信息率與信源熵之比接近于1，但要在實(shí)際中實(shí)現(xiàn)，則要求信源符號(hào)序列的L非常大進(jìn)行統(tǒng)一編碼才行，這往往是不現(xiàn)實(shí)的。例如：例題：設(shè)離散無(wú)記憶信源概率空間為信源熵為自信息方差為對(duì)信源符號(hào)采用定

12、長(zhǎng)二元編碼，要求編碼效率90%,無(wú)記憶信源有Hl(X)H(X)，因此Hl(X)H(X)，因此冊(cè)90%可以得到0.28如果要求譯碼錯(cuò)誤概率如果要求譯碼錯(cuò)誤概率106，則L2(x)2789.81010由此可見(jiàn)，在對(duì)編碼效率和譯碼錯(cuò)誤概率的要求不是十分苛刻的情況下，就需要8L10個(gè)信源符號(hào)一起進(jìn)行編碼，這對(duì)存儲(chǔ)和處理技術(shù)的要求太高，目前還無(wú)法實(shí)現(xiàn)。如果用3比特來(lái)對(duì)上述信源的8個(gè)符號(hào)進(jìn)行定長(zhǎng)二元編碼，L=1,此時(shí)可實(shí)現(xiàn)譯碼無(wú)差錯(cuò)，但編碼效率只有2.55/3=85%。因此，一般說(shuō)來(lái)，當(dāng)L有限時(shí)，高傳輸效率的定長(zhǎng)碼往往要引入一定的失真和譯碼錯(cuò)誤。解決的辦法是可以采用變長(zhǎng)編碼。§3.3最佳編碼最佳

13、碼：對(duì)于某一信源和某一碼符號(hào)集來(lái)說(shuō)，若有一唯一可譯碼，其平均碼長(zhǎng)K小于所有其他唯一可譯碼的平均長(zhǎng)度。為此必須將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)編以長(zhǎng)的碼字，使得平均碼字長(zhǎng)度最短。能獲得最佳碼的編碼方法：香農(nóng)(Shannon)費(fèi)諾(Fano)哈夫曼(Huffman)1、香農(nóng)編碼方法香農(nóng)第一定理指出了平均碼長(zhǎng)與信源之間的關(guān)系，同時(shí)也指出了可以通過(guò)編碼使平均碼長(zhǎng)達(dá)到極限值，這是一個(gè)很重要的極限定理。香農(nóng)第一定理指出，選擇每個(gè)碼字的長(zhǎng)度Ki滿足下式：1Ki=log取整Pi即：log2pi<Ki<1log2pi就可以得到這種碼。這種編碼方法稱為香農(nóng)編碼。例：設(shè)無(wú)記憶信源的概率空間為

14、：計(jì)算各符號(hào)的碼字長(zhǎng)度：K1=log2=1K2=log4=2K3=K4=log8=3用圖示碼樹(shù)，可得各自的碼字：U1：(0),U2：(10),U3：(110),U4：(111)信息熵H(U):信源符號(hào)的平均碼長(zhǎng)：編碼效率對(duì)于這種信源，香農(nóng)編碼是最佳編碼。碼樹(shù)達(dá)到滿樹(shù)。香農(nóng)編碼法多余度稍大，實(shí)用性不大，但有重要的理論意義。編碼方法如下：將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列P(U1)>P(U2)p(Un)確定碼長(zhǎng)Ki(整數(shù))：1Ki=log取整Pi為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)制數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制數(shù)。例：UU1U

15、2U3U4U5信源符號(hào)Ui符號(hào)概率p(u)累加概率Pi-logp(u)碼字長(zhǎng)度Ki碼字U10.401.32200U20.30.41.73201U30.20.72.323101U40.050.94.3511100U50.050.954.3511101以i=3為例，計(jì)算各符號(hào)的碼字長(zhǎng)度:K3=Iog0.2=3累加概率P4=0.70.10110101由圖，這些碼字沒(méi)有占滿所有樹(shù)葉，所以是非最佳碼。H(U)平均碼長(zhǎng)：1.95編碼效率：為了提高編碼效率，首先應(yīng)達(dá)到滿樹(shù)；例如把U4U5換成A、B這些前面的節(jié)點(diǎn)，就可減小平均碼長(zhǎng)。所以不應(yīng)先規(guī)定碼長(zhǎng)，而是由碼樹(shù)來(lái)規(guī)定碼字，可得更好的結(jié)果。2、費(fèi)諾編碼方法費(fèi)諾

16、編碼屬于概率匹配編碼，但它不是最佳的編碼方法。編碼過(guò)程如下：將信源符號(hào)接概率值分為兩大組，使兩個(gè)組的概率之和近于相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和“1”。將每一大組的信源符號(hào)進(jìn)一步再分成兩組，使劃分后的兩個(gè)組的概率之和近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號(hào)“0”和“1”。如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。徇UU1U2U3U4U5例：信源符號(hào)Ui符號(hào)概率p(u)第1次分組第2次分組第3次分組碼字碼長(zhǎng)U10.400002U40.05100103U50.0510113U20.310102U30.21112該費(fèi)諾碼的平均碼長(zhǎng)編碼效率：顯然，費(fèi)諾碼比香農(nóng)碼

17、的平均碼長(zhǎng)小，編碼效率高。其實(shí)這樣編碼的效率還不是最高的，現(xiàn)用另一種分割方法:信源符號(hào)Ui符號(hào)概率P（U）第1次分組第2次分組第3次分組第4次分組碼字碼長(zhǎng)U10.4001U20.30102U30.2101103U40.0511011104U50.05111114該費(fèi)諾碼的平均碼長(zhǎng)編碼效率：可見(jiàn)編碼效率又有所提高。事實(shí)上這已是最佳編碼，就是說(shuō)編碼效率已不能再提高。但這樣試探尋找分割方法總不是辦法，因而赫夫曼提出一種編碼方法，并證明這種編碼在塊碼中已是最佳的。3、哈夫曼編碼方法哈夫曼編碼也是用碼樹(shù)來(lái)分配各符號(hào)的碼字。費(fèi)諾碼是從樹(shù)根開(kāi)始，把各節(jié)點(diǎn)分給某子集；若子集已是單點(diǎn)集，它就是一片葉而作為碼字。

18、而赫夫曼編碼是先給每一符號(hào)一片樹(shù)葉，逐步合并成節(jié)點(diǎn)直到樹(shù)根。哈夫曼編碼的步驟如下：將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列P（U1）P（U2）P（Un）取兩個(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è)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字。例：給定離散信源如下：平均碼長(zhǎng)：7Kp（uJKii10.220.1920.1830.1730.1530.1040.014編碼效率2.72哈夫曼編碼方法得到的碼并非是唯一

19、的。非唯一的原因：每次對(duì)信源縮減時(shí)，賦予信源最后兩個(gè)概率最小的符號(hào)，用0和1是可以任意意的，所以可以得到不同的哈夫曼碼，但不會(huì)影響碼字的長(zhǎng)度。對(duì)信源進(jìn)行縮減時(shí)兩個(gè)概率最小的符號(hào)合并后的概率與其它信源符號(hào)的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會(huì)得到不同的哈夫曼碼。此時(shí)將影響碼字的長(zhǎng)度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。例：給定離散信源如下：有兩種哈夫曼編碼方法如下圖所示：平均碼長(zhǎng)：因?yàn)檫@兩種碼有相同的平均碼長(zhǎng)，所以有相同的編碼效率，但每個(gè)信源符號(hào)的碼長(zhǎng)卻不相同。在這兩種不同的碼中，選擇哪個(gè)碼好呢？我們引進(jìn)碼字任度Ki偏離平均碼長(zhǎng)K的方差b2，

20、即卩分別計(jì)算上例中兩種碼的方差可見(jiàn)，第一種編碼方法的方差要小許多。所以，對(duì)于有限長(zhǎng)的不同信源序列，用第一種方法所編得的碼序列長(zhǎng)度變化較小。因此相對(duì)來(lái)說(shuō)選擇第一種編碼方法要更好些。由此得出，在哈夫曼編碼過(guò)程中，當(dāng)縮減信源的概率分布重新排列時(shí)，應(yīng)使合并得來(lái)的概率和盡量處于是高的位置。這樣可使合并的元素重復(fù)編碼次數(shù)減少，使短碼得到充分利用從以上實(shí)例中可以看出，哈夫曼碼具有以下三個(gè)特點(diǎn)：哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，即Pi>pj有KiVKj,充分利用了短碼?？s減信源的最后二個(gè)碼字總是最后一位碼元不同，前面各位碼元相同（二元編碼情況），從而保證了哈夫曼是即

21、時(shí)碼。每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)。這三個(gè)特點(diǎn)保證了所得的哈夫曼碼一定是最佳碼。第五章信源編碼（第十一講）（2課時(shí)）主要內(nèi)容：（1）限失真信源編碼定理（2）常用信源編碼方法簡(jiǎn)介（游程編碼、矢量量化編碼、算術(shù)編碼)重點(diǎn)：常用信源編碼方法簡(jiǎn)介。難點(diǎn)：限失真信源編碼定理、限失真信源編碼定理。特別提示：運(yùn)用說(shuō)明：本堂課推導(dǎo)內(nèi)容較多，枯燥平淡，不易激發(fā)學(xué)生興趣，要注意多討論用途。另外，注意，解題方法。多加一些內(nèi)容豐富知識(shí)和理解。作業(yè)：靈活運(yùn)用。課外仍以學(xué)生復(fù)習(xí)。§限失真信源編碼定理定理(限失真信源編碼定理)設(shè)R(D)為離散無(wú)記憶信源X的信息率失真函數(shù)，R為信息傳輸率，則當(dāng)信息率R&g

22、t;R(D)，只要信源序列長(zhǎng)度L足夠長(zhǎng)，一定存在一種編碼方法，其譯碼失真小于或等于D+為任意小的正數(shù)；反之，若R<R(D),則無(wú)論采用什么樣的編碼方法，其譯碼失真必大于D。如果是二元信源，對(duì)于任意小的&>0,每一個(gè)信源符號(hào)的平均碼長(zhǎng)滿足如下公式：該定理指出，在失真限度內(nèi)使信息率任意接近R(D)的編碼方法存在，然而，若信息率小于R(D),平均失真一定會(huì)超過(guò)失真限度D。對(duì)于連續(xù)平穩(wěn)無(wú)記憶信源，雖然無(wú)法進(jìn)行無(wú)失真編碼，但在限失真情況下，有與該定理一樣的編碼定理。該定理只說(shuō)明最佳編碼是存在的，但對(duì)于如何進(jìn)行編碼卻一無(wú)所知，因而就不能像無(wú)損編碼那樣從證明過(guò)程中引出概率匹配的編碼方法,

23、損編碼那樣從證明過(guò)程中引出概率匹配的編碼方法,般只能從優(yōu)化的思路去求最佳編碼。這個(gè)定理證明了允許失真D確定后，總存在一種編碼方法,使信息傳輸率R大于R(D)且可任意接近R(D),而平均失真小于允許失真且可任意接近R(D),而平均失真小于允許失真D。反之，若R<R(D),那么該編碼的平D的情況下，平均每均失真將大于D。如果用二進(jìn)制符號(hào)進(jìn)行編碼的話，在允許一定失真?zhèn)€信源符號(hào)所需的二元碼符號(hào)的下限值就是R(D)。由此可見(jiàn)，信息率失真函數(shù)R(D)確實(shí)是在允許失真度為D的情況下信源信息壓縮的下限值。當(dāng)信源給定后，無(wú)失真信源壓縮的極限值是信源熵H(U);有失真信源壓縮的極限值是信息率失真函數(shù)R(D)

24、。在給定某D后，一般R(D)<H(U)。同樣，該定理只是一個(gè)存在定理。至于如何尋找最佳壓縮編碼方法，定理中并沒(méi)有給出。在實(shí)際應(yīng)用中，該定理主要存在以下兩大類問(wèn)題。第一類問(wèn)題是，符合實(shí)際信源的R(D)函數(shù)的計(jì)算相當(dāng)困難。首先，需要對(duì)實(shí)際信源的統(tǒng)計(jì)特性有確切的數(shù)學(xué)描述。其次，需要對(duì)符合主客觀實(shí)際的失真給予正確的度量，否則不能求得符合主客觀實(shí)際的R(D)函數(shù)。例如，通常采用均方誤差來(lái)表示信源的平均失真度。但對(duì)于圖像信源來(lái)說(shuō)，均方誤差較小的編碼方法，人們視覺(jué)感到失真較大。所以，人們?nèi)圆捎弥饔^觀察來(lái)評(píng)價(jià)編碼方法的好壞。因此，如何定義符合主客觀實(shí)際情況的失真測(cè)度就是件較困難的事。第三，即便對(duì)實(shí)際信源

25、有了確切的數(shù)學(xué)描述，又有符合主客觀實(shí)際情況的失真測(cè)度，而信息率失真函數(shù)R(D)的計(jì)算還是比較困難的。第二類問(wèn)題是，即便求得了符合實(shí)際的信息率失真函數(shù)，還需研究采用何種實(shí)用的最佳編碼方法才能達(dá)到R(D)。目前，這兩方面工作都有進(jìn)展。尤其是對(duì)實(shí)際信源的各種壓縮方法，如對(duì)語(yǔ)音信號(hào)、電視信號(hào)和遙感圖像等信源的各種壓縮方法有了較大進(jìn)展。相信隨著數(shù)據(jù)壓縮技術(shù)的發(fā)展，限失真編碼理論中存在的問(wèn)題將會(huì)得到解決。§限失真信源編碼常用信源編碼方法一、游程編碼游程：指數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。二元序列只有兩種符號(hào)：“0”和“1”：連“0”段稱為“0”游程，游程長(zhǎng)度為L(zhǎng)(0)連“1”段稱為“1”游程，

26、游程長(zhǎng)度為L(zhǎng)(1)由于是二進(jìn)制序列，“0”游程和“1”游程總是交替出現(xiàn)。若規(guī)定二元序列總是從“0”開(kāi)始，第一個(gè)游程是“0”游程，則第二個(gè)游程必為“1”游程，第三個(gè)又是“0”游程對(duì)于隨機(jī)序列，游程的長(zhǎng)度是隨機(jī)的，其取值為1,2,3自至無(wú)窮。游程序列：用交替出現(xiàn)的“0”游程和“1”游程的長(zhǎng)度，來(lái)表示任意二元序列。例如二元序列0001可變換成如下游程序列己規(guī)定游程序列從“0”開(kāi)始，由上述游程序列，很容易恢復(fù)出原來(lái)的二元序列。游程序列已是多元序列，各長(zhǎng)度就可按哈夫曼編碼或其它方法處理以達(dá)到壓縮碼率的目的。這種從二元序列轉(zhuǎn)換成多元序列的方法，在實(shí)現(xiàn)時(shí)比以前的并元法簡(jiǎn)單；因?yàn)橛纬涕L(zhǎng)度的計(jì)數(shù)比較容易，得到游

27、程長(zhǎng)度后就可從碼表中找出碼字輸出，同時(shí)去數(shù)下一個(gè)游程長(zhǎng)度。此外，在減弱原有序列的符號(hào)間的相關(guān)性方面采用游程變換一般也比并元法更有效。當(dāng)然，要對(duì)二元序列進(jìn)行哈夫曼編碼時(shí)應(yīng)先測(cè)定“0”游程長(zhǎng)度和“1”游程長(zhǎng)度的概率分布，或由二元序列的概率特性去計(jì)算各種游程長(zhǎng)度的概率。設(shè)二元序列為獨(dú)立序列，“0”和“1”的概率分別為P0和P1，則“0”游程長(zhǎng)度L(0)的概率為式中L(0)=1,2，游程長(zhǎng)度至少是1。從理論上來(lái)說(shuō)，游程長(zhǎng)度可以是無(wú)窮，但很長(zhǎng)的游程實(shí)際出現(xiàn)的概率非常小。則“1”游程長(zhǎng)度L(1)的概率為“0”游程長(zhǎng)度的熵：L(0)1L(0)1H(P0)HL(O)pL(0)log2pL(0)popilog2

28、poPi-“0”L(0)1L(0)1Pi游程序列的平均游程長(zhǎng)度同理，“1”游程長(zhǎng)度的熵和平均游程長(zhǎng)度：變換后的游程序列是獨(dú)立序列游程變換后符號(hào)熵沒(méi)有變。因?yàn)橛纬套儞Q是一一對(duì)應(yīng)的可逆變換。所以變換后熵值不變。由于游程變換有較好的去相關(guān)效果，因而對(duì)游程序列進(jìn)行哈夫曼編碼，可獲得較高的編碼效率。假設(shè)“0”游程長(zhǎng)度的哈夫曼編碼效率為n0,“1”游程長(zhǎng)度的哈夫曼編碼效率為n1,由編碼效率的定義得二兀序列的編碼效率假設(shè)n0>n1，則有n0>n>n1當(dāng)“0”游程和“1”游程的編碼效率都很高時(shí)，采用游程編碼的效率也很高，至少不會(huì)低于較小的那個(gè)效率。要想編碼效率n盡可能高，應(yīng)使上式的分母盡可能

29、小，這就要求盡可能提高熵值較大的游程的編碼效率，因?yàn)樗谕帜钢姓嫉谋戎剌^大。理論上來(lái)說(shuō)游程長(zhǎng)度可從1到無(wú)窮。要建立游程長(zhǎng)度和碼字之間的一一對(duì)應(yīng)的碼表是困難的。一般情況下，游程越長(zhǎng)，出現(xiàn)的概率就越?。划?dāng)游程長(zhǎng)度趨向于無(wú)窮時(shí)，出現(xiàn)的概率也趨向于0。按哈夫曼碼的編碼規(guī)則，概率越小碼字越長(zhǎng)，但小概率的碼字對(duì)平均碼長(zhǎng)影響較小，在實(shí)際應(yīng)用時(shí)常對(duì)長(zhǎng)碼采用截?cái)嗵幚淼姆椒ㄈ∫粋€(gè)適當(dāng)?shù)膎值，游程長(zhǎng)度為1,2,2n-1,2n，所有大于2n者都按2n來(lái)處理。然后按照哈夫曼碼的編碼規(guī)則，將上列2n種概率從大到小排隊(duì)，構(gòu)成碼樹(shù)并得到相應(yīng)的碼字。二、矢量量化編碼要想得到性能好的編碼，僅采用標(biāo)量量化是不可能的。在最佳編碼中

30、，如將離散信源的多個(gè)符號(hào)進(jìn)行聯(lián)合編碼可提高效率，這對(duì)連續(xù)信源也是如此。當(dāng)把多個(gè)信源符號(hào)聯(lián)合起來(lái)形成多維矢量，再對(duì)矢量進(jìn)行標(biāo)量量化時(shí)，自由度將更大，同樣的失真下，量化級(jí)數(shù)可進(jìn)一步減少，碼率可進(jìn)一步壓縮。這種量化叫做矢量量化。實(shí)驗(yàn)證明，即使各信源符號(hào)相互獨(dú)立，多維量化通常也可壓縮信息率。因而矢量量化引起人們的興趣而成為當(dāng)前連續(xù)信源編碼的一個(gè)熱點(diǎn)。可是當(dāng)維數(shù)較大時(shí)，矢量量化尚無(wú)解析方法，只能求助于數(shù)值計(jì)算；而且聯(lián)合概率密度也不易測(cè)定，還需采用諸如訓(xùn)練序列的方法。一般來(lái)說(shuō)，高維矢量的聯(lián)合是很復(fù)雜的，雖已有不少方法，但其實(shí)現(xiàn)尚有不少困難，有待進(jìn)一步研究。設(shè)矢量量化器輸入集為X=X1,x2,，XN,XjX

31、,Xj=(Xj1,Xj2，,Xjk),XRk(k維歐幾里德空間)，把Rk劃分成J=2n個(gè)互不相交的子空間R1,R2，Rj.Yi，所有的Yi構(gòu)成,Yi叫碼字或碼矢，對(duì)J階K維的矢量量化，實(shí)質(zhì)上是判斷輸入子空間代表碼字Yi，即：Yi=Q(Xj),1wiwJ,這里Yi就是Xj的編碼。實(shí)際編碼時(shí)，在發(fā)送端只需記錄代表碼字求出每個(gè)子空間的質(zhì)心間，也叫碼書(或碼本)Y=Y1,丫2，Yj,Y為量化器的輸出空J(rèn)叫碼書的長(zhǎng)度。XjRk屬于哪個(gè)子空間Ri，然后輸出該Yi的下標(biāo)i，所以編碼過(guò)程是把X映射到I=1,2，J;而譯碼過(guò)程是在接收端依據(jù)收到的I代碼，查找碼書Y,獲得碼字Yi,NXK，所以矢量量化的壓縮用來(lái)代

32、替Xj。由于總的碼字個(gè)數(shù)J一般遠(yuǎn)小于總的輸入信號(hào)能力非常大。傳輸或存儲(chǔ)一個(gè)矢量所需比特為IbJ(一般J=2n)，它是一個(gè)K維矢量，就是K個(gè)輸入信號(hào)，所以每個(gè)輸入信號(hào)的平均比特只有IbJ/K，稱之為壓縮比。適當(dāng)選取碼書長(zhǎng)度和碼字維數(shù)K，可以獲得很大壓縮比。矢量量化中碼書的碼字越多，維數(shù)越大，失真就越小。只要適當(dāng)?shù)剡x擇碼字?jǐn)?shù)量，就能控制失真量不超過(guò)某一給定值，因此碼書控制著矢量的大小。矢量量化時(shí)每輸入一個(gè)Xj，都要和J個(gè)碼字Yi逐一比較，搜索與其最接近的碼字Yi。由于兩者均為K維矢量，所以工作量很大。矢量量化是定長(zhǎng)碼，容易處理。矢量量化由碼書Y和劃分Ri的條件惟一確定。當(dāng)碼書確定后，通過(guò)最近鄰域準(zhǔn)

33、則可以惟一確定區(qū)域分割。因此，最佳量化器的設(shè)計(jì)也就是最佳碼書Y的設(shè)計(jì)。前面，在討論一維標(biāo)量的最佳設(shè)計(jì)時(shí)，引入了此算法推廣到了多維空間，稱作MaxLivod的迭代算法，1980年Linde、Buzo和Gray將LBG算法。因LBG算法由于理論上的嚴(yán)密性和實(shí)現(xiàn)的簡(jiǎn)便性以及較好的設(shè)計(jì)效果而得到了廣泛的應(yīng)用,便性以及較好的設(shè)計(jì)效果而得到了廣泛的應(yīng)用,并成為各種改進(jìn)算法的基礎(chǔ)。有關(guān)LBG算法等知識(shí)請(qǐng)參閱有關(guān)文獻(xiàn)。法等知識(shí)請(qǐng)參閱有關(guān)文獻(xiàn)。三、算術(shù)編碼1、算術(shù)碼的主要概念：把信源輸出序列的概率和實(shí)數(shù)段0,1中的一個(gè)數(shù)p聯(lián)系起來(lái)。設(shè)信源字母表為a1,a2,其發(fā)生概率為p(a”=0.6,p(a2)=0.4。將0

34、,1分成兩個(gè)與概率比例相應(yīng)的區(qū)間,其發(fā)生概率為p(a”=0.6,p(a2)=0.4。將0,1分成兩個(gè)與概率比例相應(yīng)的區(qū)間,0,0.60.6,S1=a1時(shí)，數(shù)p的值處在0,0.6,S1=a2時(shí)，0.6,I。0,1t0,0.60.6,l0,0.360.36,0.60.6,0.840.84,1S1=a1S1=a2根據(jù)信源輸出的第二個(gè)字母S2的取值情況，可以更精確地確定出數(shù)p所在的區(qū)間位置。在信源輸出第n1個(gè)符號(hào)后，若p所在的位置為I當(dāng)信源輸出的第一個(gè)符號(hào)根據(jù)信源字母S1的情況，把p所在的段再次按概率比例分成An-1,Bn-1則當(dāng)信源輸出的第n個(gè)符號(hào)為：sn=ai時(shí)，sn=a2產(chǎn)n=An-1An=An

35、-1+06(Bn-1一An-1)_Bn=An-1+0.6(Bn-1一An-1)Bn=Bn-1按照這一方法，序列的概率剛好等于p所在區(qū)間的長(zhǎng)度。隨著序列的長(zhǎng)度不斷增加,P所在區(qū)間的長(zhǎng)度就越短，也就可以更加精確地確定P的位置。當(dāng)信源字母序列長(zhǎng)度趨于無(wú)限時(shí)，p所在區(qū)間成為一點(diǎn)。2、累積概率設(shè)信源字母表為A=a1,a2,ai,am,字母ai的概率p(ai)修正的累積概率為定義字母ak的累積概率為F(a1)=0,F(a2)=p(a1),F(a3)=p(a1)+p(a2)p(ak)=F(ak+1)-F(ak)當(dāng)A=0,l二元信源時(shí)：F(0)=0,F(1)=p(0)計(jì)算信源序列S=(S1,S2,Sn)的累積

36、概率以二元無(wú)記憶信源為例：初始時(shí)：在0,1由F(1)劃分成二個(gè)子區(qū)間：0,1t0,F(1)F(1),1,F(1)=p(0)01子區(qū)間0,F(1)F(1),1的寬度為A(0)=p(0)A(1)=p(1)若輸入序列的第一個(gè)符號(hào)為s=“0”，即落入對(duì)應(yīng)的區(qū)間0,F(1)F(s=“0”)=F(0)=0當(dāng)輸入第二個(gè)符號(hào)為“1”,s=“01”對(duì)應(yīng)的區(qū)間在0,F(1)中進(jìn)行分割A(yù)(00)=A(0)p(0)=p(0)p(0)=p(00)A(01)=A(0)p(1)=p(0)p(1)=p(01)=A(0)-A(00)00”對(duì)應(yīng)的區(qū)間0,F(01);01”對(duì)應(yīng)的區(qū)間F(01),F(1)s=“01”的累積概率F(s

37、=“01”)=F(01)=p(0)p(0)當(dāng)輸入第三個(gè)符號(hào)為“1”，s1=“011”，所對(duì)應(yīng)的區(qū)間在F(01),F(1)中進(jìn)行分割對(duì)應(yīng)的區(qū)間F(s),F(s)+A(s)p(0)對(duì)應(yīng)的區(qū)間F(s)+A(s)p(0),F(1)A(010)=A(01)p(0)=A(s)p(0)A(011)=A(01)p(1)=A(s)p(1)=A(01)A(010)=A(s)A(s0)F(s1)=F(s)+A(s)p(0)F(s0)=F(s)現(xiàn)已輸入三個(gè)符號(hào)串，將這符號(hào)序列標(biāo)為s,接著輸入第四個(gè)符號(hào)為“0”或“1”?？捎?jì)算出s0=“0110”或s1=“0111”對(duì)應(yīng)的子區(qū)間及其累積概率。當(dāng)已知前面輸入符號(hào)序列為s，

38、若接著再輸入一個(gè)符號(hào)“0”累積概率區(qū)間寬度F(s0)=F(s)A(s0)=A(s)p(0)若接著輸入的一個(gè)符號(hào)是“1”，對(duì)序列s1的累積概率為F(s1)=F(s)+A(s)p(0)A(s1)=A(s)p(1)=A(s)A(s0)由前分析又知，符號(hào)序列對(duì)應(yīng)的區(qū)間寬度為A(0)=p(0)A(1)=1A(0)=p(1)A(00)=p(00)=A(0)p(0)=p(0)p(0)A(01)=A(0)A(00)=p(01)=A(0)p(1)=p(0)p(1)A(10)=p(10)=A(1)p(0)=p(1)p(0)A(11)=A(1)A(10)=p(11)=A(1)p(1)=p(1)p(1)A(010)=

39、A(01)p(0)=p(01)p(0)=p(010)A(011)=A(01)A(010)=A(01)p(1)=p(01)p(1)=p(011)III信源符號(hào)序列s所對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列s的概率p(s)二元信源符號(hào)序列的累積概率的遞推公式為F(sr)=F(s)+p(s)F(r)(r=0,1)其中sr表示已知前面信源符號(hào)序列為s接著再輸入符號(hào)為r。而F(r):F(0)=0,F(1)=p(0)同樣可得信源符號(hào)序列所對(duì)應(yīng)區(qū)間的寬度的遞推公式為A(sr)=p(sr)=p(s)p(r)(r=0,1)已輸入的二元符號(hào)序列為s=“011”，若接著輸入符號(hào)為1得序列的累積概率:F(s1)=F(0111)=

40、F(s=011)+p(011)p(0)=F(s=01)+p(01)p(0)+p(011)p(0)=F(s=0)+p(0)p(0)+p(01)p(0)+p(011)p(0)=0+p(00)+p(010)+p(0110)其對(duì)應(yīng)區(qū)間寬度A(s1)=A(s=011)p(1)=p(011)p(1)=p(0111)由于F(sr)=F(s)+p(s)F(r)A(sr)=p(sr)=p(s)p(r)是可遞推運(yùn)算，因此適合于實(shí)用。實(shí)際中，只需兩個(gè)存儲(chǔ)器，把p(s)和F(s)存下來(lái),然后根據(jù)輸入符號(hào)和上式，更新兩個(gè)存儲(chǔ)器中的數(shù)值。因?yàn)樵诰幋a過(guò)程中，每輸入一個(gè)符號(hào)要進(jìn)行乘法和加法運(yùn)算，所以稱此編碼方法為算術(shù)編碼。將

41、上式推廣到多元信源序列，得一般的遞推公式F(sak)=F(s)+p(s)F(ak)A(sak)=p(sak)=p(s)p(ak)通過(guò)關(guān)于信源符號(hào)序列的累積概率的計(jì)算，F(xiàn)(s)把區(qū)間0,1分割成許多小區(qū)間，不同的信源符號(hào)序列對(duì)應(yīng)于不同的區(qū)間為F(s),F(s)+p(s)。可取小區(qū)間內(nèi)的一點(diǎn)來(lái)代表這序列。代表大于等于的最小整數(shù)。1令Llogp(s)把累積概率F(s)寫成二進(jìn)制的小數(shù)，取小數(shù)點(diǎn)后L位，以后如果有尾數(shù)，就進(jìn)到第L位，這樣得到一個(gè)數(shù)C。例F(s)=0.，p(s)1/17，則L=5，得C=0.10111，s的碼字為10111這樣選取的數(shù)值C，一般根據(jù)二進(jìn)小數(shù)截去位數(shù)的影響，得丄CF(s)V

42、2L當(dāng)F(s)在L位以后沒(méi)有尾數(shù)時(shí)C=F(s)。而由Llogp(s)可知F(s)>2-L則信源符號(hào)序列s對(duì)應(yīng)區(qū)間的上界F(s)+p(s)>F(s)+2-L>C可見(jiàn)數(shù)值C在區(qū)間F(s),F(s)+p(s)內(nèi)。信源符號(hào)序列對(duì)應(yīng)的不同區(qū)間是不重疊的，所以編得的碼是即時(shí)碼。實(shí)用中，采用累積概率F(s)表示碼字C(s)，符號(hào)概率p(s)表示狀態(tài)區(qū)間A(s)，則有C(sp=C(s)+A(s)F(r)A(sJ)=A(s)p(r)因?yàn)樾旁捶?hào)序列因?yàn)樾旁捶?hào)序列s的碼長(zhǎng)滿足Llogp(s)，所以得若信源是無(wú)記憶的H(Sn)=nH(S)平均每個(gè)信源符號(hào)的碼長(zhǎng)例：設(shè)二元無(wú)記憶信源A=0,1，p(

43、0)=1/4，p(1)=3/4對(duì)二元序列s=做算術(shù)編碼解：根據(jù)上述的編碼規(guī)則，可得p(s=)=p2(0)p6(1)=(3/4)2(1/4)F(a3)=p(a1)+p(a2)F(s)=p(00000000)+p(00000001)+p(00000010)+p()=1p()p()p()p()=1p(111111)=1(3/4)6=0.1得C=0.1101010s的碼字為1101010編碼效率081192.7%L7/8這種按全序列進(jìn)行編碼，隨著信源序列n的增長(zhǎng)，效率還會(huì)增高。遞推編碼過(guò)程可列表如下：得s的碼字為1101010。此時(shí)s=對(duì)應(yīng)的區(qū)間為0.1,0.1?？梢?jiàn)C是區(qū)間內(nèi)一點(diǎn)。實(shí)際編碼是用硬件或

44、計(jì)算機(jī)軟件實(shí)現(xiàn)，所以采用速推公式來(lái)進(jìn)行編碼。只要存儲(chǔ)量允許，這種編碼，可以不論s有多長(zhǎng)，一直進(jìn)行計(jì)算下去，直至序列結(jié)束。2-2或1本例題中p(0)=2-2，又F(0)=0,F(1)=p(0)=2-2在遞推公式中每次需乘以乘以(I2-2)。在計(jì)算機(jī)中，乘以2-Q(Q為正整數(shù))，就可用右移Q位采取代；乘以2-Q就可用此數(shù)減去右移Q位數(shù)取代。這樣簡(jiǎn)捷快速。譯碼就是一系列比較過(guò)程。每一步比較CF(s)與p(s)p(0)若CF(s)vp(s)p(0)則譯輸出符號(hào)為“0”若CF(s)>p(s)p(0)則譯輸出符號(hào)為“1”s為前面已譯出的序列串p(s)是序列串s對(duì)應(yīng)的寬度F(s)是序列串s的累積概率，

45、即為s對(duì)應(yīng)區(qū)間的下界。p(s)p(0)是此區(qū)間內(nèi)下一個(gè)輸入為符號(hào)“0”所占的子區(qū)間寬度。由上面分析可知，算術(shù)編碼效率高，編譯碼速度也快。前面敘述了算術(shù)編碼的基本方法。在實(shí)用中還需考慮計(jì)算精度問(wèn)題、存儲(chǔ)量問(wèn)題、近似相2-Q中Q的選擇問(wèn)題等等。所以，算術(shù)編碼的編碼效率很高、當(dāng)信源符號(hào)序列很長(zhǎng)時(shí)。很大時(shí)，平均碼長(zhǎng)接近信源的一般情況下，F(xiàn)(ak)為實(shí)數(shù)，若用二進(jìn)制數(shù)精確表示，則有可能需要無(wú)窮多位，但作為碼字只需有足夠的位數(shù)，使其能與ak一一對(duì)應(yīng)就夠了，所以只需用L位來(lái)表示F(ak)，即取例：設(shè)離散無(wú)記憶信源字母表為a1,a2,a3,a4，p(a1)=0.25p(a2)=0.5，p(a3)=0.125，

46、p(a4)=0.125。求：字母ak的累積概率F(ak)及F(ak)的二進(jìn)制表示和相應(yīng)的碼字。如表所示:akp(ak)F(ak)F(ak)二進(jìn)制表示L碼字al0.2500a20.500.250.01a30.1250.750.11a40.1250.8750.111在上面兩個(gè)例子中，算術(shù)編碼的效果并不很好，這是因?yàn)閮H用算術(shù)編碼方法對(duì)婚字母進(jìn)行編碼、若對(duì)源字母序列進(jìn)行編碼，則算術(shù)編碼有獨(dú)特的優(yōu)點(diǎn)它和以隨若序列長(zhǎng)度N的增加而自然地改進(jìn)壓縮效果。第五章信源編碼(第十二講)(2課時(shí))主要內(nèi)容：(1)常用信源編碼方法簡(jiǎn)介(預(yù)測(cè)編碼)(2)常用信源編碼方法簡(jiǎn)介(變換編碼)。重點(diǎn)：常用信源編碼方法簡(jiǎn)介(預(yù)測(cè)編碼

47、)。難點(diǎn)：常用信源編碼方法簡(jiǎn)介(預(yù)測(cè)編碼)。特別提示：運(yùn)用說(shuō)明：本堂課推導(dǎo)內(nèi)容較多，枯燥平淡，不易激發(fā)學(xué)生興趣，要注意多討論用途。另外，注意，解題方法。多加一些內(nèi)容豐富知識(shí)和理解。作業(yè)：靈活運(yùn)用。課外仍以學(xué)生復(fù)習(xí)。§限失真信源編碼常用信源編碼方法四、預(yù)測(cè)編碼預(yù)測(cè)編碼的基本原理對(duì)于有記憶信源，信源輸出的各個(gè)分量之間是有統(tǒng)計(jì)關(guān)聯(lián)的，這種統(tǒng)計(jì)關(guān)聯(lián)性可以加以充分利用。預(yù)測(cè)編碼：在這種編碼方法中，編碼器和譯碼器都存貯有過(guò)去的信號(hào)值，并以此來(lái)預(yù)測(cè)或估計(jì)未來(lái)的信號(hào)值。在編碼器發(fā)出的不是信源信號(hào)本身，而是信源信號(hào)與預(yù)測(cè)值之差；在譯碼端，譯碼器將接收到的這一差值與譯碼器的預(yù)測(cè)值相加，從而恢復(fù)信號(hào)。設(shè)信

48、源第i瞬間的輸出為ui，根據(jù)信源ui的前K個(gè)樣值，給出的預(yù)測(cè)值為其中f為預(yù)測(cè)函數(shù)，它可以是線性也可以是非線性函數(shù)，線性預(yù)測(cè)函數(shù)實(shí)現(xiàn)比較簡(jiǎn)單，比如圖5-4-2所示，這時(shí)預(yù)測(cè)值為：貝怫i個(gè)樣值的預(yù)測(cè)誤差值為根據(jù)信源編碼定理，若直接對(duì)信源輸出進(jìn)行編碼，則其平均碼長(zhǎng)Ku應(yīng)趨于信源熵:若對(duì)預(yù)測(cè)變換后的誤差值e進(jìn)行編碼，其平均碼長(zhǎng)Ke應(yīng)趨于誤差信號(hào)熵：顯然，從信息論觀點(diǎn)，預(yù)測(cè)編碼能壓縮信源數(shù)碼率的必要條件為：這里Ku表示預(yù)測(cè)前的信源編碼平均碼長(zhǎng)，Ke表示預(yù)測(cè)后誤差信號(hào)編碼的碼長(zhǎng)。由于信息熵是概率分布的泛函數(shù)，故概率分布越均勻，熵越大；概率分布越不均勻，比如越集中，熵就越小，即H(E)H(U)，信源通過(guò)預(yù)測(cè)

49、以后數(shù)據(jù)壓縮(或連續(xù)時(shí)的頻帶壓縮)倍數(shù)就越大。實(shí)現(xiàn)預(yù)測(cè)編碼要進(jìn)一步考慮3個(gè)方面的問(wèn)題：預(yù)測(cè)誤差準(zhǔn)則的選?。侯A(yù)測(cè)函數(shù)的選?。侯A(yù)測(cè)器輸入數(shù)據(jù)的選取。預(yù)測(cè)誤差準(zhǔn)則：預(yù)測(cè)誤差所依據(jù)的標(biāo)準(zhǔn)如何選取預(yù)測(cè)值U?，以使預(yù)測(cè)誤差ei滿足某種意義上的最佳是預(yù)測(cè)編碼設(shè)計(jì)中的核心問(wèn)題。按照不同的最佳準(zhǔn)則，可得到比較重要的3種最佳預(yù)測(cè)器：最小均方誤差預(yù)測(cè)器：最佳準(zhǔn)則：使預(yù)測(cè)誤差的均方值達(dá)到最小最小平均絕對(duì)誤差預(yù)測(cè)器最佳準(zhǔn)則：使預(yù)測(cè)器的絕對(duì)誤差的均值達(dá)到最小最大零誤差概率預(yù)測(cè)器預(yù)測(cè)編碼的基本原理最佳準(zhǔn)則：預(yù)測(cè)值具有零誤差的概率或概率密度為最大DPCM信源的話音信號(hào)為u(t)，其iTs時(shí)刻的抽樣值為u(iTs),簡(jiǎn)寫為ui

50、。DPCM基本思想：將“話音信號(hào)樣值同預(yù)測(cè)樣值的差”作量化、編碼。K和aj是預(yù)測(cè)器的參數(shù)，為常數(shù)。該式表示？是先前K個(gè)樣值的加權(quán)和，aj稱為預(yù)測(cè)器系數(shù)。u:Ui的預(yù)測(cè)值。發(fā)端的預(yù)測(cè)器和相加器用來(lái)獲得當(dāng)前的預(yù)測(cè)值u?i預(yù)測(cè)器的輸出樣值U?與其輸入樣值i的關(guān)系滿足下式：圖中編碼器的“預(yù)測(cè)器和相加器”組成結(jié)構(gòu)同解碼器的“預(yù)測(cè)器和相加器”的組成結(jié)構(gòu)完全一樣：顯然，信道信息傳輸無(wú)誤碼時(shí)，兩個(gè)相加器輸入端的信號(hào)完全一樣：Xi=yi。此時(shí)圖中解碼器的輸出信號(hào)i與編碼器信號(hào)i是相同的：DPCM系統(tǒng)的量化誤差應(yīng)該定義為輸入信號(hào)樣值ui與解碼器輸出信號(hào)樣值i之差。DPCM系統(tǒng)信噪比Gp:預(yù)測(cè)增益SNRq:量化器所

51、產(chǎn)生的信噪比五、變換編碼眾所周知，信源序列往往具有很強(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ù)還是積分,都屬于一類正交變換，是從時(shí)域展開(kāi)成頻域的變換。同理,對(duì)離散的數(shù)據(jù)序列信號(hào)也可引入同樣的離散傅氏變換。而且，還可以進(jìn)一步將其推廣為廣義的頻域變換。在這一節(jié)中，首先從解除相關(guān)性的需求入手，尋求最佳的域變換。上一節(jié)討論的在空間和時(shí)間域

52、上壓縮信源數(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)性明顯下降，并且能量常常集中于低頻或低序系數(shù)區(qū)域中，這樣就容易實(shí)現(xiàn)碼率的壓縮，而且還

53、大大降低了實(shí)現(xiàn)的難度。變換編碼的基本原理設(shè)信源輸出為一個(gè)一維消息U=(u1,u2,，un),經(jīng)變換后輸出為X=(x1,x2,，xn),故有：X=PU由正交性ATA=A一1A=I，則有：U=1X=PTX式中：P實(shí)正交變換矩陣；PT矩陣P的轉(zhuǎn)置矩陣；P一1矩陣P的逆矩陣；I單位矩陣。如果經(jīng)正交變換后，只傳送M(M<n)個(gè)樣值，而將余下的n-M個(gè)較小的樣值丟棄。這時(shí)接收端恢復(fù)的信號(hào)為式中：如何選擇正交矩陣P，使M值較小，且使被丟棄的n-M個(gè)取值足夠地小，以至于既能得到最大的信源壓縮率，同時(shí)又使丟棄掉n-M個(gè)取值以后，所產(chǎn)生的誤差不超過(guò)允許的失真范圍是我們關(guān)心的問(wèn)題。因此，正交變換的主要問(wèn)題可歸

54、結(jié)為在一定的誤差準(zhǔn)則下，尋找最佳或準(zhǔn)最佳的正交變換，以達(dá)到最大限度地消除原消息源之間的相關(guān)性。正交變換為什么能解除相關(guān)性呢？下面討論這個(gè)問(wèn)題。由矩陣代數(shù)理論可知：對(duì)于任意兩個(gè)隨機(jī)變量x,y間的相關(guān)性可以用x,y的協(xié)方差(相關(guān)距)表示。一個(gè)信源U的各分量間的相關(guān)性可以用信源各分量間協(xié)方差矩陣U表示，其定義為式中：u信源輸出U的協(xié)方差矩陣；E:數(shù)學(xué)期望；0ijUi、Uj協(xié)方差。可以證明U的協(xié)方差矩陣U是一個(gè)實(shí)對(duì)稱矩陣，它能反映矢量U各分量間的相關(guān)性。若各分量之間互不相關(guān)，則協(xié)方差矩陣U只在主對(duì)角線上有非零元素。主對(duì)角線上的非零元素代表各分量間的方差，即自相關(guān)性；非對(duì)角線上的元素表示各分量之間的協(xié)方

55、差，即互相關(guān)性。由矩陣代數(shù)可知，對(duì)于一個(gè)實(shí)對(duì)稱矩陣A(A=AT的矩陣)，必存在一個(gè)正交矩陣P,使得：式中：入1,入2,，入n實(shí)對(duì)稱矩陣A的n個(gè)特征根?？梢?jiàn)正交變換能解除相關(guān)性。信源U經(jīng)正交變換后的輸出X協(xié)方差矩陣可定義為X=E:(X-E:X:)(X-E:X)T:=E:(PU-E:PU:)(PU-E:PU:)T=PE:(U-E:U:)(U-E:U:)丁PT=PuPT式中：X信源U正交變換后的信號(hào)X的協(xié)方差矩陣；X信源U經(jīng)正交變換后的矢量；P正交變換矩陣；PT正交變換矩陣P的轉(zhuǎn)置矩陣。為了達(dá)到信源壓縮的目的，希望通過(guò)矩陣P的正交變換后，X只保留主對(duì)角線上的部分自相關(guān)值，即希望其值隨i與j值的增大而迅速減小，從而只需取M(M<n)個(gè)數(shù)值