第五章信源編碼

目的：提高通信系統(tǒng)有效性，實現(xiàn)信源與通信系統(tǒng)間的統(tǒng)計匹配。

§５－１無失真信源編碼

一〕首先，我們研究離散、無失真、無記憶信源編碼的一般模型：假設不考慮信源統(tǒng)計特性：應滿足：相互矛盾！由 ----①

〔一〕離散、無失真、無記憶信源編碼的一般模型〔續(xù)〕結論：①當n=m時，K≥L不有效。②當K=L時，m≥n，亦不滿足有效性。解決方法：引入信源統(tǒng)計特性。考慮信源統(tǒng)計特性：即無需對全部組合的n的L次方種信息一一編碼，而僅需對其中少數大概率事件集合中元素進行編碼即可。這時，我們可以修改①式為：K/L≥H(U)/logm----②即考慮信源不等概率，而碼字為等概率，這就是等長碼的仙農無失真信源編碼定理：對離散，無記憶、平穩(wěn)、遍歷信源其符號序列：U=(U1,U2…..UL)，可用K個符號C=(C1,C2….Ck)進行等長編碼，對任意ε>0,δ>0，只要滿足：(K/L)logm≥H(U)+ε----③那么當L足夠大時，可使譯碼過失小于δ，反之，當(K/L)logm≤H(U)-2ε----④時，譯碼一定出錯。這就是等長碼信源編碼定理。〔一〕離散、無失真、無記憶信源編碼的一般模型〔續(xù)〕〔一〕離散、無失真、無記憶信源編碼的一般模型〔續(xù)〕定理證明,主要引用了序列信源中的隨機序列的漸近等同分割A.E.P特性.所謂A.E.P是指任何一個離散隨機序列信源當序列長度Ｌ→∝時,信源序列會產生兩極分化.大概率事件集合與小概率事件集合,即nL=∪對于有性質:①

②

(信源熵)(大概率事件熵)③

(等概率)對于有性質:〔一〕離散、無失真、無記憶信源編碼的一般模型〔續(xù)〕由此可見，信源編碼只需對信源中少數落入典型大概率事件的集合的符號進行編碼即可。而對大多數屬于非典型小概率事件集合中的信源符號無需編碼，且。由A.P.E推出的輔助不等式：

選典型序列中個u編碼，即

為此,有以下變長碼熵匹配編碼定理形式:其次，再討論變長碼，這時公式②可進一步修改為:

〔一〕離散、無失真、無記憶信源編碼的一般模型〔續(xù)〕-------⑤

對于二進制,可進一步簡化為：

-------⑥故稱它為熵匹配編碼。它就是變長碼信源編碼定理。可見，上述無失真信源編碼定理，不僅是存在性定理，而且是構造性定理。

例：設有一簡單離散信源：L=1,n=4對其進行近似于無失真的等長編碼，假設要求其編碼效率為95%，過失率低于10-6，試求符號聯(lián)合編碼長度L=？解：,σ2=0.6875bit2由編碼效率：

即：可見,需要100萬個信源符號聯(lián)合編碼,才能到達上述要求,這顯然是不現(xiàn)實的.下面,假設進行變長編碼又如何呢?再由:變長碼010110111

可見，假設采用變長編碼，逐位〔L=1〕即可到達100%效率，當然這里僅是一個特例，不過它已足以說明變長碼的優(yōu)越性。如何譯碼？有兩類方法：①加標志信息②尋找內在規(guī)律下面，我們給出幾種類型的信源編碼：其中編碼Ⅰ為等長碼，碼長K=2，但與pi不匹配，編碼Ⅱ至Ⅴ為變長碼，但是編碼Ⅱ的U1和U2均編為“0〞，編碼不單義〔奇異〕不能用；信源概率pi編碼Ⅰ編碼Ⅱ編碼Ⅲ編碼Ⅳ編碼ⅤU11/2000000U21/401011001U31/810100110011U41/81110111110111編碼

Ⅲ，發(fā)（編碼）單義，但是收（譯碼）不單義，比如收到“00”可能譯為亦不能用。編碼Ⅳ與Ⅴ，收、發(fā)均滿足單義，故可用，但是兩者是有差別的。雖然都是唯一可譯碼，但是編碼Ⅳ是一類實時唯一可譯碼，又稱為異前置碼或非延長碼。

所謂異前置是指某一碼組的后面向前面看：比方u4=111，被采用后，其前面的任意組合比方11，或1均不能再采用；所謂非延長碼，那么是某一碼組的前面向后面看：比方u1=0，被采用后，那么從0以后的任何延長出去組合，比方00、01、001等均不能再用。它是最正確變長碼。編碼Ⅴ也是滿足唯一可譯性，但不滿足異前置或非延長特性，譯碼時，需要延時判決，所以它不是實時可譯碼。比方收到“0〞不立即判決，而是延遲一位，根據收到的第二位在判決第一位假設為“00〞那么判第一位為0，即u1；假設為“01〞仍不能判，再觀察第三位，假設為“010〞，那么判“01〞為u2，假設為“011〞再觀察第四位，假設為“0110〞判為“011〞為u3，假設為“0111〞判為u4。下面，進一步研究實時唯一可譯碼的碼字可別離條件，它可引用很直觀的“碼樹〞概念來說明：將變長碼與碼樹建立“一一對應〞關系：樹根碼字起點樹枝數碼的進制數節(jié)點碼字或碼字的一局部終止節(jié)點碼字節(jié)數碼長非滿樹變長碼滿樹等長碼下面，我們尋找一種與上述“樹圖〞等效的解析式表達式----Kraft不等式。分析起來特別對含有很多符號種類的復雜信源更方便。定理：長度為Ki〔i=1,2,…,n〕的m進制異前置碼存在的充要條件為：----⑦。證明，下面僅給出必要性證明，充分性見書，若設碼樹共有K節(jié)，則總碼枝數為mk個。若某個長度為Ki的碼枝被選用，則自該支第Ki節(jié)點以后所有碼枝不能再選用，即有碼枝不能再選用。由于Ki中i是任意的（i=1,2,…,n），所以全樹中不能再選用的總碼枝數應為：

