7-2按时间抽取的FFT算法

盐城师范学院考试试卷2009 - 2010 学年 第二学期黄海 学院 电子信息工程 专业 《数字信号处理》试卷B班级 学号 姓名 一、填空题(本大题共16小题，每空1分，共25分)1. 数字信号处理在实现时由于量化而引起的误差因素有A/D 变换的量化效应，_系数__量化效应，数字运算过程中的有限_字长____效应。

2. 一个采样频率为fs 的N 点序列X(n),其N 点DFT 结果X(2)代表2fs/N 的频谱。

3. 双边序列的收敛域在Ｚ平面上是一 环 状的。

4. 用窗口法设计FIR 滤波器时影响滤波器幅频特性质量的主要原因是主瓣使数字滤波器存在 过渡 带，旁瓣使数字滤波器存在衰减，减少阻带 波动 。

5. 已知x(n)=δ(n)，其N 点的DFT ［x(n)］=X(k)，则X(N-1)= 1 。

6. 线性移不变数字滤波器的算法可以用 加法器 、乘法器 、延时器 这三个基本单元来描述。

7. 设两有限长序列的长度分别是M 与N ，欲通过计算两者的圆周卷积来得到两者的线性卷积，则圆周卷积的点数至少应取 M+N-1 。

8. 对于线性移不变系统，其输出序列的傅里叶变换等于输入序列的傅里叶变换与系统的频率响应的乘积。

9. 序列R 3(n)的z 变换为 121z z --++ ，其收敛域为 0z <≤∞ 。

10. 对信号进行频谱分析时，截断信号引起的截断效应表现为频谱 泄露 和谱间 干扰 两个方面。

11. 设实序列的10点DFT 为X(k)(0≤n ≤9)，已知X(1)=3+j ，则X(9)= 。

12. 设实连续信号x(t)中含有频率为40Hz 的余弦信号，先用f s =120Hz 的采样频率对其采样，并利用N=1024点DFT 分析信号的频谱，计算频谱的峰值出现在第341 条谱线附近。

