《編碼理論》課件第9章

第9章限失真信源編碼

9.1離散信源信息率失真理論9.2連續(xù)信源信息率失真理論9.3量化編碼9.4預(yù)測編碼9.5變換編碼 9.1離散信源信息率失真理論

9.1.1失真函數(shù)及保真度準(zhǔn)則

由于只涉及信源編碼問題。所以可以將信道編碼和譯碼看成是信道的一部分。這樣接收者收到消息后所產(chǎn)生的失真（或誤差）只是由信源編碼帶來的。從直觀感覺可知，若允許失真越大，信息傳輸率可越小;若允許失真越小，信息傳輸率需越大。所以信息傳輸率與信源編碼所引起的失真（或誤差）是有關(guān)的。為了定量地描述信息傳輸率和失真的關(guān)系，可以略去廣義的無擾信道，所謂廣義無擾信道是指，把信道編碼、信道、信道譯碼這三部分看成一個沒有任何干擾的廣義信道。這樣通信系統(tǒng)可簡化成如圖9-1所示。圖9-1簡化的通信系統(tǒng)1．基本離散信源失真

設(shè)離散無記憶信源：信源符號通過信道傳輸?shù)浇邮斩?，則接收端的接收量為對應(yīng)于一對（u,v），定義一個非負(fù)函數(shù)：d(ui,vj)≥0，(i＝1，2，…，n；j＝1，2，…，m)(9-1)由于信源U有n個符號，而接收V有m個符號，所以d(ui,vj)就有n×m個，這n×m個非負(fù)的函數(shù)可以排成矩陣形式，即（9-2）稱它為失真矩陣，它是n×m階矩陣。

失真函數(shù)有多種形式，應(yīng)盡可能符合信宿的主觀特性；也就是主觀上的失真感覺應(yīng)與d(ui,vj)的值相對應(yīng)。越大，所感覺到的失真也越大，而且最好成正比。當(dāng)ui＝vj時，d應(yīng)等于零，表示沒有失真，當(dāng)ui≠vj時，d為正值。設(shè)x為信源輸出信息，y為信宿收到信息，則常用失真函數(shù)有：

均方失真： d(x,y)＝(x－y)2

絕對失真： d(x,y)＝|x－y|

相對失真： d(x,y)＝|x－y|/|x|

漢明失真：均方失真和絕對失真只與(x－y)有關(guān)，而不是分別與x及y有關(guān)，在數(shù)學(xué)處理上比較方便；相對失真與主觀特性比較匹配，因?yàn)橹饔^感覺往往與客觀量對數(shù)成正比，但在數(shù)學(xué)處理中就要困難得多。其實(shí)選擇一個合適的失真函數(shù)，要完全與主觀特性匹配已是非常困難的，更不用說還要易于數(shù)學(xué)處理。前三種失真函數(shù)適用于連續(xù)信源，最后一種失真函數(shù)適用于離散信源，漢明失真函數(shù)表示當(dāng)接收符號與發(fā)出信道符號相同時，就不存在失真和錯誤，所以失真度為零。當(dāng)接收到符號與發(fā)送符號不同時，就存在失真。而且認(rèn)為只要發(fā)送符號與接收符號不同所引起的失真都相同，失真度為常數(shù)，這里常數(shù)值為1（稱為漢明失真）。

[例9-1]二元對稱信源，信源U＝{0，1}，接收變量V＝{0,1}在漢明失真定義下，失真函數(shù)為：

d(0,0)＝d(1,1)＝0

d(0,1)＝d(1,0)＝1它表示當(dāng)信源發(fā)送符號0（或符號1）而接收到的符號仍是0（或符號1）時，則認(rèn)為無失真或無錯誤存在。反之，若發(fā)送信源符號0（或符號1）而信宿接收符號1（或符號0）時，則認(rèn)為有錯誤，并且這兩種錯誤后果是等同的。失真矩陣為

[例9-2]設(shè)信源U＝{0,1},接收變量V＝{0,1,2}定義失真函數(shù)為：

d(0,0)＝d(1,1)＝0,d(0,1)＝d(1,0)＝1,d(0,2)＝d(1,2)＝0.5

則失真矩陣：

【例9－3】信源U＝{0,1,2},接收變量V＝{0,1,2},均方失真函數(shù)為d(ui,vj)＝(ui－vj)2,求失真矩陣。

解由失真定義得失真矩陣為因?yàn)樾旁碪和信宿接收量V都是隨機(jī)變量，所以單個符號失真度d(ui,vj)也是隨機(jī)變量。那么，現(xiàn)在定義傳輸一個符號引起的平均失真，即信源平均失真為（9-3）式中ui

—信源輸出符號，i＝1，2，…，n；

p(ui)—信源符號ui對應(yīng)概率；

vj—信宿接收符號；j＝1,2,…，m；

p(vj|ui)—廣義無擾信道傳遞概率。

單個符號的失真度d(ui,vj)描述了某個信源符號通過傳輸后失真的大小，對于不同的信源符號和不同的接收符號，其值是不同的。但平均失真度已對信源和信道進(jìn)行了統(tǒng)計平均，所以此值是描述某一信源在某一廣義無擾信道（或稱為試驗(yàn)信道）傳輸下的失真大小，是從總體上描述整個系統(tǒng)的失真情況。

[例9-4]等概信源，通過信道轉(zhuǎn)移概率矩陣P的信道傳輸，失真測度為均方失真測度，求平均失真。信道轉(zhuǎn)移概率矩陣為０１２解:

