配套課件-現(xiàn)代編碼技術

1、第1章通信與編碼概述 習題1. 通信系統(tǒng)的基本模型通信系統(tǒng)的基本模型如圖1.1所示，組成部分如下：信源：消息的發(fā)出者。信宿：消息的接收者。信源編碼器：消息的重組單元。信道編碼器：消息抗毀能力的構建單元。信道：消息的傳輸媒介，如電話機之間的電纜、無線電臺之間的電磁空間等。干擾源：毀壞傳輸信號的各種因素的等價體，可分為自然干擾源和人為干擾源兩類。如大氣的雷電干擾、電離層的擾動等屬于自然干擾；信號的轉發(fā)干擾等屬于人為干擾。信道譯碼器：消息的毀壞檢驗及恢復單元。信源譯碼器：消息的還原單元。發(fā)送端：從信源到信道前的各部分的總稱。接收端：從信道后到信宿的各部分的總稱。圖1.1通信系統(tǒng)的基本模型2. 信道模

2、型信道是發(fā)送端和接收端之間的連接通道，它可以等效為一個輸入端和一個輸出端的系統(tǒng)，如圖1.2所示。圖1.2信道簡化模型根據(jù)信道是否存在干擾，可將其分為無噪信道和有噪信道；根據(jù)傳輸信道是否連續(xù)，可將其分為離散信道和模擬信道；根據(jù)信道當前輸出與先前的輸入是否有關，可將其分為有記憶信道和無記憶信道；根據(jù)信道參數(shù)是否隨時間而變化，可將其分為恒參信道和隨參信道；此外，信道還可以分為二元信道和多元信道，對稱信道和非對稱信道，有損信道和無損信道等。1) 離散信道首先，我們來考慮信道的表示。假設發(fā)送端發(fā)射的信號都取自字符集：X=a1，a2，an由于信道中存在噪聲干擾、傳輸衰落、傳輸失真等因素，因此從發(fā)送端發(fā)出符

3、號ai，在接收端收到的未必是符號ai，甚至于還可能是X中不存在的符號。于是可以假設接收端接收的信號都屬于符號集：Y=b1，b2，bm對給定的信道進行大量的實驗后，經(jīng)統(tǒng)計可以發(fā)現(xiàn)：從發(fā)送端符號集中發(fā)送的符號ai以概率pij轉化為接收端符號集中的bj。為方便起見，概率pij常常表示為條件概率的形式，即pij=p(bj|ai)(i=1，2，n；j=1，2，m)這樣，用符號轉移概率pij就可以充分描述信道特性。為方便起見，引入信道轉移矩陣P，即常用的離散信道模型有以下幾種：(1) 二元對稱信道。在這種信道中，X=Y=0，1，并且p(1|0)=p(0|1)=p，即字符0和1發(fā)生錯傳的概率相同，信道轉移矩

4、陣P為二元對稱信道常常用狀態(tài)轉移圖來簡化表示，如圖1.3所示。圖1.3二元對稱信道(2) 二元刪除信道。在這種信道中，X=0，1，Y=0，1，Y中的字符表示0或1在傳輸中發(fā)生畸變而在接收端產生的一種發(fā)送端字符集中不存在的字符。在一個通信系統(tǒng)中，字符0和1分別代表正脈沖和負脈沖，發(fā)送端發(fā)送出正脈沖或負脈沖后，接收端收到的是受到干擾的畸變正脈沖或負脈沖，當畸變變化比較嚴重時，無法識別出是正脈沖還是負脈沖，這種接收信號就用來表示。對接收端是沒有意義的，應被刪除。畸變脈沖如圖1.4所示。圖1.4接收端收到的畸變脈沖(a) 畸變的正脈沖；(b) 畸變的負脈沖；(c) 畸變的脈沖二元刪除信道的信道轉移矩陣

5、P為其中，p(|0)=p，p(|1)=q。二元刪除信道常用圖1.5來表示。圖1.5二元刪除信道(3) 多元(N元)對稱信道。 多元(N元)對稱信道常用狀態(tài)轉移圖來簡化表示，如圖1.6所示。圖1.6多元(N元)對稱信道(4) 無記憶擴展信道。字符序列x經(jīng)信道后轉移成y的概率為 (1.1.1) 二維擴展信道的信道轉移矩陣P為(1.1.2) 2) 輸入離散、輸出連續(xù)的AWGN信道AWGN信道的全稱是加性高斯白噪聲(Additive White Gaussian Noise，AWGN)信道。輸入離散、輸出連續(xù)的AWGN信道具有輸入信號是離散的、輸出信號是連續(xù)的、信道受到的干擾服從高斯分布等特點，是通信

6、中最常用的信道模型之一。圖1.7是二元輸入離散、輸出連續(xù)的AWGN信道簡化模型。圖1.7二元輸入離散、輸出連續(xù)的AWGN信道簡化模型3. 編碼定理1) 香農第一定理(無失真壓縮編碼定理)定義1.1.1設離散信源空間X=a1，a2，an，離散變量ai(i=1，2，n)及對應變量的概率分布p(X)為式中，。稱lbp(ai)為離散變量ai的自信息量；稱為信源空間X的熵，單位為bit。(1.1.3a) 定義1.1.2設有離散空間X=a1，a2，an和Y= b1，b2，bm，稱為條件熵；稱為平均互信息量。其中，p(ai，bj)為離散變量ai與bj的聯(lián)合概率密度，p(ai|bj)為條件概率密度。(1.1.

7、3b) (1.1.3c) 定義1.1.3對信源輸出的一列符號序列按一定規(guī)則進行變換稱為編碼，變換后形成的新序列稱為碼字，碼字中的每一個元素稱為碼元，碼元所屬符號集稱為碼符號集，碼字中碼元的數(shù)量稱為碼長，全部碼字構成的集合稱為碼。如果q=2，則稱為二元碼；如果q2, 則稱為q元碼，這里q表示碼符號集中元素的個數(shù)。如果在一種碼的編譯碼過程中沒有信息損失，并且該碼在理想信道(無噪無信道損失)上傳輸后能不失真地恢復原消息，則稱該編碼為無失真編碼；如果在編譯碼過程中有控制地損失一些信息，則稱該編碼為限失真編碼。限失真編碼在通信中是十分重要的，如一張僅幾百兆的光盤能容納數(shù)十小時的視頻內容就源于該技術的重要

