第3章 离散傅里叶变换在第二章讨论了利用序列的傅里叶变换和z 变换来表示序列和线性时不变系统的方法，公式分别为：∑∞-∞=-=n nzn x z X )()(和∑∞-∞=-=n jwnjwen x e X )()(。
对于有限长序列，也可以用序列的傅里叶变换和z 变换来分析和表示，但还有一种方法更能反映序列的有限长这个特点，即离散傅叶里变换。
这就是我们这一章要讨论的问题。
离散傅里叶变换除了作为有限长序列的一种傅里叶表示法在理论上相当重要之外，而且由于存在着计算离散傅里叶变换的有效快速算法，因而离散傅里叶变换在各种数字信号处理的算法中起着核心的作用。
这一章讨论的问题有：1、 傅里叶变换的几种可能形式：至今学过很多种傅里叶变换形式，到底之间有什么不 同，需要分析一下；2、 周期序列的离散傅里叶级数(DFS)：通常的周期信号都可以表示成傅里叶级数，然后根据傅里叶级数可以得到傅里叶变换；也就是说傅里叶级数与傅里叶变换之间有一定的关系；3、 有限长序列的离散傅里叶变换(DFT)：这是我们的重点，我们会对其性质等作分析讨论；4、 DFT 的应用：学习了这种傅里叶变换，怎么用？计划作一个实验。
3.1 傅里叶变换的几种形式傅里叶变换就是建立以时间为自变量的"信号"与以频率为自变量的"频率函数"之间的某种变换关系。
都是指在分析如何综合一个信号时，各种不同频率的信号在合成信号时所占的比重。
如连续时间周期信号)()(mT t f t f +=，可以用指数形式的傅里叶级数来表示，可以分解成不同次谐波的叠加，每个谐波都有一个幅值，表示该谐波分量所占的比重。
傅里叶表示形式为：∑∞-∞=Ω=n t jn n e F t f )(⎰-Ω-=⇔22)(1T T tjn n dt et f TF （Fn 离散、衰减、非周期）。
例如周期性矩形脉冲，其频谱为 ,1,0,/)/sin(±==n Tn T n T F n πτπττ。
画出图形。
对于非周期信号，如门函数，存在这样的关系式：⎰⎰∞∞--∞∞-=⇔=dt e t f jw F dw ejw F t f jwt jwt)()()(21)(π，时域非周期连续，频率连续非周期。
画出图形。
例如序列的傅里叶变换，变换关系为：∑∞-∞=-=n jwnjwen x e X )()(，⎰-=πππdw e e X n x jwn jw )(21)(，时域为非周期离散序列，频域为周期为2π的连续周期函数。
以上三种傅里叶变换都是符合傅里叶变换所谓的是建立以时间为自变量的"信号"与以频率为自变量的"频率函数"之间的某种变换关系。
不同形式是因为时间域的变量和频域的变量是连续的还是离散而出现的。
这三种傅里叶变换因为总有一个域里是连续函数，而不适合利用计算机来计算。
那么如果时间域里是离散的，而频域也是离散的，就会适合在计算机上应用了，那么傅里叶变换会是什么形式？见书上90页图形，可见时域和频域都对应为序列的形式。
3.2 周期序列的离散傅里叶级数（DFS ）回顾一下，对于周期信号，通常都可以用傅里叶级数来描述，如连续时间周期信号)()(mT t f t f +=，用指数形式的傅里叶级数来表示为∑∞-∞=Ω=n tjn neF t f )(，可以看成信号被分解成不同次谐波的叠加，每个谐波都有一个幅值，表示该谐波分量所占的比重。
其中tj eΩ为基波，基频为Ω=2π/T （T 为周期）。
设)(~n x 是周期为N 的一个周期序列，即)(~n x =)(~rN n x +，r 为任意整数，用指数形式的傅里叶级数表示应该为)(~n x =∑∞-∞=k njkw k e X 0~，其中ω0=2π/N 是基频，基频序列为n jw e 0。
下面来分析一下第（K+rN ）次谐波nw rN k j e 0)(+和第（k ）次谐波njkw e0之间的关系。
因为ω0=2π/N ，代入表达式中，得到nw rN k j e0)(+=njkw e0，r 为任意整数。
这说明第（K+rN ）次谐波能够被第（k ）次谐波代表，也就是说，在所有的谐波成分中，只有N 个是独立的，用N 个谐波就可完全的表示出)(~n x 。
K 的取值从0到N-1。
这样)(~n x =N1∑-=10~N k njkw ke X ，N 1是为了计算的方便而加入的。
下面来看看k X ~如何根据)(~n x 来求解。
先来证明复指数的正交性：⎩⎨⎧=-=∑-=-其它为整数,0,,11))(2(m mN r k eN n n r k Nj π，注意该表达式是对n 求和，而表达式的结果取决于（k-r ）的值。
在)(~n x =N1∑-=10~N k n jkw k e X 两边都乘以rn N j e )/2(π-，并且从n=0到n=N-1求和，得到 ∑∑∑-=-=--=-=1010))(/2(10)/2(~1)(~N n N k n r k N j kN n rn N j e XNen x ππ交换求和顺序，再根据前面证明的正交性结论可以得出：)(~)(~10)/2(r X e n x N n rn N j =∑-=-π，换一个变量，有)(~k X =∑-=-102)(~N n kn N j e n x π，从)(~k X 的表达式可以看出)(~k X 也是周期为N 的周期序列，即)(~k X =)(~N k X +。
)(~n x =N1∑-=10~N kjkw k e X )(~k X =∑-=-12)(~N n Nj en x π在上面的傅里叶级数对中，n 和k 的范围是从-∞到∞。
为了表示的方便，引入变量)/2(N j N e W π-=，N 表示周期。
重新写上面的级数对。
讨论如下内容：1）)/2(N j N e W π-=，以N 为周期。
1=Nk N W ，2/2N N W W =；2）求和只对序列的一个周期的值进行，但求出的)(~k X 或)(~n x 却是无限长的； 3）由)(~n x 以N 为周期推导出)(~k X 以N 为周期；4）对于周期序列)(~n x =)(~rN n x +，因为z 变换不收敛，所以不能用z 变换，但若取)(~n x 的一个周期，则z 变换是收敛的。
∑∞-∞=-=n n z n x z X )(~)(，当取k N j e z )/2(π=时，)(~)(k X z X =，而jw e z jw z X e X ==|)()(，当k N w )/2(π=时，)(jw e X =)(~k X ，这相当于在ω=0到ω=2π的范围内，以2π/N 的频率间隔在N 个等间隔的频率上对傅里叶变换进行采样。
5）引入主值序列的概念，即序列在0~N-1区间的序列称为主值序列。
举例：例1 求)(~n x 的DFS 系数。
设)(~n x 为周期冲激串)(~n x =∑∞-∞=+r rN n )(δ，对于0≤n ≤N-1，)(~n x =)(n δ，可以求出)(~k X =∑-=1)(N n kn N W n δ=1，即对于所有的k 值，)(~k X 均相同。
)(~n x 表示成级数形式为)(~n x =∑∞-∞=+r rN n )(δ=∑∑-=-=-=10)/2(111N k knN j N k kn Ne NWN π=⎩⎨⎧=其它,0,1rN n 。
例2 设)(~n x 的周期为N=10，在主值区间内，0≤n ≤4时，)(~n x =1，在5≤n ≤9时，)(~n x =0。
画出)(~n x 的图形，则)(~k X =∑∑=-==4)10/2(410n kn j n kn e Wπ=)10/sin()2/sin()10/4(k k e k j πππ-，画出)(~k X 的幅值图。
X ~(0)=5，X ~(±1)=3.23，X ~(±2)=0，X ~(±3)=1.24，X ~(±4)=0，X ~(±5)=1，X ~(±6)=0，X ~(±7)=1.24，X ~(±8)=0，X ~(±9)=3.23，这是一个周期内的值。
设n 取5~14，即不是取主值周期，随便取一个周期，计算傅里叶级数)(~2k X ，得到的结果和在主值周期中的结果)(~k X 一样。
下面计算有限长序列)(n x =⎩⎨⎧≤≤≤≤95,040,1n n 的傅里叶变换。
∑∞-∞=-=n jwnjwen x e X )()(=∑=-4n jwne=jww j e e ----115 =)2/sin()2/5sin()2/1()2/5(w e w e w j w j --，如果将ω=2πk/10代入上式，则结果和)(~k X 一样。
)(jw e X 的幅度一个周期图如下所示：可以看出)(~k X 相当于在ω=0到ω=2π的范围内，以2π/10的频率间隔在10个等间隔的频率上对傅里叶变换进行采样。
例3 例题中得到这样一个结论，对于以N 为周期的周期序列)(~n x ，任取一个周期求得的傅里叶系数)(~2k X 与)(~n x 在主值区间（n=0~N-1）中求得的傅里叶系数)(~1k X 相同。
现在已知)(~n x 的周期为N ，)(~1k X =∑-=-102)(~N n kn N j e n x π，)(~2k X =∑=21m m n )(~n x kn N j e π2-，m1=rN+n1，m2=rN+n1+N-1，0≤n1≤N-1，证明)(~1k X =)(~2k X 。
证明：)(~2k X =∑-+++=111N n rN n rN n )(~n x kn Njeπ2-（令n-m=rN 或m=n-rN ）=∑+-+)()2()(~rN m k Nj e rN m x π=∑∑∑-+=-=-+=-+=11111112()())(~N n N m N n m N n n m mk Njem x π（后一个分量作变量m-N=n ）=∑-=++110)()(~n n k N n N W N n x =∑-=110)(~n n nkN W n x=∑-=1)(~N on nk NW n x =)(~1k X 例4（留作作业）)(~n x 的周期为N ，其DFS 系数为)(~k X 。
)(~k X 也是周期为N 的周期序列，试利用)(~n x 求)(~k X 的DFS 系数。
解：)(~k X =∑-=1)(~N on nkN W n x)(~r X =∑-=1)(~N k krN W k X =krN N k N n kn N W W n x ∑∑-=-=101])(~[=∑∑-=-=+101)()(~N n N k r n k N W n x ，⎩⎨⎧=+=∑-=+其余,0,10)(lN r n N W N k r n k N，所以)(~r X =)(~)(~r x N lN r x N -=+-。
