基于ARMv8处理器的实数FFT实现与性能优化研究

FFT(快速傅里叶变换)是离散傅里叶变换或其逆变换的一种常见快速算法,是高性能计算领域最重要的基础核心算法之一,在科学、工程和数学等领域的应用十分广泛.实数FFT算法,即输入或者输出为实数的FFT算法,其中包括R2C(Real-to-Complex)、C2R(Complex-to-Real)等变换类型.相比复数FFT算法,实数FFT算法在图形图像处理、数据压缩等领域有着不可替代的作用.传统实数FFT实现针对的是输入规模为偶数,一般转变为复数FFT进行运算.然而当前鲜有针对输入规模为奇数的实数FFT高效实现.对此,本文提出了一种实数FFT高效算法(DRFFT),并采用蝶形网络优化、蝶形计算优化、访存优化、SIMD优化以及数据转置等方法进行优化,大幅提升了实数FFT算法性能,最终构建了一种针对实数FFT的高性能算法库.实验结果表明,本文实现的DRFFT R2C变换在单双精度浮点数处理方面较FFTW库性能分别平均提升了37.6%和4.6%,较ARMPL库性能分别平均提升了67.6%和28.1%.DRFFT C2R变换在单双精度浮点数处理方面则较FFTW库性能分别平均提升了58.6%和10.8...     

嵌入式系统中FFT算法研究

首先分析实数FFT算法的推导过程,然后给出一种具体实现FFT算法的C语言程序,可以直接应用于需要FFT运算的单片机或DSP等嵌入式系统中。     

嵌入式系统中FFT算法研究

首先分析实数FFT算法的推导过程,然后给出一种具体实现FFT算法的C语言程序,可以直接应用于需要FFT运算的单片机或DSP等嵌入式系统中.     

多维离散Hartley变换的快速算法

近几年,由于快速Hartley变换(PHT)算法的提出,使DFT的计算面目一新,而且用FHT计算褶积比用FFT优越得多。利用两种变换间的简单关系,借助于FHT不用复数运算和计算结果是实数存储的优点,可以使实数据DFT或褶积节省一半的内存,且速度与实数据FFT算法的速度相同。但是,目前对多维DHT尚无成熟算法(只有二维和三维的算法),本文首次提出适于多维DHT的快速算法。它直观且易于在计算机上实现,从而使得用多维快速DHT计算多维DFT及褶积成为可能,同时也为实谱分析方法提供了一种新的工具。     

基于DSP的实数FFT算法研究与实现

介绍了一种实数快速傅里叶变换(FFT)的设计原理及实现方法,利用输入序列的对称性,将2N点的实数FFT计算转化为N点复数FFT计算,然后将FFT的N点复数输出序列进行适当的运算组合,获得原实数输入的2N点FFT复数输出序列,使FFT的运算量减少了近一半,很大程度上减少了系统的运算时间,解决了信号处理系统要求实时处理与傅里叶变换运算量大之间的矛盾．同时,给出了在TMS320VC5402 DSP上实现实数FFT的软件设计,并比较了执行16,32,64,128,256,512,1024点实数FFT程序代码与相同点数复数FFT的程序代码运行时间．经过实验验证,各项指标均达到了设计要求．     

高效FFT硬化方案

本文应用Cooley-TuKey经典算法,采用双加法器和“映像”存储器,获得100％的高效FFT流水蝶形运算,使1024个实数点达到1毫秒的速度,并导出其硬化的寻址、运算序列。 通常计算N点DFT,也即FFT可以用下式表示:     

FFT的DSP汇编算法的改进

本文在循环型DIT-FFT的DSP汇编算法查表实现的基础上，用1/4周期的因子表取代原有的两具周期的因子表，并把长度为2N的实数计算序列，转化为长度为N的复数序列进行FFT变换，从而改进了原算法的时间和空间复杂度及程度存储空间。     

快速傅里叶变换的高效算法及其实现

本文利用欧拉公式及DFT的时移特性,将复指数W~k化为纯数(纯实数或纯虚数),使复数FFT蝶式运算的实乘法从四次减为二次,W~k的生成次数减少一半,同时由于采用递推算法生成W~k,节省了运算时间。利用数字序列可奇偶分解及DFT的对称性质,把纯数对称序列FFT蝶式运算的实乘法减为一次,并通过只存贮正频率分量来节省存贮空间。提高了变换速度和空间利用率。算法已分别在APPLEII及ZD-065机上实现。     

节省乘法次数的FFT程序

计算离散Fourier变换(DFT)快速算法的种类各式各样,因此实现FFT程序也是名目繁多的.介绍了一种FFT程序(以下简称程序1),使用它计算一个长度N=2~m(m为大于1的整数)的复数序列需要2Nlog_2N次实数乘法,但这个程序在运算量的节省上还有很大潜力.在此,我们给出一种FFT程序(以下简称程序2),它以程序1为基础,不多占存贮单元,但计算N点复数序列仅需     

基于混合卷积窗和双窗法的FFT算法研究

FFT算法是信号处理中一个不可或缺的部分,也是其中需要改进的部分。设计一个精度优良的FFT算法有助于推进频谱分析的实用化进程。针对FFT改进算法的实现需求,文章采用了C语言结构设计了一个任意点数的FFT算法,分析了混合卷积窗的频谱特性,并总结了任意窗函数的幅值恢复方法。最终通过构建混合卷积窗和双窗法结合的处理方法有效提高了FFT算法的精度,仿真结果表明,与普通FFT、混合卷积窗、双窗法方法相比,基于混合卷积窗和双窗法结合的FFT算法具有更高的精度。     

分裂基算法在管道腐蚀超声内检测中的应用

