Matlab 实现 DIT-FFT 算法：myFFT 函数代码

本文提供使用 Matlab 编写的 DIT-FFT 函数 myFFT 的代码，该函数可以对长度为 2 的幂次方的输入序列进行快速傅里叶变换。

函数代码

function X = myFFT(x)
    N = length(x);
    L = log2(N);

    % 确保输入序列长度为2的幂次方
    if N ~= 2^L
        error('输入序列长度必须为2的幂次方');
    end

    % 做位逆序重排
    x = bitrevorder(x);

    for n = 2:2:N
        for k = 0:N/2-1
            % 计算蝶形运算的下标
            index = k * N / 2 + n;
            
            % 蝶形运算
            w = exp(-1i * 2 * pi * k / N);
            t = x(index) * w;
            u = x(index - N/2);
            x(index) = u + t;
            x(index - N/2) = u - t;
        end
    end
    
    X = x;
end

使用方法

将上述代码保存为名为 myFFT.m 的文件。
在 Matlab 中调用该函数并传入输入序列 x，函数会返回 DIT-FFT 的结果。

示例用法

x = [1 2 3 4 5 6 7 8];
X = myFFT(x);
disp(X);

说明

该函数实现了 N = 2^L 点的 DIT-FFT 算法，其中 x 是输入序列，X 是 DIT-FFT 的结果。