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     

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     

Scheme for reducing size of coefficient memory in FFT processor

Long fast Fourier transforms (FFTs) are required in applications such as orthogonal frequency division multiplexing, radars and sonars. It is highly desirable to reduce the size and power requirements of the FFT so as to realise single chip long FFT-based systems targeting portable applications. Presented here is a novel technique to reduce the coefficient memory almost by a factor of four by exploiting the relationships among the coefficient values thereby significantly reducing the area and power requirements of the hardware     

A 64-point Fourier transform chip for video motion compensationusing phase correlation

Details of a new low power fast Fourier transform (FFT) processor for use in digital television applications are presented. This has been fabricated using a 0.6-μm CMOS technology and can perform a 64 point complex forward or inverse FFT on real-time video at up to 18 Megasamples per second. It comprises 0.5 million transistors in a die area of 7.8×8 mm² and dissipates 1 W. The chip design is based on a novel VLSI architecture which has been derived from a first principles factorization of the discrete Fourier transform (DFT) matrix and tailored to a direct silicon implementation     

COFDM: an overview

The research and development of OFDM/COFDM for digital television broadcasting has received considerable attention and has made a great deal of progress in Europe. OFDM/COFDM has already been implemented in digital audio broadcasting and is being considered for terrestrial digital television and HDTV broadcasting. The advantages of COFDM claimed by the advocates in Europe have also caught the attention of US broadcasters and generated enthusiasm although a digital modulation technique called 8-VSB has been selected by the FCC Advisory Committee on Advanced Television Service (ACATS) for the final testing. There is considerable debate in the industry over the use of COFDM vs. VSB or QAM for terrestrial HDTV broadcasting. In this paper, the history of research and development on OFDM and COFDM is reviewed. Then, the basic principles, performance and implementation of OFDM and COFDM are examined. Analysis is given to enable the selection of key elements for meeting the constraints of the required applications. Based on the ATV channel model, performance expectation of COFDM under imperfect channel conditions and implementation issues are examined in details     

A VLSI array processor for 16-point FFT

An implementation of a two-dimensional array processor for fast Fourier transform (FFT) using a 2-μm CMOS technology is presented. The array processor, which is dedicated to 16-point FFT, implements a 4×4 mesh array of 16 processing elements (PEs) working in parallel. Design considerations in both the chip level and the PE level are examined. A layout design methodology based on bit-slice units (BSUs) results in a very simple design, easy debugging, and a regular interconnection scheme through abutment. It contains about 48,000 transistors on an area of 53.52 mm², excluding the 83-pad area, and operation is on a 15-MHz clock. The array processor performs 24.6 million complex multiplications per second, and computes a 16-point FFT in 3 μs     

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     

Novel Reversible Integer Fourier Transform With Control Bits

This paper presents a novel concept of the reversible integer discrete Fourier transform (RiDFT) of order 2^r, r > 2, when the transform is split by the paired representation into a minimum set of short transforms, i.e., transforms of orders 2^k, k < r. By means of the paired transform the signal is represented as a set of short signals which carry the spectral information of the signal at specific and disjoint sets of frequencies. The paired transform-based fast Fourier transform (FFT) involves a few operations of multiplication that can be approximated by integer transforms. Examples of 1-point transforms with one control bit are described. Control bits allow us to invert such approximations. Two control bits are required to perform the 8-point RiDFT, and 12 (or even 8) bits for the 16-point RiDFT of real inputs. The proposed forward and inverse RiDFTs are fast, and the computational complexity of these transforms is comparative with the complexity of the FFT. The 8-point direct and inverse RiDFTs are described in detail.     

Fast Fourier transform for discontinuous functions

In computational electromagnetics and other areas of computational science and engineering, Fourier transforms of discontinuous functions are often required. We present a fast algorithm for the evaluation of the Fourier transform of piecewise smooth functions with uniformly or nonuniformly sampled data by using a double interpolation procedure combined with the fast Fourier transform (FFT) algorithm. We call this the discontinuous FFT algorithm. For N sample points, the complexity of the algorithm is O(/spl nu/Np+/spl nu/Nlog(N)) where p is the interpolation order and /spl nu/ is the oversampling factor. The method also provides a new nonuniform FFT algorithm for continuous functions. Numerical experiments demonstrate the high efficiency and accuracy of this discontinuous FFT algorithm.     

A self-testing 2-/spl mu/m CMOS chip set for FFT applications

A chip set for high-speed radix-2 fast Fourier transform (FFT) applications up to 512 points is described. The chip set comprises a (16+16)/spl times/(12+12)-bit complex number multiplier, and a 16-bit butterfly chip for data reordering, twiddle factor generation, and butterfly arithmetic. The chips have been implemented using a standard cell design methodology on a 2-/spl mu/m bulk CMOS process. Three chips implement a complex FFT butterfly with a throughput of 10 MHz, and are cascadable up to 512 points. The chips feature an offline self-testing capability.     

Multidimensional systolic arrays for the implementation of discreteFourier transforms

