Interpolation using the fast Fourier transform

The fast Fourier transform (FFT) algorithm has had widespread influence in many areas of computation since its "rediscovery" by Cooley and Tukey [1]. An efficient and accurate method for interpolation of functions based on the FFT is presented. As an application, the generation of the characteristic polynomial in the "generalized eigenvalue problem" [2] is considered.     

Speech spectrograms using the fast Fourier transform

An important aid in the analysis and display of speech is the sound spectrogram, which represents a time-frequency?intensity display of the short-time spectrum.1-3 With many modern speech facilities centering around small or medium-size computers, it is often useful to generate spectrograms digitally, online. The fast Fourier transform algorithm provides a mechanism for implementing this efficiently.     

Integer fast Fourier transform

A concept of integer fast Fourier transform (IntFFT) for approximating the discrete Fourier transform is introduced. Unlike the fixed-point fast Fourier transform (FxpFFT), the new transform has the properties that it is an integer-to-integer mapping, is power adaptable and is reversible. The lifting scheme is used to approximate complex multiplications appearing in the FFT lattice structures where the dynamic range of the lifting coefficients can be controlled by proper choices of lifting factorizations. Split-radix FFT is used to illustrate the approach for the case of 2^N-point FFT, in which case, an upper bound of the minimal dynamic range of the internal nodes, which is required by the reversibility of the transform, is presented and confirmed by a simulation. The transform can be implemented by using only bit shifts and additions but no multiplication. A method for minimizing the number of additions required is presented. While preserving the reversibility, the IntFFT is shown experimentally to yield the same accuracy as the FxpFFT when their coefficients are quantized to a certain number of bits. Complexity of the IntFFT is shown to be much lower than that of the FxpFFT in terms of the numbers of additions and shifts. Finally, they are applied to noise reduction applications, where the IntFFT provides significantly improvement over the FxpFFT at low power and maintains similar results at high power     

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.     

Numerical calculations of the potential due to an arbitrary charge density using the fast Fourier transform

The Green's function method of finding the voltage due to an arbitrary charge density is related to a convolution integral for simple geometries. The fast Fourier transform (FFT) algorithm is used to calculate the voltages on the grid points and it is argued that significant reduction of computer time is achieved for a large number of grid points.     

板条激光器用光腔的模式计算:快速傅里叶变换法

本文使用快速傅里叶变换法对三维光腔衍射积分方程作了数值解,用以说明板条固体激光器用新型棱镜腔的模式特性.     

Conjugate pair fast Fourier transform

A new algorithm for the fast computation of the discrete Fourier transform is introduced. The algorithm, called the conjugate pair FFT (CPFFT), is used to compute a length-2/sup n/ DFT. The number of multiplications and additions required by the CPFFT is less than that required by the SRFFT algorithm.<>     

A bus-oriented multiprocessor fast Fourier transform

A bus-oriented multiprocessor architecture specialized for computation of the discrete Fourier transform (DFT) of a length N =2^M sequential data stream is developed. The architecture distributes computation and memory requirements evenly among the processors and allows flexibility in the number of processors and in the choice of a fast Fourier transform (FFT) algorithm. With three buses, the bus bandwidth equals the input data rate. A single time-multiplexed bus with a bandwidth of three times the input data rate can alternatively be used. The architecture requires processors that have identical hardware, which makes it more attractive than the cascade (pipeline) FFT for multiprocessor implementation     

ADC testing using interpolated fast Fourier transform (IFFT) technique

An ideal transfer characteristic of an analogue-to-digital converter (ADC) is simulated and an arbitrary nonlinearity error is introduced. A full-scale sine wave is also simulated and applied to ADC input. The interpolated fast Fourier transform (IFFT) technique is used to determine accurately fundamental and other harmonics in the output spectrum of the ADC. The signal-to-noise ratio and the effective number of bits (ENOB) are computed on the basis of FFT and IFFT for different resolutions of ADC and test conditions. The effects of rectangular and Hanning time window functions on the determination of frequency components are reported. The proposed method of dynamic testing of the ADC is useful for users as well as manufacturers.     

