1.3 Prime Factor 型 FFT

1.3.4 Short DFT アルゴリズム

 ここでは,PFA や WFTA で使用可能な Short DFT ルーチンの設計方法に ついて考えます.この Short DFT は素数の長さが多く,通常の FFT の 考え方は適用できません.一般に,素数の長さの高速 DFT アルゴリズムを 設計する方法は,何らかの方法で DFT を畳み込みに変換し,FFT や,FFT の 考えに基づいた高速畳み込み算法を用いることです.ここでは,Rader の 方法と呼ばれる,素数の長さの DFT を簡単な添字の変換により巡回畳み込みに 変換する方法について示します.

 Rader の方法はまず,素数の長さの DFT

            N-1                                -2πij / N   
    A(k) =  Σ   a(j) W(N; jk) ,   W(N; j)  = e             
            j=0                                            

に対して,添字の変換

         q         
    k = g   mod N  


         -p         
    j = g    mod N  

を行います.ここで,g は原始根と呼ばれる整数です.数論によると N が 素数であれば,上の式において k = 1,2,...,N-1 の N-1 個の要素と q = 0,1,...,N-2 の N-1 個の要素との間に一対一写像をなすような原始根 g が存在することがわかっています.この変換を DFT に施すと

       q             N-2    -p         q-p     
    A(g  ) = a(0) +  Σ   a(g   ) W(N; g    )   
                     p=0                       

となり,さらに

       j     〜   
    A(g  ) = A   
              j  

       -j     〜   
    a(g   ) = a   
               j  

          j         
    W(N; g  ) = h   
                 j  

と置き直せば,もとの DFT は長さ N-1 の巡回畳み込み

    〜            N-2 〜           
    A  = a(0) +  Σ   a   h       
     q           p=0  p   q-p    

に変換されます.この方法はさらに,N が奇の素数の整数乗の場合にも 拡張できます.この方法と FFT により,素数の長さ N の DFT は, N*log(N) の演算量で設計できることになります.しかし,これは N が非常に 大きいときに有効な方法です.実際の Short DFT アルゴリズムは,畳み込みを 二つの多項式の積の計算であるとみなして,多項式の剰余分解に基づく方法で 設計します.詳しくは[参考文献]を参照して ください.これには,Rader の方法で設計された長さ N = 2,3,4,5,7,8,9,16 の 乗算回数の少ない Short DFT アルゴリズムが与えられています.


目次へ戻る