- 相關(guān)推薦
一種基于減少內(nèi)存訪問的Pruning Fast DCT算法改進
1.引言散余弦變換(dct)的定義是由ahmed和rao與1974年提出,對于圖像數(shù)據(jù),通過散余弦變換,可以將低頻數(shù)據(jù)集中,利用人對高頻數(shù)據(jù)不敏感這一特點,去掉高頻部分數(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)存訪問操作。如果能進一步減少對這些權(quán)重系數(shù)和輸入序列的運算,就能進一步優(yōu)化算法執(zhí)行時間。
本文針對這一情況提出了一種改進方法,通過分解DCTpruning算法中的權(quán)重系數(shù),減少了系數(shù)的個數(shù),并由此減少了算法中的步驟。在C64X實驗平臺上出實驗證明,這種改進可以有效減少運算過程中對內(nèi)存的訪問次數(shù)。文中第2章節(jié)主要介紹第2類DCT算法思想,第3章節(jié)介紹對DCT-II的一種改進算法PruningFCT,第4章節(jié)詳細描述了一種降低PruningFCT算法在DSP上運行時間的改進思想,第5和第6章節(jié)對改進算法進行了分析及總結(jié)。
2關(guān)于FASTDCTPruning
這一章節(jié)主要介紹基本的DCT計算過程。當前被介紹最多的DCT運算是第二類DCT(DCT-II),其定義是:
。1)
其中當m=0時,
=
;當m
0時,
。1。x[n]為輸入序列,X[n]為輸出序列。直接的算法若不加以變換,在軟件和硬件上實現(xiàn)都比較困難,為此,在第二類DCT算法的基礎(chǔ)上又出現(xiàn)了很多改進算法,如FASTDCT。
2.2FASTPRUNINGDCT
針對以上問題,一些改進方法又被提出,如FCT(FASTDISCRETECOSINETRANSFORM),次算法針對DCT-II難以硬件實現(xià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)對這一部分進行改進。
3對FCTPruning算法的改進
為了進一步減少FCTPruning算法中因為權(quán)重系數(shù)和輸入x[n]帶來的內(nèi)存訪問次數(shù),文中設(shè)計了一種改進方法,首先,通過對權(quán)重系數(shù)的分解,降低所要調(diào)用的系數(shù)的個數(shù);然后,合并運算階段,減少stage個數(shù)。
3.1系數(shù)分解
通過三角恒等變換公式:
m
。3)
其中
=
m=1,2,……N/2-1
可以對FCTPruning算法中的權(quán)重系數(shù)進行分解,分解后權(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合并簡化計算
在進行了權(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ù)此,圖2(a)中的2個階段可以合并成1個階段,即圖2(b)所示。在3.1章節(jié)中提到,F(xiàn)CTPruning的蝶形運算部分可分為
個階段(stage),改進后對運算階段進行了合并,使得stage數(shù)量減少為:
為奇數(shù)
為偶數(shù)
改進后PruningFCT蝶形運算部分設(shè)計如圖(3)所示:
e
c
e
e
e
d
b
a
注:a=[
-
]/2,b=[
-
]/2,c=[
-
]/2
e=[
-
]/2
圖(3)
4對算法的分析和驗證
通過上述的改進設(shè)計,由權(quán)重系數(shù)和x[n]輸入引發(fā)的內(nèi)存訪問操作進一步減少。以圖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,當
=3時,圖1中由x[n]輸入引發(fā)的內(nèi)存訪問有87次,圖3中由x[n]輸入引發(fā)的內(nèi)存訪問有43次。
通過簡單對比顯然易見,改進后的PruningFCT算法內(nèi)存訪問次數(shù)進一步降低,這必然提高運行速度。為了更好的顯示改進的效果,將文中程序段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算法改進前改進后對內(nèi)存的占用情況如下表:
N8163264
程序段1143062126
程序段210204184
表2
由表1和表2中試驗數(shù)據(jù)可見,改進后的算法無論在內(nèi)存訪問時間上還是內(nèi)存占用方面都有了明顯提升,對表1的數(shù)據(jù)進行計算分析得出,平均訪問次數(shù)降低了41.5%;對表2的數(shù)據(jù)分析表明,內(nèi)存占用減少了32.2%。
5總結(jié)及后續(xù)發(fā)展
本文介紹了一種對PruningFCT算法改進設(shè)計,該設(shè)計的基本思想是利用三角恒等變換,把s+1階段的權(quán)重系數(shù)用s階段的權(quán)重系數(shù)來替代,從而減少了算法中的權(quán)重系數(shù),進而把蝶形運算中的階段合并,減少了階段數(shù)量,從而減少了對輸入序列的訪問次數(shù)。試驗結(jié)果顯示,改進后的算法不僅降低了內(nèi)存訪問次數(shù),還減少了內(nèi)存的占用。文中只對一維的PruningFCT算法進行了改進,二維的PruningFCT算法在圖像壓縮中的應(yīng)用更有實際意義,下一步可沿用文中所提思想對二維的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.
【一種基于減少內(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