2.1 実離散 Fourier 変換

 実際に用いられる DFT のデータのほとんどは実数です.この実数データの DFT を計算するもっとも単純な方法は,虚数部にゼロをつめて複素 FFT で 計算することです.しかし,これは半分の無駄な計算が含まれます.さらに, 入力データは半分がゼロで,出力も複素共役対称になり,データの半分が 冗長になります.しかし,この問題はちょっとした工夫で解決できます. ここでは,複素 FFT の虚部を有効に活用する方法と,複素 FFT を変形して 無駄な計算を省く方法の二つについて示します.

2.1.1 複素 FFT を間接的に用いる方法

 ここでは,複素 FFT を利用して実数データの DFT を計算するいくつかの 効率的な方法について示します.

第一の方法

 ます,第一の方法は,一つの複素 FFT を用いて二つの実数データの DFT を同時に計算するというものです.方法は,入力の複素データの 実部に一つ,虚部にもう一つの実数データを入れて複素 FFT を呼び出す というものです.すなわち,二つの実数データ r_j,s_j を一つの 複素数データ

                      
    a  = r  + i s     
     j    j      j    

にまとめて,長さ N の複素 FFT を実行します.複素 FFT の出力 A_k は, 複素共役対称性から

                      
    A  = R  + i S     
     k    k      k    


    _                   
    A    = R  − i S     
     N-k    k      k    

が成り立つので,容易に A_k,A_N-k から DFT の結果 R_k,S_k が 求められることになります.この後処理は,スケーリングを無視すれば 加算だけで実行でき,後に示す実数専用の FFT ルーチンを用いる方法と 比較してほぼ同じ効率で計算できます.一方,この方法は同時に二つの DFT を計算してしまうので,使用目的が制限されるという欠点があります. さらに,この方法の応用で細かい注意があります.たとえば,r_j の 絶対値がs_j に比べて非常に大きい場合は,途中の混合された計算で S_k は R_k に含まれる大きな誤差に埋もれてしまう危険性があります. 誤差を最小にするためには,二つのデータの値を同じ程度にそろえて おかなければなりません.しかし,二つのデータの値が極端に異ならない 場合や,二つのデータが独立でない場合 (たとえば多次元 FFT の Row-Column 法での二列を同時に変換する場合) などではそれほど 気にする必要はありません.

第二の方法

 第二の方法は,一つの実数データの DFT を半分の長さの複素 FFT で 計算するという方法です.方法は,時間間引きの FFT の分解を一段だけ行い, 長さ N の実数データの DFT を N/2 の長さの二つの DFT に分解し,上の 第一の方法を用いるというものです.具体的には,まず入力の複素データの 実部に実数データの偶数番目,虚部に奇数番目の実数データを入れて 複素 FFT を呼び出します.すなわち,実数データ r_j を複素数データ

                          
    a  = r   + i r        
     j    2j      2j+1    

として,長さ N/2 の複素 FFT を実行します.実数 DFT の出力 R_k は, 第一の方法と時間間引きの FFT のバタフライ演算を組み合わせた演算

                        1     i    k         _         
    R     =  A      − (--- + --- W   ) (A  − A      )  
     k        k         2     2   N      k    N/2-k    


    _        _          1     i    k         _         
    R     =  A      + (--- + --- W   ) (A  − A      )  
     N/2-k    N/2-k     2     2   N      k    N/2-k    


    (1 <= k < N/4)

                            
    R  = Re(A  ) + Im(A  )  
     0       0         0    

                              
    R    = Re(A  ) − Im(A  )  
     N/2       0         0    

                 
    R    = A     
     N/4    N/4  

から復元できます.この方法の演算量は,長さ N/2 の複素数 FFT の演算量に N/4-1 回の複素数乗算と 3*N/4-2 回の複素数加算を加えたものとなります. 多くの書物での同様な算法は,変形が甘く演算量はこれより少し多くなるので 注意してください.

 また,実数データの DFT の逆変換 (すなわち複素共役対称な DFT) は これらの手順を逆にすることで得られ,演算量もまったく同じになります.

 これらの方法は,複素 FFT だけを用意しておけばよいのでプログラミングの 手間が省けるという利点があります.


目次へ戻る