50年来の信号処理に関する謎が解かれる、逆高速フーリエ変換がついに一般化

  • このエントリーをはてなブックマークに追加

Photo by Paul Easker.

アメリカのアイオワ州立大学電気コンピューター工学科准教授のAlexander Stoytchev氏と博士課程学生のVladimir Sukhoy氏は、信号処理の肝と言われる高速フーリエ変換(Fast Fourier transform:FFT)と逆高速フーリエ変換(Inverse Fast Fourier transform:IFFT)のアルゴリズムの研究を進め、50年間にわたり謎であったIFFTアルゴリズムを解明したと発表した。研究成果は『Scientific Reports』に論文「Generalizing the inverse FFT off the unit circle」として2019年10月8日に発表されている。

FFTアルゴリズム自体は1965年に公開され、その4年後には汎用性の高い一般化されたバージョンであるチャープZ変換(CZT)も開発されてきた。しかし、IFFTアルゴリズムの一般化はその後50年間も解明されないままであった。今回、Stoytchev氏とSukhoy氏によって、IFFTアルゴリズムの一般化である逆チャープZ変換(ICZT)が解明された。

他のアルゴリズムと同様に、ICZTもステップを踏んで問題を解決していく手法を取る。具体的には、CZTアルゴリズムの出力をICZTの入力にフィードバックする。 CZTとICZTの2つのアルゴリズムは、プリズムの対のようなもので、プリズムの一つ目が白色光の波長を色のスペクトルに分離し、二つ目のプリズムがスペクトルを組み合わせて白色光に戻す逆プロセスを取る過程として説明できる。

研究では、ICZTアルゴリズムが計算複雑性ないし速度に相当するものに一致すること、IFFTでは行えない指数関数的に減衰または増加する周波数成分に対して利用できること、そして数値精度について実証済みだ。

Stoytchev氏は、大学院のコンピューター認知のクラスで学生が高速フーリエ変換を理解するのに役立つ例えを探している時に、未だ解明されていないアルゴリズムを定式化してみようというアイデアをひらめいた。

多くの信号処理に関する文献を読みあさったが、CZTを逆変換する文献は何も見つからなかった。文献が見つからなかったことから、これまでICZTは説明されていないか存在していないことに気づき、ICZTに興味を持ち、実際にICZTを解明しようと決めたという。

関連リンク

Engineers solve 50-year-old puzzle in signal processing
Generalizing the inverse FFT off the unit circle

関連記事

アーカイブ

fabcross
meitec
next
メルマガ登録
ページ上部へ戻る