고속 푸리에 변환 (Fast Fourier Transform, FFT)

1. 서론

장바티스트 조제프 푸리에(Jean-Baptiste Joseph Fourier)가 제시한 푸리에 해석은 임의의 연속 신호를 주기적인 정현파(sinusoid)의 합으로 분해할 수 있다는 혁신적인 아이디어를 통해 신호 해석의 새로운 지평을 열었다. 그러나 20세기에 들어 디지털 기술이 발전하면서, 세상은 연속적인 아날로그 신호가 아닌 일정한 간격으로 샘플링된 이산적인 데이터의 연속으로 표현되기 시작했다.2 이러한 디지털 데이터를 주파수 영역에서 분석하기 위한 수학적 도구로서 이산 푸리에 변환(Discrete Fourier Transform, DFT)이 고안되었다.4

DFT는 이산 신호를 구성하는 주파수 성분을 완벽하게 분석할 수 있는 강력한 이론적 기반을 제공했다. 하지만 그 실용성에는 치명적인 한계가 존재했다. DFT의 정의에 따른 직접적인 계산 방식은 데이터의 크기 N에 대해 O(N^2)의 계산 복잡도를 가졌다.2 이는 데이터의 수가 증가함에 따라 연산량이 기하급수적으로 폭증함을 의미하며, 수천 개의 데이터 포인트만으로도 실시간 처리가 거의 불가능해지는 계산상의 장벽을 만들었다.

이러한 상황에서 1965년 제임스 쿨리(James Cooley)와 존 튜키(John Tukey)에 의해 재발견된 고속 푸리에 변환(Fast Fourier Transform, FFT) 알고리즘은 가히 혁명적이었다. FFT는 DFT와 수학적으로 동일한 결과를 내면서도, 계산량을 O(N \log N)으로 획기적으로 단축시켰다.2 이 변화는 단순히 양적인 속도 개선을 넘어선 질적인 도약이었다.

O(N^2)의 장벽에 막혀 이론 속에 머물렀던 수많은 아이디어들이 FFT라는 알고리즘적 촉매제를 통해 현실 세계의 기술로 구현될 수 있었다. 이전에는 상상할 수 없었던 대규모 데이터의 실시간 주파수 분석이 가능해지면서, FFT는 디지털 신호 처리, 무선 통신, 멀티미디어 압축, 의료 영상 등 현대 기술의 거의 모든 분야에서 폭발적인 성장을 이끈 핵심 동력(enabling technology)으로 자리매김했다.1 따라서 FFT의 가장 큰 의의는 ‘속도’ 그 자체가 아니라, 그 속도로 인해 ’가능해진 것들’에 있다. 이는 알고리즘 효율성이 어떻게 공학적, 과학적 상상력의 한계를 확장하는지를 보여주는 대표적인 사례이다.

본 안내서는 고속 푸리에 변환의 수학적 원리부터 다양한 알고리즘의 구현 방식, 그리고 현대 기술에 미친 심대한 영향까지를 총망라하여 심층적으로 분석하고자 한다.

2. 이산 푸리에 변환(DFT)의 수학적 토대

2.1 이산 신호와 주파수 영역

컴퓨터와 같은 디지털 시스템이 처리하는 데이터는 자연계의 연속적인 아날로그 신호를 일정한 시간 간격으로 측정(샘플링)하여 얻은 이산 시간 신호(discrete-time signal)이다.4 이 신호는 시간의 흐름에 따른 값의 변화를 나타내며, 이를 시간 영역(time domain) 표현 x[n]이라 칭한다. 여기서 n은 이산적인 시간 인덱스를 의미한다.

DFT의 근본적인 목표는 이 시간 영역의 이산 신호 x[n]을 주파수 영역(frequency domain)으로 변환하는 것이다. 주파수 영역 표현 X[k]는 원본 신호 x[n]이 어떠한 주파수 성분들로 구성되어 있는지, 그리고 각 주파수 성분이 어느 정도의 크기(magnitude)와 위상(phase)을 갖는지를 명확하게 보여준다.1 이를 통해 복잡하게 뒤섞여 있는 시간 신호의 내재적 주기성과 패턴을 분석할 수 있게 된다.

2.2 DFT의 수학적 정의

길이가 N인 이산 신호 x[n] (단, n = 0, 1, \dots, N-1)에 대한 이산 푸리에 변환 X[k] (단, k = 0, 1, \dots, N-1)는 다음과 같이 공식적으로 정의된다.2
X[k] \triangleq \sum_{n=0}^{N-1} x[n] e^{-i \frac{2\pi}{N} nk}, \quad k = 0, 1, \dots, N-1
이 식에서 핵심적인 역할을 하는 복소 지수항 e^{-i \frac{2\pi}{N} nk}는 오일러 공식에 의해 $ \cos(\frac{2\pi}{N}nk) - i\sin(\frac{2\pi}{N}nk) $로 표현될 수 있다. 이는 복소 평면상의 단위원 위를 회전하는 페이저(phasor) 또는 벡터로 해석할 수 있다. 각 주파수 인덱스 k에 대해, DFT는 입력 신호 x[n]의 모든 샘플과 특정 주파수(k/N에 비례)를 갖는 복소 정현파와의 상관관계(correlation)를 계산하는 과정이다. 만약 신호 x[n]에 해당 주파수 성분이 강하게 포함되어 있다면, 합산 결과인 X[k]의 크기는 커지게 된다.

계산의 편의를 위해, 이 복소 지수항은 종종 ‘회전 인자(Twiddle Factor)’ 또는 ’단위근(Root of unity)’으로 불리는 W_N을 사용하여 다음과 같이 축약하여 표현한다.6
W_N \triangleq e^{-i \frac{2\pi}{N}}
이를 이용하면 DFT 정의식은 더욱 간결해진다.
X[k] = \sum_{n=0}^{N-1} x[n] W_N^{nk}
이 회전 인자 W_N이 가진 고유한 수학적 성질은 이후에 설명할 FFT 알고리즘 효율성의 근간을 이룬다.

