The Partial Fast Fourier Transform

An efficient algorithm for computing the one-dimensional partial fast Fourier transform \(f_j=\sum _{k=0}^{c(j)}e^{2\pi ijk/N} F_k\) is presented. Naive computation of the partial fast Fourier transform requires \({\mathcal O}(N^2)\) arithmetic operations for input data of length N. Unlike the standard fast Fourier transform, the partial fast Fourier transform imposes on the frequency variable k a cutoff function c(j) that depends on the space variable j; this prevents one from directly applying standard FFT algorithms. It is shown that the space–frequency domain can be partitioned into rectangular and trapezoidal subdomains over which efficient algorithms can be developed. As in the previous work of Ying and Fomel (Multiscale Model Simul 8(1):110–124, 2009), the contribution from rectangular regions can be reduced to a series of fractional-phase Fourier transforms over squares, each of which can be reduced to a convolution. In this work, we demonstrate that the partial Fourier transform over trapezoidal domains can also be reduced to a convolution. Since the computational complexity of a dealiased convolution of N inputs is \({\mathcal O}(N\log N)\), a fast algorithm for the partial Fourier transform is achieved, with a lower overall coefficient than obtained by Ying and Fomel.     

Fast minimum float computation in activity networks under interval uncertainty

This paper concerns project scheduling under uncertainty. The project is modeled as an activity-on-node network, each activity having an uncertain duration represented by an interval. The problem of computing the minimum float of each activity over all duration scenarios is addressed. For solving this NP-hard problem, Dubois et al. (in J. Intell. Manuf. 16, 407–422, 2005) and Fortin et al. (in J. Sched. doi:10.1007/s10951-010-0163-3, 2010) have proposed an algorithm based on path enumeration. In this paper, new structural properties of optimal solutions are established and used for deriving a lower bound and designing an efficient branch-and-bound procedure. Two mixed-integer programming formulations are also proposed. Computational experimentations have been conducted on a large variety of randomly generated problem instances. The results show that the proposed branch-and-bound procedure is very fast and consistently outperforms the MIP formulations and the path enumeration algorithm.     

Fast Fourier Transform for Hexagonal Aggregates

Hexagonal aggregates are hierarchical arrangements of hexagonal cells. These hexagonal cells may be efficiently addressed using a scheme known as generalized balanced ternary for dimension 2, or GBT₂. The objects of interest in this paper are digital images whose domains are hexagonal aggregates. We define a discrete Fourier transform (DFT) for such images. The main result of this paper is a radix-7, decimation-in-space fast Fourier transform (FFT) for images defined on hexagonal aggregates. The algorithm has complexity N log₇ N. It is expressed in terms of the p-product, a generalization of matrix multiplication. Data reordering (also known as shuffle permutations) is generally associated with FFT algorithms. However, use of the p-product makes data reordering unnecessary.     

一种基于FFT计算离散小波变换的方法

将小波变换和快速傅里叶变换（FFT）方法相结合,分析研究了用快速傅里叶变换计算离散小波变换的方法,总结变换结果和滤波器长度之间的移位关系,并提出通过把输入信号信号循环移位,实现完全重构的方法。这种方法计算的时间复杂度和快速傅里叶变换相当。     

六角形阵快速傅立叶变换波束形成算法

在六角形阵阵元数较多时,传统的频域相移求和波束形成方法要求的运算量很大.为此提出一种采用六角形快速傅立叶变换HFFT(Hexagonal Fast Fourier Transform)的波束形成算法.使用六角形傅立叶变换HDFT(Hexagonal Discrete Fourier Transform)完成六角形阵的波束形成,由于HDFT存在快速算法HFFT,因此能够显著降低波束形成的运算量.首先在各个通道上做FFT,将信号变换到频域,然后转角重排,再对各个阵元上相同的频点做HFFT,得到频域常规波束形成输出.理论分析表明,对于窄带信号的六角形阵波束形成,所提出的算法所需的计算量比传统的相移求和方法降低了95%以上.仿真和试验结果表明,提出的算法在不影响阵列处理性能的同时,显著降低了波束形成所需的计算量,易于工程实现.     

