고속 푸리에 변환(Fast Fourier Transform)이란?

고속 푸리에 변환(FFT, Fast Fourier Transform)이란, 푸리에 변환을 빠르게 수행할 수 있는 알고리즘이다. 일반적으로 이산 푸리에 변환(Discrete Fourier Transform)을 빠르게 수행하기 위해 사용하는데, DFT는 n개의 샘플에 대해 O(n^2)의 계산이 필요하지만 FFT는 O(nlogn)의 계산만 하면 된다. FFT의 핵심은 "쪼개어 생각하기"이다. 총 2N개의 샘플이 있을 때, 이를 짝수 인덱스와 홀수 인덱스로 분리하여 나타내는 것이다. 다니엘슨 - 란초스 보조정리 (D-L Lemma) 아래와 같은 DFT가 있다고 하자. 이때, x_n은 복소수열이며 이의 DFT인 f_k도 복소수열이다. 아래와 같이 Twiddle Factor W_n을 정의할 때, 복소평면에서 이는 ..

2024.03.12