当前位置：文档之家 › 数字信号处理原理与实践 第4章

数字信号处理原理与实践 第4章

  • 格式：ppt
  • 大小：2.34 MB
  • 文档页数：64

下载文档原格式

  / 64

合集下载

数字信号处理课件第4章快速傅里叶变换FF

数字信号处理课件第4章快速傅里叶变换FF
雷达信号压缩
通过FFT对雷达信号进行频谱分析，实现雷 达数据的压缩，减小存储空间和传输带宽。
谢谢聆听
05 FFT的局限性与挑战
浮点运算的开销问题
浮点运算开销
快速傅里叶变换（FFT）算法在实 现过程中需要进行大量的浮点运 算，这可能导致计算成本较高， 尤其是在处理大规模数据时。
硬件资源需求
由于FFT的浮点运算密集特性，对 计算设备的硬件资源（如CPU、 GPU等）要求较高，需要具备高 性能的计算能力。
FFT的软件实现
C/C实现
01
使用C或C等通用编程语言实现FFT算法，具有较好的通用性和
可移植性。
优化编译器
02
利用现代编译器的优化功能，如向量化、内联等，可以提高软
件实现的计算速度。
并行计算框架
03
利用OpenMP、CUDA等并行计算框架，可以实现多核或多
GPU上的并行计算。
FFT的优化方法
算法改进
FFT的历史与发展
历史
FFT的诞生可以追溯到1960年代，其发展经历了多个阶段，包括库利-图基算法、威尔金森算法、桑德斯算法等 。
发展
随着计算机技术的不断进步，FFT算法在实现方式、精度、并行化等方面不断得到优化和改进，以满足不同应用 场景的需求。
02 FFT的基本算法
递归算法
递归算法是一种基于数学归纳法的算法，通过将问题分解为更小的子问题来解决 问题。在FFT中，递归算法将一个长度为N的DFT问题分解为两个长度为N/2的 DFT问题，直到最后分解为基本的DFT问题。
特别是在信号处理领域，FFT的应用非常广泛。
FFT与Z变换的关系
定义
Z变换是离散时间信号 到复平面上的扩展，而 FFT是频域的一种快速 计算方法。

《数字信号处理》课件第4章 (2)

《数字信号处理》课件第4章 (2)

(4-6b)
j 1
V jk (z) Fjk (z)W j (z)
(4-7)
相应的信号流图如图4.8所示。
第四章 数字滤波器的结构表示
源节 点1 1 X(z)或x(n)
a
2
3
z－ 1 b
4
吸收 节点 1 Y(z)或y(n)
图4.8 标有支路传输比的Z变换形式的流图
第四章 数字滤波器的结构表示
在图4.8中，每一个支路的传输比均列于该支路的箭头之侧。 对支路（2、4）而言，它所作的是单位延迟变换， 此时的传递
第四章 数字滤波器的结构表示
第四章 数字滤波器的结构表示
4.1 引言 4.2 数字滤波器的信号流图表示 4.3 数字网络的矩阵表示 4.4 无限冲激响应(IIR)系统的基本网络结构 4.5 转置型 4.6 有限冲激响应(FIR)系统的基本网络结构
第四章 数字滤波器的结构表示
4.1 引 言
在设计数字滤波器的过程中，通常总是根据工程指标，按一 定的设计方法或技术，正确确定能够满足所需指标要求的滤波器 的数学模型，然后利用计算机或专用硬件加以实现。为了论述方 便， 我们把滤波器数学模型的确定放到第六章数字滤波器的设计 方法中专门研究，而把数学模型的具体实现放在这里先作必要的 介绍。 而且在这一章中，我们只对该数学模型的硬件实现作必要 的讨论， 利用计算机实现的软件设计则不再赘述。
第四章 数字滤波器的结构表示
S jk (z) bjk X j (z) Rjk (z) c jkWj (z)
把它们代入式（4-6），
N
M
Wk (z) Fjk (z)Wj (z) bjk X j (z)
j 1
j 1
N
Yk (z) c jkWj (z) j 1

数字信号处理第四章

数字信号处理第四章
或叫功率密度谱函数 x x(m ) 1 [P x x()] 2 1 P x x()ej m d
即此时 Pxx (与) 为xx (一m )傅里叶变换对
1．xx(0)21 P xx，(为)d 信号x 2 的平均功率
2． Pxx() ，0 即功率谱非负
且Pxx()P，xx() Pxx(为)实P 偶xx函*(数)
然而在实际工程问题中，我们遇到的离散时间信 号或数据往往是无法用确定的数学解析式或数据链 表来表示的，有可能描述这种信号的参变量是随机 变量，我们将这类信号称为随机信号。
数字信号处理第四章
例如信号：x(t)Acos，(如t 果其)中的参变量除了时间变量t以
外， 都是常A,数和 ，那 么该信号有确定的变换规律，每一时
数字信号处理第四章
平稳随机信号的数字特征
1、数学期望
2、均方值
3、方差
4、自相关序列
5、自协方差序列 6、互相关、互协方差序列
各态历经随机信号的数字特征
1、数学期望
2、均方值
3、方差
4、自相关序列
5、自协方差序列 6、互相关、互协方离散随机信号的频谱，离 散线性系统对随机信号的响应和FIR最优滤波和线性 预测等内容，即课本的2－4节。
第四章 离散随机信号处理
数字信号处理第四章
离散时域信号和系统有时域和频域两种表示，之 前的分析和讨论都是以假定信号为确定性为基础的。 所谓确定性是指序列在每一点上的值都可以由数学 表达式，数据链表或某种法则确定，也就是说信号 的过去、当前和未来的值都是确知的。对于确定性 信号，我们可以用Z变换或者傅里叶变换来表示。
E [ x ( k ) h ( n k ) ] k
其中H ( e j 0 ) 为直流分量。

