一种数学运算更少的分裂基FFT算法外文翻译资料

英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

IEEE中关于传动与信号处理的论文，于2007年发表

一种数学运算更少的分裂基FFT算法

摘要：

最近，Van Buskirk et al打破了Yavne于1968年创造的在计算2的整数幂次离散傅里叶变换(DFT)中所用的实数加法和乘法次数最小的记录。在这篇文章中，我们提出了一种简单的、递归的、可修正的分裂基算法，来计算离散傅里叶变换(DFT)。与Van Buskirk的算法生成程序框架所需要的计算的运算次数相比，我们的计算量比他们少至少6%。当然，我们也讨论将我们的算法应用于具有实对称性（离散余弦性质）数在这个领域中，比之前别人发布的算法相比，我们的算法中数学运算次数更低。

索引词：快速傅立叶变换(FFT),离散余弦傅里叶变换(DCT),分裂基,算法复杂度

第一部分 介绍 所有人都知道用快速傅立叶变换(FFT)来计算N点的离散傅立叶变换需要的运算量与NlogN成正比(也就是等于Theta;(NlogN))。在这其中，任何的改进都依靠于减少抽取次数或这些运算的开销而不是改变函数的形式。许多年来，FFT变换时间都是由实数的计算次数来占主导地位的。所以大家都致力于证明与实现所需的数学运算的下限值包括实数加法与实数乘法。这里我们将浮点运算量作为给定大小的 DFT计算量。尽管计算机目前硬件运行的FFT速率除了纯数学运算量外还由多种因素来决定。但仍然存在一个尚未解决的奇怪问题：对于一个给定大小为Ｎ的DFT变换中需要最少的浮点运算量到底为多少？特别是当N=2m？1968年，Yavne提出了一个被后人称为分裂基算法来解决2m次的DFT变换，它创造了只使用4NlgNminus;6N 8次浮点计算的记录，其中Ngt;１，lg是指的log2。与Cooley 和 Tukey提出的经典基2算法所需要的5NlgN次浮点计算，提高了20%。这里我们提出一种并不以牺牲数值精度的改进型分裂基算法，减小了5.6%（）的浮点计算。改进型算法所需的浮点计算次数：

其中Ngt;1。当Ngt;64时，才能体现这种新算法对复数乘法次数的简化。这点从表一也可以看出。具体一点说，我们将先假设一次复数乘法可以由4次普通的实数乘法和2次普通的实数加法来完成而不是3次实数乘法和3次实数加法的变种完成的，下文都是在这种假设前提下讨论的。在这种情况下， (1)式的结果就是所求出的实数乘法的次数。

表一：标准的复数型分裂基算法和我们的新算法关于浮点运算次数的比对

这种改进算法的浮点运算量的范例是由Van Buskirk于2004年在 Usenet首先提出的。他采用与以前不同的算法将DFT变换分解成实部、虚部以及奇次序列和偶次序列(主要是I型离散余弦和正弦变换)，在N=64点的DFT运算中，可以在 Yavne的基础上手工优化节省8次运算量。这是因为重新调整了长度为8的子变换，在计算过程中吸收其他地方的比例因子。(与之相关的节省是产生于长度为8的II型离散余弦变换环节，通过重新调整输出可以节省6次乘法运算，具体可看第8节)。之后，Van Buskirk利用自动代码生成技术来实现他的方案，主要是N=2^m个任意定点DFT变换。与此同时，我们在Van的基础上提出一种针对更传统的分裂基算法来实现同样的算法优化程度。我们的改进分裂基算法涉及在DFT的4个相互递归的子变换中将三角常量重新递归分布，当然最终的结果仍是正确的，自然序的。 几个DFT算法复杂性的严格界限在相关文献中已经被证明了，但是目前我们不知道算法的浮点运算量的下限。（注意：我们并没有说公式1是可能的下限值）。根据文献[15]的介绍，目前被认可N =2^m点DFT变换运算量的下限值是 4Nminus;2lg²Nminus;2lgNminus;4(以无理实数乘法为单位)。这跟我们算法的N=16以上点数的运算量一样，但是这种简化是以增加加法为代价的，而且有充分利用带有硬件乘法器的CPU的性能。DFT已经被证明在乘法常数有界的情况下复数加法的复杂度为Omega;(N logN)，或者假设在一个衡量算法的异步性约束下。此外，利用 Cooley-Tukey算法，比如分裂基算法，计算N =2^m点DFT，求取所需的复数加法次数Nm。这种算法在一系列的实现算法是最佳，因为它并没有引入额外的虚部，我们的算法也没有改变复数加法的次数。 下文是这样组织的：我们先回顾一下已知的、作为我们的算法的出发点的其他变种算法

