How to implement 2D discrete fourier transform in matlab without using fft2 built in function

Hi everyone,

I have an assignment that asks me to implement the 2D discrete fourier transform in matlab without using fft2 function.

I wrote a code that seems to be right (according to me) but when I compare the result I get with the result with the fft2 function, they are not the same.

If someone could tell me what's wrong, here's the code:

 function [A] = fourier1 (X)
[M,N]=size(X);
A=zeros(M,N);
ro=0;
co=0;
for u=1:M
    for v=1:N
        for m=1:M
            for n=1:N
                co=co+X(m,n)*exp(1i*(-2)*pi*((u*m/M)+(v*n/N)));
            end
            ro=ro+co;
        end
        A(u,v)=ro;
        ro=0;
        co=0;
    end
end

Thanks everyone!

[Jonathan Doucette]

I don't know if it matters to you anymore, but I'll put this in here for others. Your problem was that you needed to use (u-1), (m-1), (v-1), and (n-1) in place of u, m, v, and n, respectively, as Matlab indexes from 1 but the equations index from 0. Also, I'm not sure if this matters, but I changed where the column zeroes out to after the ro=ro+co line.

[Prateek Mittal]

I am not sure whether it is needed now. I am posting here the updated version of the code for the sake of others.

function [A] = fourier1 (X)
[M,N]=size(X);
A=zeros(M,N);
ro=0;
co=0;
for u=1:M
    for v=1:N
        for m=1:M
            for n=1:N
                co=co+X(m,n)*exp(1i*(-2)*pi*(((u-1)*(m-1)/M)+((v-1)*(n-1)/N)));
            end
            ro=ro+co;
            co = 0;
        end
        A(u,v)=ro;
        ro=0;
        co=0;
    end
end

Answer 1

[KSSV]

No tested...test on your data:

function X = myFFT(x)    %only works if N = 2^k

N = numel(x);
xp = x(1:2:end);
xpp = x(2:2:end);
if N>=8
    Xp = myFFT(xp);
    Xpp = myFFT(xpp);
    X = zeros(N,1);
    Wn = exp(-1i*2*pi*((0:N/2-1)')/N);
    tmp = Wn .* Xpp;
    X = [(Xp + tmp);(Xp -tmp)];
else
    switch N
        case 2
            X = [1 1;1 -1]*x';
        case 4
            X = [1 0 1 0; 0 1 0 -1i; 1 0 -1 0;0 1 0 1i]*[1 0 1 0;1 0 -1 0;0 1 0 1;0 1 0 -1]*x';
        otherwise
            error('N not correct.');
    end
end
end