下载文档原格式
FFT 算法的DSP 实现对于离散傅里叶变换（DFT）的数字计算，FFT是一种有效的方法。
一般假定输入序列是复数。
当实际输入是实数时，利用对称性质可以使计算DFT 非常有效。
一个优化的实数FFT算法是一个组合以后的算法。
原始的2N个点的实输入序列组合成一个N 点的复序列，之后对复序列进行N 点的FFT 运算，最后再由N 点的复数输出拆散成2N点的复数序列，这 2 N点的复数序列与原始的2N点的实数输入序列的DFT输出一致。
使用这种方法，在组合输入和拆散输出的操作中，FFT 运算量减半。
这样利用实数FFT 算法来计算实输入序列的DFT的速度几乎是一般FFT算法的两倍。
下面用这种方法来实现一个256 点实数FFT（2N=256 ）运算。
1. 实数FFT 运算序列的存储分配如何利用有限的DSP 系统资源，合理的安排好算法使用的存储器是一个比较重要的问题。
本文中，程序代码安排在0x3000 开始的存储器中，其中0x3000~0x3080 存放中断向量表，FFT程序使用的正弦表和余弦表数据（.data段）安排在OxcOO开始的地方，变量（.bss段定义）存放在0x80 开始的地址中。
另外，本文中256 点实数FFT 程序的数据缓冲位Ox23OO~Ox23ff , FFT 变换后功率谱的计算结果存放在Ox22OO~Ox22ff 中。
连续定位.cmd 文件程序如下：MEMORY {PAGE O: IPROG: origin = Ox3O8O,len=Ox1F8OVECT: lorigin=Ox3OOO,len=Ox8OEPROG: origin=Ox38OOO,len=Ox8OOOPAGE 1:USERREGS: origin=Ox6O,len=Ox1cBIOSREGS: origin=Ox7c,len=Ox4IDATA: origin=Ox8O,len=OxB8O}SECTIONS{EDATA: origin=OxCOO,len=Ox14OO{.vectors: { } > VECT PAGE O.sysregs:.trcinit:.gblinit: { } > BIOSREGS PAGE 1 { } > IPROG PAGE O { } > IPROG PAGE O.bios:frt:{ } > IPROG PAGE O { } > IPROG PAGE O.text: { } > IPROG PAGE O.cinit: { } > IPROG PAGE O.pinit: { } > IPROG PAGE O.sysinit: { } > IPROG PAGE O.data: .bss: .far:.const: { } > EDATA PAGE 1 { } > IDATA PAGE 1 { } > IDATA PAGE 1 { } > IDATA PAGE 1.switch: { } > IDATA PAGE 1 .sysmem: { } > IDATA PAGE1•cio:{ } > IDATA PAGE1.MEM$obj: { } > IDATA PAGE1.sysheap: { } > IDATA PAGE1}2.基2实数FFT运算的算法该算法主要分为以下四步进行：1）输入数据的组合和位排序首先，原始输入的2N=256个点的实数序列复制放到标记有“ d_input_addr "的相邻单元，当成N=128点的复数序列d[n]，其中奇数地址是d[n]实部，偶数地址是d[n]的虚部，这个过程叫做组合（n为序列变量，N为常量）。
用FPGA实现FFT算法引言DFT(Discrete Fourier Transformation)是数字信号分析与处理如图形、语音及图像等领域的重要变换工具，直接计算DFT的计算量与变换区间长度N的平方成正比。
当N较大时，因计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。
快速傅立叶变换(Fast Fourier Transformation，简称FFT)使DFT运算效率提高1～2个数量级。
其原因是当N较大时，对DFT进行了基4和基2分解运算。
FFT算法除了必需的数据存储器ram和旋转因子rom外，仍需较复杂的运算和控制电路单元，即使现在,实现长点数的FFT仍然是很困难。
本文提出的FFT实现算法是基于FPGA之上的，算法完成对一个序列的FFT计算，完全由脉冲触发，外部只输入一脉冲头和输入数据，便可以得到该脉冲头作为起始标志的N 点FFT输出结果。
由于使用了双ram，该算法是流型(Pipelined)的，可以连续计算N点复数输入FFT，即输入可以是分段N点连续复数数据流。
采用DIF(Decimation In Frequency)-FFT 和DIT(Decimation In Time)-FFT对于算法本身来说是无关紧要的，因为两种情况下只是存储器的读写地址有所变动而已，不影响算法的结构和流程，也不会对算法复杂度有何影响。
算法实现的可以是基2/4混合基FFT，也可以是纯基4FFT和纯基2FFT运算。
傅立叶变换和逆变换对于变换长度为N的序列x(n)其傅立叶变换可以表示如下：NnkX(k)=DFT[x(n)] = Σ x(n)Wn="0"式（１）其中，W="exp"(-2π/N)。
当点数N较大时，必须对式(1)进行基4/基2分解，以短点数实现长点数的变换。
而IDFT的实现在DFT的基础上就显得较为简单了：式（２）由式(2)可以看出，在FFT运算模块的基础上，只需将输入序列进行取共轭后再进行FFT运算，输出结果再取一次共轭便实现了对输入序列的IDFT运算，因子1/N对于不同的数据表示格式具体实现时的处理方式是不一样的。
判断题1、 信号可定义为传载信息的函数2、模拟信号就是时间连续的信号3、连续时间信号就是时间连续的信号4、离散时间信号就是时间离散的信号5、数字信号就是时间幅度都是离散的信号6、系统就是反映信号处理因果关系的设备或运算7、连续时间系统就是输入输出都是连续时间信号的系统8、数字信号处理精度高9、数字信号处理不可时分复用10、数字信号处理可靠性强，但灵活性不大1、√2、×3、√4、√5、×6、√7、√8、√9、× 10、×1、理想取样可以看成实际取样的科学的本质的抽象2、连续时间的取样造成频谱的周期重复3、连续时间信号的取样可能发生频谱混叠4、离散时间信号可用序列表示5、两序列相乘就是对应序列值相乘6、所有正弦序列都是周期的7、所有复指数序列都是周期的8、当h(n)为因果序列时，系统一定是因果的9、当h(n)绝对可和时，系统一定是稳定的 10、)(1)(n u n n h =，则系统是稳定的 11、)(2)(n u n h n -=，系统是非因果的不稳定系统 12、2)()(+=n x n y ，系统是线性的 13、)()(n x a n y n =，系统是时变的14、离散时间线性非时变系统可用常系数线性差分方程描述15、系统频率响应是指系统对不同频率的正弦序列的不同传输能力16、系统频率响应是连续的非周期的17、系统频率响应是周期的，周期为2π18、任何序列的傅里叶变换都是存在的19、实序列的傅里叶变换是共轭对称的20、Z 变换的收敛域可以是方形区域21、Z 变换的收敛域是以极点来限定边界的22、双边序列的Z 变换的收敛域为环域23、)(n ∂的收敛域为整个Z 平面24、傅里叶变换就是单位圆上的Z 变换25、系统函数收敛域包括单位圆，则系统稳定26、系统函数的收敛域在环内，则系统是因果的27、极点、零点都在单位圆内，系统是最小相位系统28、极点在单位圆内，零点有在单位圆内，也有在单位圆外，则系统是最大相位系统29、极点在单位圆内，零点有在单位圆内，也有在单位圆外，则系统是非最小相位系统30、非最小相位系统可以看成最小相位系统和全通函数相乘1、√2、√3、√4、√5、√6、×7、×8、√9、√ 10、×11、× 12、× 13、√ 14、√ 15、× 16、× 17、√ 18、× 19、√ 20、×21、√ 22、√ 23、√ 24、√ 25、√ 26、× 27、√ 28、× 29、√ 30、√1、离散傅里叶变换在一个域里边是周期的，则另一个域是连续的2、离散傅里叶变换在一个域里边是非周期的，则另一个域是离散的3、离散傅里叶变换一个域里边周期的倒数是另一个域的周期4、DFT 是DFS 取主值5、DFT 不隐含周期性6、DFT 不是连续傅里叶变换的近似7、DFT 是X(z)在单位圆上的等间隔取样8、DFT 的综合就是X(z)9、DFT 和IDFT 可用一套程序计算10、补零增长可使谱线变密11、x(n)反转，X(k)也反转。
fft的fpga实现1．引言DFT及其快速算法FFT是信号处理领域的核心组成部分。
FFT算法多种多样，按数据组合方式不同一般分时域和频域，按数据抽取方式的不同又可分为基2，基4等。
各算法的优缺点视不同的制约因素而不同。
FFT的实现方法也多种多样，可以用软件实现，也可以用硬件实现，用软件在PC机或工作站上实现则计算速度很慢。
一般多结合具体系统用硬件实现。
例如用单片机或DSP实现。
但是速度仍然很慢，难以与快速的A/D器件匹配。
在雷达信号处理领域主要追求的目标是速度，即实时性的要求非常高。
针对这种快速信号处理的要求及FPGA器件的特点，本文采用的是一种基2固定几何结构的FFT算法。
采用的是Altera公司推出的最新器件Stratix来做硬件仿真。
Stratix器件是一款采用高性能结构体系的PLD器件。
它结合了强大内核性能，大存储带宽，数字信号处理（DSP）功能，高速I/O性能和模块化设计与一体的PLD。
其内嵌的DSP模块具有很高的乘法运算速度。
在用VHDL编程时可以用MegaWizard的方法指定用DSP模块生成乘法器，用这种乘法器来做蝶形，用多个蝶形来构成FFT运算级，通过循环即可实现FFT核心运算的并行化。
用Altera公司的Quartus软件做逻辑分析和波形分析。
Quartus软件具有很强的硬件仿真和逻辑分析功能，它可将用VHDL编写的硬件描述综合到FPGA中。
2．算法介绍为了说明问题的方便，下面以基2，八点FFT为例加以说明。
传统的基2变几何结构算法如下（图一）：箭头上的数字代表旋转因子中的k。
图中输入采用的是按码位颠倒的顺序排放的。
输出是自然顺序。
这种结构的特点是每个蝶形的输出数据仍然放在原来的输入的数据存储单元内，这样只需要2N个存储单元（FFT中的数据是复数形式，每点需要两个单元存储）。
其缺点是不同级的同一位置蝶形的输入数据的寻址不固定，难以实现循环控制。
用FPGA编程时难以并行实现，数据处理速度慢。
、单项选择题1. 序列 x(n)=Re(e jn 皿)+1 m (e jn 皿),周期为()。
n A. 18B. 72C. 18 nD. 362. 设C 为Z 变换X(z)收敛域内的一条包围原点的闭曲线， F(z)=X(z)z n-1,用留数法求X(z)的反变换时()。
5、人(n)二R ,0(n) , X 2(n)二R 7(n)，用DFT 计算二者的线性卷积，为使计算量尽可能的少，应使 DFT 的长度N 满足 _______________ A. N 16 B. N =16C. N ：166. 设系统的单位抽样响应为 h(n)= S (n)+2 S (n-1)+5 S (n-2),其频率响应为( j 3 j « j2 3 j5 3j 3-j 3-j2 3A. H(e j )=e j +e j +e jB. H(e j)=1+2e j+5e jj 3 -j 3-j2 3 -j5 3j 3 1 -j 3 1 -j2 3 C. H(e j)=e j +e j+e jD. H(e j)=1+ —e j +—e j257.设序列 x(n)=2 S (n+1)+ S(n)- S (n-1)，贝U X(e j 3)| 3=0 的值为()。
A. 1B. 2C. 4D. 1/28. 设有限长序列为 x(n), N 1< n W N 2,当N K 0,N 2>0 , Z 变换的收敛域为( )。
A. 0<|z|< gB. |z|>0C. |z|<gD. |z|W89.在对连续信号均匀采样时，要从离散采样值不失真恢复原信号，则采样角频率 Qs 与信号最高截止频率 Qc 应满足关系() A. Q s>2 Q c B. Q s> Q c C. Q s< Q cD. | Q s<2 Qc10.下列系统(其中y(n)为输出序列，x(n)为输入序列)中哪个属于线性系统？( )A.y( n)=y( n-1)x(n)B.y( n)=x( n) /x( n+1)C.y( n)=x( n)+1D.y( n)=x (n )-x( n-1)11.已知某序列Z 变换的收敛域为5>|z|>3，则该序列为()A. 只能用F(z)在C 内的全部极点B. 只能用F(z)在C 外的全部极点C.必须用收敛域内的全部极点3.有限长序列h(n)(0 < n W N-1)关于D.用F(z)在C 内的全部极点或C 外的全部极点N - 1-一1偶对称的条件是2)。
一. 填空题1、一线性时不变系统，输入为输入为 x （n ）时，输出为y （n ） ；则输入为2x （n ）时，输出为输出为 2y(n) ；输入为x （n-3）时，输出为）时，输出为 y(n-3) 。
2、从奈奎斯特采样定理得出，要使实信号采样后能够不失真还原，采样频率fs 与信号最高频率f max 关系为：关系为：fs>=2f max 。
3、已知一个长度为N 的序列x(n)，它的离散时间傅立叶变换为X （e jw ），它的N 点离散傅立叶变换X （K ）是关于X （e jw ）的）的 N 点等间隔点等间隔 采样采样 。
4、有限长序列x(n)的8点DFT 为X （K ），则X （K ）= 。
5、用脉冲响应不变法进行IIR 数字滤波器的设计，它的主要缺点是频谱的数字滤波器的设计，它的主要缺点是频谱的 交叠交叠 所产生的所产生的 混叠 现象。
现象。
6．若数字滤波器的单位脉冲响应h （n ）是奇对称的，长度为N ，则它的对称中心是则它的对称中心是 (N-1)/2 。
7、用窗函数法设计FIR 数字滤波器时，数字滤波器时，加矩形窗比加三角窗时，加矩形窗比加三角窗时，加矩形窗比加三角窗时，所设计出的滤波器的过渡带比较所设计出的滤波器的过渡带比较所设计出的滤波器的过渡带比较 窄 ，阻带衰减比较，阻带衰减比较，阻带衰减比较 小小 。
8、无限长单位冲激响应（、无限长单位冲激响应（IIR IIR IIR）滤波器的结构上有反馈环路，因此是）滤波器的结构上有反馈环路，因此是）滤波器的结构上有反馈环路，因此是 递归递归 型结构。
型结构。
9、若正弦序列x(n)=sin(30n π/120)/120)是周期的是周期的是周期的,,则周期是N= 8 N= 8 。
1010、、用窗函数法设计FIR 数字滤波器时，数字滤波器时，过渡带的宽度不但与窗的过渡带的宽度不但与窗的过渡带的宽度不但与窗的 类型类型 有关，还与窗的还与窗的 采样点数 有关有关11．DFT 与DFS 有密切关系，因为有限长序列可以看成周期序列的 主值区间截断 ，而周期序列可以看成有限长序列的 周期延拓 。
2022电信数字信号处理题库一、单项选择1.下列四个离散信号中，是周期信号的是（）。
A．in(100n)B.ej2nC.conin30nD.e1jn3ej4n52.某系统的单位脉冲响应h(n)()u(n)，则该系统（）。
A.因果不稳定B.非因果稳定C.因果稳定D.非因果不稳定3.某(n)enj()3612n，则该序列是（）。
A.非周期序列B.周期N/6C.周期N6D.周期N24.一个离散系统（）。
A.若因果必稳定B.若稳定必因果C.因果与稳定有关D.因果与稳定无关5.某系统y(n)n某(n)，则该系统（）。
A.线性时变B.线性非时变C.非线性非时变D.非线性时变6.某系统y(n)g(n)某(n)，g(n)有界，则该系统（）。
A.因果稳定B.因果不稳定C.非因果稳定D.非因果不稳定7.某1(n)3in(0.5n)的周期是（）。
A.4B.3C.2D.18.若一线性移不变系统当输入为某(n)(n)时输出为y(n)R3(n)，则当输入为u(n)u(n2)时输出为（）。
A．R3(n)B.R2(n)C.R3(n)R3(n1)B.TS1/fhC.TS1/fhD.R2(n)R2(n1)D.TS1/(2fh)9.在对连续信号均匀采样时，要从离散采样值不失真恢复原信号，则采样周期TS与信号最高截止频率fh应满足关系（）。
A．TS2/fh10.某系统y(n)[某(n)]2，则该系统是（）。
A.线性移不变系统B.移不变非线性系统C.线性移变系统D.非线性移变系统11.某系统y(n)某(n)5，则该系统（）。
A.因果稳定B.非因果稳定C.因果不稳定D.非因果不稳定12.差分方程y(n)某(nm)所描述系统的单位冲激响应是（）nm0A．u(n)B.(n)C.不存在D.au(n)13.以下说法中（）是不正确的。
A.时域采样，频谱周期延拓B.频域采样，时域周期延拓C.序列有限长，则频谱有限宽D.序列的频谱有限宽，则序列无限长14.某(n)2n[u(n)u(n5)]，则某(z)的收敛域应是（）。
