第五章 信源編碼-信息論與編碼

第五章信源編碼*2信息通過信道傳輸?shù)叫潘薜倪^程即為通信。要做到既不失真又快速地通信，需要解決兩個問題：在不失真或允許一定失真條件下，如何提高信息傳輸速度----這是本章要討論的信源編碼問題.在信道受到干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大----這是下章要討論的信道編碼問題.*3一般來說，抗干擾能力與信息傳輸率二者相互矛盾。然而編碼定理已從理論上證明，至少存在某種最佳的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。信源雖然多種多樣，但無論是哪種類型的信源，信源符號之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率。*4信源編碼的基本途徑有兩個:一是編碼后使序列中的各個符號之間盡可能地互相獨立，即解除相關(guān)性----方法包括預(yù)測編碼和變換編碼.二是使編碼后各個符號出現(xiàn)的概率盡可能相等，即均勻化分布----方法主要是統(tǒng)計編碼.*5信源編碼常分為無失真信源編碼和限失真信源編碼，前者主要用于文字、數(shù)據(jù)信源的壓縮，后者主要用于圖像、語音信源的壓縮。本章主要介紹信源編碼的基本思路與主要方法，以無失真、統(tǒng)計編碼為主，期望通過本章學(xué)習(xí)能建立起信源壓縮編碼的基本概念。*65.1編碼器及相關(guān)概念為了分析方便和突出問題的重點，當(dāng)研究信源編碼時，我們把信道編碼和譯碼看成是信道的一部分，從而突出信源編碼。同樣，在研究信道編碼時，可以將信源編碼和譯碼看成是信源和信宿的一部分，從而突出信道編碼。*75.1.1碼的分類一.編碼器模型

由于信源編碼可以不考慮抗干擾問題，所以它的數(shù)學(xué)模型比較簡單。下圖為一個編碼器模型:*8輸入是信源符號集:

x為編碼器所用的編碼符號集，包含r個元素{}，稱為碼符號(碼元).由碼符號組成的輸出序列稱為碼字.

其長度稱為碼字長度或碼長，全體碼字的集合C稱為碼或碼書.編碼器將信源符號集中的信源符號（或長為N的信源符號序列）變成由碼符號組成的長為的與信源符號一一對應(yīng)的輸出序列。即:*9二.碼的分類:

對于編碼器而言，根據(jù)碼符號集合X中碼元的個數(shù)不同以及碼字長度是否一致，有以下一些常用的編碼形式：

*10(1)二元碼和r元碼

若碼符號集，編碼所得碼字為一些適合在二元信道中傳輸?shù)亩蛄校瑒t稱二元碼。二元碼是數(shù)字通信與計算機系統(tǒng)中最常用的一種碼。若碼符號集共有r個元素，則所得之碼稱為r

元碼.(2)等長碼

若一組碼中所有碼字的長度都相同----（即），則稱為等長碼.*11(3)

變長碼若一組碼中碼字的碼長各不相同（即碼字長度不等），則稱為變長碼.

如表中“編碼1”為等長碼，“編碼2”為變長碼。信源符號si符號出現(xiàn)概率p(si)編碼1編碼2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)11101*12(4)分組碼若每個信源符號按照固定的碼表映射成一個碼字，則稱為分組碼。否則就是非分組碼.

如果采用分組編碼方法，需要分組碼具有某些屬性，以保證在接收端能夠迅速而準(zhǔn)確地將接收到的碼譯成與信源符號對應(yīng)的消息。下面討論分組碼的一些直觀屬性。*131）非奇異碼和奇異碼若一組碼中所有碼字都不相同(即所有信源符號映射到不同的碼符號序列)，則稱為非奇異碼。反之，則為奇異碼。*14概率信源符號