8、貢獻。定義1.1.4設有碼C=c1，c2，ci，p(ci)=pi ，碼字ci的長度為li，稱為碼C的平均碼長，單位為bit。定義1.1.5設信源符號集為X，并有q元碼C，稱為編碼效率。(1.1.5) (1.1.4) 引理1.1.1(概率匹配原則) 設無記憶信源X=0，1，2，q1且元素相互獨立和等出現(xiàn)概率，其上有一種碼C=ci|i=1，2，M，ci有長度li，發(fā)生概率為pi，若C是無損編碼且L(C)最小，那么(1.1.6) 證明由于0，1，2，q1是獨立等概的，因此每一個這樣的元素有自信息量。 這樣，碼C中平均每個碼字含有的信息量為L(C)lbq。由于是無損編碼，因此L(C)lbq不應當小于H

9、(X)，又由于L(C)最小，因此定理1.1.1設離散平穩(wěn)無記憶信源的熵為H(X)，X= a1，a2，an，那么一定存在一種碼C使熵和平均碼長間滿足下列關系：證明基于信源X，構造一個長度為N的符號串si= (r1,r2,rN)，riX，這樣的符號串si形成一個N維擴展信源XN，對N維擴展信源進行編碼，獲得碼C=ci|i=1,2,，每個ci長為li，發(fā)生概率為pi。按概率匹配原則進行編碼，碼長應滿足：(1.1.7) 式(1.1.8)兩邊乘以pi并求和后，有(1.1.8) (1.1.9) 注意到由此可得(1.1.10) 由于是無記憶信源，故H(XN)=NH(X) (1.1.11)將式(1.1.11)

10、代入式(1.1.10)，即得式(1.1.7)。2) 香農第二定理定義1.1.6對離散無記憶信道，信源和信宿分別為X和Y，px表示信源X的概率分布，稱為信道容量。(1.1.12) 定義1.1.7消息在信道上的傳輸過程中，單位時間內傳送的實際信息量稱為信息傳輸速率，記為R。定理1.1.2設離散無記憶信道的信道容量為Cc，總存在一種RCc的碼C使接收端恢復消息的誤碼率peCc的碼C使pe任意小。順便指出，在連續(xù)AWGN信道上，香農信道容量公式為(1.1.13) 3) 香農第三定理在許多實際情況下進行無失真編碼是不必要的，信源可以在信宿恢復消息所需的條件下對消息進行壓縮處理，以減小存儲或傳輸?shù)目偭?。這

11、種壓縮方式通常就是去掉消息間的冗余度。要滿足信宿恢復消息所需要的條件，就必須在編碼時對失真設置一個最大值，稱為保真度，記為D。保真度越高，即D越小，意味著壓縮去掉的傳輸?shù)男旁葱畔⒘烤驮缴?，需要傳輸更多的信源信息量。很顯然，對給定的保真度D，信息傳輸速率R不能低于某一個下限值。保真度不同，下限值也不一定相同，即下限值是D的函數(shù)，稱為率失真函數(shù)，記為R(D)。定理1.1.3對任意給定的保真度D0，只要碼長N足夠大，一定可以找到一種碼C使編碼后每個符號的信息傳輸率不小于R(D)，且碼的平均失真度不超過D。4. 數(shù)字調制的基本原理所謂調制，是指根據(jù)調制信號的變化規(guī)律去改變載波某些參數(shù)的過程。調制具有搬

12、移信號頻譜的作用，能夠把信號的頻譜搬移到理想的位置，從而獲得適合于信道傳輸?shù)男盘?，大大提高信號傳輸?shù)挠行院涂煽啃浴Ｕ{制可以分為模擬調制和數(shù)字調制兩種，模擬調制的調制信號取值是連續(xù)的，數(shù)字調制的調制信號取值是離散的。1) 二進制數(shù)字調制二進制數(shù)字調制是指調制信號為二進制數(shù)字信號的調制方式，在這類調制中，載波的某個參數(shù)(如幅度、頻率或相位)僅有兩種簡單的變化狀態(tài)。二進制數(shù)字調制分為幅度鍵控、頻移鍵控和相移鍵控三種。(1) 二進制幅度鍵控(Binary Amplitude Shift Keying，BASK)。設xk是來自于信源的二進制數(shù)字信息1和0，其發(fā)生概率分別為p和1p，即則BASK信號可以

13、表示為式中：fc為載波頻率；g(t)是一個矩形脈沖；Ts為持續(xù)時間。式(1.1.14)表明在二進制幅度鍵控調制中，載波幅度隨二進制被調信號序列的變化而改變，如圖1.8所示。(1.1.14) 圖1.8BASK調制信號示意圖(2) 二進制頻移鍵控(Binary Frequency Shift Keying，BFSK)。設xk是來自于信源的二進制數(shù)字信息1和0，其發(fā)生概率分別為p和1p，則BFSK信號可以表示為式(1.1.15)表明BFSK調制信號隨被調信號序列在兩個載波頻率間切換。當xk=1時，使用載波頻率f1；當xk=0時，使用載波頻率f2，如圖1.9所示。(1.1.15) 圖1.9BFSK調制

14、信號示意圖(3) 二進制相移鍵控(Binary Phase Shift Keying，BPSK)。設xk是來自于信源的二進制數(shù)字信息1和0，其發(fā)生概率分別為p和1p，則BPSK信號可以表示為式(1.1.16)表明BPSK調制信號隨被調信號序列在兩個相位相差為180的信號間切換。當xk=1時，載波信號為cos(2fct)；當xk=0時，載波信號為cos(2fct)，如圖1.10 所示。(1.1.16) 圖1.10BPSK調制信號示意圖2) M進制數(shù)字調制設xk是來自于信源的二進制數(shù)字信息1和0，將m個二進制符號的所有可能組合與M(M=2m)個載波相位相對應，則MPSK信號可以表示為例如，取m=2