Fast Reverse Jacket Transform As an Alternative Representation of the N-Point Fast Fourier Transform

The Reverse Jacket matrix (RJM) is a generalized form of the Hadamard matrix. Thus RJM is closely related to the matrix for fast Fourier transform (FFT). It also has a very interesting structure, i.e. its inverse can be easily obtained and has the reversal form of the original matrix. In this paper, we have shown that a transform based on the RJM offers a simple structure of N-point FFT in terms of the decomposition of the corresponding matrix and that it computes very fast the center weighted Hadamard transform.     

VHDL在FFT变换中的应用

控制系统的速度不但取决于控制器本身的速度,而且还在相当大程度上取决于控制算法,算法运算量的大小直接影响着对设备的控制质量。通过傅立叶变换(DFT),导出FIR实序列FFT快速简化算法;由VHDL编程,通过MAX PLUSII仿真,可以清晰地观测到,大大提高了运算速度,为实序列控制系统的设计提供了简单、方便、实用的计算机设计方法。     

A Novel Approach to Fast Discrete Fourier Transform

Discrete Fourier transform (DFT) is an important tool in digital signal processing. In the present paper, we propose a novel approach to performing DFT. We transform DFT into a form expressed in discrete moments via a modular mapping and truncating Taylor series expansion. From this, we extend the use of our systolic array for fast computation of moments without any multiplications to one that computes DFT with only a few multiplications and without any evaluations of exponential functions. The multiplication number used in our method isO(Nlog₂ N/ log₂log₂ N) superior toO(Nlog₂ N) in FFT. The execution time of the systolic array is onlyO(Nlog₂ N/ log₂log₂ N) for 1-D DFT andO(N^k) fork-D DFT (k⩾2). The systolic implementation is a demonstration of the locality of dataflow in the algorithms and hence it implies an easy and potential hardware/VLSI realization. The approach is also applicable to DFT inverses.     

CCS上FFT运算的实现

FFT运算是数字信号处理技术的基础,DSP经常要用到FFT的运算,但FFT算法程序的编写调试费时费力。TI公司提供了以TMS320C28x系列芯片为基础的CCSFFTLibrary库函数,该库函数专门用于FFT运算,使在TMS320C28x系列芯片上实现FFT变得容易,本文就在CCS软件仿真器模式情况下对FFTLibrary库函数进行介绍并就使用方法进行说明。     

Fast Fourier Transform simulation techniques for Coulomb gases

An improved approach to updating the electric field in simulations of Coulomb gases using the local lattice technique introduced by Maggs and Rossetto [A.C. Maggs, V. Rossetto, Phys. Rev. Lett. 88 (2002) 196402] is described and tested. Using the Fast Fourier Transform (FFT) an independent configuration of electric fields subject to Gauss' law constraint can be generated in a single update step. This FFT based method is shown to outperform previous approaches to updating the electric field in the simulation of a basic test problem in electrostatics of strongly correlated systems.     

一种三维快速傅里叶变换并行算法

三维快速傅里叶变换在物理计算领域中被广泛地使用.传统并行算法所使用的面划分和块划分方法并不适合稀疏三维向量的傅里叶变换.提出了一种新三维快速傅里叶变换的并行算法,针对稀疏三维向量的傅里叶变换,新算法通过重新调整x,Y,z三个方向的计算顺序,能最大限度地减少计算量以及进程间的通信量,从而减少计算时间,提高并行加速比.详尽的理论分析以及多个高性能计算平台上的实验结果证明:在对稀疏三维向量作傅里叶变换时,新算法优于传统算法.     

多核计算机上的快速傅里叶变换并行算法

针对现有多核结构上快速傅里叶变换(FFT)并行算法没有利用多级缓存和线程级并行等多核特性问题,通过运用多核多级存储特性合理划分数据,采取子序列FFT计算和多线程并行逐对计算FFT相结合的方法,给出一个N点、一维、有序和基数为2的多核多线程并行计算FFT非递归算法。理论分析和实验结果表明,该算法实用、高效,能获得较好的加速比和可扩展性。     

快速傅里叶变换乘法的性能研究

大数相乘是密码学的一种关键运算,其性能影响许多密码算法,如RSA、ElGamal等公钥密码运算的性能。对常见的大数乘法算法进行了实验、分析和比较,特别针对快速傅里叶变换（Fast Fourier Transform,FFT）算法,分析了其在大数乘法中的应用,并与其他常见大数算法的效率进行了比较,归纳了快速傅里叶变换的优势范围与劣势范围。同时,由于快速傅里叶变换计算过程中有误差,当数据位足够多时,可能导致计算结果不正确,因此进一步分析了傅里叶快速变换计算正确的数据位上限,这些工作对于快速乘法算法的正确选择有重要的实际意义。     

Fault Detection under Fuzzy Model Uncertainty

The paper tackles the problem of robust fault detection using Takagi-Sugeno fuzzy models. A model-based strategy is employed to generate residuals in order to make a decision about the state of the process. Unfortunately, such a method is corrupted by model uncertainty due to the fact that in real applications there exists a model-reality mismatch. In order to ensure reliable fault detection the adaptive threshold technique is used to deal with the mentioned problem. The paper focuses also on fuzzy model design procedure. The bounded-error approach is applied to generating the rules for the model using available measurements. The proposed approach is applied to fault detection in the DC laboratory engine.     

基于匹配滤波器与FFT的伪码快速捕获方法及性能分析

针对GPS信号伪码捕获消耗资源大与捕获时间长的问题,采用匹配滤波器(MF)与快速傅里叶变换(FF-T)相结合的方法.该方法有效结合了串行捕获与并行捕获的优点,在减少硬件资源的同时实现了信号的快速捕获.详细推导了该算法的理论,并在Matlab平台上实现了伪码捕获的仿真及算法性能分析.分析表明该算法较其他算法在减少资源消耗、实现快速捕获及抗干扰方面有较大的优越性,并可应用于下一代全球导航卫星定位系统(GNSS)信号的捕获,为新一代的卫星伪码捕获奠定了基础.     

分数傅里叶变换的快速算法及计算全息图的研究

通过分析菲涅耳衍射积分的快速算法，依据Lohmann提出的任意阶的分数傅里叶变换的单透镜光学实验装置，详细分析丁光场在此单透镜系统中的传播过程，提出了一种基于傅里叶变换的分数傅里叶变换快速算法，并对基于此快速算法的分数傅里叶变换全息图的计算机生成与数字重现进行了研究。实验结果示出了分数傅里叶变换全息图及其在重构过程中分数阶匹配与否的实验结果，验证了分数傅里叶变换分数阶的重要性质和笔者提出算法的可行性。     

分数傅里叶变换的快速算法及计算全息图的研究

通过分析菲涅耳衍射积分的快速算法,依据Lohmann提出的任意阶的分数傅里叶变换的单透镜光学实验装置,详细分析了光场在此单透镜系统中的传播过程,提出了一种基于傅里叶变换的分数傅里叶变换快速算法,并对基于此快速算法的分数傅里叶变换全息图的计算机生成与数字重现进行了研究。实验结果示出了分数傅里叶变换全息图及其在重构过程中分数阶匹配与否的实验结果,验证了分数傅里叶变换分数阶的重要性质和笔者提出算法的可行性。     

快速傅里叶变换的DSP实现及代码优化

介绍了时间抽取基2FFT 算法的基本原理和特点,并详细分析了FFT 算法的DSP实现及程序优化,最后采用MATLAB软件对算法进行了仿真.仿真结果证明,该方法具有精度高、运算速度快等特点.