Severity: Notice
Message: Undefined offset: 1
Filename: infosekolah/leftmenudasboard.php
Line Number: 33
Line Number: 34
重畳加算法（ちょうじょうかさんほう、英: OverLap-Add method、略称：OA, OLA）とは、非常に長い信号 x {\displaystyle \mathbf {x} } と FIRフィルタ h {\displaystyle \mathbf {h} } の離散畳み込み h ∗ x {\displaystyle \mathbf {h} *\mathbf {x} } を分割して（効率的に）処理する手法である。
ここで信号 x [ n ] {\displaystyle x[n]} は n = 1 , … , N x {\displaystyle n=1,\ldots ,N_{x}} 、フィルタ h [ m ] {\displaystyle h[m]} は m = 0 , … , M − 1 {\displaystyle m=0,\ldots ,M-1} 以外で0、また M < N x {\displaystyle M<N_{x}} である。
重畳加算法の基本アイデアは、長い信号 x {\displaystyle \mathbf {x} } を区間長 L {\displaystyle L} で区切り、複数の短い断片 x k {\displaystyle \mathbf {x} _{k}} と フィルタ h {\displaystyle \mathbf {h} } に関する複数の畳み込みに分割して、訳注: 適切なブロック長のFFTの積として効率的に計算することにある。
離散畳み込み ( h ∗ x ) [ n ] {\displaystyle (\mathbf {h} *\mathbf {x} )[n]} は、各区間の畳み込みの総和で表せる:
ここで各区間の畳み込み y k [ n ] = d e f ( h ∗ x k ) [ n ] {\displaystyle y_{k}[n]\ {\stackrel {\mathrm {def} }{=}}\ (\mathbf {h} *\mathbf {x} _{k})[n]} は 領域 [1, L+M-1] 以外で 0 であり、任意の N ≥ ( L + M − 1 ) {\displaystyle N\geq (L+M-1)} に関し、領域 [1, N] における x k {\displaystyle \mathbf {x} _{k}} と h {\displaystyle \mathbf {h} } の N {\displaystyle N} 点巡回畳み込みと等価である。
重畳加算法のアドバンテージは、この巡回畳み込みが畳み込み定理により、次のような FFTの積の逆FFT として効率的に計算できる事にある:
ここで FFT {\displaystyle {\textrm {FFT}}} と IFFT {\displaystyle {\textrm {IFFT}}} は（ブロック長 N {\displaystyle N} の）高速フーリエ変換と逆高速フーリエ変換である。 FFTアルゴリズムによっては、（巡回畳み込み計算のために）FFTブロック長 N {\displaystyle N} を調整する事が理に適っている。例えばCooley-Tukey型FFTアルゴリズム (radix-2アルゴリズム) を使う場合、2の冪乗のブロック長を選ぶと有利である:
図1に、重畳加算法のアイデアを示す。
区間長 L {\displaystyle L} は、FFT開発初期にはしばしば効率上の理由でFFTのブロック長 N {\displaystyle N} が2の冪乗をとるよう調整されたが、更なる研究開発の結果、Nを大きな素数で素因数分解する効率的変換方法が明らかにされ、このパラメータに対する計算上の敏感さは低減された。[要説明] (訳注: FFTのブロック長 N {\displaystyle N} が2の冪乗の場合の計算量は O ( N log 2 N ) {\displaystyle O(N\log _{2}{N})} 、一般にブロック長が N = Π n i {\displaystyle N=\Pi {n_{i}}} と素因数分解できる場合の計算量は O ( N ∑ n i ) {\displaystyle O(N\sum {n_{i}})} であり、ブロック長 N {\displaystyle N} をゼロ・パディングで調整して計算量を最適化できる。) アルゴリズムの疑似コードは以下の通りである:
'''アルゴリズム 1''' (''重畳加算法(OLA)による線形畳み込み'') 使用するFFTアルゴリズムに応じてFFTブロック長 N と 分割区間長 L に最適値を設定 H = FFT(h,N) <span style="color:green;">(''ゼロ・パディングしたFFT'' )</span> i = 1 '''while''' i <= Nx il = min(i+L-1,Nx) yt = IFFT( FFT(x(i:il),N) * H, N) k = min(i+M-1,Nx) y(i:k) = y(i:k) + yt <span style="color:green;">(''オーバーラップ区間を加算'' )</span> i = i+L '''end'''
一般に信号 x {\displaystyle \mathbf {x} } が周期的でその周期が N x {\displaystyle N_{x}} の場合、畳み込み結果 y [ n ] {\displaystyle y[n]} も周期的で同じ周期をとる。
変更した疑似コードは以下の通りである[要検証 – ノート]:
アルゴリズム 2 (重畳加算法(OLA)による巡回畳み込み) アルゴリズム 1 を評価 y(1:M-1) = y(1:M-1) + y(Nx+1:Nx+M-1) y = y(1:Nx) end 【参考】英語版記事初版のアルゴリズム 2 (アルゴリズム 1 の必要範囲を引用 ) 使用するFFTアルゴリズムに応じてFFTブロック長 N と 分割区間長 L に最適値を設定 H = FFT(h,N) (ゼロ・パディングしたFFT ) (ここまで引用 ) ML = floor((N-1)/L) (未使用 ) i = Nx-L+1 k = N - L while k >= 1 il = i+L-1 yt = IFFT( FFT(x(i:il,N)) * H ) y(1:k) = y(1:k) + yt(N-k+1:N) k = k-L i = i-L end
畳み込みの計算コストは、操作に関わる複素数乗算の回数と関連付ける事ができる。主要な計算量はFFT演算によるもので、Radix-2アルゴリズム(訳注: ブロック長 N {\displaystyle N} が2の冪乗のアルゴリズム)を長さ N x = N {\displaystyle N_{x}=N} の信号に適用する場合およそ C = ( N log 2 N ) / 2 {\displaystyle C=(N\log _{2}{N})/2} 回の複素数乗算が行われる。重畳加算法における複素数乗算の回数は、FFTとフィルタ乗算とIFFTを考慮して:
なお巡回行列版の M L {\displaystyle M_{L}} セクション (訳注: 先頭と末尾の長さ(M-1)の区間？) の追加コストは、通常とても小さいので単純化のために無視できる。
FFTのブロック長 N {\displaystyle N} の最適値は、 log 2 M ≤ n ≤ log 2 N x {\displaystyle \log _{2}{M}\leq n\leq \log _{2}{N_{x}}} の範囲で動かして C O A ( N = 2 n ) {\displaystyle C_{OA}\left(N=2^{n}\right)} の最小値を整数 n {\displaystyle n} を(数値的に)探す事で得られる。 N {\displaystyle N} が2の冪乗であれば、FFTを効率的に計算できる。 N {\displaystyle N} の値が定まれば、信号 x {\displaystyle \mathbf {x} } を最適に区切る区間長 L = N − M + 1 {\displaystyle L=N-M+1} が定まる。 比較のため、普通の巡回畳み込みの計算量も示しておく:
したがって重畳加算法の計算量はほぼ O ( N x log 2 N ) {\displaystyle O(N_{x}\log _{2}{N})} でスケールし、他方、普通の巡回畳み込みの計算量はほぼ O ( N x log 2 N x ) {\displaystyle O(N_{x}\log _{2}{N_{x}})} である。(訳注: N > N x {\displaystyle N>N_{x}} なので重畳加算法の方が計算量が多い事になってしまう。2つの計算量は要検証) しかしながら、この種の推計は複素数乗算の計算量だけ考慮しており、アルゴリズムに関わる他の処理は度外視している。各アルゴリズムに要する計算時間の直接測定こそ、より大きな関心事である。 図2に、式1による標準的な巡回畳み込み[要説明]の計算時間と、アルゴリズム 2の形の重畳加算法による同様な畳み込みの計算時間の比を示す; 縦軸は信号長 N x {\displaystyle N_{x}} の対数表示、横軸はフィルタ長 N h = M {\displaystyle N_{h}=M} の対数表示で、計算時間の比を等高線で示している。両アルゴリズムはMatlabで実装した。青い太線は、重畳加算法の方が標準巡回畳み込みより速い(比>1)領域の境界線である。このケースでは重畳加算法は標準的手法より最大約3倍高速だった。[要検証 – ノート]