This paper presents an efficient technique for using a multidimensional systolic array to perform the multidimensional discrete Fourier transform (DFT). Extensions of the multidimensional systolic array suitable for fast Fourier transform (FFT) computations such as the prime-factor computation or the 2ⁿ-point decomposed computation of the one-dimensional (1-D) discrete Fourier transform are also presented. The essence of our technique is to combine two distinct types of semisystolic arrays into one truly systolic array. The resulting systolic array accepts streams of input data (i.e., it does not require any preloading), and it produces output data streams at the boundary of the array. No networks for intermediate spectrum transposition between constituent transforms are required. The systolic array has regular processing elements that contain a complex multiplier accumulator and a few registers and multiplexers. Simple and regular connections are required between the PEs     

Efficient VLSI architectures for fast computation of the discreteFourier transform and its inverse

In this paper, we propose two new VLSI architectures for computing the N-point discrete Fourier transform (DFT) and its inverse (IDFT) based on a radix-2 fast algorithm, where N is a power of two. The first part of this work presents a linear systolic array that requires log₂ N complex multipliers and is able to provide a throughput of one transform sample per clock cycle. Compared with other related systolic designs based on direct computation or a radix-2 fast algorithm, the proposed one has the same throughput performance but involves less hardware complexity. This design is suitable for high-speed real-time applications, but it would not be easily realized in a single chip when N gets large. To balance the chip area and the processing speed, we further present a new reduced-complexity design for the DFT/IDFT computation. The alternative design is a memory-based architecture that consists of one complex multiplier, two complex adders, and some special memory units. The new design has the capability of computing one transform sample every log₂ N+1 clock cycles on average. In comparison with the first design, the second design reaches a lower throughput with less hardware complexity. As N=512, the chip area required for the memory-based design is about 5742×5222 μm², and the corresponding throughput can attain a rate as high as 4M transform samples per second under 0.6 μm CMOS technology. Such area-time performance makes this design very competitive for use in long-length DFT applications, such as asymmetric digital subscriber lines (ADSL) and orthogonal frequency-division multiplexing (OFDM) systems     

Digital/analogue co-channel protection ratio field measurements

The digital terrestrial television standard approved by the European Telecommunications Standards Institute (ETSI) using coded orthogonal frequency division multiplexing (COFDM) facilitates the establishment of complex networks including single frequency networks (SFN) and multiple frequency networks (MFN). RTE and other partners of European Union (EU) sponsored projects such as MOTIVATE and VALIDATE have established and tested these networks in order to understand the important parameters of digital networks. Protection ratios are needed in order to plan the coverage of digital networks and minimise interference from co-channel transmitters. This paper describes a network established to field test protection ratios and details the measurements performed. Three co-channel UHF transmitters were installed at RTE mainstations in the Dublin area     

A CORDIC processor for FFT computation and its implementation usinggallium arsenide technology

In this paper, the architecture and the implementation of a complex fast Fourier transform (CFFT) processor using 0.6 μm gallium arsenide (GaAs) technology are presented. This processor computes a 1024-point FFT of 16 bit complex data in less than 8 μs, working at a frequency beyond 700 MHz, with a power consumption of 12.5 W. The architecture of the processor is based on the COordinate Rotation DIgital Computer (CORDIC) algorithm, which avoids the use of conventional multiplication-and-accumulation (MAC) units, but evaluates the trigonometric functions using only add and shift operations, Improvements to the basic CORDIC architecture are introduced in order to reduce the area and power of the processor. This together with the use of pipelining and carry save adders produces a very regular and fast processor, The CORDIC units were fabricated and tested in order to anticipate the final performance of the processor. This work also demonstrates the maturity of GaAs technology for implementing ultrahigh-performance signal processors     

FFT and IMDCT circuit sharing in DAB receiver

This paper proposes a circuit-sharing approach to improve efficiency for the key digital audio broadcasting (DAB) techniques, i.e., MPEG1-audio decoding and orthogonal frequency division multiplexing (OFDM). Because OFDM's fast Fourier transform (FFT) requires heavy computational power for implementation, a single butterfly processing element (BPE) is adopted to reduce the chip area required for FFT. Furthermore, by modifying the BPE logical combinational circuit, both IMDCT (inverse modified discrete cosine transform) and FFT functions can be obtained simultaneously from a single VLSI chip. Therefore, the proposed technique reduces hardware overhead, enhances circuit efficiency and significantly reduces the cost of DAB receivers. The proposed circuit is simulated as a VLSI prototype chip using a 0.35 /spl mu/m CMOS process, with a chip area of about 22.09 mm/sup 2/ and a total gate count of approximately 10839 (excluding ROM and RAM).     

A 64-point Fourier transform chip for high-speed wireless LAN application using OFDM

In this paper, we present a novel fixed-point 16-bit word-width 64-point FFT/IFFT processor developed primarily for the application in an OFDM-based IEEE 802.11a wireless LAN baseband processor. The 64-point FFT is realized by decomposing it into a two-dimensional structure of 8-point FFTs. This approach reduces the number of required complex multiplications compared to the conventional radix-2 64-point FFT algorithm. The complex multiplication operations are realized using shift-and-add operations. Thus, the processor does not use a two-input digital multiplier. It also does not need any RAM or ROM for internal storage of coefficients. The proposed 64-point FFT/IFFT processor has been fabricated and tested successfully using our in-house 0.25-/spl mu/m BiCMOS technology. The core area of this chip is 6.8 mm/sup 2/. The average dynamic power consumption is 41 mW at 20 MHz operating frequency and 1.8 V supply voltage. The processor completes one parallel-to-parallel (i.e., when all input data are available in parallel and all output data are generated in parallel) 64-point FFT computation in 23 cycles. These features show that though it has been developed primarily for application in the IEEE 802.11a standard, it can be used for any application that requires fast operation as well as low power consumption.     

Cost-Effective Triple-Mode Reconfigurable Pipeline FFT/IFFT/2-D DCT Processor

This investigation proposes a novel radix-4² algorithm with the low computational complexity of a radix-16 algorithm but the lower hardware requirement of a radix-4 algorithm. The proposed pipeline radix-4² single delay feedback path (R4²SDF) architecture adopts a multiplierless radix-4 butterfly structure, based on the specific linear mapping of common factor algorithm (CFA), to support both 256-point fast Fourier transform/inverse fast Fourier transform (FFT/IFFT) and 8times8 2D discrete cosine transform (DCT) modes following with the high efficient feedback shift registers architecture. The segment shift register (SSR) and overturn shift register (OSR) structure are adopted to minimize the register cost for the input re-ordering and post computation operations in the 8times8 2D DCT mode, respectively. Moreover, the retrenched constant multiplier and eight-folded complex multiplier structures are adopted to decrease the multiplier cost and the coefficient ROM size with the complex conjugate symmetry rule and subexpression elimination technology. To further decrease the chip cost, a finite wordlength analysis is provided to indicate that the proposed architecture only requires a 13-bit internal wordlength to achieve 40-dB signal-to-noise ratio (SNR) performance in 256-point FFT/IFFT modes and high digital video (DV) compression quality in 8 times 8 2D DCT mode. The comprehensive comparison results indicate that the proposed cost effective reconfigurable design has the smallest hardware requirement and largest hardware utilization among the tested architectures for the FFT/IFFT computation, and thus has the highest cost efficiency. The derivation and chip implementation results show that the proposed pipeline 256-point FFT/IFFT/2D DCT triple-mode chip consumes 22.37 mW at 100 MHz at 1.2-V supply voltage in TSMC 0.13-mum CMOS process, which is very appropriate for the RSoCs IP of next-generation handheld devices.     

二维级联流水结构大点数FFT运算器实现研究

大点数快速傅里叶变换(FFT)运算在雷达、通信信号侦察中有广泛应用,其基于现场可编程门阵列(FPGA)的实现方法有重要的研究价值。推导出点数为N的大点数FFT运算分解为2级小点数FFT运算级联的运算公式,在此基础上给出其实现步骤,从流水线结构设计、基本运算单元以及地址生成等方面详细介绍一维列(行)变换的工程实现方法,并给出列、行变换之间所乘旋转因子的压缩算法。工程实际应用表明,该大点数FFT运算器具有变换速度快、调试方便及可在单片FPGA实现的优点。     

A Built-in-Self-Test Σ-Δ ADC Prototype

This paper presents a built-in-self-test (BIST) Σ-Δ ADC prototype. The BIST circuity uses the proposed modified controlled sine wave fitting (CSWF) procedure to calculate the signal power and the total-harmonic-distortion-and-noise power in time domain separately. Compared with conventional Fast Fourier Transform (FFT) analysis, neither complex CPU/DSP nor bulky memory is required. The added BIST circuitry is purely digital and the hardware overhead is as low as 11.9 K gates. A prototype comprising the second-order design-for-digital-testability Σ-Δ modulator chip and an FPGA board which implements the digital functions is used to demonstrate the effectiveness of the BIST design. Measurement results show that the SNDR difference between conventional FFT analysis and the proposed BIST design of the standard ??6 dBFS, 1 KHz tone test is only 0.3 dB. Furthermore, the tested dynamic range values by both methods are the same. The proposed BIST implementation achieves the advantages of compact hardware, high test accuracy, and the flexibility of adjusting the stimuli which are important features for BIST applications.     

基于FPGA的基-6FFT算法的设计与实现

介绍了一种基于FPGA的FFT算法的实现——以Altera公司的FLEX10K系列产品为硬件平台,用VHDL语言和电路图完成系统设计描述,用MAX plusⅡ软件进行编译、综合和下载,实现了6点实序列DFT算法,并给出了仿真测试的结果。在FPGA芯片上运行的FFT算法具有速度快且抗干扰能力强的硬件实现的优点,用VHDL语言实现的基于IP核FFT算法具有很好的可移植性,可以重复使用,大大提高了设计效率。