重畳加算法
重畳加算法 (ちょうじょうかさんほう、) とは、非常に長い信号 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の冪乗のブロック長を選ぶと有利である: