数字信号处理第4章快速傅里叶变换(FFT)讲解.ppt
文本预览下载声明
第4章 快速傅里叶变换 ;第4章 快速傅里叶变换 ;学习目标;§4.1 引 言 ;§4.2 直接计算DFT的问题及改进的途径 ;运算量;一次复数乘法需用四次实数乘法和二次实数加法;
一次复数加法需二次实数加法。 ;二、 改进的途径;;§4.3 按时间抽取(DIT)的基 -2 FFT算法 ;k=0,1,…..,N/2-1;利用周期性求X(k)的后半部分;;N点
(N=8)
DFT;;2. 二次分解 N/2→N/4;X2(k)也可进行同样的分解: ;x(0)=x1(0); N/2点DFT分解为两个N/4点DFT ;一个N=8点DFT分解为四个N/4点DFT ;N=8,四个N/4点DFT即四个2点DFT,其输出分别为:
X3(k),X4(k),X5(k),X6(k),k=0, 1;N=8 按时间抽取的FFT运算流图;二、 按时间抽取的FFT算法与直接计算DFT运算量的比较
N=2M时,共有M级蝶形, 每级都由N/2个蝶形运算组成;
每个蝶形需要一次复乘、 二次复加;
每级运算都需N/2次复乘和N次复加;
M级运算总共需要: ;以乘法为例,直接DFT复数乘法次数是N2,FFT复数乘法次数是(N/2) log2N;
直接计算DFT与FFT算法的复数乘法计算量之比为 :;对一个连续时间信号xa(t)采样1秒得到一个4096个采样点的序列,若计算采样信号的4096点DFT。
假定仅对200≤f≤300Hz频率范围所对应的DFT采样点感兴趣。
(1)若直接用DFT,要计算这些值需要多少次复乘?
MN=101×4096=413696
(2)若用基2的DIT-FFT计算,则需要多少次复乘?
N/2log2N=4096/2log24096=24576;N点x(n)序列,构造新序列
y(n)=x(n/2),n为偶数时,
y(n)=0,n为奇数时, n=0,1,2,…2N-1,
求:Y(K)与X(K)的关系,K=0,1,2,…. 2N-1;解:由DIT-FFT可得
y(2n)= y1(n)=x(n), Y1(K)=X(K) y(2n+1)= y2(n)= 0, Y2(K)=0
n=0,1,….,N-1;已知x(n)长度为N(N为偶数)。定义两个长度为N/2的序列如下:
其中,G(k)=DFT[g(n)], H(k)=DFT[h(n)],分别为N/2长。
试利用G(k)和H(k)表示出X(k)=DFT[x(n)],k=0,1,……N-1。;三、 按时间抽取的FFT算法的特点;第一级蝶形运算;m表示第m级迭代,k, j为数据所在行数;; 某一级的两个节点k和j的节点变量进行蝶形运算后,得到结果为下一级k, j两节点的节点变量,即每个蝶形的输入、输出数据节点同在一条水平线上;
与其他节点变量无关,即蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中;
每级的N/2 个蝶形运算全部完成后,再开始下一级的蝶形运算;
这样经过M级运算后,原存放输入数据的N个存储单元中依次存放输出的N个值;
这种利用同一存储单元存放蝶形计算输入、输出数据的方法称为原位运算。可以节省存储单元,降低设备成本。 ; 2. 倒位序规律
基2的DIT-FFT的输出X(k)按正常顺序排列在存储单元中,即按X(0),X(1),…,X(7)的顺序排列;
输入x(n)却不是按自然顺序存储的,而是按x(0),x(4), …, x(7)的顺序存入存储单元,看起来好像是“混乱无序”的;
实际上是有规律的,我们称之为倒位序。 ;n用二进制数表示为(n2n1n0)2(当N=8=23时,二进制为三位)
第一次分组,n为偶数(相当于n的二进制数的最低位n0=0)在上半部分,n为奇数(相当于n的二进制数的最低位 n0=1)在下半部分。
下一次则根据次最低位n1为“0”或是“1”来分偶奇(而不管原来的子序列是偶序列还是奇序列),
如此继续分下去,直到最后N个长度为1的子序列。;倒位序; N=8时的自然顺序二进制数和相应的倒位序二进制数 ;先按自然顺序将输入序列存入存储单元, 为了得到倒位序的排列,我们通过变址运算来完成;
如果输入序列的自然顺序号I用二进制数(例如n2n1n0)表示,则其倒位序J对应的二进制数就是(n0n1n2),这样,在原来自然顺序时应该放x(I)的单元,现在倒位序后应放x(J)。;顺序数I的起始、终止值分别为1和N-2;
倒序数J的起始值为N/2;
为避免重复调换,只对IJ的情况进行交换。; 3. 蝶形运算两节点的“距离”;第一级蝶形
两节点间
“距离”为1;N=2M点DIT-FFT,其第m级运算,每个蝶形的两节点“距离”为2m-1。 ;系数WNr的变换规律:
其中N=2M,m=1
显示全部