A two-dimensional FFT algorithm for three-phase inverter-fedsystems

A spectrum analyzer for three-phase inverter-fed balanced systems which is capable of calculating up to 24 harmonic components of the line currents every 130 μs is presented. The method is based on a synchronized sampling technique and on a highly efficient fast Fourier transform (FFT) for three-phase systems. The latter consists of a two-dimensional six-point discrete Fourier transform (DFT) followed by a two-dimensional four-point DFT. The total FFT algorithm has been successfully implemented on a TMS32010 digital signal processor     

Autocorrelation analysis of speech signals using Fermat numbertransform (FNT)

A method for speedy computation of the autocorrelation coefficients used by linear predictive coding (LPC) that uses Fermat number transform (FNT) is described. It is found that there exists a fast computational algorithm for FNT which has a computational structure similar to the fast Fourier transform (FFT). Since the fast Fermat number transform (FFNT) and FFT have similar computational structures, readily available FFT VLSI hardware structures may be adopted for real-time implementation of the FFNT. A verification of the FFNT on an MC 68000 single-board computer has been performed with quite satisfactory results     

共轭对称数据的DFT及其FFT算法

该文对共轭对称复数序列的离散傅里叶交换(DFT)及其快速傅里叶变换(FFT)算法进行了研究,获得共轭对称序列的DFT具有虚部为零的性质,并开发出适用于共轭对称数据的FFT算法。该算法与传统FFT算法相比减少了一半的计算量和存储单元,运算速度提高了一倍。     

Sparse fast Fourier transform for exactly sparse signals and signals with additive Gaussian noise

In recent years, the Fourier domain representation of sparse signals has been very attractive. Sparse fast Fourier transform (or sparse FFT) is a new technique which computes the Fourier transform in a compressed way, using only a subset of the input data. Sparse FFT computes the desired transform in sublinear time, which means in an amount of time that is smaller than the size of data. In big data problems and medical imaging to reduce the time that patient spends in MRI machine, FFT algorithm is not ‘fast’ enough anymore; therefore, the concept of sparse FFT is very important. Similar to compressed sensing, sparse FFT algorithm computes just the important components in the frequency domain in sublinear time. In this work, sparse FFT algorithm is studied and implemented on MATLAB and its performance is compared with Ann Arbor FFT. A filter is used to hash the frequencies in the n dimensional frequency-sparse signal into B bins, where \(B=n/16\). The filter is used for analyzing an important fraction of the whole signal, and therefore, instead of computing n point FFT, B point FFT is computed, and this results in a faster Fourier transform. The probability of success of the implemented algorithm is investigated for noiseless and noisy signals. It is deduced that as the sparsity increases, the probability of perfect transform also increases. If the performances of the algorithm in both cases are compared, it is clearly seen that the performances degrade when there is noise. Therefore, it can be concluded that the algorithm should be improved especially for noisy considerations. The solvability boundary for a constant probability of error is deducted and added to give insight for future studies.     

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

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

A comparison between Walsh and Fourier analysis of the electroencephalogram for tracking the effects of anesthesia

The effects that anesthesia has on the surgical patient can be characterized with the electroencephalogram (EEG). These effects are typically quantified through frequency analysis of the EEG signal. The fast Fourier transform (FFT) is usually employed for this purpose. In recent years, the fast Walsh transform (FWT) has been proposed as an alternative to the FFT for signal analysis because it is computationally more efficient, requiring less time to complete on a digital computer. This paper statistically evaluates the quantitative and dynamic differences between the results of Walsh and Fourier analysis of the EEG done for the purpose of characterizing the effects of anesthesia. This paper shows that there are quantitative differences between the results of the two frequency analysis techniques but they are dynamically equivalent, both showing essentially the same changes due to the effects of anesthesia. The efficiency of the FWT has been reconfirmed. These results support the use of the FWT in place of the FFT for tracking the effects of anesthesia on surgical patients with the EEG.     

A low-power, high-performance, 1024-point FFT processor

This paper presents an energy-efficient, single-chip, 1024-point fast Fourier transform (FFT) processor. The 460000-transistor design has been fabricated in a standard 0.7 μm (L_poly=0.6 μm) CMOS process and is fully functional on first-pass silicon. At a supply voltage of 1.1 V, it calculates a 1024-point complex FFT in 330 μs while consuming 9.5 mW, resulting in an adjusted energy efficiency more than 16 times greater than the previously most efficient known FFT processor. At 3.3 V, it operates at 173 MHz-which is a clock rate 2.6 times greater than the previously fastest rate     

