고속 푸리에 변환

위키백과 ― 우리 모두의 백과사전.

‘FFT’ 문서는 여기로 넘어옵니다. 다른 뜻에 대해서는 FFT (동음이의)를 참고하십시오.

고속 푸리에 변환(高速 푸리에 變換, Fast Fourier transform, FFT)은 이산 푸리에 변환(Discrete Fourier transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘이다. FFT는 디지털 신호 처리에서 편미분 방정식의 근을 구하는 알고리즘에 이르기까지 많은 분야에서 사용한다.

$x 0,..., x n - 1$ 이 복소수라고 가정할때, DFT는 다음과 같이 정의한다.

$f_j = \sum_{k=0}^{n-1} x_k e^{-{2\pi i \over n} jk } \qquad j = 0,\dots,n-1$

이 식을 정의에 따라 계산하면 O(n²) 의 연산이 필요하지만, FFT를 이용하면 O(n log n)의 연산만으로 가능하다. n이 합성수일 경우 그 소인수분해를 이용하여 연산 횟수를 줄일 수는 있지만, FFT를 사용하면 n이 소수일 경우에도 O(n log n)번의 연산 횟수를 보장한다.

[편집] 쿨리-튜키 알고리즘

가장 일반적으로 사용되는 FFT 알고리즘은 쿨리-튜키 알고리즘(Cooley-Tukey algorithm)이다. 이 알고리즘은 분할 정복 알고리즘을 사용하며, 재귀적으로 n 크기의 DFT를 n = n₁ n₂가 성립하는 n₁, n₂ 크기의 두 DFT로 나눈 뒤 그 결과를 O(n) 시간에 합치는 것이다. 이 방법은 1965년에 J. W. 쿨리와 J. W. 튜키가 발표하여 널리 알려졌지만, 나중에 카를 프리드리히 가우스가 1805년에 같은 방법을 이미 개발하였으며 그 뒤에도 제한된 형태의 FFT가 종종 발견되었다는 것이 밝혀졌다.

쿨리-튜키 알고리즘은 보통 크기 n을 재귀적으로 2등분하여 분할 정복을 적용하기 때문에 n = 2^k인 경우에 많이 적용된다. 하지만 일반적으로 n₁과 n₂는 같을 필요가 없으며, 따라서 n이 임의의 합성수일 때에도 적용 가능하다. 쿨리-튜키 알고리즘은 DFT를 더 작은 크기의 DFT들로 나누기 때문에, 뒤에 설명된 다른 FFT 알고리즘과 함께 사용될 수 있다.

[편집] 원리에 관한 간단한 설명

정의에서 $W = e - 2π / N$ 라고 하고 다시 정리하면,

$f_j = \sum_{k=0}^{n-1} x_k W^{jk} \qquad j = 0,\dots,n-1$

예를 들어 N = 4일 때, 이 식을 행렬을

$\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}.$

지수의 짝홀을 기준으로 위의 식을 다음과 같이 변형할 수 있다.

$\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}$

이는 다음과 같이 다시 쓸 수 있으므로, N = 4인 DFT는 N = 2인 DFT 두 개를 사용해서 계산할 수 있다.

$= \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} \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{bmatrix}$

이 과정을 재귀적으로 적용하면 N = 2^k인 DFT를 O(k N) 시간 안에 할 수 있다. 이런 분할 과정을 그림으로 그리면 나비 모양의 그림이 나오기 때문에 나비 연산(Butterfly operation)이라고도 불린다.

[편집] 그 외의 알고리즘

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. 19 (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).