15、，那么載波相位數(shù)為M=22=4，稱為QPSK (即4PSK)信號。2個二進制符號的可能組合為00，01，10，11，2個二進制符號與載波相位間的對應關系見表1.1。(1.1.17) 表1.1QPSK信號的載波相位對應關系 為了更清楚地表明這種對應關系，常使用信號星座(Constellation)圖形來描述。圖 1.11 給出了BPSK、QPSK和8PSK信號的星座圖。圖1.11MPSK信號星座圖(a) BPSK信號星座圖；(b) QPSK信號星座圖；(c) 8PSK信號星座圖習題11. 信源編碼和信道編碼的根本目的是什么？2. 已知離散無記憶信源求信源的熵。3. 在二元對稱信道中，已知信源，信

16、宿Y的概率分布p(Y)=0.60.4，求信道轉移矩陣。4. 在實際信道中，噪聲和損失是不可避免的。矩陣P1是有噪無損信道的信道轉移矩陣，P2是無噪有損信道的信道轉移矩陣，即試畫出兩信道的狀態(tài)轉移圖，并比較兩者的差異，以及據(jù)此推斷出無噪無損信道和有噪有損信道的狀態(tài)轉移圖。5. 已知信源，信道轉移矩陣，信宿求信宿Y的概率分布p(Y)。6. 求出無記憶二元對稱信道的二維擴展信道的信道轉移矩陣。第2章信源編碼 2.1無失真信源編碼2.2限失真信源編碼習題2.1無失真信源編碼無失真信源編碼的理論基礎就是第1章介紹的香農第一定理，實現(xiàn)的途徑之一是概率匹配原則，最終目的是找到一種平均碼長最短的碼。先來看一個

17、例子。例2.1.1設有離散無記憶信源，進行以下兩種方式的二進制編碼：(1) a100，a201，a310，a411；(2) a10，a210，a3110，a4111，試求兩種編碼方式的平均碼長和編碼效率。解信源熵為H(X)=(0.5 lb0.5+0.3 lb0.3+0.15 lb0.15+0.05 lb0.05)=1.6477 bit(1) L(C1)=20.5+20.3+20.15+20.05=2 bit(2) L(C2)=0.51+0.32+0.153+0.053=1.7 bit2.1.1Huffman編碼1. 編碼原理利用概率匹配原則，編碼時，碼長應當選擇滿足式(1.1.8)的整數(shù)，但并

18、非每次應用都能獲得理想的編碼。看下面兩個例題。例2.1.2無記憶信源，利用概率匹配原則進行編碼，并求出平均碼長和編碼效率。解根據(jù)式(1.1.8)，字符a1、a2、a3、a4、a5對應的碼長分別為1、2、3、4、4，用二進制符號來表示字符，即那么，平均碼長為又因為所以，獲得的編碼效率為=100%例2.1.2的二元碼的碼樹見圖2.1。圖 2.1例2.1.2編碼的碼樹例2.1.3無記憶信源，試利用概率匹配原則進行編碼，并求出平均碼長和編碼效率。解根據(jù)式(1.1.8)，字符a1、a2、a3、a4、a5、a6對應碼長分別為2、2、3、5、6、6，用二進制符號來表示字符，即計算后，得到H(X)=1.83

19、bit，L(C)=2.55 bit，71.8%例2.1.3編碼的碼樹見圖2.2。圖 2.2例2.1.3編碼的碼樹由例2.1.3的計算可知，該編碼效率很低。從碼樹上我們可以看到，離樹根較近的地方有許多空枝，如果不考慮式(1.1.8)而把其他碼字移到這些空枝上會出現(xiàn)什么情況呢？ 圖2.3就是移動碼字后的碼樹。圖 2.3改進圖2.2后的碼樹圖2.3所示的碼樹對應的符號編碼如下：圖2.3所示碼樹對應編碼的平均碼長和編碼效率分別為L(C)=2.15 bit，85.1%由此可見，改進后的碼樹(圖2.3)的編碼效率明顯提高。例2.1.3啟示我們編碼時碼樹不能留有空枝，單純地應用概率匹配原則不一定能得到最佳編

20、碼。例2.1.3獲得較高編碼效率實質上是對碼樹實行了全局性能匹配，圖2.2所示的碼樹只是在局部枝上實行概率匹配原則，而忽略了全局優(yōu)化，因而效率較低。那么圖2.3是否是例2.1.3的最佳編碼呢？我們再來觀察針對例2.1.3的另一碼樹圖2.4。圖 2.4例2.1.3編碼的另一碼樹圖2.4所示碼樹對應的符號編碼如下：圖2.4所示碼樹對應編碼的平均碼長和編碼效率分別為L(C)=2.05 bit，89.3%定理2.1.1(q元Huffman編碼)設離散無記憶信源按下述步驟進行編碼，獲得的碼一定具有最小平均碼長。第一步，根據(jù)出現(xiàn)概率的大小，按從大到小的順序重排字符符號。第二步，在重組的信源中，從最小概率的

21、符號開始，按概率從小到大的方式取q個符號作為q片樹葉合并到一個節(jié)點上，將0，1，2，q1這q個數(shù)不重復地分配到這q個樹葉上。第三步，被合并的q個字符用一個臨時字符代替，這個臨時字符的概率為被合并的q個字符的概率之和，其余字符及概率不變，從而形成一個新的信源空間。第四步，如果新的信源空間的概率分布p(X)=1，這時的節(jié)點就是碼樹的樹根，則轉到第五步，否則， ，轉到第一步。第五步，從樹根開始，沿枝到達樹葉，途中遇到的數(shù)字按行走順序組合就得到該樹葉字符所對應的碼字，找完全部樹葉，編碼完成。證明設Huffman編碼完成后，aici(i=1，2，n)，并且碼ci的長度為li，則Huffman編碼的平均碼

22、長。再設p(ak)p(aj)，根據(jù)Huffman編碼，則有l(wèi)jlk。如果重新構造一個編碼C，其對應關系如下：即交換字符ak與aj所對應的碼字，而其余字符對應碼字不變，形成碼C，那么碼C的平均碼長為式(2.1.1)說明Huffman編碼的平均碼長最短。(2.1.1) 從Huffman編碼過程來看，如果完成編碼共引入了r個臨時字符，除第一次合并用了信源的q個字符外，其余各次合并都只使用了信源的q1個符號，所以信源符號的數(shù)量應當為n=r(q1)+q (2.1.2)例2.1.4設離散無記憶信源，構建平均碼長最短的二元碼。解第一次合并：按概率從大到小的順序重排字符，并合并最后兩個字符為新的臨時字符d1。

