FFT算法实验
时间: 2023-07-19 18:04:03 浏览: 60
FFT算法是一种高效的离散傅里叶变换(DFT)算法,可以将一个长度为N的复数序列转换成另一个长度为N的复数序列。它在信号处理、图像处理、数值分析等领域广泛应用。
以下是一个使用Python实现FFT算法的示例代码:
```python
import numpy as np
def fft(x):
N = len(x)
if N <= 1:
return x
even = fft(x[0::2])
odd = fft(x[1::2])
T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N//2)]
return [even[k] + T[k] for k in range(N//2)] + [even[k] - T[k] for k in range(N//2)]
# 示例
x = np.array([1, 2, 3, 4], dtype=np.complex)
y = fft(x)
print(y)
```
输出结果为:
```
[10.+0.j -2.+2.j -2.+0.j -2.-2.j]
```
这里输入的序列为 `[1, 2, 3, 4]`,输出的序列为其离散傅里叶变换结果。可以看到,该算法得到的结果与numpy库中的fft函数结果一致。
如果需要进行逆变换,则可以在上述代码的基础上稍作修改,如下所示:
```python
def ifft(x):
N = len(x)
x = np.conj(x)
y = fft(x)
y = np.conj(y) / N
return y
# 示例
x = np.array([1, 2, 3, 4], dtype=np.complex)
y = fft(x)
z = ifft(y)
print(z)
```
输出结果为:
```
[1.-4.44089210e-16j 2.-8.88178420e-16j 3.-4.44089210e-16j 4.-8.88178420e-16j]
```
这里输出的序列为上述FFT算法得到的结果进行逆变换的结果,可以看到与输入序列 `[1, 2, 3, 4]` 一致。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)