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

利用近似核与近似取模法改进的Rife算法

为了满足侦察雷达接收机对正弦信号频率实时估计的要求,提出了一种利用近似核和近似取模方法改进的Rife算法.该算法利用4点近似核FFT代替全精度FFT,消除了乘法运算;利用近似取模算法避免了乘法运算和开方运算,整体上使运算量大幅下降.仿真结果显示,该算法保持了全频段高精度测频特性,均方根误差与克拉美罗下界(CRLB)保持...     

基于FPGA的24点离散傅里叶变换结构设计

基于Good—Thomas映射算法和ISE快速傅里叶变换IP核,设计了一种易于FPGA实现的24点离散傅里叶变换,所设计的24点DFF模块采用流水线结构,主要由3个8点FFT模块和1个3点DFT模块级联而成。并且两级运算之间不需要旋转因子,整个DFF模块仅仅需要14个实数乘法器,布局布线后仿真工作时钟频率可达200MHz。首先根据Good—Thomas算法将并行的24路输入信号分成3组,每组8路信号,并进行并／串转换,得到3路串行信号;其次。将3路串行信号分别输入至3个FFrIP核模块进行8点FFT运算;然后,将上述3个FFrIP核模块同一时刻输出的3路信号进行3点DFF变换;最后,将得到的3路并行输出信号分别进行串／并转换,得到24路DFF输出信号。此外,设计的24点DFT结构还具有很好的扩展性,通过修改FFTIP核变换点数参数便可实现长度N=3×2^N点DFT。     

基于FPGA的可配置 FFT IP核实现研究

针对FFT算法基于FPGA实现可配置的IP核。采用基于流水线结构和快速并行算法实现了蝶形运算和4 k点FFT的输入点数、数据位宽、分解基自由配置。使用Verilog 语言编写,利用ModelSim仿真,由ISE综合并下载,在Xilinx公司的Virtex-5 xc5vfx70t器件上以200 MHz 的时钟实现验证,运算结果与其他设计的运算效率对比有一定优势     

无源单通道阵列快速DOA估计算法

针对现有无源单通道阵列DOA估计算法复杂度较高,实时性较差的问题,提出一种适用于单通道阵列的快速DOA估计算法。该算法将常规多通道阵列的空间FFT算法引入单通道阵列信号处理中,将通道切换时间带入FFT运算,构建了新的变换核函数,利用该核函数可直接对单通道阵列的采样信号进行空间FFT变换,基于此提出了适用于单通道阵列的SAA—FFT算法。理论分析与仿真实验证明了该算法的有效性。     

基于FPGA的快速傅里叶变换FFT处理器设计

FFT是DFT的快速算法,广泛应用于语音处理、数字通信、计算机等领域。该设计基于FPGA实现,采用基2时域抽取FFT算法,以倒序输入,顺序输出的方法实现字长为12位的256点FFT变换,将蝶形运算单元设计成为一种只需3个时钟周期就能进行一次蝶形运算的特殊结构,使蝶形运算的时间大大缩减。在系统仿真时以两个正弦波的叠加信号为测试信号,在Modelsim中进行仿真,验证设计的正确性。     

具有蝶型单元的FFT在FPGA上的实现

描述了一种使用FPGA实现FFT处理器的方法,基于按时间抽取(DIT)基-4算法,采用4组RAM并行为蝶型单元提供数据,使用交换器对数据进行重行排序.实验结果表明,该方案保证了运算正确性、运算精度和实现复杂度.提出了两种改进的设计思路及方法,使处理器可以获得更高的处理速度.     

少模光纤通信频域均衡中的大点数FFT设计

为了减小频域均衡系统电路实现的功耗和面积,满足长距离少模光纤通信对均衡器的要求,对关键环节快速傅里叶变换(FFT)电路的实现进行了研究,采用2维分解算法将大点数的FFT运算转换为小点数FFT处理器的设计,降低了硬件复杂度。设计了基于现场可编程门阵列的高速蝶形运算核,实现了16384点FFT的2维R22SDF结构,提高存储器的资源利用率,减少了复数乘法器的使用;进行了理论分析和实验验证,取得了不同时钟频率下的电路结构占用资源的数据。结果表明,FFT运算器的正确性得到验证,该FFT运算器能够适应少模光纤通信系统中优化频域均衡电路结构的要求,能够实现200MHz数据传输速度的频域均衡实时处理。     

基于FPGA的基-6FFT算法的设计与实现

介绍了一种基于FPGA的FFT算法的实现——以Altera公司的FLEX10K系列产品为硬件平台,用VHDL语言和电路图完成系统设计描述,用MAX plusⅡ软件进行编译、综合和下载,实现了6点实序列DFT算法,并给出了仿真测试的结果。在FPGA芯片上运行的FFT算法具有速度快且抗干扰能力强的硬件实现的优点,用VHDL语言实现的基于IP核FFT算法具有很好的可移植性,可以重复使用,大大提高了设计效率。     

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

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

基于立方卷积插值的信号DFT频谱校正算法

由于栅栏效应的存在,会使得基于信号DFT谱峰搜索的测频算法产生很大误差,因此在测频之前一般需对信号的DFT频谱进行校正。推导出用于单正弦信号DFT频谱校正的立方卷积插值核函数、插值函数及形状参数,并依据脉冲雷达信号是无数个正弦信号之和的事实,将其推广至脉冲雷达信号DFT频谱的幅度校正,给出其频谱检测算法。     

Unusual-length number-theoretic transforms using recursiveextensions of Rader's algorithm

A novel decomposition of NTT block-lengths is proposed using repeated applications of Rader's (1968) algorithm to reduce the problem to that of realising a single small-length NTT. An efficient implementation of this small-length NTT is achieved by an initial basis conversion of the data, so that the new basis corresponds to the kernel of the small-length NTT. Multiplication by powers of the kernel become rotations and all arithmetic is efficiently performed within the new basis. More generally, this extension of Rader's algorithm is suitable for NTT or DFT applications where an efficient implementation of a particular small-length NTT/DFT module exists     

基于SC-FDMA系统的噪声估计算法研究

为了提高单载波频分多址接入(SC-FDMA)系统的性能,一种简单且有效的基于探测参考信号(SRS)的噪声估计算法是必要的.针对传统基于离散傅里叶变换(DFT)算法的缺陷,提出了一种改进的基于DFT的算法.另外,在该改进的基于DFT的算法的基础上,又通过增加汉宁窗进行修正,减小了高信噪比下信号能量的泄露.仿真结果表明,在低信噪比下,改进的基于DFT的算法的性能相比传统的算法性能上有4 dB的改善.但是,在高信噪比下,改进的基于DFT的算法的性能逐渐变差,而通过添加汉宁窗却能修正这一缺陷,使其性能得到至少4 dB的改善.     

抽样子空间约束改进大数据谱聚类算法

在分析经典谱聚目标函数与加权核k-means目标函数等价基础上,设计了一种基于抽样子空间约束的改进大规模数据谱聚类算法,算法通过加权核k-means迭代优化避免矩阵特征分解的大量资源被占用,通过数据抽样及聚类中心的子空间约束,避免全部核矩阵都被使用,从而降低经典算法的时间空间复杂度。理论分析和实验结果表明,改进算法保持与经典算法相近聚类精度,提高了聚类效率,验证了改进算法的有效性。     

A three-dimensional DFT algorithm using the fast Hartley transform

A three-dimensional (3-D) Discrete Fourier Transform (DFT) algorithm for real data using the one-dimensional Fast Hartley Transform (FHT) is introduced. It requires the same number of one-dimensional transforms as a direct FFT approach but is simpler and retains the speed advantage that is characteristic of the Hartley approach. The method utilizes a decomposition of the cas function kernel of the Hartley transform to obtain a temporary transform, which is then corrected by some additions to yield the 3-D DFT. A Fortran subroutine is available on request.     

A rapid look-up table method for reconstructing MR images from arbitrary K-space trajectories

Look-up tables (LUTs) are a common method for increasing the speed of many algorithms. Their use can be extended to the reconstruction of nonuniformly sampled k-space data using either a discrete Fourier transform (DFT) algorithm or a convolution-based gridding algorithm. A table for the DFT would be precalculated arrays of weights describing how each data point affects all of image space. A table for a convolution-based gridding operation would be a precalculated table of weights describing how each data point affects a small k-space neighborhood. These LUT methods were implemented in C++ on a modest personal computer system; they allowed a radial k-space acquisition sequence, consisting of 180 views of 256 points each, to be gridded in 36.2 ms, or, in approximately 800 ns/point. By comparison, a similar implementation of the gridding operation, without LUTs, required 45 times longer (1639.2 ms) to grid the same data. This was possible even while using a 4 x 4 Kaiser-Bessel convolution kernel, which is larger than typically used. These table-based computations will allow real time reconstruction in the future and can currently be run concurrently with the acquisition allowing for completely real-time gridding.     

一种基于Kepler架构GPU的通信仿真加速方法

提出了一种在 Kepler 架构 GPU（graphics processing unit,图形处理器）上利用 CUDA（compute unified device architecture,统一计算设备架构）技术加速通信仿真中DFT（discrete Fourier transform,离散傅里叶变换）处理过程的方法。该方法的核心思想是利用线程级并行技术实现单条收发链路内部DFT运算的并行加速,并利用动态并行和Hyper-Q技术实现不同收发用户对之间链路处理过程的并行加速,从而最终达到加速仿真中DFT处理过程的目的。实验结果表明,相对单核单线程CPU程序和上一代Fermi架构GPU程序,该方法分别能够将DFT处理速度提升300倍和3倍,具有较好的加速效果。     

α 稳定分布噪声下基于核方法的非线性信道均衡算法

为了提高α稳定分布噪声下非线性信道均衡器的性能,本文利用核方法处理非线性问题,结合最小平均p范数算法的核心思想,构造了α稳定分布噪声下基于核方法的非线性均衡器,提出并推导了α稳定分布噪声下核最小平均p范数均衡算法。首先,通过核函数将接收信号映射到高维特征空间;然后,在高维特征空间中利用LMP算法对信号进行均衡;最后,将均衡器的输出信号表示为内积形式并利用核函数将其转化到输入空间进行计算。理论分析和仿真实验结果表明,与核最小均方算法和最小平均p范数算法相比,新算法在保证收敛速度的前提下降低了稳态误差,能够更好地对α稳定分布噪声下的非线性信道失真进行补偿。      

分离M维DFT快速算法

本文提出了一种新的多维信号ＤＦＴ快速算法，该算法是将多维ＤＦＴ转变成多组一维奇频率ＤＦＴ进行运算，那么其运算量主要取决于一维奇频率ＦＦＴ算法，同时，这有很强的结构，可实现同址运算，文中例举了二维信号时，它与多项式算法的比较，结果是实数据时，两者相同，复数据时，本文算法比文献在加法运算量方面略优，文中还给出了三维四维的运算量。     

Approximating large convolutions in digital images

Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0-1 valued function. This operation can be quite costly, especially when large kernels are involved. We present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an mxn image and a k-sided convex polygonal kernel K, computes a valid convolution in O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image.