2.N次擴(kuò)展信源失真

從基本離散信源失真度出發(fā)，可以定義N次無記憶擴(kuò)展信源的失真函數(shù)和平均失真度。擴(kuò)展信源失真度（失真函數(shù)）：（9-4）式中：S——信源的一個輸出序列，Y—信宿的一個接收序列，式（9－4）表明，擴(kuò)展信源的失真度等于序列中對應(yīng)單個信源符號失真度之和，單個符號失真度為d(S,Y)/N。

由此可得N次擴(kuò)展信源平均失真度為（9-5）則單個信源符號平均失真度：（9-6）當(dāng)信源與信道都是無記憶時，N次擴(kuò)展信源平均失真度：（9-7）式中：—擴(kuò)展信源中第l個分量平均失真度。此時單個信源符號平均失真度：（9-8）若平均失真度不大于所允許的失真D，即：（9－9）稱式（9-9）為保真度準(zhǔn)則。

N次擴(kuò)展信源的保真度準(zhǔn)則是：平均失真度D(N)不大于允許失真ND，即(9-10)

[例9-5]離散無記憶信源，離散無記憶信道分別為因失真測度為漢明失真測度。求平均失真及二次擴(kuò)展信源的單個符號平均失真。解:由式（9-3）可計算得對上述信源作二維擴(kuò)展，可得擴(kuò)展信源概率分布為二次擴(kuò)展信道矩陣由式（9-4）得二次擴(kuò)展信源失真矩陣，將其除2得單個符號失真矩陣為由式（9-5）得二次擴(kuò)展信源平均失或者根據(jù)式（9-8）也可得二次擴(kuò)展信源平均失真9．1．2信息率失真函數(shù)

在信源給定，又定義了失真函數(shù)以后，總希望在滿足一定失真的情況下，使信源傳輸給信宿的信息傳輸率R盡可能地小。或者說，在滿足保真度準(zhǔn)則下，尋找信源必須傳輸給信宿的信息率R的下限值。從接收端來看，就是在滿足保真度準(zhǔn)則下，尋找再現(xiàn)信源消息所必須獲得的最低平均信息量。而接收端獲得的平均信息量可用平均互信息I(U；V)來表示，這就變成了在滿足保真度準(zhǔn)則的條件下（D

≤D）,尋找平均互信息I(U；V)的最小值?？梢栽贒失真許可的試驗(yàn)信道集合BD中尋找某一個信道p(vj|ui)，使I(U；V)取最小值。由于平均互信息I(U;V)是p(vj|ui)的U型凸函數(shù)，所以在BD集合中，極小值存在。這個最小值就是在D

≤D條件下，信源必須傳輸?shù)淖钚∑骄畔⒘俊＜矗?/p>

（9-11）

（9-12）式中：S——信源的一個輸出序列；

Y——信宿的一個接收序列；

BND——所有滿足保真度準(zhǔn)則D(N)≤ND的試驗(yàn)信道的集合。

在研究信息率失真函數(shù)R(D)時，引用的條件概率p(v|u)并沒有實(shí)際信道的含義。只是為了求平均互信息的最小值而引用的、假想的可變試驗(yàn)信道。實(shí)際上這些信道反映的僅是不同的有失真信源編碼或信源壓縮。N次無記憶擴(kuò)展信源的信息率失真函數(shù)RN(D)：

（9-13）9.1.3信息率失真函數(shù)定義域及性質(zhì)

1．R(D)的定義域(Dmin,Dmax)

1)Ｄmin和R(Dmin)（9-14）（9-15）

則可得信源的最小平均失真度為（9-16）(9-17)

但是，式(9-17)能否成立是有條件的，它與失真矩陣形式有關(guān)、只有當(dāng)失真矩陣中每行至少有一個零，并每一列最多只有一個零時，式(9-17)才成立。否則R(0)可以小于H（U），它表示這時信源符號集中合些符號可以壓縮，合并，而不帶來任何失真。即（9-18）（9－18）

解：由式(9-16)可知最小允許失真度為

由式（9-15）得滿足最小允許失真度的試驗(yàn)信道是一個無噪無損的試驗(yàn)信道，信道矩陣為[例9-7]設(shè)信源及失真矩陣分別為：信宿 求及其對應(yīng)的信道。解：由式（9-16）計算得由式（9-15）可知，使平均失真度達(dá)到最小值的信道必須滿足

[例9-8]改變例9-7的失真矩陣使，求對應(yīng)失真矩陣Ｄ’及對應(yīng)信道？

解：若失真矩陣改成失真矩陣Ｄ’與失真矩陣Dij之間滿足則同樣，集合中的信道必滿足（9-19）(9-20)取最小值不取最小值(9-21)那么，通過試驗(yàn)信道的平均交互信息量(9-22)(9-23)的約束條件下，信宿V不需獲取信源U任何信息量。當(dāng)然，信源U也就不需輸出任何信息量，均可滿足保真度準(zhǔn)則 。所以，這時的信源U的信息率失真函數(shù)為（9－24）[例9-9]設(shè)二元離散信源解：由（9-20）式得最大允許失真度j=22.函數(shù)的性質(zhì)

無論是離散信源還是連續(xù)，函數(shù)都有以下特性：

(1)信息率失真函數(shù)有

或?qū)懗蓪τ陔x散信源，只有當(dāng)失真矩陣中每行至少有一個零元素，并每一列最多只有 一個零元素時，才有;(9-25)(9-26)(9-27)的條件下，使(9-28)最小化。在原則上，應(yīng)用拉格朗日乘子法可以求出解來，但如果要得到明顯的解析表達(dá)式，那是比較因難的，通常只能用參量形式來表達(dá)。即便如此，除簡單情況外，實(shí)際計算仍然是相當(dāng)困難的。尤其是對于約束條件式(9－25)，它是求解R(D)函數(shù)的最主要障礙。因?yàn)閼?yīng)用拉格朗日乘子法解得的一個或幾個p(vj|ui)很可能是負(fù)的。在這種情況下，首先必須假設(shè)某些p(vj|ui)＝0，再重新計算，這會使得計算復(fù)雜化。目前，可采用有效的迭代算法在電子計算機(jī)上求解R(D)函數(shù)。(9-29)(9-30)式中計算公式(9-31)（9-32）極小值對應(yīng)的試驗(yàn)信道9.1.5離散信源計算

對基本離散信源，若規(guī)定失真函數(shù)為漢明失真度，其失真矩陣對于一般試驗(yàn)信道的信道矩陣其平均失真度（9－34）（9－35）（9－36）試驗(yàn)信道集合BD中的所有試驗(yàn)信道的平均錯誤傳遞概率Pe都等于允許失真度D，即有（9－37）另一方面，由式(9－34)和(9－35)可知，式(9－37)中的的Pe數(shù)學(xué)表達(dá)式為（9－38）這個表達(dá)式在數(shù)學(xué)上與費(fèi)諾不等式中的Pe完全相同，因此由費(fèi)諾不等式有(9－39)（9－40）（9－41）這就是在漢明碼失真度下，離散信源U的信息率失真函數(shù)的一般表達(dá)式。

【例9－10】設(shè)二元離散信源（9－42）這個信道是唯一的試驗(yàn)信道，其平均交互信息量就等于信息率失真函數(shù)：（9-43）因?yàn)椋?-42）式所示信道矩陣中每列只有一個非零元素“1”，所以其疑義度，信息率失真函數(shù)（9－44）由式（9－20）得最大允許失真度為（j=2）（9－45）這個信道也是唯一的試驗(yàn)信道，其平均交互信息量就等于信息率失真函數(shù):（9－46）顯然，式（9－45）所示為試驗(yàn)信道的噪聲熵H(V|U)=H(V)，所以,當(dāng)允許失真度D取最大允許失真度 時，信源U的信息率失真函數(shù)為（9－47）允許失真度D處于最小允許失真度Dmin=0與最大允許失真度Dmax=ω之間，即0<D<ω，給定二元離散信源U的信息熵H(U)=H［ω,1-ω］=H(ω)，由式（9－41）可得給定二元離散信源U的信息率失真函數(shù)為在漢明失真度下，二元離散信源R（D）表達(dá)式（9－48）圖9-2二元離散信源函數(shù)

由圖9-2可看出，當(dāng)二元離散信源U的概率分布確定時，信息率失真函數(shù)R(D)是允許失真度D的函數(shù)。允許失真度D越大，R(D)函數(shù)越小，信源U可壓縮程度就越大；允許失真度D越小，R(D)函數(shù)就越大，信源可壓縮程度就越小。另一方面，對于同一允許失真度D來說，信源U的概率分布ω越接近1／2，信源分布越均勻，R(D)函數(shù)越大，信源U可壓縮程度越??；信源U的概率分布ω越不接近1／2，信源分布越不均勻，R(D)函數(shù)越小，信源U可壓縮程度越大。9.1.6保真度準(zhǔn)則下的信源編碼定理

定理9－1（限失真信源編碼定理）設(shè)離散無記憶信源U的失真函數(shù)為R（D），給定允許失真D，則當(dāng)信息率R>R（D），只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼平均失真小于或等于D＋ε，即，ε為任意小的正數(shù)；反之，若R<R（D），則無論采用什么樣的編碼方法，其平均譯碼失真必大于D,即 。

如果是二元信源，對于任意小的ε(ε>0)，每一個信源符號的平均碼長滿足如下公式:

該定理指出，在失真限度內(nèi)使信息率任意接近R（D）的編碼方法是存在的，然而，要使信息率小于R（D），平均失真一定會超過失真限度D。這個定理證明了允許失真D確定后，總存在一種編碼方法，使編碼的信息傳輸率R大于R（D）且可任意接近R（D），而平均失真小于允許失真D。反之，若R<R（D），那么編碼的平均失真將大于D。如果用二進(jìn)制符號進(jìn)行編碼的話，在允許一定量失真D情況下，平均每個信源符號所需二元碼符號的下限值就是R（D）。由此可見，信息率失真函數(shù)R（D）確實(shí)是在允許失真度為D的情況下信源信息壓縮的下限值。當(dāng)信源給定后，無失真信源壓縮的極限值是信源熵H（U）；而有失真信源壓縮極限值是信息率失真函數(shù)R（D）。第一類問題是，符合實(shí)際信源的R(D)函數(shù)的計算相當(dāng)困難。首先，需要對實(shí)際信源的統(tǒng)計特性有確切的數(shù)學(xué)描述。其次，需要對符合主客觀實(shí)際的失真給予正確的度量，否則不能求得符合主客觀實(shí)際的R(D)函數(shù)。例如，通常采用均方誤差來表示信源的平均失真度。但對于圖像信源來說，當(dāng)采用均方誤差較小的編碼方法時，人們視覺感到失真較大，所以，人們?nèi)圆捎弥饔^觀察來評價編碼方法的好壞。因此，如何定義符合主觀和客觀實(shí)際情況的失真測度就是件較困難的事。第三，即便對實(shí)際信源有了確切的數(shù)學(xué)描述，又有符合主客觀實(shí)際情況的失真測度，而信息率失真函數(shù)R(D)的計算還是較困難的。 9.2連續(xù)信源信息率失真理論

9.2.1連續(xù)信源數(shù)學(xué)模型及熵

基本連續(xù)信源數(shù)學(xué)模型為其中R是全實(shí)數(shù)集，是連續(xù)變量X取值范圍，p(x)為x的概率密度。定義連續(xù)信源的熵（差熵）為：（9－49）

同理，可定義兩個連續(xù)變量x，y的聯(lián)合熵和條件熵：(9－50)(9－51)(9－52)這樣定義的差熵具有可加性、凸?fàn)钚院蜆O值性，不存在非負(fù)性和變換不變性等。9.2.2連續(xù)信道互信息

設(shè)基本連續(xù)信道如圖9－3所示。其輸入和輸出都是單個連續(xù)型隨機(jī)變量的信道，可用模型{X,p(y｜x),Y}來描述單符號連續(xù)信道。圖9-3基本連續(xù)信道

圖9－3中，X是輸入連續(xù)型隨機(jī)變量，取值于［a,b］或?qū)崝?shù)域R；Y是信道輸出連續(xù)型隨機(jī)變量，取值于［a′,b′］或?qū)崝?shù)域R；信道的傳遞概率密度函數(shù)為p(y｜x),并滿足：（9－53）信宿接收Y滿足：信道輸入X滿足：(9-54)(9-55)定義X和Y之間平均互信息為：(9-56a)(9-56b)(9-56c)9.2.3連續(xù)信源的信息率失真函數(shù)

定義連續(xù)信源平均失真度為（9－57）式中：d(x,y)—連續(xù)信源失真函數(shù)；P(x)—連續(xù)信源X的概率密度；P(y|x)—信道傳遞概率密度。根據(jù)連續(xù)信源平均失真度的定義，可求得平均互信息I(X；Y)＝h(Y)－h(huán)(Y|X),則連續(xù)信源的信息率失真函數(shù)為（9－58）式中：BD—滿足 所有廣義無擾信道集合；inf—指下確界。嚴(yán)格地說，連續(xù)集合中可能不存在極小值，但下確界是存在的。 9.3量化編碼

9.3.1均勻量化

標(biāo)量量化中最簡單的方法是均勻量化，也叫做線性量化。設(shè)量化器輸入為x，對應(yīng)的實(shí)數(shù)值域空間為R，量化器輸出為y，對應(yīng)的實(shí)數(shù)值域空間為Rc，則x和y的關(guān)系為y＝Q（x）（9－59）

設(shè)Rc對應(yīng)取值范圍[a0,an],a0可為負(fù)無限，an可為正無限，所謂均勻量化就是將區(qū)間[a0,an]分割為n個相等距離且互不重疊的子區(qū)間[ai,ai＋1]，取每個小區(qū)間的中點(diǎn)值作為量化值yi，即ai≤x≤ai＋1

時，yi＝(ai＋1＋ai)/2,若x的概率分布函數(shù)為P（x），則：（9－60）均勻量化的量化誤差為e＝x－Q(x)＝x－yi(x)（9－61）量化器均方誤差為（9－62）量化器輸入方差為（9－63）可得量化器的信噪比SNR(SignalNoiseRate)為（9－64）

量化器一般有3個工作特性區(qū)域：

1)正常量化區(qū)

當(dāng)輸入x[ao,an]時，量化器能得到正常的量化輸出；

2)限幅區(qū)

當(dāng)x<ao

或x>an時，量化器只能分別輸出常量ao＋Δ/2和an－Δ/2。量化器此時處于限幅或過載工作狀態(tài)，將會產(chǎn)生較大的失真。

3.空載區(qū)

當(dāng)－Δ/2<x－ai<Δ/2時，將有兩種情況：

（1）當(dāng)輸入x＝ai時，由于某種因素，使得x稍高于ai，則量化器輸出上一級量化值yi＋1；當(dāng)輸入x稍低于ai時；則輸出下一級量化值yi－1，這時產(chǎn)生的誤差為±Δ，量化器輸出在兩個量化級間往返跳動，形成一個矩形波輸出，結(jié)果將產(chǎn)生量化時得點(diǎn)狀噪聲。

（2）輸入x在ai之上或之下，量化輸出分別輸出恒定值yi

＝ai＋Δ/2或yi－1

＝ai－Δ/2。9.3.2最優(yōu)量化

將樣本值量化總是要帶來誤差的，因此，人們在設(shè)計量化器時，總希望其誤差越小越好，即尋求最優(yōu)量化誤差。所謂最優(yōu)量化,就是使量化器的均方誤差σ2e為最小或量化器的信噪比SNR最大的量化。根據(jù)信息熵的理論可以推斷，量化誤差最小的最優(yōu)量化器對量化器輸入?yún)^(qū)間的分割應(yīng)該是非均勻的。由于最優(yōu)量化與p（x）有關(guān)，因而區(qū)間分割也與p（x）有關(guān)，尤其當(dāng)N足夠大時，可以近似認(rèn)為在各個子區(qū)間［ai，ai＋1］上的概率分布p（x）為一常數(shù)，也就是說，在各子區(qū)間上可被視為均勻分布，即P（x）≈P（yi），x[ai,ai＋1](9－65)最優(yōu)量化就是使量化器的均方誤差σ2e為最小，將式（9－62）分別對ai和yi求導(dǎo)，并令其為零，即(9－66)(9－67)i＝1,2,…,n