2.3 역 이산 푸리에 변환(IDFT)

역 이산 푸리에 변환(Inverse Discrete Fourier Transform, IDFT)은 주파수 영역의 신호 X[k]로부터 원본 시간 영역 신호 x[n]을 손실 없이 완벽하게 복원하는 과정이다. IDFT의 공식은 다음과 같다.2
x[n] \triangleq \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i \frac{2\pi}{N} nk}, \quad n = 0, 1, \dots, N-1
이 식은 DFT 정의식과 매우 유사한 형태를 띤다. 주된 차이점은 복소 지수항의 부호가 양수(+i)로 바뀐 것과, 전체 합산 결과에 1/N이라는 스케일링 인자가 곱해진다는 점이다. 이러한 구조적 유사성 덕분에 DFT를 빠르게 계산하는 FFT 알고리즘은 약간의 수정만으로 IDFT 계산에도 거의 동일하게 적용될 수 있다.

2.4 O(N^2) 계산 복잡도와 그 한계

DFT 정의식을 기반으로 계산 과정을 분석해 보면 그 비효율성이 명확히 드러난다. 하나의 특정 주파수 성분 X[k]를 계산하기 위해서는 합산 기호(\sum) 내에서 N번의 복소수 곱셈(x[n] \cdot W_N^{nk})과 N-1번의 복소수 덧셈이 필요하다.7

그런데 우리가 구해야 할 주파수 성분은 X부터 X[N-1]까지 총 N개이다. 따라서 전체 DFT를 계산하기 위한 총 연산량은 다음과 같다.

• 총 복소 곱셈 횟수: N \times N = N^2
• 총 복소 덧셈 횟수: N \times (N-1) = N^2 - N

이로 인해 DFT의 시간 복잡도는 O(N^2)가 된다.2 데이터 크기

N이 작을 때는 문제가 되지 않지만, N이 커짐에 따라 계산량은 감당할 수 없는 수준으로 폭증한다. 예를 들어, 디지털 오디오 신호 처리에서 흔히 사용되는 N=1024의 경우, 약 1024^2 \approx 100만 번의 복소 곱셈이 필요하다. 이는 실시간 처리에 심각한 제약을 가하며, 더 큰 규모의 데이터 분석은 사실상 불가능하게 만드는 원인이었다.

아래 표는 N=1024를 기준으로 DFT와 FFT의 연산량을 정량적으로 비교하여 그 차이를 극명하게 보여준다.

이 표는 FFT가 왜 혁명적인지를 가장 직관적으로 보여주는 정량적 증거이다. N=1024일 때, FFT는 DFT에 비해 곱셈 연산을 200배 이상, 덧셈 연산을 100배 이상 줄여준다.12 이러한 압도적인 효율성 차이는 “어떻게 이런 엄청난 계산량 감소가 가능한가?“라는 질문으로 이어지며, 다음 장에서 다룰 FFT의 핵심 원리에 대한 강력한 동기를 부여한다.

3. 고속 푸리에 변환(FFT)의 핵심 원리: 분할 정복

FFT의 경이로운 효율성은 O(N^2) 계산 과정에 숨어있는 막대한 양의 중복 계산을 제거하는 것에서 비롯된다. 이를 가능하게 하는 핵심 전략이 바로 ’분할 정복(Divide and Conquer)’이며, 가장 널리 알려진 쿨리-튜키(Cooley-Tukey) 알고리즘이 이 전략을 기반으로 한다.14 분할 정복은 해결하기 어려운 큰 문제를 해결하기 쉬운 작은 문제들로 나눈 뒤, 그 작은 문제들의 해를 효율적으로 조합하여 원래 문제의 답을 구하는 알고리즘 설계 기법이다.

3.1 쿨리-튜키(Cooley-Tukey) 알고리즘

쿨리-튜키 알고리즘은 N-포인트 DFT 계산이라는 큰 문제를 더 작은 크기의 DFT 계산 문제들로 재귀적으로 분해한다. 이 과정은 N이 합성수일 때 적용 가능하며, 특히 N이 2의 거듭제곱(N=2^v)일 때 가장 효율적인 구조를 가진다.

3.2 DFT 수식의 재귀적 분해

분할 정복 전략을 적용하기 위해, 먼저 길이 N의 입력 신호 x[n]을 두 개의 부분 수열로 나눈다. 하나는 인덱스가 짝수인 샘플들로 구성된 수열이고, 다른 하나는 홀수인 샘플들로 구성된 수열이다.7

• 짝수 인덱스 수열: x_{even}[m] = x[2m], 여기서 m = 0, 1, \dots, N/2 - 1
• 홀수 인덱스 수열: x_{odd}[m] = x[2m+1], 여기서 m = 0, 1, \dots, N/2 - 1

이제 이 분할을 원래의 DFT 정의식에 대입하여 전개한다.
\begin{align} X[k] &= \sum_{n=0}^{N-1} x[n] W_N^{nk} \\ &= \sum_{m=0}^{N/2-1} x[2m] W_N^{2mk} + \sum_{m=0}^{N/2-1} x[2m+1] W_N^{(2m+1)k} \end{align}
여기서 회전 인자의 지수 부분을 정리하면 다음과 같은 관계를 얻을 수 있다.

• W_N^{2mk} = (e^{-i \frac{2\pi}{N}})^{2mk} = (e^{-i \frac{2\pi}{N/2}})^{mk} = W_{N/2}^{mk}
• W_N^{(2m+1)k} = W_N^{2mk} W_N^k = W_{N/2}^{mk} W_N^k

