编程实现 MATLAB 中的离散傅里叶变换 FFT 函数的部分功能

FFT_NEW

编程实现MATLAB 中的离散傅里叶变换FFT 函数的部分功能。即编写一个函数𝑌 = FFT_NEW(𝑋)
满足以下条件：

• 输入向量 X 的长度是 2𝑁，其中N 是任意自然数。你可以用 X = rand(1, 2𝑁) 产生这样的序列。（这个限制是为了降低难度）

• 输出 𝑌 要和 MATLAB 自带的函数 Y = fft(X) 一模一样，即实现离散傅里叶级数的快速计算。

• 必须采用快速傅里叶的变换蝴蝶型算法，而不是根据定义死算。

Matlab代码如下：

FFT_NEW.m

function Y = FFT_NEW(X)
    % 计算输入向量 X 的长度
    N = length(X);
    
    % 如果输入向量的长度为 1，直接返回该向量
    if N <= 1
        Y = X;
        return;
    end
    
    % 递归地计算偶数索引和奇数索引部分的 FFT
    X_even = FFT_NEW(X(1:2:end));
    X_odd = FFT_NEW(X(2:2:end));
    
    % 预计算旋转因子
    factor = exp(-2i * pi * (0:(N/2 - 1)) / N);
    
    % 使用蝶形算法合并偶数部分和奇数部分的结果
    Y = [X_even + factor .* X_odd, X_even - factor .* X_odd];
end

test_FFT.m

% 示例用法
X = rand(1, 2^3);  % 生成长度为 2^3 的随机向量
Y = FFT_NEW(X);
Y_fft = fft(X);

% 绘制原始信号
figure;
subplot(3, 1, 1);
stem(0:length(X)-1, X, 'filled');
title('原始信号');
xlabel('样本点');
ylabel('幅值');

% 绘制 FFT_NEW 结果
subplot(3, 1, 2);
stem(0:length(Y)-1, abs(Y), 'filled');
title('FFT_NEW 结果');
xlabel('频率指数');
ylabel('幅值');

% 绘制 MATLAB FFT 结果
subplot(3, 1, 3);
stem(0:length(Y_fft)-1, abs(Y_fft), 'filled');
title('MATLAB FFT 结果');
xlabel('频率指数');
ylabel('幅值');

% 显示差异
figure;
stem(0:length(Y)-1, abs(Y - Y_fft), 'filled');
title('FFT_NEW 与 MATLAB FFT 结果差异');
xlabel('频率指数');
ylabel('差值');

% 检查两者是否相等
tolerance = 1e-10;  % 设定容忍误差
difference = abs(Y - Y_fft);
if all(difference < tolerance)
    disp('两者相等');
else
    disp('两者不相等');
end

IFFT_NEW

请编程实现 MATLAB 中的离散傅里叶变换 IFFT 函数的部分功能。即编写一个函数𝑋 = IFFT_NEW(𝑌)
满足以下条件：

• 输入向量 𝑌 的长度是 2𝑁，其中 𝑁 是任意自然数。你可以用 Y = rand(1, 2𝑁) 产生这样的序列。（这个限制是为了降低难度）

• 输出 𝑋 要和 MATLAB 自带的函数 X = ifft(Y) 一模一样，即实现离散傅里叶级数反变换的快速计算。

• 需采用快速傅里叶变换的蝴蝶型算法，而不是根据定义死算。

（提示：如果编出了 FFT，这题不难，但是请注意，如果用递归编程，应该是除以 2，而不是除以 𝑁。）

Matlab代码如下：

IFFT_NEW.m

function Y = IFFT_NEW(X)
    % 计算输入向量 X 的长度
    N = length(X);
    
    % 如果输入向量的长度为 1，直接返回该向量
    if N <= 1
        Y = X;
        return;
    end
    
    % 递归地计算偶数索引和奇数索引部分的 IFFT
    X_even = IFFT_NEW(X(1:2:end));
    X_odd = IFFT_NEW(X(2:2:end));
    
    % 预计算旋转因子
    factor = exp(2i * pi * (0:(N/2 - 1)) / N);
    
    % 使用蝶形算法合并偶数部分和奇数部分的结果
    Y = [X_even + factor .* X_odd, X_even - factor .* X_odd] / 2;
end

test_IFFT.m

% 生成测试数据
N = 2^3;  % 长度为 2 的幂
X = rand(1, N) + 1i * rand(1, N);  % 生成随机复数向量

% 计算 IFFT_NEW 和 MATLAB 的 ifft
Y_ifft_new = IFFT_NEW(X);
Y_ifft = ifft(X);

% 绘制原始信号
figure;
subplot(3, 1, 1);
stem(0:N-1, real(X), 'filled');
title('原始信号 (实部)');
xlabel('样本点');
ylabel('幅值');

% 绘制 IFFT_NEW 结果
subplot(3, 1, 2);
stem(0:N-1, real(Y_ifft_new), 'filled');
title('IFFT_NEW 结果 (实部)');
xlabel('频率指数');
ylabel('幅值');

% 绘制 MATLAB IFFT 结果
subplot(3, 1, 3);
stem(0:N-1, real(Y_ifft), 'filled');
title('MATLAB IFFT 结果 (实部)');
xlabel('频率指数');
ylabel('幅值');

% 绘制结果差异
figure;
stem(0:N-1, abs(Y_ifft_new - Y_ifft), 'filled');
title('IFFT_NEW 与 MATLAB IFFT 结果差异 (实部)');
xlabel('频率指数');
ylabel('差值');

% 检查两者是否相等
tolerance = 1e-10;  % 设定容忍误差
difference = abs(Y_ifft_new - Y_ifft);
if all(difference < tolerance)
    disp('两者相等');
else
    disp('两者不相等');
end