了解 radix-2 FFT 递归算法

Question

我目前正在研究 DFT 和 FFT，我们得到了这个简单的问题： 使用递归 FFT 计算此三次多项式的 DFT： -1 + 4x + 3x^2.

所以，我正在考虑这个算法：

这个递归是如何工作的？ for 循环是否位于所有递归调用的末尾？或者每次 y 回到 y^0 和 y^1？有人可以指导我吗？当然，不是所有的步骤，只是一些例子？非常感谢您！

Answer 1

本质上，递归 FFT 是从 (a0,a1,a2,...an) 开始通过 a 向后工作的。

在每个后续递归调用 Recursive-FFT 时使用 a 的子集，因此在每个新调用的 Recursive-FFT 中 a变得越来越小，直到分配给 n 的长度为 1，此时最后一次调用 Recursive-FFT returns 到前一个。

直到 n = 1 时，递归 FFT 返回给它的调用者，程序的最后一部分，即 for 循环，才被执行，此时 y 返回到先前的 Recursive-FFT，或者当堆栈中不再有来自 Recursive-FFT 的调用时返回到原始调用者（不是 Recursive-FFT 的代码）。

Answer 2

形成向量a = [-1, 4, 3, 0]，其长度为n=2=2^2。

然后（使用一张纸）完成算法的步骤：将序列拆分为 even/odd 个向量等。玩得开心（或选择其他科目进行学习）。

顺便说一句：多项式只有二阶，不是你说的三阶！？！

Answer 3

radix-2 Decimation In Frequency 算法的递归实现可以使用以下两个图来理解。第一个是指压栈阶段，而第二个是出栈阶段。

特别是，这两个图说明了以下 Matlab 实现：

% --- Radix-2 Decimation In Frequency - Iterative approach

function y = radix2_DIF_Recursive(x)

global sumCount mulCount

N = length(x);
phasor = exp(-2 * pi * 1i / N) .^ (0 : N / 2 - 1);

if N == 1
    y = x;
else
    y_top       = radix2_DIF_Recursive(x(1: 2 : (N - 1)));
    y_bottom    = radix2_DIF_Recursive(x(2 : 2 : N));
    z           = phasor .* y_bottom;
    y           = [y_top + z, y_top - z];
    sumCount    = sumCount + 6 * (N / 2);
    mulCount    = mulCount + 4 * (N / 2);
end

使用以下主脚本进行测试：

% --- Radix-2 Decimation In Frequency - Iterative approach

clear all
close all
clc

global sumCount mulCount

N = 32;

x = randn(1, N);

sumCount = 0;
mulCount = 0;

tic
xhat = radix2_DIF_Recursive(x);
timeCooleyTukey = toc;

tic
xhatcheck = fft(x);
timeFFTW = toc;

rms = 100 * sqrt(sum(sum(abs(xhat - xhatcheck).^2)) / sum(sum(abs(xhat).^2)));

fprintf('Time Cooley-Tukey = %f; \t Time FFTW = %f\n\n', timeCooleyTukey, timeFFTW);
fprintf('Theoretical multiplications count \t = %i; \t Actual multiplications count \t = %i\n', ...
         2 * N * log2(N), mulCount);
fprintf('Theoretical additions count \t\t = %i; \t Actual additions count \t\t = %i\n\n', ...
         3 * N * log2(N), sumCount);
fprintf('Root mean square with FFTW implementation = %.10e\n', rms);

上述递归实现是 radix-2 频率抽取 在 Implementation of the Discrete Fourier Transform - FFT 的迭代实现的对应物。请注意，当前的递归不需要任何反向位排序，无论是输入序列还是输出序列。

了解 radix-2 FFT 递归算法

Understanding the radix-2 FFT recursive algorithm

fft

rad

dft