Edit 1/30 - Taking @Fat32's edits into account, it seems like there is still an issue with the scale of the frequency axis. While version 2 correctly identifies the response at 1 HZ, version 1 seems to be covering a frequency range of 1/T.
I'd like version 1 to cover the same range of frequencies as version 2. Can anyone help with this?
(End edit 1/30)
I have 2 DFT algorithms that I would expect to return same frequency response. Unfortunately, the more efficient recursive algorithm does not seem to behave as expected.
Version 1 - Efficient Divide and Conquer method, but output is incorrect:
function [ s ] = DFT_ver_1( x ) N = length(x); if N == 1 s = x(1); return; else X1 = DFT_ver_1(x(1:2:N)); X2 = DFT_ver_1(x(2:2:N)); s = zeros(N,1); for k = 1:(N/2) W(k) = exp(-1j*2*pi*(k + 1)/N); s(k) = X1(k) + W(k) * X2(k); s(k+N/2) = X1(k) - W(k) * X2(k); end
Version 2 - Inefficient, but generates expected results:
function [ s ] = DFT_ver_2( x , f, n) N = length(x); b = zeros(N,N); b_1 = -2*pi*(f/N); for idx = 1 : N for jdx = 1 : N b(jdx, idx) = b_1(idx) * n(jdx); end end anlyz_fn = cos(b) + 1i * sin(b); s = single(zeros(N,1)); for k = 1 : N val = 2 * sum(anlyz_fn(k,:) * x.'); s(k) = val; end end
I would expect both algorithms to return the same result. However, this does not appear to be the case.
You can see that the bottom plot (version 2) shows the correct frequency response to a 1 HZ signal, but the middle (version 1) does not:
Code to run both:
T = single(3.20); % (sec) time window dt = single(0.05); % (sec) sample time N = T / dt; % (ct) num samples n = 0 : N - 1; % (ct) bucket index vector t = 0 : dt : T - dt; % (sec) time vector smpl_freq = 1 / dt; % (Hz) sampling frequency freq_res = smpl_freq / N; % (Hz) frequency resolution f = n * freq_res; % (Hz) freq. bucket vector x_t = sin( 2*pi*t ); subplot(3,1,1); plot(t, x_t); xlabel('Sample Time (sec)'); ylabel('Magnitude'); subplot(3,1,2); s_v1 = DFT_ver_1( x_t); %, f, n ); s_v1_mag = abs( s_v1(1:N/2) )/N; stem(f(1:N/2)/T, s_v1_mag); xlabel('Freq. Response (Hz) v1'); ylabel('Magnitude'); s_v2 = DFT_ver_2( x_t , f, n ); s_v2_mag = abs( s_v2(1:N/2) )/N; subplot(3,1,3); stem(f(1:N/2) / T , s_v2_mag); xlabel('Freq. Response (Hz) v2'); ylabel('Magnitude');