论文摘要：随着数字信号处理在计算机领域的广泛应用，各类正交变换的应用和研究也日益深入，尤其在图像处理和语音识别方面。其中应用最广泛的变换就是离散余弦变换（dct）及在其基础上发展的各类快速算法，如pruning fast dc(简写为pruning fct)t等。本文介绍了一种运行于dsp处理器的pruning fct改进算法，在该算法中，通过对pruning fct系数的分解，减少了pruning dct系数的个数，合并了算法中的步骤，由此减少了运算中内存访问的次数，在TI TMSC320C64x DSP处理器上的运行结果显示，与未修改的pruning fct算法相比，改进后的算法可以减少大约40%的内存访问次数和30%的内存空间
论文关键词：内存访问
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个。 1/2 1 2 下一页 尾页 |
