分割基数FFTアルゴリズム

分割基数 FFT は、離散フーリエ変換(DFT) を計算するための高速フーリエ変換(FFT) アルゴリズムであり、R. Yavne (1968)[1] による当初はあまり評価されなかった論文で初めて説明され、その後 1984 年にさまざまな著者によって同時に再発見されました。(「分割基数」という名前は、これらの再発明者のうちの 2 人、P. Duhamel と H. Hollmann によって造られました。) 特に、分割基数は、基数 2 と 4 の組み合わせを使用するCooley–Tukey FFT アルゴリズムのバリエーションです。つまり、長さNの DFT を、長さN /2 の 1 つの小さな DFT と長さN /4の 2 つの小さな DFTで再帰的に表現します。

分割基数 FFT とそのバリエーションは、2 の累乗サイズNの DFT を計算するために、公表されている算術演算回数 (必要な実数の加算と乗算の正確な合計回数) が最も少ないという特徴を長い間持っていました。元の分割基数アルゴリズムの算術演算回数は 2004 年に改善されました (J. Van Buskirk による未発表の研究でN =64 の手動最適化によって得られた最初の改善 [2] [3]) が、分割基数の修正によって新しい最小の算術演算回数を達成できることがわかっています (Johnson と Frigo、2007)。算術演算回数は、コンピューターで DFT を計算するために必要な時間を決定する唯一の要因 (必ずしも支配的な要因ではありません) ではありませんが、最小可能な算術演算回数の問題は長年理論的に関心を集めています。(現在のところ、演算回数の厳密な下限は証明されていません。)

分割基数アルゴリズムは、 N が4 の倍数の 場合にのみ適用できますが、DFT をより小さな DFT に分割するため、必要に応じて他の FFT アルゴリズムと組み合わせることができます。

DFT は次の式で定義されることを思い出してください。

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}}$

ここで はからまでの整数であり、 は1 の原始根を表します。 ${\displaystyle k}$${\displaystyle 0}$${\displaystyle N-1}$${\displaystyle \omega_{N}}$

${\displaystyle \omega _{N}=e^{-{\frac {2\pi i}{N}}},}$

したがって: 。 ${\displaystyle \omega _{N}^{N}=1}$

分割基数アルゴリズムは、この合計を 3 つの小さな合計で表現することによって機能します。(ここでは、分割基数 FFT の「時間によるデシメーション」バージョンを示します。周波数によるデュアル デシメーション バージョンは、基本的にこれらの手順の逆になります。)

まず、偶数インデックスの合計です。次に、奇数インデックスの合計を と の 2 つの部分に分割します(インデックスが4 を法として 1 か 3 かによって異なります)。ここで、 は0から までのインデックスを表します。結果の合計は次のようになります。 ${\displaystyle x_{2n_{2}}}$${\displaystyle x_{4n_{4}+1}}$${\displaystyle x_{4n_{4}+3}}$${\displaystyle n_{m}}$${\displaystyle N/m-1}$

${\displaystyle X_{k}=\sum _{n_{2}=0}^{N/2-1}x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}}$

ここで、 という事実を使用しました。これらの 3 つの合計は、それぞれ基数 2 (サイズN /2) と基数 4 (サイズN /4) の Cooley–Tukey ステップの一部に対応します。(基数 2 の偶数インデックス サブ変換には乗法係数がないため、そのままにしておく必要がありますが、基数 2 の奇数インデックス サブ変換では、2 番目の再帰サブディビジョンを組み合わせることでメリットが得られるという基本的な考え方です。) ${\displaystyle \omega _{N}^{mnk}=\omega _{N/m}^{nk}}$

これらの小さな合計は、長さN /2 とN /4の DFT とまったく同じであり、再帰的に実行してから再結合することができます。

具体的には、長さN /2の DFT の結果( の場合) を で表し、長さN /4の DFT の結果( の場合) をと で表します。出力は単純に次のようになります。 ${\displaystyle U_{k}}$${\displaystyle k=0,\ldots ,N/2-1}$${\displaystyle Z_{k}}$${\displaystyle Z'_{k}}$${\displaystyle k=0,\ldots ,N/4-1}$${\displaystyle X_{k}}$

${\displaystyle X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}.}$

