当前位置：文档之家 › 第三章 离散傅里叶

第三章 离散傅里叶

  • 格式：ppt
  • 大小：3.43 MB
  • 文档页数：65

下载文档原格式

  / 65

合集下载

数字信号第三章 离散傅里叶变换

数字信号第三章 离散傅里叶变换

第三章离散傅里叶变换DFT: Discrete Fourier Transform第三章学习目标z理解傅里叶变换的几种形式z掌握离散傅里叶变换(DFT)及性质，圆周移位、共轭对称性，掌握圆周卷积、线性卷积及两者之间的关系z掌握频域抽样理论z掌握DFT的应用引言DFT要解决两个问题：一是频谱的离散化；二是算法的快速计算(FFT)。

这两个问题都是为了使计算机能够实时处理信号。

Fourier变换的几种可能形式时间函数频率函数连续时间、连续频率—傅里叶变换连续时间、离散频率—傅里叶级数离散时间、连续频率—序列的傅里叶变换可以得出一般的规律：一个域的离散对应另一个域的周期延拓；一个域的连续必定对应另一个域的非周期。

−jwndw e jwn 时域离散、非周期频域连续、周期z 时域周期化→频域离散化z 时域离散化→频域周期化离散连续周期性非周期性引言Fourier变换的几种可能形式时间函数频率函数连续时间、连续频率—傅里叶变换连续时间、离散频率—傅里叶级数离散时间、连续频率—序列的傅里叶变换离散时间、离散频率—周期序列的傅里叶级数由DTFT到DFS离散时间、离散频率的傅立叶级数（DFS）由上述分析可知，对DTFT，要想在频域上离散化，那么在时域上必须作周期延拓。

对长度为M的有限长序列x(n)，以N为周期延拓（N≥M）。

注意：周期序列的离散傅里叶级数（DFS）只对有限长序列作周期延拓或周期序列成立。