23、第二次合并：按照概率從大到小的順序重排字符，并合并最后兩個字符為新的臨時字符d2。第三次合并：按照概率從大到小的順序重排字符，并合并最后兩個字符為新的臨時字符d3。第四次合并：按照概率從大到小的順序重排字符，并合并最后兩個字符為新的臨時字符d4。第五次合并：按照概率從大到小的順序重排字符，并合并最后兩個字符為新的臨時字符d5。因為p(X)=1，故編碼結束。從圖2.5所示的碼樹的樹根開始，可以讀出對應于每一字符的Huffman編碼如下：經(jīng)計算，本例的熵、平均碼長和編碼效率分別為H(X)=2.42 bit，L(C)=2.45 bit，98.8%圖 2.5例2.1.4的Huffman編碼過程例2.1

24、.5已知離散無記憶信源試求Huffman三元和四元編碼。解本例的三元Huffman編碼過程見圖2.6，三元Huffman編碼如下：圖 2.6三元Huffman編碼過程由于不滿足式(2.1.2)，因此添加一個字符a10，并取p(a10)=0。本例的四元Huffman編碼過程見圖2.7，四元Huffman編碼如下：圖 2.7四元Huffman編碼過程2. 舉例CCITT T.4對三類傳真機的掃描線長度和每行像素作了如下規(guī)定：(1) A4紙文本的一行(215 mm1%)掃描后構成一條掃描線，線上有1728個黑白像素；(2) B4紙文本的一行(255 mm1%)掃描后構成一條掃描線，線上有2048個黑

25、白像素；(3) A3紙文本的一行(303 mm1%)掃描后構成一條掃描線，線上有2432個黑白像素。三類傳真機對掃描線的編碼的結構如圖2.8所示。圖 2.8三類傳真機對掃描線的編碼的結構(a) 一維編碼方案；(b) 二維編碼方案經(jīng)過大量統(tǒng)計發(fā)現(xiàn)游程長度有以下特點：(1) 游程長度的概率分布表現(xiàn)為對掃描的文本的行與行間不同，對掃描的文本的頁與頁間不同；(2) 出現(xiàn)于每一掃描線中的游程長度的種類非常多，例如，在一條有1728個黑白像素的掃描線上出現(xiàn)的可能游程長度為1，2，3，1728。MH碼表見表2.1和表2.2。 表2.1一維改進Huffman編碼表構造碼 表2.2一維改進Huffman編碼表結

26、尾碼 傳真機傳輸一頁文件文本是按圖2.9所示的數(shù)據(jù)傳輸格式進行傳輸?shù)摹D 2.9一頁文件傳真的數(shù)據(jù)傳輸格式2.1.2算術編碼1. 基本概念Huffman編碼是在信源符號與可變長度碼字之間建立一個1-1對應關系而實現(xiàn)編碼的，算術編碼則是對信源的輸出符號流進行編碼，因此，算術編碼不需要像Huffman編碼那樣為每一個信源符號指定一個碼字。本節(jié)先介紹算術編碼的思想和基本概念，具體編碼方法的介紹將在后續(xù)各小節(jié)中陸續(xù)展開。設有無記憶信源空間，其中，p1p2pn，定義信源字符的累積概率為很明顯，有下列關系：l0=0，l1=p1，l2=p1+p2，并且pi=lili1 (2.1.4)(2.1.3)由于概率的

27、大小總是在0和1之間，因而可以把li與li1視為區(qū)間0，1)中的兩個點，那么，pi剛好等于子區(qū)間li1，li)的長度。很明顯，這些子區(qū)間是互不重疊的，不同的信源符號有唯一一個子區(qū)間與之對應，因而，我們可以任選子區(qū)間的一個點來代表這個子區(qū)間所對應的信源符號。例如，可以選子區(qū)間的左端點，這種代表是可變的，但代表的信源符號是唯一的，如圖2.10所示。圖 2.10信源字符累積概率劃分的子區(qū)間與信源符號的對應關系不同的字符序列與唯一一個子區(qū)間對應，如圖2.11所示。圖 2.11序列的累積概率劃分的子區(qū)間與序列的對應關系很明顯，每一序列的概率恰好為所對應子區(qū)間li1，li)的長度，有關系式：(2.1.5)

28、 新序列或者的累積概率為(2.1.6) (2.1.7) 2. 編碼方法算術編碼的編碼過程實質上就是尋找字符所對應的子區(qū)間，新到字符對應的子區(qū)間是通過迭代更新前一個字符的子區(qū)間來獲得的。設信源輸出的第k1個字符對應的子區(qū)間為DLk1，DHk1)，子區(qū)間的寬度為k1=DHk1DLk1，那么，第k個字符對應的子區(qū)間DLk，DHk)為(2.1.8) 式(2.1.8)也可以變形為用子區(qū)間下端點和區(qū)間寬度來表示，即(2.1.9) 算術編碼的具體編碼過程如下。首先，初始化。然后，輸入字符進行迭代運算。第一步，信源X輸出第一個字符。設 。取，更新區(qū)間，即新區(qū)間。如果信源輸出字符結束，則任取作為字符 的算術編碼

29、。否則，繼續(xù)第二步，并令(2.1.10) 第二步，信源X輸出第二個字符 。設。取，更新區(qū)間，。如果信源輸出字符結束，則任取 作為字符的算術編碼。否則，繼續(xù)第三步，并令第三步，信源X輸出第三個字符 。 假設已進行了第k1步，即已知和，繼續(xù)第k步。第k步，信源X輸出第k個字符 。(2.1.11) 設。取，更新區(qū)間， 。如果信源輸出字符結束，則任取作為字符的算術編碼。否則，繼續(xù)第k+1步，并令歸納起來，算術編碼的編碼流程圖如圖2.12所示。(2.1.12) 圖 2.12算術編碼的編碼流程圖例2.1.6設有離散無記憶信源空間，求出字符流a2a0a1a0a0a4a3的算術編碼。解首先，將區(qū)間0，1)分成