編碼1編碼2編碼3編碼4編碼51/20000011/4010110011/8101001100011/81110111110001*152）同價碼若碼符號集X：{}中每個碼符號所占的傳輸時間都相同，則所得的碼為同價碼。我們一般討論同價碼，對同價碼來說等長碼中每個碼字的傳輸時間相同，而變長碼中每個碼字的傳輸時間就不一定相同。*163）碼的N次擴展碼假定某一碼，它把信源中的符號一一變換成碼C中的碼字，則碼C的N次擴展碼是所有N個碼字組成的碼字序列的集合。*17例如：若碼滿足：則碼C的N次擴展碼集合,其中：即碼C的N次擴展碼中，每個碼字與信源的N次擴展信源中的每個信源符號是一一對應(yīng)的：*184）惟一可譯碼若任意一串有限長的碼符號序列只能被惟一地譯成所對應(yīng)的信源符號序列，則此碼稱為惟一可譯碼（或稱單義可譯碼）。否則就稱為非惟一可譯碼或非單義可譯碼。若要使某一碼為惟一可譯碼，則對于任意給定的有限長的碼符號序列，只能被惟一地分割成一個個的碼字。*19例如：對于二元碼，當(dāng)任意給定一串碼字序列，例如“10001101”，只可唯一地劃分為1,00,01,1,01，因此是惟一可譯碼；而對另一個二元碼，當(dāng)碼字序列為“01001”時，可劃分為0,10,01或01,0,01，所以是非惟一可譯的。*20對惟一可譯碼又分為即時碼和非即時碼：如果在接收端收到一個完整的碼字后，就能立即進(jìn)行譯碼，這樣的碼叫做即時碼；而在接收端收到一個完整的碼字后，還需等下一個碼字接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。即時碼又稱為非延長碼，對即時碼而言，在碼本中任意一個碼字都不是其它碼字的前綴部分。對非即時碼來說，有的碼是惟一可譯的，有的碼是非惟一可譯的，主要取決于碼的總體結(jié)構(gòu)。*21綜上所述，可將碼作所示的分類：*225.1.2碼樹對于給定碼字的全體集合，可以用碼樹來描述。對于r進(jìn)制的碼樹，如下頁圖所示，其中圖(a)為二元碼樹，圖(b)為三元碼樹。在碼樹中點是樹根，從樹根伸出個樹枝，構(gòu)成元碼樹。樹枝的盡頭是節(jié)點，一般中間節(jié)點會伸出樹枝，不伸出樹枝的節(jié)點為終端節(jié)點，編碼時應(yīng)盡量在終端節(jié)點安排碼字。*23*24碼樹中自樹根經(jīng)過一個分枝到達(dá)一階節(jié)點，一階節(jié)點最多為r個，二階節(jié)點的可能個數(shù)為r2個，n階節(jié)點最多有rn個，若將從每個節(jié)點發(fā)出的個分枝分別標(biāo)以0，1，…，r-1，則每個n階節(jié)點需要用n個r元數(shù)字表示。如果指定某個n階節(jié)點為終端節(jié)點，用于表示一個信源符號，則該節(jié)點就不再延伸，相應(yīng)的碼字即為從樹根到此端點的分枝標(biāo)號序列，該序列長度為n，用這種方法構(gòu)造的碼滿足即時碼的條件，因為從樹根到每一個終端節(jié)點所走的路徑均不相同，所以一定滿足對即時碼前綴的限制。如果有個q信源符號，那么在碼樹上就要選擇q個終端節(jié)點，用相應(yīng)r的元基本符號表示這些碼字。*25若樹碼的各個分支都延伸到最后一級端點，此時將共有個碼字，這樣的碼樹稱為整樹，如圖(a)所示。否則就稱為非整樹，如圖(b)所示，這時的碼字就不是等長碼了。因此，碼樹與碼之間具有如下一一對應(yīng)的關(guān)系：樹根碼字起點；樹枝數(shù)碼的進(jìn)制數(shù)；節(jié)點碼字或碼字的一部分；終端節(jié)點碼字；階數(shù)碼長；非整樹變長碼；整樹等長碼。定長編碼定理：1*26消息序列碼序列定長變長定理說明*27信息率：編碼效率：m-碼序列中每個符號的可能取值，單個符號的信息量為K-定長編碼的長度，總信息量L-信源符號的長度，平均每個符號的信息量為定理說明信息率略大于信源熵，可做到無失真譯碼*28結(jié)論：定長編碼簡單，但要達(dá)到一定的差錯率不易實現(xiàn)，且編碼效率低。*29*305.2變長編碼變長碼往往在碼長的平均值不很大時，就可編出效率很高而且無失真的碼，其平均碼長受香農(nóng)第一定理所限定，即：若對信源離散無記憶信源S的N次擴展信源進(jìn)行編碼，則總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使信源S中每個信源符號所需的平均碼長滿足：

對離散無記憶信源，消息長度為L，符號熵為H(X),對信源進(jìn)行m元變長編碼，一定存在無失真的信源編碼方法滿足：其碼字平均長度K滿足：其碼字平均信息率R變長編碼定理：2*31如何分離碼字？？變長編碼出現(xiàn)的問題P66例2.4.1只要4個符號一起編碼即可滿足要求，所以為了提高編碼效率，采樣變長編碼。要求：碼是唯一可譯*32*33且當(dāng)時有：其中，為N次擴展信源的平均碼長，

為信源符號擴展序列的碼長.

為對擴展信源進(jìn)行編碼后，每個信源符號編碼所需的等效的平均碼長。

