Matlab own fft2 without loops

0
votes

I have a problem.

I have a task to write an own fft2 without using for-loops in Matlab. There is a formula for computing this task:

F(u,v) = sum (0 to M-1) {sum(o to N-1) {f(m,n)*e^(-i*2pi*(um/M + vn/N))}}

Or for better reading: http://www.directupload.net/file/d/3808/qs3r9ogz_png.htm

It is easy to do it with two for-loops but I have no idea how to do this without these loops, absolutely no idea. We get no help by the teaching personal. They don't even give a hint or a reference to a book, where we could read about it.

Now, I want to try to get help here.

2
matlabfft

2 Answers

0
votes

Are you familiar with the matrix form of DFT? have a look here: http://en.wikipedia.org/wiki/DFT_matrix

You can do something similar in order to get a matrix form for 2D DFT.
You need to transformation matrices. The first is a N-by-N DFT matrix that operates on the columns of f, as explained in the link above. Next you need another M-byM DFT matrix the operates on the rows of f. Finally, you transformed signal is given by 

F = Wm * f * Wn;

without any loops. Note that the DFT matrix can be constructed also without loop by using something like

(1:M)*((1:M)')
0
votes

Just a little correction in Thp's answer: (1:M)*((1:M)') is not the right way to create the matrix, but (1:M)'*(1:M) is the correct way.