《数字信号处理—理论与实践》课件第4章

《数字信号处理—理论与实践》课件第4章
由此得到 x(n) n 3n u(n 1)
4. 围线积分法(留数法) 留数法是求Z反变换的一种有用的方法。 根据复变函数 理论， 若
X (z) x(n)z n ， Rx | z | Rx n
第 4 章 Ｚ变换
则
式中， c是X(z)的收敛域中的一条逆时针方向环绕原点的闭 合积分围线。
直接计算围线积分比较麻烦， 一般采用留数定理求解。 按照留数定理， 若函数F(z)=X(z)zn－1在围线c上连续， 在c内 有K个极点zk， 而在围线外部有M个极点zm（M和K都取有限 值）， 则有
第 4 章 Ｚ变换
2. 一般X(z)是z的有理分式， 可以表示为X(z)=B(z)/A(z)， B(z)、 A(z) 都是z的实系数多项式， 并且没有公因式。 记住了 常用序列的Z变换， 就可以将X(z)表示成简单项之和的形式， 而后求取其中的每一项Z反变换（可以查表）， 然后把求得的 每一项部分分式相加， 就得到所求的x(n)， 即若
第 4 章 Ｚ变换
（1） X(z)的收敛域为|z|>Rx－， x(n)必为因果序列， 此时 应将X(z)展开为z的负幂级数， 为此X(z)的分子、 分母应按照 z的降幂排列（或z－1升幂）；
（2） X(z)的收敛域为|z|<Rx+， x(n)必为左边序列， 此时 应将X(z)展开为z的正幂级数， 为此X(z)的分子、 分母应按照 z的升幂排列（或z－1降幂）。
1. 只在有限长度n1≤n≤n2内序列x(n)才具有非零值， 而在此 区间外x(n)=0， 即
第 4 章 Ｚ变换
x(n), n1≤n≤n2 x(n)= 0, 其他
这类序列称为有限长序列。 有限长序列的Z变换为
n2
X (z) x(n) zn nn1

数字信号处理 第4章 FFT基本思想和2种基本的FFT

数字信号处理 第4章 FFT基本思想和2种基本的FFT

= −W
W的对称性
W的可约性
2 rk WN rk = WN / 2
长序列变成短序列 若N → 2个N / 2
2 则N 2次复述乘法 →（N / 2）= N 2 / 2次复数乘法 2
从信号的特殊性上考虑
– 如奇、偶、虚、实性
W 0 X (0) X (1) W 0 = X (2) W 0 0 X (3) W
对 N = 2M ， 共可分 M 次，即 m = 0,1,L , M − 1，
8点FFT时间抽取算法信号流图
每一级有 N/2 个如下的“蝶形”单元：
xm ( p )
xm +1 ( p )
W
r N
xm (q)
−1
xm +1 (q )
算法讨论（ “级”的概念、碟形单元、 “组” 的概念、旋转因子的分布、码位倒置）
r =2l ,r =2l +1
A(k ), B(k )
C(k) = D(k) =
N / 4−1 l =0
∑x(4l)W
l =0
lk N/4
, k = 0,1,..., N / 4 −1
N / 4−1
lk x(4l + 2)WN / 4 , k = 0,1,..., N / 4 −1 ∑
k A(k) = C(k) +WN / 2 D(k), k = 0,1,..., N / 4 −1 k A(k + N / 4) = C(k) −WN / 2 D(k), k = 0,1,..., N / 4 −1
x(6)
n N
N n = 0,1,L , 2
由此得到基本 运算单元
g (0) g (1) g (2) g (3)

数字信号处理 第04章 正交变换

数字信号处理 第04章 正交变换
DCT 变换矩阵、DST 变换矩阵的 行向量。
给定：
x(n), n = 1, 2, , N
DST
定义： X s (k) =
∑ 2 N
nkπ
x(n) sin( )
N +1 n=1
N +1
k = 1, 2, , N
反变换： x(n) =
∑ 2
N +1
N k =1
X
s
(k
)
sin(
nkπ )
N +1
n = 1, 2, , N
y = Ax 3. 反变换： x = A−1 y = AT y
不需要求逆，特别有利于硬件实现
性质2：展开系数是信号在基向量上的
准确投影 ϕ2
α2
α3
ϕ3
x
α1
ϕ1
非正交基的情况下，“基向量”称为“标架 （Frame)”, 这时，展开系数不是准确投影。
性质3：正交变换保证变换前后信号的能量不变，
此性质又称为“保范(数)变换”。
2N
DCT 反变换
一阶马尔可夫过程（Markov-1):语音和图象处 理中常用的数学模型。一个随机信号 ，若其 pdf满足如下关系
p[ X (tn+1) ≤ xn+1 X (tn ) = xn , X ( tn−1) = xn−1, , X ( t0 ) = x0 ]
= p[ X (tn+1) ≤ xn+1 X (tn ) = xn ], X (tn ) X (n)
即为正交变换，或保范（数）变换
AN×N 实际上是正交矩阵， AT = A−1
(二)、正交变换的性质：
性质1：正交变换的基向量即是其对偶基