，顯然其值一定要小于全樹總碼枝數mk，即有

編碼規(guī)那么：1)

將信源消息U按概率大小排序〔由大至小〕。2)從最小兩個概率開始編碼，并賦予一定規(guī)那么，如下支路小概率為“1〞，上支路大概率為“0〞。假設兩支路概率相等，仍為下支為“1〞上支為“0〞。3)將已編碼兩支路概率合并，重新排隊，編碼。4)重復步驟3〕直至合并概率歸一時為止。5)從概率歸一端沿樹圖路線逆行至對應消息編碼，如U3為“110〞。例2〔續(xù)〕例三〔續(xù)〕可見，編成的碼C和C’不一樣，這說明哈夫曼編碼并不唯一，這是由于哈夫曼編碼是與信源統(tǒng)計特性相匹配的編碼，而不是某個信源固定特性相匹配，不唯一性是明顯的，但是只要在編碼和譯碼過程中遵守同一規(guī)則，譯碼是唯一的。雖然C和C’不一樣，但是兩者都是哈夫曼編碼，并且碼長相等。

Kc’=0.4×1+0.2×2+0.2×3+2×0.1×4=2.2Kc=0.4×2+0.2×2×2+0.1×3×2=2.2但是，若從二階矩來看，即方差來看，C’的方差大，C的方差小，所以C優(yōu)于C’例三〔續(xù)〕下面討論哈夫曼編碼應用中的一些問題：1)首先討論誤差擴散：哈夫曼編碼是一種無失真信源最正確編碼，但是在實際信道中是有失真的。噪聲的引入必然要破壞長碼結構，而且是變長碼，錯誤不但影響受干擾位，還要進一步擴散。目前對擴散還沒有很有效的方法，工程上克服方法有兩種：一是限制哈夫曼碼僅能應用于優(yōu)質信道〔<=10-6〕以限制擴散的可能性；二是采用定期清洗，防止擴散區(qū)域增大。但是它是靠犧牲有效性換取的。2)其次是速率匹配問題：由于絕大多數信源是不等概率的，由它編成的碼長度與速率是可變的。然而實際信道那么要求其輸入端速率是固定的。所以信源與信道之間還存在一個速率匹配問題。在工程上解決這一問題的方法是在兩者之間加一個類似與水庫的緩存器，它變速入，恒速出，以解決兩者速率的匹配。3)第三是與信源統(tǒng)計特性匹配的問題。其中：〔1〕、小消息〔符號〕集信源不易匹配可采用信源消息集不斷擴展的方法來解決，但是太復雜。〔2〕、信源統(tǒng)計特性未知時，怎么辦？可采用所謂通用編碼的方法來解決。上一節(jié)我們利用樹圖的理論尋找出一類唯一可譯的變長碼的編譯碼方法。即：〔同構〕樹的生成結構規(guī)律唯一可譯碼變長〔樹圖理論〕〔一一對應〕編、譯碼方法這一節(jié)中我們利用數學中最簡單的算術規(guī)律來構造一類無失真的信源編碼。 〔同構〕算術規(guī)律 非分組的信源編碼〔一一對應〕算術編碼

下面，首先從一個PCM編碼例子入手：

000→0×20+0×21+0×22→0→0→0×2–1+0×2-2+0×2-3001→1×20+0×21+0×22→1→1/8→0×2–1+0×2–2+1×2–3010→0×20+1×21+0×22→2→2/8→0×2–1+1×2–2+0×2–3011→1×20+1×21+0×22→3→3/8→0×2–1+1×2–2+1×2–3100→0×20+0×21+1×22→4→4/8→1×2–1+0×2–2+0×2–3101→1×20+0×21+1×22→5→5/8→1×2–1+0×2–2+1×2–3110→0×20+1×21+1×22→6→6/8→1×2–1+1×2–2+0×2–3111→1×20+1×21+1×22→7→7/8→1×2–1+1×2–2+1×2-3PCM碼編碼公式對應量化層歸一化編碼公式上面例子是一個簡單的三位PCM的例子其編碼可表示為：〔簡單算術表達式〕⑧

三位碼共有八層:

……

可見，這時信源編碼過程就可以看作是上述對應二進制小數作移位相加的過程。故稱它為算術編碼。

