ここでは,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 アルゴリズムが与えられています.