Chirp z変換によるFFT

2の基数のFFTがとりあえずできたので、まずそれを利用して任意の点数に対応できるアルゴリズムであるChirp z変換によるFFTをまとめてみる。これ、面白い。

Chirp z変換を利用した任意基数のFFT

Chirp z変換はこのサイト（ゲストでログインすると見せてもらえる）を見て初めて知ったのだけどなかなか面白い（ところでこのサイトは名前の綴りを間違ってる。sinやcosの中にtの非線形な項が入っている信号を音として聴くと音程が変わってぴゅいぴゅん、ぴよぴよと聴こえることからChirp）。Bluesteinのアルゴリズムとも言うらしい。

サイトを参考にノーテーションを今までのものに合わせて補いながら書き直してみる。

まずもとのDFTの定義

にちょっと細工をする。ちょっと都合でこないだの「回転因子」はexponentialのまま残す。

と書いてみる。これは最後のexponentialの肩を展開してみれば式-1と一致することがわかる。

この式の一部を

と書くと式-25は

と書ける。

G(k)は

と書くとp(n)とq^†(n)の畳み込みとみなすことができる。ここでa^†はaの複素共役を表している（勉強させてもらったサイトとは複素共役を逆に定義してる。これはあとの実装の都合でこうしたけど、本質的には同じ）。これを使って式-25を書き直すと

となる。ここで(a ⊗ b)_(k)はaとbの畳み込みで、その結果の添字をkにする、という意味である。

畳み込みはDFTを使って計算できる。このままでは一つのDFTを計算するために、DFTを2回、逆DFTを1回実行することになってなにもうれしくない。

ところが、この畳み込みはもとの長さNではなく、任意性がある。従って畳み込みのためのDFTを効率の良い2のベキのFFTを使えるようにすれば計算量が減る可能性がある。

もうすこし詳細をみてみる。