(9－68)(9－69)

這里求出的ai和yi的值就是最優(yōu)量化時的值。可見ai的最佳位置是輸出yi－1和yi的中點(diǎn),yi

最佳位置概率密度P(x)在ai

和ai＋1區(qū)間的概率中心。一般情況下，ai和yi是互相制約、相互依賴的，不容易求出解析解，所以只能用遞推公式獲得近似解。Max—Livod采用迭代方法如下：

(1)任取y0；

(2)由 ,計算a1；

(3)根據(jù)公式（9－68）計算y1；

(4)重復(fù)步驟(2)、(3)，分別計算出a2，y2，a3，y3…，直至最后求得yn－1；

(5)檢驗(yàn)yn是否為［an－1，an］的概率中心，即式 是否成立，或在允許的一定的誤差范圍內(nèi)成立；

(6)若步驟(5)滿足，則過程結(jié)束;否則，重新選y0，并重復(fù)上述操作步驟。由上述可知，對于已知概率分布模型及其數(shù)字特征的數(shù)據(jù)過程，能較容易地依據(jù)概率分布安排量化器的電平劃分，得到最小量化誤差的最優(yōu)量化器。如果概率分布是均勻的，那么，采用均勻量化器是較為理想的。對一些常見概率分布，如Gauss、Laplace、Gamma等其最優(yōu)量化器是惟一存在的；而對于概率分布模型未知的隨機(jī)過程，其優(yōu)化量化器的設(shè)計較為困難，雖然Max-Livod算法能解決此問題，但在實(shí)現(xiàn)上仍是有較大難度的。主要原因是該算法不易用硬件實(shí)現(xiàn)，而且其執(zhí)行時間也因y0的不同而不同。均勻量化器雖然不是最優(yōu)量化器，但其設(shè)計思想簡單，易于硬件實(shí)現(xiàn)，因此，在不少的數(shù)字化系統(tǒng)中至今仍然采用。然而，對于一些數(shù)字化后其數(shù)據(jù)量十分龐大的系統(tǒng)，若采用均勻量化器，勢必要有大的存儲空間，否則將影響其量化速度。這時最好采用記憶量化器(矢量量化)。倘若對量化精度要求較高，顯然采用非均勻量化器要比均勻量化器好。9.3.3矢量量化

要想得到性能好的編碼，僅采用標(biāo)量量化是不可能的。在最佳編碼中,如將離散信源的多個符號聯(lián)合編碼則可提高效率，而連續(xù)信源也是如此。當(dāng)把多個信源聯(lián)合起來形成多維矢量后再對矢量進(jìn)行標(biāo)量量化時，其自由度將更大，并且在同樣的失真下，量化級數(shù)可進(jìn)一步減少，碼率可進(jìn)一步壓縮。我們把這種量化叫做矢量量化。

實(shí)驗(yàn)證明，即使各信源符號相互獨(dú)立，多維量化通常也可壓縮信息率，從而引起了人們對矢量量化的興趣并成為當(dāng)前連續(xù)信源編碼的一個研究熱點(diǎn)?？墒钱?dāng)維數(shù)較大時，矢量量化目前尚無解析方法，則只能求助于數(shù)值計算；而且聯(lián)合概率密度也不易測定，還需采用訓(xùn)練序列等方法。一般來說，高維矢量聯(lián)合是很復(fù)雜的，雖已有不少方法，但其實(shí)現(xiàn)尚有不少困難，有待于進(jìn)一步研究。設(shè)信源構(gòu)成的矢量（矢量量化器輸入）為：X＝（X1，X2，…，XN），Xj＝（xj1，xj2，…,xjk），XRK（K維歐幾里德空間），把Rk劃分成J＝2n個互不相交的子空間R1，R2，…，RJ，求出每個子空間的質(zhì)心Yi，所有的Yi構(gòu)成Y＝{Y1，Y2，…，YJ}，Y為量化器的輸出空間，也叫碼書（或碼本），Yi叫碼字或碼矢，J叫碼書的長度。

對J階K維的矢量量化，實(shí)質(zhì)上是判斷輸入矢量XjRk屬于哪個子空間Ri，然后輸出該子空間代表變量Yi，即：Yi＝Q（Xj），1≤i≤J，1≤j≤N

（9－70）這里Yi就是Xj的編碼。實(shí)際編碼時，在發(fā)送端只需記錄代表變量Yi的下標(biāo)i，所以編碼過程是把X映射到I＝{1，2，…，J}；而譯碼過程是在接收端依據(jù)收到的I代碼，查找碼書Y，獲得碼字Yi，用來代替Xj。由于總的碼字個數(shù)J一般遠(yuǎn)小于總的輸入信號NK，所以矢量量化的壓縮能力非常大。傳輸或存儲一個變量所需比特為lbJ（一般J＝2n），它是一個K維變量，就是K個輸入信號，所以每個輸入信號的平均比特只有l(wèi)bJ/K，稱之為壓縮比。適當(dāng)選取碼書長度J和碼字維數(shù)K，可以獲得很大壓縮比。矢量量化中碼書的碼字越多，維數(shù)越大，失真就越小。只要適當(dāng)?shù)剡x擇碼字?jǐn)?shù)量，就能控制失真量不越過某一給定值，因此碼書控制著矢量的大小。矢量量化每輸入一個矢量Xj，都要和J個碼矢Yi逐一比較，搜索其最接近的碼矢Yi。由于兩者均為K維矢量，所以工作量很大。9.4預(yù)測編碼