*34要做到無失真的信源編碼，平均每個信源符號所需最少的r元碼元數(shù)為信源的熵。即它是無失真信源壓縮的極限值。若編碼的平均碼長小于信源的熵值，則惟一可譯碼不存在，在譯碼或反變換時必然要帶來失真或差錯。通過對擴展信源進(jìn)行變長編碼，當(dāng)N時，平均碼長*35無失真信源編碼的實質(zhì)：對離散信源進(jìn)行適當(dāng)?shù)淖儞Q，使變換后形成的新的碼符號信源(即信道的輸入信源)盡可能為等概率分布，以使新信源的每個碼符號平均所含的信息量達(dá)到最大，使信道的信息傳輸率達(dá)到信道容量，實現(xiàn)信源與信道理想的統(tǒng)計匹配。這實際上就是香農(nóng)第一定理的物理意義。*36為了衡量各種編碼是否達(dá)到極限情況，定義變長碼的編碼效率為：常通過編碼效率來衡量各種編碼的優(yōu)劣.為了衡量各種編碼與最佳碼的差距，定義碼的剩余度為：信息傳輸率定義為：注意:雖然與在數(shù)值上相同，但它們的單位不同，編碼效率沒有單位，而信息傳輸率的單位是比特/碼符號。*37在二元無噪無損信道中在二元信道中，若編碼效率=1，R=1比特／碼符號，則達(dá)到信道的信道容量，此時編碼效率最高，碼的剩余度為零。前面已經(jīng)說明，對于某一個信源和某一符號集來說，凡是滿足克拉夫特不等式的惟一可譯碼可以有多種，在這些惟一可譯碼中，如果有一種（或幾種）碼，其平均編碼長度小于所有其他惟一可譯碼的平均編碼長度，則該碼稱為最佳碼（或緊致碼）。*38為了使得平均編碼長度為最小，必須將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字。能獲得最佳碼（或次最佳碼）的編碼方法有很多，本節(jié)重點介紹：香農(nóng)(shannon)編碼、費諾(Fano)編碼、霍夫曼(Huffman)編碼。*395.2.1香農(nóng)碼香農(nóng)第一定理指出，可選擇每個碼字的長度滿足關(guān)系式：或：

x

表示不小于x的整數(shù)。按不等式選擇的碼長所構(gòu)成的碼稱香農(nóng)碼。香農(nóng)碼滿足克拉夫特不等式，所以一定存在對應(yīng)碼字的長度的惟一可譯碼。*40一般情況下，按照香農(nóng)編碼方法編出來的碼，其平均碼長不是最短的，也即不是緊致碼(最佳碼)。只有當(dāng)信源符號的概率分布使不等式左邊的等號成立時，編碼效率才達(dá)到最高。*41香農(nóng)碼的編碼步驟如下：

1）將個信源符號按概率遞減的方式進(jìn)行排列：

2）按香農(nóng)不等式計算出每個信源符號的碼長；

3）為了編成惟一可譯碼，計算第i個信源符號的累加概率

4）將累加概率用二進(jìn)制數(shù)表示。

5）取對應(yīng)二進(jìn)制數(shù)的小數(shù)點后位構(gòu)成該信源符號的二進(jìn)制碼字。*42例:設(shè)信源共有七個信源符號，其概率分布如表所示，試對該信源進(jìn)行香農(nóng)編碼。解:碼的性能分析：通過計算可得此信源的熵:

(比特／符號)

而碼的平均長度:

(二元碼符號／符號)

編碼效率：*43概率累加概率碼長信源符號對應(yīng)的二進(jìn)制數(shù)碼字0.2000.0002.3430000.190.20.0011…2.4130010.180.390.0110…2.4830110.170.570.1001…2.5631000.150.740.1011…2.7431010.100.890.1110…3.34411100.010.990.1111110…6.6671111110*445.2.2費諾碼費諾編碼屬于概率匹配編碼，但它一般也不是最佳的編碼方法，只有當(dāng)信源的概率分布呈現(xiàn)分布形式的條件下，才能達(dá)到最佳碼的性能。*45

費諾碼的編碼步驟如下：

1）信源符號以概率遞減的次序排列起來；

2）將排列好的信源符號按概率值劃分成兩大組，使每組的概率之和接近于相等，并對每組各賦予一個二元碼符號“0”和“1”；

3）將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之和接近于相等，再分別賦予一個二元碼符號；

4）依次下去，直至每個小組只剩一個信源符號為止；

5）信源符號所對應(yīng)的碼字即為費諾碼。*46例:將下列消息按二元費諾碼方法進(jìn)行編碼。解:碼的性能分析：此信源的熵(比特／符號)，而碼的平均長度

