重畳加算法
重畳加算法の基本アイデアは、長い信号 x {\displaystyle \mathbf {x} } を区間長 L {\displaystyle L} で区切り、複数の短い断片 x k {\displaystyle \mathbf {x} _{k}} と フィルタ h {\displaystyle \mathbf {h} } に関する複数の畳み込みに分割して、訳注: 適切なブロック長のFFTの積として効率的に計算することにある。
x k [ n ] = d e f { x [ n + k L ] , n = 1 , 2 , ... , L 0 , otherwise x [ n ] = ∑ k x k [ n − k L ] , {\displaystyle {\begin{aligned}x_{k}[n]\ &{\stackrel {\mathrm {def} }{=}}\ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\textrm {otherwise}}\end{cases}}\\x[n]&=\sum _{k}x_{k}[n-kL],\\\end{aligned}}}
一般に信号 x {\displaystyle \mathbf {x} } が周期的でその周期が N x {\displaystyle N_{x}} の場合、畳み込み結果 y [ n ] {\displaystyle y[n]} も周期的で同じ周期をとる。
1周期分の y [ n ] {\displaystyle y[n]} は、ちょうど1周期分の信号 x [ n ] {\displaystyle x[n]} (長さNx) と フィルタ h [ n ] {\displaystyle h[n]} (長さM) の畳み込みで得られる。ここでは前述のアルゴリズム 1を使う。畳み込み結果 y [ n ] {\displaystyle y[n]} は、区間 [M, Nx] で正しい。
先頭のM-1個(区間[1, M-1])の値に、末尾のM-1個(区間[Nx+1, Nx+M-1])の値を加算すれば、区間 [1, Nx] が正しい畳み込み結果を表すようになる。
変更した疑似コードは以下の通り: