Part 2 book "Applied digital signal processing - Theory and practic" includes content: Computation of the Discrete Fourier Transform; structures for discrete-time systems, design of FIR filters, design of IIR filters, multirate signal processing. | Computation of the Discrete Fourier 8 Transform This chapter is primarily concerned with algorithms for efficient computation of the Discrete Fourier Transform DFT . This is an important topic because the DFT plays an important role in the analysis design and implementation of many digital signal processing systems. Direct computation of the N -point DFT requires computational cost proportional to N 2 . The most important class of efficient DFT algorithms known collectively as Fast Fourier Transform FFT algorithms compute all DFT coefficients as a block with computational cost proportional to N log2 N . However when we only need a few DFT coefficients a few samples of DTFT or a few values of z -transform it may be more efficient to use algorithms based on linear filtering operations like the Goertzel algorithm or the chirp z -transform algorithm. Although many computational environments provide FFT algorithms as built-in func- tions the user should understand the fundamental principles of FFT algorithms to make effective use of these functions. The details of FFT algorithms are important to designers of real-time DSP systems in either software or hardware. Study objectives After studying this chapter you should be able to Understand the derivation operation programming and use of decimation-in-time and decimation-in-frequency radix-2 FFT algorithms. Understand the general principles underlying the development of FFT algorithms and use them to make effective use of existing functions evaluate competing algorithms or guide the selection of algorithms for a particular application or computer architecture. 435 Direct computation of the Discrete Fourier Transform Direct computation of the Discrete Fourier Transform The DFT of a finite-length sequence of length N is defined by see Chapter 7 N 1 X k kn x n WN k 0 1 . . . N 1 n 0 2π where WN e j N the root-of-unity is also known as the twiddle factor. The inverse DFT is given by N 1 1 kn x n X k WN . n 0 1 . . . N 1 .
