FFT — 고속 푸리에 변환 쉽게 이해하기

FFT, 즉 고속 푸리에 변환은 이산 푸리에 변환(DFT)을 빠르게 계산하는 방법입니다. 일정한 간격의 샘플이 주어지면, DFT는 그 샘플 안에 각 이산 주파수 패턴이 얼마나 들어 있는지를 알려줍니다.

중요한 점은 FFT가 결과를 바꾸지 않는다는 것입니다. 직접 공식을 써서 구한 DFT와 같은 값을 내지만, 중복되는 계산을 훨씬 덜 하면서 그 결과에 도달합니다.

FFT를 한 문장으로

FFT는 DFT가 정의하는 동일한 주파수 영역의 값을 더 빠르게 계산하는 알고리즘입니다.

DFT가 측정하는 것

샘플 $x_0, x_1, \dots, x_{N-1}$가 있다고 합시다. DFT는 다음과 같이 정의되는 값 $X_0, X_1, \dots, X_{N-1}$를 만듭니다.

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

각 $X_k$는 데이터가 하나의 이산 주파수 패턴과 얼마나 강하게 일치하는지를 측정합니다.

샘플이 샘플링 주파수 $f_s$로 일정한 간격으로 주어졌다면, 인접한 주파수 bin 사이의 간격은 다음과 같습니다.

$$\frac{f_s}{N}$$

이 조건은 중요합니다. 샘플링 주파수를 모르면 DFT bin은 여전히 존재하지만, 그것들을 헤르츠 같은 물리적 주파수로 표시할 수는 없습니다.

FFT가 더 빠른 이유

FFT는 DFT를 효율적으로 계산하기 위한 알고리즘들의 한 계열입니다. 핵심 아이디어는 복소 지수 인자의 구조를 재사용해서 거의 같은 합을 처음부터 다시 계산하지 않는 것입니다.

가장 떠올리기 쉬운 버전은 radix-2 FFT입니다. 이것은 $N$이 $2$의 거듭제곱일 때 가장 자연스럽게 동작하며, 길이 $N$의 변환 하나를 길이 $N/2$의 변환 두 개로 나눈 뒤 결과를 합칩니다.

직접 DFT를 계산하면 연산량은 대략 $N^2$에 비례해 증가합니다. 흔히 쓰는 FFT 방법에서는 이것이 약 $N \log N$으로 줄어듭니다.

이 차이 때문에 FFT는 실제로 매우 중요합니다. 입력이 작으면 두 방법 모두 괜찮아 보일 수 있습니다. 하지만 입력이 커지면 FFT가 훨씬 더 빠릅니다.

FFT가 계산을 나누는 방법

FFT는 모든 샘플을 모든 주파수 패턴과 직접 비교하는 대신, 문제를 더 작은 변환들로 나눈 다음 위상 인자를 사용해 다시 결합합니다.

표준적인 분할 방법은 다음과 같습니다.

1. 짝수 인덱스 샘플을 한 목록에 넣습니다.
2. 홀수 인덱스 샘플을 다른 목록에 넣습니다.
3. 그 목록들에 대해 더 작은 변환을 계산합니다.
4. 두 절반의 결과를 합칩니다.

이것은 주파수 분석에 분할 정복을 적용한 것입니다.

4점 FFT 예제

다음과 같은 4점 신호를 보겠습니다.

$$x = [1, 0, 1, 0]$$

이 패턴은 $1$과 $0$이 번갈아 나타나므로, 완전히 평평한 결과가 아니라 어떤 주파수 구조가 있을 것이라고 예상할 수 있습니다.

이를 짝수 인덱스와 홀수 인덱스로 나누면 다음과 같습니다.

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

짝수 부분의 2점 DFT는

$$E = [2, 0]$$

이고, 홀수 부분의 2점 DFT는

$$O = [0, 0]$$

입니다.

4점 FFT에서 결합 단계는 다음과 같습니다.

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

여기서

$$W_4 = e^{-i 2 \pi / 4}$$

입니다.

$O_k = 0$이므로 결합은 특히 단순해집니다.

$$X = [2, 0, 2, 0]$$

이제 이 결과를 해석해 봅시다.

$X_0 = 2$는 0주파수 항이므로, 샘플의 평균값이 0이 아님을 반영합니다. 이 4점 경우에서 $X_2$의 0이 아닌 값은 패턴의 번갈아 나타나는 성분을 포착합니다. 먼저 평균을 빼면 $X_0$ 항은 사라지고, 번갈아 나타나는 성분이 더 뚜렷하게 보입니다.

이 예제는 작지만 아이디어는 그대로 확장됩니다. 더 작은 변환을 풀고, 매번 전체 합을 다시 만드는 대신 그것들을 결합하는 것입니다.

FFT에서 흔한 실수

FFT와 DFT를 서로 다른 결과로 생각하기

그렇지 않습니다. FFT는 DFT를 더 빠르게 계산하는 방법일 뿐입니다.

bin을 너무 일찍 물리적 주파수로 해석하기

bin의 위치는 샘플 간격을 알 때만 물리적 주파수가 됩니다. 샘플링 주파수가 $f_s$라면, 일정 간격 샘플에서 bin 간격은 $f_s/N$입니다.

제로 패딩이 새로운 정보를 더한다고 가정하기

제로 패딩은 기저 변환을 더 촘촘히 샘플링하게 만들어 스펙트럼이 더 매끄럽게 보이게 할 수는 있지만, 새로 측정된 데이터를 추가하지는 않습니다.

신호 전처리를 무시하기

평균 제거, 윈도잉, 신중한 샘플링 선택은 매우 중요할 수 있습니다. 이런 조건을 무시하면 FFT 출력은 주어진 샘플에 대해 수학적으로는 맞더라도 해석상 오해를 부를 수 있습니다.

FFT는 어디에 쓰일까

FFT는 샘플링된 데이터에서 주파수 영역 정보를 빠르게 얻어야 하는 곳이라면 어디에나 등장합니다. 대표적인 예로 스펙트럼 분석, 필터링, 영상 처리, 진동 분석, 미분방정식의 수치해법, 빠른 다항식 계산이나 컨볼루션 계산이 있습니다.

이유는 실용적입니다. 많은 연산이 샘플 영역에서 주파수 영역으로 옮긴 뒤 더 쉽거나 더 빨라지기 때문입니다.

비슷한 경우를 직접 해보기

사인파 한 주기를 일정한 간격의 샘플 8개로 잡고, 계산기나 스크립트로 DFT를 구해 보세요. 그런 다음 상수 오프셋을 더하고 새 출력을 비교해 보세요. $X_0$에서 값이 더 커지는 것은 FFT가 무엇을 분리해 내는지 보여 주는 간단한 방법입니다.