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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、例子。例2.1.1設(shè)有離散無(wú)記憶信源，進(jìn)行以下兩種方式的二進(jìn)制編碼：(1) a100，a201，a310，a411；(2) a10，a210，a3110，a4111，試求兩種編碼方式的平均碼長(zhǎng)和編碼效率。解信源熵為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. 編碼原理利用概率匹配原則，編碼時(shí)，碼長(zhǎng)應(yīng)當(dāng)選擇滿(mǎn)足式(1.1.8)的整數(shù)，但并

18、非每次應(yīng)用都能獲得理想的編碼?？聪旅鎯蓚€(gè)例題。例2.1.2無(wú)記憶信源，利用概率匹配原則進(jìn)行編碼，并求出平均碼長(zhǎng)和編碼效率。解根據(jù)式(1.1.8)，字符a1、a2、a3、a4、a5對(duì)應(yīng)的碼長(zhǎng)分別為1、2、3、4、4，用二進(jìn)制符號(hào)來(lái)表示字符，即那么，平均碼長(zhǎng)為又因?yàn)樗?，獲得的編碼效率為=100%例2.1.2的二元碼的碼樹(shù)見(jiàn)圖2.1。圖 2.1例2.1.2編碼的碼樹(shù)例2.1.3無(wú)記憶信源，試?yán)酶怕势ヅ湓瓌t進(jìn)行編碼，并求出平均碼長(zhǎng)和編碼效率。解根據(jù)式(1.1.8)，字符a1、a2、a3、a4、a5、a6對(duì)應(yīng)碼長(zhǎng)分別為2、2、3、5、6、6，用二進(jìn)制符號(hào)來(lái)表示字符，即計(jì)算后，得到H(X)=1.83

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

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

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

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

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

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

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

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

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

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

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

30、5個(gè)子區(qū)間，即其次，初始化，即DL0=0，DH0=1，j=0最后，輸入字符進(jìn)行迭代運(yùn)算，見(jiàn)表2.3。表2.3例2.1.6字符流的算法編碼過(guò)程3. 譯碼方法因?yàn)槊恳蛔址晃ㄒ坏刂付艘粋€(gè)子區(qū)間，所以只需要根據(jù)碼字來(lái)反推是哪個(gè)子區(qū)間就能得到相應(yīng)的字符，從而實(shí)現(xiàn)譯碼。算術(shù)譯碼的過(guò)程如下。第一步，譯出字符流的第一個(gè)字符。第二步，譯出字符流的第二個(gè)字符。第三步，譯出字符流的第三個(gè)字符。如此繼續(xù)下去，直到最后一個(gè)字符譯出。歸納起來(lái)，算術(shù)編碼的譯碼流程圖如圖2.13所示。圖 2.13算術(shù)編碼的譯碼流程圖例2.1.7信源空間同于例2.1.6，譯出算術(shù)編碼b=0.7412261962890625。解譯碼過(guò)程見(jiàn)表

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

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

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

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

35、義2.2.4設(shè)信源發(fā)出長(zhǎng)為N的字符序列，其中，信宿接收字符序列為，其中，那么字符序列x與y間的失真函數(shù)為定義2.2.5設(shè)有信源X的N維擴(kuò)展信源XN，信宿Y的N維擴(kuò)展信宿YN，那么平均序列失真度為對(duì)于無(wú)記憶信道，與間有關(guān)系：(2.2.9) (2.2.8) 例2.2.2設(shè)有離散無(wú)記憶信源 ，無(wú)記憶信道轉(zhuǎn)移矩陣 ，求在誤碼失真函數(shù)下平均字符失真度和平均序列失真度。解設(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二維擴(kuò)展信源X2為由于無(wú)記憶信道 ，因此由式(1.1.2)得二維擴(kuò)展信道P2為

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

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

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

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

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

41、是預(yù)測(cè)的均方誤差應(yīng)當(dāng)最小。要使最小，必須合理選擇預(yù)測(cè)器系數(shù)ai。由(2.2.20) (2.2.21) 得到方程組使用自相關(guān)函數(shù)的定義，并考慮信源是平穩(wěn)隨機(jī)過(guò)程，于是有Ex(ni)x(nj)=R(|ij|) (2.2.23)式中，R()表示x(n)在相移為時(shí)的自相關(guān)函數(shù)。(2.2.22) 通常，采樣數(shù)據(jù)是有限的，因而R()只能通過(guò)有限個(gè)數(shù)據(jù)來(lái)估計(jì)。如果有M個(gè)采樣數(shù)據(jù)，則R()能被估計(jì)為又根據(jù)式(2.2.21)，預(yù)測(cè)的均方誤差為(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ù)壓縮編碼的實(shí)質(zhì)是去掉冗余消息，正交變換是完成這一任務(wù)的有力工具之一。正交變換主要有Karhunen-Love變換(簡(jiǎn)稱(chēng)K-L變換)、離散正弦變換(Discrete Sine Transform，DST)、 離散余弦變換(Discrete Cosine Transform，DCT)、離散Hartley變換、離散W變換等。1. K-L變換設(shè)x與y是兩個(gè)階為N1的列向量(信號(hào)矢量)，A是一個(gè)NN的矩陣，如果y=Ax，則稱(chēng)x被變換為y。如果變換矩陣A是正交矩陣，則稱(chēng)這個(gè)變換為正交變換。設(shè)Ai表示矩陣A的第i行的轉(zhuǎn)置，則A=A1，A2，ANT又因?yàn)锳是正

