FFT算法公式和流程图
时间: 2023-11-25 15:30:04 浏览: 45
FFT(快速傅里叶变换)是一种计算傅里叶变换的高效算法,它可以将一组N个复数的离散傅里叶变换(DFT)的计算时间从O(N^2)降低到O(N log N)。下面是FFT算法的公式和流程图。
公式:
设x_n为长度为N的实数序列,其傅里叶变换为X_k,则有:
X_k = ∑_(n=0)^{N-1}x_n e^(-2πikn/N) (k=0,1,2,...,N-1)
其中e为自然常数e,其近似值为2.71828。
流程图:
1. 将长度为N的实数序列x_n按位倒序排列得到新序列x'_n。
2. 对新序列x'_n做N次DFT,每次DFT的点数为2的幂次方,从2开始逐次翻倍,直到最后一次DFT的点数为N。
3. 将得到的N个DFT结果按照原序列中的位置重新排列,得到长度为N的DFT结果X_k。
示意图:
输入序列:[x0, x1, x2, x3]
输出序列:[X0, X1, X2, X3]
1. 按位倒序排列得到新序列:[x0, x2, x1, x3]
2. 对新序列做DFT:(DFT2表示点数为2的DFT)
DFT2([x0, x2]) = [x0 + x2, x0 - x2]
DFT2([x1, x3]) = [x1 + x3, x1 - x3]
DFT4([x0, x2, x1, x3]) = [x0 + x2 + x1 + x3, x0 - x2 - x1 + x3, x0 + x2 - x1 - x3, x0 - x2 + x1 - x3]
DFT8([x0, x2, x1, x3, ..., xN-2, xN-1]) = ...
DFT16([x0, x2, x1, x3, ..., xN-2, xN-1]) = ...
DFTN([x0, x2, x1, x3, ..., xN-2, xN-1]) = ...
3. 将得到的DFT结果按照原序列中的位置重新排列:
X0 = DFTN([x0, x2, x1, x3, ..., xN-2, xN-1])[0]
X1 = DFTN([x0, x2, x1, x3, ..., xN-2, xN-1])[1]
X2 = DFTN([x0, x2, x1, x3, ..., xN-2, xN-1])[2]
X3 = DFTN([x0, x2, x1, x3, ..., xN-2, xN-1])[3]
这样就得到了输入序列的傅里叶变换结果。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)