数字信号处理-奥本海姆第九章

第九章散傅立叶变换的计NXkxnej2NknN

k0,1,,N即，程序的输入是序列xn，而输出是DFTXk。证明如何将输入和/或输出序列重新IDFT：xn

Nk

k0,1,,N即，程序的输入应当是Xk或与Xk有简单联系的一个序列，而输出应当是xn或与1FFTNgnXkej2NknNk然后计xn

1gNnN

1N1Xkej2NkNnNk

N1Xkej2Nkn就可NkIDFT。2FFT程序计算NgnXkej2NknNk 1N

1Nxn

gn

X*kej2Nkn

Xkej2Nkn就可N

Nk

NkN9.2节中我们利用WN

1来推导出有限长序列Xnn0,1,N1计算个指定DFTXk的递推算法N利用WN

W

1,XNkP9.2-1NN代后输出而求得.也就是说,NXNkykNXNkP9.2-2N次迭代后的输出.注意,P9.2-P9.2的系统有相同的极点,P9.2-2NP9.2中对应系统的复共轭,即WN

N解:(a)假定xrN

0rN故

rxrWkNkyk0Nk

rNkNky2x2Wkx1W2k yNxNWkxN1WkN 因为xN0,所N NyNWkN1xlWklxl l

lN1WNklxlXNkNl(b)P9.2-2H

1Wkz 212

kz1zN1Wkz k1 k11WN 1WN9.2H

1Wkz 212

