快速傅立叶变换算法概述

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

快速傅立叶变换算法概述

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

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

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

用FPGA实现快速傅立叶变换

介绍了一种基于FPGA的FFT算法的实现方法。用VHDL语言完成系统设计描述，经过编译、综合和下载，给出了仿真测试的结果。在FPGA芯片上运行的兀叩算法具有速度快和抗干扰能力强的硬件实现的优点；用VHDL语言实现的基于FPGA的FFT算法具有很好的可移植性，可以重复使用，从而大大提高了设计效率。     

基于小波变换和快速傅立叶变换的电网谐波分析

谐波分析是谐波治理和研究谐波问题的基础。文中介绍了一种将小波变换和快速傅立叶变换结合起来的谐波分析方法,给出了电能质量信号突变点的确定公式,并对三相全控桥式整流电路产生的谐波电流进行仿真分析,得出了采用这种方法能够分别检测出扰动信号的起止时刻,也能够分析各次谐波的幅值和相角的结论。     

数字信号处理中关于高维离散傅立叶变换的PM向量编码算法

在数字信号处理中,离散Fourier变换是一种很重要的数学工具,它的应用十分广泛。本文提出的PM向量编码算法是一种新的计算高维离散傅立叶变换的快速算法。在采样点数相同的情况下,与现行的几种算法相比,PM向量编码算法在计算量和运算时间上都有不同程度的降低,从而提高了运算效率。这在实际应用中具有十分重要的意义。     

基于快速傅立叶变换的在线电网谐波分析仪

在用电设备中广泛使用各种电力电子器件,往往会引起供电电网电压波形发生畸变,即谐波污染,会带来许多危害。在线电网谐波分析仪就是为了监测电力谐波污染而设计的。其整个设计过程采用模块化设计的思想。系统硬件主要包括电源模块,传感器前端电路模块,TMS320F2812数字信号处理器(DSP)主电路板模块。系统软件主要包括人机界面(HMI)程序模块,模数转换(ADC)程序模块,快速傅立叶变换(FFT)程序模块。     

DFT-S-GMC无线接入系统56点快速傅立叶变换算法设计

提出了应用于DFT-S-GMC(DFT Spread generalized Multi-carrier)宽带无线接入系统中56点DFT/IDFT的快速算法.该算法组合Cooley-Tukey和Winogrgd算法的设计方法,将56点三次奇偶分解为8个7点的傅立叶变换,经特定的整序算法处理后,由Winograd算法得到各7点DFT/IDFT的快速算法,最后借鉴Cooley-Tukey算法的蝶形运算得到56点FFT/IFFT的运算结果.该算法的运算速度比复合数算法快若干倍,亦可推广用于设计N=P*2M(P=3,5,7,11等)这一类特殊点的FFT/IFFT算法.     

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

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

一种改进的二维离散极坐标Fourier变换快速算法

在雷达天线、图象配准、图象检索等领域内常常需要用极坐标表示二维数字信号的离散Fourier变换(DFT).与笛卡尔坐标系下的二维DFT不同,二维离散极坐标Fourier变换(DPFT)不具有行列可分性,直接计算非常耗时.本文提出一种改进的DPFT的快速算法.该算法针对二维阵列实信号,算法全部过程可用一维运算实现,大大降低了计算复杂度并且适用于实时处理.实验中与直接运算方法相比较,显示了该算法的良好性能.     

快速傅立叶变换在声音均衡和频谱中的应用

文中针对数字化音频处理中声音均衡和频谱显示的问题,提出了采用FFT算法的设计方案和具体实现.在介绍FFT算法基本原理的基础上,比较深入地分析其特点,采用FFT算法使时域上表现的声音信号转化为频域信号,分别对各频段处理后,再次由FFT转化回时域,完成声音信号均衡和频谱显示等功能,并给出了具体的实现方案.通过对均衡和频谱显示的处理,总结出对声音信号频率的处理,均可采用时域到频域再回到时域的通用方案.数字化音频处理,是未来音频处理的发展的主要方向.     

Low-Cost Fast VLSI Algorithm for Discrete Fourier Transform

A primeN-length discrete Fourier transform (DFT) can be reformulated into a (N-1)-length complex cyclic convolution and then implemented by systolic array or distributed arithmetic. In this paper, a recently proposed hardware efficient fast cyclic convolution algorithm is combined with the symmetry properties of DFT to get a new hardware efficient fast algorithm for small-length DFT, and then WFTA is used to control the increase of the hardware cost when the transform length Nis large. Compared with previously proposed low-cost DFT and FFT algorithms with computation complexity of O(logN), the new algorithm can save 30% to 50% multipliers on average and improve the average processing speed by a factor of 2, when DFT length Nvaries from 20 to 2040. Compared with previous prime-length DFT design, the proposed design can save large amount of hardware cost with the same processing speed when the transform length is long. Furthermore, the proposed design has much more choices for different applicable DFT transform lengths and the processing speed can be flexible and balanced with the hardware cost     

一种新的分数阶傅立叶变换快速算法

本文给出了分数阶傅立叶变换(FRFT)的定义,介绍了已有的几种离散FRFT快速算法,并简要分析了这几种算法的优缺点.在此基础上提出了一种新的FRFT快速算法.该算法避开特征值与特征向量的匹配问题,具有易理解、易实现、效果好等优点.并且在改变分数阶幂时不需重新计算整个过程,只需计算一个对角矩阵.为与其他方法作比较,作者最后对几个典型信号作了计算机仿真,并给出其仿真结果.     

一种分数阶傅里叶变换快速算法的研究

介绍了分数阶傅里叶变换的定义,接着提出了一种分数阶傅里叶变换的快速算法,其中分数阶傅里叶变换快速算法分三步进行:线性调频信号乘法,线性调频信号卷积,另一个线性调频信号乘法,从而利用FFT来计算FRFT。这种算法思想直观,结果与连续FRFT的输出接近。最后用具体的信号作了计算机仿真,并给出Matlab仿真结果图。     

基于算术傅里叶变换的小波变换快速算法

利用算术傅里叶变换(AFT)计算离散傅里叶变换(DFT)可使其乘法计算量仅为D(N）。文章根据这一特点，结合Mallat算法原理及离散傅里叶算法结构特征，提出了一种离散小波变换的快速算法，给出了数学推导过程，并对实验结果进行了分析。     

超高速全并行快速傅里叶变换器

设计和实现超高速快速傅里叶变换器(FFT)在雷达与未来无线通信等系统中具有重要意义。该文提出首个全并行架构的FFT处理器,其避免了复杂的路由寻址以及数据访问冲突等问题,基于较大基进行分解降低运算复杂度。由于旋转因子已知和固定,大量的乘法转化为了定系数乘法。同时由于采用了串行的计算单元,在达到全并行结构的高速度同时硬件复杂度相对较低;所有的硬件计算单元处于满载的条件,其硬件效率能达到100%。根据实际的实现结果,所提出的512点FFT处理器结构能够达到5.97倍速度面积比的提升,同时硬件开销仅占用了Xilinx V7-980t FPGA 30%的查找表资源与9%的寄存器资源。     

采用异步实现的快速傅里叶变换处理器

介绍一种采用异步实现结构的快速傅里叶变换处理器,该处理器的控制采用本地握手信号取代传统的系统时钟。给出了处理器中异步加法器的电路结构,设计了一个采用Booth译码Wallace tree结构的异步乘法器。通过对一个8点的异步快速傅里叶变换处理器进行电路仿真,得到该处理器完成一次变换的平均响应时间为31.15 ns,仅为最差响应时间42.85 ns的72.7%。可见,采用异步方式的快速傅里叶变换处理器在性能方面较同步处理器存在优势。     

基于快速傅里叶变换的局部分块视觉跟踪算法

针对视觉跟踪中目标表观变化、局部遮挡、背景干扰等问题,该文提出一种基于快速傅里叶变换的局部分块视觉跟踪算法。通过建立目标分块核岭回归模型并构建循环结构矩阵进行分块穷搜索来提高跟踪精度,利用快速傅里叶变换将时域运算变换到频域运算提高跟踪效率。首先,在包含目标的初始跟踪区域建立目标分块核岭回归模型;然后,提出通过构造循环结构矩阵进行分块穷搜索,并构建目标分块在相邻帧位置关系模型;最后,利用位置关系模型精确估计目标位置并进行分块模型更新。实验结果表明,该文算法不仅对目标表观变化、局部遮挡以及背景干扰等问题的适应能力有所增强,而且跟踪实时性较好。