DSP_12离散傅立叶变换-循环卷积

1、利用循环卷积计算线性卷积利用循环卷积计算线性卷积 Linear Convolution Computation by Circular Convolution2022-6-272一个问题一个问题许多实际问题中常需要计算线性卷积，如一个许多实际问题中常需要计算线性卷积，如一个FIR数字数字滤波器的输出就等于输入与滤波器的单位取样响应的滤波器的输出就等于输入与滤波器的单位取样响应的线性卷积。而循环卷积可以利用后面介绍的线性卷积。而循环卷积可以利用后面介绍的FFT进行快进行快速计算，因此就提出一个问题：如何利用循环卷积计速计算，因此就提出一个问题：如何利用循环卷积计算线性卷积，或者是，算线性卷积，或

2、者是，在什么条件下循环卷积等于线在什么条件下循环卷积等于线性卷积？性卷积？2022-6-273一个结论一个结论设进行线性卷积的两个序列设进行线性卷积的两个序列 和和 的长度分的长度分别为别为 M 和和 N，则在它们的后面添加零使它们成为长度，则在它们的后面添加零使它们成为长度的序列，再求它们的的序列，再求它们的 L 点的循环卷积，结果序列长度点的循环卷积，结果序列长度为为 L 。则循环卷积结果就是线性卷积，即。则循环卷积结果就是线性卷积，即 nx1 nx21NML 1212x nxnx nxn2022-6-274利用利用FFT进行线性卷积计算进行线性卷积计算根据上面结论，利用根据上面结论，利用

3、FFT计算两序列的线性卷积过程如计算两序列的线性卷积过程如下。设进行线性卷积的两序列为下。设进行线性卷积的两序列为 和和n=length(x1); m=length(x2); L=m+n-1y=ifft(fft(x1,L).*fft(x2,L); nx1 nx22022-6-275为什么在序列扩展成长度为什么在序列扩展成长度 后它们的循环卷积就后它们的循环卷积就是它们的线性卷积。是它们的线性卷积。1NML5N8M12L反折2右移1L右移 0y 2y1Ly图形解释图形解释2022-6-276圆周卷积(循环卷积)和线性卷积间的关系1120( )()( )NNmrx mx nrNm Rn1120(

4、)()( )NNrmx m x nrNm Rn()( )lNry nrNRn对x1(n)和x2(n)补零，使其长度均为N点；222( )( )()Nrx nxnx nrN对x2(n)周期延拓：1120( )( )() ( )NcNNmy nx m xnmRn圆周卷积：2022-6-277121NNNN即 当圆周卷积长度时， 点圆周卷积能代表线性卷积12( )1ly nNN而的长度为( )( )NclNy ny n点圆周卷积是线性卷积以 为周期的周期延拓序列的主值序列。12-1( )lNNNy nN只有当时，以 为周期进行周期延拓才无混叠现象N1212( ) ( )( )*( )x nx nx

5、nx n1212102NNNnNN圆周卷积和线性卷积间的关系2022-6-278频率取样频率取样 Frequency Sampling频率取样是指对序列的傅立叶变换或系统的频率特性进行频率取样是指对序列的傅立叶变换或系统的频率特性进行取样。本节讨论在上面条件下能够用得到的频谱取样值无取样。本节讨论在上面条件下能够用得到的频谱取样值无失真地恢复原信号或系统。失真地恢复原信号或系统。设任意长序列设任意长序列 绝对可和，其绝对可和，其Z变换为变换为如果在单位圆上对如果在单位圆上对 进行等角距取样，取样点数为进行等角距取样，取样点数为 M，则得则得 nx nnznxzX zX nkMnWzWnxzXk

6、XkM2022-6-279频率取样频率取样 Frequency Sampling根据根据DFT的定义，对的定义，对 求反变换得求反变换得代入代入 ，得，得而而 nkMMkpWkXMnx101 kX kX 101010111MkmnkMmnkMMkmkMmnkMMkpWMmxWWmxMWkXMnxrMnmrMnmWMMkmnkM, 0, 11102022-6-2710频率取样频率取样 Frequency Sampling所以所以该式表明，该式表明，在在Z平面的单位圆上对序列的平面的单位圆上对序列的Z变换进行等角距变换进行等角距取样，将导致时间序列的周期化取样，将导致时间序列的周期化。这一结果与对

7、连续时间。这一结果与对连续时间信号取样导致频谱周期化类似。信号取样导致频谱周期化类似。 是一个周期序列，是一个周期序列，其主值为其主值为 rprMnxnx nxp nRrMnxnRnxnxNrNpN2022-6-2711频率取样频率取样 Frequency Sampling在在 为有限长度为有限长度 N 的情况下，如果取样点的情况下，如果取样点 ，那么那么 周期延拓的结果不会产生混叠。这时周期延拓的结果不会产生混叠。这时 的主值的主值 与原序列与原序列 一样，因此一样，因此 完全能代完全能代表原序列表原序列 。如果。如果 ，则，则 周期延拓后一定周期延拓后一定产生混叠，因而产生混叠，因而 不能

8、无失真地代表原信号不能无失真地代表原信号 。在。在 为无限长的情况下，对为无限长的情况下，对Z变换取样必然导致混叠失真，因变换取样必然导致混叠失真，因此此 不能代表原序列不能代表原序列 。用。用MATLAB演示：演示：x=1:8; xf=freqz(x, 1, 6, whole); ifft(xf) nxNM nx nxp nxN nx nxN nxNM nx nxN nx nx nxNx=1:8; xf=freqz(x, 1, 8, whole); ifft(xf)2022-6-2712频率取样频率取样 Frequency Sampling对于长度为对于长度为 N 的有限长序列，对的有限长序

9、列，对Z变换取样即频率取样不变换取样即频率取样不失真的条件是取样点数失真的条件是取样点数 M 应等于或大于原序列的长度应等于或大于原序列的长度 N，即即 。在。在 时，时，Z变换的取样即变换的取样即DFT，也，也即即 ，利用，利用IDFT公式可由公式可由 恢复原序列恢复原序列 ，即，即进一步利用进一步利用Z变换公式还可恢复变换公式还可恢复Z变换，变换，NM kX nx nkNNkWkXNnx101NM kX2022-6-2713频率取样频率取样 Frequency Sampling即即或或其中其中 101101101010101011111111NkkNNNkkNNNkNNkNnnnkNnnkNNnNknNnzWzkXNzWzWkXNzWkXNzWkXNznxzX 10NkzkXzX 111zWNzzkNN该式是用该式是用 在单位圆上的在单位圆上的N个取样值表示个取样值表示 的的内插公式内插公式这个是这个是内插函数内插函数 zX zX2022-6-2714频率取样频率取样 Frequency Sampling将将 代入内插公式，便得到傅立叶变换的内插公式代入内插公式，便得到傅立叶变换的内插公式其中其中函数函数 在在 时的模值均为时的模值均为