고속 푸리에 변환

편집 역사 토론
수치해석 계산물리 마지막 수정: 2026-07-12 04:03:11

1. 개요[편집]

고속 푸리에 변환
Fast Fourier Transform
약칭FFT
분야수치해석 × 신호처리 × 계산물리
계산 복잡도O(N log N)
대표 알고리즘쿨리-투키(Cooley–Tukey) 분할정복
주요 응용스펙트럴 방법, 에발트 합산, 신호처리

N²을 N log N으로 바꾸는 순간, 세상의 절반이 계산 가능해졌다.

고속 푸리에 변환(Fast Fourier Transform, FFT)은 이산 푸리에 변환(DFT)을 O(N2)O(N^2)이 아닌 O(Nlog⁡N)O(N \log N)에 계산하는 알고리즘의 총칭이다. 변환의 결과값 자체는 DFT와 완전히 동일하다 — FFT는 새로운 변환이 아니라, DFT를 빠르게 계산하는 방법일 뿐이다. 이름에 “고속”이 붙은 이유가 그것.

DFT는 시간(또는 공간) 영역의 신호를 주파수 영역으로 갈아 넣는 도구다. 그런데 정의대로 곧이곧대로 계산하면 데이터 하나마다 NN번의 곱셈이 필요해서 총 N2N^2번. 데이터가 백만 개면 101210^{12}번이라 슈퍼컴퓨터도 땀을 뻘뻘 흘린다. FFT는 이걸 약 2×1072 \times 10^7번으로 줄인다. 대략 5만 배 빨라지는 셈이니, “일단 FFT부터 돌려”가 국룰이 된 데는 이유가 있다.1

2. 이산 푸리에 변환의 정의[편집]

길이 NN의 복소수 수열 x0,x1,…,xN−1x_0, x_1, \dots, x_{N-1}에 대한 DFT는 다음과 같이 정의된다.

Xk=∑n=0N−1xn e−2πi kn/N,k=0,1,…,N−1X_k = \sum_{n=0}^{N-1} x_n \, e^{-2\pi i \, kn / N}, \qquad k = 0, 1, \dots, N-1

여기서 WN=e−2πi/NW_N = e^{-2\pi i / N}을 회전인자(twiddle factor)라 부른다. 이 식을 행렬-벡터 곱으로 보면 N×NN \times N 행렬을 벡터에 곱하는 꼴이라 곧이곧대로는 O(N2)O(N^2)이다. 역변환은 지수의 부호를 뒤집고 1/N1/N을 곱하면 된다.

xn=1N∑k=0N−1Xk e+2πi kn/Nx_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \, e^{+2\pi i \, kn / N}

3. 쿨리-투키 분할정복[편집]

FFT의 핵심 아이디어는 회전인자의 대칭성과 주기성을 이용한 분할정복이다. 가장 널리 쓰이는 기수-2(radix-2) 쿨리-투키 알고리즘은 NN이 2의 거듭제곱일 때, 수열을 짝수 인덱스와 홀수 인덱스로 반으로 쪼갠다.

Xk=∑m=0N/2−1x2mWN/2km⏟Ek+WNk∑m=0N/2−1x2m+1WN/2km⏟OkX_k = \underbrace{\sum_{m=0}^{N/2-1} x_{2m} W_{N/2}^{km}}_{E_k} + W_N^k \underbrace{\sum_{m=0}^{N/2-1} x_{2m+1} W_{N/2}^{km}}_{O_k}

즉 크기 NN짜리 DFT 하나가 크기 N/2N/2짜리 DFT 두 개(EkE_k, OkO_k)로 쪼개진다. 게다가 WNk+N/2=−WNkW_N^{k+N/2} = -W_N^k라는 대칭성 덕분에 XkX_k와 Xk+N/2X_{k+N/2}를 한 번에 얻는다.

Xk=Ek+WNkOk,Xk+N/2=Ek−WNkOkX_k = E_k + W_N^k O_k, \qquad X_{k+N/2} = E_k - W_N^k O_k

이 쪼개기를 재귀적으로 log⁡2N\log_2 N번 반복하면, 각 단계마다 O(N)O(N)의 연산이 들어 전체 O(Nlog⁡N)O(N \log N)이 된다. 분할정복의 교과서적 사례로, 컴퓨터과학 시간에도 단골로 등장한다.

