第 03章 离散傅里叶变换及其快速算法邹江
zoujiang@public.wh.hb.cn
3.2 离散傅里叶变换及其性质
3.2.1离散傅里叶变换 (DFT)
有限长序列的傅里叶变换称为离散傅里叶变换，简写为 DFT。
DFT可以按 3个步骤由 DFS推导出来：
①将有限长序列延拓成周期序列；
②求周期序列的 DFS；
③从 DFS中取出一个周期便得到有限长 序列的 DFT。
将 x(n)延拓成周期为 N的周期序列如上图所示。
显然有的第一个周期，即 n＝ 0到 N-1的序列称为主值序列,n=0到
N-1的范围称为主值区间。
上述两式可分别表示为其中 RN(n)是矩形序列。符号 ((n))N表示 n对模 N的余数，即这里 k是商。
同理，可以认为周期序列 的 DFS系数 是有限长序列 X(k)
周期延拓的结果，而 X(k)是 的主值序列。即由此便可以得出有限长序列的离散傅里叶变换 (DFT)的表示式为由此可见，有限长序列 x(n)的 DFT即 X(k)仍是有限长序列。
在一般情况下,X(k)是一个复量，可表示为或式中例 3,1 求有限长序列的 DFT，其中 a=0.8,N=8。
解：
因此得
X(0)=4.16114
X(1)=0.71063-j0.92558
X(2)=0.50746-j0.40597
X(3)=0.47017-j0.16987
X(4)=0.46235
X(5)= 0.47017+j0.16987
X(6)= 0.50746+j0.40597
X(7)= 0.71063+j0.92558
Matlab实现 fft1.m
将 x(n)的 Z变换与 x(n)的 DFT
进行对比，可以看出式中,表示 z平面单位圆上辐角
(k=0,1,… N-1)的 N个等间隔点。
Z变换在这些点上的取样值就是
X(k)。在图 3.4(b)中的虚线包络是单位圆 (z=ejω)上的 Z变换，即傅里叶变化 X(ejω)。
关于离散傅里叶变换 (DFT)：
序列 x(n)在时域是有限长的 (长度为 N)，它的离散傅里叶变换 X(k)也是离散、有限长的 (长度也为 N)。
n为时域变量,k为频域变量。
离散傅里叶变换与离散傅里叶级数没有本质区别,DFT实际上是离散傅里叶级数的主值,DFT也隐含有周期性。
离散傅里叶变换 (DFT)具有唯一性。
DFT的物理意义：序列 x(n)的 Z变换在单位圆上的等角距取样。
3.2.2 离散傅里叶变换的性质
DFT隐含着周期性，因此在讨论 DFT的性质时，常与 DFS的概念联系起来，并把有限长序列看作周期序列的一个周期来处理。
设 x1(n)和 x2(n)的长度都为 N，且它们对应的 DFT分别为 X1(k)和 X2(k)。
1．线性设 x3(n)=ax1(n)+bx2(n),a和 b都为常数，则若它们长度不等，取长度最大者，将短的序列通过补零加长，注意此时 DFT与未补零的 DFT不相等。
此性质可以直接由 DFT的定义进行证明。
2．对称性最常遇到的是实序列。设 x(n)是一个长度为 N的实序列，且
DFT[x(n)]=X(k)，则有这意味着或这就是说，实序列的 DFT系数 X(k)的模是偶对称序列，辐角是奇对称序列。
对于复序列也有相应的共轭对称性。
3．序列的循环移位一个长度为 N的序列 x(n)的循环移位定义为循环移位分 3步计算：
(1)将 x(n)延拓成周期为 N的周期序列 ；
(2)将 移位得 或 x((n+m))N；
(3)对 x((n+m))N取主值得 x((n+m))N·RN(n)。
这个过程如下图所示。
从图中两虚线之间的主值序列的移位情况可以看出，当主值序列左移 m个样本时，
从右边会同时移进 m个样本，而且好像是刚向左边移出的那些样本又从右边循环移了进来。因此取名,循环移位,。
显然，循环移位不同于线性移位动画演示序列循环移位后的 DFT为证明：由周期序列的移位性质得因 x((n+m))N·RN(n)是 的主值序列，所以它的 DFT就是的主值，即根据时域和频域的对偶关系，可以得出若 则
4．循环卷积设 Y(k)=Xl(k)·X2(k)，则或由上式表示的卷积称为循环卷积，常记为证明：
利用 DFT的隐含周期性，将 Y(k)周期延拓计算后再取主值
m取值的 0~N-1范围是主值区间，故因此循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是周期卷积取主值。
循环卷积的计算可用图 3.6来说明。 在图 3.6(a)中,x1(n)的 N个值按顺时针方向均匀分布在内圆周上,x2(n)的 N个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积相加就得到 y(0)。若将外圆周顺时针方向转动一格 (如图 3.6(b)所示 )，将内外圆周上对应的数值两两相乘并把乘积相加，便得到
y(1)。依次类推，可以得出 y(n)的其它值。因此循环卷积也叫做圆卷积。
图 3.7表示的是序列 x1(n)和 x2(n)的 4点 (即 N=4)循环卷积的计算过程。
图中,x1(n)=δ(n)+δ(n-1)+δ(n-2),x2(n)＝ δ(n)+1.5δ(n-1)+2δ(n-2)+2.5δ(n-3)。
这一计算过程分 5步：
(1)周期延拓 (2)折叠
(3)移位和取主值 (4)相乘
(5)相加 动画演示考虑到 DFT关系的对偶性，可以证明，长为 N的两序列之积的 DFT
等于它们的 DFT的循环卷积除以 N，即
3种卷积：
线性卷积 线性卷积不受主值区间限制 点击观看动画周期卷积循环卷积 是周期卷积取主值，在一定条件下与线性卷积相等。
两个长度都为 N的因果序列的循环卷积仍是一个长度为 N的序列，
而它们的线性卷积却是一个长度为 2N-1的序列。 点击观看动画
zoujiang@public.wh.hb.cn
3.2 离散傅里叶变换及其性质
3.2.1离散傅里叶变换 (DFT)
有限长序列的傅里叶变换称为离散傅里叶变换，简写为 DFT。
DFT可以按 3个步骤由 DFS推导出来：
①将有限长序列延拓成周期序列；
②求周期序列的 DFS；
③从 DFS中取出一个周期便得到有限长 序列的 DFT。
将 x(n)延拓成周期为 N的周期序列如上图所示。
显然有的第一个周期，即 n＝ 0到 N-1的序列称为主值序列,n=0到
N-1的范围称为主值区间。
上述两式可分别表示为其中 RN(n)是矩形序列。符号 ((n))N表示 n对模 N的余数，即这里 k是商。
同理，可以认为周期序列 的 DFS系数 是有限长序列 X(k)
周期延拓的结果，而 X(k)是 的主值序列。即由此便可以得出有限长序列的离散傅里叶变换 (DFT)的表示式为由此可见，有限长序列 x(n)的 DFT即 X(k)仍是有限长序列。
在一般情况下,X(k)是一个复量，可表示为或式中例 3,1 求有限长序列的 DFT，其中 a=0.8,N=8。
解：
因此得
X(0)=4.16114
X(1)=0.71063-j0.92558
X(2)=0.50746-j0.40597
X(3)=0.47017-j0.16987
X(4)=0.46235
X(5)= 0.47017+j0.16987
X(6)= 0.50746+j0.40597
X(7)= 0.71063+j0.92558
Matlab实现 fft1.m
将 x(n)的 Z变换与 x(n)的 DFT
进行对比，可以看出式中,表示 z平面单位圆上辐角
(k=0,1,… N-1)的 N个等间隔点。
Z变换在这些点上的取样值就是
X(k)。在图 3.4(b)中的虚线包络是单位圆 (z=ejω)上的 Z变换，即傅里叶变化 X(ejω)。
关于离散傅里叶变换 (DFT)：
序列 x(n)在时域是有限长的 (长度为 N)，它的离散傅里叶变换 X(k)也是离散、有限长的 (长度也为 N)。
n为时域变量,k为频域变量。
离散傅里叶变换与离散傅里叶级数没有本质区别,DFT实际上是离散傅里叶级数的主值,DFT也隐含有周期性。
离散傅里叶变换 (DFT)具有唯一性。
DFT的物理意义：序列 x(n)的 Z变换在单位圆上的等角距取样。
3.2.2 离散傅里叶变换的性质
DFT隐含着周期性，因此在讨论 DFT的性质时，常与 DFS的概念联系起来，并把有限长序列看作周期序列的一个周期来处理。
设 x1(n)和 x2(n)的长度都为 N，且它们对应的 DFT分别为 X1(k)和 X2(k)。
1．线性设 x3(n)=ax1(n)+bx2(n),a和 b都为常数，则若它们长度不等，取长度最大者，将短的序列通过补零加长，注意此时 DFT与未补零的 DFT不相等。
此性质可以直接由 DFT的定义进行证明。
2．对称性最常遇到的是实序列。设 x(n)是一个长度为 N的实序列，且
DFT[x(n)]=X(k)，则有这意味着或这就是说，实序列的 DFT系数 X(k)的模是偶对称序列，辐角是奇对称序列。
对于复序列也有相应的共轭对称性。
3．序列的循环移位一个长度为 N的序列 x(n)的循环移位定义为循环移位分 3步计算：
(1)将 x(n)延拓成周期为 N的周期序列 ；
(2)将 移位得 或 x((n+m))N；
(3)对 x((n+m))N取主值得 x((n+m))N·RN(n)。
这个过程如下图所示。
从图中两虚线之间的主值序列的移位情况可以看出，当主值序列左移 m个样本时，
从右边会同时移进 m个样本，而且好像是刚向左边移出的那些样本又从右边循环移了进来。因此取名,循环移位,。
显然，循环移位不同于线性移位动画演示序列循环移位后的 DFT为证明：由周期序列的移位性质得因 x((n+m))N·RN(n)是 的主值序列，所以它的 DFT就是的主值，即根据时域和频域的对偶关系，可以得出若 则
4．循环卷积设 Y(k)=Xl(k)·X2(k)，则或由上式表示的卷积称为循环卷积，常记为证明：
利用 DFT的隐含周期性，将 Y(k)周期延拓计算后再取主值
m取值的 0~N-1范围是主值区间，故因此循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是周期卷积取主值。
循环卷积的计算可用图 3.6来说明。 在图 3.6(a)中,x1(n)的 N个值按顺时针方向均匀分布在内圆周上,x2(n)的 N个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积相加就得到 y(0)。若将外圆周顺时针方向转动一格 (如图 3.6(b)所示 )，将内外圆周上对应的数值两两相乘并把乘积相加，便得到
y(1)。依次类推，可以得出 y(n)的其它值。因此循环卷积也叫做圆卷积。
图 3.7表示的是序列 x1(n)和 x2(n)的 4点 (即 N=4)循环卷积的计算过程。
图中,x1(n)=δ(n)+δ(n-1)+δ(n-2),x2(n)＝ δ(n)+1.5δ(n-1)+2δ(n-2)+2.5δ(n-3)。
这一计算过程分 5步：
(1)周期延拓 (2)折叠
(3)移位和取主值 (4)相乘
(5)相加 动画演示考虑到 DFT关系的对偶性，可以证明，长为 N的两序列之积的 DFT
等于它们的 DFT的循环卷积除以 N，即
3种卷积：
线性卷积 线性卷积不受主值区间限制 点击观看动画周期卷积循环卷积 是周期卷积取主值，在一定条件下与线性卷积相等。
两个长度都为 N的因果序列的循环卷积仍是一个长度为 N的序列，
而它们的线性卷积却是一个长度为 2N-1的序列。 点击观看动画