FPGA Implementation of FFT Algorithm for OFDM Based IEEE 802.16d （Fixed WiMAX） Communications

The IEEE 802.16d communication standard uses orthogonal frequency division multiplexing （OFDM）. In the widely used OFDM systems, the fast Fourier transform （FFT） and inverse fast Fourier transform pairs are used to modulate and demodulate the data constellation on the sub-carriers. In this paper, a high level implementation of a high performance FFT for OFDM modulator and demodulator is presented. The design has been coded in Verilog and targeted into Xilinx Spartan3 field programmable gate arrays. Radix-22 algorithm is proposed and used for the OFDM communication system. The design of the FFT is implemented and applied to fixed WiMAX--IEEE 802.16d communi- cation standard. The results are tabulated and the hardware parameters are compared. The proposed architecture is least in number of multipliers used and the memory size, and second to the least in number of adders used.     

快速傅里叶变换对信号频谱的简单分析

快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法,广泛运用于故障诊断领域,因每种故障的频率成分不同,FFT可以根据这些独有的频率成分检测出不同的故障来。同时快速傅里叶变换还应用于控制工程、图像处理、机床生产、数据采集和雷达探测等方面,对社会中的工业发展起到很大的作用。本文就FFT对信号的频谱做出简单分析,对不同采样点数进行相应频谱判断,找出理论与频率图像出现误差的原因,以便人们对FFT技术能够进行更好的使用。     

由FFT芯片构成的并行FFT结构

快速傅立叶变换（ＦＦＴ）在计算机层析影象技术,语间识别,图像处理等域得了广泛的应用。随着计算机应用的发展,越来越需要对大规模的数据进行变换。并行ＦＦＴ是完成快速数据变换的一种方法。本文提出一咱由小规模ＦＦＴ芯片构成并行ＦＦＴ的方法,楞用于大规模数据的变换,并对其并行结构的面积和执行时间进行了探讨,还提出了具有容错功能的并行ＦＦＴ网络。     

A fast algorithm for the linear canonical transform

In recent years there has been a renewed interest in finding fast algorithms to compute accurately the linear canonical transform (LCT) of a given function. This is driven by the large number of applications of the LCT in optics and signal processing. The well-known integral transforms: Fourier, fractional Fourier, bilateral Laplace and Fresnel transforms are special cases of the LCT. In this paper we obtain an O(NlogN) algorithm to compute the LCT by using a chirp-FFT-chirp transformation yielded by a convergent quadrature formula for the fractional Fourier transform. This formula gives a unitary discrete LCT in closed form. In the case of the fractional Fourier transform the algorithm computes this transform for arbitrary complex values inside the unitary circle and not only at the boundary. This chirp-FFT-chirp transform approximates the ordinary Fourier transform more precisely than just the FFT, since it comes from a convergent procedure for non-periodic functions.     

DFT与FFT在宽带数字接收机中的应用

介绍了DFT和FFT在数字信道化接收机中的应用，对ALTERA公司提供的FFT核进行了性能测试，分析了在宽带数字接收机中DFT相比于FFT可能具有的优越性，提出了对数据进行重叠处理的补零滑动算法，该算法有助于构造实时处理的数字信道化接收机。     

COBRA: a 100-MOPS single-chip programmable and expandable FFT

This paper presents an optimized column fast Fourier transform (FFT) architecture, which utilizes bit-serial arithmetic and dynamic reconfiguration to achieve a complete overlap between computation and communication. As a result, for a clock rate of 40 MHz, the system can compute a 24-b precision 1K point complex FFT transform in 9.2 μs, far surpassing the performance of any existing FFT systems     

The fast Fourier transform

The fast Fourier transform (FFT), a computer algorithm that computes the discrete Fourier transform much faster than other algorithms, is explained. Examples and detailed procedures are provided to assist the reader in learning how to use the algorithm. The savings in computer time can be huge; for example, an N = 210-point transform can be computed with the FFT 100 times faster than with the use of a direct approach.     

Recursive pruning of the 2D DFT with 3D signal processingapplications

A recursively pruned radix-(2×2) two-dimensional (2D) fast Fourier transform (FFT) algorithm is proposed to reduce the number of operations involved in the calculation of the 2D discrete Fourier transform (DFT). It is able to compute input and output data points having multiple and possibly irregularly shaped (nonsquare) regions of support. The computational performance of the recursively pruned radix-(2×2) 2D FFT algorithm is compared with that of pruning algorithms based on the one-dimensional (1D) FFT. The former is shown to yield significant computational savings when employed in the combined 2D DFT/1D linear difference equation filter method to enhance three-dimensional spatially planar image sequences, and when employed in the MixeD moving object detection and trajectory estimation algorithm     

