同济大学信号与系统第九章第4讲 dft.ppt

§9-7 离散傅里叶变换的应用
运用DFT方法,往往伴随FFT算法的实施,所谓的应用几乎成为FFT应用的同意语。
(一)快速卷积
若长度为N1的序列x (n)与长度为N2的序列h(n)作线卷积,得到:
y (n)为长度为N1+ N2 –1的有限长序列,要做N1*N2次乘法运算,当N1=N2 =N,要做N2次乘法。
信号与系统同济大学汽车学院魏学哲 ******@.
直接卷积与快速卷积
如果把求线卷积改为求圆卷积,两序列分别补零加长为为N1+ N2 –1,则有可能减少运算次数。
x(n)
y(n)
卷积
FFT
FFT
序列相乘
IFFT
x(n)
h(n)
X(k)
H(k)
X(k)H(k)
y(n)
信号与系统同济大学汽车学院魏学哲 ******@.
在快速卷积过程中,共需要2次FFT,1次IFFT,相当于3次FFT运算量,在一般数字滤波中,由h(n)求H(k)是事先计算完成放在存储器中,故只需2次FFT的运算量,若假设N1=N2 =N ,则补零后:
故需要
此外X(k)与H(k)两序列相乘,还需要2N次复乘,全部复数乘法次数为:
次复数乘法运算
随着N的增大,该运算量比N2显著减少。
信号与系统同济大学汽车学院魏学哲 ******@.
以上分析是针对两序列长度相近或相等的情况,如果一个序列很短,而另一序列很长,则需要补很多零,圆卷方案甚至增加运算量,可采用分段卷积的方法,其基本原理是将x(n)分成若干小段,每小段长度与h(n)接近,将x(n)的各小段与h(n)卷积,最后取和,仍可发挥快速卷积的优越性。
信号与系统同济大学汽车学院魏学哲 ******@.
重叠相加法
假定h(n), x(n)均为因果序列。h(n)的长度为N,如图a
x(n)长度是现将等分为若干小段,每段长M,如图b
N
h(n)
图a
图b
M
M
M
N1
X(n)
信号与系统同济大学汽车学院魏学哲 ******@.
以表示x(n)序列的第i小段(i为正整数, ),为完成
各与h(n)之圆卷积,应将长度补足至N+M-1,在图c中已用虚线示意补零。
N+M-1
N+M-1
N+M-1
N+M-1
图c
信号与系统同济大学汽车学院魏学哲 ******@.
输入序列可表示为
其中
相应地,输出序列也可分解为
信号与系统同济大学汽车学院魏学哲 ******@.
利用卷积分配律可得
由于的长度为N+M-1,而的有效长度只有M,故相邻两段的必有N-1长度的重叠。见图d
N+M-1
重叠N+M-1
重叠
图d
重叠N+M-1
信号与系统同济大学汽车学院魏学哲 ******@.
按照上述原理,此方法的运算过程可分为两部分:
首先求每个与h(n)的圆卷积,样点数为N+M-1,共需P次,求各,其原理仍按图b;
然后将取和(实际上是重叠部分的相加),即得
图e y(n)
N+N1-1
信号与系统同济大学汽车学院魏学哲 ******@.
有时,N1可能很长,以致趋于无限大,例如语音信号、地震波动信号、宇宙通信中产生的某些信号等,如果不采用分段卷积的方法将迟迟不能给出结果,而且,无法找到那样大的存储设备来满足N1的需要。因此,即使在分段措施改善速度不显著的情况下,仍有可能采用这种方法。
借助FFT不仅可完成快速卷积运算,也可利用它进行解卷积运算,具体计算公式可仿照z变换解卷积方法求得。
信号与系统同济大学汽车学院魏学哲 ******@.