FFT

푸리에 변환

푸리에 변환은 물리학과 수학에서 자주 등장하는데, 그만큼 일상에서도 쓰임새가 많아요.

간단히 말해, 푸리에 변환은 시간이나 공간 영역에 있는 입력 신호를 받아 주파수 영역으로 바꿔 줘요. 더 구체적으로, 서로 다른 주파수들이 뒤섞여(즉, 중첩되어) 이루어진 입력 신호가 있으면, 이 변환은 각 주파수를 분리해 내고 그 상대적인 세기를 보여줘요.

그래서 이 변환은 신호 처리(예: 필터링, 압축 등)와 여러 데이터 과학 응용 분야에서 핵심적인 도구예요. 따라서 처음 상상하는 것보다 훨씬 널리 쓰이고 있을 텐데, 푸리에 변환의 출력이 일반적으로 복소수라는 점을 떠올리면 허수가 없어서는 안 될 대표적인 사례이기도 해요.

푸리에 변환에는 적분 형태의 정의도 있지만, 다루는 대상이 디지털이다 보니 이산 버전에 관심이 있어요. 변환의 유도 과정은 이 연습 문제의 범위를 벗어나지만, 순방향 이산 변환(주파수 영역으로 가는)은 다음과 같은 형태예요: Xₖ = Σ xₙ * ℯ^(-2iπk * n/N) 여기서 합은 n에 대해 계산하고, N은 샘플의 개수, k는 주파수, i는 허수 단위, xₙ은 개별 샘플이에요.

고속 푸리에 변환

푸리에 변환은 굉장히 유용하지만, 순진하게 구현하면 조금 느려요(O(n²)). 고속 푸리에 변환(FFT)은 이를 획기적으로 빠르게 해 주는 알고리즘이에요. 보통은 정식화에 있는 몇 가지 대칭성을 이용하는 분할 정복 전략을 통해 이루어지며, 점근적으로 O(Nlog(N))의 복잡도를 가져요. 이런 속도 향상은 이 변환이 실용적으로 쓰일 수 있는 정도와 적용 범위를 크게 넓혀 줘요.