이 관계를 위 식에 대입하면, N-포인트 DFT가 두 개의 N/2-포인트 DFT의 조합으로 표현됨을 수학적으로 유도할 수 있다.7
\begin{align} X[k] &= \sum_{m=0}^{N/2-1} x[2m] W_{N/2}^{mk} + W_N^k \sum_{m=0}^{N/2-1} x[2m+1] W_{N/2}^{mk} \\ &= X_{even}[k] + W_N^k X_{odd}[k] \end{align}
여기서 X_{even}[k]는 짝수 인덱스 수열의 N/2-포인트 DFT이고, X_{odd}[k]는 홀수 인덱스 수열의 N/2-포인트 DFT이다. 이로써 하나의 큰 문제를 두 개의 작은 문제로 성공적으로 분할했다.

3.3 회전 인자(Twiddle Factor)의 역할과 성질

문제를 분할하는 것만으로는 충분하지 않다. 분할된 문제들의 해를 다시 합치는 ‘결합(combine)’ 과정이 효율적이어야만 전체 알고리즘의 효율성이 보장된다. 여기서 회전 인자 W_N^k가 가진 내재적 수학적 성질이 결정적인 역할을 한다. 회전 인자는 다음과 같은 주기성과 대칭성을 가진다.

• 주기성: X_{even}[k]와 X_{odd}[k]는 길이가 N/2인 DFT이므로, 주파수 인덱스 k에 대해 N/2의 주기를 가진다. 즉, X_{even}[k + N/2] = X_{even}[k]이다.
• 대칭성: 회전 인자 자체는 W_N^{k+N/2} = W_N^k W_N^{N/2} = W_N^k (e^{-i \frac{2\pi}{N} \frac{N}{2}}) = W_N^k e^{-i\pi} = -W_N^k 라는 대칭성을 가진다.

이 두 가지 성질을 이용하여 X[k]의 후반부(k \ge N/2) 값을 계산해 보자. k 대신 k+N/2를 대입하면,

코드 스니펫

\begin{align}
X[k + N/2] &= X_{even}[k + N/2] + W_N^{k+N/2} X_{odd}[k + N/2] \\
&= X_{even}[k] - W_N^k X_{odd}[k]
\end{align}

놀랍게도 X[k+N/2]는 X[k]를 계산할 때 사용했던 중간 결과(X_{even}[k]와 W_N^k X_{odd}[k])들을 그대로 재활용하여 뺄셈 연산 하나만으로 얻을 수 있다. 즉, k가 0부터 N/2 - 1까지 변할 때의 계산 결과만으로도 나머지 절반인 N/2부터 N-1까지의 결과를 추가적인 DFT 계산 없이 얻게 되는 것이다.

이 두 개의 핵심 공식은 다음과 같이 요약되며, FFT 효율성의 심장부이자 ’나비(butterfly) 연산’의 수학적 기반을 이룬다.
\begin{cases} X[k] = X_{even}[k] + W_N^k X_{odd}[k] \\ X[k + N/2] = X_{even}[k] - W_N^k X_{odd}[k] \end{cases} \quad \text{for } k = 0, 1, \dots, N/2 - 1
이처럼 ’분할 정복’이라는 알고리즘적 틀이 문제의 구조를 드러내고, ’회전 인자의 대칭성’이라는 수학적 성질이 그 틀 안에서 효율적인 계산을 가능하게 했다. 이 둘의 완벽한 공생 관계가 없었다면 FFT의 혁신은 불가능했을 것이다. 이는 잘 설계된 알고리즘이 수학적 구조의 아름다움을 어떻게 실용적 가치로 변환하는지를 보여주는 완벽한 예시이다.

3.4 O(N \log N) 복잡도의 달성

하나의 N-포인트 DFT를 두 개의 N/2-포인트 DFT 문제로 나누고, 그 결과를 합치는 데 필요한 연산은 N/2번의 복소 곱셈(W_N^k X_{odd}[k])과 N번의 복소 덧셈/뺄셈이다. 즉, 결합 과정의 복잡도는 O(N)이다.8

이 분할 과정은 재귀적으로 반복될 수 있다. N/2-포인트 DFT는 다시 두 개의 N/4-포인트 DFT로, 이는 또다시 두 개의 N/8-포인트 DFT로 나뉘며,最终적으로 1-포인트 DFT(입력값 자체)에 도달할 때까지 계속된다.

이러한 재귀적 관계를 시간 복잡도에 대한 점화식(recurrence relation)으로 표현하면 다음과 같다.8
T(N) = 2T(N/2) + O(N)
이 점화식의 해는 마스터 정리에 의해 T(N) = O(N \log N)으로 알려져 있다. 직관적으로 설명하면, N을 2로 계속 나누어 1이 될 때까지의 분할 단계의 수는 \log_2 N이다. 그리고 각 단계에서는 총 N개의 데이터를 처리하는 데 O(N)의 연산이 필요하다. 따라서 전체 시간 복잡도는 O(N \log_2 N)이 된다.8

4. FFT 알고리즘의 시각화와 구현: 나비 선도

FFT의 재귀적인 계산 흐름은 추상적으로 이해하기 어려울 수 있다. ’나비 선도(Butterfly Diagram)’는 이러한 복잡한 데이터 흐름과 연산 과정을 시각적으로 명료하게 표현하여 알고리즘의 구조를 직관적으로 파악할 수 있게 해주는 강력한 도구이다.6

4.1 나비 선도의 개념

나비 선도의 가장 기본적인 구성 단위는 2-포인트 DFT를 계산하는 연산이다. 두 개의 입력(x_0, x_1)이 들어와 두 개의 출력(X_0, X_1)을 내보내는 이 연산은 덧셈, 뺄셈, 그리고 회전 인자 곱셈으로 이루어진다. 이 데이터 흐름을 선으로 연결하면 마치 나비의 날개와 같은 모양이 되어 ’나비 연산’이라 불린다.16