(二元碼符號／符號)

顯然，該碼是緊致碼，編碼效率：該碼之所以能達(dá)到最佳，是因為信源符號的概率分布正好滿足式，否則，在一般情況下是無法達(dá)到編碼效率等于“1”的。

*47*48費諾碼具有如下的性質(zhì)：①費諾碼的編碼方法實際上是一種構(gòu)造碼樹的方法，所以費諾碼是即時碼。②費諾碼考慮了信源的統(tǒng)計特性，使概率大的信源符號能對應(yīng)碼長較短的碼字，從而有效地提高了編碼效率。③費諾碼不一定是最佳碼。因為費諾碼編碼方法不一定能使短碼得到充分利用:當(dāng)信源符號較多時，若有一些符號概率分布很接近時，分兩大組的組合方法就會很多?？赡苣撤N分大組的結(jié)果，會使后面小組的“概率和”相差較遠(yuǎn)，從而使平均碼長增加。r元費諾碼前面討論的費諾碼是二元費諾碼，對r元費諾碼，與二元費諾碼編碼方法相同，只是每次分組時應(yīng)將符號分成概率分布接近的r個組。*495.2.3霍夫曼碼1952年，霍夫曼（Huffman）提出了一種構(gòu)造最佳碼的方法，這是一種最佳的逐個符號的編碼方法，一般就稱作霍夫曼碼。設(shè)信源，其對應(yīng)的概率分布為，則對二元霍夫曼碼而言，其編碼步驟如下：*501）將q個信源符號按概率遞減的方式排列起來；2）用“0”、“1”碼符號分別表示概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個新的符號，從而得到只包含q-1個符號的新信源，稱之為S信源的S1縮減信源；3）將縮減信源中的符號仍按概率大小以遞減次序排列，再將其最后兩個概率最小的符號合并成一個符號，并分別用“0”、“1”碼符號表示，這樣又形成了由q-2個符號構(gòu)成的縮減信源S2；4）依次繼續(xù)下去，直到縮減信源只剩下兩個符號為止，將這最后兩個符號分別用“0”、“1”碼符號表示；5）從最后一級縮減信源開始，向前返回，沿信源縮減方向的反方向取出所編的碼元，得出各信源符號所對應(yīng)的碼符號序列，即為對應(yīng)信源符號的碼字。*51例:對離散無記憶信源

進(jìn)行霍夫曼編碼。解:編碼過程如表所示：

1)將信源符號按概率大小由大至小排序。

2)從概率最小的兩個信源符號和開始編碼，并按一定的規(guī)則賦予碼符號，如下面的信源符號（小概率）為“1”，上面的信源符號（大概率）為“0”。若兩支路概率相等，仍為下面的信源符號為“1”上面的信源符號為“0”。

3)將已編碼兩個信源符號概率合并，重新排隊，編碼。

4)重復(fù)步驟3）直至合并概率等于“1.0”為止。

5)從概率等于“1.0”端沿合并路線逆行至對應(yīng)消息編碼.*52*53碼的性能分析：信源的熵為：(比特／符號)

