首都大学東京 都市教養学部数理科学コース 関谷博之 高速フーリエ変換 ハードウェア設計 首都大学東京 都市教養学部数理科学コース 関谷博之
フーリエ変換 目的 フーリエ変換とは 画像とフーリエ変換 高速フーリエ変換 ハードにて高速フーリエ変換 今後
目的 今我々は 「電動車椅子における危険物探査システムの開発」 を研究室で行っております。 ・そのため、画像処理技術の一つである 「高速フーリエ変換（Fast Fourier Transform, FFT)」 のハードウェアでの開発を行いました。
sin,cosの組み合わせで表すことができる！ フーリエ変換とは 公式 ・オイラーの公式： フーリエ変換をすると sin,cosの組み合わせで表すことができる！
画像とフーリエ変換 画像 フーリエ変換の役目 ｆ（ｘ、ｙ） F(u,v) フーリエ変換 Ｘ、ｙの空間領域 の空間周波数領域 ｆ（ｘ、ｙ） F(u,v) フーリエ変換 こちらでの処理の方が楽 u,v Ｘ、ｙの空間領域 の空間周波数領域 画像
フーリエ変換の利用例 合体 元の信号（低周波） 受信された信号 ノイズ（高周波） 元の信号と違う！
信号成分 ノイズ成分 フーリエ変換 周波数 ノイズ成分カット 逆フーリエ変換 元の信号 周波数
信号成分 ノイズ成分 フーリエ変換 周波数 ノイズ成分カット 逆フーリエ変換 元の信号 周波数
フーリエ変換と離散フーリエ変換 アナログ信号 デジタル信号 フーリエ変換 離散フーリエ変換 空間領域 周波数領域 「信号はその最大周波数の2倍の周波数でサンプリングすれば、 サンプリング後の不連続な信号から元の連続的な信号を再現する ことができる」という定理があります。 （サンプリング定理） フーリエ変換 アナログ信号 空間領域 周波数領域 離散フーリエ変換 デジタル信号
高速フーリエ変換（FFT） 高速フーリエ変換とは 離散フーリエ変換 高速フーリエ変換 高速化 ・高速フーリエ変換は離散フーリエ変換の乗算（・加算）の回数を減らすことで 高速化。 ・高速フーリエ変換では のデータを偶数番目と奇数番目に分け、 それぞれに離散フーリエ変換を行う。
例（N=8の時) 乗算６４回 X(0)= X(１)= X(２)= X(３)= X(４)= X(５)= X(６)= X(７)= 回転子は とする X(0)= X(１)= X(２)= X(３)= X(４)= X(５)= X(６)= X(７)= 乗算６４回
ハードにて Ｗｈｙハードウェア？ ハードウェアの方が断然早い。 ・並列処理で行うため ・バタフライ演算利用のため 単純計算の繰り返し。 かかる時間は指定したクロックのみ
バタフライ演算 ｘ１（０） ｘ２（０） ｘ３（０） Ｘ（０） ｘ（０） ｘ１（１） ｘ２（１） ｘ３（１） Ｘ（１） ｘ（１） －１ ここで ｘ１（０） ｘ２（０） ｘ３（０） Ｘ（０） ｘ（０） ｘ１（１） ｘ２（１） ｘ３（１） Ｘ（１） ｘ（１） －１ ｘ（２） ｘ１（２） ｘ２（２） ｘ３（２） Ｘ（２） －１ ｘ１（３） ｘ２（３） ｘ３（３） Ｘ（３） ｘ（３） －１ Ｘ（４） ｘ（４） ｘ１（４） ｘ２（４） ｘ３（４） －１ ｘ１（５） ｘ２（５） ｘ３（５） Ｘ（５） ｘ（５） 足し算 －１ ｘ２（６） ｘ３（６） Ｘ（６） ｘ１（６） ｘ（６） －１ 引き算 ｘ（７） ｘ１（７） ｘ２（７） ｘ３（７） Ｘ（７） －１
ハードの難点 ○ 小数点の認識ができない。 →浮動小数点or固定少数点 浮動小数・・・ 浮動小数・・・ 固定小数と比較するとさまざまな誤差が発生しやすいが、絶対値の大きな値や、逆に絶対値の小さな値を表現するのに向いている。そのため、誤差の概念がはっきりしている分野や、極端な数を扱う分野で多く用いられている。また、プログラミング言語のほとんどが対応しているということもあり、小数の表現方法としては最も普及している。 固定小数点数と比べると演算速度が遅いため、別途FPU（浮動小数点数プロセッサ）という浮動小数点数演算の高速化専用の装置を搭載している場合が多い。今ＣＰＵには実装しているものが多い。 固定小数・・・精度をあらかじめ指定しておきその中で表現する。 よって、指定された精度の中では誤差が出ず、計算も速い。 ○
今後 終わります。 実際の画像データに対して行う。 画像データの受け取り方に対して高速化。 Radix-2(基底２）からRadix-4（基底４）。 ＦＦＴ後の処理の拡大・開拓。 終わります。