利用FFT 计算卷积
一．线卷积的作用及定义
线卷积包括卷积积分和卷积和。

1．线卷积的作用
求解线性系统对任意激励信号的零态响应。

2．卷积积分
)(*)(d )()()(t h t x t h x t y =-=⎰∞
∞-τττ
3．卷积和
离散系统的时域分析是，已知离散系统的初始状态和输入信号（激励），求
离散系统的输出（响应），两种方法：递推解法和离散卷积法。

卷积和：)()()()()(n h n x m n h m x n y m *=-=
∑∞
-∞= 二．圆周卷积的定义
圆周移位：一周期为N 的周期序列, 可视为一主值序列在圆周上的循环移位。

周期序列在时间轴上
左移右移m 反时针
转称为圆周移位。

时域圆周卷积（循环卷积）
)()()(n h n x n y ⊗=()()()∑-=-=1
0)(N m N N n R m n h m x
条件：两序列实现圆卷积的条件是：长度相等，如果不相等, 可通过增补零值来
使之相等。

特点：卷积求和范围只在10-≤≤N m 有限区间进行；卷积时不作反褶平移, 而
是反褶圆移
步骤：量置换→反褶→圆移→相乘→求和。

三．两者的关系
有限长序列的圆卷积和线卷积的关系
在一般情况下，两序列的圆卷积和线卷积是不相等的，这是因为：线卷积是
平移, 结果长度为121-+=N N L ；而圆卷积是圆移，结果长度为21N N L ==。

只有
在两卷积的结果长度相时，二者才有相同的结果。

解决方法是：在作圆卷积时，通过加零的方法，使两序列的长度都增加到121-+=N N L ，此时，圆卷积的结果和线卷积同。

四．利用FFT 计算卷积
工程实际需要解决的卷积：)()()(n h n x n y *=，但其计算量很大。

而圆卷积为：)()()(n h n x n y ⊗=，便于采用FFT 算法, 故计算速度快。

若将线卷积的两个序列用增补零的方法将长度取为一致，此时两序列的离散线卷积和圆周卷积结果是相等的，这样就则可以通过圆卷积来快速计算线卷积。

1、 利用FFT 计算卷积的步骤
（1）设两序列原长度分别为：N 和M ，将长度增加到1-+≥M N L （L 为2的整数次幂）；
（2）用FFT 法求加长序列的DFT 频谱；
（3）计算两序列DFT 频谱的乘积；
（4）用IFFT 求DFT 频谱乘积的逆变换，便得两序列的离散线卷积。

2、分段快速卷积
设)(n x 为长序列，)(n h 为短序列，长度为M ，则两序列的离散线卷积可以写成如下
形式，∑∑∑-=-+=-=+-++-+-=*=101)1(1
2)()()()()()()()()(N m n K kN m N N m m N h m x m N h m x m N h m x n h n x n y
上述每个子段长度为N 。

为便于圆卷积计算，将长度通过补零加长为：1-+=M N L
x (n
0 n h (n
根据各子段()n x k 增补零的部位不一样而分两种算法。

(1) 重叠相加法
在各子段()n
的尾部增加M－1 个零，则前一子段的尾部与后一子段的首x
k
部有M－1个项是重叠的，对重叠部分的卷积须作相加计算，故称重叠相加法。

(2) 重叠舍去法
该方法是在各子段的首部增加项数, 其中第一子段前部增补M-1个零, 而以后的各子段, 其前部不是增补零, 而是重复利用前一段的后M-1个项。

此时, 由于各子段的前M-1个项重复采用了前一子段的后M-1个项，卷积结果会产生局部失真，因此，须将这前M-1个项舍去，故称重叠舍去法。