- 相關(guān)推薦
一種基于減少內(nèi)存訪問的Pruning Fast DCT算法改進(jìn)
1．引言散余弦變換（dct）的定義是由ahmed和rao與1974年提出，對于圖像數(shù)據(jù)，通過散余弦變換，可以將低頻數(shù)據(jù)集中，利用人對高頻數(shù)據(jù)不敏感這一特點，去掉高頻部分?jǐn)?shù)據(jù)，可以實現(xiàn)對數(shù)據(jù)的壓縮。近年來，基于這一思想的算法大都是在通用計算機上實現(xiàn)的，然而對數(shù)字信號處理的最佳平臺是DSP平臺，直接在DSP平臺上運行此類算法存在一定問題。眾所周知，DSP處理器大都應(yīng)用與移動平臺，對速度和耗電量要求較高。在DCT算法中存在大量的內(nèi)存訪問操作，這些操作會帶來很多長延時，而這會影響運行速度和電量消耗。比如，在TITMS320C64XDSP平臺上，執(zhí)行一次內(nèi)存裝載指令要執(zhí)行5條操作，需要4次延時，因此，頻繁的內(nèi)存訪問會增加時間開銷。雖然PruningDCT算法中已經(jīng)省去了對高頻數(shù)據(jù)的運算操作，但PruningDCT算法中的大量權(quán)重系數(shù)和輸入序列還是會導(dǎo)致較多的內(nèi)存訪問操作。如果能進(jìn)一步減少對這些權(quán)重系數(shù)和輸入序列的運算，就能進(jìn)一步優(yōu)化算法執(zhí)行時間。
本文針對這一情況提出了一種改進(jìn)方法，通過分解DCTpruning算法中的權(quán)重系數(shù)，減少了系數(shù)的個數(shù)，并由此減少了算法中的步驟。在C64X實驗平臺上出實驗證明，這種改進(jìn)可以有效減少運算過程中對內(nèi)存的訪問次數(shù)。文中第2章節(jié)主要介紹第2類DCT算法思想，第3章節(jié)介紹對DCT-II的一種改進(jìn)算法PruningFCT，第4章節(jié)詳細(xì)描述了一種降低PruningFCT算法在DSP上運行時間的改進(jìn)思想，第5和第6章節(jié)對改進(jìn)算法進(jìn)行了分析及總結(jié)。
2關(guān)于FASTDCTPruning
這一章節(jié)主要介紹基本的DCT計算過程。當(dāng)前被介紹最多的DCT運算是第二類DCT（DCT-II），其定義是：
�。�1）
其中當(dāng)m＝0時，
�。�
��；當(dāng)m
0時，
�。�1。x[n]為輸入序列，X[n]為輸出序列。直接的算法若不加以變換，在軟件和硬件上實現(xiàn)都比較困難，為此，在第二類DCT算法的基礎(chǔ)上又出現(xiàn)了很多改進(jìn)算法，如FASTDCT。
2.2FASTPRUNINGDCT
針對以上問題，一些改進(jìn)方法又被提出，如FCT(FASTDISCRETECOSINETRANSFORM)，次算法針對DCT-II難以硬件實現(xiàn)，對輸入序列的計算過程進(jìn)行了一些變換，其實現(xiàn)過程如下：
首先對輸入序列調(diào)整
[n]=x[2n],
[N-n-1]=x[2n+1],n=0,1,……N-1
于是DCT公式調(diào)整如下：
m=0,1,……N-1（2）
利用三角變換公式：cos[(2k+1)φ]=2cosφcos(2kφ)-cos[(2k-1)φ]
可以把變換后的公式分解成2部分，N/2-pt的奇數(shù)部分x[2k+1],N/2-pt偶數(shù)部分x[2k],偶數(shù)部分和奇數(shù)部分可以繼續(xù)分解，直到分解成2-pt的輸入序列。
對于16-pt的FCT運算，其設(shè)計圖如下：
圖1
圖1分為兩個部分，蝶形運算和位運算。其中蝶形運算又分為若干階段（stage），根據(jù)輸入序列數(shù)量每個階段所包含的蝶形運算數(shù)量是固定的，對于N個輸入點（即N-pt）的FCT運算，其蝶形運算部分分為
N個階段（stage），每個stage有N/2個蝶形運算以及N/
個權(quán)重系數(shù)。在運算過程中，蝶形運算部分占據(jù)了主要運算，在此期間存在大量內(nèi)存訪問操作，為了降低算法執(zhí)行時間，應(yīng)對這一部分進(jìn)行改進(jìn)。
3對FCTPruning算法的改進(jìn)
為了進(jìn)一步減少FCTPruning算法中因為權(quán)重系數(shù)和輸入x[n]帶來的內(nèi)存訪問次數(shù)，文中設(shè)計了一種改進(jìn)方法，首先，通過對權(quán)重系數(shù)的分解，降低所要調(diào)用的系數(shù)的個數(shù)；然后，合并運算階段，減少stage個數(shù)。
3.1系數(shù)分解
通過三角恒等變換公式：
m
（3）
其中
=
m=1,2,……N/2-1
可以對FCTPruning算法中的權(quán)重系數(shù)進(jìn)行分解，分解后權(quán)重系數(shù)從N-1個減少為（2N-1）/3個。
例如，對圖1中stage3和stage4出現(xiàn)的權(quán)重系數(shù)
，
，
，其中
可以分解為[
-
]/2。
[
-
]/2=2[
-
]
=2{
-[-
}
=2[
-
]
=2{
-[
}
=2[
-
]
=
=
=
經(jīng)過分解后，在stage3和stage4中的權(quán)重系數(shù)從3個減少為2個。同樣，stage2中的
，
，
，
分別替換如下：
=[
-
]/2
=[
-
]/2
=[
-
]/2
=[
-
]/2
自此，對于16-pt的FCTPruning的權(quán)重系數(shù)個數(shù)由15個減少為10個。
在此基礎(chǔ)上，可以把原有的4個運算階段（stage1，stage2，stage3，stage4）合并為2個。
3.2合并簡化計算
在進(jìn)行了權(quán)重系數(shù)分解后，可以把2個階段的蝶形運算合并成一個，由此減少了程序運行過程中循環(huán)執(zhí)行次數(shù)，也就減少了執(zhí)行期間從內(nèi)存讀寫權(quán)重系數(shù)和x[]的次數(shù)，從而使得算法執(zhí)行速度獲得較大提高。在s(s=1,2……
)階段，共有N/
個不同的權(quán)重系數(shù)，每個系數(shù)按如下法則遞歸生成：
第一個和第二個分別是：
，
(k=
)
第三個和第四個分別是：
，
第五個和第六個分別是：
，
……
該法則類似Fibonacci數(shù)列
X[n+N/
]
圖2（a）
X[n+N/
]
X[n]
圖2（b）
圖2（a）顯示了在s和s+1階段的蝶形運算規(guī)則，其中在圖2（b）中被挖掉的節(jié)點表示此處由于x[n]帶來的內(nèi)存訪問操作被消除。消除的原因是由于原本的2個階段合并成一個階段，此處的讀x[n]操作只會在一次stage循環(huán)中被執(zhí)行，而不會被執(zhí)行2次。由4.1章節(jié)中三角恒等變換公式可得2
=
，因此，只需從內(nèi)存中訪問
和
這2個系數(shù)，就可以對圖2（a）中的4個蝶形運算進(jìn)行計算，據(jù)此，圖2（a）中的2個階段可以合并成1個階段，即圖2（b）所示。在3.1章節(jié)中提到，F(xiàn)CTPruning的蝶形運算部分可分為
個階段（stage）,改進(jìn)后對運算階段進(jìn)行了合并，使得stage數(shù)量減少為：
為奇數(shù)
為偶數(shù)
改進(jìn)后PruningFCT蝶形運算部分設(shè)計如圖（3）所示：
e
c
e
e
e
d
b
a
注：a=[
-
]/2,b=[
-
]/2,c=[
-
]/2
e=[
-
]/2
圖（3）
4對算法的分析和驗證
通過上述的改進(jìn)設(shè)計，由權(quán)重系數(shù)和x[n]輸入引發(fā)的內(nèi)存訪問操作進(jìn)一步減少。以圖1和圖3中16-pt的FCT為例，圖1中顯示，16-pt的FCT中共有15個權(quán)重系數(shù)，經(jīng)過分解后圖3中權(quán)重系數(shù)降低為10個。圖1中由x[n]輸入引發(fā)的內(nèi)存訪問有128次，即圖1中實心圓和空心圓的數(shù)量，圖3中經(jīng)過合并，stage數(shù)量由4個合并成2個，程序段2算法中最外層對stage的循環(huán)次數(shù)減少為2次，大量的x[n]重復(fù)訪問被省掉，由x[n]輸入引發(fā)的內(nèi)存訪問由是減少為64次，即圖3中實心圓和空心圓的數(shù)量。對于PruningFCT算法，輸入序列數(shù)量N=16,當(dāng)
=3時，圖1中由x[n]輸入引發(fā)的內(nèi)存訪問有87次，圖3中由x[n]輸入引發(fā)的內(nèi)存訪問有43次。
通過簡單對比顯然易見，改進(jìn)后的PruningFCT算法內(nèi)存訪問次數(shù)進(jìn)一步降低，這必然提高運行速度。為了更好的顯示改進(jìn)的效果，將文中程序段1和程序段2針對同樣的輸入序列在C64XDSP平臺上運行，輸入序列分別為8-pt，16-pt，32-pt，64-pt的一維數(shù)組。輸出
為了方便起見，只取2的整數(shù)次冪，實驗結(jié)果如下表：
N248163264
8程序段1415470
程序段2233652
16程序段189118150194
程序段2426581125
32程序段1185246310386498
程序段295140172248360
64程序段13775026307709451218
程序段2188273321429541813
表1
PruningFCT算法改進(jìn)前改進(jìn)后對內(nèi)存的占用情況如下表：
N8163264
程序段1143062126
程序段210204184
表2
由表1和表2中試驗數(shù)據(jù)可見，改進(jìn)后的算法無論在內(nèi)存訪問時間上還是內(nèi)存占用方面都有了明顯提升，對表1的數(shù)據(jù)進(jìn)行計算分析得出，平均訪問次數(shù)降低了41.5%；對表2的數(shù)據(jù)分析表明，內(nèi)存占用減少了32.2%。
5總結(jié)及后續(xù)發(fā)展
本文介紹了一種對PruningFCT算法改進(jìn)設(shè)計，該設(shè)計的基本思想是利用三角恒等變換，把s+1階段的權(quán)重系數(shù)用s階段的權(quán)重系數(shù)來替代，從而減少了算法中的權(quán)重系數(shù)，進(jìn)而把蝶形運算中的階段合并，減少了階段數(shù)量，從而減少了對輸入序列的訪問次數(shù)。試驗結(jié)果顯示，改進(jìn)后的算法不僅降低了內(nèi)存訪問次數(shù)，還減少了內(nèi)存的占用。文中只對一維的PruningFCT算法進(jìn)行了改進(jìn)，二維的PruningFCT算法在圖像壓縮中的應(yīng)用更有實際意義，下一步可沿用文中所提思想對二維的PruningFCT算法進(jìn)行改進(jìn)。
參考文獻(xiàn)
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.
【一種基于減少內(nèi)存訪問的Pruning Fast DC】相關(guān)文章：
減少污染作文09-09
減少污染作文06-03
訪問記作文06-03
申請減少租金的申請書12-07
婚內(nèi)存款協(xié)議03-25
申請減少租金的申請書9篇12-07
申請減少租金的申請書13篇12-07
對什么的一次訪問作文（通用17篇）06-19
減少聚餐倡議書范文（通用14篇）12-20