python fft 代码
时间: 2023-10-13 18:27:19 浏览: 153
fft编解码
下面是一个简单的 Python FFT 代码示例:
```python
import numpy as np
def fft(x):
# 如果 x 的长度为1,返回 x
if len(x) == 1:
return x
else:
# 将 x 分成两部分
even = fft(x[0::2])
odd = fft(x[1::2])
# 计算 DFT
n = len(x)
factor = np.exp(-2j * np.pi * np.arange(n) / n)
return np.concatenate([even + factor[:int(n/2)] * odd,
even + factor[int(n/2):] * odd])
# 示例
x = np.array([1, 2, 3, 4])
print(fft(x))
```
输出结果为:
```
[10. -0.j -2.+2.j -2. -0.j -2.-2.j]
```
其中,`fft` 函数是递归地计算 DFT 的,使用了分治法的思想。具体来说,如果输入序列的长度为 $n$,则将其分成两部分,长度都为 $n/2$,然后对这两部分分别计算 DFT,并将结果合并起来。如果输入序列的长度为 $1$,则直接返回该序列。在计算 DFT 的过程中,使用了蝴蝶运算,以实现 $O(n \log n)$ 的时间复杂度。
阅读全文