仔細分析，上述例子僅是一個特例，因為它沒有考慮信源的統(tǒng)計特性，〔它認為信源是遵從等概率分布的〕所以編出的碼字是等長碼，而對應的算術運算那么是簡單的整數項相加。〔即Ki為整數〕。為了解決對一般的具有統(tǒng)計特性的信源的算術編碼問題，需要將上述算術編碼方式進一步拓廣，并要解決信源統(tǒng)計特性與編出的碼字相匹配。其中最關鍵的是要將算術編碼與信源的符號概率及累積概率建立一一對應關系。算術編碼就是基于這一思路。不過，在引入統(tǒng)計特性后的算術編碼中，每次移位的位數可以是非整數〔精度有限的有理數〕，正是由于這種非整數的引入使算數編碼變成了非分組碼。更確切地說，在每步編碼運算中除了實際移動的某一整數位以外，還以內部狀態(tài)形式保存了應該移動的“分數〞位，并將其累積到下一步編碼運算中。這樣，只要非整數的精度足夠高，那么就可以與信源消息匹配到任意良好的程度。下面，從一個單消息〔符號〕信源入手，簡述算術編碼原理及編碼方程的建立：設信源序列為:S=S1S2…Si…其中Si∈{1,2,…,j,…,N},即有N種類型,下面,首先將信源符號按對應概率大小排隊:S1S2…Sj…SN即:對應累計概率=由于信源是由單個符號組成并相互獨立,假設設信源序列為：S=S1S3S2S3=S’S3P(S)=p(S1)+p(S1)p(S3)+p(S1)p(S3)p(S2)+p(S1)p(S3)p(S2)p(S3)=p(S1S2S3)+p(S1)p(S3)p(S2)p(S3)=p(S’)+p(S’)p(S3)---------⑨其中p(S’)=p(S1)p(S3)p(S2)=[p(S1)p(S3)]·p(S2)推廣之:p(S)=[p(S1)p(S3)p(S2)]·p(S3)=p(S’)·p(S3)----------⑩這樣，將一定精度數值作為序列的算術編碼，完全可類似于上述歸一化分層的整數算術編碼。在數學上看，它實質上是一個分割單位區(qū)間的過程。完成它必須兩個遞推過程：一個代表碼字C(·),另一個代表狀態(tài)空間A(·).假設采用累積概率Ps表示碼字C(s),符號概率P(s)表示狀態(tài)區(qū)間A(s),由公式⑨⑩可求得：其中sx表示s的后續(xù)〔增長〕序列。公式⑾的遞推公式是算術編碼的根底。----------------⑾

例：假設有一單消息〔符號〕信源，含四種符號：a、b、c、d，構成一序列S=abda且：。試說明算術編碼及其具體編、譯碼過程。解：假設起始狀態(tài)為空序列Ф，且令A(Ф)=1,C(Ф)=0下面，首先給出以下符號，符號概率pi，累積概率Pj如下：由上述概率表與公式⑾，可計算出以下一系列數值：符號符號概率pi符號累積概率Pjabcd0.100(1/2)0.010(1/4)0.001(1/8)0.001(1/8)0.0000.1000.1100.111C(Φa)=C(Φ)+A(Φ)Pa=0+1×0=0A(Φa)=A(Φ)pa=1×0.1=0.1C(ab)=C(a)+A(a)Pb=0+0.1×0.1=0.01A(ab)=A(a)pb=0.1×0.01=0.001C(abd)=C(ab)+A(ab)Pd=0.01+0.001×0.111=0.010111A(abd)=A(ab)pd=0.001×0.001=0.000001C(abda)=C(abd)+A(abd)Pa=0.010111+0.00001×0=0.010111A(abda)=A(abd)pa=0.000001×0.1=0.0000001上面，我們給出了整個編碼過程，實際上它可以看作是對以下單位區(qū)間的劃分過程：算術編碼的譯碼過程如下：根據編碼后的數值大小比較來進行，即判斷碼字C〔s〕落在哪一個區(qū)間就可以得出一個相應的符號序列。具體步驟如下：1.

C〔abda〕=0.010111<0.1

可譯出第一符號為a；2.

去掉被乘概率加權因子：C〔abda〕×2=0.010111×10=0.10111在[0.1，0.11]

間，第二個符號譯為b；3.

去掉累積概率后再去掉被乘加權因子：0.10111-0.1=0.001110.00111×4=0.00111×100=0.111在[0.111，1]之間，第三個符號譯為d；4．同上0.111-0.111=0.000.00×8=0.00×1000=0.00在[0，0.1]之間，第四個符號譯為a。綜上所述，譯碼后的總輸出為：S*=abda=S〔發(fā)送的原序列〕在實際應用時，信源不是簡單的單消息〔符號〕信源，而是符號序列信源，這時上述遞推公式⑾應修改為：并設所有序列從空序列開始，即A（）=1，C（）=L（）=0若x表示子序列S后面的待編碼符號。若P（x/S）<1/2稱為小概率符號，且記x為l，否則記x=h

公式中L表示碼長,[]表示截短后的有限精度.矢量量化是一維標量量化的拓廣,是對多個樣值進行的聯(lián)合量化.標量量化是對逐個樣點值進行的量化,而矢量量化那么是對每K個樣點值為一組進行的多維聯(lián)合量化處理.它在數學上可看作K維空間中的映射:矢量量化編碼

其中u為K維空間(歐氏)中的一個連續(xù)矢量,ul為K維空間(歐氏)中的一個離散量化矢量.對于每個l，在K維空間中有一個區(qū)域Cl，它作為K維空間劃分的一個子空間.且當u∈Cl就判別它為ul,人們稱這種分割矢量空間的方法為Voroni(胞腔)子空間法。可見，矢量量化可以理解為K維歐氏空間Rk中的一種映射變換。它將Rk中的連續(xù)矢量u變換成離散的量化矢量ul，且稱量化矢量ul為碼本和重建碼本，而l=1,2,……,L，L那么表示碼本的尺寸〔大小〕。Log2L為碼本信息量，即碼本的二進制碼元數，對于矢量量化：可以實現(xiàn)，這點在一維標量量化時是不可能到達的，主要原因是由于矢量量化充分利用了信源樣點間統(tǒng)計關聯(lián)特性。顯然有:

⒀為了便于理解，可將上述矢量量化過程按以下圖形分解為編、譯碼兩個子過程如下：ulullu編碼器（u）理想信道譯碼器（l）l重建碼本碼本圖中的碼本是按照一定的失真度量準那么，通過事先進行大量的訓練而建立，并含有所有可能量化矢量值ul，l=1,2……L，這時，信道既不直接傳送Ｋ維連續(xù)樣值ｕ，也不傳送離化量化矢量ｕl，傳送的是在碼本中挑選失真最小的那個量化矢量的編號值l，接收端，由l通過譯碼器在重建碼本中再挑選失真最小量化矢量ｕl作為恢復矢量值。即：QK：ｕl＝β(l)＝β[(ｕ)] ⒁在某種失真準那么下，可以認為：β·α＝１那么：ｕl＝β[α(u)]＝ｕ顯然當K＝１時，即為簡單的標量量化。⒂

1)

矢量度量準那么的選取2)

多維空間的劃分3)

最正確量化器的設計4)

算法研究矢量量化中的幾個主要問題是：下面，我們給出一類典型矢量量化實現(xiàn)方案：

碼本序號l訓練數據群聚迭代建立碼本碼本矢量量化編碼輸入連續(xù)矢量u

ul可見，矢量量化器發(fā)送端主要包括兩局部：碼本設計與矢量量化編碼。碼本設計需要大量的反復的輸入訓練數據進行群聚迭代設計，反復計算質心，因此要消耗大量的時間，然而碼本設計并不要求實時，它可以事先預制。矢量量化編碼那么嚴格要求實時實現(xiàn)。因此在量化器中的運算量以及決定它的算法，就變得極為關鍵，這就是說，矢量量化器能否實際應用關鍵在于算法。近些年來算法研究進展很大，各種類型最正確全搜索快速算法以及準最正確的各類快速算法不斷提出，同時，由于大規(guī)模集成電路技術的飛速開展，促使矢量量化技術已逐步走向實用化。它是一類有記憶信源的限失真編碼。有記憶信源最主要的是解除信源的相關性，而預測編碼主要是從時域來解除相關性，壓縮信息率。預測編碼

〈一〉預測編碼的根本原理信源輸出預測器量化編碼輸出它不直接對信源輸出ui進行量化編碼，而是對其差值:進行量化編碼。其中為預測值。

由信息論：

差值熵：

由信源熵匹配編碼有：(16)

其中表示預測前信源編碼平均碼長其中表示預測后信源編碼平均碼長從概率觀點看，預測可理解為：

由于信息熵是概率分布的泛函數，預測前，信源分布越不均勻，熵越大；預測后，預測越準確，分布越集中，熵值就越小。即。通過預測后，信源數據壓縮的倍數就越大。實現(xiàn)預測編碼要進一步研究如下三個問題：１〕

預測函數的選取；２〕

預測誤差準那么的選取；３〕

預測器輸入數據源的選取。第２〕個問題決定預測器質量的標準，第１〕、３〕兩個問題那么主要決定預測質量的好壞。下面，我們首先討論預測函數的選取：

在工程上一般是采用容易實現(xiàn)的線性預測，這時：可見，當預測函數f確定為線性函數以后，預測精度主要決定于K值大小：K越大，預測越準確，但設備也越復雜；

K越小，預測越不準確，設備也就越簡化。

其次，討論預測誤差準那么的選取:目前大致有以下四種類型：MMSE〔最小均方誤差〕準那么；PSEM〔功率包絡匹配〕準那么；PCIV〔預測系數不變性〕準那么；ME〔最大誤差〕準那么。其中最常用的是MMSE準那么，PCIV主要特點是與輸入信號統(tǒng)計特性無關，它可對多種混合信號進行有效預測。而ME準那么那么主要用于遙測數據壓縮。最后,討論預測器輸入數據流的選取,它可以劃分為三類:<二>預測編碼的根本類型1〕△PCM型ui-1ui-2…ui-Kα1α2αk…量化編碼器DPCM中預測系數的計算線性預測值為，為過去p個樣值的線性組合，為預測系數假設選擇均方誤差準那么假設信源輸出廣義平穩(wěn)r(m)為樣值un的相關函數，上式對ai求偏導r(m)可通過估算將r(m)代入，可得ai求預測系數的線性方程稱作正態(tài)方程，Yule－Walker方程。Levinson和Durbin提出一種算法能有效的解上述方程。Levinson-Durbin算法Levinson-Durbin算法是一種用來確定線性方程組解的階遞歸算法。其中是一個階Toeplitz矩陣。是預測器系數向量，可表示為是一個p維向量，其元素為對于一階()預測器，我們得解一階預測器的剩余均方誤差(MSE)為一般的，可以用m-1階預測器的系數來表示m階預測器系數的解。于是，把表示為兩個向量之和，即式中，向量和標量待定。于是，還可以表示為式中，剛好是反序的向量現(xiàn)在由上式可以得到兩個方程。第一個方程為如下矩陣方程從而上式可以簡化為這個方程的解為剛好是反序。從而，上式的解就是反序的乘以，即(1)由前式得到的第二個方程為如下標量方程利用前式(1)，可從上式消去。結果的方程給出，即式中是剩余MSE，由下式確定用前式(1)代替最小MSE也可以遞歸計算，于是得到如下遞歸關系及在上式中利用遞歸關系，得到上式中方括號內的項就是前式中的分子，因此它可簡化為

量化…線性預測器線性預測器uiyi

xi

ei

這是一類最簡單的線性預測器。其預測器輸入直接來自信源輸出，預測函數為線性加權和，其預測精度主要決定于預測項數K。其主要缺點是量化噪聲較大。

1〕△PCM型〔續(xù)〕2〕DPCM型：uieixi量化器線性預測器線性預測器yiDPCM與△PCM比較，不同點有：①線性預測器的輸入數據源來自輸出反響端②對于量化器而言，△PCM是開環(huán)型而DPCM是閉環(huán)型。可利用反響環(huán)進一步壓低量化誤差。從而進一步提高DPCM的預測性能。<二>預測編碼的根本類型〔續(xù)〕--延時延時濾波DPCM的特例ΔM:

