时间抽取情况下的旋转因子合并FFT算法和TMFFT的软件实现

马滕斯(Martens)提出了一种效率高(可与WFTA法和PFA法相比拟)、结构简单(与FFT法相似)的DFT计算方法RGFA。作者已经证明,在基2的情况下,RCFA与旋转因子合并的频率抽取FFT算法是完全等价的。本文给出了旋转因子合并的时间抽取FFT算法,从而使得在任何条件下,目前使用的FFT算法都可以用外部特性完全相同、内部结构基本相同的高效算法旋转因子合并FFT算法来代替。本文还给出了实现旋转因子合并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-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.     

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

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

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.     

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/DFT旋转因子生成算法误差分析及修正

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

一种高精度的大点数二维FFT处理器设计

基于传统的频域抽取快速傅里叶变换(FFT)算法以及二维FFT算法,设计了一种高精度的大点数FFT处理器。该处理单元采用一个状态机控制整个运算流程,针对小点数情况的一维FFT算法和大点数情况的二维FFT算法,该处理器都可以智能地选择合适的处理流程和缓存管理,自动地完成整个FFT运算而无需软件介入。在支持大点数的二维FFT算法的基础上,该设计还通过对旋转因子计算过程的优化,以提高在大点数情况下的精度表现,在4M长度的输入序列时可以获得130 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     

A new radix-2/8 FFT algorithm for length-q/spl times/2/sup m/ DFTs

In this paper, a new radix-2/8 fast Fourier transform (FFT) algorithm is proposed for computing the discrete Fourier transform of an arbitrary length N=q/spl times/2/sup m/, where q is an odd integer. It reduces substantially the operations such as data transfer, address generation, and twiddle factor evaluation or access to the lookup table, which contribute significantly to the execution time of FFT algorithms. It is shown that the arithmetic complexity (multiplications+additions) of the proposed algorithm is, in most cases, the same as that of the existing split-radix FFT algorithm. The basic idea behind the proposed algorithm is the use of a mixture of radix-2 and radix-8 index maps. The algorithm is expressed in a simple matrix form, thereby facilitating an easy implementation of the algorithm, and allowing for an extension to the multidimensional case. For the structural complexity, the important properties of the Cooley-Tukey approach such as the use of the butterfly scheme and in-place computation are preserved by the proposed algorithm.     

A GENERAL IN-PLACE AND IN-ORDER PRIME FACTOR FFT ALGORITHM

Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,     

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

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

Programming an efficient radix-four FFT algorithm

A novel way of organizing a twiddle factor table and indexing butterfly terms for efficiently computing the radix-4 fast Fourier transform is presented. The twiddle factors are stored in radix-4 digit reversed order and the algorithm uses a recursive formula derived from Bergland's [5] radix-8 formula.     

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

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

一种旋转因子访存优化的FFT算法

为了在嵌入式设备中高效运行快速傅里叶变换算法,提出了一种针对小尺寸高速缓冲存储器优化的旋转因子的生成与访存策略,该方法能够有效提高缓存命中率及运算速率。给出了不同需求下配置参数的选取原则,基于典型算法配置参数和目标处理器平台进行算法测试。实验结果证明,优化后的方法在信噪比性能下降较小的情况下能够获有效地提升计算速率。     

A New Overlap Save Algorithm for Fast Block Convolution and Its Implementation Using FFT

Convolution of data with a long-tap filter is often implemented by overlap save algorithm (OSA) using fast Fourier transform (FFT). But there are some redundant computations in the traditional OSA because the FFT is applied to the overlapped data (concatenation of previous block and the current block) while the DFT computations are recursive. In this paper, we first analyze the redundancy by decomposing the OSA into two processes related to the previous and current block. Then we eliminate the redundant computations by introducing a new transform which is applied only to the current data, not to the overall overlapped data. Hence the size of transform is reduced by half compared to the traditional OSA. The new transform is in the form of DFT and it can be implemented by defining a new butterfly structure. However we implement it by a cascade of twiddle factor and conventional FFT in this paper, in order to use the FFT libraries in PC and DSP. The computational complexity in this case is analyzed and compared with the existing methods. In the experiment, the proposed method is applied to several block convolutions and partitioned-block convolutions. The CPU time is reduced more than expected from the arithmetic analysis, which implies that the reduced transform size gives additional advantage in data manipulation.     

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.     

一种新的1024点基-2 FFT旋转因子产生电路的结构

设计了一个新的无存储器的基-2 1024点FFT旋转因子产生电路.这个旋转因子产生电路用若干逻辑模块来产生数据,然后用这些数据合成所需要的旋转因子.用Synopsys Power Compiler进行功耗分析表明,用TSMC 0.25μm CMOS工艺综合出来的电路在50MHz时的功耗为2mW.这种旋转因子产生电路非常适合用于低功耗的设计中,尤其是移动通信和其他手持设备中.     

超长点数FFT处理器的旋转因子生成方法

对于大点数FFT处理器,提出了一种新的旋转因子生成方法。首先对三角函数曲线分段进行折线近似,将线段端点及斜率存入存储器,然后通过查表以及插值计算的方法来生成旋转因子。在保证FFT计算精度的前提下,极大地降低了对旋转因子存储器容量的需求,对大点数FFT处理器的单片ASIC实现具有重要意义。     

基于Vivado HLS 的FFT IP核设计与实现

研究基于Xilinx高层次综合工具HLS设计FFT IP核的新方法,并在Zynq平台上搭建音频频谱显示系统用于对设计的FFT IP核进行测试。首先用Matlab生成1024点FFT算法所需要的旋转因子,然后用C语言编写FFT算法程序后经HLS综合成IP核并进行了两次优化,与优化前相比延迟时间节省了19%到40%,LUT资源节省18.5%。测试结果表明,所设计的FFT IP能够成功地实现音频信号的频谱分析。     

二维级联流水结构大点数FFT运算器实现研究

大点数快速傅里叶变换(FFT)运算在雷达、通信信号侦察中有广泛应用,其基于现场可编程门阵列(FPGA)的实现方法有重要的研究价值。推导出点数为N的大点数FFT运算分解为2级小点数FFT运算级联的运算公式,在此基础上给出其实现步骤,从流水线结构设计、基本运算单元以及地址生成等方面详细介绍一维列(行)变换的工程实现方法,并给出列、行变换之间所乘旋转因子的压缩算法。工程实际应用表明,该大点数FFT运算器具有变换速度快、调试方便及可在单片FPGA实现的优点。