第四章习题讲解
1.如果一台通用计算机的速度为平均每次复乘,
每次复加,用它来计算 512点的,问直接计算需要多少时间，用 运算需要多少时间。
5 s?
0.5 sD F T x n
FFT
解,(1)直接利用 计算：
复乘次数为,复加次数为 。
DFT
2N1NN?
复乘所需时间
6 2 6 21 5 1 0 5 1 0 5 1 2 1,3 1 0 7 2T N s
复加所需时间
6
2
6
0,5 1 0 1
0,5 1 0 5 1 2 5 1 2 1 0,1 3 0 8 1 6
T N N
s
所以直接利用 DFT 计算所需时间：
12 1,4 4 1 5 3 6T T T s
复乘所需时间
6
12
6
2
5 10 l o g
2
512
5 10 l o g 512 0.01152
2
N
TN
s
6
22
6
2
0,5 10 l o g
0,5 10 51 2 l o g 51 2 0,00 23 04
T N N
s
复加所需时间所以用 FFT 计算所需时间
12 0,0 1 3 8 2 4T T T s
(2) 利用 计算：
复乘次数为,复加次数为 。
FFT
2log2
N N
2logNN
2.已知,是两个 N点实序列,的值，今需要从,求,的值，为了提高运算效率，试用一个 N点 运算一次完成。
XkYkxnyn DFT
XkYkxnyn
IFFT
例：设 x1(n)和 x2(n)都是 N点的实数序列，试用一次 N点 DFT运算来计算它们各自的 DFT,
11[ ( ) ] ( )D F T x n X k? 22[ ( ) ] ( )D F T x n X k?
解：利用两序列构成一个复序列
12( ) ( ) ( )w n x n j x n
12( ) [ ( )] [ ( ) ( )]W k D F T w n D F T x n j x n
则
12[ ( )] [ ( )]D F T x n j D F T x n
12( ) ( )X k j X k
R e [ ( ) ] ( )epw n W k
I m [ ( ) ] ( )opj w n W k
1 ( ) R e [ ( ) ]x n w n?由得
11( ) [ ( ) ] { R e [ ( ) ] } ( )epX k D F T x n D F T w n W k
*1 [ (( )) (( )) ] ( )
2 N N NW k W N k R k
2 ( ) I m [ ( ) ]x n w n?由得
22
1( ) [ ( )] { I m [ ( )] } ( )
opX k D F T x n D F T w n W kj
*1 [ (( )) (( )) ] ( )
2 N N NW k W N k R kj
解,由题意X k D F T x n Y k D F T y n，
构造序列Z k X k j Y k
对 作一次 N点 IFFT可得序列Zkzn
又根据 DFT的线性性质
ID F T X k j ID F T Y k
而,都是实序列xnyn
Re
Im
x n z n
y n z n
()z n ID F T Z k
()z n IDF T Z k IDF T X k j Y k
x n j y n
3,N=16 时，画出基 -2 按时间抽取法及按频率抽取法的 FFT 流图（时间抽取采用输入倒位序，输出自然数顺序，频率抽取采用输入自然顺序，输出倒位序）。
解：
自然序 倒位序
0 0000 0000 0
1 0001 1000 8
2 0010 0100 4
3 0011 1100 12
4 0100 0010 2
5 0101 1010 10
6 0110 0110 6
7 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流图
1 6 2,4LNL
共有 L = 4级蝶形运算，每级 N / 2 = 8个蝶形运算每个蝶形的两节点距离为,即从第一级到第四级两节点距离分别为 1,2,4,8。
12m?
-
2( ) 2
r L m
NW r k
k L m
系数 的确定：
即 的二进制左移 位补零
rNW
1 ()mXk?
1 ()mXj?
()mXk
()mXj-1
(2) 按频率抽取的基 -2FFT流图基本蝶形是 DIT 蝶形的转置同样共有 L = 4级蝶形运算，每级 N / 2 = 8个蝶形运算每个蝶形的两节点距离为,即从第一级到第四级两节点距离分别为 8,4,2,1。
2Lm?
1
2( ) 2
1
rm
NW r k
km
系数 的确定：
即 的二进制左移 位补零
rNW
1 ()mXk?
1 ()mXj?
()mXk
()mXj-1
1 j若不计乘 及乘 的运算量则实际乘法次数为10次复数乘法
2
16
DF T 256
( - 1 ) 240
N
N
NN
直接计算 需要 次复数乘法次复数加法
2
2
F F T l o g 3 2
2
l o g 6 4
N N
NN
利用 计算需要 次复数乘法次复数加法
9,在下列说法中选择正确的结论。线性调频 z 变换
(CZT) 可以用来计算一个 M点有限长序列 在 z 平面的实轴上各 点的 z 变换,使
hn
kzHz
(1),α 为实数,α≠± 1。,0,1,1kkz a k N
(2),α 为实数,α≠0 。,,1,1kz a k k N
(3) (1)和 (2)两者都行。
(4) (1)和 (2)两者都不行。即线性调频 z 变换不能计算
H (z) 在 z 为实数时的抽样。
1
0
N
n
kk
n
H z h n z
其中抽样点须满足：
0000,0,1,1jkkkkz A W A W e k N
，,,为任意实数。0A 0W 0? 0?
对于说法（ 1），只需取
，,,0 1A? 10Wa 0 0 0 0
( ),
k
k
C Z T z z
Hz
解,用于计算 平面上一段螺线作等分角的抽样点 上的复频谱
1
0 10
0,1,..,,1 C Z T ( )
k
k
k
za
za
k N H z
即起点为,初始相角和角度差均为,为螺线的伸缩率，就形成了实轴上各抽样点,
。因此可以用 算法来计算所以说法 (1)是正确的
00(2),,
()
k
kk
z ak A W
z
z z H z
对于说法 则 无法通过选择合适的 和,
使之成为 平面上一段螺线作等分角后的一组抽样点。
因此不能用CZ T算 法来计算各 点的 变换 。
13,我们希望利用一个单位抽样响应点数 N = 50 的有限冲激响应滤波器来过滤一串很长的数据。要求利用重叠保留法通过快速傅里叶变换来实现这种滤波器，
为了做到这一点，则：
（ 1）输入各段必须重叠 P个抽样点；
（ 2）我们必须从每一段产生的输出中取出 Q个抽样点，使这些从每一段得到的抽样连接在一起时，得到的序列就是所要求的滤波输出。假设输入的各段长度为 100个抽样点，而离散傅里叶变换的长度为 128点。
进一步假设，圆周卷积的输出序列标号是从 n = 0到
n = 127，则
（ a）求 P； （ b）求 Q；
（ c）求取出来的 Q个点的起点和终点的标号，即确定从圆周卷积的 128点中要取出哪些点，去和前一段的点衔接起来。
解,（ a）由于用重叠保留法，如果冲激响应hn 的点数为
N点，则圆周卷积结果的前面的 1N? 个点不代表线性卷积结果，故每段重叠点数 P为
1 5 0 1 4 9PN
（ b）每段点数为 72 128?,但其中只有 100个点是有效输入数据，其余 28个点为补充的零值点。因而各段不重叠而又有效的点数 Q为
100 100 49 51QP
（ c）每段 128个数据点中，取出来的 Q个点的序号从
49n? 到 99n? 。用这些点和前后段取出的相应点连接起来，即可得到原来的长输入序列。
另外，对于第一段数据没有前一段，故在数据之前必须加上 1 4 9PN个零值点，以免丢失数据。
1.如果一台通用计算机的速度为平均每次复乘,
每次复加,用它来计算 512点的,问直接计算需要多少时间，用 运算需要多少时间。
5 s?
0.5 sD F T x n
FFT
解,(1)直接利用 计算：
复乘次数为,复加次数为 。
DFT
2N1NN?
复乘所需时间
6 2 6 21 5 1 0 5 1 0 5 1 2 1,3 1 0 7 2T N s
复加所需时间
6
2
6
0,5 1 0 1
0,5 1 0 5 1 2 5 1 2 1 0,1 3 0 8 1 6
T N N
s
所以直接利用 DFT 计算所需时间：
12 1,4 4 1 5 3 6T T T s
复乘所需时间
6
12
6
2
5 10 l o g
2
512
5 10 l o g 512 0.01152
2
N
TN
s
6
22
6
2
0,5 10 l o g
0,5 10 51 2 l o g 51 2 0,00 23 04
T N N
s
复加所需时间所以用 FFT 计算所需时间
12 0,0 1 3 8 2 4T T T s
(2) 利用 计算：
复乘次数为,复加次数为 。
FFT
2log2
N N
2logNN
2.已知,是两个 N点实序列,的值，今需要从,求,的值，为了提高运算效率，试用一个 N点 运算一次完成。
XkYkxnyn DFT
XkYkxnyn
IFFT
例：设 x1(n)和 x2(n)都是 N点的实数序列，试用一次 N点 DFT运算来计算它们各自的 DFT,
11[ ( ) ] ( )D F T x n X k? 22[ ( ) ] ( )D F T x n X k?
解：利用两序列构成一个复序列
12( ) ( ) ( )w n x n j x n
12( ) [ ( )] [ ( ) ( )]W k D F T w n D F T x n j x n
则
12[ ( )] [ ( )]D F T x n j D F T x n
12( ) ( )X k j X k
R e [ ( ) ] ( )epw n W k
I m [ ( ) ] ( )opj w n W k
1 ( ) R e [ ( ) ]x n w n?由得
11( ) [ ( ) ] { R e [ ( ) ] } ( )epX k D F T x n D F T w n W k
*1 [ (( )) (( )) ] ( )
2 N N NW k W N k R k
2 ( ) I m [ ( ) ]x n w n?由得
22
1( ) [ ( )] { I m [ ( )] } ( )
opX k D F T x n D F T w n W kj
*1 [ (( )) (( )) ] ( )
2 N N NW k W N k R kj
解,由题意X k D F T x n Y k D F T y n，
构造序列Z k X k j Y k
对 作一次 N点 IFFT可得序列Zkzn
又根据 DFT的线性性质
ID F T X k j ID F T Y k
而,都是实序列xnyn
Re
Im
x n z n
y n z n
()z n ID F T Z k
()z n IDF T Z k IDF T X k j Y k
x n j y n
3,N=16 时，画出基 -2 按时间抽取法及按频率抽取法的 FFT 流图（时间抽取采用输入倒位序，输出自然数顺序，频率抽取采用输入自然顺序，输出倒位序）。
解：
自然序 倒位序
0 0000 0000 0
1 0001 1000 8
2 0010 0100 4
3 0011 1100 12
4 0100 0010 2
5 0101 1010 10
6 0110 0110 6
7 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流图
1 6 2,4LNL
共有 L = 4级蝶形运算，每级 N / 2 = 8个蝶形运算每个蝶形的两节点距离为,即从第一级到第四级两节点距离分别为 1,2,4,8。
12m?
-
2( ) 2
r L m
NW r k
k L m
系数 的确定：
即 的二进制左移 位补零
rNW
1 ()mXk?
1 ()mXj?
()mXk
()mXj-1
(2) 按频率抽取的基 -2FFT流图基本蝶形是 DIT 蝶形的转置同样共有 L = 4级蝶形运算，每级 N / 2 = 8个蝶形运算每个蝶形的两节点距离为,即从第一级到第四级两节点距离分别为 8,4,2,1。
2Lm?
1
2( ) 2
1
rm
NW r k
km
系数 的确定：
即 的二进制左移 位补零
rNW
1 ()mXk?
1 ()mXj?
()mXk
()mXj-1
1 j若不计乘 及乘 的运算量则实际乘法次数为10次复数乘法
2
16
DF T 256
( - 1 ) 240
N
N
NN
直接计算 需要 次复数乘法次复数加法
2
2
F F T l o g 3 2
2
l o g 6 4
N N
NN
利用 计算需要 次复数乘法次复数加法
9,在下列说法中选择正确的结论。线性调频 z 变换
(CZT) 可以用来计算一个 M点有限长序列 在 z 平面的实轴上各 点的 z 变换,使
hn
kzHz
(1),α 为实数,α≠± 1。,0,1,1kkz a k N
(2),α 为实数,α≠0 。,,1,1kz a k k N
(3) (1)和 (2)两者都行。
(4) (1)和 (2)两者都不行。即线性调频 z 变换不能计算
H (z) 在 z 为实数时的抽样。
1
0
N
n
kk
n
H z h n z
其中抽样点须满足：
0000,0,1,1jkkkkz A W A W e k N
，,,为任意实数。0A 0W 0? 0?
对于说法（ 1），只需取
，,,0 1A? 10Wa 0 0 0 0
( ),
k
k
C Z T z z
Hz
解,用于计算 平面上一段螺线作等分角的抽样点 上的复频谱
1
0 10
0,1,..,,1 C Z T ( )
k
k
k
za
za
k N H z
即起点为,初始相角和角度差均为,为螺线的伸缩率，就形成了实轴上各抽样点,
。因此可以用 算法来计算所以说法 (1)是正确的
00(2),,
()
k
kk
z ak A W
z
z z H z
对于说法 则 无法通过选择合适的 和,
使之成为 平面上一段螺线作等分角后的一组抽样点。
因此不能用CZ T算 法来计算各 点的 变换 。
13,我们希望利用一个单位抽样响应点数 N = 50 的有限冲激响应滤波器来过滤一串很长的数据。要求利用重叠保留法通过快速傅里叶变换来实现这种滤波器，
为了做到这一点，则：
（ 1）输入各段必须重叠 P个抽样点；
（ 2）我们必须从每一段产生的输出中取出 Q个抽样点，使这些从每一段得到的抽样连接在一起时，得到的序列就是所要求的滤波输出。假设输入的各段长度为 100个抽样点，而离散傅里叶变换的长度为 128点。
进一步假设，圆周卷积的输出序列标号是从 n = 0到
n = 127，则
（ a）求 P； （ b）求 Q；
（ c）求取出来的 Q个点的起点和终点的标号，即确定从圆周卷积的 128点中要取出哪些点，去和前一段的点衔接起来。
解,（ a）由于用重叠保留法，如果冲激响应hn 的点数为
N点，则圆周卷积结果的前面的 1N? 个点不代表线性卷积结果，故每段重叠点数 P为
1 5 0 1 4 9PN
（ b）每段点数为 72 128?,但其中只有 100个点是有效输入数据，其余 28个点为补充的零值点。因而各段不重叠而又有效的点数 Q为
100 100 49 51QP
（ c）每段 128个数据点中，取出来的 Q个点的序号从
49n? 到 99n? 。用这些点和前后段取出的相应点连接起来，即可得到原来的长输入序列。
另外，对于第一段数据没有前一段，故在数据之前必须加上 1 4 9PN个零值点，以免丢失数据。
