手写fft算法，和内置fft算法对比

好的，下面我将提供一个完整的Python示例，包括手写FFT算法（快速傅里叶变换）和使用NumPy的内置FFT算法，然后对比两者的结果并绘制图形。

1. 手写FFT算法

我们将实现一个简单的FFT算法，即Cooley-Tukey算法，这是一种最常用的FFT算法。

2. NumPy内置FFT算法

NumPy库提供了一个非常高效的FFT实现，我们可以直接使用它来计算FFT。

3. 代码实现

首先，确保你已经安装了NumPy和matplotlib库。如果没有安装，可以通过以下命令安装：

pip install numpy matplotlib

下面是完整的Python代码：

import numpy as np
import matplotlib.pyplot as plt

def fft_handwritten(x):
    N = len(x)
    if N <= 1: return x
    even = fft_handwritten(x[0::2])
    odd = fft_handwritten(x[1::2])
    T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(len(odd))]
    return [even[k] + T[k] for k in range(len(even))] + [even[k] - T[k] for k in range(len(even))]

# 生成测试信号
t = np.linspace(0, 1, 1024, False)
x = np.sin(2 * np.pi * 10 * t) + 0.5 * np.sin(2 * np.pi * 20 * t)

# 使用NumPy的FFT
fft_np = np.fft.fft(x)

# 手写FFT
fft_hand = fft_handwritten(x)

# 绘制结果
plt.figure(figsize=(14, 6))

# 绘制NumPy的FFT结果
plt.subplot(1, 2, 1)
plt.stem(np.abs(fft_np), linefmt='C0-', markerfmt='C0o', basefmt='C3-')
plt.title('NumPy FFT')
plt.xlabel('Frequency Bins')
plt.ylabel('Amplitude')

# 绘制手写FFT结果
plt.subplot(1, 2, 2)
plt.stem(np.abs(fft_hand), linefmt='C1-', markerfmt='C1o', basefmt='C3-')
plt.title('Handwritten FFT')
plt.xlabel('Frequency Bins')
plt.ylabel('Amplitude')

plt.tight_layout()
plt.show()

4. 代码解释

• fft_handwritten 函数实现了一个递归的FFT算法。
• 我们生成了一个包含两个正弦波的测试信号。
• 使用NumPy的FFT函数和手写的FFT函数计算FFT，并绘制结果的幅度。

5. 结果对比

运行上述代码，你将看到两个图：一个显示NumPy FFT的结果，另一个显示手写FFT的结果。理论上，如果手写FFT算法实现正确，两者的结果应该非常接近。然而，由于浮点数精度和算法优化的差异，可能会有轻微的差异。

这个示例提供了一个基本的框架，你可以根据需要调整和扩展，例如处理更大的数据集或更复杂的信号。