9.4.1基本原理對于有記憶信源，信源輸出的各個分量之間是有統(tǒng)計關(guān)聯(lián)的，這種統(tǒng)計關(guān)聯(lián)性可以加以充分利用。預(yù)測編碼就是基于這一思想的技術(shù)。它不直接對信源輸出的信號進(jìn)行編碼，而是將信源輸出信號通過預(yù)測變換后再對信源輸出與被預(yù)測值的差值進(jìn)行編碼，其原理圖如圖9－4所示。圖9－4預(yù)測編碼原理圖設(shè)信源第i瞬間的輸出值為ui，而根據(jù)信源的前k(k<i)個樣值，給出的預(yù)測值為：(9－71)式中：f（）為預(yù)測函數(shù)。

f()可以是線性函數(shù)也可以是非線性函數(shù)。線性預(yù)測函數(shù)實(shí)現(xiàn)比較簡單，這時的預(yù)測值為（9－72）式中：aj為預(yù)測系數(shù)。則第i個樣值的預(yù)測誤差值為（9－73）根據(jù)信源編碼定理，若直接對信源輸出ui進(jìn)行編碼，則其平均碼長Lu應(yīng)趨于信源熵：(9－74)若對預(yù)測變換后的誤差值e進(jìn)行編碼，其平均碼長Le應(yīng)趨于誤差信號熵：(9－75)

顯然，從信息論觀點(diǎn)，預(yù)測編碼能壓縮信源數(shù)碼率的必要條件為(9－76)由于信息熵是概率分布的泛函數(shù)，故概率分布越均勻，熵就越大；概率分布越不均勻，熵就越小?？梢宰C明預(yù)測差值的概率分布要比原始信號的概率分布集中，即H(E)≤H(U)，所以式（9－76）成立。信源通過預(yù)測以后數(shù)據(jù)壓縮(或連續(xù)時的頻帶壓縮)倍數(shù)就越大。從預(yù)測編碼原理可以看出，實(shí)現(xiàn)預(yù)測編碼要進(jìn)一步考慮三個方面的問題：首先是預(yù)測誤差準(zhǔn)則的選取，這個問題決定預(yù)測質(zhì)量標(biāo)準(zhǔn)；其次是預(yù)測函數(shù)的選??；最后一個問題是預(yù)測器輸入數(shù)據(jù)的選取。后兩個問題決定預(yù)測質(zhì)量的好壞。關(guān)于預(yù)測函數(shù)的選取，一般是采用工程上比較容易實(shí)現(xiàn)的線性預(yù)測，一旦線性方程確定下來，預(yù)測的精度與k值大小將有直接關(guān)系。k愈大，預(yù)測愈精確，但設(shè)備愈復(fù)雜；k愈小，精度愈差，但設(shè)備愈簡化，所以k值大小要根據(jù)設(shè)計要求和實(shí)際效果而確定。關(guān)于預(yù)測器輸入數(shù)據(jù)的選取，是指選取何處的原始數(shù)據(jù)作為預(yù)測器的輸入依據(jù)。一般可分為開環(huán)、閉環(huán)和開環(huán)閉環(huán)兩者的混合這三類。關(guān)于預(yù)測誤差準(zhǔn)則的選取，是指預(yù)測誤差所依據(jù)的標(biāo)準(zhǔn)。目前大致可采用四種類型準(zhǔn)則，它們分別是：最小均方誤差(MMSE)準(zhǔn)則；功率包絡(luò)匹配(PSEM)準(zhǔn)則；預(yù)測系數(shù)不變性(PCIV)準(zhǔn)則；最大誤差(ME)準(zhǔn)則。其中,最小均方誤差準(zhǔn)則是最基本、最常用的準(zhǔn)則;而預(yù)測系數(shù)不變性的主要特點(diǎn)是它預(yù)測系數(shù)與輸入信號統(tǒng)計特性無關(guān)，因而能對多種混合信號進(jìn)行有效的預(yù)測;最大誤差準(zhǔn)則主要用于遙測數(shù)據(jù)壓縮?？梢宰C明，在均方誤差準(zhǔn)則下，按條件期望值進(jìn)行預(yù)測是最佳預(yù)測。然而它必須知道ui的聯(lián)合概率密度函數(shù)，這一般是很困難的。但是對于廣義平穩(wěn)正態(tài)過程，只要已知二階矩相關(guān)函數(shù)就等效于已知ui的聯(lián)合概率密度函數(shù)。這時，線性預(yù)測與最佳預(yù)測是等效的。因?yàn)閷φ龖B(tài)信源，線性無關(guān)與統(tǒng)計獨(dú)立是完全等效的。所以，能完全解除線性相關(guān)性的信源即是符合統(tǒng)計獨(dú)立的無記憶信源。9.4.2預(yù)測方法

1.線性預(yù)測

若樣值和預(yù)測值之間呈線性關(guān)系,則稱為線性預(yù)測,否則稱為非線性預(yù)測。常用的幾種線性預(yù)測方案有：

（1）前值預(yù)測，即 。

（2）一維預(yù)測，即用ur前面已知的k個樣值預(yù)測ur的值，預(yù)測公式如式（9－72）所示。

（3）二維預(yù)測，也稱為非線性預(yù)測，即預(yù)測值與樣值之間是非線性關(guān)系。

3.自適應(yīng)預(yù)測

當(dāng)信源是一個平穩(wěn)隨機(jī)過程時，可以使用固定參數(shù)預(yù)測器進(jìn)行預(yù)測；當(dāng)信源為非平穩(wěn)過程或總體平穩(wěn)，但局部不平穩(wěn)時，再利用固定參數(shù)來設(shè)計預(yù)測器就不合理了。對這種信源應(yīng)采用自適應(yīng)預(yù)測編碼的方法。所謂自適應(yīng)預(yù)測，就是預(yù)測器的預(yù)測系數(shù)不固定，隨信源特性而有所變化。如果充分利用信源的統(tǒng)計特性及其變化，重新調(diào)整預(yù)測參數(shù)，這樣就使得預(yù)測器隨著輸入數(shù)據(jù)的變化而變化，從而得到較為理想的輸出。有些信源的統(tǒng)計特性從整體上看是非平穩(wěn)過程，但在一定的時間（或范圍）內(nèi)把它看做平穩(wěn)過程，還是合理的，例如，圖像的平坦區(qū)，語音信源的基音段。因此，可以把信源看成多個平穩(wěn)子過程構(gòu)成的組合信源?？梢宰C明組合信源模型的熵低于把非平穩(wěn)信源作為單一平穩(wěn)信源的熵，這樣采用自適應(yīng)預(yù)測可進(jìn)一步減小預(yù)測誤差和降低數(shù)碼率。自適應(yīng)預(yù)測方法很多，一般可分為線性自適應(yīng)預(yù)測和非線性自適應(yīng)預(yù)測兩大類。9.4.3

DPCM編譯碼原理

預(yù)測編碼,特別是線性預(yù)測編碼已在信息與通信系統(tǒng)的信息處理中被廣泛地采用，差分脈碼調(diào)制（DPCM）便是常用的一種。

1．DPCM型工作原理

DPCM即差分脈碼調(diào)制，其工作原理如圖9－5所示。圖9-5DPCM型原理圖

2．DPCM編、譯碼原理

實(shí)際應(yīng)用預(yù)測來解除相關(guān)性從而壓縮碼率常采用差值編碼或前值預(yù)測編碼。這在信源序列的相關(guān)性很強(qiáng)和鄰值間的相關(guān)系數(shù)接近1時是很有效的，也是最常被應(yīng)用的方法。此時預(yù)測值是相鄰兩個符號值之差或者就是前一個符號的值，并對此預(yù)測值進(jìn)行編碼。這種方法不但可用于連續(xù)信源，也可用于離散信源。差分脈碼調(diào)制(DPCM)和增量調(diào)制這兩種方法常用于語音編碼，當(dāng)然也能用于圖像編碼。語音和圖像這兩種常見的信源，其鄰值間的相關(guān)性一般都是相當(dāng)強(qiáng)的，因此采樣頻率必須較高，才能保證質(zhì)量。由采樣定理可知，采樣頻率必須大于信號頻帶的兩倍。對于語音信號，若頻帶過小，則會丟失高頻分量而影響音質(zhì)；而對于圖像信號，頻帶即意味著水平清晰度，頻帶若不夠就會使圖像模糊。若采樣頻率足夠高，相鄰樣值的時間間隔就小，其相關(guān)系數(shù)也就會接近1，因此適宜用差值編碼。差值編碼中的差分脈碼調(diào)制的工作原理已在前面介紹過,下面介紹DPCM的編、譯碼原理。最簡單的DPCM是增量調(diào)制，又稱為M。這時差值的量化級定為2。也就是當(dāng)差值為正時，用“1”表示；差值為負(fù)時，則用“0”代表。每個差值只需一比特。一般地說，要減少量化失真，則必須增加取樣頻率，即不能再采用常用的2，其中為信源上限頻率。在譯碼時，為相反變換，即規(guī)定一個增量值，當(dāng)收到“1”時在前一個值中加上一個值作譯碼輸出；收到“0”時，則在前一個值中減去一個值作為譯碼輸出。其原理圖如圖9-6所示，編譯碼器的輸入輸出波形如圖9-7所示。如果在信道中不傳送預(yù)測誤差，而是傳送線性預(yù)測器中的各項(xiàng)系數(shù)(參量)，往往傳送參數(shù)所需的數(shù)碼率遠(yuǎn)遠(yuǎn)低于傳送原始信源數(shù)據(jù)的數(shù)碼率。在接收端可以采用一隨機(jī)噪聲序列代替原來接收到的序列，則在一定條件下也可再現(xiàn)原始信源輸出序列。顯然，它也是一種變型線性預(yù)測編碼，在語音壓縮中，稱它為線性預(yù)測聲碼器(Vocoder)，可見，它是DPCM的一個特例。由于在DPCM型中，量化器位于反饋環(huán)內(nèi)故又稱為閉環(huán)型，它可以使環(huán)內(nèi)殘存量化誤差大為減少。

圖9－6

DPCM增量調(diào)制編、譯碼原理圖9－7