4. 버터플라이 연산[편집]

위의 Xk=Ek+WNkOkX_k = E_k + W_N^k O_k, Xk+N/2=Ek−WNkOkX_{k+N/2} = E_k - W_N^k O_k 한 쌍을 데이터 흐름도로 그리면 나비 날개처럼 생겨서 버터플라이(butterfly)라 부른다. FFT의 실제 구현은 이 버터플라이를 격자처럼 층층이 쌓아 올린 것에 불과하다. 입력을 비트 반전(bit-reversal) 순서로 재배치하면 추가 메모리 없이 제자리(in-place)에서 계산할 수 있어, 하드웨어 구현에도 유리하다.2

버터플라이 하나는 복소수 곱셈 한 번과 덧셈·뺄셈 두 번으로 끝난다. 단계마다 N/2N/2개의 버터플라이가 있고 단계가 log⁡2N\log_2 N개이니, 곱셈 횟수는 대략 N2log⁡2N\frac{N}{2}\log_2 N. N2N^2과의 격차가 여기서 벌어진다.

5. 실수 신호와 변형들[편집]

현실의 신호는 대개 실수다. 실수 입력은 켤레 대칭성(XN−k=Xk‾X_{N-k} = \overline{X_k})을 가져 계산의 절반이 낭비되는데, 이를 활용한 실수 FFT(rFFT)는 복소 FFT보다 약 두 배 빠르다. NN이 2의 거듭제곱이 아니어도 겁먹을 필요는 없다 — 혼합 기수(mixed-radix)나 소인수 분해(prime-factor) 알고리즘, 그리고 임의의 NN을 처리하는 블루스타인(Bluestein) 알고리즘이 있어서, FFTW 같은 라이브러리는 아무 길이나 던져도 알아서 최적 경로를 잡아준다.3

관련 변환으로는 이산 코사인 변환(DCT, JPEG의 심장), 이산 사인 변환(DST) 등이 있으며, 모두 FFT로 빠르게 계산된다.

6. 응용[편집]

FFT가 없었다면 현대 계산과학의 상당 부분이 멈춘다.

  • 스펙트럴 방법 — 편미분방정식을 푸리에 기저로 전개해 미분을 곱셈으로 바꾼다. 직접수치모사의 주력 도구.
  • 푸아송 솔버 — 주기 경계의 포아송 방정식은 푸리에 공간에서 대각화되어, FFT 두 번이면 즉시 풀린다. 주기경계조건 아래 유동 해석의 단골.
  • 에발트 합산 — 분자동역학의 장거리 쿨롱 상호작용을 PME(Particle-Mesh Ewald)로 계산할 때 격자 위에서 FFT를 돌린다.
  • 신호처리 — 스펙트럼 분석, 필터링, 그리고 두 신호의 합성곱을 곱셈으로 바꾸는 합성곱 정리(convolution theorem)의 핵심.
  • 큰 수 곱셈 — 자릿수를 계수로 보면 곱셈이 합성곱이 되어, 초거대 정수 곱셈도 FFT로 처리한다.

푸리에 급수·테일러 급수처럼 함수를 기저로 전개하는 발상이지만, FFT는 그 전개를 실제로 계산 가능하게 만든 실용의 승리다.

7. 관련 문서[편집]

8. Footnotes[편집]

  1. 2000년 IEEE는 FFT를 “20세기의 가장 중요한 알고리즘 톱10”에 올렸다. 나머지 아홉 개를 다 합쳐도 인용 횟수로는 FFT를 못 이긴다는 우스갯소리가 있다. ↩

  2. 쿨리(James Cooley)와 투키(John Tukey)가 1965년 논문을 낸 게 공식적인 시작이지만, 사실 그 뿌리는 1805년 가우스까지 거슬러 올라간다. 가우스는 소행성 궤도 계산을 하다 이 알고리즘을 먼저 발견했는데, 라틴어로 노트에 적어두고 출판을 안 해서 150년간 묻혀 있었다. 논문을 안 내면 이렇게 된다. ↩

  3. FFTW의 이름은 “Fastest Fourier Transform in the West”의 약자다. 개발자들의 겸손함이 돋보인다. 참고로 정말 빠르긴 하다. ↩