新しいものづくりがわかるメディア

RSS


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を解明しようと決めたという。

fabcross for エンジニアより転載)

関連情報

おすすめ記事

 

コメント

今人気の記事はこちら

  1. PythonでI/O制御プログラミング——CQ出版が「エレキジャックIoT No.4」を刊行
  2. バルミューダ初のスピーカー開発秘話——入社初日で開発最前線に立ったエンジニア
  3. 50年前のオートバイ「スズキGT380」をミニマムデザインでカスタム
  4. レトロゲームでプログラミングを学ぶ——ポータブルゲームコンソール「Xtron Pro」
  5. 芝浦工業大学、印刷によって紙を自律的に折り畳む技術を開発
  6. Raspberry Piでドローンを飛ばそう——クワッドコプター組み立てキット「Clover」
  7. グラフェンから無限の電力を引き出す、小型デバイス向けエナジーハーベスト回路を開発
  8. 趣味から仕事まで使える!Raspberry Pi(ラズパイ)の使い方とオススメキット
  9. ロボットやドローンにも搭載可能——ミリ波レーダーセンサー「RadarIQ」
  10. おうち時間でロボットプログラミング——スイッチサイエンス、子ども向けWebショップ「LABO KIDS」開設

ニュース

編集部のおすすめ

連載・シリーズ

注目のキーワード

もっと見る