分割基数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 は次の式で定義されることを思い出してください。

X け ＝ ∑ n ＝ 0 北 − 1 × n ω 北 n け {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}}

ここで、は からの範囲の整数であり、は 1の原始根を表します。 け {\displaystyle k} 0 {\displaystyle 0} 北 − 1 {\displaystyle N-1} ω 北 {\displaystyle \omega _{N}}

ω 北 ＝ e − 2 π 私 北 、 {\displaystyle \omega _{N}=e^{-{\frac {2\pi i}{N}}},}

したがって： ω 北 北 ＝ 1 {\displaystyle \omega _{N}^{N}=1}

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

まず、偶数インデックスの総和を求めます。次に、奇数インデックス の総和を と に分けます。これは、インデックスが 4 を法として 1 か 3 かによって決まります。ここで、 は0 から までのインデックスを表します。結果として得られる総和は次のようになります。 × 2 n 2 {\displaystyle x_{2n_{2}}} × 4 n 4 + 1 {\displaystyle x_{4n_{4}+1}} × 4 n 4 + 3 {\displaystyle x_{4n_{4}+3}} n メートル {\displaystyle n_{m}} 北 / メートル − 1 {\displaystyle N/m-1}

X け ＝ ∑ n 2 ＝ 0 北 / 2 − 1 × 2 n 2 ω 北 / 2 n 2 け + ω 北 け ∑ n 4 ＝ 0 北 / 4 − 1 × 4 n 4 + 1 ω 北 / 4 n 4 け + ω 北 3 け ∑ n 4 ＝ 0 北 / 4 − 1 × 4 n 4 + 3 ω 北 / 4 n 4 け {\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番目の再帰分割を組み合わせることで利点が得られるというものです。） ω 北 メートル n け ＝ ω 北 / メートル n け {\displaystyle \omega _{N}^{mnk}=\omega _{N/m}^{nk}}

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

より具体的には、長さN /2のDFTの結果（ の場合）を 、長さN /4のDFTの結果（ の場合）を と とします。すると、出力は単純に以下のようになります。 あなた け {\displaystyle U_{k}} け ＝ 0 、 … 、 北 / 2 − 1 {\displaystyle k=0,\ldots,N/2-1} Z け {\displaystyle Z_{k}} Z け ′ {\displaystyle Z'_{k}} け ＝ 0 、 … 、 北 / 4 − 1 {\displaystyle k=0,\ldots ,N/4-1} X け {\displaystyle X_{k}}

X け ＝ あなた け + ω 北 け Z け + ω 北 3 け Z け ′ 。 {\displaystyle X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}.}

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

ω 北 け + 北 / 4 ＝ − 私 ω 北 け {\displaystyle \omega_{N}^{k+N/4}=-i\omega_{N}^{k}}
ω 北 3 （ け + 北 / 4 ） ＝ 私 ω 北 3 け {\displaystyle \omega_{N}^{3(k+N/4)}=i\omega_{N}^{3k}}

最終的に到達する：

X け ＝ あなた け + （ ω 北 け Z け + ω 北 3 け Z け ′ ） 、 {\displaystyle X_{k}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}
X け + 北 / 2 ＝ あなた け − （ ω 北 け Z け + ω 北 3 け Z け ′ ） 、 {\displaystyle X_{k+N/2}=U_{k}-\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}
X け + 北 / 4 ＝ あなた け + 北 / 4 − 私 （ ω 北 け Z け − ω 北 3 け Z け ′ ） 、 {\displaystyle X_{k+N/4}=U_{k+N/4}-i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}
X け + 3 北 / 4 ＝ あなた け + 北 / 4 + 私 （ ω 北 け Z け − ω 北 3 け Z け ′ ） 、 {\displaystyle X_{k+3N/4}=U_{k+N/4}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}

これは、上記の 4 つの式 で からまでの範囲を指定した場合のすべての出力を示します。 X け {\displaystyle X_{k}} け {\displaystyle k} 0 {\displaystyle 0} 北 / 4 − 1 {\displaystyle N/4-1}

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

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

これらの考慮から、 N >1 （2のべき乗）の場合の実加算と乗算の回数が算出されます。この回数は、2の奇数乗の場合、残りの2の係数（ Nを4で割る分割基数ステップをすべて実行した後）がDFT定義（4回の実加算と乗算）によって直接処理されるか、または同等の基数2のCooley-Tukey FFTステップによって処理されることを前提としています。 4 北 ログ 2 ⁡ 北 − 6 北 + 8 {\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)。
「https://en.wikipedia.org/w/index.php?title=Split-radix_FFT_algorithm&oldid=1320745110」から取得