從，可得平均碼長為：編碼效率為：*54按霍夫曼碼的編碼方法，可知這種碼有如下特征：①它是一種分組碼：各個信源符號都被映射成一組固定次序的碼符號；②它是一種惟一可解的碼：任何碼符號序列只能以一種方式譯碼；③它是一種即時碼：由于代表信源符號的節(jié)點都是終端節(jié)點，因此其編碼不可能是其它終端節(jié)點對應(yīng)的編碼的前綴，霍夫曼編碼所得的碼字一定是即時碼。所以一串碼符號中的每個碼字都可不考慮其后的符號直接解碼出來。霍夫曼碼的譯碼：對接收到的霍夫曼碼序列可通過從左到右檢查各個符號進(jìn)行譯碼。*55說明：①霍夫曼碼是一種即時碼，可用碼樹形式來表示。②每次對縮減信源最后兩個概率最小的符號，用“0”和“1”碼是可以任意的，所以可得到不同的碼，但碼長不變，平均碼長也不變。③當(dāng)縮減信源中縮減合并后得到的新符號的概率與其他信源符號概率相同時，從編碼方法上來說，它們概率的排序是沒有限制的，因此也可得到不同的碼。即對給定信源，用霍夫曼編碼方法得到的碼并非是惟一，但平均碼長不變。三種編碼的比較Huffman:不唯一，但對信源沒有特殊要求，且編碼效率較高，設(shè)備要求簡單，綜合性能優(yōu)于另外兩種。相同點：三種編碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使平均碼長縮短，實現(xiàn)了信源壓縮。不同點：shnnon：有唯一的編碼，但編碼效率不是很高；Fano:編碼方法不唯一，適合與分組概率相等或相近的信源；*56*57限失真信源編碼由實際生活經(jīng)驗我們知道，一般人們并不要求完全無失真地恢復(fù)消息。對人的心理視覺研究表明，人們在觀察圖像時主要是尋找某些比較明顯的目標(biāo)特征，而不是定量地分析圖像中每個像素的亮度，或者至少不是對每個像素都等同地分析。例如觀看一段視頻或觀察一幅圖像，人們可能會關(guān)注其主要情節(jié)，對視頻或圖像中的細(xì)節(jié)并不是那么注意，此時便允許視頻或圖像有一定程度的失真。*58由香農(nóng)第一定理知，無論哪種信道，只要信息傳輸率R小于信道容量C，總能找到一種編碼方法，使得在信道上能以任意小的錯誤概率，以任意接近的傳輸率來傳送信息。實際信道中，信源輸出的信息傳輸率R一般都會超過信道容量，因此也就不可能實現(xiàn)完全無失真地傳輸信源的信息。由香農(nóng)第三定理知，在允許一定失真度D的情況下，信源輸出的信息傳輸率可壓縮到R(D)值，只要信息傳輸率R大于R(D)，一定能找到一種編碼方法，使得譯碼后的失真小于D。香農(nóng)第三定理從理論上給出了信息傳輸率與允許失真之間的關(guān)系，奠定了信息率失真理論的基礎(chǔ)。信息率失真理論是進(jìn)行量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。*59一般情況下信源編碼可分為離散信源編碼、連續(xù)信源編碼和相關(guān)信源編碼三類。前兩類編碼方法主要討論獨立信源編碼問題，后一類編碼方法討論非獨立信源編碼問題。離散信源可做到無失真編碼，而連續(xù)信源則只能做到限失真編碼。*60實用信源編碼方法無失真和限失真信源編碼定理，說明了最佳碼的存在性，但沒有給出具體構(gòu)造碼的方法，實用的編碼方法需要根據(jù)信源的具體特點來決定。霍夫曼碼在實際中已得到應(yīng)用，但它仍存在一些分組碼所具有的缺點，例如概率特性必須精確地測定，如果信源概率特性稍有變化，就必須更換碼表；對于二元信源，常需多個符號合起來編碼，才能取得較好的效果，但是如果合并的符號數(shù)目不大時，編碼效率提高得不多，特別是對于相關(guān)信源，霍夫曼編碼不能給出令人滿意的結(jié)果。因此在實用中常需作一些改進(jìn)，同時也就有必要研究非分組碼。在編碼理論的指導(dǎo)下，先后出現(xiàn)了許多性能優(yōu)良的編碼方法，本節(jié)介紹一些實用的編碼方法.*615.1.5游程編碼游程（Run-Length，簡記RL）是指符號序列中各個符號連續(xù)重復(fù)出現(xiàn)而形成符號串的長度，又稱游程長度或游長。游程編碼（Run-LengthCoding，簡記RLC）就是將這種符號序列映射成游程長度和對應(yīng)符號序列的位置的標(biāo)志序列。如果知道了游程長度和對應(yīng)符號序列的位置的標(biāo)志序列，就可以完全恢復(fù)出原來的符號序列。游程長度編碼舉例說明：

aaaa

bbb

cc

d

eeeee

fffffff(共22×8=176bit)

4a3b2c1d5e7f(共12×8=96bit)432157*62*63游程編碼特別適用于對相關(guān)信源的編碼。對二元相關(guān)信源，其輸出序列往往會出現(xiàn)多個連續(xù)的“0”或連續(xù)的“1”。在信源輸出的二元序列中，連續(xù)出現(xiàn)的“0”符號稱為“0游程”，連續(xù)出現(xiàn)的“1”符號稱為“1游程”，對應(yīng)連續(xù)同一符號的個數(shù)分別稱為“0”游程長度和“1游程”長度，因為游程長度是隨機的，其取值可以是1，2，3，…。對二元序列，“0”游程和“1游程”總是交替出現(xiàn)的，如果規(guī)定二元序列是以“0”開始的，那么第一個游程是“0”游程，第二個游程必為“1”游程，第三個游程又是“0”游程等等。將任何二元序列變換成游程長度序列，這種變換是一一對應(yīng)的，因此是可逆的、無失真的。因為游程長度是隨機的、多值的，所以游程序列本身是多元序列，對游程序列可以按霍夫曼編碼或其他編碼方法進(jìn)行處理以達(dá)到壓縮碼率的目的。000101110010001……31132131……若已知二元序列以0起始，從游程序列很容易恢復(fù)成原來的二元序列游程序列是多元序列，各長度可按赫夫曼編碼或其它方法處理以達(dá)到壓縮碼率的目的。