2-포인트 DFT의 나비 연산은 다음과 같이 표현된다.

• X_0 = x_0 + W_2^0 x_1 = x_0 + x_1
• X_1 = x_0 + W_2^1 x_1 = x_0 - x_1

FFT 알고리즘 전체는 이러한 기본 나비 연산들이 여러 단계(stage)에 걸쳐 계층적으로 연결된 구조로 표현된다.

4.2 8-포인트 시간-추출(DIT) FFT 심층 분석

실제적인 예시로, 데이터 길이가 8인(N=8) 시간-추출(Decimation-In-Time, DIT) FFT의 전체 계산 과정을 나비 선도를 통해 단계별로 상세히 분석해 본다.17 DIT 방식은 시간 영역의 입력을 짝수와 홀수로 나누는 과정을 반복하는 알고리즘이다.

입력 재정렬 (Bit-Reversal Permutation)

DIT-FFT를 메모리 사용량을 최소화하는 인-플레이스(in-place) 방식으로 효율적으로 구현하기 위해서는, 계산 시작 전에 입력 데이터 x[n]의 순서를 ‘비트-반전(bit-reversal)’ 순서로 재배열해야 한다. 이는 인덱스를 이진수로 표현했을 때 그 순서를 뒤집는 것을 의미한다. 예를 들어, 8-포인트 FFT에서 인덱스 1은 이진수로 001이고, 이를 뒤집으면 100이 되어 인덱스 4가 된다. 따라서 원래의 x은 x의 위치로 이동하고, x는 x의 위치로 이동한다.

• x (000) -> x (000)
• x (001) -> x (100)
• x (010) -> x (010)
• x (011) -> x (110)

1단계 (Stage 1): 4개의 2-포인트 DFT

비트-반전 순서로 정렬된 입력을 가지고 첫 번째 계산 단계를 시작한다. 이 단계에서는 인접한 두 개의 데이터를 입력으로 하는 2-포인트 DFT, 즉 4개의 기본 나비 연산이 수행된다. 이 단계에서는 회전 인자가 모두 W_2^0=1이므로 단순 덧셈과 뺄셈만으로 계산이 완료된다.

2단계 (Stage 2): 2개의 4-포인트 DFT

1단계의 출력값이 2단계의 입력이 된다. 이 단계에서는 4개의 입력을 받아 4개의 출력을 내는 4-포인트 DFT 2개가 수행된다. 각 4-포인트 DFT는 두 개의 2-포인트 나비 연산과 회전 인자 곱셈으로 구성된다. 이때부터 자명하지 않은 회전 인자(W_4^1 = W_8^2 = -j)가 곱해지기 시작한다.

3단계 (Stage 3): 1개의 8-포인트 DFT

마지막 3단계에서는 2단계의 출력을 입력으로 받아 최종 8-포인트 DFT를 완성한다. 이 단계에서는 8개의 모든 데이터가 관여하는 가장 큰 나비 구조가 형성되며, W_8^0, W_8^1, W_8^2, W_8^3 네 종류의 회전 인자가 적용된다.

이 3단계의 계산이 모두 끝나면, 출력단에는 최종 주파수 영역 신호 X[k]가 자연스러운 순서(natural order), 즉 X, X, \dots, X의 순서대로 나타나게 된다.19

나비 선도는 단순한 시각화 도구를 넘어, FFT 알고리즘의 계산 구조를 담고 있는 ’계산 청사진’이다. 선도의 각 단계를 살펴보면, 한 단계 내에 있는 모든 나비 연산들은 서로 독립적임을 알 수 있다. 예를 들어, 8-포인트 FFT의 1단계에서 4개의 2-포인트 DFT는 서로의 결과에 영향을 주지 않으므로 동시에 계산될 수 있다. 이는 알고리즘이 본질적으로 높은 수준의 병렬성(parallelism)을 내포하고 있음을 의미한다. 또한, 각 나비 연산은 메모리상에서 매우 가까운 위치에 있는 데이터만을 필요로 한다. 이는 ’데이터 지역성(data locality)’이 높다는 것을 의미하며, 메모리 접근 시간을 최소화하고 캐시 효율성을 극대화하는 데 매우 유리하다. 따라서 FPGA나 ASIC 같은 고성능 하드웨어 설계자들은 나비 선도를 보고 파이프라인 구조, 병렬 연산 유닛, 메모리 뱅크 구성 등을 직접적으로 설계할 수 있다. 즉, 나비 선도는 알고리즘의 추상적 개념을 물리적 회로 구조로 변환하는 핵심적인 다리 역할을 한다.

4.3 시간-추출(DIT) vs. 주파수-추출(DIF)

FFT 알고리즘에는 DIT와 쌍을 이루는 주파수-추출(Decimation-In-Frequency, DIF) 방식도 존재한다. DIF-FFT는 DIT-FFT와 정반대의 데이터 흐름을 가진다.

• 입력/출력 순서: DIF는 입력을 자연 순서로 받고, 모든 계산이 끝난 후 출력이 비트-반전 순서로 나타난다.
• 연산 구조: DIT는 나비 연산을 수행하기 전에 회전 인자를 곱하는 반면, DIF는 나비 연산을 수행한 후에 회전 인자를 곱하는 구조적 차이가 있다.20

DIT와 DIF는 총 계산량과 최종 결과는 수학적으로 동일하지만, 데이터 흐름과 구현상의 세부 사항에서 차이가 있다. 이러한 차이로 인해 특정 하드웨어 아키텍처나 메모리 구조에 따라 어느 한 방식이 다른 방식보다 약간 더 효율적일 수 있다.

5. FFT 알고리즘의 확장: 기수(Radix) 변형과 성능 최적화

