关于FFT算法流图的记忆方法

数字信号课中要求熟练掌握有关按时间抽取(DIT)的FFT算法(库里-图基算法)和按频率抽取(DIF)的FFT算法(桑德-图基算法),本文从这两个方面总结整理了这两种算法的记忆方法,帮助读者在学习FFT的算法流图后快速熟练记忆此流程图.     

旋转因子合并的频率抽取FFT算法RCFA的新解释

对频率抽取FFT算法进行修改,将两级旋转因子进行合并,得到旋转因子合并的频率抽取FFT算法。它与马滕斯(Martens)利用多项式代数理论导出的递归割圆因式分解算法(RCFA)结果完全相同,具有结构简单、计算效率高的优点。与RCFA相比,它便于被工程技术人员理解和使用,还很容易被推广到时间抽取的情况。     

分裂基FFT算法的讨论与改进

文中主要介绍了按频率抽取(DIF)分裂基FFT算法原理及其改进算法.与传统的分裂基算法相比,改进后的算法是利用了旋转因子的周期性、对称性,能够显著地减少旋转因子的个数并且节省ROM的容量.文中通过对改进的频率抽取分裂基-2/4 FFT与分裂基-2/8 FFT的DFT的演算、分析表明改进方法是有效可行.     

基于高速FFT结构的频域抗干扰算法的FPGA实现

提出了一种基于高速FFT结构的算法硬件设计与实现,FFT采用基4算法,旋转因子采用CORDIC算法生成,节省了存储资源,最后在硬件平台上测试,取得了很好的抗干扰效果.     

基于CORDIC算法的流水线型FFT处理器设计

首先分析了基二FFT算法的原理以及在FPGA上实现FFT处理器的硬件结构。其次详细研究了在FPGA上实现FFT的具体过程,利用CORDIC算法实现了旋转因子乘法器,解决了整体设计过程中主要面对的几个关键问题,最终利用Verilog编程实现了基二流水线型FFT处理器,利用MATLAB与MODELSIM结合仿真结果表明该设计满足FFT处理器的基本要求,在10 MHz的采样率下完成32点FFT只需要14.45μs,设计方法也简单易行,具有一定的推广价值。     

计算SDFT的一种新算法

基于按时间抽取的基2FFT算法，本文提出一种计算SDFT的快速算法。该算法可直接利用现有的FFT处理系统，只需更改W系数值，即可得到所需的SDFT值．与已有的算法相比，节省计算量大约20％～50％，该算法可用于SDFT多种应用中。     

FFT复数处理器设计与FPGA验证

本文介绍了一种基于现场可编程门阵列(FPGA)的快速傅里叶变换(FFT)复数处理器设计,可进行1024点复数计算。采用按时间抽取的基-4算法和基于RAM的蝶形结构。同时对最后一级旋转因子进行了优化,减少了存储器的资源占用。使用流水线的处理结构,控制器简单。最后定点matlab建模与Synopsys的仿真器VCS仿真结果进行了对比,功能正确。完成整个运算仅用了2064个周期。最后用Altera公司的Cyclone IV E系列EP4CE10E22C8芯片完成原型验证,在时钟频率为50MHz时,完成1024点复数FFT仅用41.28μs。     

浅析FFT算法中对称关系

本文通过分析比较时间抽取FFT算法以及频率抽取FFT算法的基本原理,揭示了FFT算法中存在的对称关系,同时也给出了任意基FFT算法系数矩阵的产生机理.上述的分析比较有助于学生更好地理解和实现FFT算法,同时也可借鉴该算法的思想设计其他算法.     

通用顺序即位素因子FFT算法

本文从一维到多维的下标变换出发,得到了一种通用顺序,即位素因子FFT算法。与现在的素因子FFT算法相比较,这种算法不仅节省了约一半内存,而且有更高的计算效率。此外,这种算法能很方便地将逆变换也包括在同一程序内。     

用FPGA实现FFT算法

