一种基于减少内存访问的Pruning Fast DC

一种基于减少内存访问的Pruning Fast DCT算法改进

散余弦变换（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.