쿨리-튜키 알고리즘의 기본 형태인 기수-2(Radix-2) FFT는 가장 널리 알려져 있지만, 연산 효율을 더욱 높이기 위해 다양한 기수(radix)를 사용하는 변형 알고리즘들이 개발되었다. ’기수’는 각 분할 단계에서 문제를 몇 개의 부분 문제로 나누는지를 의미한다.

5.1 기수-2 (Radix-2) 알고리즘

지금까지 설명한, 매 단계에서 문제를 2개의 부분 문제로 나누는 방식이 바로 기수-2 알고리즘이다.21 이 알고리즘은 구조가 가장 단순하여 개념적으로 이해하고 소프트웨어로 구현하기가 비교적 쉽다는 장점을 가진다.

N이 2의 거듭제곱일 때 적용할 수 있다.

5.2 기수-4 (Radix-4) 알고리즘

기수-4 알고리즘은 한 단계에서 문제를 4개의 N/4-포인트 DFT 부분 문제로 분할한다.22 이 방식은

N이 4의 거듭제곱일 때 적용할 수 있다. 기수-4의 나비 연산은 4개의 입력을 받아 4개의 출력을 내므로 기수-2보다 구조적으로 더 복잡하다. 하지만 이러한 복잡성을 감수하는 이유는 연산량, 특히 곱셈 연산 횟수를 줄일 수 있기 때문이다.23

기수-4 나비 연산에 사용되는 회전 인자 중에는 W_N^0=1이나 W_N^{N/4}=-j와 같이 실제 곱셈 없이 덧셈/뺄셈이나 실수부/허수부 교환만으로 처리할 수 있는 ’자명한 곱셈(trivial multiplication)’이 포함된다. 이 덕분에 전체 복소 곱셈 횟수를 기수-2에 비해 약 25%가량 줄일 수 있다.24 과거에는 프로세서에서 곱셈 연산이 덧셈보다 훨씬 많은 사이클을 소모하는 비싼 연산이었기 때문에, 이러한 곱셈 횟수 감소는 상당한 성능 향상을 가져왔다.

5.3 분할-기수 (Split-Radix) FFT

분할-기수(Split-Radix) FFT는 기수-2와 기수-4의 장점을 결합한 하이브리드 알고리즘이다.25 이 알고리즘은 DFT를 분해할 때, 짝수 인덱스 항에 대해서는 기수-2 분해를 적용하고 홀수 인덱스 항에 대해서는 기수-4 분해의 변형을 적용하는 비대칭적인 분해 방식을 사용한다.21

이러한 독특한 접근 방식을 통해, 분할-기수 FFT는 2의 거듭제곱 길이를 갖는 DFT를 계산하는 알려진 알고리즘 중에서 이론적으로 총 실수 연산(덧셈과 곱셈의 합) 횟수가 가장 적다.21 이 때문에 연산 횟수 최소화가 가장 중요한 목표일 때 가장 효율적인 알고리즘으로 간주된다.

5.4 주요 FFT 알고리즘 성능 비교

아래 표는 기수-2, 기수-4, 분할-기수 알고리즘의 이론적인 실수 연산량을 정량적으로 비교한다. 이 표는 “어떤 FFT 알고리즘이 가장 좋은가?“라는 실용적인 질문에 대한 이론적인 답을 제공하며, 각 알고리즘의 상수 인자 차이를 명확히 보여준다.

이론적 연산량만 보면 분할-기수 알고리즘이 가장 우수하며, 기수-4, 기수-2 순으로 효율성이 높다.22

5.5 현대 프로세서 아키텍처와 실제 성능

그러나 이론적인 연산 횟수 최소화가 현대 컴퓨터 프로세서에서 반드시 최고의 실제 성능으로 이어지는 것은 아니다. 과거에는 곱셈 연산의 비용이 매우 높아 곱셈 횟수를 줄이는 것이 알고리즘 성능의 절대적인 척도였지만, 현대 프로세서 아키텍처는 상황을 복잡하게 만들었다.

실제 성능은 알고리즘의 구조가 현대 프로세서의 특징들과 얼마나 잘 부합하는지에 더 크게 좌우된다. 주요 고려 사항은 다음과 같다.25

• FMA (Fused Multiply-Add) 명령어: 현대 CPU는 a \times b + c 형태의 연산을 단일 명령어로 처리하는 FMA 유닛을 탑재하고 있다. 이 경우, 곱셈과 덧셈을 별개의 연산으로 취급하여 횟수를 세는 것은 무의미하며, 오히려 FMA 명령어를 효율적으로 활용할 수 있는 데이터 흐름을 가진 알고리즘이 더 빠를 수 있다.
• SIMD (Single Instruction, Multiple Data) 벡터 처리: 최신 프로세서는 하나의 명령어로 여러 개의 데이터(예: 4개 또는 8개의 부동소수점 수)를 동시에 처리하는 SIMD(또는 벡터) 연산을 지원한다. 알고리즘의 구조가 단순하고 규칙적이어서 컴파일러가 쉽게 벡터화할 수 있을 때 SIMD의 성능 향상 효과를 극대화할 수 있다. 분할-기수와 같이 복잡하고 비대칭적인 구조는 벡터화에 불리할 수 있다.
• 캐시 계층 구조: 알고리즘이 데이터를 접근하는 패턴 또한 성능에 지대한 영향을 미친다. 데이터 지역성(locality)이 높아 캐시 메모리에 데이터가 적중(cache hit)하는 비율이 높으면 빠르지만, 메모리 접근 패턴이 불규칙하여 캐시 미스(cache miss)가 빈번하게 발생하면 연산 유닛이 아무리 빨라도 메모리로부터 데이터를 기다리는 데 시간을 허비하게 된다.

