离散卷积的定义：

将两个离散序列中的数，按照规则，两两相乘再相加的操作。

卷积运算：

的长度是 ， 的长度是 ， 的长度是

计算卷积的过程：序列翻转，移位，相乘，取和

计算举例：

其中k等于a的长度。

翻转移位相乘的操作如下：

代码实现：

Matlab代码：

a=[1,2,3];
b=[2,3,1];
y=conv(b,a);

C++代码：

这里实现的主要问题有几个：

1.k的取值范围：和a的长度相关

2.b的下标，如果按照公式来看的话比较直接，但是按照翻转移位来写就会比较令人迷惑

3.卷积满足交换律

void convolution(int a[],int b[],int NA,int NB)
{
	int NC=NA+NB-1;
	int *c=(int *)malloc(sizeof(int)*NC);
	memset(c,0,sizeof(int)*NC);
	for(int n=0;n<NC;n++)
	{
		for(int k=0;k<NA;k++)
		{
			int bindex=n-k;
			if(bindex>=0&&bindex<NB)
			{
				c[n]+=a[k]*b[bindex];
			}
		}
	}
	for(int n=0;n<NC;n++)
		printf("%d ",c[n]);
}

离散卷积与傅里叶变换的关系：

图源自：快速傅里叶变换：算法与应用

使用matlab代码验证

clear;
a=[1,2,3];
b=[2,3,1];
c1=conv(a,b);
na=length(a);
nb=length(b);
for i=na+1:na+nb-1
    a(1,i)=0;
end
for i=nb+1:na+nb-1
    b(1,i)=0;
end
FA=fft(a);
FB=fft(b);
FC=FA.*FB;
c2=ifft(FC);

这个代码里的pad0的长度只需要大于等于na+nb-1即可，可以设置的更大。

c1: 2     7    13    11     3
c2: 2.0000    7.0000   13.0000   11.0000    3.0000