TAILIEUCHUNG - Lecture Digital signal processing: Lecture 10 - Zheng-Hua Tan

The main contents of this chapter include all of the following: Direct computation of the DFT, decimation-in-time FFT algorithms, decimation-in-frequency FFT algorithms, fourier analysis of signals using the DFT. | Digital Signal Processing Fall 2005 - E-Study - Lecture 10 Fast Fourier Transform Zheng-Hua Tan Department of Communication Technology Aalborg University Denmark zt@ enF Center for TelelnFfastruktur Digital Signal Processing X Zheng-Hua Tan 2005 Course at a glance MM3 MM9 MM10 CTiF -f Digital Signal Processing X Zheng-Hua Tan 2005 2 Digital computation of the DFT The DFT of a finite-length sequence of length N X k .4 k 0 1 . N -1 The inverse D FT 4 -1 X k iWN11 0 1 . N -1 N k 0 Due to the duality focus on the DFT only. Use the number of arithmetic multiplications and additions as a measure of computational complexity. Fast Fourier transform FFT is a set of algorithms for the efficient and digital computation of the N-point DFT rather than a new transform. CTlF Digital Signal Processing X Zheng-Hua Tan 2005 3 Part I Direct computation of the DFT Direct computation of the DFT Decimation-in-time FFT algorithms Decimation-in-frequency FFT algorithms Fourier analysis of signals using the DFT CTiF Digital Signal Processing X Zheng-Hua Tan 2005 4 Direct computation of the DFT The DFT of a finite-length sequence of length N X k WWN k 0 1 . N -1 x n J X k n 0 Direct computation N2 complex multiplications and N N-1 complex additions Compute and store only over one period w e-j 2n N cos 2nk N j sin 2nk N k 0 1 . N -1 Compute the DFT using stored wN and input x n X k ĩ x n W n k 0 1 . N-1 n 0 WN and x n may be complex CTlF Digital Signal Processing X Zheng-Hua Tan 2005 5 Direct computation of the DFT For each k N-1 X k y Re x n Re WNn - Im x n Im WN n 0 j Re x n ImWW Im x n ReW k 0 1 . N-1 Therefore for each value of k the direct computation of X k requires 4N real multiplications and 4N-2 real additions. The direct computation of the DFT requires 4 N 2 real multiplications and N 4 N - 2 real additions. The efficiency can be improved by exploiting the symmetry and periodicity properties of WNkn CTlF Digital Signal Processing X Zheng-Hua Tan 2005

• Kĩ thuật Viễn thông
• Digital signal processing
• Digital signal
• Lecture Digital signal processing
• Discrete time signals
• Fast fourier transform
• Decimation in time FFT algorithms
• Xử lý tín hiệu số
• Signal processing
• DSP applications
• Digital Signal Processing Research Program
• Avanced Telecommunications and Signal Processing Program
• Signal Processing Program
• Combined Source
• Block processing methods
• Sample processing methods
• VLSI Digital signal processing systems
• DSP systems
• FIR Digital Filters
• Parallel processing
• Digital signal processing: Principles Algorithms and Applications
• Fast fourier transform algorithms
• Discrete time systems
• Design of digital filters
• Multirate digital signal processing
• Lecture Signal processing
• Xử lý tín hiệu
• Mixed signals processing
• Applications of digital signal processing
• Block diagram representation
• Signal flow graph description
• Quantization process
• Digital to analog converters
• Transfer functions
• Digital filter realization
• Discrete time signal
• Ultrasound signal processing
• Hardware software partitioning
• Digital signal processing systems
• Ultrasound devices
• Sampling theorem
• Analog reconstruction
• The z transform
• Properties of the z transform
• Discrete time fourier transform
• Discrete fourier transform
• Types of signals
• System impulse response
• Fourier transforms
• Inverse z transform
• Properties of z transform
• Periodic sampling
• „Frequency domain representation
• System analysis
• Frequency response
• Filter design
• IIR filter design
• FIR filter design
• Linear phase FIR filter
• Fourier transform
• Loop bound
• DSP programs