……四种傅里叶变换形式的归纳时间函数频率函数连续和非周期非周期和连续连续和周期(T0)非周期和离散(Ω=2π/T)离散(T)和非周期周期(Ωs=2π/T)和连续离散(T)和周期(T0)周期(Ωs=2π/T)和离散(Ω=2π/T)在进行DFS 分析时，时域、频域序列都是无限长的周期序列周期序列实际上只有有限个序列值有意义长度为N 的有限长序列可以看成周期为N 的周期序列的一个周期（主值序列）借助DFS 变换对，取时域、频域的主值序列可以得到一个新的变换—DFT ，即有限长序列的离散傅里叶变换3.1 离散傅里叶变换（DFT ）的定义及物理意义——有限长序列的离散频域表示x(n)的N 点DFT 是¾x(n)的z 变换在单位圆上的N 点等间隔抽样；¾x(n)的DTFT 在区间[0，2π）上的N 点等间隔抽样。

第三章离散傅里叶变换及其快速计算方法(DFT、FFT)

第三章离散傅里叶变换及其快速计算方法(DFT、FFT)

X (e jw )
（2）Z 变换 -- 提供任意序列的 z 域表示。
n

x( n)e jnw
X (z)
n


x ( n) z n
这两种变换有两个共同特征：
（1）变换适合于无限长序列 （2）它们是连续变量 ω 或 z 的函数
华北电力大学自动化系
3
3.1 问题的提出：可计算性
X (z)
而对于
n


x ( n) z n
n


x ( n) z n
找不到衰减因子使它绝对可和（收敛）。为此，定义新函 数，其 Z 变换：
华北电力大学自动化系
15
DFS 定义：正变换
X ( z)
n
x ( n) z n ~ ( n ) z n x
华北电力大学自动化系
6
3.1 问题的提出：傅里叶变换的四种形式 （3）
2. 周期连续时间信号：傅里叶级数 FS
~ (t ) x X (n 0 )
t T

时域周期频域离散
0
2 T
x(t)
~
n -
X(n 0 )e jn0t

时域连续函数造成频域是非周期的谱。 频域的离散对应时域是周期函数。
X (e jT )



T T
X (e jT )e jnT d
取样定理
n

x(nT )e jnT
1 X ( 0 ) T n
时域的离散化造成频域的周期延拓 时域的非周期对应于频域的连续
华北电力大学自动化系
8

第3章离散傅里叶变换

第3章离散傅里叶变换

j 2 kn
X (k ) X ( z) j2 k
x(n)e N ,0 k N-1 (3.3.1)
ze N
n
实际上X(k)的反变换是有限长的序列xN(n)， xN(n)=IDFT［X(k)］， 0≤n≤N-1
请问，原序列x(n)和它的频谱采样后恢复的序列xN(n)一 样吗？
频率采样定理：如果序列x(n)的长度为M，则只有当频 域采样点数N≥M时，才有
clear,close all w=linspace(0,2*pi,1000);k1=0:7;k2=0:15; X1=exp(-j*3*w/2).*sin(2*(w+eps))./sin((w+eps)/2); X2=exp(-j*3*pi*k1/8).*sin(pi*(k1+eps)/2)./sin(pi*(k1+eps)/8); X3=exp(-j*3*pi*k2/16).*sin(pi*(k2+eps)/4)./sin(pi*(k2+eps)/16); figure(1),subplot(3,1,1);plot(w,abs(X1)); subplot(3,1,2);stem(k1,abs(X2)); subplot(3,1,3);stem(k2,abs(X3)); figure(2),plot(w,abs(X1),k1*2*pi/8,abs(X2),'^r',k2*2*pi/16,abs(X3),'ok');
各种应用一般都是以卷积和相关运算为依据，或是以 DFT作为连续傅里叶变换的近似为基础。这两种理论是 DFT应用的基础。 例如：
There are applications where it is necessary to compare one reference signal with one or more signals to determine the similarity between the pair and to determine additional information based on the similarity.

第3章 离散傅立叶变换

第3章 离散傅立叶变换

由于DFS与IDFS的对称性，对周期序列乘 积，存在着频域的周期卷积公式， 若
~ f (n) ~(n) ~(n) x y
则
~ 1 ~ F ( k ) DFS [ f ( n )] N

N 1
l 0
1 ~ ~ X ( l )Y ( k l ) N

N 1
~ ~ X ( k l )Y ( l )

1 ~ ~ X ( k )Y ( k ) N


N 1
~ ~ kn X ( k )Y ( k ) w N
k 0

1 N

N 1 N 1
~ ~ ( m ) w mk Y ( k ) w nk x N N
~ ( nm )k Y ( k )w N k 0
N 1

N 1
~ ( n ) e j 2 x
/ N kn
n0
习惯上：记 W e j 2 N
/ N
，
则DFS变换对可写为
~ X (k ) ~ (n) x

1 N
N 1
~ ( n )W kn DFS x N
~ ( n ) x
n0

N 1
~ kn X ( k )W N IDFS
因此
ek N (n ) ek (n )
将周期序列展成离散傅里叶级数时，只需取 k=0 到 (N-1) 这N个独立的谐波分量，所以一个周期序列的离 散傅里叶级数只需包含这N个复指数，
~ (n) x 1 N

N 1
~ X (k )e
j 2 / N kn
K 0
利用正弦序列的周期性可求解系数

第3章 离散傅里叶变换(DFT)

第3章 离散傅里叶变换(DFT)

X(k)与x(n)均为有限长序列,但由于WknN 的周期性,X(k)隐含周 期性， 且周期均为N。 对任意整数m， 总有
k ( WN WNk mN ) , k, m, N
N 1 n 0
均为整数
( 所以,X(k)满足 X (k mN ) x(n )WNk mN ) n kn x(n )WN X (k ) n 0 N 1
k 1 X 1 x n e
n 0
2 1n 4
x n e
n 0
3

x n ( j ) n 2 2 j
n 0
3
k 2
X 2 x n e
n 0 3
3
j
2 2n 4 2 3n 4
x n e j n x n (1) n 2

DFT后的X(k)具周期性，周期为N
x(n)满足
x(n+mN)=x(n)
IDFT后的x(n)具周期性,周期为N
主值区间和主值序列
任何周期为N的周期序列 ~(n) 可以看作长度为N的有限 x
x 长序列x(n)的周期延拓序列, x(n)是 ~(n) 的一个周期。 ~(n) 中n=0到N－1的第一个周期为 ~(n) 的主值区间。 x x x 主值区间上的序列为 ~(n)的主值序列；
x((n))N表示x(n)以N为周期的周期延拓序列，
((n))N表示n对N求余，
如果 则 n=MN+n1， 0≤n1≤N-1， M为整数， ((n))N=n1
－－此运算符表示n被N除，商为M，余数为n1。
(n1) 是((n))N 的解,或称作取余数,或称作n对N取模值, 或 简称为取模值,n模N。

第三章-离散傅里叶变换(DFT)及其快速算法(FFT)

第三章-离散傅里叶变换(DFT)及其快速算法(FFT)
返回
回到本节
x(n)
IDFT[ X (k)]N

1 N
N 1
X (k)WNk n ,
k 0
n 0, 1,
, N 1
也可以表示为矩阵形式:
x DN1 X
DN1称为N点IDFT矩阵，定义为
1
DN1

1 N
1 1
1
1 WN1 WN2
WN( N 1)
线性性质 DFT的隐含周期性 循环移位性质 复共轭序列的DFT DFT的共轭对称性 循环卷积定理 离散巴塞伐尔定理
返回
回到本节
① 线性性质 设有限长序列x1(n)和x2 (n)的长度分别为N1和N2 ， x(n) ax1(n) bx2 (n) ，a和b为常数。
则
)
N M
xN (n) x((n))N X (k ) X ((k ))N
有限长序列x(n)的DFT变换X(k)，就是x(n)的周期延拓序列 ~x(n) 的DFS系数 X~(k ) 的主值序列
返回
回到本节
DFS与FT之间的关系:
M 1
X (k) DFS[xN (n)] x(n)WNkn n0
xN (n) xN (n)RN (n)
主值区间序列 N M , xN (n) x(n)
返回
回到本节
x8 (n) x4 (n)
返回
回到本节
周期序列DFS: N 1 X (k ) DFS[ xN (n)] xN (n)WNkn n0
M 1

