信息处理 - DFT 是否产生与 FFT 相同的输出？ - 吾爱随笔录

DFT 是否产生与 FFT 相同的输出？

信息处理 matlab 傅里叶变换

2022-02-13 19:15:32

在我学习 DFT 的内容/原因/方式的过程中，我尝试在 MATLAB 上实现 DFT，然后将其输出与fft输出进行比较，然后我注意到它有所不同，DFT 会产生不同的输出fft吗？

% it creates a simple gray image (4x4)
I = [255, 255, 30, 100 
    255, 50, 90, 20 
    70, 70, 20, 10 
    100, 20, 10, 0];
% it converts it to grayscale
I = mat2gray(I);
% shows it 
imshow(I);

IDFT = [];

% DFT
N1 = 4;
N2 = 4;
e = exp(1);

for w1=1:(N1)
  for w2=1:(N2)
      % X(w1, w2)
      DFT = 0;
        for n1=1:(N1)
            for n2=1:(N2)
                Intensity = I(n1,n2);
                FirstDimension = e ^ (-1i*( (2*pi/N1) * w1 * n1));
                SecondDimension = e ^ (-1i*( (2*pi/N2) * w2 * n2));
                DFT = DFT + (Intensity * FirstDimension * SecondDimension);
            end
        end
       IDFT(w1, w2) = DFT;
  end
end

IDFT
fft(I)

3个回答

是的，但你的 DFT 实现是错误的。w1, w2,n1并且n2应该在的范围内。您还应该与 MATLAB 的函数进行比较。 $0, \ldots, N-1$ fft2

这是一个正确的实现。我已经替换w1, w2with和u, with ,以遵循约定。我做了一些代数简化。vn1n2xy

I = [255, 255, 30, 100 
    255, 50, 90, 20 
    70, 70, 20, 10 
    100, 20, 10, 0];

% it converts it to grayscale
I = mat2gray(I);

% DFT
N = size(I,1);
IDFT = 1i*zeros(N,N);
for u=0:N-1
  for v=0:N-1
      DFT = 0;
      for x=0:N-1
          for y=0:N-1
              DFT = DFT + I(x+1,y+1)*exp(-1i*2*pi*(u*x+v*y)/N);
          end
      end
      IDFT(u+1, v+1) = DFT;
    end
end

IDFT
fft2(I)

IDFT =
5.3137 + 0.0000i   2.0784 - 1.0392i   1.1961 - 0.0000i   2.0784 + 1.0392i
1.8431 - 1.1176i   0.6471 - 0.6667i  -0.3137 - 0.7255i   0.7255 + 0.0784i
1.0392 - 0.0000i   0.0784 - 0.6471i  -1.6667 - 0.0000i   0.0784 + 0.6471i
1.8431 + 1.1176i   0.7255 - 0.0784i  -0.3137 + 0.7255i   0.6471 + 0.6667i


MATLAB_fft =
5.3137 + 0.0000i   2.0784 - 1.0392i   1.1961 + 0.0000i   2.0784 + 1.0392i
1.8431 - 1.1176i   0.6471 - 0.6667i  -0.3137 - 0.7255i   0.7255 + 0.0784i
1.0392 + 0.0000i   0.0784 - 0.6471i  -1.6667 + 0.0000i   0.0784 + 0.6471i
1.8431 + 1.1176i   0.7255 - 0.0784i  -0.3137 + 0.7255i   0.6471 + 0.6667i

FFT 是一种计算 DFT（离散傅立叶变换）结果的有效算法，而 DFT 是一种离散时间变换。这符合排序的意义（比如默认为冒泡排序）是一种算法，而快速排序是一种特定的算法实现排序的有效方法，其输出将与冒泡排序相同，但由于使用了完全不同的架构，效率会更高。

复杂度的一维 DFT的直接for循环实现相比，复杂度的一维 FFT 将快得多...... $O(N \text{log}N)$ $O(N^2)$

除了算术运算中涉及的舍入和近似误差外，它们的输出将完全相同。任何差异都是编码错误的直接后果。

FFT 是一种高效的 DFT 算法，因此在无限精度算术的限制下，它们将给出相同的输出，尽管直接 DFT 实现会慢得多。

但是，DFT 算法涉及三角多项式的求和，这在数值上非常不稳定，因此通常 FFT 的舍入误差较小，因为执行的操作较少，您可以利用对称性来消除一些误差

其它你可能感兴趣的问题

上一篇带有自相关的吉他音高检测下一篇信号导数的标准差