블루스타인 알고리즘

1. 개요

블루스타인 알고리즘 Bluestein's algorithm / chirp-z
목적	임의 길이 N(큰 소수 포함)의 DFT를 O(N log N)에
핵심 항등식	nk = [n2 + k2 − (k−n)2] / 2
환원	DFT → 처프와의 선형 합성곱 → 2의 거듭제곱 FFT 3번
패딩 길이	M ≥ 2N − 1
일반화	처프 z-변환(CZT), 줌 FFT
경쟁자	라더 알고리즘(소수 길이 전용)

블루스타인 알고리즘(Bluestein’s algorithm)은 길이 $N$ 의 이산 푸리에 변환을 처프(chirp) 신호와의 합성곱으로 다시 쓴 뒤, 그 합성곱을 2의 거듭제곱 길이 FFT로 계산해서 어떤 길이든 $O(N\log N)$ 에 DFT를 끝내는 방법이다. $N$ 이 1009, 10007 같은 큰 소수여도 상관없다.

고속 푸리에 변환의 쿨리-투키 분할정복은 $N$ 을 작은 인수로 쪼갤 수 있을 때만 빠르다. 소인수가 큰 길이에서는 $O(N^2)$ 에 가깝게 떨어진다. 블루스타인은 이 구멍을 합성곱 정리로 메운다. 이 문서는 항등식 하나로 DFT가 합성곱이 되는 과정, 패딩 길이의 근거, 그리고 교과서 코드를 그대로 옮기면 정밀도가 $N$ 에 비례해 나빠지는 함정을 다룬다.

2. 항등식 하나

DFT는 $X_k = \sum_{n=0}^{N-1} x_n\, W^{nk}$, $W = e^{-2\pi i/N}$ 이다. 블루스타인의 관찰은 지수 $nk$ 를 제곱들로 바꿔 쓰는 것이다.

$$nk = \frac{n^2 + k^2 - (k-n)^2}{2}$$

이걸 대입하고 처프 $w_n = e^{-\pi i n^2/N}$ 을 정의하면

$$X_k = w_k \sum_{n=0}^{N-1} \left(x_n w_n\right)\, \overline{w_{k-n}}$$

가 된다. 합 부분은 수열 $a_n = x_n w_n$ 과 $b_m = \overline{w_m}$ 의 선형 합성곱이다. 즉 DFT는 「처프를 곱하고 → 처프와 합성곱하고 → 다시 처프를 곱하는」 세 단계다. 처프는 위상이 $n^2$ 에 비례해 도는 신호, 소리로 치면 「뽀용~」 하고 주파수가 쓸려 올라가는 음이다¹.

합성곱 쪽 길이는 자유롭게 고를 수 있다. 그래서 합성곱을 2의 거듭제곱 FFT로 계산하면 원래 $N$ 이 무엇이든 빠른 FFT만 쓰게 된다. 길이 $N$ 의 DFT를 다른 길이 $M$ 의 FFT로 바꿔치기하는 셈이다.

3. 패딩 길이와 비용

합성곱 인덱스 $k - n$ 은 $-(N-1)$ 부터 $N-1$ 까지 움직이므로 $b$ 는 길이 $2N-1$ 이 필요하다. 원형 합성곱으로 선형 합성곱을 흉내 내려면 합성곱 정리의 영채움 규칙에 따라 FFT 길이가 $M \ge 2N - 1$ 이어야 한다. $b$ 는 음수 인덱스를 배열 끝에 감아 넣는다($b_{M-m} = \overline{w_m}$). 원형 겹침을 일부러 이용해 음수 인덱스를 처리하는, 깔끔한 트릭이다.

비용은 길이 $M$ FFT 세 번($a$ 정방향, $b$ 정방향, 곱의 역방향)과 처프 곱셈 $O(N)$ 이다. $b$ 의 스펙트럼은 $N$ 에만 의존하므로 같은 길이를 반복하면 미리 계산해 두고 FFT 두 번으로 줄인다. $M$ 이 $2N$ 에서 $4N$ 사이라, 같은 크기의 2의 거듭제곱 FFT보다 상수가 몇 배 크다. 점근적으로는 $O(N\log N)$ 이지만 공짜는 아니다. 실제로 $N = 1009$ 면 $M = 2048$, $N = 10007$ 이면 $M = 32768$ 이다 — 후자는 원래 크기의 3.3배다.

4. 검산과 정밀도 함정

위 공식대로 구현해 NumPy FFT와 비교했다. 처프 위상을 계산하는 방법만 두 가지로 바꿨다.

$N$	$M$	위상 $\pi n^2/N$ 그대로	위상 $\pi (n^2 \bmod 2N)/N$
1009	2048	4.5e-13	1.0e-15
10007	32768	2.7e-12	9.0e-16
100003	262144	3.3e-11	1.5e-15