x(n)WNkn
k
返回
回到本节
xN (n)
n
N
0
N

信号与系统复习资料第3章离散傅立叶变换(DFT)


1 2
1 e 12
j 2 ( k 11)
1 e 12
B
Ak
6, 6,
1k 21 k 6 101
…11…22…rr…
10 0
11 0
B 0, 0其 0它 的…k… x(n) Xc(oks)6 n 6 0 ……
0 0
6 6, k 112r 6X~(k) 6, k 1112r
NT
T0
1 f0
T0 2 f0
N
1
fs
时域离散化==>频域周期化
时域周期化==>频域离散化
N NΩ0
NT0 fs s T f0 0
-7-
§3.3 离散傅里叶级数DFS
( Discrete Fourier Series )
连续周期信号:
~xa(t) ~xa(t kT0) 基频：0 2/T0
x2 m … 5 4 3 2 1 0 5 4 3 2 1 0 … 10
x2 1m … 0 5 4 3 2 1 0 5 4 3 2 1 … 8 x2 2m … 1 0 5 4 3 2 1 0 5 4 3 2 … 6 x2 3m … 2 1 0 5 4 3 2 1 0 5 4 3 … 10
n 0
n 0
x ( n ) I D F S [ X ( k ) ] N 1 N k 0 1 X ( k ) e j2 N n k N 1 N k 0 1 X ( k ) W N n k
其中：
WN
j 2
e N
-9-
X k 与 z 变 换 的 关 系 ：
x (n ) x (n )R N (n )

x(n) x(nrN)

第3章离散傅里叶变换(DFT)09-10-1

