數(shù)字信號處理畢業(yè)論文

1、<p><b>　　引言</b></p><p>　　數(shù)字信號處理（digital signal processing，DSP）是利用計算機(jī)或?qū)Ｓ锰幚碓O(shè)備，用數(shù)值計算的方法對信號進(jìn)行采集，交換，綜合，估值與識別等加工處理，借以達(dá)到提取信息和便于應(yīng)用的目的。數(shù)字信號處理系統(tǒng)具有靈活，精確，抗干擾強(qiáng)，設(shè)備尺寸小，造價低，速度快等突出優(yōu)點[1，2]，這些都是模擬信號處理系統(tǒng)無法比擬的。

2、</p><p>　　數(shù)字信號處理的起源可追溯到17世紀(jì)，當(dāng)時已提出了有限差分，數(shù)值積分和數(shù)值插值得方法。自20世紀(jì)60年代以來，隨著計算機(jī)和信息學(xué)科的飛速發(fā)展，數(shù)字信號處理技術(shù)應(yīng)運(yùn)而生并迅速發(fā)展，現(xiàn)已形成一門獨立的學(xué)科體系[3]。數(shù)字信號處理就是研究用數(shù)字的方法，正確快速地處理信號，提取各類信息的一門科學(xué)。在國際上，一般把1965年快速傅里葉變換（FFT ,Fast Fourier Transform）的問世，

3、作為數(shù)字信號信號處理這一新興學(xué)科的開端[3，4]。目前，伴隨著通信技術(shù)、電子技術(shù)計算機(jī)的飛速發(fā)展，數(shù)字信號處理的理論也在不斷地豐富的豐富和完善，各種新算法、新理論正在不斷地推出。在這近四十多年的發(fā)展中，數(shù)字信號處理自身已基本形成一套較完整的理論體系[4]。</p><p>　　傅立葉變換在數(shù)字信號處理中扮演著重要的角色[4]。在數(shù)字信號處理中,最重要也是最基本的表達(dá)信號的兩個變量是時間和頻率。通過傅立葉變換或反變

4、換,可以把時間域信號轉(zhuǎn)到頻率域或把頻率域信號轉(zhuǎn)到時間域,但又由于我們所要測量的信號大都是連續(xù)周期信號，不能直接在計算機(jī)上計算它的傅里葉變換，而DFT及其快速算FFT是一種時域和頻域都離散化的變換，能在計算機(jī)上實現(xiàn)信號的頻譜分析及其他方面的處理，因此DFT在數(shù)字信號處理和數(shù)字圖像處理中得到了廣泛的應(yīng)用，它建立了離散時域與離散頻域之間的關(guān)系[5]。如果信號或圖像處理直接在時域或空域上處理，計算就會隨著離散采樣點數(shù)的增加而激劇增加。使得計算機(jī)

5、計算量大，費(fèi)時，難以達(dá)到實時的要求[6]。因此，一般采用DFT方法，將輸入的數(shù)字信號首先進(jìn)行DFT變換，把時域中的卷積和相關(guān)運(yùn)算簡化為在頻域上的相成處理，然后進(jìn)行DFT反變換，恢復(fù)為時域信號。這樣大大減少計算量，提高處理速度。最重要的是DFT有多種快速算法，統(tǒng)稱為快速傅立葉變換,從而使信號的實時處理和設(shè)備的簡化得以實現(xiàn)。所以說，DFT不僅在理論上有重要意義，而且在各種信號的處理中也起核心作用。</p><p>　

6、　離散傅立葉變換（DFT）是復(fù)數(shù)域的運(yùn)算，盡管借助于FFT可以提高運(yùn)算速度，但在實際應(yīng)用，特別是實時處理中帶來了不便。由于實偶函數(shù)的傅立葉變換只含有實的余弦項，因此構(gòu)造了一種實域的變換---離散余弦變換(DCT)。</p><p>　　離散余弦變換（DCT）是N Ahmed等人在1974年提出的正交變換方法[5]。它是一種正交變換，它類似于離散傅里葉變換(DFT)，但是只使用實數(shù)。離散余弦變換相當(dāng)于一個長度大概是

7、它兩倍的離散傅里葉變換，這個離散傅里葉變換是對一個實偶函數(shù)進(jìn)行的。它的思想是將一個實函數(shù)對稱延拓成一個實偶函數(shù)，實偶函數(shù)的傅立葉變換也必然是實偶函數(shù)，連續(xù)函數(shù)和離散函數(shù)（CFT）都是基于這一原理。</p><p>　　在20世紀(jì)80年代至90年代初期，人們對DCT快速算法的研究較多，并且取得了巨大的成功。早在1977年，Chen?根據(jù)變換矩陣具有對稱性，利用稀疏矩陣分解法第一次提出DCT的快速算法。l984年B．

8、G．Led 提出了一種使用余割因子的DCT矩陣分解方法，得到Cooley-Tukey式的簡單結(jié)構(gòu)，受到廣泛重視。后來Duhamel將DCT看成是一種基于循環(huán)卷積的算法，并證明。對于一維的8點DCT，其乘法的理論下限值是l1次，C．Loeffler 具體實現(xiàn)了這種ll步乘法的算法。從此以后，一維DCT快速算法的研究進(jìn)展緩慢。2000年Trac．D．Trar提出了一種DCT的近似快速算法，在算法中也沒有用到乘法，但使用了移位運(yùn)算。在國內(nèi)，趙

