信息論及編碼第5章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、而赫夫曼編碼是先給每一符號一片樹葉，逐步合并成節(jié)點直到樹根。哈夫曼編碼的步驟如下：將信源消息符號按其出現(xiàn)的概率大小依次排列P（U1）P（U2）P（Un）取兩個概率最小的字母分別配以0和1兩碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的字母重新排隊。對重排后的兩個概率最小符號重復步驟的過程。不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字。例：給定離散信源如下：平均碼長：7Kp（uJKii10.220.1920.1830.1730.1530.1040.014編碼效率2.72哈夫曼編碼方法得到的碼并非是唯一

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

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

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

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

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

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

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

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

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

28、poPi-“0”L(0)1L(0)1Pi游程序列的平均游程長度同理，“1”游程長度的熵和平均游程長度：變換后的游程序列是獨立序列游程變換后符號熵沒有變。因為游程變換是一一對應的可逆變換。所以變換后熵值不變。由于游程變換有較好的去相關效果，因而對游程序列進行哈夫曼編碼，可獲得較高的編碼效率。假設“0”游程長度的哈夫曼編碼效率為n0,“1”游程長度的哈夫曼編碼效率為n1,由編碼效率的定義得二兀序列的編碼效率假設n0>n1，則有n0>n>n1當“0”游程和“1”游程的編碼效率都很高時，采用游程編碼的效率也很高，至少不會低于較小的那個效率。要想編碼效率n盡可能高，應使上式的分母盡可能

29、小，這就要求盡可能提高熵值較大的游程的編碼效率，因為它在往分母中占的比重較大。理論上來說游程長度可從1到無窮。要建立游程長度和碼字之間的一一對應的碼表是困難的。一般情況下，游程越長，出現(xiàn)的概率就越?。划斢纬涕L度趨向于無窮時，出現(xiàn)的概率也趨向于0。按哈夫曼碼的編碼規(guī)則，概率越小碼字越長，但小概率的碼字對平均碼長影響較小，在實際應用時常對長碼采用截斷處理的方法取一個適當?shù)膎值，游程長度為1,2,2n-1,2n，所有大于2n者都按2n來處理。然后按照哈夫曼碼的編碼規(guī)則，將上列2n種概率從大到小排隊，構成碼樹并得到相應的碼字。二、矢量量化編碼要想得到性能好的編碼，僅采用標量量化是不可能的。在最佳編碼中

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

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

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

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

34、,1分成兩個與概率比例相應的區(qū)間,其發(fā)生概率為p(a”=0.6,p(a2)=0.4。將0,1分成兩個與概率比例相應的區(qū)間,0,0.60.6,S1=a1時，數(shù)p的值處在0,0.6,S1=a2時，0.6,I。0,1t0,0.60.6,l0,0.360.36,0.60.6,0.840.84,1S1=a1S1=a2根據(jù)信源輸出的第二個字母S2的取值情況，可以更精確地確定出數(shù)p所在的區(qū)間位置。在信源輸出第n1個符號后，若p所在的位置為I當信源輸出的第一個符號根據(jù)信源字母S1的情況，把p所在的段再次按概率比例分成An-1,Bn-1則當信源輸出的第n個符號為：sn=ai時，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ū)間的長度。隨著序列的長度不斷增加,P所在區(qū)間的長度就越短，也就可以更加精確地確定P的位置。當信源字母序列長度趨于無限時，p所在區(qū)間成為一點。2、累積概率設信源字母表為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)當A=0,l二元信源時：F(0)=0,F(1)=p(0)計算信源序列S=(S1,S2,Sn)的累積

