WFTA算法的FPGA设计与实现

Winograd傅里叶变换算法（WFTA）利用旋转因子W的特性对其进行分解,能够把FFT运算中乘法次数降到最低,是一种高效且资源占用相对较少的FFT实现方法。以256点分解为两维16×16点的小数组WFTA进行运算为例介绍了大数组WFTA算法的FPGA设计与实现方案。仿真测试表明,所设计的256点FFT处理器,乘法器资源消耗仅为基-2FFT的1/2、基-4FFT的2/3,且在100 MHz主时钟频率下完成运算仅需5.8μs,满足FFT处理器的高速实时性要求。     

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

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

无存储访问冲突的基2×K并行FFT架构

提出了一种无存储访问冲突的基2×K并行FFT架构.该架构通过并行地址产生算法,使K个基2蝶形运算单元同时读取或写入所需的2 K个操作数,达到平均每周期完成K个基2蝶式运算的处理能力.与已有的并行FFT架构相比,新架构地址产生电路简单,并且对于不同的K值,并行地址产生模块结构相同.在资源消耗方面,不考虑旋转因子,N点FFT处理器只需要3 N/2个存储单元.     

可变长数据全并行FFT地址生成方法

本文通过对混合基4/2 FFT算法的分析,在优化采样数据、旋转因子存储及读取方法的基础上,提出了将N=2m点,m为奇、偶两种情况的地址产生统一于同一函数的算法,并设计了简单的插入值产生及快速插入位置控制电路,从而用一个计数器、同一套地址产生硬件,通过简单的开关模式控制,可实现任意长度FFT变换的地址产生单元,该地址产生单元在一个时钟周期内产生读取所需旋转因子及并行访存4个操作数的地址.本文设计的FFT处理器每周期完成一个基4或2个基2蝶式运算,在吞吐率高、资源少的基础上实现了处理长度可编程的灵活性,同时避免了旋转因子重复读取,降低功耗.     

流水线结构FFT/IFFT处理器的设计与实现

针对实时高速信号处理的要求，设计并实现了一种高效的FFT处理器。在分析了FFT算法的复杂度和硬件实现结构的基础上，处理器采用了按频率抽取的基—4算法，分级流水线以及定点运算结构。可以根据要求设置成4P点的FFT或IFFT。处理器可以对多个输入序列进行连续的FFT运算，消除了数据的输入输出对延时的影响。平均每完成一次N点FFT运算仅需要Ⅳ个时钟周期。整个设计基于Verilog HDL语言进行模块化设计。并在Altera公司的Cyclone Ⅱ器件上实现。     

高速3780点FFT处理器的设计与实现

介绍了地面数字电视多媒体广播传输系统(DTMB)中3 780点FFT处理器的设计与实现。通过综合利用混合基算法、素因子算法和WFTA算法,来完成3 780点FFT的算法设计。采用流水线结构进行硬件实现,为进一步提高系统吞吐率,其内部3,4,5,7,9点WFTA运算单元均采用并行数据处理方式。     

基于FPGA的64点FFT处理器设计

采取基-4按频率抽取FFT算法,设计一种可在FPGA上实现的64点、32位长、定点复数FFT处理器.基-4堞形运算单元中采用六级流水线设计,并行处理4路输入/输出数据,能极大地提高FFT的处理速度.该设计采用VHDL描述的多个功能模块,经ModelSim对系统进行逻辑综合与时序仿真.实验证明,利用FPGA实现64点FFT,运算速度快,完全可以处理高速实时信号.     

高基FFT处理器高效地址产生算法

FFT算法是数字信号处理最常用算法,使用FFT处理器是进行FFT运算的重要手段之一。本文针对主基16局部流水的FFT处理器,提出了一种运用于高基FFT处理器的新型地址产生结构,能够进行16~4096点可变长的FFT运算,具有快速灵活的特点,且结构简单,适合FFT处理器中对数据通路控制的实现。     

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

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

OFDM系统中FFT算法的FPGA设计与实现

针对FFT算法在OFDM系统中的应用,对一般的FFT算法进行比较分析,设计了一种便于FPGA硬件实现的基4 FFT算法结构。该实现结构的设计以简化电路结构,节省硬件资源,便于扩展维护为目的,以第一级运算为基础实现多级FFT运算,采用了电路复用技术,以一种新的数据排序方式实现正序输入,正序输出,简化旋转因子的排列,并对一些相关的关键技术进行了设计改进。本设计在ISE10.1平台采用VHDL语言编程实现,并通过了仿真验证。     