9、耀等人也提出了一種“基于矩陣分解的DCT-I算法”[16] ，該方法也用到了l2次乘法。</p><p>　　離散余弦變換的提出雖然比快速傅立葉變換(FFT)晚，但其性能更接近于理想的KLT變換，并且由于KLT 到目前為止沒有發(fā)現(xiàn)有效的快速速算法，所以DCT在信號處理中得到了廣泛應(yīng)用[6]。離散余弦變換(DCT)域是數(shù)字信號處理技術(shù)中最常用的線性變換之一，和離散傅里葉變換一樣，也存在著快速算法。它的快速算法也是在

10、繼承完善DFT的基礎(chǔ)上不斷進(jìn)步的。但由于離散余弦變換(DCT)的變換核為實數(shù)的余弦函數(shù)，因此它的計算速度比變換核為復(fù)數(shù)指數(shù)的DFT要快。所以高效快速的離散余弦變換(DCT)得到了廣泛應(yīng)用，并且不斷激發(fā)人們對其快速算法的研究[7，8，9]。</p><p>　　基于以上研究現(xiàn)狀，如何改進(jìn)DCT的快速算法是本文的研究重點。本文首先系統(tǒng)闡述了離散傅立葉變換(DFT)的基礎(chǔ)理論及其快速算法FFT,然后詳細(xì)論述了離散余弦變

11、換的基本概念及其二維DCT快速算法的基本理論和實現(xiàn)方法，重點研究了一種改進(jìn)的離散余弦變換的快速算法，并推導(dǎo)了算法的進(jìn)行過程。本文著眼于如何改進(jìn)離散余弦變換的快速算法，分析了一維8點DCT快速算法的原理和二維8乘8DCT快速算法的理論，推導(dǎo)出了改進(jìn)的DCT快速算法的基本思路，并將此算法與其它算法做了比較，最后舉出具體實例，演繹了算法的進(jìn)行過程，結(jié)果表明該算法的運(yùn)算量明顯減少。</p><p>　　2 離散傅立葉變換

12、(DFT)及其快速算法(FFT)</p><p>　　DFT是先將信號在時域離散化，求其連續(xù)傅里葉變換后，再在頻域離散化的結(jié)果。它通常用于頻譜分析和濾波,它提供了使用計算機(jī)來分析信號和系統(tǒng)的一種方法，尤其是DFT的快速算FFT，在許多科學(xué)技術(shù)領(lǐng)域中得到了廣泛的應(yīng)用，并推動了數(shù)字信號處理技術(shù)的迅速發(fā)展[10]。</p><p>　　2.1 離散傅立葉變換(DFT)的定義和DFT性質(zhì)<

13、/p><p>　　在計算機(jī)上實現(xiàn)信號的頻譜分析及其他方面的處理工作時，對信號的要求是：在時域和頻域都是離散的，且都應(yīng)是有限長。離散傅立葉變換不是一個新的傅立葉變換形式，它實際上來自于DFS，只不過僅在時域，頻域各取一個周期，其實質(zhì)是有限長序列傅立葉變換的有限點離散采樣，從而開辟了頻域離散化的道路，使數(shù)字信號處理可以在頻域采用數(shù)字運(yùn)算的方法進(jìn)行，大大增加了數(shù)字信號處理的靈活性。</p><p>

14、　　（1） 正變換： (2.1.1)</p><p>　?。?） 反變換： (2.1.2)</p><p>　　離散傅立葉變換適用于有限長序列，和只有N個 值，但隱含周期性。是Z變換在單位圓上等距離的抽樣值，，是序列頻譜的采樣值，。 </p><p>　　假定與是長度為N的有限長序列，其各自的離散傅立葉變換分別為

15、 ， 。則DFT具有以下性質(zhì)：</p><p>　　(1) 線性 ，，為任意常數(shù) </p><p><b>　　(2) 循環(huán)移位</b></p><p>　　有限長序列的循環(huán)移位定義為：</p><p>　　表示的周期延拓序列的移位：</p><p>　　表示對移位的周期序列取主值序列。所

16、以仍然是一個長度為N的有限長序列。實際上可看作序列排列在一個N等分圓周上，并向左旋轉(zhuǎn)m位。 </p><p>　　序列循環(huán)移位后的DFT為：。實際上，利用的周期性，將代入DFT定義式，同樣很容易證明。 </p><p>　　同樣，對于頻域有限長序列X(k)的循環(huán)移位，有如下反變換特性：</p><p><b>　　(3) 循環(huán)卷積</b><

17、;/p><p><b>　　若 </b></p><p><b>　　則 </b></p><p><b>　　或 </b></p><p><b>　　同樣，若 </b></p><p><b>

18、;　　則 </b></p><p>　　所以，離散時間序列(或離散傅立葉變換)的循環(huán)卷積與離散傅立葉變換(或離散時間序列)的乘積相對應(yīng)。這就說明循環(huán)卷積的運(yùn)算可利用離散傅立葉變換轉(zhuǎn)換成乘積實現(xiàn)。</p><p>　　(4) 有限長序列的線性卷積與循環(huán)卷積(循環(huán)卷積的應(yīng)用)</p><p>　　有限長序列的線性卷積等于循環(huán)卷積，而不產(chǎn)生混淆的必要

19、條件是延拓周期 L≥N+M-1，其中N、M為兩個有限長序列的長度。 </p><p>　　(5) 奇偶對稱特性</p><p>　　時域序列奇對稱時，其也奇對稱，即若 ，則。</p><p>　　時域序列偶對稱時，其也偶對稱，即若 ，</p><p><b>　　則。</b></p><p>&l

20、t;b>　　(6) 虛實特性</b></p><p><b>　　若 ，則 。</b></p><p>　　當(dāng)為純實數(shù)序列時，＝→共軛偶對稱。 </p><p>　　當(dāng)為純虛數(shù)序列時，＝→共軛奇對稱。</p><p>　　2.2 快速傅立葉變換定義和算法思路</p><p>　