2〕DPCM型〔續(xù)〕若將量化等級定為2,即差值為正時,用”1”代表;差值為負時,用”0”代表;而每個差值只需1比特,這時DPCM即為ΔM，又稱它為增量調制.為了減少量化誤差,一般要增加取樣頻率,不能再來用常用的最高頻率的2倍，即

>2fm.在收端，譯碼是編碼的反變換，即規(guī)定一個增量Δ值，當收到一個“1”則在前一個值中加一個Δ，收到一個“0”，則減去一個Δ值。2〕DPCM型〔續(xù)〕3〕噪聲反響編碼(NFC)<二>預測編碼的根本類型〔續(xù)〕NFC是吸取△PCM與DPCM的優(yōu)點，即在△PCM結構簡單的根底上,改進其量化噪聲大的缺點，將量化器設計在另外增加的一個反響環(huán)內,以到達進一步壓減量化誤差的目標。這一點上類似于DPCM.可見NFC是△PCM與DPCM的混合改進型.<二>預測編碼的根本類型〔續(xù)〕4)預測誤差門限型(非線形)

設信源輸出序列為:若僅采用前一位作為后一樣值的預測值,則預測誤差若,不傳送;

若,傳送.4)預測誤差門限型(非線形)〔續(xù)〕其中是允許誤差的門限值,即可接受的最大誤差,在上述圖形中雖然有，前四個應傳送，不傳送。若選擇的預測值不僅僅是前一位，而是前n位的線性加權和，則可構成高階預測誤差門限型，其原理同上，實現(xiàn)方框圖如下：

顯然這一類型中線性預測器與前三類是一致的，但是由于引入了非線性門限比較器，所以它實質上是一類非線性預測器。<二>預測編碼的根本類型〔續(xù)〕下面我們給出四種類型中最常用的一種DPCM的性能分析：線性預測可表示為：

其Z變換為：可見線性預測器的響應為：

式中αj為第i項加權系數，N為預測階次。由DPCM接收部分框圖。可求得：故：

<二>預測編碼的根本類型〔續(xù)〕可見，線性預測器為一全極點濾波器。故又稱為全極點模型。下面再分析一下DPCM的幾個主要關系式：

預測誤差：經量化后：其中qi為量化噪聲引入的誤差。經無過失傳輸后接受端恢復后的重建信號為：可見，進一步性能分析可參見教材。

變換編碼是從廣域頻域〔或空域〕解除信源相關性的一種有效的手段。主要數學工具是正交和準正交變換。變換編碼下面，首先從一維信源輸出開始分析：設信源輸出：，變換后輸出：則有：由正交性有：如果，通過正交變換只傳送M<ｎ個樣值，而將ｎ－Ｍ個較小樣值丟棄。于是有：這時接收端恢復的信號為：

變換編碼〔續(xù)〕這里，所以問題可以歸結為如何選擇正交矩陣Ａ，使經正交變換后Ｍ值較小，且被丟棄的ｎ－Ｍ個值是足夠小的。為了更清晰，我們進一步引入二維分析：

其中為的協(xié)方差矩陣。為的數學期望。為ｘ的協(xié)方差。則：

變換編碼〔續(xù)〕可見經正交矩陣Ａ變換后，使信源的協(xié)方差矩陣變換成純對角線矩陣，且對角線上元素能按順序由大到小排列。下面，我們首先尋求正交變換|A|矩陣形式，即在最小均方誤差下準則MMSE下尋求最佳的正交變換。即:

變換編碼〔續(xù)〕首先求最正確bi值：求得：此取bi為xi的數學期望值，其次再求最佳ai值：

求得：或

變換編碼〔續(xù)〕最后求得：

,其中

此為一理想對角線矩陣，它完全消除了信源的相關性，稱它為Karhunan-loeve(K-L)變換，這時,最小均方誤差值為:最小項.變換編碼〔續(xù)〕上述最正確的K-L變換實際上很少應用而僅將它作為理論上最優(yōu)值得一個參數標準,其原因有1.最正確A矩陣顯然與信源統(tǒng)計特性φ密切相關,不同的φ值應有不同的最正確A矩陣,這顯然是不現(xiàn)實的.2.K-L變換目前尚沒找到相應的快速算法.正因為實現(xiàn)最正確不現(xiàn)實,因此人們將眼光轉向準最正確變換,何謂準最正確變換并沒有確切的定義,而只是指能找到一類在數學上經線行代數中相似變換后的Jordan標準型.即:變換編碼〔續(xù)〕在上,下對角線區(qū)域內僅會有少數不為0得元素1.目前已找到一批滿足上述特性的準最正確變換(不唯一).大致可以劃分為兩類：變換編碼〔續(xù)〕可見，由線性代數理論，由相似變換，總能找到一非奇異矩陣A，使，并稱與相似，同時由于變換后的Jordan型無確切定義，因此可以找到一批滿足上述標準最佳變換。

下面將分別介紹這些準最正確變換，設U為信源消息矩陣，X為經變換后的信號矩陣，在一般情況下有：原那么上，A與B可以是不同類型矩陣，實際上差不多都是同一類型、同一階次矩陣，即A=B。由于上述變換是隨機矩陣變換，所以通常給出其二階矩陣形式的協(xié)方差矩陣的等效形式：變換編碼〔續(xù)〕1〕離散付氏變換DFT:這里：其中下面討論不同形式A:變換編碼〔續(xù)〕變換編碼〔續(xù)〕變換編碼〔續(xù)〕例：以n=4DFT為例；假設顯然，它是一個非常好的準最正確變換，互相關均為零，自相關由大而小遞降型。但是，也可以看出，ADF與Φu密切相關，假設換一個Φu類型，就不會有這么好的結果。2〕離散沃爾什—哈德瑪變換WHT由于沃爾什—哈德瑪矩陣由許多類似之處,比方他們都是以1和-1為元素，其變換運算只有加減而沒有乘除，且兩類矩陣之間的關系是簡單的初等變換關系。所以我們將兩者歸為一類來研究。并首先從Hardmard矩陣開始：這里：

