녹음된 소리는 시간에 따라 흔들리는 파형으로 저장됩니다. 그런데 음높이, 잡음, 음색을 분석하려면 시간축의 숫자들을 ‘어떤 주파수가 얼마나 들어 있는가’라는 표현으로 바꾸는 편이 유용합니다. 이산 푸리에 변환(Discrete Fourier Transform, DFT)이 바로 그 변환을 맡습니다. 문제는 입력 표본이 N개일 때 정의식을 그대로 계산하면 대략 N²에 비례하는 곱셈과 덧셈이 필요하다는 점입니다. 고속 푸리에 변환(Fast Fourier Transform, FFT)은 같은 DFT 결과를 수학적 대칭과 분할 정복으로 계산해 연산량을 O(N log N)으로 줄이는 알고리즘 계열입니다.
FFT는 새로운 변환이 아니라 DFT를 빠르게 계산하는 방법입니다
FFT와 DFT는 서로 다른 결과를 내는 변환이 아닙니다. DFT는 무엇을 계산할지 정한 수학적 정의이고 FFT는 그 값을 효율적으로 구하는 계산 절차입니다. 길이 N인 복소수 입력 x₀,…,xₙ₋₁의 k번째 주파수 성분 Xₖ는 모든 입력을 복소 지수 함수와 곱해 더한 값입니다.
Xₖ = Σₙ₌₀ᴺ⁻¹ xₙ exp(-2πikn/N), k=0,1,…,N-1
exp(-2πi/N)을 Wₙ이라고 쓰면 Xₖ=ΣxₙWₙᵏⁿ으로 간단히 적을 수 있습니다. Wₙ은 복소평면의 단위원을 N등분한 점을 한 칸씩 회전시키는 N제곱근입니다. k 하나를 계산할 때 N개 항을 더하고 그런 k가 N개이므로 직접 DFT에는 N² 규모의 연산이 듭니다. 입력이 1,024개라면 정의식의 항은 약 104만 개지만, 밑이 2인 FFT의 핵심 단계 수는 1,024×log₂1,024=10,240 규모입니다. 실제 명령 수는 구현에 따라 달라도 증가율의 차이는 분명합니다.
짝수 번호와 홀수 번호를 나누면 같은 모양의 작은 DFT가 보입니다
가장 널리 설명되는 radix-2 Cooley–Tukey 알고리즘은 N이 2의 거듭제곱일 때 입력의 짝수 번째 표본과 홀수 번째 표본을 분리합니다. n=2m인 항과 n=2m+1인 항을 따로 모으면 길이 N의 합이 길이 N/2인 두 합으로 바뀝니다. 짝수 부분을 Eₖ, 홀수 부분을 Oₖ라고 하면 다음 관계를 얻습니다.
Xₖ = Eₖ + WₙᵏOₖ, Xₖ₊ₙ／₂ = Eₖ - WₙᵏOₖ
두 번째 식에서 부호가 바뀌는 까닭은 Wₙᴺ／₂=exp(-πi)=-1이기 때문입니다. 길이 N/2인 DFT 두 개를 한 번 계산하면 Xₖ와 Xₖ₊ₙ／₂를 함께 만들 수 있습니다. 각 작은 DFT도 다시 짝수와 홀수로 나누고, 길이가 1이 될 때까지 같은 일을 반복합니다. 입력을 절반으로 가르는 층은 log₂N개이고, 각 층에서 전체 N개 값을 한 번씩 결합하므로 연산량이 N log₂N에 비례합니다.
버터플라이 연산은 두 값을 네트워크처럼 결합합니다
Eₖ와 Oₖ로 두 출력 Eₖ+WₙᵏOₖ, Eₖ-WₙᵏOₖ를 만드는 작은 계산 단위를 버터플라이(butterfly)라고 부릅니다. 신호 흐름도를 그리면 두 입력에서 두 출력으로 교차하는 선이 나비 날개처럼 보이기 때문에 붙은 이름입니다. 버터플라이는 복소수 한쪽에 회전 인자 Wₙᵏ를 곱하고 그 결과를 다른 값에 더하거나 뺍니다.
| 입력 길이 N | 직접 DFT의 N² | N log₂N | 두 증가량의 비 |
|---|---|---|---|
| 8 | 64 | 24 | 약 2.7배 |
| 1,024 | 1,048,576 | 10,240 | 약 102배 |
| 1,048,576 | 약 1.10조 | 20,971,520 | 약 52,429배 |
표의 수치는 실제 실행 시간을 뜻하지 않고 증가율을 비교하기 위한 기본 연산 규모입니다. 캐시 사용, 메모리 이동, 실수·복소수 자료형, 벡터 명령, 병렬화와 라이브러리 최적화에 따라 시간은 달라집니다. 그럼에도 N이 커질수록 제곱 증가와 N log N 증가의 격차가 급격히 벌어진다는 사실은 변하지 않습니다.
8개 입력을 나누는 구조
- 길이 8 입력을 짝수 인덱스 0·2·4·6과 홀수 인덱스 1·3·5·7로 나눕니다.
- 두 길이 4 묶음을 다시 각각 짝수와 홀수 위치로 나눠 길이 2 묶음 네 개를 만듭니다.
- 길이 2 묶음을 길이 1까지 나눕니다. 길이 1의 DFT는 입력값 자체입니다.
- 아래 단계에서 얻은 두 결과를 회전 인자와 버터플라이로 결합해 길이 2, 길이 4, 길이 8 결과를 차례로 복원합니다.
- 각 단계의 회전 인자는 미리 계산하거나 점화적으로 갱신할 수 있습니다.
반복문 방식의 radix-2 구현에서는 입력이나 출력 인덱스를 비트 역순(bit reversal)으로 재배열하는 형태가 자주 등장합니다. 예를 들어 세 비트 인덱스 001₂은 뒤집으면 100₂가 됩니다. 재귀 호출이 짝수·홀수 순서로 자료를 나누는 과정을 반복문에서 미리 배치한 것입니다. 모든 FFT가 같은 재배열을 요구하는 것은 아니며 decimation-in-time, decimation-in-frequency, 제자리 계산 여부에 따라 위치가 달라집니다.
N이 2의 거듭제곱이 아니어도 FFT를 쓸 수 있습니다
FFT를 ‘입력 길이가 반드시 2의 거듭제곱이어야 하는 알고리즘’이라고 말하면 범위가 너무 좁습니다. radix-2는 설명과 구현이 간단한 한 종류입니다. Cooley–Tukey 방식은 N을 N₁N₂처럼 인수분해해 작은 변환으로 나눌 수 있고, 3이나 5 같은 다른 기수를 쓰는 mixed-radix 알고리즘도 있습니다. 소수 길이에는 Rader 알고리즘이나 Bluestein 알고리즘 같은 방법을 사용할 수 있습니다. 실무에서는 사용 중인 FFT 라이브러리가 어떤 길이를 효율적으로 처리하는지 확인합니다.
길이를 다음 2의 거듭제곱까지 0으로 채우는 제로 패딩도 흔합니다. 제로 패딩은 이산 주파수 격자를 더 촘촘하게 표시하지만 원래 신호에 없던 정보나 실제 주파수 분해능을 새로 만들지는 않습니다. 관측 시간이 같다면 가까운 두 주파수를 구별하는 근본적인 분해능은 기록 길이와 창 함수에 좌우됩니다.
실수 신호, 역변환과 정규화
음성처럼 입력이 실수이면 DFT 결과는 켤레대칭 Xₙ₋ₖ=Xₖ*을 가집니다. 음의 주파수 쪽이 양의 주파수 쪽의 복소켤레이므로 절반가량의 정보로 전체를 복원할 수 있고, 실수 전용 FFT는 이 대칭을 이용해 계산과 저장량을 줄입니다. X₀은 직류 성분이며 N이 짝수일 때 Xₙ／₂는 나이퀴스트 주파수 성분입니다.
역이산 푸리에 변환(IDFT)은 지수의 부호를 반대로 하고 보통 1/N을 곱합니다. 다만 라이브러리마다 정규화 규약이 다릅니다. 정방향에는 계수를 붙이지 않고 역방향에 1/N을 붙이기도 하고, 양쪽에 1/√N을 나누어 붙이기도 합니다. 변환 뒤 원래 크기가 N배가 되는 문제는 알고리즘 오류가 아니라 정규화 규약 차이일 수 있습니다.
FFT 결과를 읽을 때 빠뜨리기 쉬운 표본화 조건
FFT는 입력된 숫자의 DFT를 정확하고 빠르게 계산하지만, 잘못 표본화된 신호를 자동으로 고치지는 않습니다. 표본화 주파수가 fₛ이면 표현 가능한 고유 주파수 범위는 나이퀴스트 주파수 fₛ/2까지입니다. 그보다 높은 성분은 낮은 주파수로 접혀 보이는 에일리어싱을 일으킵니다. 아날로그 신호를 디지털로 바꿀 때는 적절한 표본화 속도와 안티에일리어싱 필터가 필요합니다.
유한 구간을 잘라 관측하면 구간 양끝이 주기적으로 이어진다고 보는 DFT의 가정과 실제 신호가 맞지 않을 수 있습니다. 그러면 한 주파수의 에너지가 주변 빈으로 번지는 스펙트럼 누설이 생깁니다. Hann, Hamming 같은 창 함수는 끝부분을 완화해 누설 형태를 바꾸지만 주엽 폭과 진폭 보정 사이에 절충이 있습니다. FFT 자체의 속도와 창 함수 선택은 별개의 문제입니다.
원형 합성곱과 빠른 선형 합성곱
시간 영역의 원형 합성곱은 주파수 영역에서 성분별 곱셈으로 바뀝니다. 따라서 두 길이 N 배열을 직접 합성곱해 O(N²) 작업을 하는 대신 각각 FFT하고 같은 위치끼리 곱한 뒤 역 FFT하면 O(N log N) 규모로 계산할 수 있습니다. 일반적인 선형 합성곱을 원하면 결과 길이 L₁+L₂-1 이상이 되도록 두 입력에 0을 채워야 원형으로 되감기는 항이 겹치지 않습니다.
이 성질은 긴 디지털 필터, 다항식 곱셈, 상관관계 계산과 큰 정수 곱셈에 활용됩니다. 다만 배열이 짧으면 FFT 준비와 복소 연산의 고정비용 때문에 직접 계산이 더 빠를 수 있습니다. O 표기법은 입력이 커질 때의 증가율을 말하며 모든 크기에서의 실제 속도를 보장하지 않습니다.
수치 오차와 구현에서 확인할 점
- 부동소수점 덧셈과 곱셈에는 반올림 오차가 있으므로 정방향과 역방향을 거쳐도 마지막 비트까지 완전히 같지 않을 수 있습니다.
- 주파수 빈 k가 나타내는 주파수는 kfₛ/N입니다. 배열 인덱스를 곧바로 헤르츠로 읽으면 안 됩니다.
- 실수 신호의 단측 진폭 스펙트럼을 만들 때는 직류와 나이퀴스트 항을 제외한 양의 주파수 성분을 보통 2배하지만, 창과 정규화 규약도 함께 반영해야 합니다.
- 제로 패딩은 그래프를 보간하듯 촘촘하게 만들지만 관측 시간을 늘린 것과 같지 않습니다.
- FFT라는 이름은 여러 알고리즘의 묶음입니다. 모든 구현이 radix-2 Cooley–Tukey나 같은 메모리 순서를 사용하는 것은 아닙니다.
FFT 계산 핵심 정리
DFT는 N개 표본을 N개 주파수 성분으로 바꾸며 직접 정의식을 계산하면 N² 규모의 작업이 필요합니다. Cooley–Tukey FFT는 단위원의 대칭을 이용해 길이 N 변환을 더 작은 변환으로 나눕니다. radix-2의 경우 짝수·홀수 항의 두 길이 N/2 DFT를 계산하고 버터플라이로 한꺼번에 결합합니다. 분할 단계가 log₂N개, 각 단계의 결합 작업이 N에 비례하므로 전체 복잡도는 O(N log N)이 됩니다.
속도 향상은 근삿값으로 바꾸어서 얻는 것이 아닙니다. 같은 DFT 식을 중복 계산하지 않도록 다시 배열한 결과입니다. 다만 컴퓨터에서는 부동소수점 반올림이 있고 신호 분석에는 표본화, 창 함수, 정규화 문제가 따릅니다. FFT의 수학과 입력 신호 처리 조건을 함께 확인해야 계산 결과를 올바르게 해석할 수 있습니다.