21、　自從1965年土基和庫利在《計算機(jī)數(shù)學(xué)》(Math.Computation,Vol.19,1965)雜志上發(fā)表了著名的《機(jī)器計算傅立葉變換的一種算法》論文后，桑德--圖基等快速算法相繼出現(xiàn)，又經(jīng)人們改進(jìn)，很快形成一套高效的運(yùn)算方法，這就是現(xiàn)在的快速傅立葉變換，簡稱FFT(Fast Fourier Transform)。這種算法使DFT的運(yùn)算效率提高1~2個數(shù)量級，為數(shù)字信號處理技術(shù)應(yīng)用于各種信號的實時處理創(chuàng)造了良好的條件，大大推動了數(shù)

22、字信號處理的發(fā)展[11]。</p><p>　　快速傅立葉變換(FFT)是離散傅立葉變換DFT (Discrete Fourier Transform)的快速算法，它就是利用的特性，逐步地將N點序列分解成較短的序列，計算短序列的DFT，然后組合成原序列的DFT，使運(yùn)算量顯著減少。FFT是DFT的快速計算方法，DFT是連續(xù)傅立葉變換的離散形式。 </p><p>　　=，=0，1，…N-1

23、 (2.2.1)</p><p>　　式中， =，稱為蝶形因子。此式實際上就是N點的DFT。由(2.2.1)式可以看出，計算所有的的運(yùn)算量很大。FFT算法利用了蝶形因子內(nèi)在的性質(zhì)，從而加快了運(yùn)算的速度。的以下三種性質(zhì)在FFT運(yùn)算中得到了應(yīng)用：</p><p>　　性質(zhì) 1： 的周期性 =</p><p&g

24、t;　　性質(zhì) 2： 的對稱性 =</p><p>　　性質(zhì) 3： 的可約性 =，=</p><p>　　FFT算法將長序列的DFT分解為短序列的DFT。N點的DFT先分解為2個點的DFT，每個點的DFT又分解為點的DFT，等等。最小變換的點數(shù)即所謂的“基數(shù)(Radix)"，因此，基數(shù)為2的算法的最小變換(或稱蝶形)是2點DFT。一般的，對N點FFT，對應(yīng)于N個輸入樣值

25、，有N個頻域樣值與之對應(yīng)。</p><p>　　一般而言 ，F(xiàn)FT算法可以分為時間抽取(DIT)FFT和頻率抽取(DIF)FFT兩大類。</p><p>　　2.2.1 時間抽取(DIT)FFT</p><p>　　時間抽取算法是將N點的輸入序列按照偶數(shù)和奇數(shù)分解為偶序列和奇序列兩個序列： 偶序列：x(0)， x(2)， x(4)，…，x(N-2)</p>

26、;<p>　　奇序列：x(1)， x(3) ，x(5)，…，x(N-1)</p><p>　　因此，的N點FFT可以表示 =+ (2.2.1.1)</p><p>　　因為 ===</p><p>　　所以 =+，</p><p><b>　　令，&

27、lt;/b></p><p>　　則有 =+ (2.2.1.2)</p><p>　　由于和的周期為，因此 k=0，1，…，。</p><p>　　由 =- 可知 =- (2.2.1.3)</p><p>　　用（2.2.1.

28、2）,(2.2.1.3)兩式分別用來計算和的。以同樣的方式進(jìn)一步抽取，就可以得到N/4的DFT，重復(fù)這個抽取過程，就可以使N點的DFT用一組2點的DFT來計算。在基數(shù)為2的FFT中，設(shè)N=，則總共有M級運(yùn)算，每級中有N/2個2點FFT蝶形運(yùn)算，因此，N點FFT總共有個蝶形運(yùn)算。</p><p>　　圖2.1 時間抽取算法碟形運(yùn)算圖</p><p>　　基2DIT的蝶形如圖2.1所示。設(shè)蝶形

29、的輸入分別為A和B ，輸出分別為C和D，則有 ，</p><p>　　圖2.2 N=8點DIT-FFT算法流圖</p><p>　　2.2.2 頻率抽取(DIF)FFT</p><p>　　頻率抽取FFT算法是在頻域里把序列分解為奇、偶的形式來進(jìn)行計算，頻率抽取FFT算法首先將輸入序列按照自然順序分為前半部分和后半部分：&l

30、t;/p><p>　　偶序列：x(0)，x(2)，x(4)，…，x()</p><p>　　奇序列：x(1)，x(3)，x(5)，…，x()</p><p>　　因此，的N點FFT可以表示為：=+= (2.2.1.4)</p><p>　　k為偶數(shù)時： =，k=0，1，…()</p><p>　　k為奇數(shù)時：= ，k

31、=0，1，…()</p><p>　　因為 </p><p><b>　　令　=，</b></p><p><b>　　則有： </b></p><p><b>　?。?lt;/b></p><p><b&g

32、t;　?。?lt;/b></p><p>　　以同樣的方式，就可以得到N/4點的DFT，重復(fù)這個過程， N點的DFT用一組2點的DFT來計算。設(shè)N=，則共有M級運(yùn)算。DIF的基2蝶形運(yùn)算如圖3所示。</p><p>　　圖2.3 基2的DIF-FFT蝶形運(yùn)算</p><p>　　圖2.4 8點DIF-FFT的信號流程圖</p><p>

33、　　設(shè)蝶形的輸入分別為A和B，輸出分別為C和D， 則有</p><p><b>　　，</b></p><p>　　則一個8點DIF-FFT的信號流程圖如圖2.4。</p><p>　　從圖2.1和圖2.3可以看出，DIT和DIF兩種FFT算法的區(qū)別是旋轉(zhuǎn)因子出現(xiàn)的位置不同，DIT中在輸入端而DIF中在輸出端。除此之外，兩種方法是一樣的。<