数字信号处理—原理、实现及应用(第4版)第4章 模拟信号数字处理 学习要点及习题答案

数字信号处理—原理、实现及应用(第4版)第4章 模拟信号数字处理 学习要点及习题答案

·78· 第4章 模拟信号数字处理4.1 引 言模拟信号数字处理是采用数字信号处理的方法完成模拟信号要处理的问题，这样可以充分利用数字信号处理的优点，本章也是数字信号处理的重要内容。

4.2 本章学习要点(1) 模拟信号数字处理原理框图包括预滤波、模数转换、数字信号处理、数模转换以及平滑滤波；预滤波是为了防止频率混叠，模数转换和数模转换起信号类型匹配转换作用，数字信号处理则完成对信号的处理，平滑滤波完成对数模转换后的模拟信号的进一步平滑作用。

(2) 时域采样定理是模拟信号转换成数字信号的重要定理，它确定了对模拟信号进行采样的最低采样频率应是信号最高频率的两倍，否则会产生频谱混叠现象。

由采样得到的采样信号的频谱和原模拟信号频谱之间的关系式是模拟信号数字处理重要的公式。

对带通模拟信号进行采样，在一定条件下可以按照带宽两倍以上的频率进行采样。

(3) 数字信号转换成模拟信号有两种方法，一种是用理想滤波器进行的理想恢复，虽不能实现，但没有失真，可作为实际恢复的逼近方向。

另一种是用D/A 变换器，一般用的是零阶保持器，虽有误差，但简单实用。

(4) 如果一个时域离散信号是由模拟信号采样得来的，且采样满足采样定理，该时域离 散信号的数字频率和模拟信号的模拟频率之间的关系为T ωΩ=，或者s /F ωΩ=。

(5) 用数字网络从外部对连续系统进行模拟，数字网络的系统函数和连续系统传输函数 之间的关系为j a /(e )(j )T H H ωΩωΩ==，≤ωπ。

数字系统的单位脉冲响应和模拟系统的单位冲激响应关系应为 a a ()()()t nTh n h t h nT === (6) 用DFT （FFT ）对模拟信号进行频谱分析（包括周期信号），应根据时域采样定理选择采样频率，按照要求的分辨率选择观测时间和采样点数。

要注意一般模拟信号（非周期）的频谱是连续谱，周期信号是离散谱。

用DFT （FFT ）对模拟信号进行频谱分析是一种近似频谱分析，但在允许的误差范围内，仍是很重要也是常用的一种分析方法。

数字信号处理课后答案+第4章(高西全丁美玉第三版)

数字信号处理课后答案+第4章(高西全丁美玉第三版)
一次N点FFT求得X1(k)和X2(k)。 具体方法如下：
令 y(n)=x1(n)+jx2(n) Y(k)=DFT［y(n)］ 则
这样， 通过一次N点IFFT计算就完成了计算2N点DFT。 当然还要进行由Y(k)求X1(k)、 X2(k)和X(k)的运算(运算量相对
k=0, 1, …, N－1
⎧ ⎛n⎞ ⎪ x1 ⎜ 2 ⎟ ⎪ ⎝ ⎠ x (n) = ⎨ ⎪x ⎛ n −1 ⎞ ⎪ 2⎜ 2 ⎟ ⎠ ⎩ ⎝
n = 偶数 n = 奇数
在编程序实现时， 只要将存放x1(n)和x2(n)的两个数组的元 素分别依次放入存放x(n)的数组的偶数和奇数数组元素中 即可。
运算流图。 但画图占篇幅较大， 这里省略本题解答， 请 读者自己完成。
很少)。 （2） 与（1）相同， 设 x1(n)=x(2n) n=0, 1, …, N－1 x2(n)=x(2n+1) n=0, 1, …, N－1 X1(k)=DFT［x1(n)］ X2(k)=DFT［x2(n)］ 则应满足关系式
1 X 1 ( k ) = DFT[ x1 ( n)] = Yep ( k ) = [Y ( k ) + Y * ( N − k )] 2 1 jX 2 (k ) = DFT[ jx2 (n)] = Yep (k ) = [Y ( k ) − Y * ( N − k )] 2
4． 设x(n)是长度为2N的有限长实序列， X(k)为x(n)的 2N点DFT。 (1) 试设计用一次N点FFT完成计算X(k)的高效算法。 (2) 若已知X(k) ，试设计用一次N点IFFT实现求X(k)的 2N点IDFT运算。
x1(n)和x2(n)均为实序列， 所以根据DFT的共轭对称性， 可用
② 由X1(k)和X2(k)构成N点频域序列Y(k): Y(k)=X1(k)+jX2(k)=Yep(k)+Yop(k)

