信号長が2の累乗以外のFFTがやりたいです

質問

信号長が2^n以外で、高速にフーリエ変換することが出来る方法を探しております。

信号処理で、相互相関を扱っています。
しかし信号長が長いため下の関係を用いて、周波数領域で処理しようと思っています。
(xとyとの相互相関関数のフーリエ変換)=(X*)・Y　(xのフーリエ変換したものの共役複素数)・（yのフーリエ変換したもの)

しかし、信号長が2^nではないためゼロ詰めした場合の相互相関値には誤差が出てしまいます。
ですので、2^n以外の信号長で高速にDFT出来る方法を探しております。

その方法や、解説ページ、プログラムなど、御存じの範囲で構いませんので教えてください。
よろしくお願いします。

回答No.1

Tacosan

一般論でいくと, 信号長 n = p1・p2・...・pk と書ける (p1, p2, ... の中には同じものがあってもよい) ときに DFT なら n^2 時間かかるところ FFT では n(p1 + p2 + ... + pk) 時間になる, んだったかな? 本質的には, 各 pi に対し「大きさ pi のブロック」ごとに DFT のようなことをするだけだったはずです.
う～ん, 自分で書いていてかなり不安なので, n = 6 = 2・3 くらいでチェックしてみてください.

お礼

回答ありがとうございました。

結局、fftwという有名なアルゴリズムを知人に教えていただき、
それを使うことになりました。