34、;/p><p>　　3 離散余弦變換的基本理論</p><p>　　離散余弦變換（DCT for Discrete Cosine Transform）是一種正交變換，它類似于離散傅立葉變換 (DFT),但它只使用實數(shù)。離散余弦變換相當(dāng)于一個長度大概是它兩倍的離散傅里葉變換，這個離散傅里葉變換是對一個實偶函數(shù)進(jìn)行的(因為一個實偶函數(shù)的傅里葉變換仍然是一個實偶函數(shù))，在有些變形里面需要將輸入或者

35、輸出的位置移動半個單位(DCT有8種標(biāo)準(zhǔn)類型，其中4種是常見的)。</p><p>　　最常用的一種離散余弦變換的類型是下面給出的第二種類型，通常我們所說的離散余弦變換指的就是這種。它的逆，也就是下面給出的第三種類型，通常相應(yīng)的被稱為"反離散余弦變換"，"逆離散余弦變換"或者"IDCT"。有兩個相關(guān)的變換，一個是離散正弦變換 (DST for Discr

36、ete Sine Transform),它相當(dāng)于一個長度大概是它兩倍的實奇函數(shù)的離散傅立葉變換；另一個是改進(jìn)的離散余弦變換 (MDCT for Modified Discrete Cosine Transform),它相當(dāng)于對交疊的數(shù)據(jù)進(jìn)行離散余弦變換[13]。</p><p>　　3.1 一維離散余弦變換的各種定義</p><p>　　余弦變換是傅里葉變換的一種特殊情況。在傅里葉級數(shù)展開

37、式中，如果被展開的函數(shù)是實偶函數(shù)，那么，其傅里葉級數(shù)中只包含余弦項，再將其離散化由此可導(dǎo)出余弦變換，或稱之為離散余弦變換（DCT）。下圖(3.1),(3.2)分別給出偶對稱和奇對稱的?！　?</p><p>　　圖3.1 偶對稱的 </p><p><b>　　圖3.2 奇對稱的</b></p><p>　　設(shè)一維離散函數(shù)f(x)，x=0

38、，1，…，N-1，把f(x)擴(kuò)展成為偶函數(shù)的方法有兩種，以N=4為例，可得出如圖3.1和圖3.2所示的兩種情況。圖3.1稱偶對稱，圖3.2稱奇對稱，從而有偶離散余弦變換（EDCT）和奇離散余弦變換（ODCT）。由圖1和2看出，對于偶對稱擴(kuò)展，對稱軸在x=處。</p><p>　　= (3.1.1)　　采樣點數(shù)增到2N。　　</p><p

39、>　　對于奇對稱擴(kuò)展，對稱軸在x=0處。</p><p>　　=　 (3.1.2)　　采樣點數(shù)增到2N－1。由離散傅里葉變換定義出發(fā)，對公式（3.1.1）作傅里葉變換，以表示，則得=　 　 　　

40、 </p><p><b>　　(3.1.3)</b></p><p><b>　　式中，　　</b></p><p>　　當(dāng) u=0, =</p><p><b>　　當(dāng)　　</b></p><p>　　當(dāng) ，，且=2[]　考慮正交變換公式與逆變換

41、公式的對稱性，令 (3.1.4) 　　　 　　式中 (3.1.5)</p><p><b>　　(3.1.6)　　</b></p><p>　

42、　(3.1.7) </p><p>　　定義式（3.1.4）和式（3.1.5）為離散偶余弦正變換公式；式（3.1.6）和式（3.1.7）為離散偶余弦變換核公式?！　‰x散偶余弦逆變換公式為C(0)+C(u) 　　 (3.1.8)</p><p>　　x = 0，1，…，N-1　　將公式（3.1.4）和公式（3.1

43、.5）合并、化簡，可得到一維離散偶余弦正變換公式</p><p>　　即C(u)=E(u) 　　 式中　　</p><p>　　當(dāng)u=0時，E(u)= ； 當(dāng)時， </p><p>　　總上述可歸納：若給定序列，則其離散有限傅里葉變換為：</p><p><b>　?。?.1.9）</b></p>&

44、lt;p>　　當(dāng)時，為實數(shù)，則其離散余弦變換定義為</p><p><b>　　（3.1.10）</b></p><p><b>　?。?.1.11）</b></p><p>　　顯然，其變換的核函數(shù) （3.1.12） </p><p>　　是實數(shù)，式中系數(shù)

45、 （3.1.13）</p><p>　　這樣，若是實數(shù)，那么它的DCT變換也是實數(shù)。對傅里葉變換，若是實數(shù)，其DFT一般為復(fù)數(shù)。由此可以看出，DCT避免了復(fù)數(shù)運(yùn)算。將（3.1.9）式寫成矩陣，有 （3.1.14）</p><p>　　式中，都是的向量，是的變換矩陣，其元素

46、由（3.1.12）式給出。當(dāng)時，有</p><p>　?。?.1.13） </p><p>　　可以證明，的行、列向量均有如下的正交關(guān)系：</p><p>　　可見變換矩陣是歸一化的正交陣，DCT是正交變換，由此立即得到DCT的反變換關(guān)系：</p><p><

47、;b>　?。?.1.14）</b></p><p><b>　　即 </b></p><p><b>　?。?.1.15）</b></p><p>　　當(dāng)k 為其他值時,為了實現(xiàn)實數(shù)域運(yùn)算,對其進(jìn)行改造,將信號以原點為中心對稱增加一倍,從N個擴(kuò)展到 2N個，并對相位也進(jìn)行修改,除了N 改2N 外,還要加

