고속 푸리에 변환(Fast Fourier Transform, FFT)은 이산 푸리에 변환(Discrete Fourier Transform, DFT)을 계산하는 효율적인 알고리즘이다. DFT의 계산 복잡도를 $O(N^2)$에서 $O(N \log N)$로 획기적으로 감소시켜, 신호 처리, 영상 처리, 통신 시스템, 오디오 압축, 과학 계산 등 다양한 분야에서 실시간 처리를 가능하게 하는 핵심 기술로 사용된다.
기본 원리 FFT는 DFT의 대칭성과 주기성을 이용하는 분할 정복(Divide and Conquer) 방식을 기반으로 한다. 입력 데이터의 개수 $N$을 소인수분해하여 작은 크기의 DFT로 분해하고, 중간 계산 결과를 재사용함으로써 연산량을 줄인다. 가장 널리 쓰이는 형태는 $N$이 2의 거듭제곱($N=2^m$)인 경우에 적용되는 '기수 2(Radix-2) FFT' 알고리즘이다.
주요 알고리즘 분류
- 시간 영역에서의 디시메이션(Decimation-in-Time, DIT): 입력 신호를 짝수 번째와 홀수 번째로 나누어 재귀적으로 계산하는 방식(Cooley-Tukey 알고리즘의 대표적 형태).
- 주파수 영역에서의 디시메이션(Decimation-in-Frequency, DIF): 출력 스펙트럼을 짝수 번째와 홀수 번째로 나누어 계산하는 방식.
- 혼합 기수(Mixed-Radix) FFT: $N$이 2의 거듭제곱이 아닐 때 소인수를 조합하여 적용하는 방식.
- 소인수 FFT(Prime Factor Algorithm, PFA) / 윈오그래드 FFT(Winograd FFT): 특정 크기나 곱셈 연산 최소화에 특화된 변형 알고리즘.
역사 현대적인 FFT 알고리즘은 1965년 제임스 쿠oley(James Cooley)와 존 튜키(John Tukey)가 발표한 논문("An algorithm for the machine calculation of complex Fourier series")을 통해 널리 알려졌다. 다만, 유사한 아이디어는 1805년 카를 프리드리히 가우스(Carl Friedrich Gauss)가 소행성 궤도 계산을 위해 사용한 기록이 남아 있어, 역사적으로는 가우스가 최초 발견자로 평가받기도 한다.
활용 분야
- 디지털 신호 처리(DSP): 필터링, 스펙트럼 분석, 컨볼루션(Convolution) 고속 수행.
- 통신: OFDM(직교 주파수 분할 다중화) 변복조(LTE, Wi-Fi, 5G 등).
- 영상 처리: JPEG, MPEG 등 압축 표준에서의 이산 코사인 변환(DCT) 연산 가속.
- 오디오: MP3, AAC 등 손실 압축 코덱.
- 과학 공학: 편미분 방정식 수치 해법(스펙트럼 방법), 자기공명영상(MRI) 재구성, 대규모 정수 곱셈(NTT 등) 등.
구현 고려 사항
- 비트 역순(Bit-reversal): 기수 2 DIT FFT에서 입력 또는 출력의 순서를 재배열하는 과정.
- 트위들 팩터(Twiddle Factor): $W_N^k = e^{-j2\pi k/N}$로 표현되는 복소 지수 승수. 미리 계산하여 테이블로 저장하거나 재귀적으로 계산하여 곱셈 연산을 줄임.
- 수치 정밀도: 유한 정밀도 연산(부동소수점)에서 누적 오차 발생 가능. 고정소수점 연산 장치(DSP 칩 등)에서는 스케일링(Scaling) 기법 필요.
