Write a Matlab program to perform an 8-point decimation-in-time Fast Fourier Tra

Question

Write a Matlab program to perform an 8-point decimation-in-time Fast Fourier Transform. You do not need to create a routine that works for any (input) power of 2 length, -you can special- ize your routine for the case of N 8. Also, you do not need to capitalize on the in-place com- putation property of the FFT (you can use separate arrays for storing the output of each stage). Test your routine by computing the DFTs for the sequences x1[n] = (1,-1,1,-1,1,-1,1,-1) and x2[n] (1,1,1,1,0,0,0,0) and comparing with the result produced by Matlab's built-in 'ft' command.

Explanation / Answer

clc
clear all
x=input('Enter input Sequence in matrix form: ');
p=nextpow2(length(x));   
x=[x zeros(1,(2^p)-length(x))];
N=length(x);   
S=log2(N); %Number of stages   
hf=1; %intitialize   
x=bitrevorder(x); %Reverses bit order   
for stage=1:S;   
for index=0:(2^stage):(N-1);   
for n=0:(hf-1);
pos=n+index+1;   
power=(2^(S-stage))*n;   
wn=exp((-1j)*(2*pi)*power/N); %twiddle factor   
a=x(pos)+x(pos+hf).*wn; %a+b*wn
b=x(pos)-x(pos+hf).*wn; %a-b*wn
x(pos)=a;
x(pos+hf)=b;   
end;
end;
hf=2*hf; %number of butterflies updation
end;
y=x;   
fprintf('The DIT FFT of x(n) sequence is ')
disp(y)

fprintf(' DFT using inbuit function fft(x(n)) is ')
disp(fft(x))

Output:

1)

Enter input Sequence in matrix form: [1 -1 1 -1 1 -1 1 -1]
The DIT FFT of x(n) sequence is
0 0 0 0 8 0 0 0

DFT using inbuit function fft(x(n)) is
8 -8 8 -8 8 -8 8 -8

2)

Enter input Sequence in matrix form: [1 1 1 1 0 0 0 0]
The DIT FFT of x(n) sequence is
Columns 1 through 5

4.0000 + 0.0000i 1.0000 - 2.4142i 0.0000 + 0.0000i 1.0000 - 0.4142i 0.0000 + 0.0000i

Columns 6 through 8

1.0000 + 0.4142i 0.0000 + 0.0000i 1.0000 + 2.4142i

DFT using inbuit function fft(x(n)) is
Columns 1 through 5

8.0000 + 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 + 0.0000i

Columns 6 through 8

8.0000 + 0.0000i 8.0000 + 0.0000i 8.0000 + 0.0000i

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.