文档介绍：第四章习题讲解
,每次复加,用它来计算512点的,问直接计算需要多少时间,用运算需要多少时间。
解:
(1)直接利用计算:
复乘次数为,复加次数为。
复乘所需时间
复加所需时间
所以直接利用DFT 计算所需时间:
复乘所需时间
复加所需时间
所以用 FFT 计算所需时间
(2) 利用计算:
复乘次数为,复加次数为。
, 是两个N点实序列, 的值,今需要从, 求, 的值,为了提高运算效率,试用一个N点运算一次完成。
例:设x1(n)和x2(n)都是N点的实数序列,试用一次N点DFT运算来计算它们各自的DFT:
解:
由题意
构造序列
对作一次N点IFFT可得序列
又根据DFT的线性性质
而, 都是实序列
3. N=16 时,画出基-2 按时间抽取法及按频率抽取法的 FFT 流图(时间抽取采用输入倒位序,输出自然数顺序,频率抽取采用输入自然顺序,输出倒位序)。
解:
自然序倒位序
0 0000 0000 0
0001 1000 8
0010 0100 4
0011 1100 12
0100 0010 2
0101 1010 10
0110 0110 6
0111 1110 14
自然序倒位序
8 1000 0001 1
9 1001 1001 9
10 1010 0101 5
11 1011 1101 13
12 1100 0011 3
13 1101 1011 11
14 1110 0111 7
15 1111 1111 15
(1) 按时间抽取的基-2FFT流图
共有L = 4级蝶形运算,每级N / 2 = 8个蝶形运算
每个蝶形的两节点距离为,即从第一级到第四级两节点距离分别为1,2,4,8。
-1