kz1zN1Wkz k1 k11WN 1WNP9.2-29.2具有相同的极点,9.2NN共轭.即WkWkNNP9.3N8FFTx[7X[2P9.3x[7X[2的路径有多少条？在一般情况下这一结论是否DFTX[2]P9.3DFTN

X[2] （a）j jW2W2 8e x[7X[21条。在一般情况下，每个输入样1条。分别是：W0，W2，W2N X[2]x[0]W0x[7]W2N N

N

j22nx[nA[rnrnBN1BN2B1B0nB0B1BN2BN1Bi（i=0、1、…、N-1）为二进制码元（0x[kD[k

nN＝8x[nNx[n]2N同时考虑到W2jP9.4b-1B[和C[值。可得最终简化后的计算流图，如9.4b-2所示。NC[1]=2A[0]-C[1]=2A[0]---C[3]=2---C[5]=2A[1]-----

-

-

44

-NN

1212

kE[r2]-

9.4c

原流 逆流 E[r1]D[r1]D[r2]/E[rE[r E[rD[rD[r]2 且标出任何传输比等于－1DFT序列的适当值分别标出输入和解：执行流图运算所需要的实乘法次数为484128实加法次数为2164284192次WWW WWWW WWWWW

WWW WWWW WWWW W

WWWWW WW WW

WWWWWWWW W

X3XXX7XX X XXW WWW

WWW W

WWW WW W

W WWW W W

XX X9.4.2节中曾断言,FFTFFT算法的流图.本习题的目2FFT算法推导出这仪结论.2FFTP9.6-1中.这个流图表示如下方程NXmpXm1pXm1NXmq

p

从这些方程入手,证明利用图P9.6-2所示的蝶形图可由Xmp和Xmq计算Xm1p和Xm19.20的按频率抽取算法中Xvrr0,1,N1DFTXk,而第零X0rxrr0,1,,N1为正常位序排列的输入序列.如果图9.20P9.6-2形式的适当蝶形来替代,DFTXk(倒位序)来计算序列xn(正常位序)的流图.画出当N=8时所得结果的流图.(c)在(b)IDFT算法,即,计算下式的算法:xn

n0,1,,N1NNkNXkXk N

k0,1,,N1

可以看出,(c)9.20按频率抽取算法的转置,9.10所示的按时间抽取算法.是否可得出结论,对于每一种按时间抽取算法(9.14~9.16),必有一解(a)P9.6-2可写出XX

p121

p1 1

NmNmXm1q

Xmp

Xm将上式带入题给方程组可得XmpXm1pXm11

p1XqWr1

p1XqWr

N

NXmXmq

p

N1N

p1XqWr1

p1XqWr Xm

N

因此可用图P9.6-2所示的蝶形图可由Xmp和Xmq计算出Xm1p和Xm1q.1 2

。

。 1WX4 2

2

1W

1

。

2

X

1W

1W

2

1W

1 1X

。2 。2

1W

1

1W

2

X

1W

1 1W

。

。

。2 1W 1

1W

1 1WX7

1

N 1

1(c)X(c)XkN

n 1

NNN

n Nxn的IDFT可将(b)中图的输Xk相应变为xnkn再对整个图作共轭,最后再乘

。

。 X

。

W0

XNN

。W0 N。N。

X

W2WN0N 。WN0W。1。。W。1。。N1WN2N 。W0WN2N。3。3WNN。W2WNN

W0NN。N。。W0N。。1NW0N

XXXXX将(c)9.10相同的图在许多的应用中（如计算频率响应或者内插,1971M2DFTN2v(2按频率抽取算法进行修剪。N162FFT算法的完整流图，合理地标出全部分M2，即，仅当n0和n1x[n0N16DFT的，也就是在（b）P9.7所示的半蝶形来代替，而在最M2DFTN2v(FFTMNDFT和v来9.26Xm1[WNXm[WNXm（a）N=16M2DFTN2v(的一般情况，可以使用修剪的碟形的级数比总的级数少一级，就是(v1级。M点序列的NDFT所需要复数乘22i22v

9.26的程序使之包括修剪算法（暂略n

n

Nnx[rx[rNN/F[0] x[2n1]n

N/x[2n1]n

N/x[2n1H[0]nF[k]

N/xx[2n1]x[2n1]。N/nx[rN]

F[k] nk

QWN/n

F[k]H[k]H[k]W H[kH[k]W2kH[k]WkWkWkN/ NH[k]WkN

。WkW I[k]

I[k]X[k]G[k]WkW

G[k]

G[k]

N kN

kN Nk=0sin2k0N N （c（d）杜哈梅尔和霍尔曼（DuhamelandHollman，1984）以及杜哈梅尔（Duhamel,1986）曾提NxnDFTXkSRFFT算法的原理。证明Xk的偶序号项可表示成对于k

21

2X2k

N xnxn

N证明DFTXk的奇序号项可表示成对于kN

41

4X4k1

N xnxn

2jxn

4xn

N

162N较。在这两种情况下均假设与W0N（a） N NN

NN

xnxn n

x N2WNN

4k1n

4 4xnN

xnn N xnNN xnN

2WN WWWWWW WSRFFT12482算法需要41641282 FFT算法时,利用规范形式或耦合形式的振荡器递推的产生WN的幂往往时很有用的.N2v2按时间抽取算法.9.10N=8时的这种算法,9.25NFORTRAN程序为了有效的产生这些系数,应当逐级的改变振荡器的频率.0vlog2N,因此有初始输入序列的数列是第零列,DFTv列.时我们假定数列中的数据在编号从0到N-1依次排列的复数寄存器中.下面的所有问题都是关于从第(m-1)m号数列,其中1mv.m表示.m级中应当计算多少个蝶形?m级中需要多少个不同的系数产生系数所用的振荡器的频率是什么?即在重复计算之前可以迭代多少次假设使用耦合形式振荡器来产生WN的各次幂,在振荡器的差分方程中的系数是什m级中一个蝶形的两个复输入点的数列位置间相隔多少使用相同系数的各蝶形之第一个数列位置的地址之间相隔多少解:

sin2

2m 2m N

9.25FORTRAN9.10FFTv（a）K19~3007~18实现倒位序DFTXjYAjBCjDAC

XABDCYABDC351

XjYABDCDAjABDC ACBDjBCAjBCXABDCYABDC351在计算DFT中,有必要使一个复数与另一个复值为1的复数相乘,即XjYej.显然,ej的乘法称为旋转.DFTFFT算法中可能需要许多不同的幅角值.但是我们可能并不希望将sin和cos所需要的值都作一个数表,而用幂级数计算这些函数都进制移位和由一个小表来查表相结合的方法来高效的计算乘积XjYej.定义

arctan2i.证明任何幅角02M iiˆ其中i1,且误差的界限arctan2M可以事先将幅角算出并在一个长度为M的小数表中.找出一种算法用以得到序列ii0,1,M1,使得i1.M=11时,用你的算法计算表示幅角100的序列 X0Y0

2i1

i1,2,,

X

2i1

i1,2,,

XM

XjY

eM其中ˆ ii,GM是实正数且与无关.这就是说,原始的复数以幅角ˆ在复面中旋转,且幅值由常数GM确定FFTP9.15-1NWrrNN因为复数乘法器的系数Wr＝ej9.14CORDICNCORDIC旋转子算法可以获得要求的幅角变换，但是引入了一个依赖于幅角CORDICNWrP9.15-1P9.15-2GNP9.15-2FFT算法，当N8P9.15-3FFT算法的输出却不是所要求的FFT算法地输出是Y[k]W[k]X[kX[k是输入序列的DFT,而W[k]是GN和k的函数。希望序列W[k]服从一种特别简单的规则。请找出该规则并它 x[nx[nx[nFFT算法的输入，输x[nDFTX[k]。Xm1[ Xm[X

WXmWXm1[ Xm[X

GW

NXmN（a）证明：由图P9.15-3可以看出，该图与82按频率抽取FFT算法的完整流图相比，唯一的区别是在有旋转因子的地方，图P9.15-3多一个增益因子G，将G等效倒输出端Y[0]x[0],Y[1]Y[2]Gx[2],Y[3]G2XY[4]Gx[4],Y[5]G2XY[6]G2x[6],Y[7]G3X Y[k]w[k]XGGw[k]

kk k

k“1”的个数，即i

f(k，fw[k]GiGfx[nDFTX[k]。xˆ[nx[n]h[n]H[kh[nNDFT 要使Y[kW[k]X[k]H[kX H[k]

W[k]

W[k]

（N点循环卷积（a）AN24，BN1 1CN((N 4，D 1

9其中0n1N110k1N110n2N210k2N21。X[((4k9k))]

3

x[((4n3n

]WknWkn

2

n20n1

2

31 422 0120 0120123 0120123 x[11]

X[11]9.32N2vFFTN3v3DFT3×39FFTN3v3NDFTWNN3v3按时间抽取算法能否使用同址运算？（a）9FFT算法的计算公式为：9 r

W3rk9r9 9 rxrW3rkWk r

r GkWk DFT3×39FFTN）N3v3NDFT需要与W的幂相乘的复数乘法的次数为43v123v1103v1NN3v3按时间抽取算法可W9W9W3W3W9W3G0W3W9W9W9W9W9W3W3W92W9W3G2W9W9WG29W3WW93WGW932

X

X

X

X X

X X

XWW43

XWW9本习题涉及有限长序列z变换样本的有效计算问题.利用线性调频变换算法,0.5,起始角为和终止角为225Xz值的步骤 100个样本解:因为xn为已知时间序列,z变换的形式为Xzxnz由题意可知xn序列长度N=100,计算的样本数M=25,相邻样本点的间

251

j 设A0.5e6WerzAWr

0.5ej6erNrX

xnznNxnAnWrnN

n

j j(当N为偶数时，N点序列

NDFTjj()kX[k]＝Ne4 j(求2N点序列 的2N点DFT（N为偶数j(解：因为已知当N为偶数时，N点序列 的N点DFTjj()k

j()n2

X[k]＝Ne4 ，0n2Nj()(nN

j()(n22NnN2 Nej(N)j()(nN

j( y[n]

0nN＝x[nN

Nn2N y[n2NDFTN 2NDFT{y[n]}x[n]Wnkx[nN]WN

N

2 2nx[n]Wnkx[n]W(nN

2 21Wnk1x[n]W2 21x[n]W

2 j22X(e2j2

2X(2

j22X(e2j2

)( jj(k)(Ne4 N

N

j

N

j

(n2k2)(nk)2（a）X[k] N x[n]eN h[nej(N)n2

jn2jk2j

nk2 j

k2N1

jn2jnk2X[k]n0

NeNe

e

n0

Ne

)2

jn2

即

h[k](1)N1x[n]h*[nh[kn](1)NX[k]（c）k=N，N+1，…，2N－1在式（9.20-1）h[r]满足条件0r2N1h[kh[k]2N1

N

N j（d）ˆ(z)ejk

zkejNkk0

zkejN(kN)z(kNkN

N

N jej

zkzNejN(k2kNN)zk1(1)NzNejN

zkk

k

kMN M

1

j(2rMN

2MMz

M j其中 e

zkejN(rlM)z(rlM) ejNr

zrk（e（f）

l0

1

j(2rMN

z1

算法中，将Xk当作ykN来计算，XkykN式中ykN是图P9.21所示网络的输出，考虑用舍入的定点运算来实 B位再加上一个符号位，并且假设在加法之前将乘积舍入。还假定舍xn为实数，画出有限精度计算Xk实部和虚部的线性噪声模型的流图，假设与1相乘不产生舍入噪声。计算Xk实部和虚部二者舍入噪声的方差2cos2k NzykWNzP9.21

1WkzHz 12cos2kz1zN N N hnWNN XkykNxrhNNrxn为实NeXkeykNxrehNNrN N NImXkImykNxrImhNNrN N 1cos2kzNH1zN

12

kz1zsin2kzNH2zN

12

kz1z画出有限精度计算Xk实部和虚部的线性噪声模型的流图如下2cos2Nzey2kzNN zyk2zN（b）由上图（a）可看出Xk实数部分舍入噪声的方差e e

Ne式 e1

e1e

1N2NN2N

n0 1N1

j4

j4nk4n0 4n0

NNkkN 2

式中0kN1222b

NNNN

12

由上图（b）可看出Xk虚数部分舍入噪声的方差e e

Ne式 e1

e1e

1

4nk

N2 N2

n0

N NNNkkN 2

式中0kN1222b

NNNN

12

DFT直接计算法.B位再加上一个符号位(即总长位B+1位).并假设由任何实数乘法引入的舍入噪声和由任何其他的实数乘法所引入的舍入噪声不相关.xn为实数,求每个DFT值Xk的实部和虚部二者中舍入噪声的方差NN NN 量化后,QxnWknxncos2kn

n,kjxnsin2kn

n,kNN NN

在定点舍入中,误差n,k和n,k是 量,它在12B和12B区间 2 2 是均匀分布的彼此独立和输入无关k0时不产生误差k0时NnxnWkn中共有N项,但n0时,W 1,因此不会产生误差,故只有N-N项误差

N其实数部分的误差1n,k的方差 122 其虚数部分的误差2nk的方差2n=0或k=0时,

122因此1

2

1n,k2n,k0.Xk实数部分误差的方差

k

1

kXk虚数部分误差的方差

k

1

kFFTXm[p]

[p]Wr

NXm[q]N

[p]Wr

N1。NX

p]12

[q]2Re{Xm[p]}和Re{Xm[q]}

Im{Xm[q]}Re{和

[p]}12

[p]}2Re{

[q]}12

[q]}2NFFT算法中不出现溢出，这些条件充分吗？清说明原因。（a）FFT算法中，有如下的方程组：NXm

[p]

NN

[p]Wr

Xm

[q]

[p]Wr

p]12

[q]12

[p]

[p]Wr

[q]

[p]W

NNNWr1NNNXm

[p]

[p]Wr

[q]

[p]W

NNXm1[p]Xm1[q]1NN同样可得：Xm[q]1和

Re{Xm[p]}Re{Xm[q]}

Im{Xm[q]}Re{和

[p]}12

[p]}2Re{

[q]}1N2N

[q]}N2N

[p]}Re{Wr

[p]}Re{

m[p]}Re{

[p]}Re{Wr

[Re{

[p]}11

（Xm1p1/2Xm1p1/2）以上推出：Re{Xmp]}1。Re{Xm[q]}1ImXmp]}1ImXm[q]}1。0FFT9.20的按频12的比例因子时，得出输出噪声方差和噪声-N解：把因子Wr和输出的衰减12结合在一起，它产生的误差信号mNEm,q2122b23NN

EXk2EFk243kEFk2kEX

24NN 已经量化,FFT算法中的乘法和加法不产生误差.NNN

vWriWnk i1

iNNiNNN假定系数WrB位再加上一个符号位(B+1位),N虚部互不相关且均匀分布.证明量的方差是误差Fk可以表示

226

Wkn

k0,1,,NN证明因子 Wkn可以表示N Wkn

Wri

NjN

若忽略高阶项并假设量i间互不相关,证明Fk的方差22v22BN16 6

利用帕斯瓦尔定理,DFT 2v6 611Xk2

22 N Nv解(a)2

个蝶形,9.9示.如从某个xn计算Xk,要经过v个蝶形.一般说来,每经过一个蝶形要乘一vWri这里r是n,I=1,……,v.总乘积WriWnk,v xnWnk是Xk中的一项,现在经过量化每支路的乘子由Wri变为Wri, 下图所示.这里的i相当于书中mq再除以Xmk.因此经过v个蝶形到输v riv

ˆ端Xk时,X

i是X

的一部分,NNv riv Xm

NiWri Ni

XmNWri在一般情况下是复数,量化时实数部分和虚数部分都要量化,Ni1in,kj2in,kN由于Wri的实数部分和虚数部分的绝对值都小于1,因此N 12B之间变化, 2

E1in,kEn,k

122故2E2E2n,k2n,k1

利用上边的结果,vv

nk

vvvvvv

j

i N因为是2B1数量级,所以的高阶项可以不计. N

WnkFk21

Wnk1x

Wnk

Nxn2N

Wnk

n0

WnkEWrjWrj

Nj j

j因为xn已知,利用上式证明EFk0F2EFk2F

Wnk2

N2xn2EN

Wnk2

vxnnk4次实乘法,而在计算nk的误差时只有实数项和虚数项两个误差,2.为了书写简便,我们令vWrjai j则

E

Wnk2Eai

ajN N

nki jjj

E

2ankiaEai

22ai

1,

i E Wnk2vE2v F2N1x2n2v22B FN(e)由xn2N

1N1Xk2可得Nk 1N1Xk2Nk

2v6

2N2vDFTFFTk

＋

，k0,..255（假设有限长序列xnNDFTXk,并且还假设该序列满足对称条NxnxnN式中N为偶数xn为复数

2

0nN

0,2,N2Xk0

2DFTDFTXk1,3,N1（a）

2NN

NXkXkX2r N

NNnN NNxnW2rn

NxnNxn

2W2rnNNNNN

NNNxnW2rnNNN

xn

NxnxnN

2

0nNNN

0n

2NNN

N xnxn

NxnxnWN（b）k

N

2r

N21 2r

N

2rXk

2r1

xn

xnWN

xnWNnN2N21 2r1nN21

2r1nNxn

x

N2N21 2r1nN21

2r1n

Nr Nxn

x

N2

WNN21 2r1nN21

2rxnN

x

N2NxnxnNN21 2r

xnWN2用时间混叠构成序列yn,xnxnN

0nNyn

2 2 XkXkYkk0,2,N2证明上述算法可以得出所要求的结果假设我们用下式由序列xn构造一个有限长序列 r

xnrM0

0nM1确定MDFTYk与xn的傅立叶变换Xej之间的关系.证明(a)的结果推导一种累死于(a)的算法,N/2DFT(N为偶数)解(a)证明DFT的定义可得XkXkNN2

N

n2nN2N

N

nWn

xNmWk2m22

2N2

N2xnWn2

N mW

W

N N

k j2k当k为偶数时WN2 2N N22

nWn

xN N

N

2xnxN n02N2

k

N2NYk命题得证(b)X(b)XkNNr

2Nr

N=xnWnkxnWnk

nN

rnr=N

N

N

r rrxnWnkrr

xN

m

xr1N

mrN mW mW NN n0 N j2N j2

n0 WN N WNk

NN则WN

N

r

此时Xkxnn0rNr

n0rrNr

rMk

rn0r rkr YkXrkXej

2所以(a)得结果只是(b)r=2得一种特殊情况.2N

N

Xk

nWn

xNmWk2mN

N

N22xnWn22

xNmWk

WNk

当k为奇数时WNN

e

Xk2xnxN n0N

2xnxN

n0 xnxN

0nN1yn ynN点DFT即为奇序号DFT值Xk 假设有个DFT程序可以用来计算复序列的DFT如果我们想要计算一个实序列的DFTDFT的对称性来减x[n是长度为N的实序列，而x[nNDFTX[k]表示，它的实部和XR[k]XI[k]证明若x[n是实数，则当k0,1,2...，N1时，XR[k]＝XR[NkXI[k]＝XI[Nk]考虑两个实序列x1[nx2[n]，它的DFTX1[kX2[k]。令g[n]是g[n]＝x1[n]＋jx2[nDFT为G[kGR[kjGI[k]。如象式（8.96）定义的那样，令GOR[k、GER[k]、GOI[k]和GEI[k分别表示G[k]的实部的奇部和偶部和G[k1kN

[k]＝1

[k]

[N

[k]＝1

[NG[k]＝1{G[k]G[Nk G[k]＝1{G[k]G[Nk GER[k]、GOI[k]和GEI[kX1[kX2[k]N2v2FFTDFT。在以下几种情况下求出X1[kX2[k]所需要的实数乘法和实数加法的次数（使用该程序两次（同时将输入序列的虚部设为零）分别计算两个复N点序列的DFTX1[k2[k]（ii）Nx[n]N2x1[nx2[nn=0,1,2,(N/2)－1N/2DFTX1[kX2[k]X[k（bx[nDFT的方法。求用这个方法所需要的实数乘法和实数加法的次数。NFFTX[k证明：

x[n是长度为N的实序列，而x[n的N点DFTX[k]表示，且DFTDFT{xep[n]}Re{X[k]}XRDFT{xop[n]}jXI

[n]1{x[n]x[((n)) [n]1{x[n]x[((n)) DFT

[n]}1{X[k]X[Nk]}2

R[k]

[n]}1{X[k]X[Nk]}

[k X

[Nk]1{X[Nk]X[k]}2

R[k]jXI

[Nk]1{X[Nk]X[k]}

[kXI[k]＝XI[Nk]（b）G[kX1[k{X1R[k]X2I[k]}j{X1I[k]X2R{GER[k]GOR[k]}j{GEI[k]GOI[kN又DFT{g[nG*[((k))]NGR[Nk]jGI[Nk]{GER[k]GOR{X1R[k]X2I[k]}

j{GEI[k]GOI[k]}j{X1I[k]X2R[kX1R[k]X2I[k]GER[k]XX

[k]X2I[k]

[k]GORXX

[k]X2R[k]

[k]GEIX1I[k]X2R[k]GOI[k]GEI X1[k]X1R[k]jX1IGER[k]jGOIX2[k]X2R[k]jX2IGEI[k]N2v时，FFTNv/2Nv4次实数乘法和3[4N(v1)4v]

次实数乘法；需2Nv3N(v12N(5NvN)当输入是N(2Nv8N（d）x[n]x

其中 是由乘法因子 引入的；需(5NvN6N)5N(v1) X(ej)X(ej2)ej2X(ej2 X[k]Wk

0kN NX[k]NX[k

2]Wk

[kN

22NkN2

（X1[k]22 22X2[k]N/2（e）x[nN/2x1[n]x[nN/2x2[n]g[nx1[njx2[n；那么由（b）X1[k]GER[k]jGOI[k]X2[k]GEI[k]jGOR[k]考虑各个步骤需要的乘法和加法，那么此算法一共需要：2Nv8N4N2N(v6次实数乘法；需要5N(v1)4NN(5v9)次实数加法。NFFTX[k所需要的次数，由（c）中的结果：4Nv次实数乘法。N(5v1X[kX(ej

2k

(ej)

2

(ej)

j2

，jB(（A(B(为实函数，3j2N

j2N

k

Y1[k]

N2A1N

k)

N2jB3N

k)

k)jB3(

X1[kX3[k]X[k1kA2k)ReY[k]X[kj1kB2k)jImY[k] 1 3

Y[k]

[k]

[K X1[kX2[kX3[kX4[kx3[nx3[Nnx[((nNx[((NnNx[((nNx3[((n1))Nx3[((n1))Nu3[n]n0时，上式化为u3[Nu3[0]，注意到u3[Nu3[0]，故只有u3[00由u3[nx3[((n1))Nx3[((n1))NU[kWkX[kWkX[kWkWkX[k] y1[nx1[nu3[nx1[nx1[Nn]u3[nu3[Nn，

U3[k

1。1

WkW

WkW（b

[k]

2。2

WkW

WkW

当n在区间0nL1之外时；当n在区间0nP1之外时序列yn的长度是多少当直接计算卷积和时，计算yn

kNN1Nk NDFTynLPDFTLP

2FFTDFT。利用这个公NFFT方法比直接计算卷积和需要较少的实数乘（a）当直接计算卷积和时ynxnhnxmhn则计算一个yn非零样本需要的实数乘法次数为mynLmFFT计算yn的步骤如下（3）计算YkXkHk（4）ynIDFTYk，NDFT和 （1（2（4）

N次相乘，还有步骤N 3NlogNNN13v2 2 NmdLPFFT 8.9.3节中我们曾表明,线性实不变滤波可以用以下步骤来实现:先把输入信号分成有限长的信号段,然后用DFT来实现这些信号段的循环卷积.曾讨论过的两种方法称为重叠相加法和保留法.如果用一个FFT算法来计算DFT,则这些分段的方法计算每个假设复输入序列xn是有限长的且复冲激响应hn有7个样本因此只有0nP1时hn0.还假设 保留法利用由基2FFT算法实现的长L2vDFT来计算输出.式,且该式为vP的函数假设冲激响应的长度为P=500.利用(a)得出的公式并使用保留法,绘出每个输出样本的乘法次数作为v之函数的曲线v20.v为何值时乘法次数最少?比较用FFT的保留法计算每个输出样本所需的复数乘法次数与直接计算卷积何所需要的每个输出样本的复数乘法次数.证明,当FFT很长时,计算每个输出样本的复数乘法次数大约为v.因此,FFT长度,保留法就没有直接法来得效率高.若P=500,则v为何值时直接法将更FFT的长度是冲激响应长度的两倍(L=2P),Lzv.利用(a)的公式,P的最小值,使得用FFT的保留法所需用的复乘法次数比直接卷积法来得少. y[n]aky[nk]＋bkx[nkk kFFTN2vDFTFFTj(2HHz

512 y[n]aky[nk]＋bkx[nkk kx[n][nh[n]LTIh[n0,(n0)h[n512h[n512j2 DFT{hˆ[n]}H(e5129.37一个长度为N的序列xn的离散哈特利（Hartley）变换（DHT）定NXHkxnHNnkNHNaCNaSN

k0,1,,N1，(P9.37- CNa

N

SNasin

N1942年提出该方法是针对连续时间的情况，但是哈特利变换也具有对离散时间情况十分有用和引人注目的特性（Bracewell,1983,1984。具体讲，由式（P9.37-1）DHT也是一个实序列。DHT也具有卷积性质，DFT完全相似，DHT也具有在使用中必须考虑的隐含周期性。这就是说，如果认为xn式一个有限长序列，使得当n0和nN1时xn0，则可以构成一个

xn

r

示，DHSDHT。(a)DHS的分析方程式定义为XN~k1xXN

nk

DHSN~~N

对所有XH XHHNnk也是正交的，NH

mkN

mN

利用这一性质和式（P9.37-2）DHSDHSxn

XN

kHN

3xn

N1HNH

n0,1,,N

用式（P9.37-1）和式（P9.37-4）DHT分析关系式和综合关系式的定义，我们(c)HNaHNaNHNaHNabHNaCNbHNaSN。HNbCNaHNbSN考虑一个循环移位序列x1n，它定义

n0,1,,N1 0x1n 0

换句话说，x1n是从移位周期序列~xnn0中抽取一个周期而得到的序列（c）DHS系数是

~