OK, you've got a few errors that we need to fix... if you want this to work exactly like how fft2
works in MATLAB.
Error #1 - Wrong normalization factor
fft
and ultimately fft2
have no normalization factors when computing the transform. You can get rid of that division statement when computing the first part of the DFT matrix. Also, the first part of the DFT matrix, in the exponent, you need to divide by the total length of the signal, not the length subtracted by 1.
Error #2 - Power operation for completing the last part of the DFT matrix is wrong
You calculate a meshgrid
from 1 to l
, but the power operations require that you start from 0
. Therefore, you need to subtract u
and x
by 1 before you do the power calculation.
Error #3 - Application of FFT to rows and columns
As you have already noted, the 2D FFT is separable and can be done by performing the 1D FFT on the rows first, followed by the columns. The operation that you're doing unfortunately isn't correct. post_dft
needs to be transposed as you want to apply the resulting intermediate operations over the columns.
As such, with all of the fixes I mentioned above, your corrected code is:
function res=myDFT(signal)
signal=double(signal);
l=size(signal,1);
x=[1:l];
[x, u]=meshgrid(x,x);
%// Error #1
pre_dft=exp(1i*(-2*pi)./l); %// Change
%// Error #2
pre_dft=(pre_dft.^((u-1).*(x-1))); %// Change
%// Error #3
post_dft = pre_dft.'; %// Change
res = pre_dft*signal*post_dft;
end
Testing the above with some random data, and comparing with fft2
:
rng(123123);
in = rand(7);
out1 = myDFT(in);
out2 = fft2(in);
out1
contains the corrected custom implementation while out2
contains the result of MATLAB's fft2
algorithm. We get:
>> out1
out1 =
Columns 1 through 4
26.2182 + 0.0000i -1.3805 + 1.0956i 2.2881 - 0.4435i -0.8005 + 1.5133i
-1.3067 + 0.3236i -0.5703 - 1.3884i -0.7127 + 0.1303i 3.2689 - 0.5995i
-0.6136 - 2.0731i -0.2776 + 1.2926i 0.1587 - 1.4504i -0.5305 + 1.4018i
-3.0703 + 0.3715i -1.5094 - 0.0216i 0.2573 - 3.2934i -1.1100 + 1.4180i
-3.0703 - 0.3715i -0.9940 + 0.1328i 1.7269 + 0.2915i 0.2814 + 2.2212i
-0.6136 + 2.0731i 1.8351 + 1.0629i 1.2891 + 1.7418i 0.4402 + 1.8756i
-1.3067 - 0.3236i -0.4974 - 0.9678i -2.2419 + 2.0839i -1.6844 + 0.9781i
Columns 5 through 7
-0.8005 - 1.5133i 2.2881 + 0.4435i -1.3805 - 1.0956i
-1.6844 - 0.9781i -2.2419 - 2.0839i -0.4974 + 0.9678i
0.4402 - 1.8756i 1.2891 - 1.7418i 1.8351 - 1.0629i
0.2814 - 2.2212i 1.7269 - 0.2915i -0.9940 - 0.1328i
-1.1100 - 1.4180i 0.2573 + 3.2934i -1.5094 + 0.0216i
-0.5305 - 1.4018i 0.1587 + 1.4504i -0.2776 - 1.2926i
3.2689 + 0.5995i -0.7127 - 0.1303i -0.5703 + 1.3884i
>> out2
out2 =
Columns 1 through 4
26.2182 + 0.0000i -1.3805 + 1.0956i 2.2881 - 0.4435i -0.8005 + 1.5133i
-1.3067 + 0.3236i -0.5703 - 1.3884i -0.7127 + 0.1303i 3.2689 - 0.5995i
-0.6136 - 2.0731i -0.2776 + 1.2926i 0.1587 - 1.4504i -0.5305 + 1.4018i
-3.0703 + 0.3715i -1.5094 - 0.0216i 0.2573 - 3.2934i -1.1100 + 1.4180i
-3.0703 - 0.3715i -0.9940 + 0.1328i 1.7269 + 0.2915i 0.2814 + 2.2212i
-0.6136 + 2.0731i 1.8351 + 1.0629i 1.2891 + 1.7418i 0.4402 + 1.8756i
-1.3067 - 0.3236i -0.4974 - 0.9678i -2.2419 + 2.0839i -1.6844 + 0.9781i
Columns 5 through 7
-0.8005 - 1.5133i 2.2881 + 0.4435i -1.3805 - 1.0956i
-1.6844 - 0.9781i -2.2419 - 2.0839i -0.4974 + 0.9678i
0.4402 - 1.8756i 1.2891 - 1.7418i 1.8351 - 1.0629i
0.2814 - 2.2212i 1.7269 - 0.2915i -0.9940 - 0.1328i
-1.1100 - 1.4180i 0.2573 + 3.2934i -1.5094 + 0.0216i
-0.5305 - 1.4018i 0.1587 + 1.4504i -0.2776 - 1.2926i
3.2689 + 0.5995i -0.7127 - 0.1303i -0.5703 + 1.3884i
Looks fine to me!
dftmtx
from the Signal Processing Toolbox might help debug your code. – A. Donda