关键字 |
| 离散傅里叶变换(DFT)，快速傅里叶变换(FFT)，快速傅里叶反变换(IFFT)，一般分裂基数，基数3/6,System Verilog语言。 |
介绍 |
| 离散傅里叶变换(DFT)是应用于几乎所有科学和工程领域的最重要的工具之一。DFT可以用快速傅里叶变换(FFT)等高效算法实现。目前应用最广泛的方法是所谓的2m算法，如基2、基4和分裂基FFT (SRFFT)。大量的研究使得这类算法得到了快速的发展。同时，对计算长度- n =km DFT的算法进行了研究，得到了和k=3和k=6的方法。 |
| 当k≠2时，求解km的算法效率较低，实际意义不大。然而，序列长度为3m或6m的应用较多。这封信的想法是开发一个有用的算法长度N=6m DFT。现有的已发表算法报告在;一般的分裂基数算法似乎更适合于长度- DFT。在这封信中，我们提出了一种基于基数-6的算法。该算法的实现比已有的算法效率更高。其计算复杂度约等于4.071给出的方程nloga¯害怕一个½¯害怕一个½n - 5.61 - 33.555 n + loga¯害怕一个½¯害怕½n - 130.992,接近标准SRFFT (SRFFT的复杂性是4 nloga¯害怕一个½¯害怕一个½N-6N + 8)。本文提出的算法为基数3/6算法，采用基数(1,j)。算法将一个长度为N=6m的DFT分解为1个子长度为N/3的DFT和4个子长度为N/6的DFT。分解的灵活性使该算法能够实现非6次幂的DFT，而其长度可以被6整除。 Appropriate permutations are used for sub DFTs input sequences to reduce the computational intension. |
文献调查 |
a.长度qx2m的基数2/8 FFT算法 |
| 提出了一种新的基-2/8快速傅里叶变换(FFT)算法，用于计算任意长度N= qx2^m的离散傅里叶变换，其中m为奇数。它大大减少了数据传输、地址生成、twiddle因子计算或访问查找表等操作，极大地缩短了FFT算法的执行时间。结果表明，该算法的算术复杂度(乘法、加法)在大多数情况下与现有的分裂基FFT算法相同。提出的算法背后的基本思想是混合使用基数2和基数8的索引映射。该算法以简单的矩阵形式表示，从而便于算法的实现，并允许对多维情况进行扩展。对于结构的复杂性，所提出的算法保留了Cooley-Tukey方法的重要性质，如使用蝴蝶格式和原地计算。它只适用于序列长度N=qx2m的DFT |
b.长度qx2m的基数2/16 FFT算法 |
| 通过适当混合基-2、基-4和基-16索引映射，并结合一些旋转因子[3]，提出了一种基-2/16频率抽取(DIF)快速傅里叶变换(FFT)算法及其更高基版本，即基-4/16 DIF FFT算法。结果表明，所提出的算法和现有的基-2/4和基-2/8 FFT算法需要完全相同数量的算术运算(乘法和加法)。利用这种技术，可以证明所有可能的基- 2r/2rs类型的分裂基FFT算法用于计算2m DFT需要完全相同的算术运算次数。该算法只适用于长度为N=2m的序列，其中m为整数。 |
实现提出的基3/6算法 |
| 提出了一种适用于乘法-加法指令的基-6 FFT算法。在具有乘法-加法指令的处理器上，新的基数-6 FFT算法比传统的基数-6 FFT算法需要更少的浮点指令。提出了一种计算6基FFT的算法，该算法比传统的6基FFT算法具有更少的浮点指令。在具有乘法-加法指令的处理器上，比较了新基数-6 FFT算法与传统基数-6 FFT算法的浮点指令数。 |
| 离散傅里叶变换的定义由 |
 |
| 在哪里 |
| WN =e π， j=√−1，序列长度 |
| 假设{xn}是一个能被6整除的整数。对于长度为N的DFT, 6的幂对于所提出的算法是最好的。显然，DFT可以分为三个长度为n /3的子DFT。为了得到一个最好的算法，我们继续分解三个子dft。由于前面没有缩放因子;第一个子DFT应保持原样，直接进入下一阶段的递归分解。其余两个子dft被分为四个长度为- n /6的子dft。实际上，如果DFT的长度可以被6整除，那么DFT就可以被该算法分解。广义长度N可设为N= 2rx3m，其中r≥m-1。大小为N= 2rx3m的DFT的分解表示为 |
 |
| 其中四个长度- n /6子dft被重新排序。为简化描述，可将(2)表示为 |
 |
| 在哪里 |
 （4） |