결론적으로, 이론적으로 가장 효율적인 분할-기수 알고리즘이 복잡한 제어 흐름과 불규칙한 메모리 접근으로 인해 실제로는 단순한 구조의 기수-2 또는 기수-4 알고리즘보다 느리게 동작하는 경우가 발생할 수 있다. 이 때문에 FFTW(Fastest Fourier Transform in the West)와 같은 최첨단 FFT 라이브러리는 단 하나의 ‘최고’ 알고리즘을 고집하지 않는다. 대신, 실행 시점에 시스템의 하드웨어 특성(CPU 종류, 캐시 크기 등)을 동적으로 측정하여, 해당 시스템에서 최상의 성능을 내는 기수-2, 기수-4, 분할-기수 등 다양한 알고리즘 조각(codelets)들을 최적으로 조합하는 ‘적응형(adaptive)’ 전략을 사용한다. 이것이 이론적 연산량과 실제 성능 사이의 간극을 메우는 현대적 접근법이다.

6. 현대 기술을 구현하는 FFT의 응용

FFT는 그 계산 효율성 덕분에 이론의 영역을 넘어 우리 주변의 거의 모든 디지털 기술에 깊숙이 스며들어 있다. FFT가 없었다면 현대의 디지털 문명은 현재와 같은 모습으로 존재하기 어려웠을 것이다.

6.1 디지털 신호 처리 (DSP)

• 스펙트럼 분석: 시간 영역 신호를 FFT를 통해 주파수 영역으로 변환하여 신호에 포함된 주파수 성분을 분석하는 것은 가장 기본적이면서도 강력한 응용이다. 오디오 이퀄라이저는 FFT를 사용해 음악 신호의 주파수 대역별 에너지를 조절하며, 산업 현장에서는 모터나 터빈의 진동 신호를 FFT로 분석하여 특정 주파수에서의 이상 신호를 감지함으로써 고장을 사전에 진단한다.10
• 고속 컨볼루션: 신호 처리에서 필터링과 같은 연산은 컨볼루션(convolution)을 통해 수행된다. 시간 영역에서의 컨볼루션은 O(N^2)의 복잡도를 갖는 매우 계산량이 많은 연산이다. 그러나 컨볼루션 정리(Convolution Theorem)에 따르면, 시간 영역에서의 컨볼루션은 주파수 영역에서의 곱셈과 동일하다. 따라서 두 신호를 각각 FFT하고, 주파수 영역에서 곱한 뒤, 그 결과를 IFFT(역 FFT)하면 훨씬 빠른 O(N \log N)의 복잡도로 컨볼루션 결과를 얻을 수 있다. 이 ‘고속 컨볼루션’ 기법은 디지털 필터링, 이미지의 블러(blur) 효과 처리 등에서 광범위하게 사용된다.

6.2 통신 시스템: OFDM

Wi-Fi, LTE, 5G, 디지털 방송 등 현대의 거의 모든 고속 무선 통신 시스템은 직교 주파수 분할 다중(Orthogonal Frequency Division Multiplexing, OFDM)이라는 기술을 기반으로 한다.27 OFDM은 고속의 데이터 스트림을 수백에서 수천 개의 저속 병렬 데이터 스트림으로 나눈 뒤, 각각을 서로 다른 주파수를 가진 부반송파(subcarrier)에 실어 동시에 전송하는 방식이다.

OFDM 기술의 구현에서 FFT와 IFFT는 핵심적인 변복조기(modulator/demodulator) 역할을 수행한다.

• 송신단 (IFFT): 전송할 데이터 심볼들을 주파수 영역의 입력으로 간주하고, 이를 IFFT를 통해 시간 영역의 OFDM 신호로 변환한다. IFFT는 수많은 정현파(부반송파)를 합성하여 하나의 복합적인 시간 신호를 생성하는 역할을 매우 효율적으로 수행한다.28
• 수신단 (FFT): 수신된 시간 영역의 OFDM 신호를 FFT를 통해 다시 주파수 영역으로 변환한다. FFT의 출력값은 각 부반송파에 실려 있던 원래의 데이터 심볼에 해당한다.27

FFT의 O(N \log N)이라는 고속 연산 능력이 없었다면, 수천 개의 부반송파를 실시간으로 처리해야 하는 OFDM 기반의 광대역 통신은 현실적으로 불가능했을 것이다.30

6.3 이미지 처리 및 압축: JPEG와 DCT

우리가 일상적으로 사용하는 JPEG 이미지 압축의 핵심에는 이산 코사인 변환(Discrete Cosine Transform, DCT)이라는 기술이 있다.32 DCT는 신호를 주파수와 유사한 성분으로 분해하는 변환으로, 특히 이미지와 같이 인접 픽셀 간의 상관관계가 높은 데이터의 에너지를 소수의 저주파수 계수에 집중시키는 특성이 매우 뛰어나다.34

JPEG 압축 과정은 다음과 같다. 이미지를 8x8 픽셀 블록으로 나눈 뒤, 각 블록에 2차원 DCT를 적용한다. 그러면 64개의 픽셀 값은 64개의 DCT 계수로 변환되는데, 이미지 에너지의 대부분이 좌측 상단의 저주파수 계수 몇 개에 집중된다.35 인간의 시각은 미세한 고주파수 변화보다 전체적인 밝기 변화 같은 저주파수 변화에 더 민감하다는 심리시각적 특성을 이용하여, 에너지가 거의 없는 고주파수 계수들을 양자화(quantization) 과정을 통해 과감하게 0으로 만들거나 정밀도를 낮춘다. 이 과정을 통해 데이터의 양을 획기적으로 줄여 높은 압축률을 달성한다.32

여기서 중요한 점은 DCT가 수학적으로 실수 값을 갖는 짝대칭(even-symmetric) 함수에 대한 DFT와 밀접한 관련이 있다는 것이다.36 실제로 효율적인 DCT 알고리즘은 FFT를 기반으로 구현될 수 있다. 즉, FFT 알고리즘의 발전이 JPEG과 같은 효율적인 이미지 및 비디오(MPEG) 압축 기술의 등장을 간접적으로 뒷받침한 셈이다.

