卷积运算的最早使用出现在达朗贝尔于1754年出版的《宇宙体系的几个要点研究》中对泰勒定理的推导之中[3]。还有西尔维斯特·拉克鲁瓦(英语:Sylvestre François Lacroix),将类型的表达式,用在他的1797年–1800年出版的著作《微分与级数论文》中[4]。此后不久,卷积运算出现在皮埃尔-西蒙·拉普拉斯、约瑟夫·傅里叶和西梅翁·泊松等人的著作中。这个运算以前有时叫做“Faltung”(德语中的折叠)、合成乘积、叠加积分或卡森积分[5]。
卷积, 在泛函分析中, 捲積, convolution, 或译为疊積, 褶積或旋積, 是透過两个函数f, displaystyle, 和g, displaystyle, 生成第三个函数的一种数学算子, 表徵函数f, displaystyle, 与经过翻转和平移的g, displaystyle, 的乘積函數所圍成的曲邊梯形的面積, 如果将参加的一个函数看作区间的指示函数, 还可以被看作是, 滑動平均, 的推廣, 互相关和自相关的图示比较, 运算涉及函数f, displaystyle, 并假定f, displaysty. 在泛函分析中 捲積 convolution 或译为疊積 褶積或旋積 是透過两个函数f displaystyle f 和g displaystyle g 生成第三个函数的一种数学算子 表徵函数f displaystyle f 与经过翻转和平移的g displaystyle g 的乘積函數所圍成的曲邊梯形的面積 如果将参加卷积的一个函数看作区间的指示函数 卷积还可以被看作是 滑動平均 的推廣 卷积 互相关和自相关的图示比较 运算涉及函数f displaystyle f 并假定f displaystyle f 的高度是1 0 在5个不同点上的值 用在每个点下面的阴影面积来指示 f displaystyle f 的对称性是卷积g f displaystyle g f 和互相关f g displaystyle f star g 在这个例子中相同的原因 目录 1 定义 2 历史 3 简介 4 图解 5 周期卷积 6 离散卷积 6 1 多维离散卷积 6 2 离散周期卷积 7 性质 7 1 代数 7 2 积分 7 3 微分 8 卷积定理 8 1 周期卷积 8 2 离散卷积 8 3 离散周期卷积 9 推广 10 离散卷積的計算方法 10 1 方法1 直接計算 10 2 方法2 快速傅立葉轉換 10 3 方法3 分段卷積 10 4 應用時機 10 5 例子 11 应用 12 参见 13 引用 14 延伸阅读 15 外部链接定义 编辑卷积是数学分析中一种重要的运算 设 f t displaystyle f t nbsp 和g t displaystyle g t nbsp 是实数R displaystyle mathbb R nbsp 上的两个可积函数 定义二者的卷积 f g t displaystyle f g t nbsp 为如下特定形式的积分变换 f g t f t g t t dt displaystyle f g t triangleq int infty infty f tau g t tau mathrm d tau nbsp f g t displaystyle f g t nbsp 仍为可积函数 并且有着 f g t f t t g t dt g f t displaystyle f g t triangleq int infty infty f t tau g tau d tau g f t nbsp 函数f displaystyle f nbsp 和g displaystyle g nbsp 如果只支撑在 0 displaystyle 0 infty nbsp 之上 则积分界限可以截断为 f g t 0tf t g t t dt displaystyle f g t int 0 t f tau g t tau d tau quad nbsp 对于 f g 0 R displaystyle f g 0 infty to mathbb R nbsp 对于两个得出复数值的多元实变函数 英语 Function of several real variables 可以定义二者的卷积为如下形式的多重积分 f g t1 t2 tn Rnf t1 t2 tn g t1 t1 t2 t2 tn tn dt1dt2 dtn Rnf t g t t dnt displaystyle begin aligned f g t 1 t 2 cdots t n amp triangleq int int cdots int mathbb R n f tau 1 tau 2 cdots tau n g t 1 tau 1 t 2 tau 2 cdots t n tau n d tau 1 d tau 2 cdots d tau n amp triangleq int mathbb R n f tau g t tau d n tau end aligned nbsp 卷积有一个通用的工程上的符号约定 1 f t g t f t g t t dt f g t displaystyle f t g t triangleq underbrace int infty infty f tau g t tau d tau f g t nbsp 它必须被谨慎解释以避免混淆 例如 f t g t t0 displaystyle f t g t t 0 nbsp 等价于 f g t t0 displaystyle f g t t 0 nbsp 而f t t0 g t t0 displaystyle f t t 0 g t t 0 nbsp 却实际上等价于 f g t 2t0 displaystyle f g t 2t 0 nbsp 2 历史 编辑卷积运算的最早使用出现在达朗贝尔于1754年出版的 宇宙体系的几个要点研究 中对泰勒定理的推导之中 3 还有西尔维斯特 拉克鲁瓦 英语 Sylvestre Francois Lacroix 将 f u g x u du textstyle int f u cdot g x u du nbsp 类型的表达式 用在他的1797年 1800年出版的著作 微分与级数论文 中 4 此后不久 卷积运算出现在皮埃尔 西蒙 拉普拉斯 约瑟夫 傅里叶和西梅翁 泊松等人的著作中 这个运算以前有时叫做 Faltung 德语中的折叠 合成乘积 叠加积分或卡森积分 5 卷积 这个术语早在1903年就出现了 然而其定义在早期使用中是相当生僻的 6 7 直到1950年代或1960年代之前都未曾广泛使用 简介 编辑如果f displaystyle f nbsp 和g displaystyle g nbsp 都是在Lp 空间L1 Rn displaystyle L 1 mathbb R n nbsp 内的勒贝格可积函数 则二者的卷积存在 并且在这种情况下f g displaystyle f g nbsp 也是可积的 8 这是托內利定理的结论 对于在L1 displaystyle L 1 nbsp 中的函数在离散卷积下 或更一般的对于在任何群的上的卷积 这也是成立的 同样的 如果f L1 Rn displaystyle f in L 1 mathbb R n nbsp 而g Lp Rn displaystyle g in L p mathbb R n nbsp 这里的1 p displaystyle 1 leq p leq infty nbsp 则f g Lp Rn displaystyle f g in L p mathbb R n nbsp 并且其Lp范数间有着不等式 f g p f 1 g p displaystyle f g p leq f 1 g p nbsp 在p 1 displaystyle p 1 nbsp 的特殊情况下 这显示出L1 displaystyle L 1 nbsp 是在卷积下的巴拿赫代数 并且如果f displaystyle f nbsp 和g displaystyle g nbsp 几乎处处非负则两边间等式成立 卷积与傅里叶变换有着密切的关系 例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换 利用此一性質 能簡化傅里叶分析中的许多问题 由卷积得到的函数f g displaystyle f g nbsp 一般要比f displaystyle f nbsp 和g displaystyle g nbsp 都光滑 特别当g displaystyle g nbsp 为具有紧支集的光滑函数 f displaystyle f nbsp 为局部可积时 它们的卷积f g displaystyle f g nbsp 也是光滑函数 利用这一性质 对于任意的可积函数f displaystyle f nbsp 都可以简单地构造出一列逼近于f displaystyle f nbsp 的光滑函数列fs displaystyle f s nbsp 这种方法称为函数的光滑化或正则化 函数f t displaystyle f t nbsp 和g t displaystyle g t nbsp 的互相关 f g t displaystyle f star g tau nbsp 等价于f t displaystyle f tau nbsp 的共轭复数f t displaystyle overline f tau nbsp 与g t displaystyle g tau nbsp 的卷积 f g t f t t g t dt f t g t displaystyle f star g tau triangleq int infty infty overline f t tau g t dt overline f tau g tau nbsp 这里的t displaystyle tau nbsp 叫做移位 displacement 或滞后 lag 对于單位脈衝函数d t displaystyle delta t nbsp 和某个函数h t displaystyle h t nbsp 二者得到的捲積就是h t displaystyle h t nbsp 本身 此h t displaystyle h t nbsp 被稱為衝激響應 d h t d t h t t dt h t displaystyle delta h t int infty infty delta tau h t tau d tau h t nbsp 在连续时间线性非时变系统中 输出信号y t displaystyle y t nbsp 被描述为输入信号x t displaystyle x t nbsp 与冲激响应h t displaystyle h t nbsp 的卷积 9 y t x h t x t t h t dt x t h t t dt displaystyle y t x h t triangleq int limits infty infty x t tau cdot h tau mathrm d tau int limits infty infty x tau cdot h t tau mathrm d tau nbsp 两个独立的随机变量U displaystyle U nbsp 和V displaystyle V nbsp 每个都有一个概率密度函数 二者之和的概率密度 是它们单独的密度函数的卷积 fU V x fU y fV x y dy fU fV x displaystyle f U V x int infty infty f U y f V x y dy left f U f V right x nbsp 图解 编辑已知右侧第一行图中两个函数f t displaystyle f t nbsp 和g t displaystyle g t nbsp 首先將兩個函數都用约束变量t displaystyle tau nbsp 來表示 并将g t displaystyle g tau nbsp 翻转至纵轴另一侧 从而得到右侧第二行图中f t displaystyle f tau nbsp 和g t displaystyle g tau nbsp 向函数g t displaystyle g tau nbsp 增加一个时间偏移量t displaystyle t nbsp 得到函数g t t g t t displaystyle g tau t g t tau nbsp t displaystyle t nbsp 不是常数而是自由变量 当t displaystyle t nbsp 取不同值时 g t t displaystyle g t tau nbsp 能沿着t displaystyle tau nbsp 轴 滑动 如果t displaystyle t nbsp 是正值 则g t t displaystyle g t tau nbsp 等于g t displaystyle g tau nbsp 沿着t displaystyle tau nbsp 轴向右 朝向 displaystyle infty nbsp 滑动数量t displaystyle t nbsp 如果t displaystyle t nbsp 是负值 则g t t displaystyle g t tau nbsp 等价于g t displaystyle g tau nbsp 向左 朝向 displaystyle infty nbsp 滑动数量 t displaystyle t nbsp 讓t displaystyle t nbsp 從 displaystyle infty nbsp 变化至 displaystyle infty nbsp 当兩個函數交會時 計算交會範圍中兩個函數乘積的積分值 換句話說 在时间t displaystyle t nbsp 计算函数f t displaystyle f tau nbsp 经过权重函数g t t displaystyle g t tau nbsp 施以权重后其下的面积 右侧第三 第四和第五行图中 分别是t 0 displaystyle t 0 nbsp t 2 5 displaystyle t 2 5 nbsp 和t 5 5 displaystyle t 5 5 nbsp 时的情况 从t gt 1 displaystyle t gt 1 nbsp 时开始有交会 例如在第四行图中 t 0 displaystyle tau 0 nbsp 则g t t g 2 5 displaystyle g t tau g 2 5 nbsp t 1 5 displaystyle tau 1 5 nbsp 则g t t g 1 displaystyle g t tau g 1 nbsp 对于t 0 1 5 displaystyle tau notin 0 1 5 nbsp 有着f t g t t 0 displaystyle f tau g t tau 0 nbsp 最後得到的波形 未包含在此圖中 就是f displaystyle f nbsp 和g displaystyle g nbsp 的捲積 nbsp 两个矩形脈衝波的捲積 其中函数g displaystyle g nbsp 首先对t 0 displaystyle tau 0 nbsp 反射 接著平移t displaystyle t nbsp 成為g t t displaystyle g t tau nbsp 那么重叠部份的面积就相当于t displaystyle t nbsp 处的卷积 其中橫坐標代表待变量t displaystyle tau nbsp 以及新函數f g displaystyle f ast g nbsp 的自變量t displaystyle t nbsp nbsp 矩形脈衝波和指數衰減脈衝波的捲積 後者可能出現於RC電路中 同樣地重疊部份面積就相當於t displaystyle t nbsp 處的捲積 注意到因為g displaystyle g nbsp 是對稱的 所以在這兩張圖中 反射並不會改變它的形狀 nbsp 周期卷积 编辑主条目 圆周卷积 nbsp nbsp 矩形脉冲波和指数衰减脉冲波的周期卷积 两个T displaystyle T nbsp 周期的函数hT t displaystyle h T t nbsp 和xT t displaystyle x T t nbsp 的 周期卷积 定义为 10 11 t0t0 ThT t xT t t dt displaystyle int t 0 t 0 T h T tau x T t tau d tau nbsp 这里的t0 displaystyle t 0 nbsp 是任意参数 任何可积分函数 英语 Absolutely integrable function s t displaystyle s t nbsp 都可以通过求函数s t displaystyle s t nbsp 的所有整数倍P displaystyle P nbsp 的平移的总和 从而制作出具有周期P displaystyle P nbsp 的周期函数 sP t displaystyle s P t nbsp 这叫做周期求和 英语 Periodic summation sP t m s t mP m s t mP m Z displaystyle s P t triangleq sum m infty infty s t mP sum m infty infty s t mP quad m in mathbb Z nbsp 对于无周期函数h displaystyle h nbsp 与x displaystyle x nbsp 其周期T displaystyle T nbsp 的周期求和分别是hT t displaystyle h T t nbsp 与xT t displaystyle x T t nbsp h displaystyle h nbsp 与x displaystyle x nbsp 的周期卷积 可以定义为h t displaystyle h t nbsp 与xT t displaystyle x T t nbsp 的常规卷积 或x t displaystyle x t nbsp 与hT t displaystyle h T t nbsp 的常规卷积 二者都等价于hT t displaystyle h T t nbsp 与xT t displaystyle x T t nbsp 的周期积分 h xT t h t xT t t dt t0t0 ThT t xT t t dt displaystyle h x T t triangleq int infty infty h tau x T t tau d tau int t 0 t 0 T h T tau x T t tau d tau nbsp h xT t x hT t displaystyle h x T t x h T t nbsp 圆周卷积是周期卷积的特殊情况 11 12 其中函数h displaystyle h nbsp 和x displaystyle x nbsp 二者的非零部份 都限定在区间 0 T displaystyle 0 T nbsp 之内 此时的周期求和称为 周期延拓 h xT displaystyle h x T nbsp 中函数xT displaystyle x T nbsp 可以通过取非负余数的模除运算表达为 圆周函数 xT t x tmod T t R displaystyle x T t x t mathrm mod T quad t in mathbb R nbsp 而积分的界限可以缩简至函数h displaystyle h nbsp 的长度范围 0 T displaystyle 0 T nbsp h xT t 0Th t x t t mod T dt displaystyle h x T t int 0 T h tau x t tau mathrm mod T d tau nbsp 离散卷积 编辑 nbsp 离散卷积示意图对于定义在整數Z displaystyle mathbb Z nbsp 上且得出复数值的函数f n displaystyle f n nbsp 和g n displaystyle g n nbsp 离散卷积定义为 13 f g n m f m g n m m f n m g m displaystyle f g n triangleq sum m infty infty f m g n m sum m infty infty f n m g m nbsp 這裡一樣把函數定義域以外的值當成零 所以可以擴展函數到所有整數上 如果本來不是的話 两个有限序列的卷积的定义 是将这些序列扩展成在整数集合上有限支撑的函数 在这些序列是两个多项式的系数之时 这两个多项式的普通乘积的系数 就是这两个序列的卷积 这叫做序列系数的柯西乘积 當g n displaystyle g n nbsp 的支撐集為有限長度的 M M 1 M 1 M displaystyle M M 1 dots M 1 M nbsp 之时 上式會變成有限求和 f g n m MMf n m g m displaystyle f g n sum m M M f n m g m nbsp 多维离散卷积 编辑 主条目 多维离散卷积 英语 Multidimensional discrete convolution nbsp 用离散二维卷积对图像进行锐化 英语 Kernel image processing 处理的动画类似于一维情况 使用星号表示卷积 而维度体现在星号的数量上 M displaystyle M nbsp 维卷积就写为M displaystyle M nbsp 个星号 下面是M displaystyle M nbsp 维信号的卷积的表示法 y n1 n2 nM h n1 n2 nM M x n1 n2 nM displaystyle y n 1 n 2 n M h n 1 n 2 n M overset M cdots x n 1 n 2 n M nbsp 对于离散值的信号 这个卷积可以直接如下这样计算 k1 k2 kM h k1 k2 kM x n1 k1 n2 k2 nM kM displaystyle sum k 1 infty infty sum k 2 infty infty sum k M infty infty h k 1 k 2 k M x n 1 k 1 n 2 k 2 n M k M nbsp 结果的离散多维卷积所支撑的输出区域 基于两个输入信号所支撑的大小和区域来决定 nbsp 在两个二维信号之间的卷积的可视化离散周期卷积 编辑 nbsp 对比离散无周期卷积 左列 与离散圆周卷积 右列 对于离散序列和一个参数N displaystyle N nbsp 无周期函数h displaystyle h nbsp 和x displaystyle x nbsp 的 周期卷积 是为 h xN n m h m xN n m k x n m kN m 0N 1 k h m kN xN n m displaystyle h x N n triangleq sum m infty infty h m underbrace x N n m sum k infty infty x n m kN sum m 0 N 1 left sum k infty infty h m kN right x N n m nbsp 这个函数有周期N displaystyle N nbsp 它有最多N displaystyle N nbsp 个唯一性的值 h displaystyle h nbsp 和x displaystyle x nbsp 的非零范围都是 0 N 1 displaystyle 0 N 1 nbsp 的特殊情况叫做圆周卷积 h xN n m 0N 1h m xN n m m 0N 1h m x n m modN displaystyle h x N n sum m 0 N 1 h m x N n m sum m 0 N 1 h m x n m bmod N nbsp 离散圆周卷积可简约为矩阵乘法 这里的积分变换的核函数是循环矩阵 y0y1 yN 1 h0hN 1 h1h1h0 h2 hN 1hN 2 h0 x0x1 xN 1 displaystyle begin bmatrix y 0 y 1 vdots y N 1 end bmatrix begin bmatrix h 0 amp h N 1 amp cdots amp h 1 h 1 amp h 0 amp cdots amp h 2 vdots amp vdots amp ddots amp vdots h N 1 amp h N 2 amp cdots amp h 0 end bmatrix begin bmatrix x 0 x 1 vdots x N 1 end bmatrix nbsp 圆周卷积最经常出现的快速傅里叶变换的实现算法比如雷德演算法之中 性质 编辑代数 编辑 主条目 卷积代数 英语 Convolution algebra 各种卷积算子都满足下列性质 交换律 f g g f displaystyle f g g f nbsp 结合律 f g h f g h displaystyle f g h f g h nbsp 分配律 f g h f g f h displaystyle f g h f g f h nbsp 数乘结合律 a f g af g f ag displaystyle a f g af g f ag nbsp 其中a displaystyle a nbsp 为任意实数 或复数 复数共轭 f g f g displaystyle overline f g overline f overline g nbsp 微分有关 f g f g f g displaystyle f g f g f g nbsp 积分有关 如果F t tf t dt textstyle F t int infty t f tau d tau nbsp 并且G t tg t dt textstyle G t int infty t g tau d tau nbsp 则有 F g t f G t t f g t dt displaystyle F g t f G t int infty t f g tau d tau nbsp 积分 编辑 如果f displaystyle f nbsp 和g displaystyle g nbsp 是可积分函数 则它们在整个空间上的卷积的积分 简单的就是它们积分的乘积 14 Rn f g t dnt Rnf t dnt Rng t dnt displaystyle int mathbb R n f g t d n t left int mathbb R n f t d n t right left int mathbb R n g t d n t right nbsp 这是富比尼定理的结果 如果f displaystyle f nbsp 和g displaystyle g nbsp 只被假定为非负可测度函数 根据托内利定理 这也是成立的 微分 编辑 在一元函数情况下 f displaystyle f nbsp 和g displaystyle g nbsp 的卷积的导数有着 ddt f g dfdt g f dgdt displaystyle frac d dt f g frac df dt g f frac dg dt nbsp 这里的ddt displaystyle frac d dt nbsp 是微分算子 更一般的说 在多元函数的情况下 对偏导数也有类似的公式 ti f g f ti g f g ti displaystyle frac partial partial t i f g frac partial f partial t i g f frac partial g partial t i nbsp 这就有了一个特殊结论 卷积可以看作 光滑 运算 f displaystyle f nbsp 和g displaystyle g nbsp 的卷积可微分的次数 是f displaystyle f nbsp 和g displaystyle g nbsp 的总数 这些恒等式成立的严格条件 为f displaystyle f nbsp 和g displaystyle g nbsp 是绝对可积分的 并且至少二者之一有绝对可积分 L1 displaystyle L 1 nbsp 弱导数 这是Young卷积不等式 英语 Young s convolution inequality 的结论 在离散情况下 差分算子D f n f n 1 f n displaystyle Delta f n f n 1 f n nbsp 满足类似的关系 D f g Df g f Dg displaystyle Delta f g Delta f g f Delta g nbsp 卷积定理 编辑主条目 卷积定理 卷积定理指出 15 在适当的条件下 两个函数 或信号 的卷积的傅里叶变换 是它们的傅里叶变换的逐点乘积 更一般的说 在一个域 比如时域 中的卷积等于在其他域 比如频域 逐点乘法 设两个函数g x displaystyle g x nbsp 和h x displaystyle h x nbsp 分别具有傅里叶变换G s displaystyle G s nbsp 和H s displaystyle H s nbsp G s F g s g x e i2psxdx s RH s F h s h x e i2psxdx s R displaystyle begin aligned G s amp triangleq mathcal F g s int infty infty g x e i2 pi sx dx quad s in mathbb R H s amp triangleq mathcal F h s int infty infty h x e i2 pi sx dx quad s in mathbb R end aligned nbsp 这里的F displaystyle mathcal F nbsp 算子指示傅里叶变换 卷积定理声称 F g h s G s H s s R displaystyle mathcal F g h s G s H s quad s in mathbb R nbsp F g h s G s H s s R displaystyle mathcal F g cdot h s G s H s quad s in mathbb R nbsp 应用逆傅里叶变换F 1 displaystyle mathcal F 1 nbsp 产生推论 g h s F 1 G H s R displaystyle g h s mathcal F 1 G cdot H quad s in mathbb R nbsp g h s F 1 G H s R displaystyle g cdot h s mathcal F 1 G H quad s in mathbb R nbsp 这里的算符 displaystyle cdot nbsp 指示逐点乘法 这一定理对拉普拉斯变换 双边拉普拉斯变换 Z变换 梅林变换和Hartley变换 英语 Hartley transform 等各种傅里叶变换的变体同样成立 在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换 周期卷积 编辑 对于周期为P displaystyle P nbsp 的函数gP x displaystyle g P x nbsp 和hP x displaystyle h P x nbsp 可以被表达为二者的周期求和 英语 Periodic summation gP x m g x mP m ZhP x m h x mP m Z displaystyle begin aligned g P x amp triangleq sum m infty infty g x mP quad m in mathbb Z h P x amp triangleq sum m infty infty h x mP quad m in mathbb Z end aligned nbsp 它们的傅里叶级数系数为 G k F gP k 1P PgP x e i2pkx Pdx k ZH k F hP k 1P PhP x e i2pkx Pdx k Z displaystyle begin aligned G k amp triangleq mathcal F g P k frac 1 P int P g P x e i2 pi kx P dx quad k in mathbb Z H k amp triangleq mathcal F h P k frac 1 P int P h P x e i2 pi kx P dx quad k in mathbb Z end aligned nbsp 这里的F displaystyle mathcal F nbsp 算子指示傅里叶级数积分 逐点乘积gP x hP x displaystyle g P x cdot h P x nbsp 的周期也是P displaystyle P nbsp 它的傅里叶级数系数为 F gP hP k G H k displaystyle mathcal F g P cdot h P k G H k nbsp 周期卷积 gP h x displaystyle g P h x nbsp 的周期也是P displaystyle P nbsp 周期卷积的卷积定理为 F gP h k P G k H k displaystyle mathcal F g P h k P cdot G k H k nbsp 离散卷积 编辑 对于作为两个连续函数采样的序列g n displaystyle g n nbsp 和h n displaystyle h n nbsp 它们具有离散时间傅里叶变换G s displaystyle G s nbsp 和H s displaystyle H s nbsp G s F g s n g n e i2psn s RH s F h s n h n e i2psn s R displaystyle begin aligned G s amp triangleq mathcal F g s sum n infty infty g n cdot e i2 pi sn quad s in mathbb R H s amp triangleq mathcal F h s sum n infty infty h n cdot e i2 pi sn quad s in mathbb R end aligned nbsp 这里的F displaystyle mathcal F nbsp 算子指示离散时间傅里叶变换 DTFT 离散卷积的卷积定理为 F g h s G s H s displaystyle mathcal F g h s G s H s nbsp 离散周期卷积 编辑 对于周期为N displaystyle N nbsp 的序列gN n displaystyle g N n nbsp 和hN n displaystyle h N n nbsp gN n m g n mN m n ZhN n m h n mN m n Z displaystyle begin aligned g N n amp triangleq sum m infty infty g n mN quad m n in mathbb Z h N n amp triangleq sum m infty infty h n mN quad m n in mathbb Z end aligned nbsp 相较于离散时间傅里叶变换G s displaystyle G s nbsp 和H s displaystyle H s nbsp 的周期是1 displaystyle 1 nbsp 它们是按间隔1 N displaystyle 1 N nbsp 采样G s displaystyle G s nbsp 和H s displaystyle H s nbsp 并在N displaystyle N nbsp 个采样上进行了逆离散傅里叶变换 DFT 1或IDFT 的结果 离散周期卷积 gN h n displaystyle g N h n nbsp 的周期也是N displaystyle N nbsp 离散周期卷积定理为 F gN h k F gN k G k N F hN k H k N k n Z displaystyle mathcal F g N h k underbrace mathcal F g N k G k N cdot underbrace mathcal F h N k H k N quad k n in mathbb Z nbsp 这里的F displaystyle mathcal F nbsp 算子指示长度N displaystyle N nbsp 的离散傅里叶变换 DFT 它有着推论 gN h n F 1 F gN F hN displaystyle g N h n mathcal F 1 mathcal F g N cdot mathcal F h N nbsp 对于其非零时段小于等于N displaystyle N nbsp 的g displaystyle g nbsp 和h displaystyle h nbsp 离散圆周卷积的卷积定理为 gN h n F 1 F g F h displaystyle g N h n mathcal F 1 mathcal F g cdot mathcal F h nbsp 推广 编辑卷积的概念还可以推广到数列 测度以及广义函数上去 函数f g displaystyle f g nbsp 是定義在Rn displaystyle mathbb R n nbsp 上的可測函數 measurable function f displaystyle f nbsp 与g displaystyle g nbsp 存在卷积并记作f g displaystyle f g nbsp 如果函數不是定義在Rn displaystyle mathbb R n nbsp 上 可以把函數定義域以外的值都規定成零 這樣就變成一個定義在Rn displaystyle mathbb R n nbsp 上的函數 若G是有某m 测度的群 例如豪斯多夫空间上哈尔测度下局部紧致的拓扑群 对于G上m 勒贝格可积的实数或复数函数f和g 可定义它们的卷积 f g x Gf y g xy 1 dm y displaystyle f g x int G f y g xy 1 dm y nbsp 对于这些群上定义的卷积同样可以给出诸如卷积定理等性质 但是这需要对这些群的表示理论以及调和分析的彼得 外尔定理 离散卷積的計算方法 编辑計算卷積f n g n displaystyle f n g n nbsp 有三種主要的方法 分別為 直接計算 Direct Method 快速傅立葉轉換 FFT 分段卷積 sectioned convolution 方法1是直接利用定義來計算卷積 而方法2和3都是用到了FFT來快速計算卷積 也有不需要用到FFT的作法 如使用數論轉換 方法1 直接計算 编辑 作法 利用卷積的定義y n f n g n m 0M 1f n m g m displaystyle y n f n g n sum m 0 M 1 f n m g m nbsp dd 若f n displaystyle f n nbsp 和g n displaystyle g n nbsp 皆為實數信號 則需要MN displaystyle MN nbsp 個乘法 若f n displaystyle f n nbsp 和g n displaystyle g n nbsp 皆為更一般性的複數信號 不使用複數乘法的快速演算法 會需要4MN displaystyle 4MN nbsp 個乘法 但若使用複數乘法的快速演算法 則可簡化至3MN displaystyle 3MN nbsp 個乘法 因此 使用定義直接計算卷積的複雜度為O MN displaystyle O MN nbsp 方法2 快速傅立葉轉換 编辑 概念 由於兩個離散信號在時域 time domain 做卷積相當於這兩個信號的離散傅立葉轉換在頻域 frequency domain 做相乘 y n f n g n Y f F f G f displaystyle y n f n g n leftrightarrow Y f F f G f nbsp dd 可以看出在頻域的計算較簡單 作法 因此這個方法即是先將信號從時域轉成頻域 F f DFTP f n G f DFTP g n displaystyle F f DFT P f n G f DFT P g n nbsp dd 於是Y f DFTP f n DFTP g n displaystyle Y f DFT P f n DFT P g n nbsp dd 最後再將頻域信號轉回時域 就完成了卷積的計算 y n IDFTPDFTP f n DFTP g n displaystyle y n IDFT P DFT P f n DFT P g n nbsp dd 總共做了2次DFT和1次IDFT 特別注意DFT和IDFT的點數P displaystyle P nbsp 要滿足P M N 1 displaystyle P geq M N 1 nbsp 由於DFT有快速演算法FFT 所以運算量為O Plog2 P displaystyle O P log 2 P nbsp 假設P displaystyle P nbsp 點DFT的乘法量為a displaystyle a nbsp f n displaystyle f n nbsp 和g n displaystyle g n nbsp 為一般性的複數信號 並使用複數乘法的快速演算法 則共需要3a 3P displaystyle 3a 3P nbsp 個乘法 方法3 分段卷積 编辑 概念 將f n displaystyle f n nbsp 切成好幾段 section 每一段分別和g n displaystyle g n nbsp 做卷積後 再將結果相加 作法 先將f n displaystyle f n nbsp 切成每段長度為L displaystyle L nbsp 的區段 L gt M displaystyle L gt M nbsp 假設共切成S段 f n n 0 1 N 1 f1 n f2 n f3 n fS n S NL displaystyle f n n 0 1 N 1 to f 1 n f 2 n f 3 n f S n S left lceil frac N L right rceil nbsp dd Section 1 f1 n f n n 0 1 L 1 displaystyle f 1 n f n n 0 1 L 1 nbsp dd Section 2 f2 n f n L n 0 1 L 1 displaystyle f 2 n f n L n 0 1 L 1 nbsp dd displaystyle vdots nbsp dd dd Section r fr n f n r 1 L n 0 1 L 1 displaystyle f r n f n r 1 L n 0 1 L 1 nbsp dd displaystyle vdots nbsp dd dd Section S fS n f n S 1 L n 0 1 L 1 displaystyle f S n f n S 1 L n 0 1 L 1 nbsp dd f n displaystyle f n nbsp 為各個section的和f n r 1Sfr n r 1 L displaystyle f n sum r 1 S f r n r 1 L nbsp dd 因此 y n f n g n r 1S m 0M 1fr n r 1 L m g m displaystyle y n f n g n sum r 1 S sum m 0 M 1 f r n r 1 L m g m nbsp dd 每一小段作卷積則是採用方法2 先將時域信號轉到頻域相乘 再轉回時域 y n IDFT r 1S m 0M 1DFTP fr n r 1 L m DFTP g m P M L 1 displaystyle y n IDFT sum r 1 S sum m 0 M 1 DFT P f r n r 1 L m DFT P g m P geq M L 1 nbsp dd 總共只需要做P displaystyle P nbsp 點FFT 2S 1 displaystyle 2S 1 nbsp 次 因為g n displaystyle g n nbsp 只需要做一次FFT 假設P displaystyle P nbsp 點DFT的乘法量為a displaystyle a nbsp f n displaystyle f n nbsp 和g n displaystyle g n nbsp 為一般性的複數信號 並使用複數乘法的快速演算法 則共需要 2S 1 a 3SP displaystyle 2S 1 a 3SP nbsp 個乘法 運算量 NL3 L M 1 log2 L M 1 1 displaystyle frac N L 3 L M 1 log 2 L M 1 1 nbsp 運算複雜度 O N displaystyle O N nbsp 和N displaystyle N nbsp 呈線性 較方法2小 分為 Overlap Add 和 Overlap Save 兩種方法 分段卷積 Overlap Add欲做x n h n displaystyle x n h n nbsp 的分段卷積分 x n displaystyle x n nbsp 長度為 N displaystyle N nbsp h n displaystyle h n nbsp 長度為 M displaystyle M nbsp Step 1 將x n displaystyle x n nbsp 每 L displaystyle L nbsp 分成一段Step 2 再每段 L displaystyle L nbsp 點後面添加 M 1 displaystyle M 1 nbsp 個零 變成長度 L M 1 displaystyle L M 1 nbsp Step 3 把 h n displaystyle h n nbsp 添加 L 1 displaystyle L 1 nbsp 個零 變成長度 L M 1 displaystyle L M 1 nbsp 的 h n displaystyle h n nbsp Step 4 把每個 x n displaystyle x n nbsp 的小段和 h n displaystyle h n nbsp 做快速卷積 也就是IDFTL M 1 DFTL M 1 x n DFTL M 1 h n displaystyle IDFT L M 1 DFT L M 1 x n DFT L M 1 h n nbsp 每小段會得到長度 L M 1 displaystyle L M 1 nbsp 的時域訊號Step 5 放置第 i displaystyle i nbsp 個小段的起點在位置 L i displaystyle L times i nbsp 上 i 0 1 NL 1 displaystyle i 0 1 lceil frac N L rceil 1 nbsp Step 6 會發現在每一段的後面 M 1 displaystyle M 1 nbsp 點有重疊 將所有點都相加起來 顧名思義 Overlap Add 最後得到結果舉例來說 x n 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 displaystyle x n 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 nbsp 長度 N 15 displaystyle N 15 nbsp h n 1 2 3 displaystyle h n 1 2 3 nbsp 長度 M 3 displaystyle M 3 nbsp 令 L 5 displaystyle L 5 nbsp nbsp x n 和h n 令 L 5 displaystyle L 5 nbsp 切成三段 分別為 x0 n x1 n x2 n displaystyle x 0 n x 1 n x 2 n nbsp 每段填 M 1 displaystyle M 1 nbsp 個零 並將 h n displaystyle h n nbsp 填零至長度 L M 1 displaystyle L M 1 nbsp nbsp 分段x n 將每一段做IDFTL M 1 DFTL M 1 x n DFTL M 1 h n displaystyle IDFT L M 1 DFT L M 1 x n DFT L M 1 h n nbsp nbsp 分段運算結果若將每小段擺在一起 可以注意到第一段的範圍是 0 6 displaystyle 0 thicksim 6 nbsp 第二段的範圍是 5 11 displaystyle 5 thicksim 11 nbsp 第三段的範圍是 10 16 displaystyle 10 thicksim 16 nbsp 三段的範圍是有重疊的 nbsp 合併分段運算結果最後將三小段加在一起 並將結果和未分段的卷積做比較 上圖是分段的結果 下圖是沒有分段並利用快速卷積所算出的結果 驗證兩者運算結果相同 nbsp 結果比較圖分段卷積 Overlap Save欲做x n h n displaystyle x n h n nbsp 的分段卷積分 x n displaystyle x n nbsp 長度為 N displaystyle N nbsp h n displaystyle h n nbsp 長度為 M displaystyle M nbsp Step 1 將 x n displaystyle x n nbsp 前面填 M 1 displaystyle M 1 nbsp 個零Step 2 第一段 i 0 displaystyle i 0 nbsp 從新的 x n displaystyle x n nbsp 中 L i M 1 i displaystyle L times i M 1 times i nbsp 取到 L i 1 M 1 i 1 displaystyle L times i 1 M 1 times i 1 nbsp 總共 L displaystyle L nbsp 點當做一段 因此每小段會重複取到前一小段的 M 1 displaystyle M 1 nbsp 點 取到新的一段全為零為止Step 3 把 h n displaystyle h n nbsp 添加 L M displaystyle L M nbsp 個零 變成長度 L displaystyle L nbsp 的 h n displaystyle h n nbsp Step 4 把每個 x n displaystyle x n nbsp 的小段和 h n displaystyle h n nbsp 做快速卷積 也就是IDFTL DFTL x n DFTL h n displaystyle IDFT L DFT L x n DFT L h n nbsp 每小段會得到長度 L displaystyle L nbsp 的時域訊號Step 5 對於每個 i displaystyle i nbsp 小段 只會保留末端的 L M 1 displaystyle L M 1 nbsp 點 因此得名 Overlap SaveStep 6 將所有保留的點合再一起 得到最後結果舉例來說 x n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 displaystyle x n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 nbsp 長度 N 15 displaystyle N 15 nbsp h n 1 2 3 displaystyle h n 1 2 3 nbsp 長度 M 3 displaystyle M 3 nbsp 令 L 7 displaystyle L 7 nbsp nbsp x n 和h n 將 math, 维基百科,wiki,书籍,书籍,图书馆,