43、交矩陣，即ATA=AAT=I，所以A1=AT于是，由變換y=Ax得到(2.2.27) 設(shè)x的均值為0，現(xiàn)在我們希望用較少的y的分量來(lái)表示x，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)x的壓縮。例如，用y的前m個(gè)分量來(lái)表示數(shù)據(jù)x，這樣的表示只能是x的近似，記為，即誤差矢量為(2.2.28) (2.2.29) 當(dāng)然，在恢復(fù)信號(hào)x時(shí)，也只能用y的這前m個(gè)分量。因此，希望能合理選擇變換矩陣A使均方誤差達(dá)到最小。這里使用了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)提示我們，實(shí)現(xiàn)數(shù)據(jù)的壓縮的變換矩陣應(yīng)當(dāng)由信號(hào)的協(xié)方差矩陣的特征向量來(lái)構(gòu)成。將式(2.2.33)代入式(2.2.31)，得到均方誤差er為(2.2.34) (2.2.32) 2. DCT變換1) 一維DCT變換一維DCT變換由Ahmed和Rao首先給出，一維DCT變換能將信號(hào)x=(x(0)，x(1)，x(N1)T 變換到信號(hào)y=(y(0)，y(1)，y(N1)T，且滿(mǎn)足下列關(guān)系式：(2.2.35) 令那么，一維DCT變換的正變換可以簡(jiǎn)寫(xiě)為(2.2.37) (2.2.36) 寫(xiě)成矩陣形式，有y=CNx (2.2.38)式中：(2.2.39) 由于矩

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

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

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

48、進(jìn)壓縮效果不會(huì)有明顯提高。因此，在對(duì)靜止圖像進(jìn)行壓縮的JPEG技術(shù)標(biāo)準(zhǔn)中，建議的圖像塊的大小為88，其壓縮流程見(jiàn)圖2.20。圖 2.20靜止數(shù)字圖像的JPEG壓縮流程3. 小波變換1) 概念準(zhǔn)備設(shè)有函數(shù)f(t)(t+)，如果函數(shù)f(t)滿(mǎn)足：那么，稱(chēng)f(t)為絕對(duì)可積函數(shù)。設(shè)函數(shù)f(t)(t+)絕對(duì)可積，稱(chēng)(2.2.50) (2.2.51) 為f(t)的傅里葉變換。稱(chēng)為F()的傅里葉反變換。這里j2=1。設(shè)有函數(shù)f(t)(t1，b00，定義，稱(chēng)下面積分為離散小波變換。(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給出了幾個(gè)較小的i和k對(duì)應(yīng)的Harr小波伸縮平移族及尺度函數(shù)的波形。圖 2.27尺度函數(shù)波形與Harr小波伸縮平移族的幾個(gè)波形由式(2.2.80)不難看出，二尺度下的離散小波變換就是離散細(xì)節(jié)系數(shù)，Mallat塔式算法為計(jì)算提供了一套遞推公式。在式(2.2.81)中令i=0并用n來(lái)代替k，則有由式(2.2.88)，對(duì)(t)進(jìn)行伸縮平移操作，即用2itk代替t后，有(2.2.88) (2.2.89) 再令m=2k+n，則式(2.2.89)可以簡(jiǎn)化表示為將式(2.2.90)兩邊同乘以2i/2

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

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

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

53、即用Wi表示在的正交補(bǔ)空間，即且則有(2.2.102)(2.2.103)設(shè)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上的標(biāo)準(zhǔn)正交基，定義(2.2.104)f(x，y)可以在二維小波函數(shù)和二維尺度函數(shù)下展開(kāi)為式中：、 和分別為空間、 和上的小波展開(kāi)系數(shù)； 為空間Vi上的尺度展開(kāi)系數(shù)，即(2.2.105)(2.2.106)類(lèi)似于一維情況，二維離散小波變換也有快速M(fèi)allat分解算法，算法公式如下：(2.2.107)二維離散小波變換的快速M(fèi)allat重建算法遞推公式為(2.2.108)習(xí)

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

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

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

57、定義3.1.3設(shè)有碼C，稱(chēng)wt(x)=|i|xi0，i=1，2，n| (3.1.4)為碼字x的漢明重量。定義3.1.4設(shè)有碼C，0 =(0，0)，稱(chēng)wt(C)=minwt(x)|xC，x0 (3.1.5)為碼C的最小漢明重量。例3.1.1設(shè)有碼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設(shè)有碼C，如果，有x+yC，則稱(chēng)碼C是線(xiàn)性碼。所有的這樣2k個(gè)碼字構(gòu)成的集合稱(chēng)為分組碼。須注意一點(diǎn)，nk個(gè)校驗(yàn)元可以放在碼字中的任何位置，如果碼字前k位固定為信息碼，則這種分組碼稱(chēng)為系統(tǒng)分組碼，如圖 3.1 所示。圖 3.1系統(tǒng)(n，k)分組碼碼字結(jié)構(gòu)定義3.1.6將k位信息碼通過(guò)一定的規(guī)則添加nk個(gè)校驗(yàn)元而形成長(zhǎng)為n的碼字，如果所有這樣的碼字組成一個(gè)線(xiàn)性碼，則稱(chēng)為(n，k)線(xiàn)性分組碼。定義3.1.7稱(chēng)(n，k)線(xiàn)性分組碼的 為碼率。例3.1.2構(gòu)造奇偶校驗(yàn)碼。對(duì)X=0，1

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

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