Scribd
Upload
112 views2 pages

Radix-2 Dit FFT Algo Function

The document describes a radix-2 decimation-in-time (DIT) fast Fourier transform (FFT) algorithm using three butterfly functions. It defines butterflies for stages 1, 2, and 3 of a radix-2 DIT FFT. It then shows an example implementation on a length-8 vector, applying the butterfly functions in stages to compute the DIT FFT.

Uploaded by

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

Radix-2 Dit FFT Algo Function

The document describes a radix-2 decimation-in-time (DIT) fast Fourier transform (FFT) algorithm using three butterfly functions. It defines butterflies for stages 1, 2, and 3 of a radix-2 DIT FFT. It then shows an example implementation on a length-8 vector, applying the butterfly functions in stages to compute the DIT FFT.

Uploaded by

Sukanti Pal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

RADIX-2 DIT FFT ALGO

function​ [ z ] = buttrfly1(x,N )
z=[];
z1=[];
z2=[];
for​ k=1:N/2
w=exp(-j*2*pi*(k-1)/N);
z1=[z1,x(k)+x(k+(N/2))]
z2=[z2,x(k)-x(k+(N/2))]
end
z=[z1 z2]

function​ [ z ] = buttrfly2(x,c )
l=length(x);
z=[];
z1=[];
z2=[];
for​ k=1:l/2
w=exp(-j*2*pi*(k-1)/c);
z1=[z1,x(k)+(x(floor(((k+l)/2)+1)))*w]
z2=[z2,x(k)-(x(floor(((k+l)/2)+1)))*w]
end
z=[z1 z2]
end

function​ [ z ] = buttrfly3(x,c )
l=length(x);
z=[];
z1=[];
z2=[];
for​ k=1:l/2
w=exp(-j*2*pi*(k-1)/c);
z1=[z1,x(k)+(x(floor(((k+l)/2)+1)))*w]
z2=[z2,x(k)-(x(floor(((k+l)/2)+1)))*w]
end
z=[z1 z2]

clc
clear ​all
v=[1 2 3 4 4 3 2 1]
x = bitrevorder(v)
N=8;
z=[]
for​ i= 1:N/4:N
g=[x(i),x(i+1)]
y=buttrfly1(g,N/4 )
z=[z y]
end
z1=[]
for​ i= 1:N/2:N
g1=[z(i:i+3)]
y1 = buttrfly2(g1,N/2)
z1=[z1 y1]
end
[ z2 ] = buttrfly3(z1,N )
z2

DIT
function​[z]=butterfly(x,N)
z=[]
z1=[]
z2=[]
for​ k=1:N/2
w=exp(-j*2*pi*(k-1)/N)
z1=[z1,x(k)+x(k+N/2)*w]
z2=[z2,x(k)-x(k+N/2)*w]
end
z=[z1,z2]

clc
clear ​all
v=[1 1 1 1 1 1 1 1]
x = bitrevorder(v)
N=8;
z=[]
for​ i= 1:N/4:N
g=[x(i),x(i+1)]
y=butterfly(g,N/4 )
z=[z y]
end
z1=[]
for​ i= 1:N/2:N
g1=[z(i:i+3)]
y1 = butterfly(g1,N/2)
z1=[z1 y1]
end
[ z2 ] = butterfly(z1,N )
z2

You might also like