36、概率以二元無記憶信源為例：初始時：在0,1由F(1)劃分成二個子區(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)若輸入序列的第一個符號為s=“0”，即落入對應的區(qū)間0,F(1)F(s=“0”)=F(0)=0當輸入第二個符號為“1”,s=“01”對應的區(qū)間在0,F(1)中進行分割A(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”對應的區(qū)間0,F(01);01”對應的區(qū)間F(01),F(1)s=“01”的累積概率F(s

37、=“01”)=F(01)=p(0)p(0)當輸入第三個符號為“1”，s1=“011”，所對應的區(qū)間在F(01),F(1)中進行分割對應的區(qū)間F(s),F(s)+A(s)p(0)對應的區(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)已輸入三個符號串，將這符號序列標為s,接著輸入第四個符號為“0”或“1”?？捎嬎愠鰏0=“0110”或s1=“0111”對應的子區(qū)間及其累積概率。當已知前面輸入符號序列為s，

38、若接著再輸入一個符號“0”累積概率區(qū)間寬度F(s0)=F(s)A(s0)=A(s)p(0)若接著輸入的一個符號是“1”，對序列s1的累積概率為F(s1)=F(s)+A(s)p(0)A(s1)=A(s)p(1)=A(s)A(s0)由前分析又知，符號序列對應的區(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信源符號序列s所對應區(qū)間的寬度等于符號序列s的概率p(s)二元信源符號序列的累積概率的遞推公式為F(sr)=F(s)+p(s)F(r)(r=0,1)其中sr表示已知前面信源符號序列為s接著再輸入符號為r。而F(r):F(0)=0,F(1)=p(0)同樣可得信源符號序列所對應區(qū)間的寬度的遞推公式為A(sr)=p(sr)=p(s)p(r)(r=0,1)已輸入的二元符號序列為s=“011”，若接著輸入符號為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)其對應區(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)是可遞推運算，因此適合于實用。實際中，只需兩個存儲器，把p(s)和F(s)存下來,然后根據(jù)輸入符號和上式，更新兩個存儲器中的數(shù)值。因為在編碼過程中，每輸入一個符號要進行乘法和加法運算，所以稱此編碼方法為算術編碼。將

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

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

43、0)=1/4，p(1)=3/4對二元序列s=做算術編碼解：根據(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這種按全序列進行編碼，隨著信源序列n的增長，效率還會增高。遞推編碼過程可列表如下：得s的碼字為1101010。此時s=對應的區(qū)間為0.1,0.1?？梢奀是區(qū)間內(nèi)一點。實際編碼是用硬件或

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

45、即為s對應區(qū)間的下界。p(s)p(0)是此區(qū)間內(nèi)下一個輸入為符號“0”所占的子區(qū)間寬度。由上面分析可知，算術編碼效率高，編譯碼速度也快。前面敘述了算術編碼的基本方法。在實用中還需考慮計算精度問題、存儲量問題、近似相2-Q中Q的選擇問題等等。所以，算術編碼的編碼效率很高、當信源符號序列很長時。很大時，平均碼長接近信源的一般情況下，F(xiàn)(ak)為實數(shù)，若用二進制數(shù)精確表示，則有可能需要無窮多位，但作為碼字只需有足夠的位數(shù)，使其能與ak一一對應就夠了，所以只需用L位來表示F(ak)，即取例：設離散無記憶信源字母表為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)的二進制表示和相應的碼字。如表所示:akp(ak)F(ak)F(ak)二進制表示L碼字al0.2500a20.500.250.01a30.1250.750.11a40.1250.8750.111在上面兩個例子中，算術編碼的效果并不很好，這是因為僅用算術編碼方法對婚字母進行編碼、若對源字母序列進行編碼，則算術編碼有獨特的優(yōu)點它和以隨若序列長度N的增加而自然地改進壓縮效果。第五章信源編碼(第十二講)(2課時)主要內(nèi)容：(1)常用信源編碼方法簡介(預測編碼)(2)常用信源編碼方法簡介(變換編碼)。重點：常用信源編碼方法簡介(預測編碼

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

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

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

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

51、產(chǎn)生的信噪比五、變換編碼眾所周知，信源序列往往具有很強的相關性，要提高信源的效率首先要解除信源的相關性。解除相關性可以在時域上進行（這就是上節(jié)中介紹的預測編碼），也可以在頻域，甚至在廣義頻域內(nèi)進行，這就是要在本節(jié)中介紹的變換編碼。在信號分析中，對連續(xù)的模擬信號，如果它是周期性的,則可采用傅氏級數(shù)展開，若是非周期性的,則可采用傅氏積分（變換）來表示，但無論是級數(shù)還是積分,都屬于一類正交變換，是從時域展開成頻域的變換。同理,對離散的數(shù)據(jù)序列信號也可引入同樣的離散傅氏變換。而且，還可以進一步將其推廣為廣義的頻域變換。在這一節(jié)中，首先從解除相關性的需求入手，尋求最佳的域變換。上一節(jié)討論的在空間和時間域

52、上壓縮信源數(shù)據(jù)冗余量的預測編碼的最大特點是直觀、簡潔、易于實現(xiàn)，特別是容易設計出具有實時性的硬件結構。但是預測編碼的不足在于壓縮能力有限。具有更高壓縮能力的方法和目前最為成熟的方法是變換編碼，特別是正交變換編碼方法和目前尚處于研究階段的小波變換編碼，這兩種方法都具有很強的數(shù)據(jù)壓縮能力。變換編碼的基本原理就是將原來在空間域上描述的信號，通過一種數(shù)學變換（例如，傅里葉變換、正交變換等）變換到變換域（如頻率域、正交矢量空間）中進行描述。簡單地講，即把信號由空間域變換到變換域中，用變換系數(shù)來描述。這些變換系數(shù)之間的相關性明顯下降，并且能量常常集中于低頻或低序系數(shù)區(qū)域中，這樣就容易實現(xiàn)碼率的壓縮，而且還

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

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

55、差，即互相關性。由矩陣代數(shù)可知，對于一個實對稱矩陣A(A=AT的矩陣)，必存在一個正交矩陣P,使得：式中：入1,入2,，入n實對稱矩陣A的n個特征根?？梢娬蛔儞Q能解除相關性。信源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正交變換后的信號X的協(xié)方差矩陣；X信源U經(jīng)正交變換后的矢量；P正交變換矩陣；PT正交變換矩陣P的轉置矩陣。為了達到信源壓縮的目的，希望通過矩陣P的正交變換后，X只保留主對角線上的部分自相關值，即希望其值隨i與j值的增大而迅速減小，從而只需取M(M<n)個數(shù)值