30、5個子區(qū)間，即其次，初始化，即DL0=0，DH0=1，j=0最后，輸入字符進行迭代運算，見表2.3。表2.3例2.1.6字符流的算法編碼過程3. 譯碼方法因為每一字符被唯一地指定了一個子區(qū)間，所以只需要根據(jù)碼字來反推是哪個子區(qū)間就能得到相應的字符，從而實現(xiàn)譯碼。算術譯碼的過程如下。第一步，譯出字符流的第一個字符。第二步，譯出字符流的第二個字符。第三步，譯出字符流的第三個字符。如此繼續(xù)下去，直到最后一個字符譯出。歸納起來，算術編碼的譯碼流程圖如圖2.13所示。圖 2.13算術編碼的譯碼流程圖例2.1.7信源空間同于例2.1.6，譯出算術編碼b=0.7412261962890625。解譯碼過程見表

31、2.4，得到算術編碼b對應的字符流為a2a0a1a0a0a4a3。表2.4例2.1.7的算術編碼b的譯碼過程4. 二元QM編譯碼器二元QM編譯碼器是一種自適應方式的算術編譯碼器，其優(yōu)點是無需預先確定信源空間的概率模型，特別適合于難以進行概率統(tǒng)計的信源空間，編譯碼中所需要的概率通過概率估計器估計來獲得。此外，算術編碼每次遞推要進行乘法運算，并且要求運算在下一個字符到來前完成，有時要達到這一要求是困難的。QM編譯碼器能轉乘法運算為移位操作或減法運算，極大地提高了處理速度，因此，QM編譯碼器得到了廣泛應用。例如，JPEG圖像壓縮標準中就使用QM編譯碼器。QM編譯碼器的編譯碼原理框圖見圖2.14。圖

32、2.14QM編譯碼器的編譯碼原理框圖(a) 編碼器；(b) 譯碼器式(2.1.9)的子區(qū)間迭代關系可以簡化為如下兩種形式：(1) 如果第k個字符的概率較大，即字符a1，則有(2) 如果第k個字符的概率較小，即字符a2，則有(2.1.14) (2.1.13) 式(2.1.13)和(2.1.14)可以用如下的計算機賦值語句來實現(xiàn)：(1) 對于MPS，有 DLDL，(12Q) (2.1.15)(2) 對于LPS，有 DLDL+(12Q)，2Q (2.1.16)實際的QM編譯碼器就是按式(2.1.15)和(2.1.16)來實現(xiàn)編譯碼的。2.2限失真信源編碼2.2.1基本概念什么是失真？簡單地說，失真就

33、是信宿接收到的符號與信源發(fā)出的符號不同。 定義2.2.1設信源X=a1，a2，an，信宿Y=b1，b2，bm，從信源發(fā)送出符號xX，信宿接收到符號yY，稱為失真函數(shù)。(2.2.1) 失真函數(shù)d(x，y)可以通過設置不同的d0來表示失真的嚴重程度，常見的d0取值方法主要有以下幾種形式。誤碼失真：d0=1絕對失真：d0=|xy| (2.2.2)平方失真：d0=(xy)2 (2.2.3)相對失真： (2.2.4) 定義2.2.2設從信源X發(fā)送長度為N的符號序列(x1，x2，xN)，信宿接收到的是長度為M的符號序列(y1，y2，yM)，定義階是NM的矩陣A：稱A為失真矩陣。(2.2.5) 例2.2.1

34、在N元對稱信道中，采用誤碼失真函數(shù)，即d(i，i)=0，d(i，j)=1，i，j=0，1，N1且ij，失真矩陣為在二元刪除信道中，定義d(0，0)=d(1，1)=0，d(0，1)=d(1，0)=1，失真矩陣為設信源X=0，1，2，3，信宿Y=0，1，2，3，采用平方失真函數(shù)，失真矩陣為定義2.2.3設信源p(ai，bj)表示ai與bj的聯(lián)合概率，稱為平均字符失真度。式中，E表示數(shù)字期望，p(ai，bj)=p(ai) p(bj|ai)。(2.2.6) 如果是連續(xù)信號，式(2.2.6)中的求和符號轉化為積分符號，概率轉化為隨機變量的概率密度函數(shù)，就得到連續(xù)隨機變量的平均失真函數(shù)：(2.2.7) 定

35、義2.2.4設信源發(fā)出長為N的字符序列，其中，信宿接收字符序列為，其中，那么字符序列x與y間的失真函數(shù)為定義2.2.5設有信源X的N維擴展信源XN，信宿Y的N維擴展信宿YN，那么平均序列失真度為對于無記憶信道，與間有關系：(2.2.9) (2.2.8) 例2.2.2設有離散無記憶信源 ，無記憶信道轉移矩陣 ，求在誤碼失真函數(shù)下平均字符失真度和平均序列失真度。解設信宿為，則有 p(b1|a1)=0.75，p(b2|a1)=0.25，p(b1|a2)=0.4，p(b2|a2)=0.6由式(2.2.6)得平均字符失真度為X二維擴展信源X2為由于無記憶信道 ，因此由式(1.1.2)得二維擴展信道P2為

36、又因為各字符序列間的誤碼失真函數(shù)為根據(jù)式(2.2.8)，平均序列失真度 為顯然，符合式(2.2.9)的結論。在通信系統(tǒng)中，允許的失真有一定的限度，這個限度可以用平均字符失真度和保真度D來衡量，即滿足所謂的如下保真度準則：(2.2.10) 2.2.2離散與連續(xù)信源的限失真編碼方法1. 離散信源的限失真編碼設X=0，1，考慮無記憶等概信源X3=000, 001, 010，011，100，101，110，111，信源需要向信宿傳送消息101000100010111110001110假設通過無噪無損信道進行傳送，應當如何進行壓縮編碼呢？一種壓縮方法是將信源分成兩個子集，分別是000，001，010，1

37、00和011，101，110，111，前一個子集的字符序列全部編碼為000，后一個子集的字符序列全部編碼為111。將000與111分別壓縮為0和1在信道上傳輸，那么消息、編碼、壓縮、傳輸與接收、譯碼的關系見表2.5。 表2.5消息、編碼、壓縮、傳輸與接收、譯碼間的關系2. 模/數(shù)(A/D)轉換的量化失真編碼現(xiàn)代通信中大量采用數(shù)字通信技術，這是因為數(shù)字信號比模擬信號具有更強的抗干擾能力和壓縮能力。A/D轉換過程如圖2.15所示。圖 2.15A/D轉換過程設連續(xù)變量x的取值范圍在區(qū)間(b0，bn)中，將區(qū)間(b0，bn)分成n=2N個小區(qū)間b0，b1)，b1，b2)，b2, b3)，bi，bi+1

