信息处理 - 为什么这种递归 DFT 算法不等同于这种迭代方法？ - 吾爱随笔录

编辑 1/30 - 考虑到 @Fat32 的编辑，频率轴的比例似乎仍然存在问题。虽然版本 2 正确识别了 1 HZ 的响应，但版本 1 似乎覆盖了 1/T 的频率范围。

我希望版本 1 覆盖与版本 2 相同的频率范围。有人可以帮忙吗？

（结束编辑 1/30）

我有 2 个 DFT 算法，我希望它们返回相同的频率响应。不幸的是，更有效的递归算法似乎并没有像预期的那样表现。

版本 1 - 高效的分治法，但输出不正确：

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

版本 2 - 效率低，但产生预期结果：

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

我希望这两种算法都能返回相同的结果。然而，情况似乎并非如此。

您可以看到底部图（版本 2）显示了对 1 HZ 信号的正确频率响应，但中间图（版本 1）没有：

运行两者的代码：

       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');