重複保存方式

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

ただし、領域[1, M ]の外側のmについてはh [ m ] = 0 となる。この記事では、 や などの一般的な抽象記法を用いるが、これらの記法では関数は特定の瞬間ではなく、全体として考えるべきであることが理解されている（畳み込み#記法 を参照）。 ${\textstyle y(t)=x(t)*h(t),}$ ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ ${\textstyle t}$

図1：4つのグラフの連続は、オーバーラップセーブ畳み込みアルゴリズムの1サイクルを表しています。1つ目のグラフは、ローパスFIRフィルタで処理される長いデータシーケンスです。2つ目のグラフは、区分的に処理されるデータの1つのセグメントです。3つ目のグラフはフィルタリングされたセグメントで、使用可能な部分は赤色で表示されています。4つ目のグラフは、出力ストリームに追加されたフィルタリングされたセグメントを示しています。^[A] FIRフィルタは、M=16サンプルのボックスカーローパスフィルタで、セグメントの長さはL=100サンプル、オーバーラップは15サンプルです。

概念としては、任意の長さLのy [ n ] の短いセグメントを計算し、それらを連結するというものです。そのためには、次の入力セグメントと重なる長い入力セグメントが必要になります。重なり合ったデータは「保存」され、再度使用されます。^[1] まず、各出力セグメントに対して従来の畳み込みのみを行う処理について説明します。次に、その畳み込みをより効率的な方法で置き換える方法について説明します。

任意の整数kに対してn = kL  +  Mで始まる線分を考え、次のように定義します。

${\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}}$

${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].}$

次に、、および同値としてについて、次のように書くことができます。 ${\displaystyle kL+M+1\leq n\leq kL+L+M}$ ${\displaystyle M+1\leq n-kL\leq L+M}$

${\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}$

を代入することで、計算はについて行うだけで済む。これらの手順は図1の最初の3つのトレースに示されているが、出力の目的の部分（3番目のトレース）は1  ≤  j  ≤  Lに対応する。^[B] ${\displaystyle j=n-kL}$ ${\displaystyle y_{k}[j]}$ ${\displaystyle M+1\leq j\leq L+M}$

x _k [ n ] を周期N  ≥  L  +  M  − 1で周期的に拡張すると、次の式が成り立ちます。

${\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}$

畳み込み    と は    領域 において等価である。したがって、 のN点の巡回（または巡回）畳み込みを  領域 [1,  N ] 内で計算すれば十分である。部分領域 [ M  + 1,  L  +  M ] が出力ストリームに追加され、その他の値は破棄される。巡回畳み込みの利点は、巡回畳み込み定理によれば、線形畳み込みよりも巡回畳み込みの方が効率的に計算できることである。 ${\displaystyle (x_{k,N})*h\,}$ ${\displaystyle x_{k}*h\,}$ ${\displaystyle M+1\leq n\leq L+M}$ ${\displaystyle x_{k}[n]\,}$ ${\displaystyle h[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は、 N個の離散点にわたって評価される離散フーリエ変換とその逆変換を指し、
• Lは通常、N = L+M-1が2 の整数乗となるように選択され、変換は効率性を考慮してFFTアルゴリズムを使用して実装されます。
• 円畳み込みの先端効果と後端効果は重ね合わせて加算され、^[C]その後破棄されます。^[D]

擬似コード

（線形畳み込みのオーバーラップ節約アルゴリズム）h = FIR_インパルス応答M = 長さ(h)重なり = M − 1N = 8 × 重複 （より良い選択については次のセクションを参照）ステップサイズ = N − オーバーラップH = DFT(h, N)位置 = 0位置+ N ≤ 長さ(x) yt = IDFT(DFT(x(位置+(1:N))) × H) y(position+(1:step_size)) = yt(M : N) (M−1個のy値を破棄) 位置 = 位置 + ステップサイズ終わり

効率性の考慮

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

DFTとIDFTをFFTアルゴリズムで実装する場合、上記の擬似コードでは、 FFT、配列の積、IFFTに約N（log ₂（N）+ 1）^{回の複素乗算が必要になります。 [E]} 各反復処理では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}}.}$

したがって、オーバーラップ保存法のコストはほぼ に比例しますが、単一の大きな循環畳み込みのコストはほぼ になります。 ${\displaystyle O\left(N_{x}\log _{2}N\right)}$ ${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$

重複破棄

Overlap–discard ^[2]とOverlap–scrap ^[3]は、ここで説明した同じ手法を指すあまり一般的ではないラベルです。しかし、これらのラベルは、overlap–addと区別する上で実際には（ overlap–saveよりも）より適切です。なぜなら、どちらの手法も「保存」しますが、破棄するのは片方だけだからです。「保存」とは、セグメントk + 1 を処理するために、セグメントkからM  − 1 個の入力（または出力）サンプルが必要であることだけを指します。

重複の拡張–保存

オーバーラップセーブアルゴリズムは、システムの他の一般的な操作を含めるように拡張することができます。^{[F] [4]}

• 追加のIFFTチャネルは、順方向FFTを再利用することで最初のチャネルよりも安価に処理できる。
• 異なるサイズの順方向FFTと逆方向FFTを使用することでサンプリングレートを変更できます。
• 周波数変換（ミキシング）は周波数ビンを並べ替えることで実現できる

参照

• オーバーラップ加算法
• 循環畳み込み#例

注記

1. RabinerとGold、図2.35、4番目のトレース。
2. 不要なエッジ効果を最後のM-1個の出力にシフトすることは、IDFTをバッファ内で計算できるため、実行時の利便性を高める可能性があります。これにより、エッジ効果は次のIDFTで上書きされます。このシフトは、インパルス応答の時間シフトによってどのように行われるかを説明します。 ${\displaystyle y[n]}$
3. 先行エッジ効果と後続エッジ効果を別々に保持するOverlap-add メソッドと混同しないでください。
4. エッジ効果は、をに置き換えることでIDFT出力の先頭から最後尾に移動できます。これは、長さNのバッファがM-1サンプル分循環シフト（回転）されることを意味します。したがって、h(M)要素はn=1にあります。h(M-1)要素はn=Nにあります。h(M-2)要素はn=N-1にあります。などです。 ${\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])}$ ${\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),}$
5. ^{N=2 k}の Cooley–Tukey FFT アルゴリズムでは(N/2) log ₂ (N) が必要です – FFT – 定義と速度を参照してください
6. カーリンら。 1999 年、31 ページ、20 列目。

参考文献

1. 「Overlap-Add (OLA) STFT処理 | スペクトルオーディオ信号処理」www.dsprelated.com . 2024年3月2日閲覧。「Overlap-Save」という名前は、前のフレームのL-1サンプル（ここでは現在のフレームのM-1サンプル）が次のフレームの計算のために保存されることに由来しています。
2. Harris, FJ (1987). DFElliot (編).デジタル信号処理ハンドブック. サンディエゴ: アカデミック・プレス. pp.  633– 699. ISBN 0122370759。
3. Frerking, Marvin (1994).通信システムにおけるデジタル信号処理. ニューヨーク: Van Nostrand Reinhold. ISBN 0442016166。
4. Borgerding, Mark (2006). 「オーバーラップ保存をマルチバンドミキシング・ダウンサンプリングフィルタバンクに変換する」IEEE Signal Processing Magazine . 23 (2006年3月): 158– 161. Bibcode :2006ISPM...23..158B. doi :10.1109/MSP.2006.1598092.

4. ラビナー、ローレンス・R.、ゴールド、バーナード (1975). 「2.25」 .デジタル信号処理の理論と応用. ニュージャージー州エングルウッド・クリフス: プレンティス・ホール. pp. 63–67. ISBN 0-13-914101-4。
5. 米国特許6898235、Carlin, Joe、Collins, Terry、Hays, Peter他、「ハイパーチャネライゼーションを用いた広帯域通信傍受および方向探知装置」、公開日1999年12月10日、発行日2005年5月24日 、https://patentimages.storage.googleapis.com/4d/39/2a/cec2ae6f33c1e7/US6898235.pdfでも閲覧可能

外部リンク

• ディープ・クンドゥール博士、オーバーラップ追加およびオーバーラップ保存、トロント大学

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