%0 Journal Article
%T Radix-2¦Á/4¦Â Building Blocks for Efficient VLSI¡¯s Higher Radices Butterflies Implementation
%A Marwan A. Jaber
%A Daniel Massicotte
%J VLSI Design
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/690594
%X This paper describes an embedded FFT processor where the higher radices butterflies maintain one complex multiplier in its critical path. Based on the concept of a radix-r fast Fourier factorization and based on the FFT parallel processing, we introduce a new concept of a radix-r Fast Fourier Transform in which the concept of the radix-r butterfly computation has been formulated as the combination of radix-2¦Á/4¦Â butterflies implemented in parallel. By doing so, the VLSI butterfly implementation for higher radices would be feasible since it maintains approximately the same complexity of the radix-2/4 butterfly which is obtained by block building of the radix-2/4 modules. The block building process is achieved by duplicating the block circuit diagram of the radix-2/4 module that is materialized by means of a feed-back network which will reuse the block circuit diagram of the radix-2/4 module. 1. Introduction For the past decades, the main concern of the researchers was to develop a fast Fourier transform (FFT) algorithm in which the number of operations required is minimized. Since Cooley and Tukey presented their approach showing that the number of multiplications required to compute the discrete Fourier transform (DFT) of a sequence may be considerably reduced by using one of the fast Fourier transform (FFT) algorithms [1], interest has arisen both in finding applications for this powerful transform and for considering various FFT software and hardware implementations. The DFT computational complexity increases according to the square of the transform length and thus becomes expensive for large . Some algorithms used for efficient DFT computation, known as fast DFT computation algorithms, are based on the divide-and-conquer approach. The principle of this method is that a large problem is divided into smaller subproblems that are easier to solve. In the FFT case, dividing the work into subproblems means that the input data can be divided into subsets from which the DFT is computed, and then the DFT of the initial data is reconstructed from these intermediate results. Some of these methods are known as the Cooley-Tukey algorithm [1], split-radix algorithm [2], Winograd Fourier transform algorithm (WFTA) [3], and others, such as the common factor algorithms [4]. The problem with the computation of an FFT with an increasing is associated with the straightforward computational structure, the coefficient multiplier memories¡¯ accesses, and the number of multiplications that should be performed. The overall arithmetic operations deployed in the computation of
%U http://www.hindawi.com/journals/vlsi/2014/690594/