What is the fast Fourier transform?

The fast Fourier transform is a computational tool which facilitates signal analysis such as power spectrum analysis and filter simulation by means of digital computers. It is a method for efficiently computing the discrete Fourier transform of a series of data samples (referred to as a time series). In this paper, the discrete Fourier transform of a time series is defined, some of its properties are discussed, the associated fast method (fast Fourier transform) for computing this transform is derived, and some of the computational aspects of the method are presented. Examples are included to demonstrate the concepts involved.     

Historical notes on the fast Fourier transform

The fast Fourier transform algorithm has a long and interesting history that has only recently been appreciated. In this paper, the contributions of many investigators are described and placed in historical perspective.     

Pseudonoise test signals and the fast Fourier transform

Recent published work has indicated a growing interest in the combined use of periodic pseudonoise (p.n.) test signals and the fast Fourier transform (f.f.t.). However, it has been noted by Barker and Davy that the period of pseudonoise sequences are such that it is not possible to use the most efficient form of the f.f.t. This letter points out ways round the problem by drawing attention to a previously published result in this area. In addition, a little known algorithm that directly exploits the f.f.t. to generate pseudonoise is given.     

A guided tour of the fast Fourier transform

For some time the Fourier transform has served as a bridge between the time domain and the frequency domain. It is now possible to go back and forth between waveform and spectrum with enough speed and economy to create a whole new range of applications for this classic mathematical device. This article is intended as a primer on the fast Fourier transform, which has revolutionized the digital processing of waveforms. The reader's attention is especially directed to the IEEE Transactions on Audio and Electroacoustics for June 1969, a special issue devoted to the fast Fourier transform.     

Solution to some electromagnetic problems using fast Fourier transform with conjugate gradient method

Using the fast Fourier transform (FFT) to compute the convolution integrals that appear in the conjugate-gradient method (CGM), an efficient numerical procedure to solve electromagnetic problems is obtained. In comparison with the method of moments (MM), the proposed FFT-CGM avoids the storage of large matrices and reduces the computer time by orders of magnitude.     

A fast Gaussian method for Fourier transform evaluation

A Gaussian method for fast evaluation of approximations to Fourier integral transforms is presented. This method is faster than the FFT for transforms of functions that require considerable computer time to compute. It is especially useful when transforms of high accuracy are needed.     

Generation of Dolph-Chebyshev weights via a fast Fourier transform

Dolph-Chebyshev weights, which realize a minimum side-lobe level for a specified main-lobe width, can be generated by a single fast Fourier transform (FFT). For an even number of elements 2H, the size of the FFT is H. This result has utility for spectral analysis as well as for array processing.     

A sparse data fast Fourier transform (SDFFT)

A multilevel algorithm that efficiently Fourier transforms sparse spatial data to sparse spectral data with controllable error is presented. The algorithm termed "sparse data fast Fourier transform" (SDFFT) is particularly useful for signal processing applications where only part of the k-space is to be computed - regardless of whether it is a regular region like an angular section of the Ewald sphere or it consists of completely arbitrary points scattered in the k-space. In addition, like the various nonuniform fast Fourier transforms, the O(NlogN) algorithm can deal with a sparse, nonuniform spatial domain. In this paper, the parabolic reflector antenna problem is studied as an example to demonstrate its use in the computation of far-field patterns due to arbitrary aperture antennas and antenna arrays. The algorithm is also promising for various applications such as backprojection tomography, diffraction tomography, and synthetic aperture radar imaging.     

Precise expression relating the Fourier transform of a continuoussignal to the fast Fourier transform of signal samples

The fast Fourier transform (FFT) signature of a finite duration, constant frequency, time signal displays sidebands which are a sampling artifact. An analytical expression is derived which precisely predicts artifact behavior. Using this expression, a precise spectral estimate (PSE) is derived. It is demonstrated that this method outperforms the FFT with and without Hamming weighting both in estimating the magnitudes and phases of the spectral components of a time series. Furthermore, PSE is capable of resolving frequency to a fraction of an FFT frequency resolution cell