FPGA implementation of high-performance,resource-efficient Radix-16 CORDIC rotator based FFT algorithm

The fast Fourier transform (FFT) is an algorithm widely used to compute the discrete Fourier transform (DFT) in real-time digital signal processing. High-performance with fewer resources is highly desirable for any real-time application. Our proposed work presents the implementation of the radix-2 decimation-in-frequency (R2DIF) FFT algorithm based on the modified feed-forward double-path delay commutator (DDC) architecture on FPGA device. Need for a complex multiplier to carry out the multiplication of complex twiddle factors and large memory to store the twiddle factors are the main concerns for FFT implementation. Propose work aims to address these issues. In this work, a high-performance radix-16 COordinate Rotational DIgital Computer (CORDIC) algorithm based rotator is proposed to carry out the complex twiddle factor multiplication. Further, CORDIC needs only rotational angles to carry out complex multiplication, which reduces the need for large memory to store the twiddle factors. To compute the total rotation for n-bit precision, our proposed radix-16 CORDIC algorithm takes n/4 iteration as compared to n iteration of the radix-2 CORDIC algorithm. Our proposed architecture of the radix-2 decimation-in-frequency (R2DIF) algorithm is implemented on a Virtex−7 series FPGA. Further, the detailed comparison is presented between our proposed FFT implementation and other recently proposed FFT implementations. Experimental results suggest that proposed implementation has less latency and hardware utilization as compared to recently proposed implementations.     

Optimized Least-Square Nonuniform Fast Fourier Transform

The main focus of this paper is to derive a memory efficient approximation to the nonuniform Fourier transform of a support limited sequence. We show that the standard nonuniform fast Fourier transform (NUFFT) scheme is a shift invariant approximation of the exact Fourier transform. Based on the theory of shift-invariant representations, we derive an exact expression for the worst-case mean square approximation error. Using this metric, we evaluate the optimal scale-factors and the interpolator that provides the least approximation error. We also derive the upper-bound for the error component due to the lookup table based evaluation of the interpolator; we use this metric to ensure that this component is not the dominant one. Theoretical and experimental comparisons with standard NUFFT schemes clearly demonstrate the significant improvement in accuracy over conventional schemes, especially when the size of the uniform fast Fourier transform (FFT) is small. Since the memory requirement of the algorithm is dependent on the size of the uniform FFT, the proposed developments can lead to iterative signal reconstruction algorithms with significantly lower memory demands.      

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

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

A method to perform a fast fourier transform with primitive image transformations.

The Fourier transform is one of the most important transformations in image processing. A major component of this influence comes from the ability to implement it efficiently on a digital computer. This paper describes a new methodology to perform a fast Fourier transform (FFT). This methodology emerges from considerations of the natural physical constraints imposed by image capture devices (camera/eye). The novel aspects of the specific FFT method described include: 1) a bit-wise reversal re-grouping operation of the conventional FFT is replaced by the use of lossless image rotation and scaling and 2) the usual arithmetic operations of complex multiplication are replaced with integer addition. The significance of the FFT presented in this paper is introduced by extending a discrete and finite image algebra, named Spiral Honeycomb Image Algebra (SHIA), to a continuous version, named SHIAC.     

Closed-form discrete fractional and affine Fourier transforms

The discrete fractional Fourier transform (DFRFT) is the generalization of discrete Fourier transform. Many types of DFRFT have been derived and are useful for signal processing applications. We introduce a new type of DFRFT, which are unitary, reversible, and flexible; in addition, the closed-form analytic expression can be obtained. It works in performance similar to the continuous fractional Fourier transform (FRFT) and can be efficiently calculated by the FFT. Since the continuous FRFT can be generalized into the continuous affine Fourier transform (AFT) (the so-called canonical transform), we also extend the DFRFT into the discrete affine Fourier transform (DAFT). We derive two types of the DFRFT and DAFT. Type 1 is similar to the continuous FRFT and AFT and can be used for computing the continuous FRFT and AFT. Type 2 is the improved form of type 1 and can be used for other applications of digital signal processing. Meanwhile, many important properties continuous FRFT and AFT are kept in the closed-form DFRFT and DAFT, and some applications, such as filter design and pattern recognition, are also discussed. The closed-form DFRFT we introduce has the lowest complexity among all current DFRFTs that is still similar to the continuous FRFT