Laser Focus World JAPAN　レーザーフォーカスワールドジャパン

February 1, 2012, Cambridge--マサチューセッツ工科大学(MIT)の研究グループがSODA(Symposium on discrete Algorithms)で高速フーリエトランスフォーム(FFT)を改善する新しいアルゴリズムを発表した。
この改善は、ある状況下では劇的であり、10倍の高速化が実現可能だ。新しいアルゴリズムは特に画像圧縮に有用であり、例えばスマートフォンは大容量のビデオファイルを、バッテリーの消耗なしに、割り当てられた帯域を消費し尽くすことなく送ることができるようになる。
FFTと同様、新しいアルゴリズムはデジタル信号で動作する。デジタル信号とは単に一連の数字、楽器の音のようなアナログ信号の個別サンプルにすぎない。FFTは、一定数のサンプルを含むデジタル信号をとりだして、同数の周波数のウエイト付けされた総和としてそれを表す。
フーリエ変換で、強く重みづけされた周波数を相対的に少ない数しか含まない信号は「スパース」(疎)と言う。この新しいアルゴリズムは、信号の最大級のウエイト付周波数のウエイトを決める。信号がスパースであればあるほど、そのアルゴリズムで益々高速化する。実際、信号が十分にスパースであれば、アルゴリズムは全体を読むのではなくランダムにサンプリングすればよいことになる。
この新しいアルゴリズムは、2つの主要なアイデアに依拠している。まず、信号をより狭い帯域にスライスし、一般的に1つのスライスがヘビーウエイトの1つの周波数のみを含むようにする。
信号処理では、特定の周波数を分離するための基本ツールは1つのフィルタだが、フィルタは境界が曖昧になりがちだ。一連の周波数は、多かれ少なかれ無傷でそのフィルタを透過する。その範囲の直ぐ外側の周波数はなお一層減衰する、さらに同様に減衰し、究極的にはそれらの周波数はほぼ完全にフィルタで除去されるところまで行く。
もしヘビーウエイトの1つの周波数がフィルタのエッジのところに存在するようなことが起こると、その周波数は特定できないほど減衰することになる。したがって、研究チームはまず、フィルタがオーバーラップするような、コンピュータ計算上効率的な方法を見いだすことだった。そうするとターゲットにしている範囲の内部では周波数が不当に減衰することはなく、スペクトラムスライス間の境界は極めてシャープな状態にとどまる。
スペクトラムスライスを分離した後、研究グループはそのスライスで最もウエイトが重い周波数を特定しなければならない。SODA論文では、スペクトラムスライスを繰り返しカットして大部分の信号パワーが集中している周波数のみを保持する。しかし、未発表の論文では、遙かに効率的な技術について触れている。それは4G携帯ネットワークから信号処理法を借用するというものだ。周波数は一般に、上下動するものだが、振幅とも考えられる。異なる時間で同じ帯域のスライスをサンプリングすることで、研究グループは振動周期のどこに支配的な周波数が存在するかを特定することができる。
(詳細は、www.mit.edu)