13. 设序列)1()()1(2)(--++=n n n n x δδδ，则0|)(=ωωj e X 的值为 2 。

A一、选择题（每题3分,共5题）1、 )63()(π-=n j e n x ，该序列是 。

A.非周期序列B.周期6π=N C.周期π6=N D 。

周期π2=N 2、 序列)1()(---=n u a n x n ，则)(Z X 的收敛域为 。

A.a Z <B.a Z ≤C.a Z >D.a Z ≥ 3、 对)70()(≤≤n n x 和)190()(≤≤n n y 分别作20点DFT ，得)(k X 和)(k Y ，19,1,0),()()( =⋅=k k Y k X k F ，19,1,0)],([)( ==n k F IDFT n f ,n 在 范围内时,)(n f 是)(n x 和)(n y 的线性卷积。

A.70≤≤nB.197≤≤nC.1912≤≤n D 。

190≤≤n4、 )()(101n R n x =，)()(72n R n x =,用DFT 计算二者的线性卷积，为使计算量尽可能的少，应使DFT 的长度N满足 。

A.16>N B 。

16=N C.16<N D.16≠N5。

已知序列Z 变换的收敛域为｜z ｜<1，则该序列为 .A 。

有限长序列B 。

右边序列 C.左边序列 D 。

双边序列二、填空题（每题3分，共5题)1、 对模拟信号（一维信号,是时间的函数）进行采样后，就是 信号，再进行幅度量化后就是 信号.2、要想抽样后能够不失真的还原出原信号,则抽样频率必须 ，这就是奈奎斯特抽样定理.3、对两序列x(n)和y(n ）,其线性相关定义为 。

4、快速傅里叶变换（FFT)算法基本可分为两大类，分别是： ； 。

5、无限长单位冲激响应滤波器的基本结构有直接Ⅰ型， ，______ 和______ 四种。

三、10)(-≤≥⎩⎨⎧-=n n ba n x n n求该序列的Z 变换、收敛域、零点和极点.（10分）四、求()()112111)(----=z z Z X ，21<<z 的反变换。

FFT 算法分析FFT 算法的基本原理是把长序列的DFT 逐次分解为较短序列的DFT 。

按照抽取方式的不同可分为DIT-FFT （按时间抽取）和DIF-FFT （按频率抽取）算法。

按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n 为大于1的整数），基2、基4算法较为常用。

基2、DIT-FFT （按时间抽取）：-1/21/212(21)/21/21/2/2()() ()()(2)(21)(2)(21)N knNn knknN Nn n N N k r k r NNr n N N kr k krN NN r n X k x n Wx n W x n W x r Wx r Wx r WWx r W ===--+==--====+=++=++∑∑∑∑∑∑∑偶数奇数000令/211/2(2)()N kr N r x r WX k -==∑，/212/2(21)()N krN r x r W X k -=+=∑，则有：1212()()()(/2)()()kN k NX k X k W X k X k N X k W X k =++=-蝶形运算单元如下所示：基2、DIF-FFT （按频率抽取）：-10/211/2/21/21(/2)/21/2/21/2()() ()()()(/2)[()(/2)](2)[()(/2)](21)[()(N knNn N N kn knNNn n N N N kn k n N NNn n N kN kn NNn N rnN n X k x n Wx n Wx n W x n Wx n N W x n Wx n N WX r x n x n N W X r x n x n N =--==--+==-=-===+=++=++=+++=-+∑∑∑∑∑∑∑00000/21/2/2)]N n rnN N n W W -=∑则有：12()()(/2)()[()(/2)]nNx n x n x n N x n x n x n N W =++=-+蝶形运算单元如下所示：由前面的分析可知，DIT （按时间抽取）算法与DIF （按频率抽取）算法没有本质上的区别，只是复数加减法与旋转因子乘法的次序有区别，两种方法的运算量是一样的。

山东理工大学成人高等教育信号分析与处理复习题一、简答题1、判断系统)]()([)(n x n x n n y --=系统的线性、时不变性？2、给出一种不用改变FFT 算法的计算程序可以实现IFFT 运算的方法？3、在离散傅里叶分析中会出现什么问题？应如何改善这些问题？二、计算题1、dt t t )1()42(22-+⎰∞∞-δ 2、求信号)]1()([--t u t u t 的拉氏变换3、 dt t t t )2()]3cos(5[513-+⎰∞-δ 4、 求信号)sin()]1()([)(t t u t u t x π--=的拉氏变换 5、求正弦信号)sin()(θ+Ω=t A t x 的自相关函数6、有一频谱分析仪用的FFT 处理器，其抽样点数必须是2的整数幂。

假定没有采用任何特殊的数据处理措施，已给条件为：(1)频率分辨力≤10Hz (2)信号的最高频率≤4kHz 试确定以下参量：(1)最小记录长度T ；(2)抽样点的最大时间间隔Ts ；(3)在一个记录中的最少点数N 。

7、导出用2个4点DFT 计算一个8点DFT 的按时间抽取的基－2FFT 算法，并画出运算流图？8、设计FIR 低通滤波器，通带允许起伏1dB ，通带截至频率为0.3πrad ，阻带截止频率为0.6πrad ，阻带最小衰减大于40 dB 。

9、已知序列｝ 1 ,1 ,1 ,2{)(=n x ，｝2 ,1 ,2 ,2{)(h =n 1) 试计算出)(n x *)(n h2) 试计算出)(n x 与)(n h 5点的循环卷积 3) 试计算出)(n x 与)(n h 8点的循环卷积10、有限长序x(n )={1,2,-1,3}，采用FFT 运算流图求序列x(n)的离散傅立叶变换X(k)。

11、设计FIR 低通滤波器，通带允许起伏1dB ，通带截至频率为0.25πrad ，阻带截止频率为0.5π rad ，阻带最小衰减大于50 dB 。

一、填空、选择、判断：1. 一线性时不变系统，输入为 x （n ）时，输出为y （n ） ；则输入为2x （n ）时，输出为 2y(n) ；输入为x （n-3）时，输出为 y(n-3) 。

2. 线性时不变系统离散时间因果系统的系统函数为252)1(8)(22++--=z z z z z H ，则系统的极点为 2,2121-=-=z z ；系统的稳定性为 不稳定 。

3.4. 对模拟信号（一维信号，是时间的函数）进行采样后，就是 时域离散信 信号，再进行幅度量化后就是 数字 信号。

5. 单位脉冲响应不变法缺点 频谱混迭 ，适合____低通带通 滤波器设计，但不适合高通带阻 滤波器设计。

6. 请写出三种常用低通原型模拟滤波器特沃什滤波器、切比雪夫滤波器 、 椭圆滤波器。

7. FIR 数字滤波器的单位取样响应为 h(n), 0≤n≤N -1, 则其系统函数 H(z)的极点在 z=0 是 N-1 阶的。

8. 对于N 点（N ＝2L ）的按时间抽取的基2FFT 算法，共需要作 2/NlbN 次复数乘和 _NlbN 次复数加。

9. 从奈奎斯特采样定理得出，要使实信号采样后能够不失真还原，采样频率fs 与信号最高频率f max 关系为：fs>=2f max 。

10. 已知一个长度为N 的序列x(n)，它的离散时间傅立叶变换为X （e jw ），它的N 点离散傅立叶变换X （K ）是关于X（e jw ）的 N 点等间隔 采样 。

11. 有限长序列x(n)的8点DFT 为X （K ），则X （K ）=()70()nk N n X k x n W ==∑。

12. 用脉冲响应不变法进行IIR 数字滤波器的设计，它的主要缺点是频谱的 交叠 所产生的现象。

13. 若数字滤波器的单位脉冲响应h （n ）是奇对称的，长度为N ，则它的对称中心是 (N-1)/2 。

14. 用窗函数法设计FIR 数字滤波器时，加矩形窗比加三角窗时，所设计出的滤波器的过渡带比较 窄 ，阻带衰减比较 小 。

一、填空、选择、判断：1. 一线性时不变系统，输入为 x （n ）时，输出为y （n ） ；则输入为2x （n ）时，输出为 2y(n) ；输入为x （n-3）时，输出为 y(n-3) 。

2. 线性时不变系统离散时间因果系统的系统函数为252)1(8)(22++--=z z z z z H ，则系统的极点为2,2121-=-=z z ；系统的稳定性为 不稳定 。

3. 对模拟信号（一维信号，是时间的函数）进行采样后，就是 时域离散信 信号，再进行幅度量化后就是 数字 信号。

4. 单位脉冲响应不变法缺点 频谱混迭 ，适合____低通带通 滤波器设计，但不适合高通带阻 滤波器设计。

5. 请写出三种常用低通原型模拟滤波器特沃什滤波器、切比雪夫滤波器 、 椭圆滤波器。

6. FIR 数字滤波器的单位取样响应为 h(n), 0≤n≤N -1, 则其系统函数 H(z)的极点在 z=0 是 N-1 阶的。

7. 对于N 点（N ＝2L）的按时间抽取的基2FFT 算法，共需要作 2/NlbN 次复数乘和 _NlbN 次复数加。

8. 从奈奎斯特采样定理得出，要使实信号采样后能够不失真还原，采样频率fs 与信号最高频率f max 关系为： fs>=2f max 。

9. 已知一个长度为N 的序列x(n)，它的离散时间傅立叶变换为X（e jw ），它的N 点离散傅立叶变换X （K ）是关于X （e jw）的 N 点等间隔 采样 。

10. 有限长序列x(n)的8点DFT 为X （K ），则X （K ）=()70()nk N n X k x n W ==∑。

11. 用脉冲响应不变法进行IIR 数字滤波器的设计，它的主要缺点是频谱的 交叠 所产生的现象。

12. 若数字滤波器的单位脉冲响应h （n ）是奇对称的，长度为N ，则它的对称中心是 (N-1)/2 。

13. 用窗函数法设计FIR 数字滤波器时，加矩形窗比加三角窗时，所设计出的滤波器的过渡带比较 窄 ，阻带衰减比较 小 。

按时间抽取的FFT算法讲义1. 引言FFT（快速傅里叶变换）算法是一种高效的计算离散傅里叶变换（DFT）的方法，被广泛应用于信号处理、图像处理和科学计算等领域。

在本讲义中，我们将按照时间的顺序介绍FFT 算法的基本原理和步骤。

2. DFT的定义离散傅里叶变换（DFT）将离散时间域的信号转换为频域的复数信号，其定义为：X(k) = Σ[x(n) * exp(-j*2πnk/N)]其中，X(k) 表示频域的复数信号，x(n) 是输入的离散时间域信号，N 是信号的样本点数，k 是频率索引（0 ≤ k < N）。

3. DFT的计算DFT的直接计算方法是通过遍历所有频率索引 k，并计算上述公式。

但这种方法的时间复杂度为 O(N^2)，当样本点数较大时计算开销较大。

4. 快速傅里叶变换的思想FFT算法的核心思想是将 DFT 的计算过程分解为多个规模较小的 DFT 计算，以降低计算的复杂度。

具体而言，FFT算法利用了信号的周期性质，将输入信号划分为奇数索引和偶数索引的两个子序列，分别进行 DFT 的计算。

5. 雷德算法（Radix-2）雷德算法是FFT算法的一种常用实现方式，其基本思路是将DFT 计算递归地分解为规模为 M/2 的子问题，并利用旋转因子求解。

6. FFT算法的步骤（1）输入信号 x(n) 的样本点数为 N，其中 N 必须为2的幂次，否则需要进行零填充。

（2）将输入信号分解为奇数索引和偶数索引的两个子序列。

（3）对两个子序列分别进行 FFT 的计算。

（4）通过旋转因子和蝶形结构计算两个子序列的 DFT。

（5）将两个子序列的 DFT 结果合并得到整个信号的 DFT。

7. FFT算法的优势相较于直接计算DFT，FFT算法具有以下优势：- 时间复杂度为 O(NlogN)，较直接计算的 O(N^2) 更高效。

- 适用于样本点数为2的幂次的信号。

- 算法实现简单易懂，且可以通过并行计算进一步提高效率。

《数字信号处理》复习题一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

每小题2分）1。

在对连续信号均匀采样时，若采样角频率为Ωs，信号最高截止频率为Ωc，则折叠频率为( D)。

A。

Ωs B。

ΩcC. Ωc/2 D。

Ωs/22。

若一线性移不变系统当输入为x(n）=δ(n）时输出为y（n）=R3(n），则当输入为u(n)-u(n—2)时输出为（C）。

A。

R3(n) B。

R2（n）C. R3（n)+R3(n-1）D. R2(n）+R2（n-1)3. 一个线性移不变系统稳定的充分必要条件是其系统函数的收敛域包含( A）。

A。

单位圆 B. 原点C。

实轴 D. 虚轴4. 已知x(n)=δ（n)，N点的DFT[x(n)］=X(k），则X（5）=( B）。

A. N B。

1 C。

0 D。

—N5. 如图所示的运算流图符号是( D)基2 FFT算法的蝶形运算流图符号。

A。

按频率抽取 B. 按时间抽取C. 两者都是D。

两者都不是6。

直接计算N点DFT所需的复数乘法次数与（B)成正比。

A。

N B。

N2C。

N3 D。

Nlog2N7. 下列各种滤波器的结构中哪种不是I I R滤波器的基本结构( D）.A。

直接型B。

级联型C. 并联型D。

频率抽样型8。

以下对双线性变换的描述中正确的是( B）。

A。

双线性变换是一种线性变换B。

双线性变换可以用来进行数字频率与模拟频率间的变换C。

双线性变换是一种分段线性变换D. 以上说法都不对9。

已知序列Z变换的收敛域为|z|〉1，则该序列为（B)。

A. 有限长序列B。

右边序列C. 左边序列D。

双边序列10. 序列x（n)=R5(n），其8点DFT记为X(k）,k=0,1,…，7，则X(0)为（D）。

A。

2 B。

3C。

4 D。

511. 下列关于FFT的说法中错误的是（A)。

A。

FFT是一种新的变换B. FFT是DFT的快速算法C。

FFT基本上可以分成时间抽取法和频率抽取法两类D. 基2 FFT要求序列的点数为2L(其中L为整数)12。

数字信号处理期末试卷(含答案)一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在括号内。

1.若一模拟信号为带限，且对其抽样满足奈奎斯特采样定理，则只要将抽样信号通过( )即可完全不失真恢复原信号。

A.理想低通滤波器B.理想高通滤波器C.理想带通滤波器D.理想带阻滤波器 2．下列系统（其中y(n)为输出序列，x(n)为输入序列）中哪个属于线性系统？( )A.y(n)=x 3(n)B.y(n)=x(n)x(n+2)C.y(n)=x(n)+2D.y(n)=x(n 2)3.．设两有限长序列的长度分别是M 与N ，欲用圆周卷积计算两者的线性卷积，则圆周卷积的长度至少应取( )。

A ．M+NB.M+N-1C.M+N+1D.2(M+N)4.若序列的长度为M ，要能够由频域抽样信号X(k)恢复原序列，而不发生时域混叠现象，则频域抽样点数N 需满足的条件是( )。

A.N ≥MB.N ≤MC.N ≤2MD.N ≥2M 5.直接计算N 点DFT 所需的复数乘法次数与( )成正比。

A.N B.N 2 C.N 3 D.Nlog 2N6.下列各种滤波器的结构中哪种不是FIR 滤波器的基本结构( )。

A.直接型 B.级联型 C.并联型 D.频率抽样型7.第二种类型线性FIR 滤波器的幅度响应H(w)特点( )： A 关于0=w 、π、π2偶对称 B 关于0=w 、π、π2奇对称C 关于0=w 、π2偶对称 关于=w π奇对称D 关于0=w 、π2奇对称 关于=w π偶对称 8.适合带阻滤波器设计的是： （ ） A )n N (h )n (h ---=1 N 为偶数 B )n N (h )n (h ---=1 N 为奇数 C )n N (h )n (h --=1 N 为偶数D )n N (h )n (h --=1 N 为奇数9.以下对双线性变换的描述中不正确的是( )。

A.双线性变换是一种非线性变换B.双线性变换可以用来进行数字频率与模拟频率间的变换C.双线性变换把s 平面的左半平面单值映射到z 平面的单位圆内D.以上说法都不对10.关于窗函数设计法中错误的是：A 窗函数的截取长度增加，则主瓣宽度减小；B 窗函数的旁瓣相对幅度取决于窗函数的形状，与窗函数的截取长度无关；C 为减小旁瓣相对幅度而改变窗函数的形状，通常主瓣的宽度会增加；D 窗函数法不能用于设计高通滤波器； 二、填空题(每空2分，共20分)1. 用DFT 近似分析连续信号频谱时, _________效应是指DFT 只能计算一些离散点上的频谱。