| 在(3)中，Bk和Fk可以成对处理，因为and是共轭对。以类似的方式，Ck和Ek可以成对处理。(3)的直接实现执行了许多不必要的操作，因为Xk, X2N/6+k, X4N/6+k,XN/6+k, X3N/6+k和XNN/6+k的计算彼此共享许多计算。特别地，如果我们把N/6加到K，大小- DFT不会改变(因为它们是周期性的)，而如果我们把2N/6加到K，大小-N/3的DFT是不变的，所以，唯一改变的是，，和项。为了减少操作次数，需要以下六个恒等式: |
 （5） |
 (6） |
 (7） |
 （8） |
 （9) |
 （10） |
| 在上述6个方程中，我们让范围从0到N/6 -1，就可以得到一个完整的输出X {k}集。 |
| 现在我们总结了所提出的基-3/6 FFT算法的方案。将长度为n的初始输入序列{xn}分解为5个子序列。这一过程对每个新的子序列依次重复，直到所有子dft的大小都能被6整除。图1-3给出了3,6,12点根3/6算法的流程图(2点FFT和4点FFT可以用SRFFT进行)。 |
| 3点DFT需要4次实乘法和12次实加法(一些算法假设3点DFT是用2次实乘法和12次实加法计算的，因为不需要乘以1/2，而乘以1/2可以用位移位来计算)。 |
| 初始输入序列{¯害怕一个½¯害怕一个½¯害怕一个½¯害怕一个½}长度- N是分解成5子。这一过程对每个新的子序列依次重复，直到所有子dft的大小都能被6整除。 |
| 基-3/6 DIF FFT的推导如下 |
 |
| P (k)， Q (k)和R (k)中的每一个和都被认为是N/3点DFT。变换X (k)可分为三部分，如式(11)所示。 |
 |
 |
| 在该算法中进行递归分解，直到所有子dft的长度不能被6整除为止。一般情况下，只有1只第一种特殊蝴蝶(r≥1,m≥1)，1只第二种特殊蝴蝶(r≥2,m≥1)，1只第三种特殊蝴蝶，1只第四种特殊蝴蝶(r≥3,m≥1)。总数的第五和第六类型的蝴蝶是2¯害怕一个½¯害怕一个½¯害怕一个½¯害怕一个½¯害怕害怕一个½¯½4。因此，本文算法的算术复杂度可由式(14)表示。 |
 |
结果与讨论 |
| 在System Verilog中实现了12点DFT序列，并使用Modelsim Version 6.4进行了仿真。 |
| ,图4显示了12号radix-3/6算法的输入序列FFT即{¯害怕一个½¯害怕一个½¯害怕一个½¯害怕一个½}={1,2,3,4,5,6,7,8,9,10,11}的Modelsim仿真应用。 |
| 图5显示了给定输入序列的输出序列Xk={78，-6+22.3923i，-6+ 10.3923 i，-6+6i，-6+3.464i，-6+1.6i，-6，-6-1.6i，-6-3.4i， -6-6i，- 6- 10.3923 i，-6-22.3923i}。 |
| 上图。6is the RTL (Register Transfer Level) Schematic for 12 point input sequence using radix 3/6 algorithm generated in Xilinx 9.1i. The schematic contains one 4-point SRFFT, four 2-point FFT and three 3-point FFTs butterfly blocks. |
| 图7显示了将12点分裂基数3/6 IFFT输入序列{Xk}={12,0,0,0,0,0,0,0}应用于Modelsim进行仿真的仿真结果。 |
| 仿真结果显示Fig.8 12点分裂基数3/6传输线的输出序列{¯害怕一个½¯害怕一个½¯害怕一个½¯害怕一个½}={0.999,0.999,0.999,0.999,0.999,0.999,0.999,0.999,0.999,0.999,0.999,0.999}。 |
未来的范围 |
| 使用Verilog实现16点RADIX 3/6 FFT设计，并使用Verilog系统进行验证。这些实现通常使用高效的快速傅里叶变换(FFT)算法，以至于术语“FFT”和“DFT”经常互换使用。DFT的同义词有限傅里叶变换(现在很少见)进一步模糊了这个术语，它显然早于术语“快速傅里叶变换”，但具有相同的初始化。 |
结论 |
| 针对长度为6m的DFT，提出了一种基为3/6的FFT算法。该算法是一种基3和基6的混合算法。它可以求非6次幂的DFT，只要它的长度-6m能被6除。为了减少操作次数，所有子dft都进行了有利的重新排序。与已有算法相比，该算法的实现需要较少的实际操作。该算法的算术复杂度约为，接近标准SRFFT算法。由于序列长度为不规则整数，因此很难得到完全准确的计算复杂度公式。 |
数字一览 |
|
|
参考文献 |
- M. Frigo和S. Johnson，“fftw3的设计和实现”，IEEE程序，第93卷，no. 1。2，页216-231,2005。
- J. Keiner, S. Kunis和D. Potts，“使用nfft 3-A软件库进行各种非等距快速傅里叶变换，”ACM Trans。数学。《软件》(TOMS)，第36卷，no。4，页19 - 19,2005。
- D. Sepiashvili，“最优FFT实现的性能模型和搜索方法”，硕士论文，卡内基梅隆大学，匹兹堡，宾夕法尼亚州，2000。
- J. Cooley和J. Tukey，“复杂傅里叶级数的机器计算算法”，数学。计算，第19卷，no。90，页297-301,1965。
- P. Duhamel和H. Hollmann，“分裂基数FFT算法”，电子，lett。1984年1月，第20卷，第14-6页。
- Kamar和Y. Elcherif， "共轭对快速傅里叶变换"电子。列托人。，vol. 25, no.5, pp. 324–325, Apr. 1989.
- S. Bouguezel, M. Ahmad，和M. Swamy，“一种新的基-2/8 FFT算法的长度dft，”IEEE Trans。电路系统。第51卷，没有。9，页1723-1732,2004年9月。
- E. Dubois和A. Venetsanopoulos，“一个新的算法为基-3 FFT，”IEEE Trans。Acoust。，Speech, Signal Process,, vol. ASSP-26, pp.222–225, Jun. 1978.
- S. Prakash和V. Rao，“一种新的基-6 FFT算法”，IEEE Trans。Acoust。，Speech, Signal Process., vol. ASSP-29, no. 4, pp. 939–941,Aug. 1981.
- Y. Suzuki, T. Sone，和K. Kido，“一种新的FFT算法的基数3,6,12，”IEEE Trans。Acoust。，Speech, Signal Process., vol. ASSP- 34,no. 2, pp. 380–383, Apr. 1986.
|
菜单
（4）
（5）
(6）
(7）
（8）
（9)
（10）