6.4 음성 및 오디오 처리

• 음성 인식: 구글 어시스턴트나 애플 시리와 같은 음성 인식 시스템은 사용자의 음성 신호를 FFT를 통해 스펙트로그램(spectrogram)으로 변환한다. 스펙트로그램은 시간에 따른 주파수 성분의 변화를 보여주며, 시스템은 이로부터 모음의 특징 주파수인 포먼트(formant)와 같은 음성학적 특징을 추출하여 어떤 단어가 발음되었는지를 인식한다.37
• 오디오 압축: MP3, AAC와 같은 손실 오디오 압축 형식은 변형 이산 코사인 변환(Modified Discrete Cosine Transform, MDCT)을 사용한다. MDCT는 DCT의 변형으로, 오디오 신호를 주파수 영역으로 변환한 뒤, 인간의 청각이 둔감한 주파수 대역의 정보를 제거(심리음향 모델 적용)하여 데이터를 압축한다.11

6.5 의료 영상 및 과학 연구

• 자기공명영상(MRI): MRI는 인체에 자기장을 가한 후 RF 펄스를 보내 수소 원자핵의 반응 신호를 측정하여 영상을 얻는다. 이때 측정되는 데이터는 k-공간(k-space)이라는 주파수 공간상의 데이터이다. 이 k-공간 데이터를 2차원 또는 3차원 FFT를 통해 역변환함으로써 우리가 진단에 사용하는 해부학적 단층 이미지를 재구성한다.37 FFT의 속도는 MRI 스캔 시간 단축과 고해상도 이미지 구현에 직접적인 영향을 미친다.
• 기타 분야: FFT의 응용 분야는 무궁무진하다. 지진학에서는 지진파 데이터를 FFT하여 지진의 진원과 규모를 파악하고 37, 금융 공학에서는 주식 시장 데이터와 같은 시계열 데이터를 FFT하여 숨겨진 주기성이나 계절성을 분석한다.26 천문학에서는 전파망원경으로 수신한 신호를 FFT하여 천체의 특성을 연구하는 등, 데이터에 내재된 주기성을 찾는 거의 모든 과학 및 공학 분야에서 FFT는 핵심적인 분석 도구로 사용된다.

7. 결론

고속 푸리에 변환(FFT)은 이산 푸리에 변환(DFT)의 계산 복잡도를 근본적으로 개선한, 단순한 최적화를 넘어선 알고리즘의 위대한 승리이다. O(N^2)에서 O(N \log N)으로의 전환은 계산 과학의 패러다임을 바꾸었으며, 이론 속에 갇혀 있던 수많은 가능성을 현실 세계의 기술로 해방시켰다.

FFT는 현대 디지털 혁명의 보이지 않는 기반이다. 우리가 매일 사용하는 스마트폰의 무선 통신(OFDM), 인터넷을 통해 소비하는 압축된 이미지(JPEG)와 음악(MP3), 병원에서 진단에 사용하는 첨단 의료 영상(MRI) 기술의 중심에는 모두 FFT가 조용히 작동하고 있다. FFT는 이처럼 눈에 잘 띄지는 않지만 우리 주변의 거의 모든 디지털 기술을 가능하게 하는 ’조용한 동력(silent engine)’으로서의 역할을 충실히 수행해왔다.

쿨리-튜키 알고리즘이 제시한 분할 정복의 지혜, 그리고 그 지혜를 현실로 만든 회전 인자의 아름다운 수학적 성질의 조화는 알고리즘 설계의 정수를 보여준다. 더 나아가, 이론적 연산량과 실제 하드웨어 성능 사이의 관계에 대한 고찰은 우리에게 알고리즘이 존재하는 계산 환경과의 상호작용을 깊이 이해해야 한다는 교훈을 준다.

결론적으로, FFT의 사례는 잘 설계된 단 하나의 알고리즘이 어떻게 과학과 공학의 발전을 수십 년간 이끌고, 나아가 인류의 삶의 방식을 근본적으로 변화시킬 수 있는지를 보여주는 가장 강력하고 영감 있는 증거이다. 이는 미래의 계산과학과 알고리즘 연구가 지닌 무한한 잠재력과 중요성을 다시 한번 일깨워준다.

8. 참고 자료

