Fast Fourier Transform PDF
Document Details
Uploaded by BoundlessXenon
Tags
Summary
This document presents a supplementary problem on radix-2 FFT algorithms in digital signal processing. It discusses the efficiency of convolution methods compared to using DFTs. The problem focuses on determining the values of L for a given sequence length when convolution directly is more efficient than performing convolution by taking the inverse DFT.
Full Transcript
CHAP. 71 THE FAST FOURIER TRANSFORM The two-dimensional array representation for the input is and for the output array we have 1 2 3 4 The int...
CHAP. 71 THE FAST FOURIER TRANSFORM The two-dimensional array representation for the input is and for the output array we have 1 2 3 4 The interconnections between the five- and three-point DFTs are the same as in the mixed-radix algorithm. However, there are no twiddle factors, and the ordering of the input and output arrays is different. The 15-point prime fuctor algorithm is diagrammed in the figure below. The savings with the prime factor algorithm over the mixed-radix FFT are the eight complex multiplies by the twiddle factors. Supplementary Problems Radix-2 FFT Algorithms 7.17 Let x ( n ) be a sequence of length 1024 that is to be convolved with a sequence h ( n ) of length L. For what values of L is it more efficient to perform the convolution directly than it is to perform the convolution by taking the inverse DFT of the product X (k)H ( k ) and evaluating the DFTs using a radix-2 FFT algorithm?
