1.3 Prime Factor 型 FFT

1.3.3 Winograd DFT アルゴリズム (WFTA)

　Winograd DFT Algorithm (WFTA) は，PFA の多次元 DFT の計算ブロックにある変形を施したものです[参考文献]．この変形の基本的な考え方は，PFA の多重にネストされた Short DFT の演算の順序 (すなわち j1 に対する演算と j2 に対する演算の順序) は交換可能であるということです．WFTA は，ネストされた Short DFT を加算ブロックと乗算ブロックとに分け，それらを交換し乗算部を一つにまとめるというものです．この変形により，乗算回数は劇的に減少します．この変形を行うためには，Short DFT ルーチンの構造にある種の仮定が必要になります．その仮定とは，PFA で用いた Short DFT ルーチンのように Short DFT ルーチンが乗算ブロックと加算ブロックで構成されているというものです．

　WFTA は図で見ると一目瞭然になります．まず，長さが 3 と 5 の Short DFT ルーチンのデータフローとブロック図は次のようになります．

図1.3.3-1. 長さ 3 の Short DFT


図1.3.3-2. 長さ 5 の Short DFT

図1.3.3-3. 長さ N の Short DFT

この Short DFT ルーチンを用いた長さ 15 の PFA ルーチンのブロック図は次のようになります．

図1.3.3-4. 長さ 15 の PFA

この加算ブロックと乗算ブロックとを交換すると次のようになります．

図1.3.3-5. 長さ 15 の WFTA

この図で二段ある乗算部は一つにくくることができ，一段になります．この乗算部の係数はあらかじめ計算しておくことで，乗算回数を大幅に減らすことができます．これが WFTA の考え方です．一般に， M 段ある乗算部を一段にする変形で乗算回数は 1/M に減ります．しかし，WFTA の加算ブロックと乗算ブロックとを交換する変形で乗算回数が少し増えるため，全体の乗算回数は単純に 1/M にはなりません．N=15 の場合，18 回の乗算になり，PFA の半分の 15 回よりも少し増えます．さらに，WFTA では Short DFT に含まれる 1 による乗算は省略できなくなります．これは，乗算部を一つにするときに，ほとんどの係数が 1 ではなくなってしまうからです．それでも WFTA は PFA に比べて乗算回数は半分くらいに減ります．また，WFTA では演算量と引き換えに，in-place 演算ができなくなります．これは，一般に乗算部でのデータ数は最初のデータ数よりも多くなるからです．

　次に，演算量について少し詳しく考えます．その前に，長さ Ni の Short DFT の計算を μi 回の乗算 (WFTA では 1 による省略可能な乗算も含める)と αi 回の加算で行うことができると仮定しておきます．このとき，長さ N = N1 × N2 の WFTA の乗算回数 μ と加算回数 α は

    μ = μ1 μ2

    α = N2 α1 + μ1 α2

となることがわかります．ここで，N1 と N2 を逆にすると加算回数がかわることに注意してください．さらに一般に，長さ N が

      　  d　    
    N ＝ Π  N   
      　 i=1　i

のように d 個の因数に分解されたとき，WFTA の演算量は

    　 　  d 　　   
    μ ＝ Π   μ   
    　 　 i=1　　i  


    　 　   　 α1     μ1   α2     μ1   μ2   α3        　  
    α ＝ N （----- ＋ ----・---- ＋ ----・----・---- ＋ ...）  
    　 　   　　N1    　N1  　N2    　N1  　N2  　N3

となります．この乗算回数には 1 による乗算も含まれています．

　もし，長さ Ni の Short DFT が Ni^2 回の乗算で計算されるならば， WFTA の乗算回数は N^2 と最悪になり，全く意味をなしません．もし，長さ Ni のShort DFT が Ni*log(Ni) 回の乗算で計算されるならば，

    　 　    d　    　   
    μ ＝ N Π  log μ   
    　 　   i=1　   　i

となります．さらに，長さ Ni の Short DFT が最適に設計され，Ni に比例する乗算回数で計算されるならば

    　 　  　　　　 d    
    μ ＝ (比例定数)  N

となります．したがって，WFTA の演算量は，PFA のそれよりも必ずしもよくはならず，Short DFT の演算量に強く依存します．WFTA は実は， Short DFT の乗算回数が少なくなるように設計されているという仮定でのみ有効なアルゴリズムです．また，WFTA は長さ N1 × N2 ×... Nd の多次元 DFT をどういう順序で組み合わせるかによって加算回数が異なります．したがって，実際の設計では加算回数が少なくなるような組合せを選ぶことが必要になります．

目次へ戻る