畳み込み定理

ウィキペディア

畳み込み

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/28 07:27 UTC 版)

プログラミングにおける畳み込みについては「重畳関数」をご覧ください。

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "畳み込み" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年7月)

2つの正方形による畳み込み。解として得る波形は三角波となる。黄色の領域で示されている面積が2つの方形波の合成積である。

正方形がRC回路に入力された場合の出力信号波形を得るために、RC回路のインパルス応答と方形波の畳み込みを行っている。 黄色の領域で示されている面積が合成積である。

畳み込み（たたみこみ、英: convolution）とは、関数 g を平行移動しながら関数 f に重ね足し合わせる二項演算である。あるいはコンボリューションとも呼ばれる。

定義

一次元

連続

連続関数 f, g の畳み込み f ∗ g は以下のように定義される：

${\displaystyle (f*g)(t)=\int f(\tau )g(t-\tau )\,d\tau }$

ウィキペディア小見出し辞書

畳み込み定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/28 23:15 UTC 版)

「ショーンハーゲ・ストラッセン法」の記事における「畳み込み定理」の解説

ショーンハーゲ・ストラッセン法も、他の高速フーリエ変換を用いる乗算と同じように、畳み込み定理の巡回畳み込みを効率的に計算できる性質を用いている。具体的には、 2つのベクトルの巡回畳み込みは、それぞれを一度離散フーリエ変換し、その結果の積を逆離散フーリエ変換することで得られる。 数式で表現すると（ここでのドット積はベクトルの内積（スカラー積）ではなくて、２つのベクトルを成分ごとに積を作って新しいベクトルを作る操作である） CyclicConvolution(X, Y) = IDFT(DFT(X) · DFT(Y)) 入力を変換した DFT(X) と DFT(Y) の積を計算するためにも高速フーリエ変換を用いて離散フーリエ変換と逆離散フーリエ変換を行い、乗算アルゴリズムを再帰的に呼び出すことで、巡回畳み込みを効率的に計算できる。 このアルゴリズムは、逆向きの巡回畳み込みを用いれば重みの付いた変換である DWT に対応する畳み込み定理も適用でき、より有用なアルゴリズムとなる。ベクトル X と Y の長さが n であり、 aが 位数 2n の原始根であるとする(つまり、a2n = 1 )。このとき、Aを重みベクトルとして以下のように定義する A = (aj), 0 ≤ j < n A−1 = (a−j), 0 ≤ j< n よって、 NegacyclicConvolution(X, Y) = A−1 · IDFT(DFT(A · X) · DFT(A · Y)) といえる。離散フーリエ変換前にAが掛けられ、逆離散フーリエ変換後にA−1が掛けられることを除けばほぼ同じ形である。