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

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

Systolic FFT Processors: A Personal Perspective

This paper provides a personal perspective on developments in the implementation of two systolic fast Fourier transform processors over the last 25 years and identifies some of the lessons learned. This has been a period of tremendous advancements in integrated circuit technology that is demonstrated by the resulting processors. The first processor is the Modular Transform Processor that was developed at TRW in the 1982–1984 time frame using VLSI technology. It is a set of six large circuit boards that computes 4,096-point fast Fourier transforms using 22-bit floating-point arithmetic at sustained data rates of 40 MSPS. The second processor is a single ASIC chip systolic FFT processor developed by the Mayo Foundation in the 2001–2002 time frame that computes 4,096-point FFTs using 16-bit fixed-point arithmetic at sustained data rates of 200 MSPS. Some thoughts on the future directions of systolic FFT processor development are offered. Future systems will compute large transforms (e.g., 16 K-point to 1 M-point) at high data rates (e.g., 500 MSPS to 1 GSPS), will employ more precise arithmetic (e.g., 32-bit single precision IEEE Standard floating-point arithmetic), will consume very low power (e.g., on the order of one watt) and will be realized on a single chip.     

Scalable FFT Processors and Pipelined Butterfly Units

This paper considers partial-column radix-2 FFT processors and realizations of butterfly operations. The area and power-efficiency of butterfly units to be used in the proposed processor organization based on bit-parallel multipliers, distributed arithmetic, and CORDIC are analyzed and compared. All the selected butterfly units are synthesized onto the same 0.11 μ ASIC technology allowing the results to be compared. The proposed processor organization permits the area of the FFT implementation to be traded against the computation time, thus the final structure can be easily tailored according to the requirements of the given application. The power consumption comparison shows that butterflies based on bit-parallel multipliers are power-efficient but have limitations on clock frequency. Butterflies based on distributed arithmetic could be used when higher clock frequencies are used. If extremely long FFTs are needed, the CORDIC based butterflies are applicable. Jarmo Takala received his M.Sc. (hons) degree in Electronics and Dr.Tech. degree in Information Technology from Tampere University of Technology, Tampere, Finland (TUT) in 1987 and 1999, respectively. From 1992 to 1996, he was a Research Scientist at VTT-Automation, Tampere, Finland. Between 1995 and 1996, he was a Senior Research Engineer at Nokia Research Center, Tampere, Finland. From 1996 to 1999, he was a Researcher at TUT. Currently, he is Professor in Computer Engineering at TUT and head of the Insitute of Digital and Computer Systems of TUT. His research interests include circuit techniques, parallel architectures, and design methodologies for digital signal processing systems. Konsta Punkka received his M.Sc. degree (hons) in Electrical Engineering from Tampere University of Technology (TUT), in 2002. He is currently working towards his Dr.Tech. degree as a research scientist in the Institute of Digital and Computer Systems at TUT. His research interests include optimization and implementation of DSP architectures.     

Mixed-Radix Algorithm for the Computation of Forward and Inverse MDCTs

The modified discrete cosine transform (MDCT) and inverse MDCT (IMDCT) are two of the most computationally intensive operations in MPEG audio coding standards. A new mixed-radix algorithm for efficiently computing the MDCT/IMDCT is presented. The proposed mixed-radix MDCT algorithm is composed of two recursive algorithms. The first algorithm, called the radix-2 decimation-in-frequency algorithm, is obtained by decomposing an N-point MDCT into two MDCTs with the length N/2. The second algorithm, called the radix-3 decimation-in-time algorithm, is obtained by decomposing an N -point MDCT into three MDCTs with the length N/3. Since the proposed MDCT algorithm is also expressed in the form of a simple sparse matrix factorization, the corresponding IMDCT algorithm can be easily derived by simply transposing the matrix factorization. Comparison of the proposed algorithm with some existing ones shows that our proposed algorithm is more suitable for parallel implementation and particularly suitable for the layer III of MPEG-1 and MPEG-2 audio encoding and decoding. Moreover, the proposed algorithm can be easily extended to the multidimensional case by using the vector-radix method.     

Reduced Memory and Low Power Architectures for CORDIC-based FFT Processors

This paper presents a pipelined, reduced memory and low power CORDIC-based architecture for fast Fourier transform implementation. The proposed algorithm utilizes a new addressing scheme and the associated angle generator logic in order to remove any ROM usage for storing twiddle factors. As a case study, the radix-2 and radix-4 FFT algorithms have been implemented on FPGA hardware. The synthesis results match the theoretical analysis and it can be observed that more than 20% reduction can be achieved in total memory logic. In addition, the dynamic power consumption can be reduced by as much as 15% by reducing memory accesses.     

一种在r台机上的并行排序算法

本文给出一个在ｒ台机上的实用并行排序算法，并行步数不超过Ｔｒ＝Ｏ（ｎ／ｒ）ｌｏｇ２ｒ．ｌｏｇ２ｎ），１＜ｒ＜ｎ．     

A New Base—6 FFT Algorithm

A new FFT algorithm has been deduced, which is called the base-6 FFT algorithm. The amount for calculating the DFT of complex sequence of N =2 r by the base-6 FFT algorithm is M r( N )=14/3· N log 6 N -4 N +4 for multiplication operation of real number and A r( N )=23/3· N log 6 N -2 N +2 for addition operation of real number. The amount for calculating the DFT of real sequence is a half of it with the complex sequence.     

FFT算法的一种FPGA设计

在分析了快速傅里叶算法理论的基础上,提出了一种频率抽取基4FFT的FPGA设计方案,针对现有FFT的FPGA实现过程中蝶形运算需要频繁乘以多个旋转因子提出了改进方法,减少了旋转因子的乘法次数和存储空间,加快了蝶形运算的速度,设计的地址映射方法,无需运算即可得到所需数据的存放地址,并结合采用乒乓结构和流水线方式,来提高快速傅里叶变换(FFT)FPGA实现的速度,为实现FFT算法提供了一定的参考价值。     

一种新结构FFT算法及其FPGA实现

本文给出了一种面向FPGA实现的新结构FFT算法,并利用FPGA器件内部丰富的逻辑单元,RAM、ROM和DSP块实现了FFT核心运算的并行化,与利用传统结构实现的FFT相比大大提高了FFT的运算速度,与用DSP实现的FFT相比速度也要快得多。     

一种基于SIMD-MCC计算机的二维FFT并行算法

FFT是图像处理中最重要的全局算子之一。文章以SIMD-MCC并行计算机为模型,讨论了二维FFT的并行实现问题,同时给出了相应的并行算法。该算法利用处理元的局部存储器,可在K×K的阵列上处理M×M的图像(M>K),较好的解决了在固定规模阵列上对大尺寸图像进行处理的问题。通过对算法的性能分析表明本算法是可行和高效的。