ホーム ] FFT乗算 ] 逆数除算 ]

上へ
FFT乗算の原理
FFT乗算原理の確認
基数の決定
FFT方式の決定
FFTライブラリ開発
システムへの組込み

FFT乗算

FFT乗算の原理

最終更新日:2007/04/26 見直し

●概要

  導入にあたり、フーリエ変換やFFTはあるものとして、FFT乗算についての原理と乗算の方法を調べた。

●原理

 フーリエ変換は、数学的には 直交変換(積分変換)の一つで、信号(一次元、二次元、画像、物体など、データであれば結局何でも良い)を全く別の切り口で表現するものである。フーリエ変換では、周期関数の集合として表現する。離散系では有限の集合となる。実空間では距離などであったものが、フーリエ空間では、周波数と 解釈すればよい。ここでは、フーリエ変換には言及しないので、他書に依られたい。

○畳み込み

 重要な数学演算に、畳み込み(コンボリューション)がある。これは、ある関数 f に、別の関数 g を重畳させる演算である。通常、f*g と表す。連続空間では畳み込み積分となる。これは、一言で言えば、あるデータ群に対して、一定の変形を連続的に施すことになり、例えば、フィルタを掛けるイメージとなる。畳み込みは離散系でもあり、この場合は、積分ではなく、総和となる。離散系の畳み込みのk番目の要素は、

 (f*g)(k) = 杷(n)*g(k-n)

と表される。但し、離散系では区間が有限であるため、周期関数と見なされ、循環畳み込みとなる。つまり、f が区間を周期として繰り返し現われるとしている。ちなみに、連続系では、-∞から+∞の線形畳み込みとなる。 

○多項式の掛算

 さて、f、g を多項式の係数列とすれば、簡単のため、3要素とすると、その掛算は、                                      

    f0 f1 f2
    g0 g1 g2
    f0*g2 f1*g2 f2*g2
  f0*g1 f1*g1 f2*g1  
f0*g0 f1*g0 f2*g0    
f0*g0 f0*g1+f1*g0 f0*g2+f1*g1+f2*g0 f1*g2+f2*g1 f2*g2

となる。最下段が積の結果である。これは、実は、離散系の畳み込みに他ならない。しかも、筆算で行う数値の掛算とも同じである。但し、筆算の掛算では、随時桁上げ処理を行うことが異なっている。数値も多項式であるから、数値の掛算も、離散系の畳み込みと同じと言える。

○畳み込み定理

 フーリエ変換の重要定理に、畳み込み定理がある。それは、

  F(f*g) = F(f)・F(g)

で、実空間の畳み込みのフーリエ変換は、元の関数のそれぞれのフーリエ変換の単純な積(要素同士)になる。下図のようになる。乗算回数が、N2 から N になる。これは、例えば、フィルタ(周波数フィルタ)では、フーリエ空間では、要素が既にそれぞれの周波数成分なので、それぞれの成分を個々に補正(フィルタリング)すれば良い・・・と言うイメージを浮かべてもらえば分かり良い。

 もう、お分かりと思うが、数値を多項式と見立てて(本来は多項式なのだが)、多項式の乗算、即ち、離散系の畳み込みをフーリエ空間で行い、それを実空間に戻して、数値の乗算をしたことにするのである

 今、4096個(まあ、桁と思って良い)の一次元データに4096個データの一次元フィルタを掛けるとすれば、実空間では、4096*4096 約1678万回の乗算が必要となるが、DFTでは、畳み込みだけでは、0.4万回で済む。前後に3回のDFTが必要となるが、この分は、FFTで行えば8万回程度なので、約8.4万回で済むことになる。約200倍のスピードとなる。

 FFTにより、畳み込みがDFTで現実的に行えるようになり、今日の隆盛を見ているのである。

●方法

○数値の扱い

 DFTではサンプリングデータ列 a(i) が入力となる。今、乗算したい数値N を、多項式とすれば、

 N = (ai * Bi)

と表せる。つまり、数値N は基底数B のB進数表現に他ならない。MegaLong では、B = 100,000,000 となっている。この多項式の、ai を、サンプリングデータ列 a(i) と思えば良い。

○FFT乗算の方法

  1. 被乗数、乗数をデータ列、a(i)、b(i) とする。配列の要素数を偶数にし、かつ乗算結果は、二つの配列サイズの合計になるので、a、b とも、2倍にし、後半に0を埋める。つまり、3者同じサイズにする。これは、循環畳み込みの弊害(折り返し誤差など)を避け、線形畳み込みにしていることになる。
  2. a(i)、b(i) のフーリエ変換、A()、B() を求める。複素数の乗算が必要。
  3. A()、B() の同じ要素同士の乗算(つまり、コンボリューションする)を行い、これをC() とする。
  4. C() を逆フーリエ変換する。これをc() とする
  5. c() は、基底数を越える部分が出てくるので、桁上げを行う、あるいは、桁合せを行う。筆算でもやっている筈。これが、乗算結果となる。最後の要素は常に 0 となる。c() では、かなりの項目数の総和となり(中央の項が最も多くなる)、下手をすればオーバーフローすることが考えられる。整数演算では、基数の選択が重要となる。.NETでは、Doubleの有効整数桁を超えない範囲に設定する必要がある。