5〕離散余弦變換DCT：由于前面在付氏變換中引入了復數，帶來了運算上的不方便，DCT正是針對這一缺點而進行的改進。根據離散付氏變換的公式，只需將信源數據長度再擴張一倍，并保證對稱性即可求得DCT。DCT根據對稱性不同還可劃分為兩類，〔奇〕ODCT與〔偶〕EDCT，前者將數據擴展為2N-1并以M=0為中心點，兩側各N-1個；后者將數據擴展為2N，并以M=0與M=1之間為中心點。且：

以上各類離散準最正確變換編碼各具特色。如果僅從解除相關性的性能上看：KLT>DCT〔平穩(wěn)馬氏鏈〕>DFT>WHT>HrTST但是如果從復雜性,計算復雜度上來看,上述順序正好相反:HrT>WHT>DFT>DCT>KLTST通用編碼Huffman編碼能產生最優(yōu)信源編碼，但需要知道所有信源符號的發(fā)生概率。在有記憶離散信源情況下，那么Huffman編碼必須知道所有長度n≧2的所有信源符號組合的聯(lián)合概率。對于實際信源，聯(lián)合概率的計算復雜度非常高，結果Huffman編碼在許多實際的有記憶信源中往往無法實現(xiàn)。Lampel-Ziv(LZ)通用信源編碼與Huffman編碼不同，LZ編碼算法與信源統(tǒng)計特性無關，屬于通用信源編碼范疇，是一種將變長碼段映射為等長碼字的算法，編碼方法可以描述為：在LZ算法中，離散信源的輸出序列分解成長度可變的分組，稱為碼段(phrases)。每當信源輸出字符組在最后位置加上一個字符后與前面的已有碼段都不相同時，把它作為一種新的碼段引入。將這些碼段列入一個位置字典，用來記載已有碼段的位置。在對一個新的碼段編碼時，只要指出字典中現(xiàn)有碼段的位置，把新字符附在后面即可。LZ算法舉例：考慮二進制序列

按上述編碼方式序列可以分解為如下碼段：1,0,10,11,01,00,100,111,010,1000,011,001,110,101,10001,1011序列中的每一個碼段是前面某一個碼段加上一個新的信源輸出字符構成的。為了編碼，需要構造位置字典。字典位置

字典內容

碼字

100011000012001000000030011100001040100110001150101010010160110000010070111100001108100011101001LZ算法的字典LZ算法的字典(續(xù))910010100101010101010000111011101101101011121100001011011311011100100014111010100111151111100011010116101111101LZ算法的信源譯碼器是編碼的逆過程，根據碼字的特點，首先可以構造出編碼字典，然后對接收序列作相應的解碼。需要指出，上述例如中，將44位信源比特編碼成16個碼字，每個碼字5比特，總共是80位碼字。因此這種算法沒有提供任何數據壓縮。本例編碼效率低下的原因是由于所考慮的序列非常短。隨著序列長度的增加，LZ算法的效率越來越高，可以實現(xiàn)信源輸出序列的壓縮。如何選擇字典列表的總長度是LZ算法實際應用的重要問題。一般而言，無論表有多大，總有可能溢出。為了解決溢出問題，信源編譯碼器必須協(xié)調一致，將無用的碼段從各自的字典中刪除，在它們留下的位置上換上新的碼段。Ziv和Lampel證明，將LZ編碼應用于遍歷平穩(wěn)離散信源時，其壓縮比可以以概率1收斂于該信源的仙農信息熵。LZ編碼壓縮比可以到達信源熵率這一結論一方面說明LZ編碼的有效性，但也說明通用編碼不能做的比Huffman編碼更好。LZ算法已經廣泛應用于計算機文件的壓縮。Unix操作系統(tǒng)中的“compress〞、“uncompress〞以及Windows操作系統(tǒng)中的Winzip、Winrar等文件壓縮軟件中采用的算法就是LZ算法的不同變種。實用化與純理論上的要求之間存在著一定差異：首先：實際比理論要復雜，理論分析時往往認為信源平穩(wěn)遍歷的，是遵從某一個分布特征，……等等，實際上是辦不到的，最多是近似上大致滿足;其次：理論上追求是性能越優(yōu)良越好，追求最正確，實際上是要更側重可實現(xiàn)性，追求性能與可實現(xiàn)性之間的折衷，追求準最正確。第三：理論上往往分析各種單一最正確化方法與性能，實際上往往是實用主義，采用多種組合準最正確化。這一點，以后在圖像信源編碼中表達更明顯。實用型信源編碼

下面，我們分別討論三類代表性信源：1〕文件信源〔無失真信源編碼〕；2〕語音信源〔限失真信源編碼〕3〕圖像信源〔限失真信源編碼〕實用型信源編碼〔續(xù)〕1>文件傳真信源編碼：關于文件傳真的一些有關知識：（1）CCITT建議的文件傳真的兩種分辨率：A行分辨率：1728相素/行（即8樣點/mm），

列分辨率：3.85行/mm；B行分辨率：8樣點/mm，

列分辨率：7.7行/mm；