引言 DFT（Discrete Fourier Transformation）是数字信号分析与处理如图形、语音及图像等领域的重要变换工具,直接计算DFT的计算量与变换区间长度N的平方成正比。当N较大时,因计算量太大,直接用DFT算法进行谱分析和信号的实时处理是不切实际的。快速傅立叶变换（Fast FourierTransformation,简称FFT）使DFT运算效率提高1～2个数量级。其原因是当N较大时,对DFT进行了基4和基2分解运算。FFT算法除了必需的数据存储器ram和旋转因子rom外,仍需较复杂的运算和控制电路单元,即使现在,实现长点数的FFT仍然是很困难。本文提出的FFT实现算法是基于FPGA之上的,算法完成对一个序列的FFT计算,完全由脉冲解发,外部只输入一脉冲头和输入数据,便可以得到该脉冲头作为起始标志的N点FFT输出结果。由于使用了双     

TWIDDLE FACTOR MERGED TIME-DECIMAL FFT ALGORITHM AND THE SOFTWARE IMPLEMENTATION FOR TWIDDLE FACTOR MERGED FFT ALGORITHM

Martens proposed a highly efficient and simply formed DFT algorithm——RCFA,whose efficien-cy is comparable with that of WFTA or that of PFA,and whose structure is similar to that of FFT.Theauthors have proved that,in the case of radix 2,the RCFA is exactly equivalent to the twiddle factor mergedfrequency-decimal FFT algorithm.The twiddle factor merged time-decimal FFT algorithm is providedin this paper.Thus,in any case,the FFT algorithm used currently can be replaced by the more efficientalgorithm——the twiddle factor merged FFT algorithm,with exactly the same external property and thesimilar internal structure.Also in this paper,the software for implementing the twiddle factor merged FFTalgorithm(TMFFT)is provided.     

TWIDDLE FACTOR MERGED FREQUENCY-DECIMAL FFT ALGORITHM——A NEW EXPLANATION OF THE RCFA

Merging the twiddle factors in two neighbouring stages for the frequency-decimal FFT algorithm, we can obtain the twiddle factor merged frequency-decimal FFT algorithm. The result is exactly the same as that of the Recursive Cyclotomic Factorization Algorithm (RCFA) derived by Martens (1984) by use of the theory of polynomial algebra. So it has the advantages of simple sturcture and high efficiency in computation. It is much easier to be understood and implemented by engineers than RCFA, and it is also easy to be generalized to the case of time-decimal FFT.     

TWIDDLE FACTOR MERGED FREQUENCY-DECIMAL FFT ALGORITHM——A NEW EXPLANATION OF THE RCFA

Merging the twiddle factors in two neighbouring stages for the frequency-declmal FFTalgorithm,we can obtain the twiddle factor merged frequency-decimal FFT algorithm.The result is exactlythe same as that of the Recursive Cydotomic Factorization Algorithm(RCFA)derived by Martens(1984)byuse of the theory of polynomial algebra.So it has the advantages of simple stureture and high efficiency incomputation.It is much easier to be understood and implemented by engineers than RCFA,and it is also easyto be generalized to the case of time-decimal FFT.     

FFT/DFT旋转因子生成算法误差分析及修正

旋转因子生成是FFT/DFT算法中的重要步骤,直接影响系统实现时的计算速度和资源开销。一种改进的算法给出了一个原理简单、计算速度快、占用存储资源少的旋转因子生成方案。然而系统实现时,乘加单元定点操作会引入截位或舍入误差,且该误差会随着乘加次数的增加而逐级扩散,导致旋转因子精度值下降,无法满足系统性能要求。基于FFT/DFT矩阵分解实现方式,本文给出了旋转因子生成的具体硬件实现结构,以及详细的误差分析。同时采用重定标的误差修订方案以减小误差,并推导出了重定标次数与系统给定条件之间的关系式,便于设计者进行灵活的设计。文章同时引入流水技术提高了系统速率。性能分析表明,相对于以往的算法,本文提出的算法占用的存储资源大大减少;且相对于不进行重定标方案,7次重定标能保证旋转因子精度提高约16个dB。      

Balanced Binary-Tree Decomposition for Area-Efficient Pipelined FFT Processing

