고속 푸리에 변환: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 robot Adding: ar:تحويل فوريي السريع |
편집 요약 없음 |
||
9번째 줄:
이 식을 직접 구하면 O(''n''<sup>2</sup>) 의 연산이 필요하지만, FFT를 이용하면 O(''n'' log ''n'')의 연산만으로 가능하다. 일반적으로 ''n''을 어떻게 [[소인수분해]]하는냐에 따라 연산횟수를 줄일 수 있지만 , FFT를 이용하면 O(''n'' log ''n'')번의 연산으로 충분하다. 이것은 심지어 ''n''이 [[소수]]여도 가능하다.
==Cooley-Tukey FFT 알고리즘==
가장 일반적인 고속 푸리에 변환(FFT) (이)란, 이Cooley-Tukey 형태 알고리즘이다.
[[분할통치법]](divide and
conquer)을 사용한 알고리즘으로、재귀적으로 ''n''=''n''<sub>1</sub>''n''<sub>2</sub>의 사이즈 변환을 통해 고속화를 도모하고 있다. 스텝 마다 변환의 사이즈를 사이즈 ''n''/2 의 2개의 변환에 분할하는 수법이므로 2의 누승으로 한정된다. 그러나, 일반적으로는 수의 [[소인수분해]]하의 누승은 되지 않기 때문에、짝수때와 홀수때로 다른 알고리즘을 사용한다.
===원리에 관한 간단한 설명===
[[Image:FFT ButterFly.png|right|thumb|200px|FFT의 버터플라이 연산의 그림]]
이산 Fourier 계수는''W''<sub>''N''</sub>=''e''<sup>-2πi/N</sup>를 이용해 나타내면
:<math>f_j = \sum_{k=0}^{n-1} x_k W^{jk}
\qquad j = 0,\dots,n-1.</math>
예를 들면、''N''=4 일 때、이산 Fourier 계수는 행렬을 이용해 표현하면
:<math>
\begin{bmatrix}f_0\\f_1\\f_2\\f_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}.
</math>
입력열''x''<sub>''k''</sub>를 첨자의 우기로 나누고, 이하와 같이 변형한다.
:<math>
\begin{bmatrix}f_0\\f_1\\f_2\\f_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^0W^0&W^0W^0\\
W^0&W^2&W^1W^0&W^1W^2\\
W^0&W^0&W^2W^0&W^2W^0\\
W^0&W^2&W^3W^0&W^3W^2
\end{bmatrix}
\begin{bmatrix}x_0\\x_2\\x_1\\x_3\end{bmatrix}
</math>
그러면, 사이즈2 의FFT 의 연산 결과를 이용해 표현할 수 있어 사이즈의 분할을 할 수 있다.
:<math>=
\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{matrix}
\begin{bmatrix}W_2^0&W_2^0\\W_2^0&W_2^1\end{bmatrix}\!\!\!\!\begin{bmatrix}x_0\\x_2\end{bmatrix}\\
\begin{bmatrix}W_2^0&W_2^0\\W_2^0&W_2^1\end{bmatrix}\!\!\!\!\begin{bmatrix}x_1\\x_3\end{bmatrix}
\end{matrix}
</math>
또, 이 분할 순서를 그림으로 하면 나비와 같은 그림이 되는 것부터, 버터플라이 연산이라고도 불린다
==그 외의 알고리즘==
* Prime Factor Algorithm (PFA)
* Bruun's FFT algorithm
* Rader's FFT algorithm
* Bluestein's FFT algorithm
==응용==
*스펙트럼 분석기
*OFDM 변복조기
*CT 스캐너、MRI 등
==참고문헌==
* [1] J. W. Cooley and J. W. Tukey: Math. of Comput. <B>19</B> (1965) 297.
* [2] Carl Friedrich Gauss, "Nachlass: Theoria interpolationis methodo nova tractata," Werke band 3, 265–327 (Königliche Gesellschaft der Wissenschaften, Göttingen, 1866). See also M. T. Heideman, D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform," IEEE ASSP Magazine 1 (4), 14–21 (1984).
* [3] H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, "Real-valued fast Fourier transform algorithms," ''IEEE Trans. Acoust. Speech Sig. Processing'' '''ASSP-35''', 849–863 (1987).
{{comp-stub}}
| |||