*64*65對于r元序列也存在相應(yīng)的游程序列。在r元序列中，可有r種游程。連續(xù)出現(xiàn)的符號的游程，其長度L(i)就是“i游程”長度。用L(i)也可構(gòu)成游程序列，但此時由于游程所對應(yīng)的信源符號可有r種，因此，這種變換必須再加一些標(biāo)志信源符號取值的識別符號，才能使編碼以后的游程序列與原來的r元序列一一對應(yīng)。所以把r元序列變換成游程序列再進(jìn)行壓縮編碼通常效率不高。*66游程編碼仍是變長碼，有著變長碼固有的缺點，即需要大量的緩沖和優(yōu)質(zhì)的通信信道。此外，由于游程長度可從“1”直到無窮大，這在碼字的選擇和碼表的建立方面都有困難，實際應(yīng)用時尚需采取某些措施來改進(jìn)。例如，通常長游程出現(xiàn)的概率較小，所以對于這類長游程所對應(yīng)的小概率碼字，在實際應(yīng)用時采用截斷處理的方法。游程編碼已在圖文傳真、圖像傳輸?shù)韧ㄐ殴こ碳夹g(shù)中得到應(yīng)用。在實際中還常常將游程編碼與其他編碼方法綜合起來使用，以期得到更好的壓縮效果。*675.1.6

冗余位編碼數(shù)據(jù)冗余的例子你的妻子，Helen，將于明天晚上6點零5分在上海的虹橋機場接你。

(23*2+10=56個半角字符)你的妻子將于明天晚上6點零5分在虹橋機場接你。