This paper presents an area-efficient algorithm for the pipelined processing of fast Fourier transform (FFT). The proposed algorithm is to decompose a discrete Fourier transform (DFT) into two balanced sub-DFTs in order to minimize the total number of twiddle factors to be stored into tables. The radix in the proposed decomposition is adaptively changed according to the remaining transform length to make the transform lengths of sub-DFTs resulting from the decomposition as close as possible. An 8192-point pipelined FFT processor designed for digital video broadcasting-terrestrial (DVB-T) systems saves 33% of general multipliers and 23% of the total size of twiddle factor tables compared to a conventional pipelined FFT processor based on the radix-2² algorithm. In addition to the decomposition, several implementation techniques are proposed to reduce area, such as a simple index generator of twiddle factor and add/subtract units combined with the two's complement operation     

FPGA implementation of high-performance,resource-efficient Radix-16 CORDIC rotator based FFT algorithm

The fast Fourier transform (FFT) is an algorithm widely used to compute the discrete Fourier transform (DFT) in real-time digital signal processing. High-performance with fewer resources is highly desirable for any real-time application. Our proposed work presents the implementation of the radix-2 decimation-in-frequency (R2DIF) FFT algorithm based on the modified feed-forward double-path delay commutator (DDC) architecture on FPGA device. Need for a complex multiplier to carry out the multiplication of complex twiddle factors and large memory to store the twiddle factors are the main concerns for FFT implementation. Propose work aims to address these issues. In this work, a high-performance radix-16 COordinate Rotational DIgital Computer (CORDIC) algorithm based rotator is proposed to carry out the complex twiddle factor multiplication. Further, CORDIC needs only rotational angles to carry out complex multiplication, which reduces the need for large memory to store the twiddle factors. To compute the total rotation for n-bit precision, our proposed radix-16 CORDIC algorithm takes n/4 iteration as compared to n iteration of the radix-2 CORDIC algorithm. Our proposed architecture of the radix-2 decimation-in-frequency (R2DIF) algorithm is implemented on a Virtex−7 series FPGA. Further, the detailed comparison is presented between our proposed FFT implementation and other recently proposed FFT implementations. Experimental results suggest that proposed implementation has less latency and hardware utilization as compared to recently proposed implementations.     

基于超大点数FFT优化算法的研究与实现

针对应用系统对超大点数快速傅里叶变换(FFT)的性能需求不断提升,以及现有处理平台的资源对实现超大点数FFT的制约问题,该文提出一种超大点数FFT的实现方法。该方法通过优化铰链因子存储,采用行列号方式访问2维矩阵避免了3次显性转置,从而节省了内存资源;同时,通过分析处理器的分级存储结构特点,优化了矩阵行列划分规则,进而提高了行列访问效率。实验结果表明,该方法节约了近一半的内存资源,且有效提高了超大点数FFT的执行速度。     

Configurable Floating-Point FFT Accelerator on FPGA Based Multiple-Rotation CORDIC

Fast Fourier transform (FFT) accelerator and Coordinate rotation digital computer (CORDIC) algorithm play important roles in signal processing.We propose a conflgurable floating-point FFT accelerator based on CORDIC rotation,in which twiddle direction prediction is presented to reduce hardware cost and twiddle angles are generated in real time to save memory.To finish CORDIC rotation efficiently,a novel approach in which segmentedparallel iteration and compress iteration based on CSA are presented and redundant CORDIC is used to reduce the latency of each iteration.To prove the efficiency of our FFT accelerator,four FFT accelerators are prototyped into a FPGA chip to perform a batch-FFT.Experimental results show that our structure,which is composed of four butterfly units and finishes FFT with the size ranging from 64 to 8192 points,occupies 33230(3％) REGs and 143006(30％)LUTs.The clock frequency can reach 122MHz.The resources of double-precision FFT is only about 2.5 times of single-precision while the theoretical value is 4.What's more,only 13331 cycles are required to implement 8192-points double-precision FFT with four butterfly units in parallel.     

WFTA算法的FPGA设计与实现

Winograd傅里叶变换算法（WFTA）利用旋转因子W的特性对其进行分解,能够把FFT运算中乘法次数降到最低,是一种高效且资源占用相对较少的FFT实现方法。以256点分解为两维16×16点的小数组WFTA进行运算为例介绍了大数组WFTA算法的FPGA设计与实现方案。仿真测试表明,所设计的256点FFT处理器,乘法器资源消耗仅为基-2FFT的1/2、基-4FFT的2/3,且在100 MHz主时钟频率下完成运算仅需5.8μs,满足FFT处理器的高速实时性要求。