(값은 최대 상대오차.) 오른쪽 열은 기계 정밀도다. 왼쪽 열은 $N$ 에 거의 비례해 나빠진다. 원인은 처프 위상이다. $n$ 이 $N$ 근처면 $\pi n^2/N \approx \pi N$ 라디안, $N = 10^5$ 에서 약 $3\times10^5$ 라디안이다. 이렇게 큰 인자에 대해 사인·코사인을 계산하면, 인자 자체의 반올림 오차 $|\theta|\,\varepsilon \approx 3\times10^5 \times 1.1\times10^{-16} \approx 3\times10^{-11}$ 이 그대로 위상 오차가 된다. 표의 $3.3\times10^{-11}$ 과 맞는다.

처방은 $e^{-\pi i n^2/N}$ 이 $n^2$ 에 대해 주기 $2N$ 이라는 점을 쓰는 것이다. 정수 연산으로 $n^2 \bmod 2N$ 을 먼저 구하면 위상이 늘 $[0, 2\pi)$ 안에 머문다. 정수 $n^2$ 은 $N$ 이 $3\times10^9$ 정도까지 64비트에 안전하게 들어간다. 「쿨리-투키는 반올림 오차가 $O(\log N)$ 으로 자란다」는 FFT의 장점(고속 푸리에 변환의 반올림 절)이 블루스타인에서는 처프 계산 한 줄 때문에 날아갈 수 있다는 것이 요점이다. 수학적으로 같은 식이 부동소수점 연산에서는 다르다².

5. 라더 알고리즘과의 비교

소수 길이 DFT의 다른 고전 해법은 라더 알고리즘(Rader, 1968)이다. $N$ 이 소수면 $\{1, \dots, N-1\}$ 이 곱셈군을 이루고 원시근 $g$ 로 순환하므로, 인덱스를 $n = g^q \bmod N$ 으로 바꾸면 DFT가 길이 $N-1$ 의 원형 합성곱이 된다.

	블루스타인	라더
적용 길이	임의의 $N$	소수 $N$
합성곱 길이	$M \ge 2N-1$ (선형 → 패딩)	$N-1$ (이미 원형)
필요한 것	처프 계산	원시근, 인덱스 순열
약점	패딩으로 2~4배 부피	$N-1$ 의 소인수가 다시 크면 재귀

라더는 합성곱이 짧고 원형이라 효율이 좋지만, $N-1$ 이 또 다른 큰 소수를 품으면 재귀가 깊어진다. 블루스타인은 그런 사정 없이 늘 2의 거듭제곱으로 간다. 실제 라이브러리는 둘을 섞는다. FFTW는 소수 길이에 라더를 쓰는 경로를 가지고 있고, NumPy·SciPy가 쓰는 pocketfft 계열은 큰 소인수가 있을 때 블루스타인으로 넘어간다. 사용자가 할 일은 거의 없다 — np.fft.fft 에 길이 10007을 넣어도 그냥 빠르다. 다만 성능이 중요하면 여전히 빠른 길이로 영채움하는 게 이긴다(scipy.fft.next_fast_len)³.

6. 일반화 — 처프 z-변환과 줌 FFT

라비너·셰이퍼·라더(1969)는 같은 항등식이 단위원 위 $N$ 점만이 아니라 z-평면의 나선 경로 $z_k = A\,W^{-k}$ ($k = 0,\dots,K-1$) 위에서 z-변환을 계산하는 데도 통한다는 것을 보였다. 이것이 처프 z-변환(chirp z-transform, CZT)이다. $A$, $W$ 를 마음대로 고를 수 있으므로

• 줌 FFT — 전체 대역이 아니라 좁은 주파수 구간 $[f_1, f_2]$ 만 아주 촘촘하게 본다. 영채움으로 해상도를 올리는 것보다 계산이 훨씬 적다. 공진 피크 근처를 확대해 감쇠비를 읽는 모드 해석·진동 계측에서 쓴다.
• 단위원 안쪽 경로 — 감쇠하는 지수 신호의 극점을 강조해 볼 수 있다.

SciPy는 scipy.signal.czt 와 zoom_fft 로 이를 제공한다. 블루스타인 알고리즘은 이 CZT에서 $A = 1$, $W = e^{-2\pi i/N}$, $K = N$ 으로 놓은 특수형이다.

7. 관련 문서

• 고속 푸리에 변환 · 합성곱 정리 · 푸리에 변환 · 라더 알고리즘
• 디지털 필터 · 윈도 함수 · 이산 코사인 변환 · 모드 해석
• 부동소수점 연산 · 스펙트럴 방법 · 순환 행렬

8. Footnotes

1. 이름 자체가 새 지저귐(chirp)에서 왔다. 레이더 펄스 압축에서 쓰던 그 처프다. DSP 사람들은 같은 신호로 레이더도 하고 DFT도 한다. ↩

2. 교과서 의사코드는 대개 exp(-1j*pi*n**2/N) 한 줄로 끝난다. 그 한 줄이 $N=10^5$ 에서 다섯 자리를 먹는다. 정수 나머지 한 번이면 되찾는다. ↩

3. 블루스타인은 「소수 길이도 빠르다」를 보장하는 보험이지, 「소수 길이가 2의 거듭제곱만큼 빠르다」는 약속이 아니다. 길이를 고를 수 있으면 고르는 게 국룰. ↩