48、上0+ 與0- 的相位,他們分別為與，則式（3.1.1）應(yīng)該為式（3.1.2），即：</p><p>　　由于信號的安排為，并且，故式（3.1.1）展開相加之后，所有項都抵消，而可化簡為：</p><p><b>　　(3.1.16)</b></p><p><b>　?。?.1.17）</b></p>&l

49、t;p>　　這就是離散余弦變換的關(guān)系式。</p><p>　　從形式上來看，離散余弦變換一個線性的可逆的函數(shù): (其中R是實數(shù)集, 或者等價的說一個的方陣。離散余弦變換有幾種變形的形式，它們都是根據(jù)下面的某一個公式把 n 個實數(shù)變換到另外n個實數(shù)的操作。下面給出離散余弦變換的四種類型：</p><p>　　DCT-I =(+)+ []</p><p>

50、　　DCT-II =[]</p><p>　　DCT-III =+[]</p><p>　　DCT-IV =[]</p><p>　　3.2 二維離散余弦變換的定義及反變換</p><p>　　DCT變換被認(rèn)為是一種準(zhǔn)最佳變換，具有壓縮比高、誤碼率小，信息集中能力和計算復(fù)雜

51、性綜合效果好等優(yōu)點[10]。一個M×N矩陣A 的二維DCT定義如下：</p><p><b>　?。?.2.1）</b></p><p>　　其中： </p><p>　　式中， F( u ,v )為空間域圖像在( x, y )處的灰度值，x ，y=0，1，2， ，N-1， f(x ,y)為變換系數(shù)矩陣，u ,v =

52、0，1，2， ，N-1，N為數(shù)字圖像的寬度和高度。</p><p>　　二維離散余弦反變換公式如下：</p><p>　?。?.2.2） </p><p>　　其中：為空間域采樣值；為頻率域采樣值。通常，數(shù)字圖像用象素方陣表示，即，在這種情況下，二維離散余弦的正反變換可簡化為：</p><p><b>　　（3.2.3）<

53、/b></p><p><b>　?。?.2.4）</b></p><p><b>　　其中：</b></p><p>　　4 離散余弦變換（DCT）的快速算法</p><p>　　離散余弦變換也象DFT一樣具有快速實現(xiàn)的算法。對于n個點的DCT變換，其算法復(fù)雜度為O()。</p>

54、;<p>　　4.1 一維離散余弦變換的快速算法</p><p>　　DCT首先由N．Ahmad等人于1974年提出的[13]，設(shè)數(shù)據(jù)序列x(n)，n=0，1 ，N-1，則X(n)的DCT定義為：</p><p>　　,k=0,1, ,N-1</p><p><b>　　(4.1.1)</b></p><p&g

55、t;　　在這里，Y(k)是第K個DCT系數(shù)。</p><p>　　若寫成矩陣形式，則有：其中表示DCT變換矩陣，離散余弦逆變換（IDCT）定義為： (4.1.2)</p><p>　　4.2 二維88快速DCT的基本原理及其實現(xiàn)方法</p><p>　　離散余弦變換（Discrete Cos

56、ine Transform ,DCT）是一種最接近統(tǒng)計最優(yōu)變換K--L變換的正交變換，已有的各種成熟的壓縮標(biāo)準(zhǔn)如JPEG,MPEG1/2/4,H.26X以及HDTV等都無一例外地采用基于DCT/IDCT的壓縮編碼。但通常的DCT運(yùn)算量比較大，為了降低DCT算法的運(yùn)算量，提高運(yùn)算速度，人們提出了多種快速計算DCT的方法。例如在2D-DCT快速算法中，Duhame和Guillemot提出了一種直接多項式變換法；Vetterli提出了一種間接

57、算法，用附加一些旋轉(zhuǎn)方法將2D-DCT映射為2D-DFT,再用多項式計算2D-DFT；Wu和Paoloni提出了一種矩陣分解法，利用Kronecker積將N乘N的DCT轉(zhuǎn)化為N的平方點的一維變換，然后對此一維變換矩陣進(jìn)行分解，減少矩陣中所包含的乘法次數(shù)等等。后來提出的快速算法幾乎都是在上面提出的集中快速算法的基礎(chǔ)上的改進(jìn)，以及針對一些特殊情況的快速算法。在DCT的快速算法中，Loeffer,Ligtenberg和Moschytz在198

58、9年提出的算法最有代表性。在圖像和視頻壓縮中，二維8乘8快速DCT變換是使用最普遍</p><p>　　在此主要介紹二維88快速DCT的基本原理及其實現(xiàn)方法。由于二維8乘8快速DCT的算法是通過計算行方向的一維DCT和列方向的一維DCT來實現(xiàn)的，因此首先介紹一維8點快速DCT算法。</p><p>　　4.2.1 一維8點快速算法DCT</p><p>　　在20世

59、紀(jì)80年代，DCT算法受到了人們的關(guān)注，人們提出了多種針對一維8點DCT的算法。下表4.1給出七種不同的快速算法的比較，這些算法都是針對8點的一維DCT，各算法以其作者進(jìn)行標(biāo)志。</p><p>　　表4.1 各種快速DCT快速算法的比較</p><p>　　若把DCT看做一種循環(huán)旋轉(zhuǎn)運(yùn)算，則對于8點的一維DCT算法，理論上最少需要11次乘法和29次加法。Loeffler的算法是達(dá)到這一

60、極限的算法。直接計算DCT需要64次乘法和56次加法，而用Loeffler的快速算法來計算以維DCT只需要11次乘法和29次加法，可見Loeffler 快速算法在很大程度上減少了計算量。</p><p>　　Loeffler快速算法是一種極具有代表性的一維8點快速DCT算法，下面詳細(xì)介紹Loeffler快速算法。</p><p>　　Loeffler快速算法的基本原理。快速DCT算法把一維

61、DCT算法分為4級，由于各級之間的輸入輸出具有依存關(guān)系，4級操作必須串進(jìn)行，而各級內(nèi)部的運(yùn)算可采用并聯(lián)方式來進(jìn)行處理。它有三種運(yùn)算因子：蝶形因子，旋轉(zhuǎn)因子和倍乘因子。下圖是Lo </p><p>　　圖4.1 Loeffler算法流程圖 </p><p>　　(a)蝶形因子 （b）旋轉(zhuǎn)因子 (c)倍乘因子</p>&

62、lt;p>　　圖4.2 Loeffler快速DCT算法中的三種因子</p><p>　　上圖中表示Loeffler快速DCT算法中的三種，其中,或表示輸入，，或表示輸出。幾種運(yùn)算因子之間的關(guān)系介紹如下。</p><p>　　ⅰ蝶形因子的輸入輸出關(guān)系是: </p><p>　　由上式可見，完成一個蝶形因子需要2次加法運(yùn)算。</p><p>

63、;　?、⑿D(zhuǎn)因子的輸入輸出關(guān)系是：</p><p>　　根據(jù)上面的公式，直接計算旋轉(zhuǎn)因子需要4次乘法和2次加法。為了減少運(yùn)算量，對上面描述旋轉(zhuǎn)因子輸入輸出關(guān)系的等式做變換，變形為:</p><p>　　采用上面變形后的等式，只需要3次乘法和3次加法就可以完成一個旋轉(zhuǎn)因子的運(yùn)算。等式變換后使旋轉(zhuǎn)因子的計算量減少。</p><p>　?、?倍乘因子的輸入輸出關(guān)系是：&l

64、t;/p><p>　　倍乘因子只需要一次乘法。</p><p>　　以上分析可得出結(jié)論：計算蝶形因子需要2次加法操作，計算旋轉(zhuǎn)因子需要3次乘法因子和3次加法操作，計算倍乘因子需要1次乘法操作。而 Loeffler的快速算法流程圖中共存在10個蝶形因子，3個旋轉(zhuǎn)因子和2個倍乘因子，因此，總的乘法次數(shù)是33+2=11，總的加法次數(shù)是102+33=29。</p><p>　　

65、(2) Loeffler 快速算法DCT算法的計算 前面介紹了Loeffler快速算算法的運(yùn)算流程，并且對其在運(yùn)算過程中所需要的乘法和加法操作的次數(shù)，也就是運(yùn)算量進(jìn)行了分析。下面來推導(dǎo)一維DCT快速算法的8個系數(shù)。進(jìn)一步驗證Loeffler快速算法的正確性。按DCT系數(shù)y(0),y(4),y(2)y(6),y(7),y(3),y(5),y(1)的順序來排列。偶系數(shù)y(0) ,y(4),y(2).y(6), 按照位序增序排序，而奇系數(shù)

66、y(7),y(3),y(5),y(1) 按倒位序降序排列。按這種順序?qū)⒚總€DCT系數(shù)的表達(dá)式化為流程圖中三種因子的組合。</p><p>　　給出一維8點DCT的公式為：</p><p><b>　　F（u）=</b></p><p><b>　　式中 </b></p><p>　　對于一維D