数字信号处理-原理、实现及应用(第4版) 第四章 模拟信号的数字处理

数字信号处理-原理、实现及应用(第4版) 第四章 模拟信号的数字处理
（3）当未知时，由 x(n) 无法恢复原正弦信号。
结论：
正弦信号采样（2）
三点结论： （1）对正弦信号，若 Fs 2 f0 时，不能保证从采样信号恢
复原正弦信号； （2）正弦信号在恢复时有三个未知参数，分别是振幅A、
频率f和初相位，所以，只要保证在一个周期内均匀采样 三点，即可由采样信号准确恢复原正弦信号。所以，只要 采样频率 Fs 3 f0 ，就不会丢失信息。 （3）对采样后的正弦序列做截断处理时，截断长度必须 是此正弦序列周期的整数倍，才不会产生频谱泄漏。（见 第四章4.5.3节进行详细分析）。
D/A
D/A为理想恢复，相当于理想的低通滤波器，ya (t) 的傅里叶变换为：
Ya ( j) Y (e jT )G( j) H (e jT ) X (e jT )G( j)
保真系统中的应用。
在 |Ω|>π/T ，引入了原模拟信号没有的高频分量，时域上表现
为台阶。
ideal filter
•
-fs
-fs/2 o
• fs/2 fs
f •
2fs
•
•
-fs
-fs/2 o
fs/2
•
fs
•
f
2fs
措施
D/A之前，增加数字滤波器，幅度特性为 Sa(x) 的倒数。
在零阶保持器后，增加一个低通滤波器，滤除高频分量， 对信号进行平滑，也称平滑滤波器。
c
如何恢复原信号的频谱？
P (j)
加低通滤波器，传输函数为
G(
j)
T
0
s 2 s 2
s
0
s
X a ( j)
s 2
s c c
s
理想采样的恢复

《数字信号处理》第四章 相关分析

《数字信号处理》第四章 相关分析

对函数两边同时作傅立叶变换有：
F
r12( )


r12 (
)e j2f
d



x1
(t
)
x2
(t
)dtej2f d


x1
(t
)

x2
(t
)ej2f d dt

第二节 相关函数的性质
这是由于：
① r(τ)完全由它的能量谱或功率谱P(f )来决定； ② P(f ) =∣X(f )∣2
具有相同的振幅谱而不同相位谱的信号，可以 有相同的自相关函数。
第一节 相关
相关函数r(τ)存在的条件是：
信号x1(t)和x2(t)是绝对可积函数。
即：
x12
(t)dt

,
或

x(t)dt

x 2 2
(t)dt


与自相关函数相对应，如果参与相关的两个信号是
不同的信号，则其相关函数称为互相关函数。
第一节 相关
t
min
xe2 (t)

x
2
(t
)dt
1


x(t

)
y(t
)dt

2

x
2
(t
)dt

y2 (t)dt



若令
xy

x(t) y(t)dt
x2 (t)dt y2 (t)dt


则相对误差可表示为
min

1

(t

)dt

数字信号处理-第四章(加绪论共八章)精品PPT课件

数字信号处理-第四章(加绪论共八章)精品PPT课件
= 2- (cosω+cos2ω)
21
4.1.2 小结
• 四种FIR数字滤波器的相位特性只取决于 h(n)的对称性，而与h(n)的值无关。 •幅度特性取决于h(n)。 •设计FIR数字滤波器时，在保证h(n)对称的 条件下，只要完成幅度特性的逼近即可。
注意：当H(ω)用│H(ω)│表示时，当H(ω)为 奇对称时，其相频特性中还应加一个固定 相移π。
22
4.1.3 线性相位FIR滤波器的零点特性
h(n) h(N 1 n)
H z zN1H z1
N 1
N 1
H z hnzn hN 1 nzn
N 1 n0
n0
N 1
h(m)z N 1m z N 1 h m z m
m0
m0
zN 1H z1
1）若 z = zi 是H(z)的零点，则 z = zi-1 也是零点
4.1.1 线性相位的条件 线性相位意味着一个系统的相频特性是 频率的线性函数，即 ()
式中为常数，此时通过这一系统的各频率分
量的时延为一相同的常数，系统的群时延为
g
d () d
5
线性相位FIR滤波器的DTFT为
N1
H e j h n e jn H e j () H ()e j
26
截短并移位的脉冲响应
过渡带带宽＝阻带边缘频率－通带边缘频率 设计中用的通带边缘频率=所要求的通带边缘频率+(过渡带带宽/2) 27
20
例1 N=5, h (0) = h (1) = h (3) = h (4) = -1/2, h (2) = 2，求 幅度函数H (ω)。
解 Ｎ为奇数并且h(n)满足偶
对称关系 a (0) = h (2) = 2 a (1) = 2 h (3) = -1 a (2) = 2 h (4) = -1 H (ω) = 2 - cosω- cos2ω