38、)，n稱為量化級數(shù)。對于位于bi，bi+1)中的任何采樣值，都用yi(bi，bi+1)來表示(i=0，1，2，n1)，見圖2.16。那么，y0，y1，yn1就是x(b0，bn)的n級量化值。圖 2.16量化示意圖下面來討論如何選取量化值yi。由于yi是指定的，不再是隨機變量，因而式(2.2.7)變?yōu)椴捎闷椒绞д婧瘮?shù)，則式(2.2.11)變?yōu)?2.2.11) (2.2.12) 對式(2.2.12)求關于bi+1的導數(shù)，并令其為零，得到于是，得到(2.2.13) 式(2.2.13)說明平均失真度達到最小，應選擇bi+1為區(qū)間yi，yi+1的中點。又因為所以(2.2.14) 考慮變量x的概率密度函數(shù)

39、是均勻的，即那么，式(2.2.14)可化為(2.2.16) (2.2.15) 式(2.2.16)說明yi應為區(qū)間bi，bi+1的中點，結合式(2.2.13)，得到各小區(qū)間是均勻的，不難計算將式(2.2.17)代入式(2.2.12)，求得(2.2.18) (2.2.17) 2.2.3最小均方誤差準則下的最佳線性預測編碼方法通常，在模擬信號采樣值間存在一定的相關性，因此，相鄰采樣值之差的方差會比采樣值的方差小許多，這說明如果用量化采樣值的量化級數(shù)去量化差值，那么量化誤差會減小，這意味著在保持相同量化精度的條件下，對相鄰采樣值之差的量化級數(shù)可以減小，這一結論對數(shù)據(jù)壓縮極為有利。差分脈沖編碼調制(DP

40、CM)系統(tǒng)就是利用上述思想進行工作的，見圖2.17。圖 2.17DPCM系統(tǒng)框圖從圖2.17可以看出，DPCM系統(tǒng)的關鍵就是預測器的構造，預測器可以通過前向預測法來實現(xiàn)。已知采樣值x(1)，x(2)，x(n1)，需要估計x(n)。自然會想到，估計x(n)的最簡單的方法就是把它視為已知采樣值的線性組合，即x(n)被估計為預測器可以通過圖2.18所示的橫向FIR濾波器結構來實現(xiàn)。(2.2.19) 圖 2.18前向預測器的實現(xiàn)結構式(2.2.19)通過過去的數(shù)據(jù)來估計當前數(shù)據(jù)，因此稱為前向預測。式(2.2.19)中的N稱為預測器的階，ai稱為預測器系數(shù)，預測誤差為人們當然希望前向預測器是最佳的，也就

41、是預測的均方誤差應當最小。要使最小，必須合理選擇預測器系數(shù)ai。由(2.2.20) (2.2.21) 得到方程組使用自相關函數(shù)的定義，并考慮信源是平穩(wěn)隨機過程，于是有Ex(ni)x(nj)=R(|ij|) (2.2.23)式中，R()表示x(n)在相移為時的自相關函數(shù)。(2.2.22) 通常，采樣數(shù)據(jù)是有限的，因而R()只能通過有限個數(shù)據(jù)來估計。如果有M個采樣數(shù)據(jù)，則R()能被估計為又根據(jù)式(2.2.21)，預測的均方誤差為(2.2.24) (2.2.25) 聯(lián)合式(2.2.22)和式(2.2.23)，得到(2.2.26) 圖2.19給出了Levinson遞推算法的流程。圖 2.19Levin

42、son遞推算法的流程2.2.4最佳變換編碼方法數(shù)據(jù)壓縮編碼的實質是去掉冗余消息，正交變換是完成這一任務的有力工具之一。正交變換主要有Karhunen-Love變換(簡稱K-L變換)、離散正弦變換(Discrete Sine Transform，DST)、 離散余弦變換(Discrete Cosine Transform，DCT)、離散Hartley變換、離散W變換等。1. K-L變換設x與y是兩個階為N1的列向量(信號矢量)，A是一個NN的矩陣，如果y=Ax，則稱x被變換為y。如果變換矩陣A是正交矩陣，則稱這個變換為正交變換。設Ai表示矩陣A的第i行的轉置，則A=A1，A2，ANT又因為A是正

43、交矩陣，即ATA=AAT=I，所以A1=AT于是，由變換y=Ax得到(2.2.27) 設x的均值為0，現(xiàn)在我們希望用較少的y的分量來表示x，從而實現(xiàn)對數(shù)據(jù)x的壓縮。例如，用y的前m個分量來表示數(shù)據(jù)x，這樣的表示只能是x的近似，記為，即誤差矢量為(2.2.28) (2.2.29) 當然，在恢復信號x時，也只能用y的這前m個分量。因此，希望能合理選擇變換矩陣A使均方誤差達到最小。這里使用了A是正交矩陣，即 的條件。由式(2.2.27)有，將其代入式(2.2.30)，有(2.2.30) (2.2.31) 為了使式(2.2.31)最小，考慮Lagrange條件極值，約束條件是矩陣A正交，有于是，獲得C

44、xAi=iAi (2.2.33)式(2.2.33)提示我們，實現(xiàn)數(shù)據(jù)的壓縮的變換矩陣應當由信號的協(xié)方差矩陣的特征向量來構成。將式(2.2.33)代入式(2.2.31)，得到均方誤差er為(2.2.34) (2.2.32) 2. DCT變換1) 一維DCT變換一維DCT變換由Ahmed和Rao首先給出，一維DCT變換能將信號x=(x(0)，x(1)，x(N1)T 變換到信號y=(y(0)，y(1)，y(N1)T，且滿足下列關系式：(2.2.35) 令那么，一維DCT變換的正變換可以簡寫為(2.2.37) (2.2.36) 寫成矩陣形式，有y=CNx (2.2.38)式中：(2.2.39) 由于矩

45、陣CN是正交的，因此一維DCT的反變換不難求出，即將式(2.2.40)寫成一般表達式，即(2.2.40) (2.2.41) 令稱式(2.2.42)為一維DCT變換的變換核。利用變換核，一維DCT變換的正、反變換可以簡單表示為(2.2.43) (2.2.42) 2) 二維DCT變換在許多場合，需要變換的信號不是一維信號，而是二維信號，如一幅靜態(tài)數(shù)字圖像就是用二維信號來表示的。二維DCT變換是非常重要的一類二維變換。設x(n，m)|n=0，1，N1；m=0，1，M1表示一個二維離散信號集合，二維DCT變換將信號集合x(n，m)變換為y(u，v)|u=0，1，N1；v=0, 1，M1，且滿足下列關系

46、：(2.2.44) 二維DCT變換的反變換為定義二維DCT變換的變換核為(2.2.45) (2.2.46) 那么，二維DCT變換的正、反變換在變換核下可以簡化表示為(2.2.47) 注意到變換核是可分離的，即h(u，v，n，m)=g(u，n，N)g(v，m，M)，這里的g(，)就是式(2.2.42)，所以，二維DCT變換的正變換也可以寫成如下的矩陣形式：式中：y(u，v)NM表示NM階矩陣，第u行第v列元素為y(u，v)；CN和CM的意義同于式(2.2.39)。(2.2.48) 展開式(2.2.47)的反變換，得到式(2.2.49)表示一個NM個點的圖像可以理解為由NM個基圖像的加權和構成，其

47、權重就是二維DCT變換值y(u，v)，因而y(u，v)代表了對應的基圖像h(u，v，n，m)在加權和中所占的比重，在物理概念上相當于二維DCT變換把空間像素的幾何分布變換成空間的頻率分布。(2.2.49) 圖像塊的大小NM除了對二維DCT變換的計算量有很大影響外，對圖像的壓縮效果也有明顯影響。通常，在對圖像進行DCT變換時往往把圖像分割成許多小方塊，然后按順序對每一塊進行處理，圖像塊較小，圖像中包含的像素就少，進行DCT變換的計算量就小，但壓縮效果差，還會產生“方塊效應”；圖像塊過大，雖然去相關性能好，但計算量很大并且一旦圖像塊的像素足夠多后對數(shù)據(jù)壓縮的效果就會達到飽和狀態(tài)，再加大塊的尺寸對改

48、進壓縮效果不會有明顯提高。因此，在對靜止圖像進行壓縮的JPEG技術標準中，建議的圖像塊的大小為88，其壓縮流程見圖2.20。圖 2.20靜止數(shù)字圖像的JPEG壓縮流程3. 小波變換1) 概念準備設有函數(shù)f(t)(t+)，如果函數(shù)f(t)滿足：那么，稱f(t)為絕對可積函數(shù)。設函數(shù)f(t)(t+)絕對可積，稱(2.2.50) (2.2.51) 為f(t)的傅里葉變換。稱為F()的傅里葉反變換。這里j2=1。設有函數(shù)f(t)(t1，b00，定義，稱下面積分為離散小波變換。(2.2.85) (2.2.86) 最典型的a0和b0的取值是a0=2，b0=1，即我們已經(jīng)熟悉的二尺度小波伸縮平移族式(2.2

49、.71)。例如, 以為尺度函數(shù)，那么，小波函數(shù)就是Harr函數(shù)，其小波伸縮平移族為(2.2.87) 圖2.27給出了幾個較小的i和k對應的Harr小波伸縮平移族及尺度函數(shù)的波形。圖 2.27尺度函數(shù)波形與Harr小波伸縮平移族的幾個波形由式(2.2.80)不難看出，二尺度下的離散小波變換就是離散細節(jié)系數(shù)，Mallat塔式算法為計算提供了一套遞推公式。在式(2.2.81)中令i=0并用n來代替k，則有由式(2.2.88)，對(t)進行伸縮平移操作，即用2itk代替t后，有(2.2.88) (2.2.89) 再令m=2k+n，則式(2.2.89)可以簡化表示為將式(2.2.90)兩邊同乘以2i/2

50、并應用式(2.2.65)，得到又由式(2.2.79)，有(2.2.91) (2.2.90) (2.2.92) 同理，不難推導出式(2.2.92)和式(2.2.93)是離散小波變換Mallat塔式算法的兩個關鍵遞推方程，這兩個方程建立了Vi1空間的分辨率為i1的離散平滑逼近系數(shù)到Vi和Ui兩個子空間的分辨率為i的離散平滑逼近系數(shù) 和離散細節(jié)系數(shù) 間的遞推關系，使計算量大幅度地減小。Mallat塔式算法的分解遞推流程見圖2.28。(2.2.93) 圖 2.28Mallat格式算法的分解遞推流程在遞推出離散平滑逼近系數(shù)和離散細節(jié)系數(shù)后，由式(2.2.64)、式(2.2.76)和式(2.2.77)，f

51、(t)可以分解成(2) 離散小波反變換。離散小波變換主要用于信號的分解，離散小波反變換主要用于信號的重建，重建是分解的逆過程。為了快速完成信號的重建，我們也需要找到離散平滑逼近系數(shù)和離散細節(jié)系數(shù)間的遞推關系。由式(2.2.76)、式(2.2.77)和式(2.2.78)，有(2.2.94) (2.2.95) 利用式(2.2.65)和式(2.2.71)，并把二尺度函數(shù)的性質式(2.2.81)和式(2.2.83)代入式(2.2.95)，有由式(2.2.65)，式(2.2.96)可以簡化為(2.2.97) (2.2.96) 注意到，所以式(2.2.97)兩邊同乘以i1，m(t)后求內積，可以得到進一步

52、地，有式(2.2.99)就是重建信號的Mallat快速算法遞推公式，遞推流程可以用圖2.29來表示。(2.2.99) (2.2.98) 圖 2.29Mallat算法的重建遞推流程(3) Mallat算法的初值及h(n)與g(n)間的關系。于是，分辨率i=0時的離散平滑逼近系數(shù)a0可以用對原函數(shù)的采樣來近似代替，即式中，t為采樣間隔時間。已知h(n)與g(n)間的關系是實現(xiàn)Mallat算法快速分解的另一個前提，可以證明兩者有如下關系：g(n)=(1)nh(1n) (2.2.101)(2.2.100)5) 二維離散小波變換類似于一維離散小波變換，在分辨率i下的二維尺度空間Vi可以表示為與的張量積，

53、即用Wi表示在的正交補空間，即且則有(2.2.102)(2.2.103)設f()是Wi上的小波函數(shù)，fi，m(x)=2i/2(2ixm)，f i，n(y)=2i/2(2iyn)，f i，m(x)|mZ和f i，n(y)|nZ是Wi上的標準正交基，定義(2.2.104)f(x，y)可以在二維小波函數(shù)和二維尺度函數(shù)下展開為式中：、 和分別為空間、 和上的小波展開系數(shù)； 為空間Vi上的尺度展開系數(shù)，即(2.2.105)(2.2.106)類似于一維情況，二維離散小波變換也有快速Mallat分解算法，算法公式如下：(2.2.107)二維離散小波變換的快速Mallat重建算法遞推公式為(2.2.108)習

54、題21. 已知離散無記憶信源為求二元Huffman編碼，并計算效率，畫出碼樹。2. 已知離散無記憶信源為求三元和四元Huffman編碼。3. 已知離散無記憶信源為算術編碼為b=0.57470703125(0.10010011001)，譯出長度N=5的字符流。4. 無記憶信源，信道轉移矩陣為 ，試求在平方失真函數(shù)下的平均字符失真度。 5. 求采用絕對失真函數(shù)時，A/D轉換的量化失真編碼的平均失真度，其中，p(x)采用式(2.2.15)。6. 設信號x=(x1，x2)T的協(xié)方差矩陣，求出K-L變換y=Ax的正交矩陣A。7. 驗證N=4時的一維DCT變換矩陣是正交矩陣。8. 設有一個二維圖像信號(a

55、0)，試求出二維DCT變換。9. 結合表2.1和表2.2，對用MH編碼壓縮的傳真信號 00110101000011010110001011100000011010110000000000001譯出黑白游程長度的順序分布，并計算壓縮比。第3章分組碼 3.1糾、檢錯編碼的基本概念3.2線性分組碼3.3循環(huán)碼3.4BCH碼習題 3.1糾、檢錯編碼的基本概念為了降低錯誤概率pe及使接收端具備檢錯、糾錯能力，我們這樣來對待傳消息進行編碼。選碼C1=00000，11111，作映射：即消息中的每一符號比特按其重復的5比特碼字來表示，并由發(fā)送端傳送。接收端按選大原則進行譯碼，在接收的5比特矢量中，哪個符號多就

56、譯為哪個。例如接收為10110，則譯為11111。消息的編碼、譯碼關系見表3.1。表3.1消息的編碼、譯碼關系定義3.1.1，x=(x1，x2，xn)，y=(y1，y2，yn)，稱dist(x，y)=|i|xiyi，i=1，2，n| (3.1.1)為碼字x與y的漢明距離。碼字間的漢明距離滿足下列三角不等式：dist(x，y)dist(x，z)+dist(z，y) (3.1.2)在一個碼中，任意兩個不同碼字間漢明距離的最小者稱為這個碼的最小漢明距離。定義3.1.2設有碼C，稱 (3.1.3)為碼C的最小漢明距離。在一個碼中，碼字中非零碼元的數(shù)目也是一個重要的參數(shù)，這個參數(shù)通常稱為碼字的漢明重量。

57、定義3.1.3設有碼C，稱wt(x)=|i|xi0，i=1，2，n| (3.1.4)為碼字x的漢明重量。定義3.1.4設有碼C，0 =(0，0)，稱wt(C)=minwt(x)|xC，x0 (3.1.5)為碼C的最小漢明重量。例3.1.1設有碼C2=(a1，a2，a3，a4，a5，a6，a7，a8)，式中a1=(0000000)a2=(0011101)a3=(0100111)a4=(0111010)a5=(1001110)a6=(1010011)a7=(1101001)a8=(1110100)求dist(a2，a4)，dist(a3，a7)，wt(a8)，dist(C2)，wt(C2)。解di

58、st(a2，a4)=4，dist(a3，a7)=4，wt(a8)=4，dist(C2)=4，wt(C2)=4定義3.1.5設有碼C，如果，有x+yC，則稱碼C是線性碼。所有的這樣2k個碼字構成的集合稱為分組碼。須注意一點，nk個校驗元可以放在碼字中的任何位置，如果碼字前k位固定為信息碼，則這種分組碼稱為系統(tǒng)分組碼，如圖 3.1 所示。圖 3.1系統(tǒng)(n，k)分組碼碼字結構定義3.1.6將k位信息碼通過一定的規(guī)則添加nk個校驗元而形成長為n的碼字，如果所有這樣的碼字組成一個線性碼，則稱為(n，k)線性分組碼。定義3.1.7稱(n，k)線性分組碼的 為碼率。例3.1.2構造奇偶校驗碼。對X=0，1

59、的k維擴展信源Xk添加一位校驗位形成一個長為k+1的碼字，即且滿足關系：x1+x2+xk+xk+1=0(偶校驗) (3.1.6)即信息碼(x1x2xk)中如有偶數(shù)個1，則xk+1=0，如有奇數(shù)個1，則xk+1=1。或x1+x2+xk+xk+1=1(奇校驗) (3.1.7)即信息碼(x1x2xk)中如有偶數(shù)個1，則xk+1=1，否則xk+1=0。解僅討論偶校驗，所得結論適合于奇校驗。設發(fā)送碼字(x1x2xkxk+1)，接收矢量為(y1y2ykyk+1)，如果無錯，則接收矢量應滿足式(3.1.6)；如果產生奇數(shù)個錯誤，則y1+y2+ yk+yk+1=1， 因為一個碼元x發(fā)生錯誤意味著這個碼元變?yōu)閤

60、+1，為討論方便，不防設y1，y2，y2r+1發(fā)生錯誤，于是y1+y2+yk+yk+1=(1+x1)+(1+x2)+(1+x2r+1)+x2r+2+xk+xk+1=(2r+1)+(x1+x2+xk+xk+1)=2r+1=1 (mod2)說明不滿足式(3.1.6)，從而發(fā)現(xiàn)錯誤，但無法判別哪些碼元、多少碼元出錯，所以無糾錯能力。如果是偶數(shù)個錯誤，則有 y1+y2+yk+yk+1=2r+(x1+x2+xk+xk+1)=2r=0 (mod2)說明滿足式(3.1.6)，因而無法檢出錯誤。綜合起來，奇偶校驗碼能檢奇數(shù)個錯誤，不能檢偶數(shù)個錯誤，無糾錯能力，碼率為。定理3.1.1在一個線性分組碼中，碼的最小