エレガントなSciPy ―Pythonによる科学技術計算

88

4 章　周波数と高速フーリエ変換

また

DFT

は、

scipy.sfignal.fftconvolve

が、大量の入力に高速畳み込みを実行する際にも使

われます。

SciPy

では、

Fortran

の

FFTPACK

ライブラリを採用しています。このライブラリは世界最速で

はありませんが、

FFTW

などのパッケージと違って、許容的フリーソフトウェアライセンスで許

諾されています。

4.5

　

DFT

の長さを決定する

まともに

DFT

を計算しようとすると

O(N

2

)

回の操作が必要です

†

。なぜでしょうか。異なる周

波数

（

πf × 0, 2πf × 1; 2πf × 3, ..., 2πf × (N – 1)2

）を持つ

N

個の（複素）正弦波があって、

信

号が各正弦波とどのくらいよく一致するかを調べたいわけです。最初の正弦波から順に、信号との

内積を取ります（この操作自体にも

N

回の乗法操作が伴います）。各正弦波に対してこの操作を

1

回ずつ、計

N

回繰り返すと、操作の合計は

N

2

回となるわけです。

では、これを

FFT

と比較します。

FFT

の場合は、理想的な場合では

O(N log N)

回になりま

す。計算を賢く再利用しているおかげです。すばらしく改良されましたね。しかし、

FFTPACK

に

実装されている（ひいては

SciPy

が使用する）古典的なクーリー

-

テューキー型アルゴリズムで

は、変換をサイズが小さい素数の断片に分割統治するので、「滑らかな」入力長の場合にだけ改良

の効果が出ます（入力長が滑らかとみなされるのは、図

4-9

に示されるように最大素因数が小さ ...