A GENERAL IN-PLACE AND IN-ORDER PRIME FACTOR FFT ALGORITHM

Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,     

通用顺序即位素因子FFT算法

本文从一维到多维的下标变换出发,得到了一种通用顺序,即位素因子FFT算法。与现在的素因子FFT算法相比较,这种算法不仅节省了约一半内存,而且有更高的计算效率。此外,这种算法能很方便地将逆变换也包括在同一程序内。     

Computing the inverse DFT with the in-place, in-order prime factorFFT algorithm

We present a method for computing the inverse discrete Fourier transform (IDFT) by the in-place, in-order prime factor FFT algorithm (PFA). This is achieved by modifying the input and the output index mapping equations. This approach does not result in any additional cost in terms of program length and computational time     

An analysis for the realization of an in-place and in-order primefactor algorithm

It is shown that the prime factor algorithm (PFA) has an intrinsic property that allows it to be easily realized in an in-place and in-order form. In contrast to other approaches that use two equations for loading data from and returning the results to the memory, respectively, it is shown formally that in many cases only one equation is enough for both operations. Thus a truly in-place and in-order computation is obtained. Nevertheless, the sequence length of the PFA computation must be carefully selected. The conditions under which a particular sequence length is possible for in-place and in-order PFA computation are analyzed     

高速64点FFT芯片设计技术

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

Balanced Binary-Tree Decomposition for Area-Efficient Pipelined FFT Processing

This paper presents an area-efficient algorithm for the pipelined processing of fast Fourier transform (FFT). The proposed algorithm is to decompose a discrete Fourier transform (DFT) into two balanced sub-DFTs in order to minimize the total number of twiddle factors to be stored into tables. The radix in the proposed decomposition is adaptively changed according to the remaining transform length to make the transform lengths of sub-DFTs resulting from the decomposition as close as possible. An 8192-point pipelined FFT processor designed for digital video broadcasting-terrestrial (DVB-T) systems saves 33% of general multipliers and 23% of the total size of twiddle factor tables compared to a conventional pipelined FFT processor based on the radix-2² algorithm. In addition to the decomposition, several implementation techniques are proposed to reduce area, such as a simple index generator of twiddle factor and add/subtract units combined with the two's complement operation     

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

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

DTMB接收机中3780点FFT处理器的设计

提出了一种适合于DTMB接收机使用的FFT处理器的设计方法.该处理器基于混合基算法,素因子分解法和WFTA算法,采用动态截位法来保证精度与减小功耗和面积.FPGA验证表明：在输入输出均为13位时,该处理器的信噪比达到了60.4dB,运行最高频率达到84.48MHz,满足了DTMB接收机对FFT处理器的精度要求和速度要求.     

快速图像匹配相关系数算法及实现

最大归一互相关图像匹配算法是图像匹配中的常用算法,其关键是解算活动图与基准图间的相关系数。针对相关系数计算量大的特点,分析了FFT的基与FFT处理速度之间的关系以及基16FFT算法特点,提出用基16FFT算法计算相关系数,相关系数的处理时间大幅减小;同时针对高基蝶形单元设计复杂、使用不灵活等特点,提出采用级连思想实现主基16蝶形单元,使处理器的设计复杂度降低。实验证明,将主基16FFT处理器用于相关系数的计算中,使最大归一互相关图像匹配处理速度达到国际领先水平。     

A new radix-2/8 FFT algorithm for length-q/spl times/2/sup m/ DFTs

In this paper, a new radix-2/8 fast Fourier transform (FFT) algorithm is proposed for computing the discrete Fourier transform of an arbitrary length N=q/spl times/2/sup m/, where q is an odd integer. It reduces substantially the operations such as data transfer, address generation, and twiddle factor evaluation or access to the lookup table, which contribute significantly to the execution time of FFT algorithms. It is shown that the arithmetic complexity (multiplications+additions) of the proposed algorithm is, in most cases, the same as that of the existing split-radix FFT algorithm. The basic idea behind the proposed algorithm is the use of a mixture of radix-2 and radix-8 index maps. The algorithm is expressed in a simple matrix form, thereby facilitating an easy implementation of the algorithm, and allowing for an extension to the multidimensional case. For the structural complexity, the important properties of the Cooley-Tukey approach such as the use of the butterfly scheme and in-place computation are preserved by the proposed algorithm.