蝶形运算k的取值_怎么判断k的取值范围_蝶形运算流图

在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至DFT被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散傅立叶变换才在实际的工程中得到广泛应用。蝶形运算k的取值需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。

本文不加推导地直接给出DFT的计算公式：

其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度值实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取连续的N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N截至的N个频率点的相对幅度。

根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*N^2次实数乘法，2*N*(N-1)次实数加法。

1.WN的对称性

2.WN的周期性

3.WN的可约性

根据以上这些性质，我们可以得到式(5)的一系列有用结果

假设采样序列点数为N=2^L，L为整数，如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下：

于是根据DFT计算公式(1)有：

至此，我们将一个N点的DFT转化为了式(7)的形式，此时k的取值为0到N-1,现在分为两段来讨论，当k为0～N/2-1的时候，因为x1(r)，x2(r)为N/2点的序列，因此，此时式(7)可以写为：

而当 k取值为N/2~N-1时，k用k’+N/2取代，k’取值为0~N/2-1。对式(7)化简可得：

综合以上推导我们可以得到如下结论：一个N点的DFT变换过程可以用两个N/2点的DFT变换过程来表示，其具体公式如式(10)所示DFT快速算法的迭代公式：

上式中X'(k’)为偶数项分支的离散傅立叶变换，X''(k’’)为奇数项分支的离散傅立叶变换。 式(10)的计算过程可以用图1的蝶形算法流图直观地表示出来。

图1 时间抽取法蝶形运算流图

在图1中，输入为两个N/2点的DFT输出为一个N点的DFT结果，输入输出点数一致。运用这种表示方法，8点的DFT可以用图2来表示：

图2 8点DFT的4点分解

根据公式(10)，一个N点的DFT可以由两个N/2点的DFT运算构成，再结合图1的蝶形信号流图可以得到图2的8点DFT的第一次分解。该分解可以用以下几个步骤来描述：

1.将N点的输入序列按奇偶分为2组分别为N/2点的序列

2.分别对1中的每组序列进行DFT变换得到两组点数为N/2的DFT变换值X1和X2

3.按照蝶形信号流图将2的结果组合为一个N点的DFT变换结果

根据式(10)我们可以对图2中的4点DFT进一步分解，得到图3的结果，分解步骤和前面一致。

图3 8点DFT的2点分解

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-44987-1.html