MATLAB:找到离散傅立叶变换的更快方法

Question

我正试图在matlab中编写一段代码，该代码与内置fft函数基本相同。因此，计算任何给定输入向量的离散傅立叶变换。

转换由给出

%                    N
%      X(k) =       sum  x(n)*exp(-j*2*pi*(k-1)*(n-1)/N), 1 <= k <= N.
%                   n=1

现在我创建了自己的代码来实现这一点，但当我查看计算时间时，计算工作量大约是200倍。显然，我想减少这种情况。

下面是我代码的计算部分，其中y是输出向量。

N=length(input_vector)
for k = 1:N
y(k)=0;
for n = 1:N
term = input_vector(n)*exp(-2*pi*1i*(n-1)*(k-1)/N);
y(k)=y(k)+term;
end
end

现在我认为计算量很大，因为for循环和带有y(k)=y(k)+term的行，因为这在所有迭代中都会发生。我认为我应该能够通过使用向量/矩阵表示法或使用带有伪变量的函数来缩小它，然后迭代这些函数。但我不知道如何开始这个过程。

如有任何帮助或建议，我们将不胜感激。

Answer 1

使用隐式展开可以大大减少算法的计算时间：

% Vector length
N = length(input_vector);
% Vectorized DFT algorithm
y = sum(input_vector.*exp(-2*pi*1i*[0:N-1].'*[0:N-1]/N),2);

然而，有两个缺点：

1. 矢量化将消耗大量内存(因为矢量N*N必须创建(
2. 它不会比内置功能更快