的分裂基FFT算法，然后介绍我们的改进算法，分析算法代价(从理论以及来两个实际范例的应用来计算算法的运算量)以及数值精度，并将其应用于实数与实对称数据(离散余弦)中，发现相对其他算法的长处，总结实现的结论以及未来的改进的方向。

第二部分 共轭对分裂基算法

我们的算法不是以标准的分裂基算法为改进的出发点，而是针对被称作共轭对的变种分裂基算法，这种FFT算法最初提出来是为了减少浮点运算量的，但不久它就被证明了运算量与标准的分裂基算法一样。这种变种也在 Bernstein未发表的作品中被发现，他认为这种方法可以减小旋转因子的负荷。无独有偶，当Volynets把变种算法应用于离散哈特莱变换，得出类似的观点，我们也用到该原理，因为共轭对FFT能保留冗余旋转因子，这样能使我们完成传统普通分裂基算法实现的内容：提取、重新排列以及简化FFT共轭对。以下是推导出算法的过程，我们将DFT变换定义为：

其中k= 0...Nminus;1，omega;_N=exp(minus;2pi;i/N)，其中N可以被4整除，我们根据时间抽取将Xn分解成3个小部分的DFT变换：(偶数部分)、 和(其中X_minus;1 = X_Nminus;1),在标准的分裂基中第三部分也可以写成，实际上这里我们向左平移了4个点，可以得到：

其中 和 共轭双旋转因子(而普通的分裂基算法的双旋转因子是和)(这里强调一下本文我们将使用术语“旋转因子”是指带FFT变换中出现的所有独立的三角常数)。上面的和式是N/2 和N/4点的DFT变换结果，可以通过k ge; N/4时的值与i、-1相乘来求得。具体可看算法1，这样我们可以来获得三个部分的DFT子变换的结果，并记作 u_k , z_k , 和 。

为了简单起见，在算法1中忽略k=0的特殊情况，因为当k=0，等于1，没有复数运算。而当k = N/8时，= (1minus;i)/，只需要2次实数乘法，而不是4次。它还省出的递归的基础项：当N = 1，y₀ = x₀ , N = 2，y ₀ = x ₀ x 1 和y ₁ = x ₀ minus;x ₁。通过这些优化和基础项，标准假设中，与plusmn;1、 plusmn;i的乘法都不算在最终运算量中，通过提取公共因子表达式plusmn; 来出DFT最终运算次数。具体来说，实数加法的次数alpha;(N)与实数乘法的次数 micro;(N) 分别为（以4次复数乘法与两次复数加法为计算量）

传统上，递归可以“扁平化”为一个迭代算法，来一次性完成给定点数大小的FFT计算。通过公式= 可以将旋转因子的数目减半，但是对运算量的大小没有影响。具体可看第6部分。虽然本文中，我们只考虑了按时间抽取分解算法（DIT），但在广义的双频域抽取算法（DIF）可以在相同的操作数下，通过网表换位来实现（扭转计算的流程图）。

第三部分 新FFT算法：重新排列旋转因子

减少运算量的关键是观察到算法1中，在求取y_k，之前，先将z_k 和（点数为N/4的子变换中第k项的输出结果）分别乘以或。我们可以根据参数1/s_N/4,k 来不花费任何代价地重新排列N/4点的子变换，乘以旋转因子得到s _N/4,k ，我们只需要找到一种排列标准就可以在子变换计算中省去若干计算（就如传统计算FFT一样，我们可以认为所有的独立常数如s _N/4,k都可以提前算出来，因此没有必要算在总的运算量中）。我们的算法建立在这样的事实上： 在共轭对算法中，z_k 和中存在共轭对的旋转因子，因此我们只需要对其中一个进行缩放，极大的简化旋转因子的个数来优化计算量。这是传统的分裂基算法不能实现的，因为它的旋转因子为和。以上只是我们方法的一个总述，具体分析算法在第四部分。

