FFT による巡回畳み込み

目次

• Cooley-Tukey FFT
• FFT による巡回畳み込み ← 今回の話
• Bluestein's FFT

本題

配列長 $N$ の配列 $a$ と $b$ があったとき、その巡回畳み込み $c$ は

\begin{aligned}
& c[n] =
  \sum_{m=0}^{N - 1}
    a[m] \cdot b[(n-m) \mod N] &
  & ( 0 \le n < N ) &
\end{aligned}

で定義される。
そして、このときの $a, b, c$ は離散フーリエ変換 $\mathcal{F}$ を用いて以下が成り立つことが知られている。

\mathcal{F}(c) = \mathcal{F}(a) \cdot \mathcal{F}(b)

証明:

\begin{aligned}
& \mathcal{F}(c)[k] &=&
  \sum_{n=0}^{N-1}
    c[n]
    \exp\left(-2\pi i \frac{n k}{N}\right) & \\
& &=&
  \sum_{n=0}^{N-1}
    \left(
    \sum_{m=0}^{N - 1}
      a[m] \cdot b[(n-m) \mod N]
    \right)
    \exp\left(-2\pi i \frac{n k}{N}\right) & \\
& &=&
  \sum_{m=0}^{N-1}
    a[m]
    \sum_{n=0}^{N - 1}
      b[(n-m) \mod N]
    \exp\left(-2\pi i \frac{n k}{N}\right) & \\
& & & \downarrow l = n - m\ と置くと & \\
& &=&
  \sum_{m=0}^{N-1}
    a[m]
  \sum_{l=0}^{N - 1}
    b[l]
    \exp\left(-2\pi i \frac{(m+l) k}{N}\right) & \\
& &=&
  \sum_{m=0}^{N-1}
    a[m]
    \exp\left(-2\pi i \frac{m k}{N}\right)
  \sum_{l=0}^{N - 1}
    b[l]
    \exp\left(-2\pi i \frac{l k}{N}\right) & \\
& &=& \mathcal{F}(a)[k] \cdot \mathcal{F}(b)[k] &
\end{aligned}

これに FFT を利用すると巡回畳み込みを $O(N \log N)$ で計算できる。

c[n] = \mathcal{F}^{-1}(\mathcal{F}(a) \cdot \mathcal{F}(b))[n]

ただし、Cooley-Tukey FFT では配列長が合成数になっている必要があった。
そのため、配列長が素数などの場合は適当に長さを調整したい。
計算結果は変えずに配列長を $N \rightarrow N'$ に伸ばした配列 $a', b'$ を作れるか考える。
巡回畳み込みの定義をもう一度見返してみる。

\begin{aligned}
& c[n] =
  \sum_{m=0}^{N - 1}
    a[m] \cdot b[(n-m) \mod N] &
  & ( 0 \le n < N ) & \\
\Rightarrow & c[n] =
  \sum_{m=0}^{N' - 1}
    a'[m] \cdot b'[(n-m) \mod N'] &
  & ( 0 \le n < N ) &
\end{aligned}

$a'$ は $a$ の末尾を $0$ で埋めると良さそうだが、 $b'$ はやや複雑である。
$b'$ は $b'[n \mod N']\ (-N < n < N)$ の範囲が元々の計算に利用される。
言い換えると $b'$ の末尾 $N-1$ 個と先頭 $N$ 個の範囲が利用されるため、この要素は変更せず中央に $0$ を追加することとなる。
つまり $N'$ は最低でも $2N-1$ 以上にする必要があるということになる。

\begin{aligned}
& a &= [&a_{0}&, &a_{1}&, &a_{2}&] \\
& b &= [&b_{0}&, &b_{1}&, &b_{2}&] \\
&&& \downarrow & \\
& a' &= [&a_{0}&, &a_{1}&, &a_{2}&, &0&, &...& &&&&, &0&] \\
& b' &= [&b_{0}&, &b_{1}&, &b_{2}&, &0&, &...&, &0&, &b_{1}&, &b_{2}&]
\end{aligned}

このような配置にすることで任意の配列長の巡回畳み込みを Cooley-Tukey FFT で行うことができる。

c[n] = \mathcal{F}^{-1}(\mathcal{F}(a') \cdot \mathcal{F}(b'))[n]

参考

• Convolution - Wikipedia