〔2〕我國標準：A行分辨率：8樣點/mm，列分辨率：4行/mm；B行分辨率：8樣點/mm，列分辨率：8行/mm；以上是對A4文件制定的〔210*297mm〕。如果采用各個像素按0.1直接編碼，一頁A4文件，分辨率為5樣點/mm〔行，列〕那么需傳送：,用2400b/s(或4800b/s)那么需11(5.5)分鐘，假設文件壓縮中僅能利用文件信源的一維概率特征，據測試有：pw=93.3%,pB=6.7%,1>文件信源編碼〔續(xù)〕那么H〔U〕=-pwlogpw–pBlogpB=-0.933log0.933–0.677log0.677=0.3546bit一維熵編碼理論壓縮比KO為：可見壓縮比不高。假設二維信元符號〔消息〕改成“0〞，“1〞游程，即連“0〞，連“1〞的游程為單元，那么可得1>文件信源編碼〔續(xù)〕由二進制〔m=2〕信源編碼定理，有對平均每個像素有：其中

1>文件信源編碼〔續(xù)〕假設定義：那么可求得：再定義：那么可求得：1>文件信源編碼〔續(xù)〕這時，黑、白游程混合編碼條件下，平均每個像素的信源編碼定理。（即像素熵編碼定理）最終可求得：理論上極限壓縮比為：對A4文件，中文七種樣張統(tǒng)計特性如下：

1>文件信源編碼〔續(xù)〕例：將無失真信源編碼理論用于編碼。目前第三類機采用的就是修正的哈夫曼碼或者是算術碼。修正主要有三點：1〕被編碼的消息〔符號〕不是簡單的“0〞和“1〞；而是“0〞串〔0游程〕“1〞串〔1游程〕的不同長度。2〕信源制定碼表的依據。不是實時的實際信源，而是采用8種〔7種〕典型樣張可測得的統(tǒng)計特性來近似代表實際信源的統(tǒng)計特性。3〕將對整個一維1728像素的統(tǒng)計特性碼表，在制定碼表的分解、簡化為兩類碼表的合成，即將黑白游程長度分解為：其中K為根本游程長度〔0~63位〕的整數倍，由它可構成一個構造碼表，而R其長度為0至63，稱為結尾碼，它是根本游程碼的碼表。1>文件信源編碼〔續(xù)〕下面舉一個例子說明：某一A4文件中一段特性如下：編碼前總碼長：

LW1=131LB1=4LW2=6LB2=65L=lW1+lB1+lW2+lB2=131+4+6+65=206位將它進行修正哈夫曼編碼〔MH〕，分別查黑〔B〕、白〔W〕游程4的結尾碼表，構造碼表有：lW1=131=2*64+3=128+3,查白游程構造碼表：128=>10010查白游程結尾碼表：3=>1000故經哈夫曼編碼后為：100101000共9位1>文件信源編碼〔續(xù)〕同理：lB1=4，查黑游程結尾碼表：4=>011〔3位〕lW2=6，查白游程結尾碼表：6=>1110〔4位〕lB2=65=64+1：64=>00000011111=>010Huffman碼：0000001111010〔13位〕Huffman編碼后總長為：9+3+4+13=29。實際壓縮比：所以上述截斷式實際編碼修正方法對信源統(tǒng)計特性影響不大。工程上可實用。

1>文件信源編碼〔續(xù)〕實際統(tǒng)計分析說明：對于A4文件，對中文七類樣張的統(tǒng)計平均壓縮比這一結論在前面已計算過。1>文件信源編碼〔續(xù)〕2>語音編碼

〔1〕混合編碼：以參量編碼為主，以波形編碼為輔。在滿足根本質量前提下，盡可能提高壓縮率。下面，我們首先從理論上來分析各類語音編碼的潛力。首先分析波形編碼：引用R(D)函數理論，假設語音近似遵從正態(tài)分布〔實際上為近似Gamma分布〕是一個滿足短時廣義平穩(wěn)的一階正態(tài)馬氏鏈。其相關矩陣為R(τ)=σ2ρ│τ│,其中σ2為方差,ρ為相關系數,在均方誤差保真度準那么下,由信息論可求得:R(D)=1/2log2σ2(1-ρ2)/D其中:σ2/D為信噪比,且波形編碼取樣點間的相關系數ρ≈0.96,那么可算得:信噪比(dB)35322825232017R(D)(bit)43.52.52.3421.51壓縮倍數k22.283.23.4245.382>語音編碼〔續(xù)〕〔1〕混合編碼〔續(xù)〕上述表格繪出的R(D)值是最保守的估計值,原因是:其一:正態(tài)分布R(D)值大于其他一切分布R(D)值,故語音實際分布的R(D)值大于上述R(D)估計值.其二:接收語音最終是人耳,計算中未算入人耳的主觀性能引入的R(D)值變化,故實際上R(D)還要求按照一般能進入公用移動網,大致要求其信噪比為24-25dB,從表中可查出壓縮倍數k≈3.5,再考慮上述兩個因素,一般可認為k≈4左右.其次,在分析參量編碼,由語音分析,可認為語音最基本組成單元為音素.例如英語為例：其音素大約有個，同時按照通常講話速率，每秒大約發(fā)出10個音素。這時英語語音信源給出的信息率為：

僅從可懂度看，它與目前PCM標準速率64kb/s相比，可求得壓縮比方下：〔1〕混合編碼〔續(xù)〕可見其潛力很大，目前實驗室聲碼器〔參量編碼〕已可做到600bit/s左右，尚相差7-8倍。實際上，除了保密通信以及一些特殊的軍事通信以外很少采用這類低質量的參量編碼〔聲碼器〕。目前，在移動通信等領域，已將信源編碼的焦點轉移至混合編碼的方向。自八十年代以來，CCITT與現(xiàn)在的ITU—T等國際組織制定了一系列混合編碼的標準如下：

標準編碼傳輸速率質量(mos)備注G711PCM64Kbit/s4.2

G722

64,56或48bit/s

G726ADPCM40,32,24,16Kbit/s4.1

G727

同上4.1

G728LD-CELP16Kbit/s4.1

G729CS-ACELP8Kbit/s4.1

