FFT算法答案

第三章 离散傅里叶变换及其快速算法习题答案参考3.1 图P3.1所示的序列()x n %是周期为4的周期性序列。

请确定其傅里叶级数的系数()Xk %。

解：(1)11*0()()()()()()N N N nk nk nk N N N n n n X k x n W x n W x n W X k X k -----=====-==-=∑∑∑%%%%%%3.2 （1）设()x n %为实周期序列，证明()x n %的傅里叶级数()Xk %是共轭对称的，即*()()X k X k =-%。

（2）证明当()x n %为实偶函数时，()Xk %也是实偶函数。

证明：（1）1011**()()()[()]()()N nk Nn N N nk nkNNn n X k x n W X k x n Wx n WX k --=---==-=-===∑∑∑%%%%%%（2）因()x n %为实函数，故由（1）知有 *()()Xk X k =-%或*()()X k X k -=% 又因()x n %为偶函数，即()()xn x n =-%%，所以有(1)11*0()()()()()()N N N nk nk nk N N N n n n X k x n W x n W x n W X k X k -----=====-==-=∑∑∑%%%%%%3.3 图P3.3所示的是一个实数周期信号()x n %。

利用DFS 的特性及3.2题的结果，不直接计算其傅里叶级数的系数()Xk %，确定以下式子是否正确。

（1）()(10)Xk X k =+%%，对于所有的k ； （2）()()Xk X k =-%%，对于所有的k ； （3）(0)0X=%；（4）25 ()jkX k eπ%，对所有的k是实函数。

解：（1）正确。

因为()x n%一个周期为N＝10的周期序列，故()X k%也是一个周期为N＝10的周期序列。

（2）不正确。

因为()x n%一个实数周期序列，由例3.2中的（1）知，()X k%是共轭对称的，即应有*()()X k X k=-%，这里()X k%不一定是实数序列。

