Scribd
Upload
132 views3 pages

IDFT and FFT Computation Steps

The document describes the process to find the inverse discrete Fourier transform (IDFT) of a sequence using the fast Fourier transform (FFT) algorithm. It involves 4 steps: 1) Take the complex conjugate of the given Fourier transform sequence X(k) 2) Calculate the discrete Fourier transform (DFT) of the complex conjugate X*(k) using FFT 3) Take the complex conjugate of the DFT output 4) Divide the result by N (where N is the number of points in the sequence) to obtain the IDFT It then provides examples of using this process to find the IDFT of different sequences using both direct and inverse FFT implementations.

Uploaded by

SAILAJA CHERUVUPALLI
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
132 views3 pages

IDFT and FFT Computation Steps

The document describes the process to find the inverse discrete Fourier transform (IDFT) of a sequence using the fast Fourier transform (FFT) algorithm. It involves 4 steps: 1) Take the complex conjugate of the given Fourier transform sequence X(k) 2) Calculate the discrete Fourier transform (DFT) of the complex conjugate X*(k) using FFT 3) Take the complex conjugate of the DFT output 4) Divide the result by N (where N is the number of points in the sequence) to obtain the IDFT It then provides examples of using this process to find the IDFT of different sequences using both direct and inverse FFT implementations.

Uploaded by

SAILAJA CHERUVUPALLI
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

INPUT STAGE 1 OUTPUT STAGE 2 OUTPUT

X(0) a=x(0)+x(2) X(0)=a+b


0
X(1) b=x(1)+x(3) X(2)=[a-b]W 4

0
X(2) c=[x(0)-x(2)]W X(1)=c+d 4

1 0
X(3) d=[x(1)-x(3)]W X(3)=[c-d]W
4 4

Find the Fourier transform of x(n)={1,1,1,1} using DIF FFT.

Finding IDFT using FFT algorithm.


N −1
1
x(n)= N ∑ X (k)e j 2 πnk / N
n=0

N −1
1
=N ∑ X ( k ) [e− j2 πnk / N ¿ ]¿*
n=0

N −1 N−1
1
=
N
∑ ¿ ¿X (k)e * − j2 πnk / N *
¿ DFT X(k)= ∑ x (n) e− j 2 πnk / N
n=0 n =0

1
= N [DFT{ X*(k)}]*
Procedure to find IDFT using FFT

Step 1: Find complex conjugation of given X(k)

Step 2: Find DFT of X*(k) using either DIT FFT or DIF FFT

Step 3: Find complex conjugate of output of DFT

Step 4: Multiply the result with 1/N.

X(k)={0,2.8284-j2.8284,0,0,0,0,0,2.8284+j2.8284} using DIT FFT

Step 1: X*(k)= {0,2.8284+j2.8284,0,0,0,0,0,2.8284-j2.8284}

Step 2: N=8

DFT{X*(k)}={5.6568,8,5.6568,0,-5.6568,-8,-5.6568,0}

Step 3: [DFT{X*(k)}]*={ 5.6568,8,5.6568,0,-5.6568,-8,-5.6568,0}

Step 4: 1/8*[DFT{X*(k)}]*={0.707,1,0.707,0,-0.707,-1,-0.707,0}

Find IDFT of the sequence X(k)={7,-0.707-j0.707,-j,0.707-


j0.707,1,0.707+j0.707,j,-0.707+j0.707} using DIF FFT algorithm.

Step 1 :X*(k)={7,-0.707+j0.707,j,0.707+j0.707,1,0.707-j0.707,-j,-0.707-
j0.707}

Step 2:DFT{X*(k)}={8,8,8,8,8,8,8,0}

Step 3: [DFT{X*(k)}]*={8,8,8,8,8,8,8,0}

Step 4: 1/8*[DFT{X*(k)}]={1,1,1,1,1,1,1,0}
Compute IDFT of X(k)={0,0,4,0} using DIT FFT

X(n)={1,-1,1,-1}

You might also like