序列的DFS级数系数的主值序列！
§3.2 离散傅里叶变换的基本性质
一. 线性性质
x1(n)和x2(n)是两个有限长序列，长度分别为N1和N2
y(n)=ax1(n)+bx2(n)
式中a、 b为常数， 即N≥max［N1, N2］， 则y(n)的N
点DFT为：
（补零问题！）
Y(k)=DFT［y(n)］=aX1(k)+bX2(k), 0≤k≤N-1
➢再 反 转 形 成 x2((-m))N ， 取 主 值 序 列 则 得 到 x2((m))NRN(m)，通常称之为x2(m)的圆周反转； ➢对x2(m)的圆周反转序列圆周右移n，形成
x2((n-m))NRN(m)； ➢当n=0,1,2,…,N-1时，分别将x1(m)与x2((n-m))NRN(m)相 乘，并在m=0到N-1区间内求和，便得到其循环卷积y(n)。
y(n) x((n m))N RN (n)
则循环移位后的DFT为
Y (k) DFT [ y(n)] DFT [x((n m))N RN (n)] WNmk X (k)
证：利用周期序列的移位性质加以证明
DFS [x((n m)) N ] DFS [~x (n m)] WNmk X~(k)
x1(n)
0
N-1
~x2 (n)
0
N-1
n n
~x2 (m)
x2 0 mN RN (m)
0
m
x2 1 mN RN (m)
0
x2
2
mN
RN
(m)
m
0
m
x2 3 mN RN (m)
0
m
y(n) x1(n) N x2 (n) ➢两个长度

数字信号处理：第3章 离散傅里叶变换(DFT)


N 1
X (k mN ) x(n)WN(kmN )n
n0
N 1
x(n)WNkn X (k)
n0
同理可证明(3.1.2)式中
x(n+mN)=x(n)
~
实际上， 任何周期为N的周期序列 x 都可以看
作长度为N的有限长序列x(n)的周期延拓序列， 而x(n)
则是
~
x
的一个周期， 即
~
x(n) x(n mN )
式和(3.2.10)式代入得到
x*(N-n)=x*ep(N-n)+x*op(N-n) =xep(n)-xop(n)
xep(n)=1/2［x(n)+x*(N-n)］ xop(n)=1/2［x(n)-x*(N-n)］
(3.2.12) (3.2.13) (3.2.14)
2. DFT的共轭对称性 (1) 如果x(n)=xr(n)+jxi(n) 其中 xr=Re［x(n)］=1/2［x(n)+x*(n)］ jxi(n)=jIm［x(n)］=1/2［x(n)-x*(n)］ 由(3.2.7)式和(3.2.13)式可得 DFT［xr(n)］=1/2DFT［x(n)+x*(n)］
n0
X(k)的离散傅里叶逆变换为
X (k) DFT[x(n)]
1 N
N 1 n0
X (n)WNkn ,
k=0, 1, &, N-1
(3.1.2)
式中，
j 2
eN
， N称为DFT变换区间长度N≥M，
通常称(3.1.1)式和(3.1.2)式为离散傅里叶变换对。 下面
证明IDFT［X(k)］的唯一性。
则 ((n))N=n1
~
例如， N 5, x(n) x(n)5,

离散傅里叶变换第三章


1 ,0 n 4 j 已知序列 x(n) ，求其傅里叶变换 X (e ) ，并在频
在频率
5 s i n ( ) j5 4 e j j n 1 j2 2 X ( e ) e e j5 1 e n 0 s i n ( ) 2 2 j k
X ( k ) D F S x ( n ) x ( n ) e n 0

N 1
2 1 j k n N N n 0
k n x ( n ) W N
式中，DFS 表示离散傅里叶级数正变换； IDFS 表示离
散傅
设离散序列x(k)是长度为N的有限长序列xN(n)的 DFT，即 xN(n)=IDFT[X(k)]， 0≤n≤N-1
隔采样
问题： xN(n)与原序列x(n)之间是怎样的关系？
3.2.2 频域采样理论
DFT 与 DFS 的 关 系 : X(k) 是 xN(n) 以 N 为 周 期 的 周 期 延 拓 序列 X(n)
正变换：
逆变换：
j t Xj ( ) xte () d t

（3.1.1）
1 j t （3.1.2） x () t Xj ( ) e d 2
X ( j )

式中， 是模拟角频率， 函数。
是一个非周期的频谱密度
3.1 几种傅里叶变换的形式
变换对示意图：
（3.1.8） （3.1.9）
1 j T j nT x ( n T ) X ( e ) e d
n
s 2 s s 2
3.1
几种傅里叶变换的形式
该变换对示意图：
图3.1.3
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

