发布时间 : 星期二 文章SoCVista8.快速卷积更新完毕开始阅读995c8066f5335a8102d22076
第八章、快速卷积
众所周知，卷积是数字信号处理中最常见也是最重要的计算之一。利用卷积可以实现相关计算和FIR滤波等等。正因为卷积如此重要，所以半个世纪以来学者们提出了多种不同卷积实现结构，这些结构各有优点，针对不同应用可以灵活选择。这里我们重点讨论快速卷积，顾名思义，快速卷积重点在一个“快”，如果对卷积速度要求较高，那么本章的设计方法就
一个奢侈的想法——“能不能在保证高速的前提下，尽可能的降低面积和功耗呢？”快速卷积就是这么一种抠门的卷积计算
是理想的工具。为了提高速度，就要牺牲面积和功耗！
方法：在保证速度的前提下，尽可能使用简单运算（加法）来代替复杂运算（乘法），同时还有利于计算共享，从而节约面积，与此同时功耗也能得到一定程度的改善。
本章的任务：
弄清楚以下5个问题，
1） 简单运算代替复杂运算到底意味着什么？
2） 快速卷积的Cook-Toom算法及改进Cook-Toom算法，如何根据化简出来的符号多项
式构造卷积计算矩阵（线性卷积）。
3） 快速卷积的Winograd算法及改进Winograd算法，（同上）如何根据化简出来的符号多
项式构造卷积计算矩阵（线性卷积/循环卷积）。 4） 课后思考：如何挖掘快速卷积中的计算共享？
5） 课后思考：为什么说快速卷积节约面积的同时也改善了功耗，体现在哪些方面？
在正式讲解快速卷积之前，先来看一个简单运算代替复杂运算的例子。巧的是这个例子的结论正好可以用到快速卷积的设计中，届时将给出不同于课本上快速卷积例题的设计结果。
例1、 考虑如下复数乘法
?a?j?b??c?j?d???ac?bd??j??ad?bc?
将其写成矩阵形式，有
?ac?bd??c?ad?bc???d????d??a???? c???b?从矩阵式中，可以看出一对复数相乘，需要4次乘法和2次加法。相同的功能，如果采用下
面的计算过程
?c?d?ac?bd??101???ad?bc???011???0?????0?0c?d00??10??01???a? 0??????b???d????1?1??新的矩阵计算方式只需要3次乘法3次加法。这里要说明一点，从应用角度说，c-d和c+d
所涉及的两次加法是不占计算量的。实际应用时，c+j*d是固定不变的，只是a+j*b不断改变，所以c-d和c+d在计算开始前已经算好，不再改变，所以说在迭代过程中c-d和c+d不占计算量。这个现象对应于利用卷积实现FIR滤波时，h(n)序列是固定不变的，只是输入x(n)不断更新。
代码 1
> > >
实际上卷积有三种表示， 1） 最常见的求和形式
s?n???h?m??x?n?m?
m?0N?12） 矩阵形式（有限长序列卷积）
?s0??h0?s???h?1??1??s2????0
0??x0?h0????x?
?1?h1??
2?2卷积
?s0??h0?s??h?1???1?s2??0????s3??03） 多项式相乘形式
0h0h100??x0?0????x? h0??1?x2?????h1?
2?3卷积
s0?s1p?????sN?L?2pN?L?2??h0?h1p?????hN?1pN?1??x0?x1p?????xL?1pL?1?
求和形式是卷积最常用的定义，直观的操作是：固定h(n)，反转x(n)并右移n个单位，与h(n)的对应点相乘并求和得s(n)；此外，还可以固定x(n)，反转h(n)并右移n个单位，与x(n)的对应点相乘并求和得s(n)。对于有限长序列的卷积矩阵形式也正好体现了反转右移的特点，观察2?2卷积和2?3卷积的矩阵形式，这里反转h(n)，矩阵从第一行到最末行正对应于h(-n)逐步右移。N?L尺寸的卷积可依此规律写出。
对于卷积的多项
式形式，令p?z?1，不就是说时域的卷积等于频域的乘法吗！即
???s?n????S?z?,h?n????H?z?,x?n????X?z?
s?n??h?n??x?n??S?z??H?z??X?z?
快速卷积算法，就是以卷积的多项式表示来进行构造的。如果你对该形式感到疑惑，可以动
手算算验证一下。以下分别用矩阵形式和多项式形式计算2?2卷积，可以看出两种形式结果相同。
代码 2
> > > > > 再回头看看例1的复数乘法，注意到卷积的矩阵形式，快速卷积的目的在于将卷积矩阵式变形为如下
?c?dac?bd101???????ad?bc??011???0?????0?0c?d00??10??a????0???01???? ?b???d?1?1???形式的计算过程，显然这种计算过程减少了乘法次数，代价就是增加加法次数。也就是所谓的弱计算换强计算，体会到这一点，就完成本章任务一了。
快速卷积主要有基于拉格朗日插值公式的Cook-Toom算法和基于中国剩余定理（CRT）的Winograd算法。在学习的过程中，我们不需要过分纠缠于这两种方法的数学证明，默认其正确并掌握其构造快速卷积矩阵的步骤即可。
Cook-Toom用于小尺寸的线性卷积，而Winograd算法可用于尺寸稍大的线性卷积和循环卷积。值得一提的是，实际应用的卷积尺寸往往很大，不太可能是2x2或2x3这种尺寸，那么是不是说本章的内容没有应用价值了呢？其实不然，就像单独评价一块砖头，看不出它有啥了不起，但是如果你明白高楼大厦是由一块块砖头砌成的，你就不会小看它。本章的设计结果不一定是直接用于卷积计算，可以和多相分解（即交叉分解）或分块分解结合起来，将显示出其“巨大的威力”。多相分解和分块分解在第九章讨论，这里首先牢牢掌握快速卷积的Cook-Toom和Winograd设计法。
第一节、 Cook-Toom 算法
Cook-Toom算法基于拉格朗日插值定理来构造卷积的结果多项式S(p)。拉格朗日定理表述如下：
设?0,?1,...,?n为?a,b?上n+1个互不相同的点。如果在点?i（i?0,1,...,n）处的函数值Si已知，则存在唯一的次数不高于n的多项式S?p?使得S?p?出
np??i?Si，该多项式有下式给
S?p???Sii?0j?0,j?in??p???in??j???j?
j?0,j?i
其实拉格朗日插值不难理解，n阶多项式共有n+1个待定系数，而n+1个互不相同的点对
??i,Si?正好用于构造
n+1个线性方程，容易证明该方程组存在唯一解，所以可唯一确定
S?p?，从另一个角度也可以利用拉格朗日插值公式得出相同的S?p?。
下面我们所关心的是，卷积和拉格朗日插值
有什么关系？快速卷积又在何方？
前面说到卷积可以表示成多项式乘法，考虑N?L线性卷积，其中