스무디에서 재료를 다시 꺼낸다면
딸기·바나나·우유를 갈아 스무디를 만들었다고 하자. 다 섞인 스무디를 보고 “딸기가 몇 개, 바나나가 몇 개 들어갔지?”를 알아맞히는 건 어렵다. 그런데 신기하게도 소리·신호의 세계에는 이걸 정확히 해내는 도구가 있다. 그게 푸리에 변환이다.
푸리에 변환은 한 마디로 이렇다. 섞여 있는 것을 원래 재료(주파수)별로 다시 분해한다. 프리즘이 흰 빛을 무지개 색으로 펼치는 것과 똑같다. 흰 빛(섞인 신호)을 넣으면 빨주노초파남보(각 주파수 성분)가 나온다.
이 글은 수식을 최대한 걷어내고 그림과 비유 위주로 간다. 개념 → FFT가 왜 빠른지 → 분할 정복·DP와의 관계 → 실제 어디 쓰이는지(JPEG·5G·AI) → 마지막에 진짜 코드, 순서다.
푸리에 변환이 하는 일
음악 앱의 이퀄라이저(EQ) 막대를 떠올려 보자. 음악이 흐르면 저음·중음·고음 막대가 각각 위아래로 춤춘다. 그 막대 하나하나가 “지금 이 순간 이 주파수가 얼마나 세게 들어있나”를 보여준다. 그 막대 높이를 계산해 주는 게 바로 푸리에 변환이다.
조금 더 정리하면, 같은 소리를 보는 두 가지 방식이 있다.
- 시간으로 보기: “0.1초엔 이만큼, 0.2초엔 저만큼 출렁였다” — 우리가 녹음하는 원래 파형
- 주파수로 보기: “낮은음이 이만큼, 높은음이 저만큼 섞여 있다” — 푸리에 변환의 결과(EQ 막대)
푸리에 변환은 이 둘 사이를 오가게 해 준다. 왜 굳이 주파수로 바꿀까? 어떤 일은 시간으로 보면 어렵지만 주파수로 보면 쉽기 때문이다. 예를 들어 “이 녹음에서 60Hz 전기 잡음만 빼줘” 같은 건, 주파수로 펼쳐 놓으면 그 막대 하나만 깎아내면 끝이다.
컴퓨터가 쓰는 버전 = DFT
컴퓨터는 연속적인 소리를 통째로 못 다룬다. 마이크는 소리를 1초에 수만 번 찍어 숫자 배열로 저장한다. 이 숫자 배열에 쓰는 푸리에 변환을 DFT(이산 푸리에 변환) 라고 부른다. “이산(discrete)”은 그냥 “띄엄띄엄한 숫자들”이라는 뜻이다.
DFT가 하는 일을 말로 풀면 이렇다.
주파수마다 “이 신호가 그 주파수랑 얼마나 닮았어?”를 점수로 매긴다. 닮았으면 높은 점수, 안 닮았으면 0에 가깝게.
이 점수표가 바로 EQ 막대(스펙트럼)다. 닮은 정도를 재는 계산이 곱해서 더하기뿐이라 어렵지 않다.
🔍 딱 한 번만 보는 진짜 식 (건너뛰어도 됨) 입력
x₀…x_{n-1}에 대해X_k = Σ x_m · e^{-i·2πkm/n}. 겁날 것 없다.e^{-i…}부분이 “k번째 주파수의 파동”이고, 그걸 입력과 곱해 더한 게 “닮음 점수”다. 예로[1,2,3,4]를 넣으면 결과는[10, -2+2i, -2, -2-2i]이고, 첫 값10은 그냥1+2+3+4(전체 평균에 해당하는 성분)다.
문제는 속도다
DFT를 정의 그대로 계산하면 느리다. 점수표 칸이 n개고, 칸 하나를 채우려면 입력 n개를 전부 훑어야 한다. 그래서 n × n, 즉 n²번의 작업이 든다.
비유하자면 파티에서 모든 사람이 모든 사람과 일일이 악수하는 것과 같다. 사람이 10명이면 악수가 100번, 100명이면 1만 번, 1000명이면 100만 번 — 사람이 늘수록 폭발한다.
오디오에서 흔한 크기인 n = 4096이면 약 1,600만 번. 소리를 매 순간 이렇게 계산하면 금세 버겁다. 여기서 FFT가 등장한다.
FFT = 똑같은 답, 훨씬 빠른 길
먼저 가장 중요한 오해부터 짚자. FFT는 DFT의 “대충 빠른 근사”가 아니다. 답은 DFT와 완전히 똑같고, 단지 계산하는 길이 영리해서 빠를 뿐이다. (DFT가 “무엇을 구할까”라면, FFT는 “그걸 어떻게 빨리 구할까”다.)
FFT(가장 유명한 게 Cooley–Tukey 방식)의 핵심 아이디어는 “같은 계산을 두 번 하지 말자” 다. 입력을 짝수 번째와 홀수 번째로 반씩 쪼개면, 한 번 구한 절반의 결과를 위아래 두 칸을 채우는 데 재활용할 수 있다. 그리고 그 절반을 또 반으로, 또 반으로 쪼갠다 — 토너먼트 대진표처럼.
그 결과 작업량이 n²에서 n × log n 으로 줄어든다. 숫자로 보면 차이가 확 와닿는다.
| n | 순진한 DFT (n²) |
FFT (n·log₂n) |
|---|---|---|
| 1,024 | 약 100만 | 약 1만 |
| 4,096 | 약 1,600만 | 약 5만 |
n=4096에서 1,600만 번이 5만 번으로 — 300배 넘게 빨라진다. (덤으로 누적 오차도 오히려 더 작다. 빠른데 더 정확하다.)
길이가 2의 배수로 딱 떨어지지 않으면? 보통 뒤에 0을 채워(zero-pad) 크기를 맞춘다.
분할 정복이란? 그리고 DP랑 뭐가 다를까
방금 “반씩 쪼갠다”가 바로 분할 정복(divide and conquer) 이다. 큰 문제를 작은 문제로 나눠 풀고(분할·정복), 결과를 합친다(결합). 병합 정렬(merge sort) 과 완전히 같은 구조이고, 둘 다 같은 이유로 n log n이 된다.
여기서 많이 헷갈리는 게 동적 계획법(DP) 과의 차이다. “문제를 쪼개 푼다”는 점은 비슷한데, 둘을 가르는 기준은 딱 하나다.
쪼갠 작은 문제들이 서로 겹치는가?
- 안 겹치면 → 분할 정복 (FFT, 병합 정렬). 짝수 쪽 데이터와 홀수 쪽 데이터는 완전히 별개라, 한쪽 결과를 다른 쪽이 다시 쓸 일이 없다. 그래서 “답을 적어뒀다 재활용”할 이유가 없다.
- 겹치면 → DP. 예를 들어 피보나치
F(n)=F(n-1)+F(n-2)는F(3)같은 똑같은 작은 문제를 수십 번 다시 만난다. 그래서 한 번 푼 답을 메모해 두고 재활용하면 어마어마하게 빨라진다.
| 분할 정복 (FFT) | 동적 계획법 (DP) | |
|---|---|---|
| 쪼갠 문제들 | 서로 안 겹침 | 서로 겹침(똑같은 게 반복) |
| 핵심 기술 | 나눠서 합치기 | 한 번 푼 답 메모해 재활용 |
| 친구들 | 병합 정렬, 퀵 정렬 | 피보나치, 배낭 문제 |
한 줄로: 겹치면 메모(DP), 안 겹치면 그냥 쪼개기(분할 정복). FFT의 두 반쪽은 안 겹치니까 DP가 아니라 분할 정복, 즉 병합 정렬의 식구다.
어디에 진짜로 쓰일까
푸리에 변환·FFT는 “20세기 최고의 알고리즘” 후보로 꼽힐 만큼 우리 일상 도처에 박혀 있다.
- 음악 앱 튜너·음성 비서: 소리를 주파수로 펼쳐 “지금 음이 라(A)인지”, “무슨 말을 했는지” 알아낸다.
- 사진/영상 압축(JPEG·동영상): 이미지를 주파수로 바꾼 뒤, 눈에 잘 안 띄는 성분을 버려 용량을 줄인다.
- 휴대폰 통신(4G·5G): 무선 신호를 FFT로 주파수에 실어 보내고 받는다. 지금 이 글도 그 위를 지나왔다.
- 큰 수·다항식 곱셈 빠르게: 이게 알고리즘적으로 제일 우아한 활용이다 ↓
보너스: 곱셈이 빨라지는 마법
푸리에에는 합성곱 정리라는 보물이 있다 — 시간 영역에서 골치 아픈 “합성곱”이, 주파수 영역에선 그냥 하나씩 곱하기(쉬움)로 바뀐다. 그래서 아주 큰 두 수(또는 다항식)를 곱할 때, 주파수로 보냈다가 → 하나씩 곱하고 → 되돌리면 n²이 n log n으로 준다.
작은 주의: 이때 그냥 곱하면 끝과 처음이 겹치는 “순환” 효과가 생긴다. 그래서 미리 뒤에 0을 충분히 채워(보통 2배 길이) 겹침을 막는다. 그리고 입력이 작을 땐 오히려 평범한 곱셈이 더 빠르다 — 실무 라이브러리는 크기에 따라 알아서 갈아탄다.
AI에서는 어떻게 쓰일까
낡은 신호처리 얘기 같지만, 푸리에는 최신 AI에서 다시 인기다. 이유는 같다 — “전체를 한꺼번에 보는 계산”을 싸게 해 주기 때문이다.
- FNet — 비싼 부품을 싼 부품으로 교체. 요즘 AI(Transformer)의 핵심 부품인 “셀프 어텐션”은 성능은 좋지만 느리고 무겁다(
n²). 구글의 FNet은 그 자리에 학습할 것도 없는 푸리에 변환을 끼워 넣었다. 결과는? BERT 정확도의 92~97%를 유지하면서 학습이 GPU에서 80%, TPU에서 70% 빨라졌다. 무거운 부품을 가볍고 빠른 수학 트릭으로 바꿔치기한 셈이다. - FNO — 주파수 세계에서 학습하기. Fourier Neural Operator는 데이터를 주파수로 바꿔 거기서 학습한다. 큰 흐름(낮은 주파수)만 남기고 잔주름은 버리니, 날씨·유체 시뮬레이션처럼 넓은 그림이 중요한 문제에서 강하다(날씨 예측 모델 FourCastNet의 토대).
- 목소리를 알아듣는 AI의 입구: Whisper 같은 음성 AI는 소리를 모델에 넣기 직전, 거의 항상 FFT로 만든 스펙트로그램(주파수 그림)으로 바꾼다. 바로 다음 절의 내 프로젝트가 그 입구를 직접 만든 사례다.
진짜 코드로 보기
이론만 보면 멀게 느껴지니, 내가 만든 guitar-tab(기타 연주를 분석하는 프로젝트)의 실제 코드를 보자. 재밌는 건, 한 프로젝트 안에 직접 DFT와 FFT가 둘 다 들어 있다는 점이다. “작으면 단순하게, 크면 빠르게”라는 선택이 그대로 보인다.
작을 땐 그냥 직접 DFT (쉬운 쪽)
드럼 소리를 256개 샘플로만 보면 충분해서, 굳이 FFT 없이 정의 그대로 계산한다.
/** 256점 실수 DFT — 주파수별 세기(magnitude) 반환 */
function computeMags256(samples: Float32Array): Float32Array {
const N = 256;
const mags = new Float32Array(128);
for (let k = 0; k < 128; k++) { // 주파수 칸마다
let re = 0, im = 0;
for (let n = 0; n < N; n++) { // 입력을 전부 훑어 "닮음 점수" 누적 → n×n
const hann = 0.5 * (1 - Math.cos((2 * Math.PI * n) / (N - 1))); // 가장자리 잡음 줄이는 보정
const angle = (2 * Math.PI * k * n) / N;
const s = n < samples.length ? samples[n] * hann : 0;
re += s * Math.cos(angle);
im -= s * Math.sin(angle);
}
mags[k] = Math.sqrt(re * re + im * im); // 그 주파수의 세기
}
return mags;
}
이중 for 루프가 보이는가? 그게 바로 앞에서 말한 n²(악수 다 하기) 다. 그래도 N이 256으로 작으니 충분히 빠르다. (출처: guitar-tab/src/transcribe/drums.ts)
클 땐 FFT (빠른 쪽)
연주 톤을 분석할 땐 N=4096이라 직접 DFT는 무리다. 그래서 FFT를 쓴다. 코드가 길어 보여도 핵심은 딱 세 덩어리다.
export function fftComplex(re: Float32Array, im: Float32Array): void {
const n = re.length;
// ① 자리 재배치: 짝/홀로 끝까지 쪼개면 입력이 이 순서가 된다 (비트 반전)
for (let i = 1, j = 0; i < n; i++) {
let bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) { [re[i], re[j]] = [re[j], re[i]]; [im[i], im[j]] = [im[j], im[i]]; }
}
// ② 단계 키우기: 2 → 4 → 8 → … → n (총 log₂n 번만 돈다)
for (let len = 2; len <= n; len <<= 1) {
const ang = (-2 * Math.PI) / len;
const wRe = Math.cos(ang), wIm = Math.sin(ang);
for (let i = 0; i < n; i += len) {
let curRe = 1, curIm = 0;
for (let k = 0; k < len / 2; k++) {
// ③ 나비 연산: 절반 결과를 재활용해 위·아래 칸을 한 번에 채운다
const aRe = re[i + k], aIm = im[i + k];
const bRe = re[i + k + len / 2] * curRe - im[i + k + len / 2] * curIm;
const bIm = re[i + k + len / 2] * curIm + im[i + k + len / 2] * curRe;
re[i + k] = aRe + bRe; im[i + k] = aIm + bIm;
re[i + k + len / 2] = aRe - bRe; im[i + k + len / 2] = aIm - bIm;
const nextRe = curRe * wRe - curIm * wIm;
curIm = curRe * wIm + curIm * wRe; curRe = nextRe;
}
}
}
}
세 덩어리만 기억하면 된다.
- 자리 재배치(①): 반씩 쪼개는 분할 정복을 미리 한 번에 정리해 두는 단계.
- 단계 키우기(②): 작은 묶음부터 큰 묶음으로
log₂n번만 합친다 — 이 “log₂n번”이 빠름의 비결. - 나비 연산(③): 한 번 구한 절반 결과로 위·아래 두 칸을 동시에 채우는, “두 번 계산 안 하기”의 실체.
이 둘이 한 프로젝트에 공존한다는 게 핵심이다. 작으면 단순한 게 이기고, 커지면 FFT가 이긴다 — 이 글 전체의 결론이 코드에 그대로 박혀 있다. (출처: guitar-tab/src/tonelab/dsp.ts)
한 장 정리
- 푸리에 변환 = 섞인 신호를 주파수 재료로 분해하기(프리즘·EQ 막대). 컴퓨터용이 DFT.
- DFT는 느리다(
n², 다 같이 악수). FFT는 같은 답을 빠르게(n log n). 근사가 아니라 답은 똑같다. - FFT는 분할 정복(반씩 쪼개 합치기 = 병합 정렬 식구). DP와 다른 점은 “쪼갠 문제가 겹치느냐” 하나 — 안 겹쳐서 메모가 필요 없으니 DP가 아니다.
- 쓰이는 곳: 튜너·음성비서·JPEG·5G·큰 수 곱셈, 그리고 AI(FNet·FNO).
- 실제 코드: 작으면 직접 DFT, 크면 FFT — 내 guitar-tab에 둘 다 산다.
참고
- Fast Fourier transform — Wikipedia
- Understanding the Cooley-Tukey FFT — Van Hunter Adams (Cornell ECE)
- FNet: Mixing Tokens with Fourier Transforms (arXiv:2105.03824)
- Fourier Neural Operator for Parametric PDEs (Li et al., arXiv:2010.08895)
- 내 프로젝트 코드:
guitar-tab/src/tonelab/dsp.ts(FFT),guitar-tab/src/transcribe/drums.ts(직접 DFT)
푸리에 변환은 섞인 신호를 주파수로 펼치는 프리즘이고, FFT는 같은 답을 분할 정복으로 더 빠르게 구하는 방법이다.
댓글