しかし、これは不要な計算を実行します。なぜなら、は と多くの計算を共有するからです。特に、 N /4 をkに追加しても、サイズN /4 の DFT は変更されません ( N /4で周期的であるため)。一方、サイズN /2 の DFT は、 N /2 をkに追加しても変更されません。したがって、変更されるのは、回転因子と呼ばれる項と項だけです。ここでは、恒等式を使用します。 ${\displaystyle k\geq N/4}$${\displaystyle k<N/4}$${\displaystyle \omega _{N}^{k}}$${\displaystyle \omega _{N}^{3k}}$

${\displaystyle \omega _{N}^{k+N/4}=-i\omega _{N}^{k}}$

${\displaystyle \omega _{N}^{3(k+N/4)}=i\omega _{N}^{3k}}$

最終的に到達するのは:

${\displaystyle X_{k}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}$

${\displaystyle X_{k+N/2}=U_{k}-\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}$

${\displaystyle X_{k+N/4}=U_{k+N/4}-i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}$

${\displaystyle X_{k+3N/4}=U_{k+N/4}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}$

上記の 4 つの式で からまでの範囲を指定した場合、すべての出力が得られます。${\displaystyle X_{k}}$${\displaystyle k}$${\displaystyle 0}$${\displaystyle N/4-1}$

これらの式は、さまざまな DFT 出力を加算と減算のペア（バタフライと呼ばれる）で組み合わせる必要があるように配置されていることに注意してください。このアルゴリズムの演算回数を最小限に抑えるには、（回転因子が 1 の場合）および（回転因子が であり、より高速に乗算できる場合）の特殊なケースを考慮する必要があります。たとえば、Sorensenら(1986) を参照してください。とによる乗算は通常、自由としてカウントされます（すべての否定は、加算を減算に変換することで吸収でき、その逆も同様です）。 ${\displaystyle k=0}$${\displaystyle k=N/8}$${\displaystyle (1\pm i)/{\sqrt {2}}}$${\displaystyle \pm 1}$${\displaystyle \pm i}$

この分解は、 Nが 2 の累乗の場合に再帰的に実行されます。再帰の基本ケースは、DFT が単なるコピーであるN =1と、DFT が加算と減算であるN =2 です。 ${\displaystyle X_{0}=x_{0}}$${\displaystyle X_{0}=x_{0}+x_{1}}$${\displaystyle X_{1}=x_{0}-x_{1}}$

これらの考慮の結果、実加算と乗算の回数がカウントされます( N >1 の場合は 2 の累乗)。このカウントは、2 の奇数累乗の場合、残りの係数 2 ( N を4 で割るすべての分割基数ステップの後) が DFT 定義 (4 つの実加算と乗算) によって直接処理されるか、または同等に基数 2 の Cooley-Tukey FFT ステップによって処理されることを前提としています。 ${\displaystyle 4N\log _{2}N-6N+8}$

• R. Yavne、「離散フーリエ変換を計算するための経済的な方法」、Proc. AFIPS Fall Joint Computer Conf. 33、115–125 (1968)。
• P. DuhamelとH. Hollmann、「Split-radix FFTアルゴリズム」、Electron. Lett. 20 (1)、14–16 (1984)。
• M. Vetterli および HJ Nussbaumer、「演算数を削減したシンプルな FFT および DCT アルゴリズム」、Signal Processing 6 (4)、267–278 (1984)。
• JB Martens、「再帰的円分因数分解 - 離散フーリエ変換を計算するための新しいアルゴリズム」、IEEE Trans. Acoust.、Speech、Signal Processing 32 (4)、750–761 (1984)。
• P. Duhamel と M. Vetterli、「高速フーリエ変換: チュートリアルレビューと最新技術」、Signal Processing 19、259–299 (1990)。
• SG Johnson および M. Frigo、「より少ない算術演算を備えた修正分割基数 FFT」、IEEE Trans. Signal Process。55 ( 1)、111–119 (2007)。
• Douglas L. Jones、「Split-radix FFT アルゴリズム」、Connexions Web サイト (2006 年 11 月 2 日)。
• HV Sorensen、MT Heideman、CS Burrus、「分割基数FFTの計算について」、IEEE Trans. Acoust.、Speech、Signal Processing 34 (1)、152–156 (1986)。