만약 여러분의 스마트폰이 음성 인식을 하는 데 30분이 걸리고, 5G 데이터 다운로드가 100배 느려진다면 어떨까요? 푸리에 변환을 ‘빠르게’ 만드는 고속 푸리에 변환(FFT)이 없었다면, 그것이 바로 우리의 현실이었을지도 모릅니다. 이 글은 푸리에 변환을 ‘실시간’으로 가능하게 만든 천재적인 알고리즘, 고속 푸리에 변환(FFT, Fast Fourier Transform)의 핵심 원리를 파헤쳐 봅니다.
왜 FFT가 디지털 혁명의 핵심이라 불리는지, 그 경이로운 ‘속도’의 비밀을 $O(N \log N)$이라는 키워드를 통해 명확하게 이해시켜 드리는 것이 이 글의 목표입니다.
⚡️ 모든 것의 시작: “느린” 푸리에 변환, DFT
컴퓨터는 ‘연속’이 아닌 ‘이산’ 신호를 다룬다
현실 세계의 신호, 예를 들어 우리의 목소리나 라디오 전파는 ‘아날로그(Analog)’, 즉 끊김 없는 연속적인 파동입니다. 하지만 컴퓨터는 이런 연속적인 신호를 그대로 처리할 수 없죠.
대신, ‘샘플링(Sampling)’이라는 과정을 통해 1초에 수천, 수만 번씩 신호의 값을 콕 집어 측정합니다. 그 결과 “3, 5, 1, -2, -4…”와 같은 숫자의 나열로 변환하는데, 이것이 바로 ‘이산(Discrete)’ 데이터입니다. 컴퓨터가 다루는 모든 디지털 신호(음악 파일, 통신 데이터)가 바로 이 이산 데이터죠.
이산 푸리에 변환(DFT, Discrete Fourier Transform)은 이렇게 샘플링된 $N$개의 시간 영역 데이터(숫자 나열)를 분석해서, 이 신호가 어떤 주파수 성분($N$개)들로 구성되어 있는지 그 ‘레시피’를 알려주는 핵심적인 수학적 도구입니다.
DFT는 왜 ‘느린가’? $O(N^2)$ 계산 복잡도의 의미
DFT의 원리 자체는 강력하지만, 여기엔 치명적인 단점이 있었습니다. 바로 ‘계산 속도’죠. DFT와 FFT의 근본적인 차이가 바로 이 계산 복잡도에서 드러납니다.
DFT 공식을 아주 단순하게 살펴보죠. $N$개의 데이터 샘플이 있을 때, 특정 주파수 성분 하나(예: ‘100Hz 성분이 얼마나 강한가?’)를 알아내기 위해서는 $N$개의 모든 시간 샘플 데이터 각각에 특정 계산(복소수 곱셈 및 덧셈)을 수행한 뒤, 그 결과를 모조리 더해야 합니다. 즉, 단 하나의 주파수 성분을 계산하는 데 $N$번의 연산이 필요합니다.
그런데 우리가 궁금한 건 100Hz 성분 하나가 아니죠. $N$개의 모든 주파수 성분(0Hz부터 최대 주파수까지)이 궁금합니다. 따라서 이 $N$번의 연산을 총 $N$개의 주파수 성분에 대해 전부 반복해야 하는 겁니다.
결과적으로 총 계산량은 $N \times N$, 즉 $N^2$에 비례하게 됩니다.
컴퓨터 공학에서는 이런 계산량의 증가 추세를 ‘Big-O 표기법(Big-O notation)’으로 나타내며, DFT의 계산 복잡도를 $O(N^2)$ (Order of N squared, N의 제곱에 비례)라고 부릅니다. 이 말은 $N$이 커질수록 계산량이 제곱으로, 말 그대로 ‘폭발적으로’ 증가한다는 뜻입니다.
| 데이터 개수 (N) | 계산량 ($N^2$) | 비고 |
|---|---|---|
| 64 | 4,096 | 간단한 연산 |
| 1,024 (약 1K) | 1,048,576 (약 100만) | CD 음질 오디오(44.1kHz) 기준 약 0.023초 분량 |
| 4,096 (약 4K) | 16,777,216 (약 1,600만) | 실시간 처리에 심각한 부담 시작 |
| 65,536 (64K) | 4,294,967,296 (약 43억) | 오디오 약 1.5초 분량. 실시간 처리 불가능. |
보시다시피, 데이터가 1,024개만 되어도 계산량이 100만 번을 훌쩍 넘어갑니다. 이런 속도로는 음성 인식이나 5G 통신처럼 1초에도 수십, 수백 번의 변환이 필요한 ‘실시간’ 시스템에는 도저히 적용할 수 없는 수준이었죠.
✨ 디지털 혁명: “빠른” 푸리에 변환, FFT
1965년, 벨 연구소의 제임스 쿨리(James Cooley)와 존 튜키(John Tukey)가 이 $O(N^2)$의 벽을 무너뜨리는 혁명적인 알고리즘을 발표합니다. 이것이 바로 고속 푸리에 변환(FFT)입니다.
FFT는 DFT와 수학적으로 100% 동일한 결과를 주지만, 계산 ‘과정’ 자체를 천재적인 방법으로 최적화한 알고리즘이죠.
핵심 아이디어: ‘분할 정복 (Divide and Conquer)’
FFT 원리의 핵심은 바로 ‘분할 정복 (Divide and Conquer)’입니다. $N$개의 거대하고 복잡한 문제를 한 번에 푸는 대신, 이 문제를 더 작은 문제로 ‘쪼개서’ 푼 다음, 그 결과들을 나중에 간단히 ‘합치는’ 방식이죠.
예를 들어, 1,024개 샘플에 대한 DFT 문제(1024×1024 $\approx$ 100만 번 계산)를 푸는 대신, FFT는 이 문제를 다음과 같이 바꿔버립니다.
- 데이터를 짝수 번째 샘플(512개)과 홀수 번째 샘플(512개)로 나눕니다.
- 512개짜리 짝수 샘플 그룹에 대해 DFT(FFT)를 수행합니다.
- 512개짜리 홀수 샘플 그룹에 대해 DFT(FFT)를 수행합니다.
- 이렇게 얻어진 2개의 작은 결과(512개짜리 스펙트럼 2개)를 간단한 계산(‘나비 연산’이라 불림)을 통해 ‘합쳐서’ 최종 1,024개짜리 스펙트럼을 만듭니다.
이 방식의 진짜 핵심은, 이 ‘쪼개기’ 과정을 재귀적으로(recursively) 끝까지 반복한다는 데 있습니다. 512개짜리 문제도 다시 256개짜리 문제 2개로, 256개는 128개로… 결국 1개짜리 DFT 문제(데이터가 1개일 때의 DFT는 그냥 그 자신)가 될 때까지 쪼개는 겁니다.
컴퓨터는 이 가장 작은 1개짜리 문제들을 풀고, 그 결과들을 다시 합치고(2개짜리), 또 합치고(4개짜리)… 최종 1,024개짜리 결과를 도출합니다. 이 영리한 과정 속에서, DFT의 $O(N^2)$에서 발생했던 그 엄청난 양의 ‘중복 계산’이 마법처럼 사라지게 됩니다.
$O(N^2)$를 $O(N \log N)$으로 바꾸는 마법
그렇다면 계산량은 대체 얼마나 줄어드는 걸까요?
- ‘분할’의 단계(Stages): $N$개의 데이터를 1개가 될 때까지 2로 나누는 횟수는 몇 번일까요? 이는 수학적으로 $\log_2 N$ 번입니다. (예: 1,024는 $2^{10}$이므로 $\log_2 1024 = 10$단계)
- ‘정복’의 계산량(Operations per Stage): 각 단계(예: 256개짜리 4개를 512개짜리 2개로 합치는 단계)에서는 $N$개의 모든 데이터에 대해 한 번씩의 간단한 ‘합치기'(나비 연산)만 수행합니다. 즉, 각 단계의 총 계산량은 $N$에 비례하죠.
결과적으로, FFT의 총 계산량은 (각 단계의 계산량) $\times$ (총 단계 수) = $N \times \log_2 N$에 비례하게 됩니다.
이것이 바로 FFT 계산 복잡도인 $O(N \log N)$의 진짜 의미입니다. $N^2$와 $N \log N$이 얼마나 큰 차이인지 숫자로 직접 비교해 보면 그 위력을 실감할 수 있습니다.
[표] “얼마나” 빨라지는가?: DFT vs FFT 계산 복잡도 비교
| 데이터 개수 (N) | “느린” DFT 계산량 ($N^2$) | “빠른” FFT 계산량 ($N \log_2 N$) | 속도 향상 (약) |
|---|---|---|---|
| 8 | 64 | $8 \times 3 = 24$ | 2.7 배 |
| 1,024 (1K) | 1,048,576 (약 100만) | $1024 \times 10 = 10,240$ (약 1만) | 102 배 |
| 4,096 (4K) | 16,777,216 (약 1,600만) | $4096 \times 12 = 49,152$ (약 5만) | 341 배 |
| 1,048,576 (1M) | $\approx 1.1 \times 10^{12}$ (1조 1천억) | $1048576 \times 20 \approx 2.1 \times 10^7$ (약 2천만) | 52,000 배 |
표를 보면 데이터 개수(N)가 커질수록 FFT의 효율은 그야말로 기하급수적으로 좋아지는 것을 볼 수 있습니다. 100만 개의 데이터(오디오 약 23초)를 DFT로 계산하면 ‘조’ 단위의 연산이 필요했지만, FFT로는 ‘천만’ 단위의 연산으로 충분합니다. 100배가 아닌, 무려 5만 배 이상 빨라지는 것입니다.
바로 이 어마어마한 차이가 ‘불가능’을 ‘실시간’으로 바꾼 핵심입니다.
FFT의 조건: 데이터 개수는 $2^n$ (2의 거듭제곱)
Cooley-Tukey 알고리즘과 같은 대부분의 고전적인 FFT 원리는 데이터를 정확히 ‘반’으로 쪼개는 ‘분할 정복’ 전략을 기반으로 합니다. 따라서 이 알고리즘은 데이터 샘플의 개수(N)가 $2^n$ (2의 거듭제곱, 예: 8, 64, 512, 1,024, 2,048, 4,096…)일 때 가장 효율적으로 작동합니다.
혹시 ‘그럼 데이터 개수가 1,000개처럼 $2^n$이 아니면 어떡하죠?’라는 궁금증이 생길 수 있습니다. 이럴 때 가장 일반적인 방법은 ‘제로 패딩(Zero-Padding)’입니다. 1,000개의 원본 데이터 뒤에 0의 값을 가진 24개의 가상 데이터를 덧붙여, 데이터의 총 길이를 $2^{10} = 1,024$개로 인위적으로 맞춘 뒤 FFT를 수행하는 것이죠.
🎧 FFT는 어디에 사용되는가? (실시간 처리가 핵심인 분야)
$O(N \log N)$이라는 경이적인 속도 향상 덕분에, FFT는 ‘실시간 신호 처리’가 필요한 거의 모든 현대 기술의 기반이 되었습니다.
1. 오디오/음성 처리 (노이즈 캔슬링, 음성 인식)
- 노이즈 캔슬링: 우리가 노이즈 캔슬링 이어폰을 끼는 순간, 이어폰은 외부 소음을 마이크로 받아들여 즉시(예: 1초에 48,000개 샘플) FFT를 수행합니다. 그리고 수 밀리초(ms) 이내에 그 소음을 상쇄하는 반대 위상의 파형을 만들어냅니다. 만약 $O(N^2)$의 DFT였다면, 소음이 이미 다 지나간 한참 뒤에야 계산이 끝났을 겁니다.
- 음성 인식: 스마트폰이나 AI 스피커가 “시리야”, “OK Google” 같은 명령어를 즉시 알아듣는 것도 FFT 덕분입니다. 마이크 입력을 20ms~40ms 정도의 짧은 구간으로 계속 잘라내고, 이 짧은 구간마다 FFT를 반복 수행(STFT, 단시간 푸리에 변환)하여 실시간으로 음성의 주파수 패턴 변화를 분석합니다.
2. 📡 통신 시스템 (5G, LTE, WiFi)
현대 무선 통신의 핵심 기술인 OFDM(직교 주파수 분할 다중)은 FFT가 없으면 구현 자체가 불가능했을 기술입니다.
- 송신 (데이터 보내기): 5G 기지국은 IFFT(역 고속 푸리에 변환)를 사용하여, 전송할 데이터를 수백, 수천 개의 서로 다른 주파수 채널(부반송파)에 데이터를 ‘동시에’ 실어 보냅니다.
- 수신 (데이터 받기): 우리의 스마트폰은 이렇게 뒤섞여 들어온 복잡한 신호를 받자마자 FFT를 수행해, 이 신호를 다시 수천 개의 개별 채널 데이터로 ‘즉시’ 분리해냅니다. 이 과정이 1초에도 수천 번씩 지연 없이 일어나야 지금의 고속 데이터 통신이 가능합니다.
3. 🧠 이미지 및 신호 분석 (MRI, 스펙트럼 분석기)
- 의료 영상 (MRI): MRI 장비가 인체로부터 수집하는 원본 신호 데이터(k-공간)는 이미지 형태가 아닙니다. 이 복잡한 신호 데이터에 2D FFT를 적용해야 비로소 우리가 보는 선명한 뇌나 무릎의 단층 이미지로 재구성됩니다.
- 컨볼루션(Convolution) 가속: 포토샵의 블러, 샤프닝 필터나 AI의 이미지 인식(CNN)에 사용되는 $O(N^2)$의 컨볼루션 연산은 계산량이 엄청납니다. 하지만 ‘컨볼루션 정리’에 따라, 두 신호를 각각 FFT하고(주파수 영역으로 변환), 단순히 곱한 뒤, 다시 IFFT하면($O(N \log N)$) 컨볼루션과 동일한 결과를 훨씬 빠르게 얻을 수 있습니다.
💡 $O(N \log N)$, 세상을 실시간으로 만든 위대한 도약
고속 푸리에 변환(FFT)은 단순히 푸리에 변환을 ‘개선’한 알고리즘이 아닙니다. $O(N^2)$라는 거대한 계산량의 벽을 $O(N \log N)$으로 무너뜨려, ‘이론상 가능’했던 신호 처리를 ‘실시간 현실’로 끌어내린, 디지털 시대의 가장 위대한 알고리즘 혁명 중 하나라고 할 수 있습니다.
오늘날 우리가 당연하게 누리는 거의 모든 실시간 디지털 기술, 즉 즉각적인 음성인식, 끊김 없는 5G 동영상 스트리밍, 주변 소음을 지워주는 노이즈 캔슬링의 바로 그 근간에는, 복잡한 문제를 ‘쪼개서 푼다’는 이 천재적인 ‘분할 정복’ 아이디어가 지금 이 순간에도 숨 쉬고 있습니다.