数字信号处理 第4章 信号与系统的复频域分析

数字信号处理 第4章 信号与系统的复频域分析
有的零点和极点以及比例因子bm，就可以 确定系统函数。因此，系统函数的零点和
极点的分布反映了系统的各种特征。
系统函数往往用零点和极点在S平面上的分 布图来表示，以”○”表示零点，以”×” 表示极点，以“⊙”表示重零点，以”*” 表示重极点。
jω
×
1
○
*
-2
-1
○
01
○
2
σ
×
-1
H
(s)
s(s (s2 2s
求上式的拉氏反变换，就可以得到系统的
冲激响应为：
n
h(t) bm kie pit i 1
每一极点对应一分量 epit ,(有r重极点时对 应 t e r1 pit ），极点位置就决定了该分量 的时域性质。
在H(s)的系数都为实数时，如果有一极点
为复数，必有另一极点是该极点的共轭复 数，同时系数k也将为共轭复数，一对共轭 极点组成的响应分量仍然为实数。
系统稳定性：对于任何一个有界的激励， 稳定系统产生的响应在任何时候都是有界 的。也就是要求系统的冲激响应有界（随 着t→∞，|h(t)|将逐渐衰减到零）。系统的 冲激响应的时域性质可由系统函数的极点 位置确定，因此，系统的稳定性可由系统 函数的极点位置来判断。
1、系统函数的极点全部位于左半S平面时， 随着t→∞将逐渐衰减到零，系统稳定。因
1
F (s)estds F (s)estds
2 j C0 Ci
Ci
0
k
Re
s(sk
)
1
2
j
Ci
F
(s)e st ds
F (s)estds 0 t 0
C1
F (s)estds 0 t 0
C2

数字信号处理第四章

数字信号处理第四章

第四章线性时不变离散时间系统的频域分析一、传输函数和频率响应例4。

1传输函数分析Q4.1clear;M = input（'Enter the filter length M: '）；w = 0:2*pi/1023:2＊pi；num = (1/M）＊ones（1,M);den = ［1];h = freqz(num, den， w）;subplot（2，1,1)plot（w/pi，abs（h)）;gridtitle（’Magnitude Spectrum ｜H(e^｛j\omega｝）｜')xlabel(’\omega /\pi'）；ylabel（'Amplitude’）;subplot(2，1,2）plot(w/pi,angle(h));gridtitle（'Phase Spectrum arg[H(e^｛j\omega｝）］')xlabel(’\omega /\pi’);ylabel('Phase in radians’）;M=2 M=10 M=15幅度谱为偶对称,相位谱为奇对称，这是一个低通滤波器。

M越大,通带越窄且过渡带越陡峭。

Q4。

2使用修改后的程序P3。

1，计算并画出当w=[0,pi]时传输函数的因果线性时不变离散时间系统的频率响应.它表示哪种类型的滤波器？w = 0:pi/511：pi；num = [0.15 0 -0.15］;den = [1 —0。

5 0.7];如下图1这是一个带通滤波器.图1 图2Q4。

3对下面的传输函数重做习题Q4。

2:，式(4。

36)和式（4.37）给出的两个滤波器之间的区别是什么？你将选择哪一个滤波器来滤波，为什么？w = 0:pi/511：pi;num = ［0.15 0 —0。

15］;den = [0。

7 -0。

5 1]；如上图2也是一个带通滤波器，这两个滤波器的幅度谱是一样的，相位谱不太一样，我会选择第一个带通滤波器，因为它的相位谱更加平滑,相位失真小。

数字信号处理课件第四章1-精选文档

数字信号处理课件第四章1-精选文档

例 ： 已 知 序 列 x ( nR ) ( n ) , 将 x ( n ) 以 N 8 为 周 期 4 进 行 周 期 延 拓 成 x ( n ) ， 求 x ( nD ) 的 F S 。
解 法 一 ： 数 值 解
n k X (k) x (nW ) N n 0 N 1
x(n)W8nk
1 1N X ( l)X ( k l) 1 2 Nl 0 1 1N X l)X ( k l) 2( 1 Nl 0
N 1
例 ： 已 知 序 列 xn () Rn () ， x () n ( n 1 ) Rn () 1 4 2 5 分 别 将 序 列 以 周 期 为 6 周 期 延 拓 成 周 期 序 列 xn () 和 x () n ， 求 两 个 周 期 序 列 的 周 期 卷 积 和 。 1 2
n0
7
nk W 8 n0
3
1 e e
2 j k 8

2 j 2 k 8

e
2 j 3 k 8

X ( 4 )0 X ( 5 )1 j 1 ( 6 )0 X ( 7 )1 j 1 2 X 2
X ( 0 )4 X ( 1 )1 j2 1X ( 2 )0 X ( 3 )1 j2 1
( n ) I D F S [( Y k ) ] x () m x ( n m ) 则 y 1 2
m 0 N 1
x mx ) 1(nm ) 2(
m 0
N 1
同样，利用对称性
若 则
y () n x () n x () n 1 2
n k Y () k D F S [() y n ] y () n W N n 0

数字信号处理第4章 相关与谱分析

数字信号处理第4章 相关与谱分析

17
由DTFT的性质，时域上两个序列相乘，在频 域上是两个序列的离散时间傅里叶变换的卷积，即 加窗后序列x1(n)的频谱函数为：
18
图4.1.2矩形窗频谱函数的幅度频谱
19
图4.1.3用矩形窗函数截断余弦序列后的频谱
20
前后序列的频谱存在差异。这种差异对频谱分 ①频谱泄漏。无限长序列加矩形窗截断后，在 矩形窗频谱函数的作用下，使得X(ejω)出现了较大 的频谱扩展和向两边的波动，通常称之为频谱泄漏
1
对信号作频谱分析，实际上就是计算信号的傅 里叶变换，获得信号的频谱函数或频谱图。对于非 周期连续信号，其傅里叶变换是连续非周期函数； 对于周期的连续时间信号，其傅里叶分析是无穷级 数；离散时间序列的傅里叶变换是w的连续周期函 数。无论哪一种变换，都不便于用计算机计算。
2
一、用DFT对连续时间信号进行谱分析的原理和 公式推导 设xa(t) 为连续时间信号，对xa(t)以时间间隔T 进行采样，得到离散时间信号即序列x(n)。分别用 Xa(jΩ)和X(ejω)表示xa(t)和x(n)经过傅里叶变换后的 频谱函数，有：
3
由连续时间信号的傅里叶逆变换得： 因为x(n)是xa(t)
4
令ω=ΩT－2πk，则有
又由IDTFT的定义知：
5
对比上两式可得离散时间信号x(n)与连续时间 信号xa(t)的频谱函数关系为：
6
如果连续时间信号的频谱是有限带宽且最高角 频率为Ωc，同时抽样过程满足取样定理，即Ωs≥2Ω c，那么当时，
7
另一方面，设x(n)是有限长序列，长度为L， 其N点的DFT记为X(k)。 X(k)是X(ejω)在［0，2π）区间上的N个等间隔 采样点，即：
8
由频域取样定理知，当N≥L时，X(ejω)完全可 由X(k)确定，此时有：

《数字信号处理》 第4章

《数字信号处理》 第4章
造成倒位序的原因： 将其按标号的偶奇的不断分组， 每次分解总是将偶序列放在上面， 把奇序列放在下面。 首先最低位按0、1分为偶、奇两组， 接着次低位也按0、1分组， 依此类推
右图为描述倒位序的树状图(N=8)
5 倒位序的实现
对照表
变址功能
产生倒序数的十进制运算规律 N=2M，用M位二进制数表示，则从左至右的十进制权值为：
N 1 4
x1(2l)WNk22l
N 1 4
x1(2l
1)WNk22l1
r0
l0
l0
N1
N1
4
4
x3(l)WN kl4WN k2 x4(l)WN kl4
l0
l0
X 3(k) W N k2X 4(k),k0 ,1 ,
,N 1 2
式中
N1 4
N1 4
X3(k)DFTx3(l) x3(l)WN kl4 X4(k)DFTx4(l) x4(l)WN kl4
47线性调频变换chirp变换算法471算法原理已知序列xn0nn1是有限长序列其z变换为为适应z可沿z平面更一般的路径取值就沿z平面上的一段螺线作等分角的采样z的这些采样点zk为因此有其中a决定起始采样点z0的位置a0表示z0的矢量半径长度通常取a010表示z0的相角0表示两相邻采样点之间的角度差w0一般为正值表示螺线的伸展率图471线性调频变换在平面的螺线采样当mn即时各采样点zk就均匀等间隔地分布在单位圆上这就是求序列的dft
N
W N k(N n)W N (N k)nW N kn,
W
2 N
1
N
k
WN 2
WNk
利用这些特性，使DFT运算中有些项可以合并，并且可以 将长序列的DFT分解为几个短序列的DFT，以减少DFT的运算 次数。

数字信号处理原理与实践 第4章

数字信号处理原理与实践 第4章

-1.0000 + -1.0000 +

2．fft2和ifft2函数 调用方式 (1)Y＝fft2(x) 参数说明 如果x是向量，则与一维快速傅里叶变换fft相同。 如果x是矩阵，则计算该矩阵的二维快速傅里叶变 换，数据二维傅里叶变换fft2(x)相当于fft(fft(x))， 即先对x的列做一维傅里叶变换，然后对变换结果 的行做傅里叶变换。
4.1 离散傅里叶变换存在的问题
对于N点序列，其DFT为
X (k )

n 0
N 1
kn x(n)W N
kn x ( n) 和 WN 一般情况下， 都是复数，每计算一个值，需要作N 次复数乘法和(N-1)次复数加法，求N点的值，需要N2次复 数乘法，以及N(N-1)次复数加法。由于实一次复数乘法 需要四次实数乘法和两次实数加法，一次复数加法需要两 次实数加法。





例4-1 fft(x)函数的应用。 X=[1 4 2 3] Y=fft(x) 运行结果： Y = 10.0000 -1.0000 - 1.0000i -4.0000 1.0000i 例 4-2 ifft(x)函数的应用。 Y = [10.0000 -1.0000 - 1.0000i -4.0000 1.0000i] X=ifft(Y) 运行结果： X=1 4 2 3
以N=16为例,X(k)的第一级的分解可以得到4 个分裂基,X1(k)的第二级分解可以得到2个分 裂基,一个基-4的4点DFT和2个基-2的2点DFT, 而X2(k)和X3(k)的第二级的分解分别是基-4的 4点DFT,对N =16 的分裂基FFT 的示意图如 图所示。
4.7快速傅里叶变换的MATLAB程序实现
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

则
k X (k ) X 1 (k ) W N X 2 (k )
k=0，1，…N/2-1
N / 2k 后半部分的 X ( N / 2 k ) X1 ( N / 2 k ) WN X 2 (N / 2 k)
k X1(k ) WN X 2 (k )

这样，N点 X (k ) 的就可以用X1(k ) 和 X 2 (k ) 来表示， 分别为N/2个点的DFT。






例 4-3 fft2的应用。 X=[2 3 7 5;2 4 6 5;2 4 5 6;1 2 3 4]; Y=fft2(X); 运行结果： Y= 61.0000 -14.0000 + 7.0000i -5.0000 14.0000 - 7.0000i 0 - 7.0000i -3.0000 + 2.0000i 4.0000 - 1.0000i 1.0000 + 2.0000i 7.0000 -2.0000 + 1.0000i 1.0000 -2.0000 1.0000i 0 + 7.0000i -1.0000 - 2.0000i 4.0000 + 1.0000i 3.0000 - 2.0000i

式中将X(k)分解为偶数组和奇数组,分别令 k=2r,k=2r+1,r=0,1,2,…,N/2-1,则
令
得到两个N/2点DFT

这样，一个N点的DFT被分解为两个N/2点 的DFT。当N＝8时，上述过程如图所示：

将一个N点DFT分解为4个N/4点DFT的过程 如图所示。
是一个完整的N＝8，按频率抽选的FFT结构如 图所示。

如果N＝16，通过上述推导可以把16点的 DFT分成4个4点的DFT，其信号第一级流图 如图所示。
可以用同样的方法对X1(k)、X2(k)、X3(k)做第 三级分解,把r 为偶序号的x1(r)作N/4点的DFT, 把r 为奇序号的x1(r)作N8点的DFT。同样的, 对X2(k)、X3(k)做同样的处理。
令 X 1 (k )
x (r )W
1 r 0
N 1 2
rk N /2

x(2r )W
r 0
N 1 2
rk N /2
k=0，1，…N/2-1
X 2 (k )
x
r 0
N 1 2
rk WN 2 (r ) /2

x(2r 1)W
r 0
N 1 2
rk N /2
k=0，1，…N/2-1


由于每一级都含有N/2个蝶型单元，每一个 蝶型单元又只需要一次复数乘法，两次复 数加法，则完成一次时选FFT的总计算量为： 复数乘法次数：Mf = (N/2)log2N=MN/2 复数加法次数：Af = Nlog2N=MN
当全部FFT完成后，变换后输出的序列依照 正序排列，即存储单元中顺序放着 X(0),X(1),…,X(N-1)。但输入却不是原来的自 然顺序，而是x(0),x(4),x(2),…,x(N-1) 是由于作奇偶分开所产生的。

IFFT的流图如图
4.6 分裂基FFT算法
分裂基FFT算法又称基2/4算法，或混合基算法，它和前面 讲的基2算法有关，也和基4算法有关。基4算法比基2FFT 算法更快，从理论上说，用较大的基数可以进一步减少运 算次数，但程序过于复杂，所以一般不取基数大于8。 1984年，法国的杜梅尔和霍尔曼首先提出了“分裂基” 算法，把基2算法和基4算法结合起来，其基本思路是对偶 数序号输出采用基2算法，对奇数数序号输出采用基4算法。 由于分裂基算法是目前已知的对于N＝2M算法中具有最少 的加法次数和乘法次数，并且具有非常好的结构，因此被 认为是最好的FFT算法。后来的研究表明，该算法最接近 理论上的所需乘法次数的最小值。首先介绍一下基4FFT算 法。
第四章 快速傅里叶变换
数字信号处理原理与实践 (修订版)@NEU
离散傅里叶变换（DFT）在数字信号 处理中是最常用的运算之一，由于DFT计 算比较繁琐，在相当长的时间内并没有得 到真正的应用。直到1965年库利 (J.W.Cooley)和图基(J.W.Tukey)提出了DFT的 一种快速算法，又有桑德(G.Sande)和图基 的快速算法相继出现，之后又出现了各种 各样的DFT算法，这些方法统称为快速傅 里叶变换（FFT）。
4.1 离散傅里叶变换存在的问题
对于N点序列，其DFT为
X (k )

n 0
N 1
kn x(n)W N
kn x ( n) 和 WN 一般情况下， 都是复数，每计算一个值，需要作N 次复数乘法和(N-1)次复数加法，求N点的值，需要N2次复 数乘法，以及N(N-1)次复数加法。由于实现一次复数乘法 需要四次实数乘法和两次实数加法，一次复数加法需要两 次实数加法。
以N=16为例,X(k)的第一级的分解可以得到4 个分裂基,X1(k)的第二级分解可以得到2个分 裂基,一个基-4的4点DFT和2个基-2的2点DFT, 而X2(k)和X3(k)的第二级的分解分别是基-4的 4点DFT,对N =16 的分裂基FFT 的示意图如 图所示。
4.7快速傅里叶变换的MATLAB程序实现
运算可以用蝶形信号流图表示。

求N点的值，需要N2次复数乘法和N(N-1)次 复数加法。对于N/2点DFT有(N/2)2=N2/4次 复数乘法和(N/2)( N/2-1)次复数加法，因此， 两个N/2点DFT有N2/2次复数乘法和N( N/21)次复数加法。

把两个N/2的DFT合成一个N点DFT时，需要 N/2个蝶型运算，包括N/2次复数乘法和N 次复数加法。由于N>>1，总共的复数乘法 为，复数加法次数为，通过这样的分解， 运算量几乎可以减少到一半。
4.4 运算量进一步减少的方法
虽然前面讨论的FFT算法，已经大大减 少了运算量，但是还可以通过一些措施， 进一步减少运算量。 对于N＝2M，一共需要M级运算，每级 N/2个蝶型单元，每个蝶型单元进行一次复 数乘法，则总共需要MN/2次复数乘法，如 果＝1，－1，j，-j，则与这些因子相乘时不 作实际的复数乘法运算。
-1.0000 + -1.数 调用方式 (1)Y＝fft2(x) 参数说明 如果x是向量，则与一维快速傅里叶变换fft相同。 如果x是矩阵，则计算该矩阵的二维快速傅里叶变 换，数据二维傅里叶变换fft2(x)相当于fft(fft(x))， 即先对x的列做一维傅里叶变换，然后对变换结果 的行做傅里叶变换。





例4-1 fft(x)函数的应用。 X=[1 4 2 3] Y=fft(x) 运行结果： Y = 10.0000 -1.0000 - 1.0000i -4.0000 1.0000i 例 4-2 ifft(x)函数的应用。 Y = [10.0000 -1.0000 - 1.0000i -4.0000 1.0000i] X=ifft(Y) 运行结果： X=1 4 2 3
4.2.1 算法的推导

设N＝2M，M为正整数，N是2的M次方，如 果不满足这个条件，可以人为的加上若干 个零值点，达到这个要求。这种N为2的整 数次幂的FFT称为基2 FFT。

将 x(n) 按照奇数和偶数分解为两个序列，将N 点的DFT运 算分解为两个N/2点的DFT运算，即令n=2r，n=2r+1，r=0， 1，2，….N/2-1

MATLAB为计算快速傅里叶变换，提供了一 系列丰富的数学函数，主要有fft，Ifft，fft2， ifft2等。当所处理的数据的长度为2的幂时， 采用基—2算法进行计算，计算速度会显著 增加。所以，要尽可能使所要处理的数据 长度为2的整数次幂或者用添零方式来添补 数据使其长度成为2的整数次幂。


以N＝8为例，其自然序号是0，1，2，3， 4，5，6，7。第一次按奇偶分开，得到两 组N/2点的DFT，的序列号是0，2，4，6和 1，3，5，7。对每一组再做奇偶分开，这 时抽取后得到四组，每组的序号是0，4和2， 6和1，5和3，7。

这种从十进制看来很乱的输入顺序,实际上 是按二进制“倒序位”排列的。仍然以N=8 为例,x(0),x(1),…,x(7)对应是 x(000),x(001),x(010),x(011),x(100), x(101),x(110),x(111),将二进制码翻转得到 x(000),x(100),x(010),x(110), x(001),x(101),x(011),x(111),它们对应的十进 制序号分别是 x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)。
4.5 IDFT的快速计算方法IFFT

IDFT的快速计算方法是快速傅里叶反变换， 用英文缩写IFFT来表示，无论时选法还是频 选法的FFT算法均可用于IDFT运算。对于N 点序列，其DFT运算公式为

其IDFT运算公式为
只要将DFT运算中的改为，在将结果乘以1/N，就可以 用FFT的计算方法来实现IFFT。频域序列为输入，时域序列 为输出，所以时选FFT对应时选的IFFT，频选FFT对应频选 IFFT。对于系数1/N要做如下处理，把1/N分解为（1/2） M，在M的每一级运算都要乘以1/2，这样做的目的是为了 避免在运算过程中出现溢出。其中N为IFFT变换的点数，N ＝2M，且M为整数。
在实际运算过程中，运算量并没有如此之大， 因为在DFT运算中包含着大量的重复运算， 同时一些系数是不需要乘法运算的。
4.2 按时间抽取的基2 FFT算法

nk W 利用 N 的周期性，对称性，把长度为N点的
DFT运算逐次分解为较短序列的DFT运算。 这种方法叫时间抽取法(decimation-in-time, 缩写为DIT)，简称时选法。