管道腐蚀内检测中超声回波信号具有周期性特点,功率谱估计是重要的数据处理方法之一。基于分裂基的FFT算法具有较小的乘法次数和加法次数,且算法结构较好。采用频率抽取分裂基2／4 FFT算法对管道腐蚀超声内检测回波信号进行了处理．得到管道壁厚数据,经分裂基FFT算法和基2 FFT算法比较,分裂基FFT算法明显减少了数据处理时间,提高了检测速度。理论分析和实验结果表明,该分裂基算法精度高,数据处理速度快,满足管道腐蚀内检测的实时性要求。     

基于FPGA的FFT算法研究

本文针对目前数字信号处理中广泛采用的快速傅里叶变换FFT(Fast Fourier Transform)算法采用软件编程来实现的应用现状,在对FFT算法进行分析的基础上,研究基于FPGA(Field Programmable Gate Array)芯片的FFT算法,把FFT算法对实时性的要求和FPGA芯片设计的灵活性结合起来,采用Altera公司的Cyclone Ⅱ系列FPGA芯片中的FFT megacore IP核来定制FFT功能,最后分别使用Quartus Ⅱ和matlab软件开发工具验证实现.     

基于CUDA的高速FFT计算*

针对快速傅里叶算法FFT在图形图像处理和科学计算领域的重要作用,提出了一种基于CUDA的高速FFT计算方法,在分析GPU硬件平台执行模式及FFT算法并行性特征的基础上,采用多线程并行的映射方法实现算法,并从存储层次优化算法。实验结果表明该算法的高效性,优化后的FFT加速比能达到CUFFT库加速比的2-6倍。     

FFT信号分析仪应用简介

<正> 自从1965年Cooley和Tucky提出快速付立叶(FFT)算法以后,解决了利用数字计算技术进行付立叶分析所迂到的计算工作量大、计算时间长的老大难问题。接着出现了各种根据FFT算法制造的FFT信号分析仪,为各个科技领域提供了迅速、方便、有效的分析手段。目前,FFT算法和FFT信号分析设备正在不断地渗透到每个涉及付立叶变换的领域。我国从七十年代初期引进、研制,应用FFT算法和设备以来,现在正在逐渐广泛地为各部门、备单位所了介和应用。下面简介FFT分析仪的若干应用。     

基于超大规模FPGA的FFT设计与实现

在宽带数字接收机中,需要对数字检波输出的信号流进行实时FFT运算。提出了一种用于宽带数字接收机的基于Xilinx的Virtex-IV芯片的高速FFT的设计与实现方法,采用了多级串行流水线结构及优化的数据存取方式,设计出用单片FPGA实现了2048点实数的FFT方案。其完成2048点FFT的时间约为4.57μs,能很好地满足系统处理的实时性要求,在工程实践中有很大的应用前景。     

改进的基于FFT pruning 的窄带高分辨率频谱算法

提出一种改进的基于FFT pruning的窄带高分辨率频谱计算方法。该方法是对Sreenivas’s FFT pruning 算法和 Nagai 的利用频移变换的FFT pruning 算法的推广。同时提出输出点分级思想,可实现任意窄带上非2的整数幂次频点输出。该算法比Sreenivas’s FFT pruning 算法具有更小的计算量和更简单的信号流图。     

频域抽取多维向量基快速傅里叶变换

给出了频域抽取(DIF)多维向量基快速傅里叶变换(FFT)算法。对多维频域信号的每一维,采用向量基2频域抽取法,导出了快速算法蝶形运算的一般形式。该FFT算法适合于维数为任意整数的情况,当维数为1时,算法退化为著名的频域抽取向量基2 FFT算法。为了便于编程实现,以频域抽取3维向量基FFT算法为例,给出了快速算法实现流程,该流程易于向任意整数维推广。计算量比较结果显示,频域抽取多维向量基FFT算法比多维分离式FFT算法计算量低。     

基于FPGA的IFFT处理器设计

通过分析FFT的Cooley-Tukey算法,导出相应的IFFT算法。采用Altera公司的Cyclone Ⅱ系列FPGA芯片中的FFT megacore IP核定制FFT功能,分别使用Quartus Ⅱ和VHDL开发工具验证实现。     

大规模集群上多维FFT算法的实现与优化研究

快速傅里叶变换(fast Fourier transform,FFT)是用于计算离散傅里叶变换(discrete Fourier transform,DFT)或其逆运算的快速算法,在工程、科学和数学领域的应用非常广泛,例如信号分解、数字滤波、图像处理等。因此,在实际应用中对FFT算法进行细粒度优化是非常重要的。研究了FFT算法常用的分解策略以及FFT算法在大规模集群系统上的并行实现,并提出了相关的优化策略。在此基础上,对多种FFT算法在不同平台上进行了性能评估,并分析了各算法的实现、优缺点及其在大规模计算时的可扩展性。实验结果表明,相关研究有助于对现有的FFT算法进行进一步的优化,以及指导如何在大规模CPU+GPU的异构系统上根据不同需求选择实现性能更优的FFT算法。     

一种在多核嵌入式平台上实现FFT的快速并行算法

快速傅利叶变换（fast Fourier transform,FFT）算法是对实时数字信号进行快速分析处理的一个基本方法。针对多核嵌入式实时环境下并行FFT算法进行了研究,以有效提高实时信号处理的速度。提出了一种新的静态多项式FFT算法,充分利用静态多项式奇偶项的不同特点直接代入数据计算,免去了层层迭代的计算过程,减少了运算过程中的通信提高并行性能。对该算法思想本文在理论进行了严密论证,通过嵌入式实时平台上运行测试和仿真实验,证实了在数据分段较短的约束条件下,该多项式静态算法较经典的FFT并行算法在时间复杂度上有一定优势。本文结论:多项式静态FFT算法能够有效提高并行FFT运行速度。