快速傅立叶变换算法概述

快速傅立叶变换（FFT）属于数字信号处理中最基础的运算,已广泛应用于通讯、医学电子学、雷达或无线电天文学等领域。对FFT的主要算法进行了概述 ,并对其特性和运算工作量进行了分析和对比,期望对快速傅立叶变换算法有一个清晰的认识。     

快速傅立叶变换算法概述

快速傅立叶变换（FFT）属于数字信号处理中最基础的运算，已广泛应用于通讯、医学电子学、雷达和射电天文学等领域。本文对FFT的主要算法作了概述，并对其特性和运算工作量进行了分析和对比，期望对快速傅立叶变换算法有一个清晰的认识。     

一种新型的快速模板匹配算法

提出了一种基于快速傅立叶变换的快速模板匹配算法。针对现有模板匹配算法运算量大,计算速度在现有技术条件下受到制约的问题,提出基于快速傅立叶变换的快速模板匹配算法,利用傅立叶变换中的卷积定理,结合快速傅立叶变换(FFT),将计算量大为减少,同时使用单指令多数据流(IMD)算法实现了加速,收到了良好的效果。     

长序列信号快速相关及卷积的算法研究

文章通过对快速傅立叶变换（FFT）的算法原理分析,根据线性相关和卷积的数学特征及物理含义,针对长序列信号,提出了一种基于FFT的长序列快速相关及卷积算法,用C＋＋进行了算法编程,在计算机上得到较好的实验效果,提高了运行速度,并结合算术傅立叶变换进行了改进。     

用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输出结果。由于使用了双     

DIF-2FFT算法的矩阵形式的DLP计算模式

快速傅里叶变换(FFT)是减少离散傅里叶变换(DFT)计算时间的算法。而在无线/移动通信系统中无线通信算法和多媒体应用处理算法中存在大量的矩阵或向量运算,均可以由DLP计算实现。本文研究的FFT算法就存在大量的矩阵运算,通过对FFT矩阵算法的分析,本文提出了在DLP计算模式下通过阵列计算机来实现FFT的快速算法,在MATLAB仿真平台上进行了传统算法与改进之后算法的比较,提出了进一步减少运算时间的FFT并行算法。     

用Xtensa可配置处理器实现高性能低功耗系统

可配置处理器允许嵌入式开发人员来定制适合目标算法的处理器,使得处理器和算法能够更好地匹配。设计人员可以增加专用的、可变宽度的寄存器,专用的执行部件和更宽的数据总线以达到专用算法的最优处理器配置。加速FFT运算按频率抽取快速傅立叶变换FFT算法的核心是一种称为“蝶形”的运算。蝶形操作是FFT算法的最里层循环的运算。每个蝶形运算需要六次加法和四次乘法来计算基2蝶形结果的实部和虚部。采用TI(ETensilicaIn-structionExtention)语言,设计团队可以用四个加法器和两个乘法器来扩展整个Xtensa处理器的流水线,以便使得一半F…     

基于FPGA的快速傅立叶变换

在对FFT(快速傅立叶变换 )算法进行研究的基础上 ,描述了用FPGA实现FFT的方法 ,并对其中的整体结构、蝶形单元及性能等进行了分析。     

快速傅立叶变换辅助设计数字低通滤波器

详尽讨论了快速傅立叶变换(FFT)应用于有限冲击响应(FIR)数字低通滤波器(DLPF)的设计和分析方法.应用FFT算法,将理想DLPF幅频特性转换到变换域,获得其变换域序列;设计窗函数对该序列开窗,获得FIR有限序列;应用快速傅立叶逆变换(IFFT)对其进行变换,获得相应窗函数可实现DLPF幅频特性.结果发现,FFT算法可获得与传统卷积算法相同的结果;不需要推算窗函数的频谱解析表达式;可以处理Kaiser窗等变换域解析式复杂、频域解析式难以精确求解的窗函数设计与分析.与传统的卷积分析法相比,FFT不仅算法简单、灵活,而且处理能力强,是分析FIR DLPF设计的有力工具.     

基于FPGA的激光测距系统中基4算法的FFT研究

文章提出了利用可编程逻辑器件FPGA通过硬件来实现快速傅立叶变换( FFT)的基4 算法,提出了采用两个蝶形运算器同时并行计算,每次蝶形运算按顺序进行的结构,将并行处理与顺序处理相结合,提高并行度和数据吞吐量,每次蝶形运算时间不超过1μs,完成整个256点复数FFT运算大约需要120μs左右,同时又节省资源。该方法在激光矿井提升机位置跟踪系统中应用取得了良好效果。     

A Speech Scrambler Using the Fast Fourier Transform Technique

This paper describes an analog speech scrambler using the FFT technique (FFT scrambler). The FFT scrambler provides highly secured scrambled signal by permuting a large number of FFT coefficients. Important items to be considered in the designing of the FFT scrambler are discussed, such as FFT frame length, permutation of FFT coefficients, and frame synchronization, in addition to the configuration of the experimental FFT scrambler. Possible causes for the degradation of the descrambled signal, such as transmission channel group delay and intersymbol interference, are also discussed, together with experimental results.     

New continuous-flow mixed-radix (CFMR) FFT Processor using novel in-place strategy

The paper proposes a new continuous-flow mixed-radix (CFMR) fast Fourier transform (FFT) processor that uses the MR (radix-4/2) algorithm and a novel in-place strategy. The existing in-place strategy supports only a fixed-radix FFT algorithm. In contrast, the proposed in-place strategy can support the MR algorithm, which allows CF FFT computations regardless of the length of FFT. The novel in-place strategy is made by interchanging storage locations of butterfly outputs. The CFMR FFT processor provides the MR algorithm, the in-place strategy, and the CF FFT computations at the same time. The CFMR FFT processor requires only two N-word memories due to the proposed in-place strategy. In addition, it uses one butterfly unit that can perform either one radix-4 butterfly or two radix-2 butterflies. The CFMR FFT processor using the 0.18 /spl mu/m SEC cell library consists of 37,000 gates excluding memories, requires only 640 clock cycles for a 512-point FFT and runs at 100 MHz. Therefore, the CFMR FFT processor can reduce hardware complexity and computation cycles compared with existing FFT processors.     

An expandable column fft architecture using circuit switching networks

The Fast Fourier Transform (FFT) is widely used in various digital signal processing applications. The performance requirements for FFT in modern real-time applications has increased dramatically due to the high demand on capacity and performance of modern telecommunication systems, where FFT plays a major role. Software implementations of FFT running on a general purpose computer can no longer meet current speed requirements. However, recent advances in VLSI technology have made it possible to implement the entire FFT system on a single silicon substrate. This article presents a column FFT design suitable for ULSI (Ultra Large Scale Integration) implementations. The basic building block is a 64-point column FFT. FFTs with longer transform lengths can be easily realized using the 64-point column FFT building block. The butterfly processors in the column FFT are connected using circuit switching networks. The circuit switching networks not only provide dynamically recon-figurable interconnections among the butterfly processors, but also provide a fault-tolerant capability. Bit-serial arithmetic is used in the architecture. Assuming the data word length is 16 bits, the 1024-point column FFT engine proposed in this article is capable of processing 1024 complex data samples in 533 clock cycles. If the clock frequency is 40 MHz, it will take 13.3 µs to complete a 1024-point FFT.     

基于多核处理器BWDSP1042的FFT性能优化

博微DSP1042(BWDSP1042)是我国自主研发的一款高性能数字信号处理器.现阶段,由于BWDSP硬件计算资源和访存带宽限制,通过调优快速傅里叶变换(Fast Fourier Transform,FFT)算法结构运算时间仍可减少.基于高性能多核BWDSP1042体系架构以及指令编排原则,优化了基-2FFT算法结构...     

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

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

高速64点FFT芯片设计技术

针对高速64点FFT(快速傅里叶变换)处理芯片的实现,分析了FFT运算原理,并根据FFT算法原理介绍了改进的FFT运算流图。介绍了FFT处理器系统的各模块的功能划分,并根据FFT处理器结构及其特殊寻址方式,采用Verilog HDL对处理器系统的控制器、双数据缓存、地址生成器、蝶形运算单元以及I/O控制等模块进行了RTL(寄存器传输级)设计,并在ModelSim中对各模块以及整个系统进行功能仿真和验证,给出了部分关键模块的仿真波形图。设计中,注重从硬件实现以及电路的可综合性等角度进行RTL电路设计,以确保得到与期望性能相符的硬件电路。     

定点FFT量化误差模型及性能分析

介绍了快速傅里叶变换（FFT）的基本原理,针对硬件实现中的定点运算,分析推导出了不同FFT长度扣不同量化位数带来的误差模型,并进行了实验验证。结果表明,相同量化位数条件下,FFT长度越长误差越大;相同FFT长度条件下,量化位数越多,误差越小。实验结果为FFT设计提供了参考。     

基于ZP-FFT提高雷达检测性能的仿真分析

当目标的多普勒频率与FFT滤波器组不精确匹配时,信号单元的部分能量会产生泄漏。提出了对FFT输入信号进行零填充(Zero-Padding,ZP)的ZP-FFT方法,并推导了相应的处理增益(Processing Gain,PG)公式。与FFT、FFT-DWT (Discrete Wavelet Transform)和FFT/FFT-DWT相比,ZP-FFT在保持较低运算量的同时提高了PG值。仿真结果进一步表明, ZP-FFT在整个频率范围上有比其它三种方法更好的检测性能。     

由FFT芯片构成的并行FFT结构

快速傅立叶变换（ＦＦＴ）在计算机层析影象技术,语间识别,图像处理等域得了广泛的应用。随着计算机应用的发展,越来越需要对大规模的数据进行变换。并行ＦＦＴ是完成快速数据变换的一种方法。本文提出一咱由小规模ＦＦＴ芯片构成并行ＦＦＴ的方法,楞用于大规模数据的变换,并对其并行结构的面积和执行时间进行了探讨,还提出了具有容错功能的并行ＦＦＴ网络。     

一种按时间抽取的混合基实序列高效FFT算法

针对2N点实序列FFT的实现,分析了FFT运算的基本原理,并在基本原理的基础上介绍了一种按时间抽取的混合基FFT算法.此算法采用"包装"算法和基2-基4混合算法结合的方法进行运算.通过复杂度分析,显示了此算法与传统的单一基2或基4的FFT相比,大大减少了计算过程中所需的实加法的个数;当点数大于1024时,所需实乘法的个数也有所减少.这是一种实序列FFT的高效低复杂度算法.