DPCM增量調(diào)制編、譯碼器的輸入、輸出波形（a）編碼器輸入及編碼輸出;（b）譯碼器的恢復(fù)波形由上述分析可見,估值和實(shí)際值之間存在著兩類誤差,一類是量化誤差,另一類是過載誤差。一般情況下，量化誤差的絕對值小于Δ。當(dāng)階梯曲線跟不上連續(xù)曲線的上升斜率（或下降斜率）時而產(chǎn)生的誤差稱為過載誤差（或失真）。當(dāng)所選的級差Δ小時，易產(chǎn)生過載失真，此時的量化失真可較小；反之，Δ大時，量化失真將增大，而過載失真就減少。過載失真與信號的斜率有關(guān)，斜率越大，越容易出現(xiàn)過載。下面討論量化誤差對系統(tǒng)的影響。

由式(9－72)可知，線性預(yù)測器的響應(yīng)為（9－77）其Z變換為（9－78）可見，線性預(yù)測器的響應(yīng)為（9－79）式中：aj——第j項(xiàng)加權(quán)系數(shù)；k——預(yù)測階次。由圖9－5中接收部分的框圖可知：（9－80）故（9－81）式(9－81)表明,線性預(yù)測器為一全極點(diǎn)濾波器，故又稱為全極點(diǎn)模型。DPCM預(yù)測誤差信號為（9－82）經(jīng)過量化后為：(9－83)式中：qi——量化誤差(或量化噪聲)。在接收端恢復(fù)后的重建信號為(無傳輸差錯時)（9－84）將式(9－82)、(9－83)代入式(9－84)得：（9－85）

9.5變換編碼

X＝PU(9－86)由正交性ATA＝A－1A＝I，則有U＝P－l

X＝PTX

(9－87)式中：P—實(shí)正交變換矩陣；

PT—矩陣P的轉(zhuǎn)置矩陣；

P－l—矩陣P的逆矩陣；

I—單位矩陣。如果經(jīng)正交變換后只能傳送M（M<n）個樣值，而將余下的n-M個較小的樣值丟棄。這時接收端恢復(fù)的信號為(9－88)式中：如何選擇正交矩陣P，使M值較小，且使被丟棄的n－M個取值足夠地小，以至于既能得到最大的信源壓縮率，同時又使丟棄掉n－M個取值以后，所產(chǎn)生的誤差不超過允許的失真范圍是我們所關(guān)心的問題。因此，正交變換的主要問題可歸結(jié)為：在一定的誤差準(zhǔn)則下，尋找最佳或準(zhǔn)最佳的正交變換，以達(dá)到最大限度地消除原消息源之間的相關(guān)性。正交變換為什么能解除相關(guān)性呢？下面討論這個問題。由矩陣代數(shù)理論可知：對于任意兩個隨機(jī)變量x、y間的相關(guān)性可以用x、y的協(xié)方差(相關(guān)距)來表示。一個信源變量U的各分量間的相關(guān)性用信源各分量間協(xié)方差矩陣ΦU表示，其定義為（9－89）可以證明U的協(xié)方差矩陣ΦU是一個實(shí)對稱矩陣，它能反映變量U各分量間的相關(guān)性。若各分量之間互不相關(guān)，則協(xié)方差矩陣ΦＵ只有主對角線上有非零元素。主對角線上的非零元素代表各分量間的方差，即自相關(guān)性；非對角線上的元素表示各分量之間的協(xié)方差，即互相關(guān)性。

由矩陣代數(shù)可知，對于一個實(shí)對稱矩陣A(A＝AT的矩陣)，必存在一個正交矩陣P，使得：（9－90）式中：λ1λ2…λn——實(shí)對稱矩陣A的n個特征根。信源U經(jīng)正交變換后的輸出X協(xié)方差矩陣可定義為（9－91)式中：ΦX——信源U正交變換后的信號X的協(xié)方差矩陣；X——信源U經(jīng)正交變換后的矢量；P——正交變換矩陣；PT——正交變換矩陣P的轉(zhuǎn)置矩陣。為了達(dá)到信源壓縮的目的，希望通過矩陣P的正交變換后，ΦX只保留主對角線上的部分自相關(guān)值，即希望其值隨i與j值增大而迅速減小，從而只需取M（M<n）個數(shù)值。同時希望各互相關(guān)分量均為0,即最大限度地消除原來信源間的相關(guān)性。這也就是研究正交變換的主要指導(dǎo)思想。下面給出最佳的正交變換和準(zhǔn)最佳的正交變換的概念。所謂最佳，是指在一定的條件（即準(zhǔn)則）下的最佳，而這些準(zhǔn)則既有客觀的，也有主觀的。這里是按照客觀統(tǒng)計上的最小均方誤差準(zhǔn)則(MMSE)尋求最佳的正交變換。最佳變換是指變換后的協(xié)方差矩陣ΦX為理想對角線矩陣,這表明,經(jīng)正交交換后完全消除了互相關(guān)性。所謂準(zhǔn)最佳變換，是指變換后的協(xié)方差矩陣ΦX是近似對角形矩陣。由矩陣代數(shù)的相似變換理論可知，任何矩陣都可相似于約旦(Jordan)標(biāo)準(zhǔn)型所構(gòu)成的矩陣。而約旦標(biāo)準(zhǔn)型就是準(zhǔn)對角形矩陣，即矩陣的主對角線上均為特征值λi(i＝1，2，…，n)，而在對角線下僅有若干個不為0的1值。而所謂相似變換，是指總能找到一非奇異矩陣P使得P－1AP＝B，這時稱A與B相似，如果P為正交矩陣，則有P－1AP＝PTAP