寬帶語音編碼〔1〕混合編碼〔續(xù)〕標準編碼傳輸速率質量(mos)備注G723-1

6.3-5.3Kbit/s4-3.6

GSM-SRRPELD13Kbit/s3.6

GSM-ER

13Kbit/s4

IS-96(Ⅱ)

13Kbit/s4.1

IS-641

8Kbit/s4

IS-54

8Kbit/s3.6

IS-96(Ⅰ)

8Kbit/s3.4

GSM-HR

6.5Kbit/s3.6

FS-1016

4.8Kbit/s3.2

FS-1015

2.4Kbit/s2.4

用于多媒體低比特率〔1〕混合編碼〔續(xù)〕決定混合編碼的主要技術指標：混合編碼的綜合性能=f(比特率、質量、時延、復雜度)下面分別討論這四個指標：〔1〕比特率〔b/s〕：數量指標，取決于信源的壓縮率。比特率越低，一般質量也會相應降低，為了補救質量往往又可以采用提高復雜度〔硬、軟件〕，但是他又會帶來處理時延的增大。因此要考慮綜合優(yōu)化。降低比特率另一措施是將固定速率改變?yōu)榭勺兯俾蔍S—95中就采用了基于不同背景噪聲電平的1、1/2、1/4、1/8四類不同語音速率。這樣可以大大降傳送語音的平均速率。〔1〕混合編碼〔續(xù)〕〔2〕

質量：目前語音質量的評估方法是采用CCITT建議的5級評分的“平均評價得分MOS“方法，4-5分列為高質量可達參加公用網要求；3-4分為根本達標，一般可入移動網要求；3分以下為不合格。評分測試條件：無背景噪聲，無傳輸過失、無模擬轉接與二次編碼。顯然這些條件過于理想化。〔3〕時延：語音為實時通信系統(tǒng)對時延很敏感，時延主要包括：算法時延、處理時延和傳輸時延。三類時延之和稱為單向系統(tǒng)時延，如果無回波，它最大允許值為400ms，最好在200ms以下，又回波，僅允許25ms。〔1〕混合編碼〔續(xù)〕〔4〕復雜度：語音編碼通常是采用DSP來實現(xiàn)的。這些芯片往往可采用每秒計算百萬條信令的速度〔mips〕，隨機存儲器〔RAM〕，和只讀存儲器〔ROM〕來描述。目前一般將小于15mips的語音編碼為低復雜度編碼，而將大于30mips的語音編碼為高復雜度編碼。在一個芯片上裝有越多的RAM和ROM，芯片價格就越高，體積就越大，所以復雜度越高，性能越好，但同時受到本錢，功耗，時延等因素制約。〔1〕混合編碼〔續(xù)〕以下表格給出這些年來，ITU建議的四個標準：G729，G729A以及兩類G723—1的四大指標量級：

G729G729-AG723-1G723-1比特率(kb/s)886.35.3話音質量(MOS得分)4.14.14.13.6幀長(ms)10101030子幀長(ms)557.57.5算法延時(ms)151537.537.5復雜度MIPS(定點DSP)2010.514.616RAM(16bit字長)2.7k2k2.2k2.2k〔1〕混合編碼〔續(xù)〕ADPCM是在DPCM的根底上開展起來的。而DPCM前面已討論過。由于預測誤差的幅度變化范圍遠小于原始信號〔預測前〕幅度變化范圍，因此在相同量化噪聲條件下DPCM量化比特數要遠少于PCM。從而到達語音壓縮編碼的目的。ADPCM與DPCM相比，主要區(qū)別在于ADPCM中的量化囂和預測囂采用了自適應控制，同時在譯碼囂中多了一個同步編碼調整，其作用是為了在同步級連時不產生誤差積累。八十年代以來32kb/sADPCM已日趨成熟。它具有與PCM相近的質量。下面，給出G721ADPCM編、譯碼框圖：2>語音編碼〔續(xù)〕〔2〕波形編碼ADPCM根本原理〔2〕波形編碼ADPCM根本原理〔續(xù)〕<32kb/sADPCM編碼系統(tǒng)S>

<32kb/sADPCM譯碼系統(tǒng)S>

〔2〕波形編碼ADPCM根本原理〔續(xù)〕由圖可見，在編碼器中，輸入將八位非線性PCMc‘(n)變換成12位的線性碼X〔n〕，再由16電平自適應量化器將差值信號d〔n〕轉化成四位二進制碼c〔n〕，同時為了適應不同的輸入信號采用了自適應參數來控制量化階距大小，它是由定標因子自適應和自適應速度控制兩局部組成。譯碼系統(tǒng)中的大局部與編碼器電路相同。主要是多了一個同步編碼調整電路，其作用是為了在同步級聯(lián)工作時，不產生誤差積累。〔2〕波形編碼ADPCM根本原理〔續(xù)〕參量編碼出發(fā)點是跟蹤波形產生過程，傳送好產生波形的參量，而不是波形本身。在收端通過發(fā)聲模型綜合成人工合成語言。固有時稱它為生碼器。語音產生模型如下：

2>語音編碼〔續(xù)〕〔3〕參量編碼的線性預測人工合成語音的15個主要參量：12個時變?yōu)V波器鼓勵參數：{α}i=1,2…..12;音調周期p〔基音周期〕；清濁音判決u/v；增益控制參量G；下面給出現(xiàn)線性預測LPC原理框圖如下：〔3〕參量編碼的線性預測〔續(xù)〕線性預測目前仍是混合編碼中聲碼器實現(xiàn)的主流，近些年來，以下三方面值得注意：1〕提高合成語音質量措施：采用余數鼓勵聲碼器RELP；多脈沖鼓勵聲碼器MELP；聲道參數模型的改善；2