1. FFT(고속푸리에 변환)란 무엇인가 - 꼬맹이 놀이터, https://comeng.tistory.com/entry/FFT%EA%B3%A0%EC%86%8D%ED%91%B8%EB%A6%AC%EC%97%90-%EB%B3%80%ED%99%98%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80
2. DFT, FFT 이해하기, https://www.acmicpc.net/blog/view/141
3. 이산 푸리에 변환 - 나무위키, https://namu.wiki/w/%EC%9D%B4%EC%82%B0%20%ED%91%B8%EB%A6%AC%EC%97%90%20%EB%B3%80%ED%99%98
4. FFT 와 DFT 관계 (Fast Fourier Transform vs Discrete Fourier Transform) - 팜테크(FAMTECH) - 티스토리, https://famtech.tistory.com/17
5. 푸리에 변환과 스펙트럼 - 데이터 사이언스 스쿨, https://datascienceschool.net/03%20machine%20learning/03.03.02%20%ED%91%B8%EB%A6%AC%EC%97%90%20%EB%B3%80%ED%99%98%EA%B3%BC%20%EC%8A%A4%ED%8E%99%ED%8A%B8%EB%9F%BC.html
6. 고속 푸리에 변환 - 위키백과, 우리 모두의 백과사전, https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98
7. FFT (Fast Fourier Transform) Algorithm이란 무엇인가??, https://nowgnas.github.io/archive/2020-05-07-FFT.html
8. Fast Fourier Transform (FFT) 구현 - fullog - 티스토리, https://fullyz.tistory.com/24
9. 이산 푸리에 변환(DFT) 및 FFT 이해하기 - YouTube, https://www.youtube.com/watch?v=IeL_YjhhXBw
10. FFT와 윈도잉 이해하기 - NI, https://www.ni.com/ko/shop/data-acquisition/measurement-fundamentals/analog-fundamentals/understanding-ffts-and-windowing.html
11. 고속 푸리에 변환 - 붉은 각설탕 - 티스토리, https://redcubes.tistory.com/227
12. Fast Fourier Transform (FFT) Algorithms Direct Computation of the DFT, https://uomustansiriyah.edu.iq/media/lectures/5/5_2022_10_31!09_01_55_PM.pdf
13. Speed and Precision Comparisons - The Scientist and Engineer’s Guide to Digital Signal Processing, https://www.dspguide.com/ch12/4.htm
14. 07-1. FFT 유도 - Algorithm Information Computing - 티스토리, https://infograph.tistory.com/332
15. Fast Fourier Transform - VCANUS’s Technical Blog, https://tech-vcanus.github.io/development/Fast-Fourier-Transform/
16. FFT: The Butterfly Diagram - AlwaysLearn.com, https://www.alwayslearn.com/DFT%20and%20FFT%20Tutorial/DFTandFFT_FFT_TheButterflyDiagram.html
17. FFT: An 8 Input Butterfly - AlwaysLearn.com, https://www.alwayslearn.com/DFT%20and%20FFT%20Tutorial/DFTandFFT_FFT_Butterfly_8_Input.html
18. Learn the FFT | Lloyd Rochester’s Geek Blog, https://lloydrochester.com/post/dsp/fast-fourier-transform/
19. DIT FFT | 8 point | Butterfly diagram - YouTube, https://m.youtube.com/watch?v=FaWSGmkboOs&pp=0gcJCfwAo7VqN5tD
20. 8 point DIF FFT butterfly diagram - YouTube, https://www.youtube.com/watch?v=5d-U4KXMtfg
21. EFFICIENT VLSI ARCHITECTURE USING DIT-FFT RADIX-2 AND SPLIT RADIX FFT ALGORITHM - ijtre, https://ijtre.com/images/scripts/2014011022.pdf
22. A General Comparison Of FFT Algorithms - Infineon Developer …, https://community.infineon.com/gfawx74859/attachments/gfawx74859/psoc135/31403/1/A_General_Comparison_Of_FFT_Algorithms_713229618.pdf
23. Radix-4 FFT versus Radix-2 - Signal Processing Stack Exchange, https://dsp.stackexchange.com/questions/9938/radix-4-fft-versus-radix-2
24. There are many ways to decompose an FFT [Rabiner and Gold] • The simplest ones are radix-2, https://www.ece.ucdavis.edu/~bbaas/281/notes/Handout.fft2.pdf
25. Notes on FFTs: for implementers | The ryg blog - WordPress.com, https://fgiesen.wordpress.com/2023/03/19/notes-on-ffts-for-implementers/
26. [FFT 시리즈 #1] 마크베이스 네오를 활용한 실시간 고속 푸리에 변환 (FFT : Fast Fourier Transformation) - MachBase, https://machbase.medium.com/fft-%EC%8B%9C%EB%A6%AC%EC%A6%88-1-%EB%A7%88%ED%81%AC%EB%B2%A0%EC%9D%B4%EC%8A%A4-%EB%84%A4%EC%98%A4%EB%A5%BC-%ED%99%9C%EC%9A%A9%ED%95%9C-%EC%8B%A4%EC%8B%9C%EA%B0%84-%EA%B3%A0%EC%86%8D-%ED%91%B8%EB%A6%AC%EC%97%90-%EB%B3%80%ED%99%98-fft-fast-fourier-transformation-204393818158
27. OFDM - 지식덤프, http://www.jidum.com/jidums/view.do?jidumId=502
28. OFDM이란? - FFT(고속 퓨리에 변환) - RF열무의 라이프 스터디 블로그, https://rf-yeolmu.tistory.com/63
29. Software-Defined Radio 기반 LTE OFDM 수신기 구현 - AWS, https://journal-home.s3.ap-northeast-2.amazonaws.com/site/2020kics/presentation/0359.pdf
30. [논문]OFDM 시스템에 적합한 FFT 성능 평가 및 구현 - 한국과학기술정보연구원, https://scienceon.kisti.re.kr/srch/selectPORSrchArticle.do?cn=JAKO201017463456646
31. OFDM System에서 FFT 윈도우 위치 복원 알고리즘을 이용한 효율적인 프레임 동기방식의 성능분석 - Korea Science, https://koreascience.kr/article/JAKO200119663059043.pdf
32. 이산코사인변환 기반 이미지 압축 알고리즘에 관한 재구성 - Korea Science, https://koreascience.kr/article/JAKO201912261948933.pdf
33. JPEG 압축 제대로 이해하기 - bskyvision.com, https://bskyvision.com/entry/JPEG-%EC%9D%B4%EB%AF%B8%EC%A7%80-%ED%8C%8C%EC%9D%BC-%ED%98%95%EC%8B%9D%EC%9D%98-%EC%9B%90%EB%A6%AC%EC%99%80-%EC%9D%B4%ED%95%B4
34. [디지털이미지] JPEG 압축 이해하기 - Suyeon’s Blog - 티스토리, https://suyeon96.tistory.com/15
35. JPEG압축, DCT이산 코사인 변환 - 프랑스 대학원생의 Diary, https://nuninienfrance.tistory.com/24
36. 이산 코사인 변환 - 위키백과, 우리 모두의 백과사전, https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%82%B0_%EC%BD%94%EC%82%AC%EC%9D%B8_%EB%B3%80%ED%99%98
37. 푸리에 변환: 신호의 마법사 ‍♂️ - 재능넷, https://www.jaenung.net/tree/5400