China 
Africa 
Explore chapters and articles related to this topic
System Design
Published in Udo W. Pooch, Alan D. George, Lois Wright Hawkes, Microprocessor-Based Parallel Architecture for Reliable Digital Signal Processing Systems, 2018
Alan D. George, Lois Wright Hawkes
One common approach to implementing discrete Fourier transforms using the fast Fourier transform (FFT) algorithm, which was introduced earlier, is known as the decimation-in-time technique, due to the way the time domain input sequence is divided or decimated into successively smaller sequences. When used in base two, this complex N-point fast Fourier transformation algorithm requires (N/2)log2N butterfly operations. Each butterfly operation has two inputs and two outputs u and v, and is based on the following two equations: u(k+1)=u(k)+WNrv(k)v(k+1)=u(k)−WNrv(k) The variable WN is known as the twiddle factor, where: WNr=e−j2πNr=cos2πNr−jsin2πNr Each twiddle factor term is a complex coefficient which can be referenced from trigonometric lookup tables at execution time by using positive integer r as an index (where the value of r depends upon which stage or pass of the FFT the butterfly belongs to [BRIG74]). In terms of arithmetic requirements, the butterfly consists of one complex multiplication and two complex additions, which in turn dictates a total of four real multiplications and six real additions. By including memory or register variable access in a similar manner to that previously done with digital filter difference equations, the following butterfly timing approximation equation can be generated: tbfly=4tmult+6tadd+8tmem
Efficient FPGA architecture to implement non-separable fast Fourier transform for image and video applications
Published in International Journal of Electronics, 2023
Sayantam Sarkar, Satish S. Bhairannawar
In this paper, efficient non-separable architecture to implement 8-point DIT-FFT on FPGA is proposed. The overall architecture is derived from the non-separable DIT-FFT equations generated by solving the conventional Butterfly diagram with corresponding twiddle factor values. Along with it, the uses of complex conjugate relations simplifies the architecture at hardware level. Moreover, the uses of the Multiplier Equivalent block in the proposed architecture reduces the overall hardware utilisations where the basic logical elements are used for optimisation purpose. The Q-format is used in the architecture to get good trade-off between hardware parameters and data accuracy. For higher points of FFT, modification in the architecture is needed which can be derived from the corresponding butterfly diagram in the similar manner. In future, higher level of FFT will be implemented on FPGA in the similar manner with real time image and video signals as input.
Design and analysis of high performance and low power FFT for DSP datapath using Vedic Multipliers
Published in International Journal of Electronics Letters, 2022
Nidhi Gaur, Pradeep Kumar, Anu Mehra
Radix 2-FFT architecture involves calculation of twiddle factor. The 8-point FFT architecture has 12 butterfly structures and each structure has a complex multiplication unit with complexity of (n/2). Block diagram of 8-point FFT processor with butterfly units as components is shown in Figure 5. Here different 8-points from x(0) to x(7) represents Inputs and X(0) to X(7) represent outputs (Gaur, Mehra et al., 2019b). FFT operation is accomplished with the help of butterfly units. Each point is divided into its real and imaginary part and multiplication of all components are done separately in four units of floating-point multiplier in a butterfly unit (Figure 6). Here 24-bit multiplier proposed using Vedic algorithm, is used to design 32-bit floating point multiplier for butterfly unit.