重畳加算法
離散畳み込み ( h ∗ x ) [ n ] {\displaystyle (\mathbf {h} *\mathbf {x} )[n]} は、各区間の畳み込みの総和で表せる:
y [ n ] = ( h ∗ x ) [ n ] = ∑ m = 0 M − 1 ( h [ m ] ⋅ ∑ k x k [ n − m − k L ] ) = ∑ k ( h ∗ x k ) [ n − k L ] {\displaystyle {\begin{aligned}y[n]=(\mathbf {h} *\mathbf {x} )[n]&=\sum _{m=0}^{M-1}\left(h[m]\cdot \sum _{k}x_{k}[n-m-kL]\right)\\&=\sum _{k}(\mathbf {h} *\mathbf {x} _{k})[n-kL]\\\end{aligned}}}
ここで各区間の畳み込み 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} 点巡回畳み込みと等価である。
区間長 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} をゼロ・パディングで調整して計算量を最適化できる。) アルゴリズムの疑似コードは以下の通り: