Efficient computation of the DFT with only a subset of input oroutput points

Ways of efficiently computing the discrete Fourier transform (DFT) when the number of input and output data points differ are discussed. The two problems of determining whether the length of the input sequence or the length of the output sequence is reduced can be found to be duals of each other, and the same methods can, to a large extent, be used to solve both. The algorithms utilize the redundancy in the input or output to reduce the number of operations below those of the fast Fourier transform (FFT) algorithms. The usual pruning method is discussed, and an efficient algorithm, called transform decomposition, is introduced. It is based on a mixture of a standard FFT algorithm and the Horner polynomial evaluation scheme equivalent to the one in Goertzel's algorithms. It requires fewer operations and is more flexible than pruning. The algorithm works for power-of-two and prime-factor algorithms, as well as for real-input data     

Multiplicative filtering in the fractional Fourier domain

In this article, we investigate the multiplicative filtering in the fractional Fourier transform (FRFT) domain based on the generalized convolution theorem which states that the convolution of two signals in time domain results in simple multiplication of their FRFTs in the FRFT domain. In order to efficiently implement multiplicative filtering, we express the generalized convolution structure by the conventional convolution operation. Utilizing the generalized convolution structure, we convert the multiplicative filtering in the FRFT domain easily to the time domain. Based on the model of multiplicative filtering in the FRFT domain, a practical method is proposed to achieve the multiplicative filtering through convolution in the time domain. This method can be realized by classical Fast Fourier transform (FFT) and has the same capability compared with the method achieved in the FRFT domain. As convolution can be performed by FFT, this method is more useful from practical engineering perspective.     

Split-Radix Algorithms for Arbitrary Order of Polynomial Time Frequency Transforms

The polynomial time frequency transform is one of important tools for estimating the coefficients of the polynomial-phase signals (PPSs) with the maximum likelihood method. The transform converts a one-dimensional (1-D) data sequence into a multidimensional output array from which the phase coefficients of the data sequence are estimated. A prohibitive computational load is generally needed for high-order polynomial-phase signals although the 1-D fast Fourier transform (FFT) algorithm can be used. Based on the split-radix concept, this paper derives a fast algorithm for arbitrary order of polynomial time frequency transforms to significantly reduce the computational complexity. Comparisons on the computational complexity needed by various algorithms are also made to show the merits of the proposed algorithm     

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

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

基于短时傅立叶变换的跳频序列瞬时频率估计

采用了G函数的方法来模拟跳频序列，然后利用短时傅立叶变换对它进行分析与瞬时频率的估计。该方法能够有效地描绘出跳频信号的频率随时间跳变的规律（跳频图案），具有很高的时间一频率分辨率。计算机仿真验证了应用短时傅立叶变换分析跳频序列的有效性和实用性。     

Symmetric convolution of asymmetric multidimensional sequencesusing discrete trigonometric transforms

This paper uses the fact that the discrete Fourier transform diagonalizes a circulant matrix to provide an alternate derivation of the symmetric convolution-multiplication property for discrete trigonometric transforms. Derived in this manner, the symmetric convolution-multiplication property extends easily to multiple dimensions using the notion of block circulant matrices and generalizes to multidimensional asymmetric sequences. The symmetric convolution of multidimensional asymmetric sequences can then be accomplished by taking the product of the trigonometric transforms of the sequences and then applying an inverse trigonometric transform to the result. An example is given of how this theory can be used for applying a two-dimensional (2-D) finite impulse response (FIR) filter with nonlinear phase which models atmospheric turbulence.     

Fast convolution filter banks for satellite payloads with on-boardprocessing

Filter banks able to demultiplex channels of different sizes are necessary on board the satellite when a single bit-rate channel is assigned to each user. In this paper, the method referred to as the fast convolution filter bank is analyzed for regenerative payloads. The size of the input fast Fourier transform (FFT) depends on the narrowest channel, while the inverse fast Fourier transform (IFFT) number of points is relative to the decimation ratio associated with each channel. In order to reduce the complexity, most of the frequency coefficients are forced to zero, leading to a violation of the overlap-and-save (OS) condition. It is shown that the resulting error can be modeled as a cyclostationary process, and an optimization method based on minimization of the associated mean-square error (MSE) is proposed. Fast convolution is then compared with multistage implementation in terms of flexibility, reconfigurability, and complexity     

Computationally Efficient FIR Filtering of Polynomial Signals in DFT Domain

Fast unbiased finite impulse response (UFIR) filtering of polynomial signals can be provided in the discrete Fourier transform (DFT) domain employing fast Fourier transform (FFT). We show that the computation time can further be reduced by utilizing properties of UFIR filters in the DFT domain. The transforms have been found and investigated in detail for low-degree FIRs most widely used in practice. As a special result, we address an explicit unbiasedness condition uniquely featured to UFIR filters in DFT domain. The noise power gain and estimation error bound have also been discussed. An application is given for state estimation in a crystal clock employing the Global Positioning System based measurement of time errors provided each second. Based upon it, it is shown that filtering in the time domain takes about 1?second, which is unacceptable for real-time applications. The Kalman-like algorithm reduces the computation time by the factor of about 8, the FFT-based algorithm by about 18, and FFT with the UFIR filter DFT properties by about 20.     

Algebraic Signal Processing Theory: Cooley–Tukey Type Algorithms for Real DFTs

In this paper, we systematically derive a large class of fast general-radix algorithms for various types of real discrete Fourier transforms (real DFTs) including the discrete Hartley transform (DHT) based on the algebraic signal processing theory. This means that instead of manipulating the transform definition, we derive algorithms by manipulating the polynomial algebras underlying the transforms using one general method. The same method yields the well-known Cooley-Tukey fast Fourier transform (FFT) as well as general radix discrete cosine and sine transform algorithms. The algebraic approach makes the derivation concise, unifies and classifies many existing algorithms, yields new variants, enables structural optimization, and naturally produces a human-readable structural algorithm representation based on the Kronecker product formalism. We show, for the first time, that the general-radix Cooley-Tukey and the lesser known Bruun algorithms are instances of the same generic algorithm. Further, we show that this generic algorithm can be instantiated for all four types of the real DFT and the DHT.     

The use of finite fields to compute convolutions

A transform is defined in the Galois field ofq^2elementsGF(q^2), a finite field analogous to the field of complex numbers, whenqis a prime such that (--1) is not a quadratic residue. It is shown that the action of this transform overGF(q^2)is equivalent to the discrete Fourier transform of a sequence of complex integers of finite dynamic range. Ifqis a Mersenne prime, one can utilize the fast Fourier transform (FFT) algorithm to yield a fast convolution without the usual roundoff problem of complex numbers.     

基于TMS320F28335的FIR-IFFT数字滤波方法

针对现有数字滤波方法存在大量傅里叶变换以及卷积运算,在工业控制领域处理50 Hz信号时,易造成处理器消耗大量运算时间,导致在低端处理器上无法实现常规数字滤波算法的问题,介绍了一种修改后的数字滤波算法,综合短时采样序列与最优窗函数在TMS320F28335上可快速实现该算法。经过窗函数截取后的信号进行FFT分析,去除谐波频率后IFFT还原波形,与通用的IIR或FIR滤波器相比,大幅缩短了程序运行时间,同时减少通用滤波器的大量卷积运算,提高程序执行效率。     

Convolution,correlation, and sampling theorems for the offset linear canonical transform

The offset linear canonical transform (OLCT), which is a time-shifted and frequency-modulated version of the linear canonical transform, has been shown to be a powerful tool for signal processing and optics. However, some basic results for this transform, such as convolution and correlation theorems, remain unknown. In this paper, based on a new convolution operation, we formulate convolution and correlation theorems for the OLCT. Moreover, we use the convolution theorem to investigate the sampling theorem for the band-limited signal in the OLCT domain. The formulas of uniform sampling and low-pass reconstruction related to the OLCT are obtained. We also discuss the design method of the multiplicative filter in the OLCT domain. Based on the model of the multiplicative filter in the OLCT domain, a practical method to achieve multiplicative filtering through convolution in the time domain is proposed.     

A Computable Fourier Condition Generating Alias-Free Sampling Lattices

We propose a Fourier analytical condition linking alias-free sampling with the Fourier transform of the indicator function defined on the given frequency support. Our discussions center around how to develop practical computation algorithms based on the proposed analytical condition. We address several issues along this line, including the derivation of simple closed-form expressions for the Fourier transforms of the indicator functions defined on arbitrary polygonal and polyhedral domains; a complete and nonredundant enumeration of all quantized sampling lattices via the Hermite normal forms of integer matrices; and a quantitative analysis of the approximation of the original infinite Fourier condition by using finite computations. Combining these results, we propose a computational testing procedure that can efficiently search for the optimal alias-free sampling lattices for a given polygonal or polyhedral shaped frequency domain. Several examples are presented to show the potential of the proposed algorithm in multidimensional filter bank design, as well as in applications involving the design of efficient sampling patterns for multidimensional band-limited signals.     

基于FFT的多周期噪声的滤波-X算法研究

为了弥补已有消噪技术的缺陷及不足,结合实际应用对有源噪声控制技术及针对多周期低频噪声主动控制进行深入的研究,根据快速傅里叶算法(FFT)和凹槽滤波器的工作原理,系统地研究并设计滤波-X算法,进行相关计算机仿真出结果分析;运用快速傅里叶变换(FFT)的方法,将多周期信号从时域变换到频域,从而达到对多周期噪声消噪的目的。     

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.     

Efficient Partitioning of Algorithms for Long Convolutions and their Mapping onto Architectures

We present an efficient approach for the partitioning of algorithms implementing long convolutions. The dependence graph (DG) of a convolution algorithm is locally sequential globally parallel (LSGP) partitioned into smaller, less complex convolution algorithms. The LSGP partitioned DG is mapped onto a signal flow graph (SFG), in which each processor element (PE) performs a small convolution algorithm. The key is then to reduce the complexity of the SFG in two steps: 1. local reduction of complexity: the short Fast Fourier Transform (FFT) is used to perform the small convolution within the PE; and 2. global reduction of complexity: the short FFTs within the PEs are relocated to the global level, where redundant short FFT operations are eliminated. The remaining operation within the PEs is now a simple element-wise multiply-add. After a graph transform, the structure of the SFG kernel is recognized as a set of parallel small convolutions. If we use the short FFT to perform these short convolutions, we come to our final realization of the long convolution algorithm. The computational complexity of this realization is close to the optimum for convolutions, that is, O(N log N). Our approach is thus achieving this N log N –low without having to implement large-size FFTs. We use, instead, small FFT blocks. The advantage is that small FFT transforms are commercially available, and that they can even be implemented in single-chip VLSI architectures. Our final SFG is three dimensional and can be mapped efficiently onto prototype architectures or dedicated VLSI processors. We demonstrate the procedure in the paper by a design example: the implementation of a prototype convolution architecture that we designed for a real-time radar imaging system.     

Generalized Gabor expansions of discrete-time signals in l2(Z) via biorthogonal-like sequences

In this paper, a biorthogonal-like sequences (BLS) theory and its application to the generalized Gabor expansions (equivalently, the generalized short-time Fourier transform/filterbank summation) are presented. A pair of BLS's are defined to be two sequences satisfying a biorthogonal-like condition (BLC), which is a moment equation and equivalent to a linear difference equation. We show that two collections in a Hilbert space generated by a pair of BLS's in the joint time-frequency domain are complete, either can be used as an analysis filter, and the other can be used as a synthesis filter for a generalized Gabor expansion of discrete-time signals. A sufficient and necessary condition on the existence of BLS's based on the moment equation is presented, which is simpler to use than frame theory. Given a filter generating a frame, its BLS's also generate frames. The dual frame is one of them. Given a FIR analysis/synthesis filter, there is a FIR synthesis/analysis filter if BLS's exist. The algorithm to compute FIR analysis and synthesis filters based on the linear difference equation is presented in this paper, which is simpler than frame operator     

Backprojection by upsampled Fourier series expansion andinterpolated FFT

A fast backprojection method through the use of interpolated fast Fourier transform (FFT) is presented. The computerized tomography (CT) reconstruction by the convolution backprojection (CBP) method has produced precise images. However, the backprojection part of the conventional CBP method is not very efficient. The authors propose an alternative approach to interpolating and backprojecting the convolved projections onto the image frame. First, the upsampled Fourier series expansion of the convolved projection is calculated. Then, using a Gaussian function, it is projected by the aliasing-free interpolation of FFT bins onto a rectangular grid in the frequency domain. The total amount of computation in this procedure for a 512x512 image is 1/5 of the conventional backprojection method with linear interpolation. This technique also allows the arbitrary control of the frequency characteristics.     

高动态弱直扩信号的分级捕获算法

针对低信噪比高动态环境下直扩信号经典捕获算法中多普勒频偏估计精度和快速傅里叶变换(FFT)运算量的矛盾,提出了一种基于频偏补偿的两级非相干累加捕获算法。该算法以部分匹配滤波器结合快速傅里叶变换(PMF-FFT)算法为单元,首先利用第一级频偏粗估值对多普勒频偏进行补偿,然后通过调整第二级PMF-FFT中部分匹配滤波器长度并利用滑动平均窗对残余频偏进行精估。理论分析和仿真结果表明,与经典捕获算法相比,该算法在FFT运算点数相同的条件下,可以有效地提高多普勒频偏估计精度,并且在高动态环境下具有更好的检测性能。     

数字再现三维物体菲涅耳计算全息的研究

提出了一种用计算机产生和再现三维物体离轴菲涅尔（Fresnel)全息图的数字方法。采用Born近似法则建立了理想三维的物体模型；利用博奇（Burch)编码方法制作了此三维物体的计算全息图。通过卷积和快速傅立叶变换（FFT）的方法计算衍射积分，以数字聚焦的方法进行再现，通过改变再现距离，获得了三维物体各截面的再现像。直接利用数字滤波技术消除了虚像和零级像，得到了清晰的实像，给出了此三维物体的计算全息图及其不同截面的数字再现结果。