67、CT的系數(shù)F(0),F(4),根據(jù)一維8點DCT的公式，有</p><p><b>　　F(0)= =</b></p><p><b>　　F(4)= </b></p><p>　　={[]+[]}-{[]+[]}</p><p>　　y(0)和y(4)都可以表示為3級蝶形因子的級聯(lián)。</p&

68、gt;<p>　　同理，其余的6個系數(shù)也可以得出：</p><p><b>　　F(2)= </b></p><p>　　={[]-[]}+{[]-]}</p><p><b>　　F(6)= </b></p><p>　　={[]-[]}-{[]-]}</p><

69、p><b>　　F(7)= </b></p><p>　　={[]+[]}+{-]+[]}-{-[]+[]-[-]+[]}</p><p><b>　　F(3)= </b></p><p>　　={-[]+[]}-{[]+[]}</p><p><b>　　F(5)= </b&

70、gt;</p><p>　　={[]+[]}-{-[]+[]}</p><p><b>　　F(1)= </b></p><p>　　={[]+[]}+{-]+[</p><p>　　]}-{-[]+[]-[-]+[]}</p><p>　　由上面的DCT系數(shù)的表示公式可以看出，y(0)和y(4)

71、都可以表示為3級蝶形因子的級聯(lián)；y(2)和y(6)表示為2級蝶形因子與一級旋轉(zhuǎn)因子的級聯(lián)；y(7)和y(1) 表示為1級蝶形運(yùn)算與1級旋轉(zhuǎn)運(yùn)算級聯(lián)后，再級聯(lián)2級蝶形運(yùn)算；y(5)和y(3)表示為1級蝶形，1級旋轉(zhuǎn)，1級蝶形和一級倍乘運(yùn)算的依次順序級聯(lián)。</p><p>　　綜上所述，一維8點DCT的8個系數(shù)利用一維8點DCT的公式來計算，其結(jié)果可以轉(zhuǎn)化為三種因子的級聯(lián)形式，從而證明一維8點DCT算法的流程圖是正確

72、的。</p><p>　　4.2.2 二維 8乘8 DCT 快速算法</p><p>　　為了減弱或消除圖像數(shù)據(jù)的空間相關(guān)性，可以運(yùn)用二維DCT變換，將圖像 f( x ,y )從空間域轉(zhuǎn)換到DCT變換域。</p><p>　　二維8乘8快速DCT算法及其逆變換IDCT的計算公式定義如下：</p><p>　　F（u，v）=C（u）C（v）&

73、lt;/p><p>　　F(x ,y)= F( u ,v ) </p><p><b>　　式中</b></p><p>　　f( x ,y )表示像素的值，F(xiàn)( u ,v )表示DCT系數(shù)。對于二維DCT的計算方法很多或進(jìn)行行--列方法運(yùn)算。直接方法是二維的數(shù)據(jù)；而行--列方法是根據(jù)DCT/IDCT的正交可分解性，通過對輸入矩陣先行行方向的一維D

74、CT,再作列方向的一維 DCT 。即將 N乘N 數(shù)據(jù)按行（或列）方向進(jìn)行N 個一維DCT計算，產(chǎn)生中間數(shù)據(jù)矩陣再按列（行）方向進(jìn)行N 個一維DCT計算，最后得到二維DCT的結(jié)果。</p><p>　　下圖（4.3）所描述的是二維離散余弦變換（2D-DCT）和二維離散余弦逆變（2D-IDCT）的處理流程。在圖中有兩個一維DCT/IDCT 的處理模塊和一個轉(zhuǎn)置RAM模塊。輸入數(shù)據(jù)首先要經(jīng)過串-并轉(zhuǎn)換模塊，把串行輸入的

75、數(shù)據(jù)轉(zhuǎn)換為并行的形式；再經(jīng)過第一個DCT/IDCT處理模塊，按行方向進(jìn)行一維DCT/IDCT；然后產(chǎn)生的中間數(shù)據(jù)輸入到轉(zhuǎn)置RAM中；將轉(zhuǎn)置后的數(shù)據(jù)輸入到第二個DCT/IDCT處理模塊，按列方向進(jìn)行一維DCT/IDCT；最后數(shù)據(jù)再經(jīng)過并-串轉(zhuǎn)換模塊，把并行的數(shù)據(jù)變?yōu)榇械臄?shù)據(jù)。</p><p>　　圖4.3 二維DCT/IDCT處理流程圖</p><p>　　上圖描述的二維DCT快速算法的處

76、理流程中有三種模塊：DCT/IDCT處理模塊，轉(zhuǎn)置RAM模塊，串-并（并-串）轉(zhuǎn)換模塊。串-并模塊是實現(xiàn)數(shù)據(jù)的串-并轉(zhuǎn)換模塊的功能與串-并轉(zhuǎn)換模塊的功能正好相反，即把沒收到的一組8個并行數(shù)據(jù)轉(zhuǎn)換成8個串行數(shù)據(jù)輸出。轉(zhuǎn)置RAM模塊對兩個一維DCT處理模塊之間的中間數(shù)據(jù)進(jìn)行轉(zhuǎn)置處理。DCT/IDCT模塊用來對輸入的數(shù)據(jù)做DCT/IDCT處理。針對二維8乘8快速DCT的計算，DCT模塊完成一維8點DCT計算，采用Loeffler的一維快速DC

77、T算法。</p><p>　　5 一種新的改進(jìn)型離散余弦快速算法</p><p>　　改進(jìn)型的離散余弦變換（Modified discrete cosine transform）作為良好的時頻分析工具，在信號處理的實時性上顯得至關(guān)重要，為此需要研究其快速算法。下面論述基于快速DCT變換的MDCT快速算法的原理。</p><p><b>　　5.1 算法原理

78、</b></p><p>　　改進(jìn)型離散余弦變換（MDCT ：Modified Discrete Cosine Transform）的定義為： （5.1.1）</p><p>　　式中，。式（5.1.1）與DCT相比多了一個常數(shù)為此首先簡化該式，分離余弦函數(shù)中包含的信息。利用三角公式中的余弦和積關(guān)系：2cosAcosB=cos(A+B)+cos(A-B)

79、。</p><p><b>　　令 </b></p><p>　　對大括號進(jìn)一步調(diào)整 </p><p>　　其中（推導(dǎo)見附錄1）所以式（5.1.1）可改寫為如下形式：</p><p><b>　?。?.1.2）</b></p><p><b>　　其中， <

80、/b></p><p>　　由此，對X(k)的計算轉(zhuǎn)化為系數(shù)Z(k)的計算，明顯地,Z(k)具有對稱性，Z(n-1-k)=Z(k)，所以只需計算一半系數(shù)，即 對Z(k)分離其奇偶序號項</p><p>　　對后半部分進(jìn)一步解析，令</p><p><b>　?。ㄍ茖?dǎo)見附錄2）</b></p><p><b&g

81、t;　　其中 </b></p><p>　　再令 于是Z(k)可重寫為：</p><p><b>　?。?.1.3）</b></p><p>　　至此，本文將N點的轉(zhuǎn)化為兩個點的的計算，其遞推公式（5.1.3），這樣的遞推形式與傳統(tǒng)將N點DCT分解為一個點DCT和一個點DST的線性組合不同，其子變換仍為的形式，便于編程；這與FFT相

82、似，但所有運(yùn)算皆為實數(shù)運(yùn)算。</p><p><b>　　5.2 舉例</b></p><p>　　以N=8為例，具體演繹算法的進(jìn)行過程。依據(jù)下面的過程可以類推N=(n為大于3的自然數(shù))。</p><p><b>　　預(yù)處理</b></p><p>　　z(0)=x(0)-x(3)</p>

83、;<p>　　z(1)=x(1)-x(2)-x(4) </p><p>　　z(2)=x(2)-x(1)-x(5)</p><p>　　z(3)=x(3)-x(0)-x(6) </p><p>　　z(4)=x(4)-x(7)</p><p><b>　　z(5)=x(5)</b&g