对于一个给定点数为N的子变换，我们根据公式 1/s _N,_k对于输出y_k进行缩放。假设 kle;N/8时，s_N,_k=s_{N,k N/4}=cos(2pi;k/N)。因此从算法1得到的y_k可以写成u_k/s_N,_k (t_N,_,)，其中

对于计算一个固定k值的需要经过4次实数乘法和2次实数加法（总共6次运算量），而对于计算t_N,的值需要经过2次实数乘法和2次实数加法（总共4次运算量）。类似的缩放方法在相关文献[30]中提出来提高乘加运算的次数。文献[30]中提出的类似缩放方法涉及给定与快速给定QD算法。我们通过计算t_N，_,的值可以节省4次实数乘法。而通过计算可以节省2次实数乘法，通过计算又可以节省2次实数乘法，跟直接计算t_N，_,似乎没有任何变化。但是实际上不直接计算t_N，_,，我们可以选择将比例因素下放在u_k 的每次递归计算中。这样做的好处是我们可以在N/2的子变换中将比例因素结合旋转因子来节省大多数的额外乘法运算。事实上，我们会看到，我们的确需要通过两个层次的递归，以获得所有可能的节省。

图一：以等式7中比例因数的纵坐标，横坐标为N=2¹² =4096，k的值

此外，我们执行在每次递归执行缩放，所以在子变换z_k 和需要用缩放因子进行缩放成相同大小，具体实现就是乘以子变换的缩放因子cos(2pi;k/N)，再递归到上层，缩放因子可以通过一下的方程是给定，其中 k₄等于k 除以N/4的余数：

根据上式我们可以得到一个有分形图案，这个定义还有几个性质：

和

比较重要的是它具有对称性。我们通常可以把它定义为：

其中要么正割要么是余割，t _N,_k 永远是 plusmn;1plusmn;i*tan 或者 plusmn;cotplusmn;i的形式，最后一个性质是最为关键的，因为它意味着在任何缩放变换中，在所有的缩放变换与最多需要4次运算的t_N,k 乘法中总计算量可以达到t_N,,，。

我们现在只是简单提出算法而不是更进一步的解释它，算法包括了四个相互递归类似分割基的函数，这可以在算法2，3的流程中体现，具体在下一部分中分析。正如我们在以前的部分所讲，我们忽略了k=0和k=N/8的特殊情况，以及N=1和N=2的基本情况。

第四部分 运算量计算 使用算法2和3来解决DFT变换的实数加法运算量明显与算法１一样（以４次实数乘法与２次实数加法为一次运算量），它们唯一的不同就是使用不同的实数乘法缩放因子。因此剩下的与算法1的对比就是计算实数乘法的优化次数M(N)，所以我们必须计算3个子变换中的实数乘法的优化（如果情况差的化就是多余）次数M_S (N), M_S2 (N),和M_S4 (N)。对于newfft_N (x) 部分，乘法的次数就是newfft_N (x)的次数，没有优化。因为所有的缩放因子都包含于旋转因子中，而且s_N/4,0 = 1当 k = 0 的特殊情况也没有额外增加运算量。所以因此运算量的减少纯粹来自子变换：

就像上面讨论的一样，在newfft_N (x)中，用t_N,k代替可以在每个旋转因子参与运算可以节省2次实数乘法，或者是每个循环k次迭代中节省4次实数乘法。这节省了N次乘法，但我们必须考虑到k=0，k = N/8的特殊情况。当k = N/8时，t _N,k = 1minus;i,可以在每个旋转因子计算中节省2次乘法。但当k=0的特殊情况，t_N,0 = 1，本身没有乘法运算，所以并没有优化。因此我们可以N-4次乘法运算。

或许从第一眼看过去，newfft2_N(x) 好像跟splitfft_N(x)有相同数量的乘法运算。因为就如上面所说的，每个t_N,k所节省2次乘法被的乘法所抵消了。（注意我们并没有将 转换成t_N,k,。因为我们必须根据来进行缩放，这样才能保证不会改变t_N,的一般形式）。但是当k=0的特殊情况，普通分裂基不需要乘法计算，而我们的算法却需要消耗2个额外乘法计算，因为当Ngt; 2时，s_N,₀/s_2N

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[148132]，资料为PDF文档或Word文档，PDF文档可免费转换为Word