matlab不调用库函数实现fft算法

### 手动实现快速傅里叶变换（FFT） 快速傅里叶变换（Fast Fourier Transform, FFT）是一种高效的离散傅里叶变换（Discrete Fourier Transform, DFT）算法。DFT 的定义如下： 对于长度为 \( N \) 的序列 \( x[n] \)，其 DFT 定义为： \[ X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi k n / N}, \quad k = 0, 1, ..., N-1. \] 以下是基于分治策略的手动实现 FFT 方法的 MATLAB 实现代码。 #### MATLAB 中手动实现 FFT ```matlab function X = manual_fft(x) % 获取输入信号的长度 N = length(x); % 如果输入长度为 1，则返回本身作为基情况 if N == 1 X = x; return; end % 将输入分为偶索引部分和奇索引部分 even_x = x(1:2:N); % 偶数位置元素 odd_x = x(2:2:N); % 奇数位置元素 % 对偶数部分和奇数部分分别递归调用 FFT Y_even = manual_fft(even_x); % 计算偶数部分的 FFT Y_odd = manual_fft(odd_x); % 计算奇数部分的 FFT % 初始化输出数组 X = zeros(N, 1); % 使用旋转因子 W_N^k 来组合结果 for k = 0:N-1 W_N_k = exp(-1i * 2 * pi * k / N); % 旋转因子 X(k+1) = Y_even(mod(k,N/2)+1) + W_N_k * Y_odd(mod(k,N/2)+1); end end ``` 此代码实现了标准的 Cooley-Tukey 算法，该算法通过将原始问题分解为较小子问题来减少复杂度。时间复杂度从 O\(N^2\) 减少到 O\(N log_2 N\) [^1]。 #### 测试代码 可以使用以下测试代码验证上述 `manual_fft` 函数的结果是否与 MATLAB 内置函数一致： ```matlab % 创建一个随机信号 x = randn(1, 8); % 调用手动实现的 FFT 和 MATLAB 自带的 fft 进行比较 X_manual = manual_fft(x'); X_builtin = fft(x'); % 显示两者之间的误差 disp('Error between manual and built-in FFT:'); disp(norm(X_manual - X_builtin)); ``` 如果两者的误差接近于零，则说明手动实现正确无误。 --- ### 注意事项 1. 输入信号的长度应为 2 的幂次方以简化实现过程。如果不是 2 的幂次方，可以通过补零操作将其扩展至最近的大于等于当前长度的 2 的幂次方。 2. 上述代码假设输入是一个列向量。如果是行向量，在传递给函数之前需转置为列向量。 3. 此实现仅适用于一维信号。多维 FFT 可以通过对每一维度单独应用一维 FFT 来完成 [^2]。 ---

以下是基于FFT的图像平移算法的 Matlab 代码： ```matlab function shifted_image = fft_shift(image, shift) % 输入参数：image表示输入的图像，shift表示需要平移的像素数目 % 输出参数：shifted_image表示平移后的图像 [M, N] = size(image); % 获取图像的行数和列数 x = 0:N-1; y = 0:M-1; [X, Y] = meshgrid(x, y); % 生成网格坐标矩阵 % 将网格坐标矩阵中心移到图像中心 X_centered = X - N/2; Y_centered = Y - M/2; % 计算平移后的网格坐标矩阵 X_shifted = X_centered - shift(2); Y_shifted = Y_centered - shift(1); % 利用时移性质进行平移操作 shifted_image = ifft2(fft2(image) .* exp(-1i*2*pi*(X_shifted.*X/N + Y_shifted.*Y/M))); end ``` 该函数首先获取图像的行数和列数，然后生成网格坐标矩阵，将网格坐标矩阵中心移到图像中心，计算平移后的网格坐标矩阵，最后利用时移性质进行平移操作。其中，`fft2`函数用于对图像进行二维傅里叶变换，`ifft2`函数用于对平移后的频域图像进行二维傅里叶反变换，`exp`函数用于生成平移因子，`.*`表示矩阵元素相乘，`*`表示矩阵乘法，`/`表示矩阵右除。平移因子可以理解为一个旋转因子，用于将图像中心移动到不同的位置。需要注意的是，平移因子中的负号是因为 Matlab 中的二维傅里叶变换和频域中心的定义不同。 以下是利用该函数实现图像平移的示例代码： ```matlab % 读入图像 image = imread('lena.png'); % 将图像转换为灰度图像 image = rgb2gray(image); % 显示原始图像 subplot(1, 2, 1); imshow(image); title('Original Image'); % 平移图像 shifted_image = fft_shift(image, [50, 100]); % 显示平移后的图像 subplot(1, 2, 2); imshow(shifted_image, []); title('Shifted Image'); ``` 该代码首先读入图像并转换为灰度图像，然后显示原始图像。接着调用 `fft_shift` 函数进行图像平移，平移距离为 [50, 100] 像素，最后显示平移后的图像。需要注意的是，在显示平移后的图像时，需要使用空的方括号作为第二个参数，以使 Matlab 使用默认的显示范围。