原理の簡単な説明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 05:20 UTC 版)
「高速フーリエ変換」の記事における「原理の簡単な説明」の解説
離散フーリエ係数は、1の原始 N 乗根の1つ WN = e−2πi/N を使うと、次のように表せる。 F ( t ) = ∑ x = 0 N − 1 f ( x ) W N t x . {\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)W_{N}^{tx}.} 例えば、N = 4 のとき、 F ( t ) = X t {\displaystyle F(t)=X_{t}} 、 f ( k ) = x k {\displaystyle f(k)=x_{k}} とすれば、離散フーリエ係数は行列を用いて表現すると（W = W4 と略記） [ X 0 X 1 X 2 X 3 ] = [ W 0 W 0 W 0 W 0 W 0 W 1 W 2 W 3 W 0 W 2 W 4 W 6 W 0 W 3 W 6 W 9 ] [ x 0 x 1 x 2 x 3 ] {\displaystyle {\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}={\begin{bmatrix}W^{0}&W^{0}&W^{0}&W^{0}\\W^{0}&W^{1}&W^{2}&W^{3}\\W^{0}&W^{2}&W^{4}&W^{6}\\W^{0}&W^{3}&W^{6}&W^{9}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{bmatrix}}} となる。入力列 xk を添字の偶奇で分けて、以下のように変形する。 [ X 0 X 1 X 2 X 3 ] = [ W 0 W 0 W 0 W 0 W 0 W 2 W 1 W 3 W 0 W 4 W 2 W 6 W 0 W 6 W 3 W 9 ] [ x 0 x 2 x 1 x 3 ] = [ W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 2 W 1 W 0 W 1 W 2 W 0 W 0 W 2 W 0 W 2 W 0 W 0 W 2 W 3 W 0 W 3 W 2 ] [ x 0 x 2 x 1 x 3 ] {\displaystyle {\begin{aligned}{\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}&={\begin{bmatrix}W^{0}&W^{0}&W^{0}&W^{0}\\W^{0}&W^{2}&W^{1}&W^{3}\\W^{0}&W^{4}&W^{2}&W^{6}\\W^{0}&W^{6}&W^{3}&W^{9}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\\&={\begin{bmatrix}W^{0}&W^{0}&W^{0}W^{0}&W^{0}W^{0}\\W^{0}&W^{2}&W^{1}W^{0}&W^{1}W^{2}\\W^{0}&W^{0}&W^{2}W^{0}&W^{2}W^{0}\\W^{0}&W^{2}&W^{3}W^{0}&W^{3}W^{2}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\end{aligned}}} ( ∵ W k + N = W k {\displaystyle \because W^{k+N}=W^{k}} ) すると、サイズ 2 のFFTの演算結果を用いて表現でき、サイズの分割ができる。 [ X 0 X 1 X 2 X 3 ] = [ 1 0 W 0 0 0 1 0 W 1 1 0 W 2 0 0 1 0 W 3 ] [ W 2 0 W 2 0 0 0 W 2 0 W 2 1 0 0 0 0 W 2 0 W 2 0 0 0 W 2 0 W 2 1 ] [ x 0 x 2 x 1 x 3 ] {\displaystyle {\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}={\begin{bmatrix}1&0&W^{0}&0\\0&1&0&W^{1}\\1&0&W^{2}&0\\0&1&0&W^{3}\end{bmatrix}}\,{\begin{bmatrix}W_{2}^{0}&W_{2}^{0}&0&0\\W_{2}^{0}&W_{2}^{1}&0&0\\0&0&W_{2}^{0}&W_{2}^{0}\\0&0&W_{2}^{0}&W_{2}^{1}\end{bmatrix}}\,{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}} また、この分割手順を図にすると蝶のような図になることから、バタフライ演算とも呼ばれる。 バタフライ演算は、計算機上ではビット反転で実現される。DSPの中には、このバタフライ演算のプログラムを容易にするため、ビット反転アドレッシングを備えているものがある。
※この「原理の簡単な説明」の解説は、「高速フーリエ変換」の解説の一部です。
「原理の簡単な説明」を含む「高速フーリエ変換」の記事については、「高速フーリエ変換」の概要を参照ください。
- 原理の簡単な説明のページへのリンク
