傅里叶变换(Fast Fourier Transform)实例代码
时间: 2023-06-21 21:17:34 浏览: 86
以下是一个用于计算离散傅里叶变换(DFT)的Python实例代码:
```python
import numpy as np
def dft(x):
"""计算离散傅里叶变换"""
N = len(x)
n = np.arange(N)
k = n.reshape((N, 1))
e = np.exp(-2j * np.pi * k * n / N)
return np.dot(e, x)
def fft(x):
"""计算快速傅里叶变换"""
N = len(x)
if N <= 1:
return x
even = fft(x[::2])
odd = fft(x[1::2])
factor = np.exp(-2j * np.pi * np.arange(N) / N)
return np.concatenate([even + factor[:N//2] * odd,
even + factor[N//2:] * odd])
# 测试
x = np.array([0, 1, 2, 3])
print("原始序列:", x)
print("DFT结果:", dft(x))
print("FFT结果:", fft(x))
```
代码中的`dft`函数实现了离散傅里叶变换,`fft`函数实现了快速傅里叶变换。对于长度为N的序列,DFT的时间复杂度为O(N^2),而FFT的时间复杂度为O(NlogN),因此在实际应用中,我们通常使用FFT来计算傅里叶变换。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)