尝试对长度为 2 的幂的向量实施快速傅立叶变换

Question

如果正确完成，它应该有运行时间 O(n log n)。

function d = ffTU(f)

n = [size(f)](1);

if n==1
  d = f;
  return;

else

  even=ffTU(f(2:2:end,:));
  odd =ffTU(f(1:2:end,:));

  for k=0:(n/2)-1
    T(k+1)= exp(-2i*pi*k/n)*odd(k+1);

  end

  for k=0:(n/2)-1
    d(k+1) = even(k+1) + T(k+1) + even(k+1) - T(k+1);
  end

end

我不断收到这些错误：

error: ffTU: A(I): index out of bounds; value 2 out of bound 1
error: called from
    ffTU at line 16 column 11

我知道我必须调整函数的索引，但我想我已经解决了。

Answer 1

在循环之前预分配T：

T = zeros(n/2,1);

或者更好的是，不用循环计算它：

k = (0:(n/2)-1).';
T = exp(-2i*pi*k/n).*odd(:);

您应该为 d 做类似的事情。

您还需要测试输入是否为偶数大小。

而不是

n = [size(f)](1);

做

n = size(f,1);

但是，如果您的输入不是列向量，则情况会变糟。用

修复它

f = f(:);
n = size(f,1);

并且您计算 d 时出现错误，因为您将其设置为 2*even，未使用 T（如 T-T==0.

尝试对长度为 2 的幂的向量实施快速傅立叶变换

Trying to implement Fast Fourier transform for vectors of length power of 2

fft

octave