オーバーラップ加算法

Method in signal processing

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

${\displaystyle y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],}$

式1

地域外の場合は ${\displaystyle h[m]=0}$ ${\displaystyle m}$ ${\displaystyle [1,M].}$ 

この記事では、 や などの一般的な抽象表記法を使用します。これらの表記法では、関数は特定の瞬間ではなく、全体として考えるべきであることが理解されています( Convolution#Notation を参照)。 ${\textstyle y(t)=x(t)*h(t),}$ ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ ${\textstyle t}$

アルゴリズム

図1：5つのプロットのシーケンスは、オーバーラップ加算畳み込みアルゴリズムの1サイクルを示しています。最初のプロットは、ローパスFIRフィルタで処理される長いデータシーケンスです。2番目のプロットは、区分的に処理されるデータの1つのセグメントです。3番目のプロットは、フィルタの立ち上がりおよび立ち下がりのトランジェントを含む、フィルタリングされたセグメントです。4番目のプロットは、新しいデータが前のセグメントの結果に追加される場所を示しています。5番目のプロットは、更新された出力ストリームです。FIRフィルタはサンプル数のボックスカーローパスフィルタで、セグメントの長さはサンプル、オーバーラップは15サンプルです。 ${\displaystyle M=16}$ ${\displaystyle L=100}$

概念は、問題を の短いセグメントを持つの複数の畳み込みに分割することです。 ${\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],\,}$

これは短い畳み込みの和として表すことができる：^[1] ${\displaystyle y[n]}$

${\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}}}$

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

${\displaystyle y_{k}[n]\ =\ \scriptstyle {\text{IDFT}}_{N}\displaystyle (\ \scriptstyle {\text{DFT}}_{N}\displaystyle (x_{k}[n])\cdot \ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])\ ),}$

式2

どこ：

• DFT _NとIDFT _Nは離散点上で評価される離散フーリエ変換とその逆変換を指し、 ${\displaystyle N}$
• ${\displaystyle L}$は、通常、2 の累乗の整数になるように選択され、変換は効率化のためにFFTアルゴリズムを使用して実装されます。 ${\displaystyle N=L+M-1}$

擬似コード

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

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

効率性の考慮

図2: コスト関数を最小化するN（2の整数乗）の値のグラフ ${\displaystyle {\tfrac {N\left(\log _{2}N+1\right)}{N-M+1}}}$

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

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

式3

例えば、とEq.3が等しい場合、 Eq.1を直接評価すると出力サンプルごとに最大 回 回の複素乗算が必要になり、最悪のケースは と の両方が複素数値の場合です。また、任意のEq.3に対して が最小値を持つことにも注意してください。図 2 は、フィルタ長の範囲 ( ) でEq.3を最小化する の値のグラフです。 ${\displaystyle M=201}$ ${\displaystyle N=1024,}$ ${\displaystyle 13.67,}$ ${\displaystyle 201}$ ${\displaystyle x}$ ${\displaystyle h}$ ${\displaystyle M,}$ ${\displaystyle N.}$ ${\displaystyle N}$ ${\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}}.}$

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

図3：オーバーラップ加算法のゲインと単一の大きな円形畳み込み法のゲインの比較。軸は信号長N _xとフィルタ長N _hの値を示しています。

参照

• 重複保存方式
• 循環畳み込み#例

注記

1. この条件は、セグメントに少なくともゼロが追加されていることを意味し、出力の上昇および下降トランジェントの循環的なオーバーラップを防ぎます。 ${\displaystyle x_{k}}$ ${\displaystyle M-1}$
2. ^kの Cooley–Tukey FFT アルゴリズムでは(N/2) log ₂ (N) が必要です – FFT – 定義と速度を参照してください

参考文献

1. ラビナー、ローレンス・R.; ゴールド、バーナード (1975). 「2.25」 .デジタル信号処理の理論と応用. ニュージャージー州エングルウッド・クリフス: プレンティス・ホール. pp. 63–65. ISBN 0-13-914101-4。

さらに読む

• オッペンハイム、アラン・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.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Overlap–add_method&oldid=1320401714"