解: 由DFT的共轭对称性可知
x(n) X(k)=Fep(k) jy(n) jY(k)=Fop(k)
1 a N 1 bN F (k ) j k k 1 aWN 1 bWN
1 1 aN X (k ) Fep (k ) [ F (k ) F * ( N k )) 取主值 x((n m)) R (n) N N N 区间
时域循环移位定理
若
y(n) x((n m)) N RN (n)
Y (k ) DFT [ y (n)] WN mk X (k )
频域循环移位定理
如果X(k)=DFT[x(n)]N
ep312. m
%输入时域序列向量xn=R4(n)
%以下为绘图部分（省略，程序集中有）
图3.1.3 程序ep312.m 运行结果
ex312.m
3.2 离散傅里叶变换的基本性质
3.2.2 循环移位性质
序列的循环移位
定义： y(n) x((n m)) N RN (n)
x ( n)
周期 延拓
n 0
3
kn 4
e
n 0
3
j
2π kn 4

1 e j2πk 1 e
7
j 2π k 4
k 0 4 0 k 1, 2,3
3 j 2π kn 8
设变换区间N=8，则
X (k ) x(n)W8kn e
n 0 n 0
e
3 j πk 8
π sin( k ) 2 π sin( k ) 8
z e
j 2 k N
, ,
0 k N-1 0 k N-1
X ( k ) X (e )
j
2 k N
X(k)是在z 平面单位圆上对X(z)的N点等间隔抽样。
X(k)是在 X (e j ) 对在 [0, 2 ) N点等间隔抽样。
频域抽样能 否不失真恢 复原连续信 号
所以，由X(k)可以求得两个实序列x1(n)和x2(n)的N点DFT：
1 X 1 (k ) DFT [ x1 (n)] [ X (k ) X * ( N k )] 2
1 X 2 (k ) DFT[ x2 (n)] j [ X (k ) X * ( N k )] 2
2π cos m n N
n=0, 1, …, N－1
3.1.2 DFT与傅里叶变换和Z变换的关系
X ( z ) ZT[ x(n)] x(n) z n
n 0 kn X (k ) DFT[ x(n)]N x(n)WN x(n)e n 0 n 0 M 1 M 1 j 2 kn N
x(n) x1 (n) jx2 (n)
对x(n)求DFT得到：
X (k ) DFT{x(n)} X ep (k ) X op (k )
1 X ep (k ) DFT[ x1 (n)] [ X (k ) X * ( N k )] 2
1 X op (k ) DFT[ jx2 (n)] [ X (k ) X * ( N k )] 2
k 0, 1, , 7
x(n)的离散傅里叶变换结果与变换区间长度N的取值有关。
1． 计算以下序列的N点DFT， 在变换区间0≤n≤N－1内， 序列定 义为
(4) x(n)=Rm(n)
m1 n 0
0<m<N
X (k ) WNkn
π j ( m1) k 1 WNkm e N 1 WNk
1 xop (n) [ x(n) x* ( N n)] 2
DFT的共轭对称性
【例3.2.2】 利用DFT的共轭对称性，设计一种高效算法，通过 计算一个N点DFT，就可以计算出两个实序列x1(n)和x2(n)的N点 DFT。
解：1、直接求解，需作两次N点的DFT. 2、将两个实数序列合并为一个复数序列
M 1
k 0,1, , N 1
X (k ) X ( z) ze
X (k ) X (e j ) |
j
2π k N
k 0,1,, N 1
k 0,1,, N 1
2π k N
【例3.1.2】 设x(n)=R4(n)，X(ejω)=FT［x(n)］。分别计算
1 N 1 x(n) IDFT[ X (k )] X (k )WN kn 解: （1） N k 0
1 N N j j 2 π mn N j j 2 π ( N m ) n e e N e e N 2 2
2π j( 2 π mn ) j( mn ) 1 e N e N 2
12． 已知f(n)=x(n)+jy(n)， x(n)与y(n)均为长度为N的实序 列。 设 F(k)=DFT［f(n)］N 0≤k≤N－1 (1)
1 bN 1 aN F (k ) j k k 1 aWN 1 bWN
a, b为实数
试求X(k)=DFT［x(n)］N， Y(k)=DFT［y(n)］N
频率函数
非周期和连续 非周期和离散(Ω0=2π/T0) 周期(Ωs=2π/T)和连续 周期(Ωs=2π/T)和离散 (Ω0=2π/T0)
3.1离散Fourier变换的定义 1.定义
X (k ) DFT [ x(n)] x(n)e
n 0 N 1 j
2 nk N
nk x(n)WN n 0
0≤k≤N－1
Y(k)=X((k+l))NRN(k)
nl y(n) IDFT[Y (k )]N WN x(n)
3.2.3 循环卷积定理
循环卷积
设序列h(n)和x(n)的长度分别为N和M。h(n)与x(n)的L点循环
卷积定义为
L 1 yc (n) h(m) x((n m)) L RL (n) m0
N 1
0 k N 1
1 x(n ) IDFT [ X (k )] N
X (k )WN nk 0 n N 1 k 0
N 1
式中，WN e
j
2π N
【例3.1.1】 x(n)=R4(n), 求x(n)的4点和8点DFT。 解 设变换区间N=4，则
X (k ) x(n)W
【例3.3.1】 长度为26的三角形序列x(n)如图3.3.1(a) 所示。编写MATLAB程序验证频域采样理论。
MATLAB求解程序ep331.m如下： %《数字信号处理(第三版）》第3章例3.3.1程序ep331. % 频域采样理论验证 M=26; N=32; n=0:M; xa=0:M/2; xb= ceil(M/2)-1:-1:0; xn=［xa, xb］; %产生M长三角波序列x(n) Xk=fft(xn, 512); %512点FFT［x(n)］ X32k=fft(xn, 32); %32点FFT［x(n)］ x32n=ifft(X32k); %32点IFFT［X32(k)］得到 x32(n) X16k=X32k(1:2:N); %隔点抽取X32k得到 X16(k) x16n=ifft(X16k, N/2); %16点IFFT［X16(k)］ 得到x16(n)
1 1 bN Y (k ) jFop (k ) [ F (k ) F * ( N k )] 2j 1 bWNk

7． 证明: 若x(n)为实序列， X(k)=DFT［x(n)］N， 则X(k)为 共轭对称序列， 即X(k)=X*（N－k)； 若x(n)实偶对称， 即 x(n)=x(N－n)， 则X(k)也实偶对称； 若x(n)实奇对称， 即x(n)=－
频域循环卷积定理
3.2.4 复共轭序列的DFT
则
设x*(n)是x(n)的复共轭序列，长度为N，X(k)=DFT［x(n)］N，
DFT[ x* (n)]N X * ( N k )
0 k N 1
3.2.5 DFT的共轭对称性
且X(N)=X(0)。
* xep (n) xep ( N n)
0 n N 1
* xop (n) xop ( N n)
0 n N 1
任何有限长序列都可以表示成其共轭对称分量和共轭反对称 分量之和。
x(n) xep (n) xop (n)
0 n N 1
1 xep (n) [ x(n) x* ( N n)] 2
1 e
N 0
j
k m km
0≤k≤N－1

Company Logo
2． 已知下列X(k)， 求x(n)=IDFT［X(k)］
N j 2e N X (k ) e j 2 0 k m k N m 其它k
xop (n) 0
X (k ) X R (k )
x(n)为实序列
X (k ) X * ( N k )
前已证
X (k ) X ( N k )
X(k)为实偶序列
(3)x(n)为实奇序列 x(n)=-x(N－n)
x(n)为奇序列
xep (n) 0
X (k ) X j (k )
X(ejω)在频率区间［0，2π］上的16点和32点等间隔采样，
并绘制X(ejω)采样的幅频特性图和相频特性图。 解 由DFT与傅里叶变换的关系知道，X(ejω)在频率区
间［0，2π］上的16点和32点等间隔采样，分别是x(n)的16
点和32点DFT。调用fft函数求解本例: % DFT的MATLB计算 xn=［1 1 1 1］; Xk16=fft(xn, 16); Xk32=fft(xn, 32); %计算xn的16点DFT %计算xn的32点DFT