Transcription of Introduction to the Fast-Fourier Transform (FFT) Algorithm
{{id}} {{{paragraph}}}
Introduction to the Fast-FourierTransform (FFT) RamalingamDepartment of electrical EngineeringIIT Ramalingam (EE Dept., IIT Madras)Intro to FFT1 / 30 The Discrete Fourier Transform (DFT)DFT of anN-point sequencexn,n= 0,1,2,..,N 1 isdefined asXk=N 1 n=0xne j2 kNnk= 0,1,2, ,N 1 AnN-point sequence yields anN-point transformXkcan be expressed as aninner product:Xk=[1e j2 kNe j2 j2 kN(N 1)] 1 Ramalingam (EE Dept., IIT Madras)Intro to FFT2 / 30 The Discrete Fourier Transform (DFT)Notation:WN=e j2 N. Hence,Xk=[ (N 1)kN] 1 By varyingkfrom 0 toN 1 and combining theNinnerproducts, we get the following:X=WxWis anN Nmatrix, called as the DFT Matrix Ramalingam (EE Dept.)
Introduction to the Fast-Fourier Transform (FFT) Algorithm C.S. Ramalingam Department of Electrical Engineering IIT Madras C.S. Ramalingam (EE Dept., IIT Madras) Intro to FFT 1 / 30
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document:
{{id}} {{{paragraph}}}