finding dft without using fft

Hi Guys!

I have one file name as data2 which has 100000 velocity data in column2 and I want to divide this data into record size of 256 and then perform dft without using the built in fft function in matlab. I also want to take a vaerage of these dft results point for point for all the dft results. I have perform the fft for the same data and i am expecting almost same types of plot for fft and dft. I have written a code for this but the plot that i am geeting is not similar to fft. Can you please help me what i am missing in my code. Here is my script

fontSize = 10;
tic;
start1= 1;
last1= 256;
for n= 1:1:390
    e(start1:last1,1)= data2(start1:last1, 2);
    start1= last1+1;
    last1= start1+ 255;
end
l=length(e)
dummymat1= zeros(l,1);
for v= 0:l-1
    for n= 0:l-1
        dummymat1(v+1)= dummymat1(v+1)+ e(n+1)* exp(((-i)*2*pi*v*n)/l);
    end
end
dft_1= abs(dummymat1);
first_point= 1;
last_point= 256;
for n= 1:1:390
    f(:,n)= dft_1(first_point:last_point, 2);
    first_point= last_point+1;
    last_point= start1 + 255;
end
for z=1:1:256
    sum (z,:) = f(z,:);
end;
for x=1:1:129
    avg(x,:)= mean(sum(x,:));
end
xx= linspace(0,15000/2,129)
loglog(xx,avg);
xlim([10^1 10^4])
xticks([10^1 10^2 10^3 10^4])
xticklabels({'10^1', '10^2', '10^3','10^4'})
ylim([10^1 10^5])
yticks([10^1 10^2 10^3 10^4 10^5])
yticklabels({'10^1', '10^2', '10^3', '10^4','10^5'})
toc;

[Raushan]

@Walter Roberson ?

[Raushan]

@Chunru ?

[Walter Roberson]

A lot of people have posted code to "manually" do fourier transform, and I am sure that there are File Exchange contributions to do it as well. It isn't worth our time to debug this particular one.

[Raushan]

Yeah you are right I did fft correctly but I am facing problem while doing dft.

[Walter Roberson]

dft means "discrete fourier transform". fft means "fast fourier transform", which is a particular algorithm for calculating a dft efficiently. If you "did fft" then you did dft -- all fft are dft .

But your fourier transform algorithm does not analyze the length of the signal down to prime factors, and it does not implement a butterfly transform. It is not, in fact, a fast fourier transform, just a discrete fourier transform. fft is a dft implemented with mathematical short-cuts

There is also the term stft which is "short time fourier transform". It consists of "sliding" a window over the data, taking a windowing function to reduce sharp edges at the ends, and doing a dft (discrete fourier transform) on the resulting window -- most commonly by calling fft() to implement the discrete fourier transform. You do not appear to be doing that.

Answer 1

[Chunru]

% If you want to compare fft and dft, it's better to write dft as a
% function and then perform the comparision.
x = cos(2*pi*.1*(0:255));

tic; y1 = fft(x); toc

Elapsed time is 0.003273 seconds.

tic; y2 = dft(x); toc

Elapsed time is 0.043077 seconds.

plot(abs(y1), 'r'); hold on
plot(abs(y2), 'b')
legend("fft", "dft")

function y = dft(x)
% DFT of a vector inpu x
l = length(x); 
y = zeros(size(x));

w = exp(-2i*pi/l);
for k=0:l-1             % freq index
    for n = 0:l-1;      % time index
        y(k+1) = y(k+1) + x(n+1)*w^(k*n);
    end
end
end