Real FFT
FFTは複素信号を処理します。入力は複素信号であり、出力も複素信号です。ところが、実数しか必要としないアプリケーションはたくさんあります。そのような場合、虚部を0としてFFTを行うわけですが、もったいない点は否めません。何とかならないかと思うのが人情です。そしてうまい具合に何とかする手だてがあります。Real FFTです。
実数データの複素FFT結果
はじめに、実数データr[]を複素FFTにかけた場合の結果について考えます。
R=FFT(r)
ここでFFT結果の実部Re(R)と虚部Im(R)を調べてみると、おもしろいことがわかります。
- Re(R[])は左右対称になる（偶関数）
- Im(R[])は点対称になる（奇関数）
ちょっとScilabで適当なデータを作ってFFTにかけた結果をお見せしましょう。入力データは実数配列です。
最初にお見せするのは実部 Re(R)。左右対称になっています。
[f:id:suikan:20101219195452p:image]
次が虚部 Im(R)。点対称になっています。
この結果から次のことが言えます。
まず、実部のデータですが、中点を軸にして紙を折るようにして対応する両側のデータを足しあわせると*1、結果はそれぞれのデータが２倍になります。なぜならデータは線対称になっており、同じデータが左右に広がっているからです。
一方、実部のデータですが、同じように中点を軸にして両側のデータを足しあわせると、対応するおのおののデータは絶対値が同じで符号が逆なのですべて0になってしまいます。
虚数データの複素FFT結果
つぎに、実部のない虚数だけのデータをFFTにかけるとどうなるか考えてみましょう。これはFFTの性質から簡単に導き出せます。
FFTは線形な変換です。つまり、
FFT(Ar) = A FFT(r)
が成立すると言うことです。ここから直ちに
FFT(ir) = iFFT(r) = iR[]
だということがわかります。言い換えると、純粋虚数データのFFT結果は、実数データのFFT結果にiをかけたものになります。
したがって、irのFFT結果であるiRは次のようになります。
- Re(iR)= -Im(R)は点対称になる（奇関数）
- Im(iR)= Re(R)は左右対称になる（偶関数）
実データの虚データのFFT結果の比較
ここまでの結果をまとめるとこうなります。
| データ処理 | 結果の実部 | 結果の虚部 |
|---|---|---|
| 実データのFFT | 偶関数 | 奇関数 |
| 虚データのFFT | 奇関数 | 偶関数 |
これを利用すると、複素データのFFT結果から、実データのFFT結果と虚データのFFT結果を分離することができます。具体的には中心を軸として対応するデータの和と差をとることで、偶関数データと奇関数データを取り出すことができます。これは非常におもしろい性質です。
Real FFTの実装方法
複素データのFFT結果から実データのFFT結果と複素データのFFT結果を取り出せることから、実データFFTの計算量を以下のようにして削減できます。
- N点の実データを前半と後半に二分する。
- 後半のデータにiをかけて前半のデータと足す
- 合成した複素データをN/2点FFTにかける
- 結果から実部のFFT結果と虚部のFFT結果を取り出す
- 虚部のFFT結果に-iをかけて実部のFFT結果の後ろにつなげる
- N点バタフライをかける
これによって、N点実データのReal FFTをO(N/2 log(N/2))で実行できます。Nが十分大きければ、N点複素FFTの半分の時間で実FFTを実行できます