84、t;</p><p>　　z(6)=x(6) </p><p><b>　　z(7)=x(7)</b></p><p>　　圖5.1 奇偶分序數(shù)組示意圖</p><p>　　構(gòu)造奇偶分序組（見圖5.1）</p><p><b>　　遞推（見圖5.2）</b></

85、p><p>　　圖5.2 遞推示意圖</p><p><b>　　后處理</b></p><p><b>　　結(jié)論 </b></p><p>　　除預(yù)處理操作復(fù)雜外，本算法的結(jié)構(gòu)簡單，遞推中半蝶形運(yùn)算的所有操作皆為實數(shù)，再加上系數(shù)具有對稱性，因此其該乘法加法次數(shù)都較基于FFT的算法少。由上述分析可知，

86、其實數(shù)加法和乘法次數(shù)分別為和，與文獻(xiàn)[ 14，15]相比，具體數(shù)據(jù)見表5.1。</p><p>　　表5.1算法實數(shù)操作比較</p><p>　　由表5.1可知基于DCT變換的快速算法的運(yùn)算量明顯減少。并將此算法的結(jié)果與其它算法的結(jié)果作了比較，結(jié)果表明：算法速度提高了，雖然算法的結(jié)果仍是正確的。</p><p><b>　　6 結(jié)束語</b>&

87、lt;/p><p>　　DCT的快速算法有多種，基于多項式變換的DCT快速算法，基于查表的無乘法DCT快速算法，利用循環(huán)卷積實現(xiàn)的DCT快速算法等，本文以離散余弦變換的快速算法的基本理論為基礎(chǔ)，提出了改進(jìn)型離散余弦變換的快速算法，并用具體實例進(jìn)行驗證，結(jié)果表明此算法可行，說明此算法在一定程度上減少了運(yùn)算量，尤其是減少了將近三分之一的乘法的運(yùn)算次數(shù)。但是，該算法過程中的預(yù)處理操作比較復(fù)雜，所以在運(yùn)算簡便方面不是太理想。

88、由于改進(jìn)型的DCT是良好的時頻分析工具，其快速算法也顯得至關(guān)重要。在以后的時間里，我將繼續(xù)研究，完善基于快速DCT變換的MDCT快速算法。</p><p><b>　　[參考文獻(xiàn)]</b></p><p>　　[1] 胡廣書， 數(shù)字信號處理導(dǎo)論[M]. 北京: 清華大學(xué)出版社, 2005.</p><p>　　[2] 丁玉美, 高西全. 數(shù)字信

89、號處理[M]. 西安: 西安電子科技大學(xué)出版社,1994.[3] 奧本海姆著. 劉樹棠，黃建國譯. 離散時間信號處理[M]. 西安: 西安交通大學(xué)出版社 </p><p><b>　　2001.</b></p><p>　　[4] 朱秀昌, 劉峰, 胡棟. 數(shù)字圖像處理與圖像通信[M]. 北京: 北京郵電大學(xué)出版社,2002.</p><

90、;p>　　[5] Kenneth R.Castleman 著, 朱志剛, 石定機(jī)等譯. 數(shù)字圖像處理[M]. 北京: 電子工業(yè)出版社,2002.</p><p>　　[6] 李在銘. 數(shù)字圖像處理壓縮與識別技術(shù)[M]. 成都: 電子科技大學(xué)出版社, 2000.</p><p>　　[7] 谷獲隆嗣（日本）. 快速算法與并行信號處理[M]. 北京: 科學(xué)出版社, 2003.</p

91、><p>　　[8] K.R. Rao and P. Yip, 離散余弦變換 : 算法、優(yōu)點和應(yīng)用 (Discrete Cosine Transform: Algorithms, Advantages, Applications) (Academic Press, Boston, 1990). </p><p>　　[9] Syed Ali Khayam , Department of Ele

92、ctrical & Computer Engineeri . Michigan State University . The Discrete Cosine Transform(DCT):Theory and , Application March 10th 2003.</p><p>　　[10] Gilbert Strang Massachusetters Institute of Tec

93、hnology . Discrete Cosine Transform(DCT).</p><p>　　[11] 何小敏, 王正勇. 數(shù)字圖像通信及其應(yīng)用[M]. 成都: 四川大學(xué)出版社, 2006.</p><p>　　[12] 陳禾, 毛志剛, 葉以正. DCT快速算法及其VLSI實現(xiàn)[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 1998.</p><p>　　[13] 徐盛

94、, 胡劍凌, 陳 健. 一種新的MDCT快速算法[J]. 上海交通大學(xué)，200030, 2000. 12.</p><p>　　[14] 杜相文, 陳賀毒, 趙巖. 基于查表的無乘法DCT快速算法[J].吉林大學(xué)南嶺校區(qū)通信工程學(xué)院測控技術(shù)與儀器系，長春130025 ；2．吉林大學(xué)通信工程學(xué)院通信工程系，長春130012 2004 10.</p><p>　　[15] 殷瑞祥. 基于多

95、項式變換的2D—DCT快速算法[J]. 華南理工大學(xué)電子與信息工程學(xué)院，廣東廣州510640, 2001 9.</p><p><b>　　附 錄</b></p><p><b>　　附錄1</b></p><p><b>　　=</b></p><p><b>　

96、　=</b></p><p><b>　　=</b></p><p><b>　　=</b></p><p><b>　　=</b></p><p><b>　　=</b></p><p><b>　　=<

97、;/b></p><p><b>　　附錄2</b></p><p><b>　　=</b></p><p><b>　　=</b></p><p><b>　　=+</b></p><p><b>　　+</