第三章离散傅里叶变换及其快速算法习题答案参考3.1 图P3.1所示的序列(xn 是周期为4的周期性序列。

请确定其傅里叶级数的系数(X k。

解:(111*0((((((N N N nk nk nk N N N n n n X k x n W x n W x n W X k X k −−−−−=====−= =−=∑∑∑3.2 (1设(xn 为实周期序列,证明(x n 的傅里叶级数(X k 是共轭对称的,即*((X k X k =− 。

(2证明当(xn 为实偶函数时,(X k 也是实偶函数。

证明:(1 111**((([(]((N nk N n N N nk nkNNn n Xk x n W Xk x n W xn W X−−=−−−==−=−===∑∑∑ k(2因(xn 为实函数,故由(1知有 *((Xk X k =− 或*((X k X k −= 又因(xn 为偶函数,即((x n x n =− ,所以有(111*0((((((N N N nk nk nk N N N n n n X k x n W x n W x n W X k X k −−−−−=====−= =−=∑∑∑3.3 图P3.3所示的是一个实数周期信号(xn 。

利用DFS 的特性及3.2题的结果,不直接计算其傅里叶级数的系数(Xk ,确定以下式子是否正确。

(1,对于所有的k; ((10Xk X k =+ (2((Xk X k =− ,对于所有的k; (3; (00X=(425(jkX k eπ,对所有的k是实函数。

解:(1正确。

因为(x n 一个周期为N =10的周期序列,故(X k 也是一个周期为N=10的周期序列。

(2不正确。

因为(xn 一个实数周期序列,由例3.2中的(1知,(X k 是共轭对称的,即应有*((Xk X = k −,这里(X k 不一定是实数序列。

(3正确。

因为(xn (0n ==在一个周期内正取样值的个数与负取样值的个数相等,所以有 10(0N n Xx −=∑ (4不正确。

数字信号处理原理与算法实现课后练习题含答案题目一给定一个分别由两个信号串A和B组成的长度为4的信号的数组arr：arr = np.array([[1,2,1,1],[2,3,1,1]])请问如何使用FFT算法计算每个信号串的频域表达式？答案一使用FFT算法进行频域转换后，每个信号串的频域表达式如下：A_freq = np.fft.fft(arr[0])B_freq = np.fft.fft(arr[1])题目二设有如下的离散时间信号：x = np.sin(2*np.pi*100*np.linspace(0,1,256)) + np.sin(2*np.pi*2000*np.lins pace(0,1,256)) + np.random.randn(256)请问如何对该信号进行时域显示和频域显示？答案二使用Matplotlib库可以对离散时间信号进行时域显示：import matplotlib.pyplot as pltplt.plot(x)plt.show()使用FFT算法并结合Matplotlib库可以对离散时间信号进行频域显示：from scipy.fftpack import fftx_freq = fft(x)plt.plot(np.abs(x_freq))plt.show()题目三对于一个长度为16的实数序列x，要求其DFT的结果为奇对称，即X[k] =-X[N-k]其中 k 和 N 均为整数。

请问该序列有哪些数值？答案三由于X[k] = -X[N-k]，因此对于k = 0，有X[0] = 0。

同时由于这是一个实数序列，因此N-k = N-0 = N，表示X[N]为实数。

对X[N/2]进行分析，因为N为偶数，所以N/2为整数。

因此X[N/2] =-X[N/2]说明X[N/2]为零或为纯虚数。

现在考虑对k进行分析。

由于X[k] = -X[N-k]，因此在考虑k时，也要同时考虑N-k的情况。

第六章 快速傅里叶变换(FFT)1. 如果一台通用计算机的速度为平均每次复乘需100μs,每次复加需20μs,今用来计算N=1024点的DFT[x(n)],问用直接运算需要多少时间,用FFT 运算需要多少时间。

解：ss FFT ss FFT N N a N N N m ss DFT s DFT DFT N a m FFT FFT DFT DFT μμμμμμμ23221027682666221020482010241051210512010240log ),10242(,5120log 210820104,10410104,104104102444⨯=⨯⨯=⨯======⨯=⨯⨯⨯=⨯⨯⨯⨯=⨯===作复加所需时间作复乘所需时间作复加所需时间作复乘所需时间作复乘 2. 用图6.8所示流程图验证图6.7所示的8点变址运算。

证明：由图6.8知取A=x(0),B=x(4)N=8X(k)=12/,,1,0),()(21-=+N k k X W k X k NX(N/2+k)=12/,,1,0),()(21-=-N k k X W k X k N5.试证实以下流图是一个N=8的FFT 流图.其输入是自然顺序的,而输出是码位倒置顺序的,试问这个流图是属与时间抽取法还是频率抽取法?并比较与书中哪一个流图等效。

解：这个流图属于频率抽取法。

6.试设计一个频率抽取的8点FFT 流图,需要输入是按码位倒置顺序而输出是按自然顺序的。

解:设计的流图为第五题的流图左右翻转180度。

∑∑-=-==+=1202/21202/1)()12()()2(N k kr N N k kr N W k x r X W k x r X7.试用图6.14(a)中的蝶形运算设计一个频率抽取的8点IFFT 流图。

解：X(0) 1/2 x(0) X(4) x(1)X(2) x(2)X(6) x(3)X(1) x(4)X(5) x(5)X(3) x(6)X(7) x(7)9.试作一个N=12点的FFT 流图,请按N=2,2,3分解,并问可能有几种形式?解：可能有三种先分成2组，每组有6各点，后每组内再分成两组322⨯⨯=N时间顺序为x(0),x(4),x(8),x(2),x(6),x(10),x(1),x(5),x(9),x(7),x(11)频域顺序为X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),X(8),X(9),X(10),X(11)流图如图6.18解：由题可得∑∑-=-=-=-=∴-⋅⋅⋅====102210)(|)(1,,1,0,)()(N n kn Nj z z k N j k N n ne n x z X N k e z z z n x z X k ππ由于(a)将M 点序列分成若干段N 点序列，设段数为k 即N k M kN )1(-≥>并令kn N j N n k i i z z k en y z X N n N k M N k M n N k n x n y N n x n y n x n y k π21010110)]([[|)(11)1(,01)1(0],)1([)()()()()(--=-==-∑∑=⎩⎨⎧-≤<------≤≤-+=+==若用N 点FFT 计算)(k z X 先由x(n)形成)(n y i ，再计算∑-=10)(k i i n y 的N 点FFT 即可(b)先将序列添加一点等于零的点，使得⎩⎨⎧-≤≤-≤≤=1,010),()(0N n M M n n x n x再计算)(0n x 的N 点FFT 即10,)(|)(20-≤≤=∑-=N k e n x z X kn N j z z k π即可13.已知X(K),Y(K)是两个N 点实序列x(n),y(n)的DFT 值,今需要从X(K),Y(K)求x(n),y(n)值,为了提高运算效率试设计用一个N 点IFFT 运算一次完成。

课后习题及答案_第3章离散傅里叶变换--习题数字信号处理第三版第3章离散傅里叶变换(DFT)习题1．计算以下序列的N点DFT，在变换区间0≤n≤N－1内，序列定义为(1) x(n)=1(2) x(n)=δ(n)(3) x(n)=δ(n－n0) 0n0N(4) x(n)=Rm(n) 0mN(5) n ) jNmn N x(=e,0 mπ 2 (6) n ) x(=cos mn ,0mN2π(7) x(n)=ejω0nRN(n)(8) x(n)=sin(ω0n)RN(n)(9) x(n)=cos(ω0n)RN(N)(10) x(n)=nRN(n)2．已知下列X(k)，求x(n)=IDFT［X(k)］Njθ 2e N（1）X (k)= e jθ20 N k=m k=N m其它kNjθ j2e N jθ（2）X (k)= je 2 0 k=m k=N m 其它k其中，m为正整数，0mN/2, N为变换区间长度。

3．已知长度为N=10的两个有限长序列：做图表示x1(n)、x2(n)和y(n)=x1(n) * x2(n)，循环卷积区间长度L=10。

，4．证明DFT的对称定理，即假设X(k)=DFT［x(n)］数字信号处理第三版证明DFT［X(n)］=Nx(N－k)5．如果X(k)=DFT［x(n)］，证明DFT的初值定理1x(0)=N∑X(k)k=0N 16．设x(n)的长度为N，且X(k)=DFT［x(n)］0≤k≤N－1令h(n)=x((n))NRmN(n) m为自然数H(k)=DFT［h(n)］mN 0≤k≤mN－1求H(k)与X(k)的关系式。

7．证明: 若x(n)为实序列，X(k)=DFT［x(n)］N，则X(k)为共轭对称序列，即X(k)=__（N－k)；若x(n)实偶对称，即x(n)=x(N－n)，则X(k)也实偶对称；若x(n)实奇对称，即x(n)=－x(N－n)，则X(k)为纯虚函数并奇对称。

FFT （快速傅⾥叶变换）算法详解多项式的点值表⽰(Point Value Representation)设多项式的系数表⽰(Coefficient Representation)：P a (x )=a 0+a 1x +a 2x 2+⋯+a n −1x n −1=n −1∑i =0a ix i则我们对上⾯的式⼦可以代⼊不同的 n 个 x 的值，构成⼀个 n 维向量：P a (x 0)P a (x 1)P a (x 2)⋮P a (x n −1)=1x 0x 20⋯x n −101x 1x 21⋯x n −111x 2x 22⋯x n −12⋮⋮⋮⋱⋮1x n −1x 2n −1⋯x n −1x −1a 0a 1a 2⋮a n −1更简洁的写法：P a =X α对上式观察后发现，X 是所谓的范德蒙德矩阵(Vandermonde's Matrix)，在 n 个 x 的值不同的情况下，其⾏列式的值为：det (X )=∏0⩽i <j ⩽n −1(x j −x i )很明显，当所有 n 个 x 取值不同时，其⾏列式不为零，因此 X 可逆。

所以我们可以唯⼀确定多项式系数构成的向量 α：α=X −1P a也就是说，多项式 P a (x ) 还可以由 n 个 x 代⼊得到的 n 个点值来唯⼀表⽰：{x 0,P(x 0),x 1,P(x 1),x 2,P(x 2),⋯,x n −1,P(x n −1)}这就是多项式的点值表⽰。

多项式的点值表⽰是指，对于 n 次多项式，可以⽤ n 个不同的 x 和与之对应的多项式的值 P(x ) 构成⼀个长度为 n 的序列，这个序列唯⼀确定多项式，并且能够与系数表⽰相互转化。

n 次单位根了解了多项式的点值表⽰，⼀个很⾃然的问题是：如何选择 x 的值，来防⽌其指数⼤⼩爆炸型增长呢？这⾥可以借⽤复数的单位根。

简单回顾⼀下，复数有两种表⽰⽅法：迪卡尔积坐标表⽰和极坐标表⽰，这⾥我们⽤到的是后者：z =re i θi 是虚数单位，r 表⽰模长，θ 表⽰相⾓。

第一章快速傅里叶变换（FFT ）4.1 填空题（1）如果序列)(n x 是一长度为64点的有限长序列)630(≤≤n ，序列)(n h 是一长度为128点的有限长序列)1270(≤≤n ，记)()()(n h n x n y *=（线性卷积），则)(n y 为 点的序列，如果采用基FFT 2算法以快速卷积的方式实现线性卷积，则FFT 的点数至少为 点。

解：64+128-1＝191点; 256(2)如果一台通用机算计的速度为：平均每次复乘需100s μ，每次复加需20s μ，今用来计算N=1024点的DFT )]([n x 。

问直接运算需（ ）时间，用FFT 运算需要（ ）时间。

解：①直接运算：需复数乘法2N 次，复数加法）（1-N N 次。

直接运算所用计算时间1T 为s s N N N T 80864.12512580864020110021==⨯-+⨯=μ）（② 基2FFT 运算：需复数乘法N N2log 2次，复数加法N N 2log 次。

用FFT 计算1024点DTF 所需计算时间2T 为s s N N N NT 7168.071680020log 100log 2222==⨯+⨯=μ。

(3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子k Nj e π2-的来减少计算量，其特点是 _______、_________和__________。

解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置 （4）N 点的FFT 的运算量为复乘 、复加 。

解：N NL N mF 2log 22==；N N NL aF 2log ==4.2 选择题1．在基2DIT —FFT 运算中通过不断地将长序列的DFT 分解成短序列的DFT ，最后达到2点DFT 来降低运算量。

若有一个64点的序列进行基2DIT —FFT 运算，需要分解 次，方能完成运算。

A.32 B.6 C.16 D. 8 解：B2．在基2 DIT —FFT 运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16，倒序前信号点序号为8，则倒序后该信号点的序号为 。