重畳加算法

重畳加算法 (ちょうじょうかさんほう、) とは、非常に長い信号  と FIRフィルタ  の 離散畳み込み  を分割して(効率的に)処理する手法である。

ここで 信号 は 、フィルタ は  以外で0、またである。

重畳加算法の基本アイデアは、長い信号  を区間長で区切り、複数の短い断片  と フィルタ  に関する複数の畳み込みに分割して、FFTの積として効率的に計算することにある。

離散畳み込みは、各区間の畳み込みの総和で表せる:

ここで各区間の畳み込み は 領域 [1, L+M-1] 以外で 0 であり、任意の  に関し、領域 [1, N] における  と  の 点巡回畳み込みと等価である。

重畳加算法のアドバンテージは、この巡回畳み込みが畳み込み定理により、次のような FFTの積の逆FFT として効率的に計算できる事にある:

ここで とは(ブロック長の)高速フーリエ変換と逆高速フーリエ変換である。
FFTアルゴリズムによっては、(巡回畳み込み計算のために)FFTブロック長を調整する事が理に適っている。例えばCooley-Tukey型FFTアルゴリズム (radix-2アルゴリズム) を使う場合、2の冪乗のブロック長を選ぶと有利である:

アルゴリズム 

図1に、重畳加算法のアイデアを示す。
 信号 (長さNx) を区間長で区切り、オーバーラップの無いk個の断片の列を得る。
 各区間について、断片  (長さ≦L) と フィルタ  (長さM) のFFT結果の積をとり逆FFTして、区間毎の畳み込み結果  (長さ≦L+M-1) を得る。(なお畳み込み結果は、元信号(区間長L)と比べ (フィルタの長さ-1) だけ長くなり、オーバーラップが生じる)
 最終的な出力信号は、図に示すように、各区間の結果 のオーバーラップ(重畳)部を加算しながら連結して得られる。
区間長は、FFT開発初期にはしばしば効率上の理由でFFTのブロック長が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

巡回畳み込みへの応用 

一般に信号が周期的でその周期がの場合、畳み込み結果も周期的で同じ周期をとる。
 1周期分のは、ちょうど1周期分の信号  (長さNx) と フィルタ (長さM) の畳み込みで得られる。ここでは前述のアルゴリズム 1を使う。畳み込み結果は、区間 [M, Nx] で正しい。
 先頭のM-1個(区間[1, M-1])の値に、末尾のM-1個(区間[Nx+1, Nx+M-1])の値を加算すれば、区間 [1, Nx] が正しい畳み込み結果を表すようになる。
変更した疑似コードは以下の通り:

    アルゴリズム 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アルゴリズム()を長さの信号に適用する場合およそ 回の複素数乗算が行われる。重畳加算法における複素数乗算の回数は、FFTとフィルタ乗算とIFFTを考慮して:

なお巡回行列版のセクション () の追加コストは、通常とても小さいので単純化のために無視できる。

FFTのブロック長の最適値は、の範囲で動かしての最小値を整数を(数値的に)探す事で得られる。が2の冪乗であれば、FFTを効率的に計算できる。の値が定まれば、信号を最適に区切る区間長が定まる。
比較のため、普通の巡回畳み込みの計算量も示しておく:

したがって重畳加算法の計算量はほぼ でスケールし、他方、普通の巡回畳み込みの計算量はほぼ である。() しかしながら、この種の推計は複素数乗算の計算量だけ考慮しており、アルゴリズムに関わる他の処理は度外視している。各アルゴリズムに要する計算時間の直接測定こそ、より大きな関心事である。
図2に、による標準的な巡回畳み込みの計算時間と、アルゴリズム 2の形の重畳加算法による同様な畳み込みの計算時間の比を示す; 縦軸は信号長の対数表示、横軸はフィルタ長の対数表示で、計算時間の比を等高線で示している。両アルゴリズムはMatlabで実装した。青い太線は、重畳加算法の方が標準巡回畳み込みより速い(比>1)領域の境界線である。このケースでは重畳加算法は標準的手法より最大約3倍高速だった。

関連項目 

 (Overlap-save method)

参考文献

外部リンク 

信号処理

フーリエ解析
数値解析
数学に関する記事