重ね合わせ追加法

信号処理において、オーバーラップ加算法は、非常に長い信号の離散畳み込みを評価する効率的な方法である。${\displaystyle x[n]}$有限インパルス応答（FIR）フィルタを使用${\displaystyle h[n]}$:

どこ${\displaystyle h[m]=0}$のために${\displaystyle m}$地域外${\displaystyle [1,M].}$ 

この記事では、次のような一般的な抽象表記法を使用します。${\textstyle y(t)=x(t)*h(t),}$または${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ここでいう機能は、特定の瞬間ではなく、全体として捉えるべきであるという理解に基づいている。${\textstyle t}$（畳み込み表記法を参照）。

この概念は、問題を複数の畳み込みに分割することである。${\displaystyle h[n]}$短いセグメントで${\displaystyle x[n]}$:

${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}$

どこ${\displaystyle L}$は任意のセグメント長です。すると：

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}$

そして${\displaystyle y[n]}$短い畳み込みの和として記述できます: ^{[ 1 ]}

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}$

線形畳み込み${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,}$領域外ではゼロ${\displaystyle [1,L+M-1].}$そして任意のパラメータに対して${\displaystyle N\geq L+M-1,\,}$^{[ A ]}それは${\displaystyle N}$-点円形畳み込み${\displaystyle x_{k}[n]\,}$と${\displaystyle h[n]\,}$その地域で${\displaystyle [1,N].}$ 円形畳み込みの利点は、円形畳み込み定理によれば、線形畳み込みよりも効率的に計算できることである。

どこ：

• DFT _Nと IDFT _Nは離散フーリエ変換とその逆変換を表し、${\displaystyle N}$離散点、そして
• ${\displaystyle L}$慣例として、${\displaystyle N=L+M-1}$は2のべき乗の整数であり、変換は効率性を考慮してFFTアルゴリズムを使用して実装されています。

以下は、そのアルゴリズムの擬似コード表現です。

（線形畳み込みのためのオーバーラップ加算アルゴリズム） h = FIRフィルター M = length(h) Nx = length(x) N = 8 × 2^ceiling( log2(M) ) (フィルタ長Mより大きい最小の2のべき乗の8倍。もう少し良い選択肢については次のセクションを参照してください。) step_size = N - (M-1) (上記のテキストのL) H = DFT(h, N) 位置 = 0 y(1 : Nx + M-1) = 0 位置 + ステップサイズ ≤ Nxの間、 y(position+(1:N)) = y(position+(1:N)) + IDFT(DFT(x(position+(1:step_size)), N) × H) 位置 = 位置 + ステップサイズ 終わり

DFTとIDFTがFFTアルゴリズムによって実装される場合、上記の擬似コードでは、FFT、配列の積、およびIFFTに対して約N（log ₂（N）+ 1）回の複素数乗算が必要となります。 ^{[ B ]} 各反復ではN-M+1個の出力サンプルが生成されるため、出力サンプルあたりの複素数乗算の回数は約次のようになります。

例えば、${\displaystyle M=201}$そして${\displaystyle N=1024,}$式3は${\displaystyle 13.67,}$一方、式1を直接評価するには、${\displaystyle 201}$出力サンプルごとに複素乗算が行われ、最悪の場合は両方が${\displaystyle x}$そして${\displaystyle h}$複素数値です。また、任意の与えられた値に対して、${\displaystyle M,}$式3は、${\displaystyle N.}$ 図2は、${\displaystyle N}$フィルタ長の範囲に対して式3を最小化する（${\displaystyle M}$)

式1の代わりに、長さの長いシーケンスに式2を適用することも考えられます。${\displaystyle N_{x}}$サンプル。複雑な乗算の総数は次のようになります。

${\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}$

比較すると、擬似コードアルゴリズムで必要とされる複素乗算の回数は以下のとおりです。

${\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}$

したがって、オーバーラップ追加法のコストはほぼ${\displaystyle O\left(N_{x}\log _{2}N\right)}$単一の大きな円形畳み込みのコストはほぼ${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$図3では、 MATLABシミュレーションによって作成された2つの方法の比較も示されています。等高線は、両方の方法を実行するのにかかる時間の比率が一定であることを示す線です。オーバーラップ加算方式の方が速い場合、比率は1を超え、3にも達する比率が見られます。

• オーバーラップ保存法
• 円形畳み込み#例

• オッペンハイム、アラン・V.、シェーファー、ロナルド・W. (1975).デジタル信号処理. ニュージャージー州エングルウッド・クリフス：プレンティス・ホール. ISBN 0-13-214635-5。
• ヘイズ、M. ホレス (1999).デジタル信号処理. シャウムズ・アウトライン・シリーズ. ニューヨーク: マグロウヒル. ISBN 0-07-027389-8。
• Senobari, Nader Shakibay; Funning, Gareth J.; Keogh, Eamonn; Zhu, Yan; Yeh, Chin-Chia Michael; Zimmerman, Zachary; Mueen, Abdullah (2019). "超効率的な相互相関 (SEC-C): デスクトップコンピュータに適した高速マッチドフィルタリングコード" (PDF) . Seismological Research Letters . 90 (1): 322– 334. doi : 10.1785/0220180122 . ISSN 0895-0695 .