一種基于減少內存訪問的Pruning Fast DC

一種基于減少內存訪問的Pruning Fast DCT算法改進

　1．引言

　　散余弦變換（dct）的定義是由ahmed和rao與1974年提出，對于圖像數據，通過散余弦變換，可以將低頻數據集中，利用人對高頻數據不敏感這一特點，去掉高頻部分數據，可以實現對數據的壓縮。近年來，基于這一思想的算法大都是在通用計算機上實現的，然而對數字信號處理的最佳平臺是DSP平臺，直接在DSP平臺上運行此類算法存在一定問題。眾所周知，DSP處理器大都應用與移動平臺，對速度和耗電量要求較高。在DCT算法中存在大量的內存訪問操作，這些操作會帶來很多長延時，而這會影響運行速度和電量消耗。比如，在TITMS320C64XDSP平臺上，執行一次內存裝載指令要執行5條操作，需要4次延時，因此，頻繁的內存訪問會增加時間開銷。雖然PruningDCT算法中已經省去了對高頻數據的運算操作，但PruningDCT算法中的大量權重系數和輸入序列還是會導致較多的內存訪問操作。如果能進一步減少對這些權重系數和輸入序列的運算，就能進一步優化算法執行時間。

　　本文針對這一情況提出了一種改進方法，通過分解DCTpruning算法中的權重系數，減少了系數的個數，并由此減少了算法中的步驟。在C64X實驗平臺上出實驗證明，這種改進可以有效減少運算過程中對內存的訪問次數。文中第2章節主要介紹第2類DCT算法思想，第3章節介紹對DCT-II的一種改進算法PruningFCT，第4章節詳細描述了一種降低PruningFCT算法在DSP上運行時間的改進思想，第5和第6章節對改進算法進行了分析及總結。

　　2關于FASTDCTPruning

　　這一章節主要介紹基本的DCT計算過程。當前被介紹最多的DCT運算是第二類DCT（DCT-II），其定義是：

　�。�1）

　　其中當m＝0時，

　�。�

　��；當m

　　0時，

　�。�1。x[n]為輸入序列，X[n]為輸出序列。直接的算法若不加以變換，在軟件和硬件上實現都比較困難，為此，在第二類DCT算法的基礎上又出現了很多改進算法，如FASTDCT。

　　2.2FASTPRUNINGDCT

　　針對以上問題，一些改進方法又被提出，如FCT(FASTDISCRETECOSINETRANSFORM)，次算法針對DCT-II難以硬件實現，對輸入序列的計算過程進行了一些變換，其實現過程如下：

　　首先對輸入序列調整

　　[n]=x[2n],

　　[N-n-1]=x[2n+1],n=0,1,……N-1

　　于是DCT公式調整如下：

　　m=0,1,……N-1（2）

　　利用三角變換公式：cos[(2k+1)φ]=2cosφcos(2kφ)-cos[(2k-1)φ]

　　可以把變換后的公式分解成2部分，N/2-pt的奇數部分x[2k+1],N/2-pt偶數部分x[2k],偶數部分和奇數部分可以繼續分解，直到分解成2-pt的輸入序列。

　　對于16-pt的FCT運算，其設計圖如下：

　　圖1

　　圖1分為兩個部分，蝶形運算和位運算。其中蝶形運算又分為若干階段（stage），根據輸入序列數量每個階段所包含的蝶形運算數量是固定的，對于N個輸入點（即N-pt）的FCT運算，其蝶形運算部分分為

　　N個階段（stage），每個stage有N/2個蝶形運算以及N/

　　個權重系數。在運算過程中，蝶形運算部分占據了主要運算，在此期間存在大量內存訪問操作，為了降低算法執行時間，應對這一部分進行改進。

　　3對FCTPruning算法的改進

　　為了進一步減少FCTPruning算法中因為權重系數和輸入x[n]帶來的內存訪問次數，文中設計了一種改進方法，首先，通過對權重系數的分解，降低所要調用的系數的個數；然后，合并運算階段，減少stage個數。

　　3.1系數分解

　　通過三角恒等變換公式：

　　m

　�。�3）

　　其中

　　=

　　m=1,2,……N/2-1

　　可以對FCTPruning算法中的權重系數進行分解，分解后權重系數從N-1個減少為（2N-1）/3個。

　　例如，對圖1中stage3和stage4出現的權重系數

　　，

　　，

　　，其中

　　可以分解為[

　　-

　　]/2。

　　[

　　-

　　]/2=2[

　　-

　　]

　　=2{

　　-[-

　　}

　　=2[

　　-

　　]

　　=2{

　　-[

　　}

　　=2[

　　-

　　]

　　=

　　=

　　=

　　經過分解后，在stage3和stage4中的權重系數從3個減少為2個。同樣，stage2中的

　　，

　　，

　　，

　　分別替換如下：

　　=[

　　-

　　]/2

　　=[

　　-

　　]/2

　　=[

　　-

　　]/2

　　=[

　　-

　　]/2

　　自此，對于16-pt的FCTPruning的權重系數個數由15個減少為10個。

　　在此基礎上，可以把原有的4個運算階段（stage1，stage2，stage3，stage4）合并為2個。

　　3.2合并簡化計算

　　在進行了權重系數分解后，可以把2個階段的蝶形運算合并成一個，由此減少了程序運行過程中循環執行次數，也就減少了執行期間從內存讀寫權重系數和x[]的次數，從而使得算法執行速度獲得較大提高。在s(s=1,2……

　　)階段，共有N/

　　個不同的權重系數，每個系數按如下法則遞歸生成：

　　第一個和第二個分別是：

　　，

　　(k=

　　)

　　第三個和第四個分別是：

　　，

　　第五個和第六個分別是：

　　，

　　……

　　該法則類似Fibonacci數列

　　X[n+N/

　　]

　　圖2（a）

　　X[n+N/

　　]

　　X[n]

　　圖2（b）

　　圖2（a）顯示了在s和s+1階段的蝶形運算規則，其中在圖2（b）中被挖掉的節點表示此處由于x[n]帶來的內存訪問操作被消除。消除的原因是由于原本的2個階段合并成一個階段，此處的讀x[n]操作只會在一次stage循環中被執行，而不會被執行2次。由4.1章節中三角恒等變換公式可得2

　　=

　　，因此，只需從內存中訪問

　　和

　　這2個系數，就可以對圖2（a）中的4個蝶形運算進行計算，據此，圖2（a）中的2個階段可以合并成1個階段，即圖2（b）所示。在3.1章節中提到，FCTPruning的蝶形運算部分可分為

　　個階段（stage）,改進后對運算階段進行了合并，使得stage數量減少為：

　　為奇數

　　為偶數

　　改進后PruningFCT蝶形運算部分設計如圖（3）所示：

　　e

　　c

　　e

　　e

　　e

　　d

　　b

　　a

　　注：a=[

　　-

　　]/2,b=[

　　-

　　]/2,c=[

　　-

　　]/2

　　e=[

　　-

　　]/2

　　圖（3）

　　4對算法的分析和驗證

　　通過上述的改進設計，由權重系數和x[n]輸入引發的內存訪問操作進一步減少。以圖1和圖3中16-pt的FCT為例，圖1中顯示，16-pt的FCT中共有15個權重系數，經過分解后圖3中權重系數降低為10個。圖1中由x[n]輸入引發的內存訪問有128次，即圖1中實心圓和空心圓的數量，圖3中經過合并，stage數量由4個合并成2個，程序段2算法中最外層對stage的循環次數減少為2次，大量的x[n]重復訪問被省掉，由x[n]輸入引發的內存訪問由是減少為64次，即圖3中實心圓和空心圓的數量。對于PruningFCT算法，輸入序列數量N=16,當

　　=3時，圖1中由x[n]輸入引發的內存訪問有87次，圖3中由x[n]輸入引發的內存訪問有43次。

　　通過簡單對比顯然易見，改進后的PruningFCT算法內存訪問次數進一步降低，這必然提高運行速度。為了更好的顯示改進的效果，將文中程序段1和程序段2針對同樣的輸入序列在C64XDSP平臺上運行，輸入序列分別為8-pt，16-pt，32-pt，64-pt的一維數組。輸出

　　為了方便起見，只取2的整數次冪，實驗結果如下表：

　　N248163264

　　8程序段1415470

　　程序段2233652

　　16程序段189118150194

　　程序段2426581125

　　32程序段1185246310386498

　　程序段295140172248360

　　64程序段13775026307709451218

　　程序段2188273321429541813

　　表1

　　PruningFCT算法改進前改進后對內存的占用情況如下表：

　　N8163264

　　程序段1143062126

　　程序段210204184

　　表2

　　由表1和表2中試驗數據可見，改進后的算法無論在內存訪問時間上還是內存占用方面都有了明顯提升，對表1的數據進行計算分析得出，平均訪問次數降低了41.5%；對表2的數據分析表明，內存占用減少了32.2%。

　　5總結及后續發展

　　本文介紹了一種對PruningFCT算法改進設計，該設計的基本思想是利用三角恒等變換，把s+1階段的權重系數用s階段的權重系數來替代，從而減少了算法中的權重系數，進而把蝶形運算中的階段合并，減少了階段數量，從而減少了對輸入序列的訪問次數。試驗結果顯示，改進后的算法不僅降低了內存訪問次數，還減少了內存的占用。文中只對一維的PruningFCT算法進行了改進，二維的PruningFCT算法在圖像壓縮中的應用更有實際意義，下一步可沿用文中所提思想對二維的PruningFCT算法進行改進。

　　參考文獻

　　1 N. AHMED, T. NATARAJAN, and K. R. RAO “DiscreteCosine Transform,” IEEE Transactions on Computers, vol. C-23, pp.90-93, January 1974.

　　2 K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms,Advantages, Applications. New York: Academic, 1990.

　　3 M. Wezelenburg, “General radix-2n DCT and DST algorithms,”Proceedings of the International Conference on ECCTD’97,pp.789-794, Budapest, Hungary, September 1997.

　　4 Y.-H. Chan and W.-C. Siu, “Mixed-radix discrete cosinetransform,” IEEE transactions on Signal Processing, vol. 41,no.11, pp. 3157-3161, November 1993.

　　5 Z. Wang, “Pruning the fast discrete cosine transform,” IEEETrans. Commun. vol. 39, no. 5, pp. 640-643, May 1991.

　　6 Athanassios N. Skodras, “Fast Discrete Cosine TransformPruning,” IEEE Trans. On Signal Processing, Vol. 42, no. 7,pp.1833-1837, July 1994.

　　7 S.C.Chan and K.L.Ho “A new two-dimensional fast cosinetransform algorithm,” IEEE Trans. Signal Processing,vol. 39,no. 2, pp. 481-485, February 1991.

【一種基于減少內存訪問的Pruning Fast DC】相關文章：

減少污染作文09-09

減少污染作文06-03

訪問記作文06-03

申請減少租金的申請書12-07

婚內存款協議03-25

申請減少租金的申請書9篇12-07

申請減少租金的申請書13篇12-07

對什么的一次訪問作文（通用17篇）06-19

減少聚餐倡議書范文（通用14篇）12-20