(20*2+3=43個半角字符）Helen將于明晚6點在虹橋機場接你。

(10*2+7=27個半角字符）描述語言

1．“這是一幅2×2的圖像，圖像的第一個像素是紅的，第二個像素是紅的，第三個像素是紅的，第四個像素是紅的”。

2．“這是一幅2×2的圖像，整幅圖都是紅色的”整理圖像的描述方法可以達(dá)到壓縮的目的*68實際圖像中冗余信息的表現(xiàn)（灰度圖）*69冗余位信源序列中不攜帶信息的符號。多元信源序列：冗余位上面二元1表示信息位，0表示冗余位

5.1.6

冗余位編碼*70冗余位序列游程編碼信息序列霍夫曼編碼*71對于連續(xù)信源輸出的消息，首先要在時間上進(jìn)行采樣，然后在取值上進(jìn)行量化并進(jìn)而編碼。在符合采樣定理的條件下，采樣所帶來的信息失真可以忽略不計。量化是用值域上有限個稱為量化值中的一個來代替信號值，量化必然帶來誤差；如果量化后采用無失真編碼，那么連續(xù)信源編碼中的信息失真就都來自量化過程。5.2連續(xù)信源編碼*72量化方法：一種是將各個采樣時刻的信號值逐個進(jìn)行量化，稱為標(biāo)量量化；另一種是將個采樣時刻的信號值組成一組，將其看作一個維矢量，將這些維矢量逐個進(jìn)行量化，稱為矢量量化。脈沖編碼調(diào)制（PCM，pulsecodemodulation）是研究最早、使用最廣的一種最佳標(biāo)量量化編碼。

5.2.1最佳標(biāo)量量化*73PCM的編碼原理：采樣量化編碼

模擬信號經(jīng)過采樣，成為時間離散的信號序列；將各個采樣時刻的信號值逐個量化、編碼，得到與取值也是離散的信號量化值序列相對應(yīng)的二進(jìn)制編碼序列。*74均勻量化是指在整個量化范圍內(nèi)的量化間隔都是相等，也稱為線性量化x1x2x3x4xq1xq2xq3xq4x1x2x3x4xq1xq2xq3xq4(a)(b)均勻量化*75四舍五入原則的中平量化特性x1x2x3x4xq1xq2xq3xq4由于均勻量化正反兩個方向的對稱性，可以將其分為極性判斷和信號絕對值量化兩個步驟。*76歸一化信號絕對值滿足，信號的量化數(shù)目為，則量化間隔，碼長*77(1)對信號值進(jìn)行極性判斷，確定極性碼；(2)通過信號絕對值與量化碼各位權(quán)值組合的逐次比較，確定量化碼；(3)將極性碼和量化碼組合起來，得到均勻量化編碼。編碼過程*78*79【例5.2.1】已知某一采樣時刻的歸一化信號值，設(shè)量化間隔，求其均勻量化編碼。

確定碼長：

確定極性碼：由于信號值，所以極性碼；確定量化碼：信號絕對值與量化碼最高位權(quán)值比較，由于，所以；與量化碼最高位和次高位權(quán)值之和比較，由于，所以；與量化碼最高位和最低位權(quán)值之和比較，由于，所以；故量化碼；將其組合，歸一化信號值的均勻量化編碼為量化值與信號值之間由于四舍五入而產(chǎn)生的量化誤差一般也稱為量化噪聲。

*80對于有記憶信源，采樣后的信號序列存在時間相關(guān)性，仍然對各個采樣時刻的信號值逐個進(jìn)行量化，會造成碼長的冗余。1.預(yù)測編碼利用信號序列的時間相關(guān)性，通過預(yù)測以減少信息冗余后再進(jìn)行編碼2.變換編碼引入某種變換，將信號序列變換為另一個域上彼此獨立或者相關(guān)程度較低的序列，同時將能量集中在部分樣值上，再對這個新序列進(jìn)行編碼。5.3相關(guān)信源編碼*81*825.3.1預(yù)測編碼預(yù)測編碼是數(shù)據(jù)壓縮三大經(jīng)典技術(shù)（統(tǒng)計編碼、預(yù)測編碼、變換編碼）之一，它是建立在信源數(shù)據(jù)相關(guān)性之上的。由信息理論可知，對于相關(guān)性很強的信源，條件熵可遠(yuǎn)小于無條件熵，因此人們常采用盡量解除相關(guān)性的辦法，使信源輸出轉(zhuǎn)化為獨立序列，以利于進(jìn)一步壓縮碼率。常用的解除相關(guān)性的措施是預(yù)測和變換，其實質(zhì)都是進(jìn)行序列的一種映射。一般來說，預(yù)測編碼有可能完全解除序列的相關(guān)性，但必需確知序列的概率特性；變換編碼一般只解除矢量內(nèi)部的相關(guān)性，但它可有許多可供選擇的變換方法，以適應(yīng)不同的信源特性。下面介紹預(yù)測編碼的一般理論與方法。*83預(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ù)測就是要找到計算預(yù)測值的預(yù)測函數(shù)。預(yù)測編碼原理

將第

個時刻的信號值

記為，相應(yīng)第

個時刻的信號值記為。對于時間相關(guān)的信號序列，由于

與

相關(guān)，故只要知道，就可對

進(jìn)行預(yù)測。設(shè)預(yù)測值為，則，稱為預(yù)測誤差。*84線性預(yù)測是最常用的預(yù)測方法，其表達(dá)為，式中，稱為預(yù)測階數(shù)， 為加權(quán)系數(shù)。

預(yù)測階數(shù)應(yīng)該取多大，加權(quán)系數(shù)又應(yīng)該怎樣選取，才能在性能和簡單上得到合理的折中?

最常用的是增量調(diào)制（DM）、差分脈沖編碼調(diào)制（DPCM）和自適應(yīng)差分脈沖編碼調(diào)制（ADPCM，），通常也稱為差值編碼。預(yù)測編碼

*85*865.4變換編碼由前節(jié)已經(jīng)看到，對于有記憶信源，由于信源前后符號之間具有較強相關(guān)性，要提高信息傳輸?shù)男适紫刃枰獬旁捶栔g的相關(guān)性，解除相關(guān)性可以在時域上進(jìn)行（如前面介紹的預(yù)測編碼方法），也可以在變換域上進(jìn)行，這就是本節(jié)要介紹的變換編碼方法。對于圖像信源等相關(guān)性更強的信源，常采用基于正交變換的變換編碼方法進(jìn)行數(shù)據(jù)壓縮。變換編碼的基本原理是將原來在空間（時間）域上描述的信號，通過一種數(shù)學(xué)變換（例如傅里葉變換等），將信號變到變換域（例如頻域等）中進(jìn)行描述，在變換域中，變換系數(shù)之間的相關(guān)性常常顯著下降，并常有能量集中于低頻或低序系數(shù)區(qū)域的特點，這樣就容易實現(xiàn)碼率的壓縮，并還可大大降低數(shù)據(jù)壓縮的難度。*87最早將正交變換思想用于數(shù)據(jù)壓縮是在20世紀(jì)60年代末期，由于快速傅里葉變換的出現(xiàn)，人們開始將離散傅里葉變換用于圖像壓縮；之后在1969年哈達(dá)瑪變換用于圖像壓縮；1971年KL變換用于圖像壓縮，得到了最佳的性能，故KL變換又稱為最優(yōu)變換；1974年出現(xiàn)了綜合性能較好的離散余弦變換（DCT），并很快得到廣泛的應(yīng)用；20世紀(jì)80年代后期，國際電信聯(lián)盟(ITU)制訂的圖像壓縮標(biāo)準(zhǔn)H.261選定DCT作為核心的壓縮模塊；隨后國際標(biāo)準(zhǔn)化組織(ISO)制定的活動圖像壓縮標(biāo)準(zhǔn)MPEG-1也以DCT作為視頻壓縮的基本手段；H.263/264的視頻壓縮國際標(biāo)準(zhǔn)中也有用到DCT。*88高性能的變換編碼方法不僅能使輸出的壓縮信源矢量中各分量之間的相關(guān)性大大減弱，而且使能量集中到少數(shù)幾個分量上，在其他分量上數(shù)值很小，甚至為“0”。因此在對變換后的分量(系數(shù))進(jìn)行量化再編碼時，因為在量化后等于“0”的系數(shù)可以不傳送，因此在一定保真度準(zhǔn)則下可達(dá)到壓縮數(shù)據(jù)率的目的，量化參數(shù)的選取主要根據(jù)保真度要求或恢復(fù)信號的主觀評價效果來確定。*89在變換編碼方法中最關(guān)鍵的是正交變換的選擇，最佳的正交變換是KL變換，這一變換的基本思想是由Karhunen和Loeve兩人分別于1947年和1948年單獨提出的，主要用于圖像信源的壓縮。由于KL變換使變換后隨機矢量的各分量之間完全獨立，因而它常作為衡量正交變換性能的標(biāo)準(zhǔn)，在評價其它變換的性能時，常與KL變換的結(jié)果進(jìn)行比較。KL變換的最大缺點是計算復(fù)雜，而且其變換矩陣與信源有關(guān)，實用性不強。為此人們又找出了各種實用化程度較高的變換，如離散傅里葉變換（DFT）、離散余弦變換（DCT）、沃爾什變換（WHT）等等，其中性能較接近KL變換的是離散余弦變換（DCT），在某些情況下，DCT能獲得與KL變換相同的性能，因此DCT也被稱為準(zhǔn)最佳變換。*90例給定兩幅圖像信源如圖所示，對它們進(jìn)行DCT，則其DCT系數(shù)圖所示，圖中亮度越大表示對應(yīng)的DCT系數(shù)數(shù)值也越大。*91正變換反變換其中指數(shù)上的求和是以“2”為模的，是D的二進(jìn)制表達(dá)式中的第i位的取值。例如當(dāng)n=3時，對，有。比較可知,WHT正變換和反變換只差一個常數(shù)項，所以用于正變換的算法也可用于反變換，這使得WHT的使用非常方便。*92WHT變換矩陣是一個對稱的正交矩陣，例如當(dāng)N=8時的WHT變換矩陣為：*93對WHT變換矩陣而言，其構(gòu)成規(guī)律具有簡單的迭代性質(zhì)，可以方便地產(chǎn)生各階變換矩陣。最小階(N=2)的TH為：如果用代表N階WHT變換矩陣，則上面所述的迭代關(guān)系如下：*94例給定如圖(a)所示的圖像信源，對其進(jìn)行WHT，則WHT系數(shù)圖(b)所示，同樣在圖中亮度越大表示對應(yīng)的WHT系數(shù)的取數(shù)值也越大。從本例可以看到，經(jīng)沃爾什-哈達(dá)瑪變換后圖像信號的能量向左上角集中，因而有利于數(shù)據(jù)的壓縮。但WHT的能量集中能力不如DCT。*95近年來，由于DCT的信息集中能力和計算復(fù)雜性綜合得比較好，而得到了較多的應(yīng)用，DCT已被設(shè)計在單個集成塊上。另外，近年來得到廣泛研究和應(yīng)用的一些編碼方法（例如子帶編碼、小波變換編碼、分形編碼等）也直接或間接地與變換編碼相關(guān)，在實際應(yīng)用中，需要根據(jù)信源特性來選擇變換方法以達(dá)到解除相關(guān)性、壓縮碼率的目的。另外還可以根據(jù)一些參數(shù)來比較各種變換方法間的性能優(yōu)劣，如反映編碼效率的編碼增益、反映編碼質(zhì)量的塊效應(yīng)系數(shù)等。當(dāng)信源的統(tǒng)計特性很難確知時，可用各種變換分別對信源進(jìn)行變換編碼，然后用實驗或計算機仿真來計算這些參數(shù)，從而選擇合適的編碼。*96

例：設(shè)有信源(1)求信源熵H(X);(2)編二進(jìn)制霍夫曼碼；(3)計算其平均碼長及編碼效率Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04*97Huffman編碼例輸入S1S2S3S4S5S6輸入概率0