重畳加算法

重畳加算法 (ちょうじょうかさんほう、) とは、非常に長い信号 formula_1 と FIRフィルタ formula_2 の 離散畳み込み formula_3 を分割して(効率的に)処理する手法である。
ここで 信号 formula_5は formula_6、フィルタ formula_7は formula_8 以外で0、またformula_9である。
重畳加算法の基本アイデアは、長い信号 formula_1 を区間長formula_11で区切り、複数の短い断片 formula_12 と フィルタ formula_2 に関する複数の畳み込みに分割して、FFTの積として効率的に計算することにある。
離散畳み込みformula_15は、各区間の畳み込みの総和で表せる:
ここで各区間の畳み込み formula_17は 領域 [1, "L"+"M"-1] 以外で 0 であり、任意の formula_18 に関し、領域 [1, N] における formula_12 と formula_2 の formula_21点巡回畳み込みと等価である。
重畳加算法のアドバンテージは、この巡回畳み込みが畳み込み定理により、次のような FFTの積の逆FFT として効率的に計算できる事にある:
ここで formula_22とformula_23は(ブロック長formula_21の)高速フーリエ変換と逆高速フーリエ変換である。
FFTアルゴリズムによっては、(巡回畳み込み計算のために)FFTブロック長formula_21を調整する事が理に適っている。例えばCooley-Tukey型FFTアルゴリズム (radix-2アルゴリズム) を使う場合、2の冪乗のブロック長を選ぶと有利である:
アルゴリズム.
図1に、重畳加算法のアイデアを示す。
区間長formula_11は、FFT開発初期にはしばしば効率上の理由でFFTのブロック長formula_21が2の冪乗をとるよう調整されたが、更なる研究開発の結果、Nを大きな素数で素因数分解する効率的変換方法が明らかにされ、このパラメータに対する計算上の敏感さは低減された。 ()
アルゴリズムの疑似コードは以下の通り:
 アルゴリズム 1 ("重畳加算法(OLA)による線形畳み込み")
 使用するFFTアルゴリズムに応じてFFTブロック長 N と 分割区間長 L に最適値を設定
 H = FFT(h,N) ("ゼロ・パディングしたFFT" )
 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 ("オーバーラップ区間を加算" )
 i = i+L
 end
巡回畳み込みへの応用.
一般に信号formula_1が周期的でその周期がformula_37の場合、畳み込み結果formula_38も周期的で同じ周期をとる。
変更した疑似コードは以下の通り:
 アルゴリズム 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アルゴリズム()を長さformula_43の信号に適用する場合およそ formula_44回の複素数乗算が行われる。重畳加算法における複素数乗算の回数は、FFTとフィルタ乗算とIFFTを考慮して:
なお巡回行列版のformula_46セクション () の追加コストは、通常とても小さいので単純化のために無視できる。
FFTのブロック長formula_21の最適値は、formula_48の範囲で動かしてformula_49の最小値を整数formula_50を(数値的に)探す事で得られる。formula_21が2の冪乗であれば、FFTを効率的に計算できる。formula_21の値が定まれば、信号formula_1を最適に区切る区間長formula_54が定まる。
比較のため、普通の巡回畳み込みの計算量も示しておく:
したがって重畳加算法の計算量はほぼ formula_56でスケールし、他方、普通の巡回畳み込みの計算量はほぼ formula_57である。() しかしながら、この種の推計は複素数乗算の計算量だけ考慮しており、アルゴリズムに関わる他の処理は度外視している。各アルゴリズムに要する計算時間の直接測定こそ、より大きな関心事である。
図2に、による標準的な巡回畳み込みの計算時間と、"アルゴリズム 2"の形の重畳加算法による同様な畳み込みの計算時間の比を示す; 縦軸は信号長formula_37の対数表示、横軸はフィルタ長formula_59の対数表示で、計算時間の比を等高線で示している。両アルゴリズムはMatlabで実装した。青い太線は、重畳加算法の方が標準巡回畳み込みより速い(比>1)領域の境界線である。このケースでは重畳加算法は標準的手法より最大約3倍高速だった。