1159271856 本篇文章给大家谈谈fft算法，以及fft算法有什么用对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
fft可分解多少级
2的n-1次方级。
FFT算法的实质是把一长序列的DFT计算分割为较短序列的DFT计算，对于基2算法而言，是把序列每次一分为二，最后分割成两点DFT，也可以采用别的分割法，每次一分为三，四，五等，就得到了基3，基4，基5等算法，其中基4算法由于具备某些优点，应用价值较大。
快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT；快速傅里叶变换是1965年由J.W库利和T.W.图基提出的，采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
实序列的FFT算法
在以上讨论FFT算法中，均假定序列x(l)为复的，但实际问题中的序列大多为实的。当然，我们可以把实序列处理成虚部为零的复序列。因此，就要引进许多零参加运算。这样一来，在机器运算时间和存储单元方面都将造成很大的浪费。在本段中，我们介绍对实序列x(l)应用FFT算法的一个有效方法。
1.同时计算两个实序列的FFT算法
设有N=4的两个实序列x1(l)与x2(l)。为了求得它们的谱X1(m)与X2(m)，我们用此二实序列构造成如下复序列
物探数字信号分析与处理技术
利用上一段的方法，可以求得复序列x(l)的谱X(m)。根据(7-3-1)得到
物探数字信号分析与处理技术
上式中的m用N-m代替，则得
物探数字信号分析与处理技术
将上式两端取共轭，根据对称性有
物探数字信号分析与处理技术
根据DFT的复共轭性质，对于实序列x1(l)与x2(l)，有
物探数字信号分析与处理技术
于是从(7-3-4)得到
物探数字信号分析与处理技术
联立求解(7-3-2)和(7-3-6)便得到
物探数字信号分析与处理技术
例如设有两个N=4点的实序列，
物探数字信号分析与处理技术
我们用它们构造一个N=4点的复序列
物探数字信号分析与处理技术
利用FFT算法求X(m)，m=0，1，2，3(图7-3-1)，
图7-3-1 N=4点的FFT算法流程图
于是得到
物探数字信号分析与处理技术
因此从式(7-3-7)得到
物探数字信号分析与处理技术
物探数字信号分析与处理技术
2.实序列的FFT算法
设有N点的实序列x(l)，l=0，1，2，…，N-1。按照点的奇偶编号，将它们分成N/2个点的两个子序列
物探数字信号分析与处理技术
设x1(l)的谱与x2(l)的谱分别为X1(m)与X2(m)
物探数字信号分析与处理技术
其中
于是可以将实序列x(l)的谱X(m)，用两个子序列x1(l)，x2(l)的谱X1(m)，X2(m)来表示
物探数字信号分析与处理技术
其中
物探数字信号分析与处理技术
注意，x1(l)，x2(l)与X1(m)，X2(m)均以N/2为周期，
利用x1(l)、x2(l)构成如下复序列
物探数字信号分析与处理技术
利用FFT算法可以求得复序列 的谱 。根据(7-3-7)就求得两个实子序列的谱X1(m)与X2(m)
物探数字信号分析与处理技术
有了X1(m)，X2(m)，根据(7-3-10)就可求得X(m)。以上就是用FFT算法求实序列x(l)的谱X(m)的方法。必须指出，用公式(7-3-10)求X(m)时，第一，两个实子序列的谱X1(m)，X2(m)及复序列x珓(l)的谱珘X(m)均是以N/2为周期的周期序列;第二，由于x
(l)是实序列，根据DFT的复共轭性质有X(m)=X*(N-m)，m=0，1，…，N/2，故只需求得前(N/2)+1个点的X(m)，就得到全部N个点的X(m)了
例如，有N=8点的实序列，
物探数字信号分析与处理技术
首先，按点的奇偶编号分成两个实子序列，
物探数字信号分析与处理技术
其次用它们构造如下复序列，
物探数字信号分析与处理技术
用FFT算法求此复序列的谱 (图7-3-2)
图7-3-2 N=4点的FFT算法流程图
于是得到:
根据周期性，有
物探数字信号分析与处理技术
根据(7-3-12)式，
物探数字信号分析与处理技术
根据周期性，有
物探数字信号分析与处理技术
故最终由(7-3-10)得到
物探数字信号分析与处理技术
FFT算法分几种？
FFT算法分析FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。 网上有帮助文档: (右上角有点击下载)
发表评论