基于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的一种MIMD并行算法

1.引言 傅里叶变换是分析和处理信息的一种有效数学工具,应用范围十分广泛,1965年Cooley-Turkey提出快速傅里叶交换(FFT)算法,若把一次复数乘法和一次复数加法定义为一次单元运算,其计算量简记为1,使用FFT算法,当离散采样点数N=2~m(m     

计算二维FFT的MIMD并行算法

1.引言 Mueller提出一种计算信号阵列S(N,N)(设N=2~M)二维FFT的并行算法,它要用N~2/2个处理单元和2N个M立方体网,资源开销巨大,结构复杂,难以实现。而本文提出的两种计算信号阵列S(N,N)二维FFT的并行算法,一种叫宏流水线MIMD并     

FFT的DSP汇编算法的改进

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

基于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特性的低复杂度峰均比降低算法

部分传输序列(PTS)方法是OFDM系统中降低PAPR的一种高效技术,但计算复杂度高。提出一种基于FFT特性的多相循环移位和共轭(PCSC)法,该方法先由一个IFFT运算产生一个时域序列,然后结合FFT的时域循环移位性和共轭性构造出不同的转换,在时域产生更多的备选序列。为进一步降低计算复杂度,PCSC法充分利用天线Tx1而在天线Tx2中未使用IFFT运算。仿真结果表明,在子块数量和相位加权系数相同时,本文所提出的PCSC方法相对于PTS方法具有更加良好的PAPR降低性能。     

长为PL的快速递归付里叶变换算法

一、引言离散付里叶变换(DFT)的实际应用愈来愈广泛,但直接计算DFT需要正比于N~2的运算次数。显然当N很大时,直接计算DFT要花费大量的计算时间.一九六五年,Cooley和Tukey提出的快速付里叶变换(FFT)使计算DFT的运算次数正比于N logN,从而使运     

GFT及离散卷积的并行算法及其实现

一、GFT的计算 GFT是离散富里叶变换DFT的一种推广.它在许多方面有实际应用,其定义为: 设a,b为二个实数,x_n(n=0,1,…,N—1)为一实序列,称 X_k=sum from n=0 to N-1 x_nW_N~((n+a)(k+b)),k=0,1…,N-1,为具有时间参数a及频率参数b的广义DFT.简记为GFT(a,b),其中W_N=e~(-i2π/N)。可以证明其逆变换为     

多核计算机上的快速傅里叶变换并行算法

针对现有多核结构上快速傅里叶变换(FFT)并行算法没有利用多级缓存和线程级并行等多核特性问题,通过运用多核多级存储特性合理划分数据,采取子序列FFT计算和多线程并行逐对计算FFT相结合的方法,给出一个N点、一维、有序和基数为2的多核多线程并行计算FFT非递归算法。理论分析和实验结果表明,该算法实用、高效,能获得较好的加速比和可扩展性。     

复形态联想记忆及其性能分析

在Ritter的实域形态联想记忆(real morphological associative memory,简称RMAM)模型的基础上,通过在复数域中序关系的引入构成复数格和环,导出了在复数域上与RMAM相一致的联想规则,构建了一类复域MAM(complex MAM,简称CMAM),从而将RMAM从实域推广至复域,使其可直接处理复信号(如经FFT(fast Fourier Transformation)变换所得数据).证明了该模型的收敛性,分析了其纠错能力和存储能力,并获得了与RMAM相一致的一系列定理和性质.此外,还比较了复形态网络和其他网络(如Hopfield神经网络)的异同.计算机仿真结果表明了CMAM的可行性.     

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

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

利用对称性加速实序列FFT的方法及其FPGA实现*

针对工程实践中傅里叶变换的输入序列一般为实序列的情况,充分利用FFT（快速傅里叶变换）奇偶虚实的对称性质,提出了一种实序列FFT的加速算法。将2N点的实序列DFT转换为N点的复序列DFT,并行计算使运算量明显减少;并给出了基于FPGA的硬件实现方法。     

利用CORDIC算法在FPGA中实现可参数化的FFT

针对在工业中越来越多的使用到的FFT,本文设计出了一种利用CORDIC算法在FPGA上实现快速FFT的方法。CORDIC实现复数乘法比普通的计算器有结构上的优势,并且采用了循环结构的CORDIC算法大大节约了硬件资源。在FFT的结构上采用了2个16点FFT的计算模块来实现蝶形计算。通过地址控制器和RAM的配合,可以完成8点至2048点的虚部实部均为16位的FFT计算。     

基于FPGA的通用FFT处理器的设计

介绍了一种通用的可以在低端或是高端的FPGA上实现N（N=2M,M=2,3,4…）点FFT变换的方法。设计采用基4布斯编码算法和华莱士树算法设计完成了16X16位有符号数并行乘法器,并采用此并行乘法器为核心设计了FFT算法中的基-2蝶形运算单元,设计了串并转化模块、并串转换模块、移位选择模块、溢出检测模块和地址与控制模块等其它模块,并以这些模块和FPGA内部的双口RAM和ROM为基础组成了基-2FFT算法模块。整个模块采用基-2时域抽取,顺序输入,逆序输出的方法;利用Modelsim完成了FFT模块的前后仿真;利用Matlab编写了用于比较仿真结果和Matlab中FFT函数产生的结果的程序,从而验证了仿真结果的正确性。该模块最后能够在Cyclone EP1C6Q240C8型FPGA上稳定运行在60MHz。整个FFT模块能够在183μs左右完成1024点的16位定点复数FFT运算,能够满足一般工程的要求。该方法也可以用于实现更低点数或是更高点数的FFT运算。     

基于TBB的谐波分析多核并行化研究

电能质量谐波分析中通常使用快速傅立叶变换算法(FFT),但在大数据量时其循环体执行效率低,实时性不高。针对上述问题,提出在多核处理器上采用TBB(Intel线程构建模块)并行实现复序列FFT的思路,提高谐波分析的速度,增强实时性。此外,与其他并行库改造程序的实验对比结果表明,TBB可以以更简单的手段,实现更高效的程序并行。     

实序列FFT算法的存储单元图解析方法

为了正确有效地开发实序列FFT的汇编语言程序,提出了以存储单元图的方式解析实序列FFT算法的方法。首先推导了由复序列FFT的实虚部计算实序列FFT的实虚部的公式,指出了计算复序列FFT所包括的级别、蝶组、蝶形三层循环,所涉及的正弦量的计算与存储方式,以及复序列FFT转化为实序列FFT的步骤等。在此基础上利用存储单元图在TMS320C54X汇编语言环境下详细解析了实序列FFT的实虚部计算公式。设计了复序列FFT的实虚部计算的第一级、第二级、第三级到最后级的存储单元图,由复序列FFT的实虚部计算其共轭对称与反对称部分的实虚部的存储单元图,以及由此计算实序列FFT的存储单元图。CCS3.3环境下的仿真结果验证了该解析方法的正确性。     

利用微处理机测试信道误码率

<正> 目前微处理机在数字通信方面的应用已很广泛.笔者将Z-80CPU用于某机的控制、检测上,取得了较好的效果.现将检测信道误码(比特)率部分介绍如下.测试信道的误码率采用(2~(15)-1)位m序列码,其特征多项武为1+X~(11)+x~(15).当发送端发送出这一m序列码时,在接收端将本地m序列产生器产生的同一m序列码(以下简称本地码)与接收到的m序列信码(以下简称信码)进行序列同步,然后检测出差错比特数.测试误码率的原理与随动式误码测试仪相似.当本地码与信码未同步时(本文中均指序列同步),将收到的信码"注入"本地码产生器15比特,让其重新启动,直至两者同步为止.可以近似认为,一次同步的概率约为(1-Pe)~(15),其中Pe为信道的误码率.当两者同步后,将本地码与信码逐比特比较,检测出差错比特数.由上可见,要测试误码率必须要解决以下问题:     

基于二维FFT的图像滤波方法及实现

二维快速傅立叶变换(FFT)在一个传统概念的处理机上实现时,需要芯片具有更多的逻辑资源。本文给出了基于FPGA的自定义处理机(CCM)的二维FFT算法和实现。在CCM的Splash-2平台上实现了二维FFT,计算速度达到180Mflops,最快速度超过Sparc-10工作站的23倍。同时,对于一个N×N图像,这种实现方法可以满足二维FFT所需要的O(N2log2N)次的浮点算术运算。     

基于软硬件的协同支持在众核上对1-DFFT算法的优化研究

随着高性能计算需求的日益增加,片上众核(many-core)处理器成为未来处理器架构的发展方向.快速傅立叶变换(FFT)作为高性能计算中的重要应用,对计算能力和通信带宽都有较高的要求.因此基于众核处理器平台,实现高效、可扩展的FFT算法是算法和体系结构设计者共同面临的挑战.文中在众核处理器Godson-T平台上对1-D FFT算法进行了优化和评估,在节省几乎三分之一L2 Cache存储开销的情况下,通过隐藏矩阵转置,计算与通信重叠等优化策略,使得优化后的1-D FFT算法达到3倍以上的性能提升.并通过片上网络拥塞状况的实验分析,发现对于像FFT这样访存带宽受限的应用,增加L2 Cache的访问带宽,可以缓解因为爆发式读写带给片上网络和L2 Cache的压力,进一步提高程序的性能和扩展性.     

有效的STBC-OFDM系统信道估计方法

提出了一种新的空时分组编码(STBC)-正交频分复用(OFDM)系统的信道估计方法.该方法通过插入经过空时编码的训练序列,在时域里进行信道估计.通过分析,表明了自相关具有零相关区(ZCZ)的序列是最小平方(LS)意义下的最优训练序列.该方法解决了文献中提到的复数多相训练序列硬件实现复杂度高且对序列长度有限制的缺点.由于无需对接收到的训练序列进行离散傅立叶变换(DFT),且不涉及矩阵求逆,所以计算复杂度低.仿真实验结果表明了该方法的有效性.