합성곱 정리

1. 개요

합성곱 정리 Convolution theorem
내용	합성곱의 푸리에 변환 = 푸리에 변환의 곱
이산판	DFT는 원형 합성곱을 곱으로 바꾼다
선형 합성곱	길이 N+M−1 이상으로 영채움
긴 신호	중첩가산(overlap-add), 중첩저장(overlap-save)
비용	직접 O(NM) → FFT O((N+M) log(N+M))
함정	순환 겹침(wrap-around), 절대오차 바닥

합성곱 정리(convolution theorem)는 두 함수의 합성곱을 푸리에 변환하면 각 푸리에 변환의 점별 곱이 된다는 정리다. 「시간 영역의 합성곱 = 주파수 영역의 곱셈」, 거꾸로 「시간 영역의 곱셈 = 주파수 영역의 합성곱」이다.

고속 푸리에 변환 문서는 이 정리를 응용 목록의 한 줄로 걸어 두었다. 이 문서는 그 한 줄을 실제로 코드로 옮길 때 생기는 일을 다룬다. 연속판 정리를 그대로 이산 신호에 쓰면 거의 확실히 틀린다. DFT가 대각화하는 것은 우리가 원하는 선형 합성곱이 아니라 원형(순환) 합성곱이기 때문이다. 영채움, 블록 분할, 그리고 FFT 합성곱의 오차가 어떻게 생겼는지가 이 문서의 내용이다.

2. 연속판과 이산판

연속 함수에 대해 $(f*g)(t) = \int f(\tau)g(t-\tau)\,d\tau$ 라 하면

$$\mathcal F\{f*g\} = \mathcal F\{f\}\cdot\mathcal F\{g\}$$

이다(변환 정규화 관례에 따라 $2\pi$ 같은 상수가 붙는다). 이산 신호에서 길이 $N$ 의 DFT로 같은 일을 하면 성립하는 것은

$$\mathrm{DFT}_N\{a \circledast b\} = \mathrm{DFT}_N\{a\}\cdot\mathrm{DFT}_N\{b\}, \qquad (a\circledast b)_n = \sum_{m=0}^{N-1} a_m\, b_{(n-m)\bmod N}$$

이다. 인덱스에 붙은 $\bmod N$ 이 전부다. DFT는 신호를 주기 $N$ 으로 반복된다고 보기 때문에, 오른쪽 끝을 넘어간 값이 왼쪽 처음으로 돌아와 더해진다.

선형대수로 보면 더 깔끔하다. 원형 합성곱은 순환 행렬(circulant matrix) $C$ 곱이고, 순환 행렬의 고유벡터는 행렬 성분과 상관없이 언제나 푸리에 모드다. 따라서 DFT 행렬 $F$ 가 모든 순환 행렬을 동시에 대각화한다: $C = F^{-1}\,\mathrm{diag}(\hat c)\,F$. 합성곱 정리는 이 한 줄의 다른 이름이다¹.

3. 원형 대 선형 — 겹침이 실제로 생기는 모습

$a = (1,2,3,4)$, $b = (1,1,1)$ 을 생각하자. 우리가 원하는 선형 합성곱은 길이 $4+3-1 = 6$ 이다.

$$a * b = (1,\ 3,\ 6,\ 9,\ 7,\ 4)$$

그런데 둘 다 길이 4로 맞춰 DFT를 곱하고 역변환하면 나오는 것은

$$a \circledast_4 b = (8,\ 7,\ 6,\ 9)$$

다. 선형 결과의 꼬리 $(7, 4)$ 가 앞으로 돌아와 $1+7 = 8$, $3+4 = 7$ 로 더해졌다. 가운데 두 값 $(6, 9)$ 은 겹침이 닿지 않아 멀쩡하다. 이것이 순환 겹침(wrap-around, time-domain aliasing)이다.

처방은 단순하다. 두 신호를 $L \ge N + M - 1$ 로 영채움하면 꼬리가 돌아올 자리가 0이라 원형 합성곱과 선형 합성곱이 같아진다. 같은 예제를 $L = 6$ 으로 채우면 정확히 $(1,3,6,9,7,4)$ 가 나온다. FFT가 2의 거듭제곱에서 가장 빠르므로 실무에서는 $L$ 을 그 이상의 가장 가까운 「빠른 길이」로 올린다. 영채움이 부족하면 결과 앞쪽이 조용히 오염된다 — 에러 메시지는 없다.

주기 경계를 가진 문제에서는 반대로 원형이 정답이다. 주기경계조건 상자 위의 포아송 방정식을 FFT로 푸는 스펙트럴 방법, 주기 격자의 에발트 합산 역공간 항은 겹침이 물리 그 자체다. 문제는 비주기 문제에 원형 도구를 쓸 때만 생긴다.

4. 긴 신호 — 중첩가산과 중첩저장

필터 $h$(길이 $M$, 예컨대 101)는 짧고 신호 $x$(길이 수백만)는 길면, 신호 전체를 한 번에 FFT하는 것은 메모리도 지연시간도 낭비다. 스톡햄(Stockham, 1966)이 정리한 두 블록 방법이 표준이다.

중첩가산(overlap-add, OLA). 신호를 길이 $L_b$ 블록으로 자르고, 각 블록을 $B \ge L_b + M - 1$ 로 영채움해 필터와 원형 합성곱한다. 각 블록 결과는 길이 $L_b + M - 1$ 이라 다음 블록과 $M-1$ 개 샘플이 겹치는데, 그 겹친 부분을 더한다. 선형성 덕분에 블록별 합성곱의 합이 전체 합성곱이다.

중첩저장(overlap-save, OLS). 블록을 영채움하는 대신 앞 블록의 마지막 $M-1$ 개 샘플을 겹쳐서 읽는다. 원형 합성곱을 그대로 하고, 앞쪽 $M-1$ 개 출력(순환 겹침으로 오염된 부분)을 버린다. 덧셈이 없어 약간 싸다².

검산. 길이 10000 무작위 신호에 101탭 무작위 필터를 블록 크기 $B = 256$(블록당 신호 156샘플)으로 중첩가산해서 직접 합성곱과 비교하면 최대 절대오차가 $1.8\times10^{-14}$ 이다. 블록이 몇 개든 결과는 같은 합성곱이다.

블록 크기는 저울질이다. $B$ 가 작으면 블록당 버리거나 더하는 $M-1$ 개 비율이 커지고, 크면 FFT 비용과 지연이 커진다. 경험칙은 $B$ 를 $M$ 의 몇 배 수준의 2의 거듭제곱으로 잡는 것이다. 실시간 오디오는 여기에 지연 제약이 붙어 블록을 여러 크기로 나누는 분할 합성곱까지 간다.

5. 언제 FFT가 이기나

직접 합성곱은 $O(NM)$, FFT 합성곱은 $O(L\log L)$ 에 FFT 세 번(정방향 둘, 역방향 하나)의 상수가 붙는다. 그래서 필터가 짧으면 직접 합이 이긴다. 손익분기 탭 수는 하드웨어·SIMD·라이브러리에 따라 크게 달라서 숫자 하나로 못 박기 어렵다 — SciPy의 scipy.signal.convolve 가 method='auto' 에서 크기를 보고 둘 중 하나를 고르는 것도 그 때문이다. 원칙은 두 길이가 모두 길수록, 그리고 같은 필터를 여러 번 쓸수록(필터 스펙트럼을 한 번만 계산) FFT 쪽으로 기운다는 것이다.

2차원에서는 격차가 훨씬 커진다. $K\times K$ 커널의 직접 합성곱은 픽셀당 $K^2$ 곱셈이고 FFT는 픽셀당 $O(\log)$ 다. 다만 합성곱 신경망의 3×3 커널처럼 아주 작은 커널은 직접 합이나 위노그라드 변환이 이긴다.

6. FFT 합성곱의 오차는 「절대」 오차다

FFT 기반 합성곱의 반올림 오차는 대략 $\varepsilon\,\|a\|\,\|b\|$ 수준으로 결과 전체에 고르게 깔린다. 결과 값이 크든 작든 같은 잡음 바닥이 붙는다는 뜻이다. 직접 합은 이렇지 않다 — 작은 항끼리 곱한 작은 결과는 작은 오차를 가진다.

검산. 구간 $[-10, 10]$ 의 401점 가우시안 $e^{-x^2}$ 을 자기 자신과 합성곱했다. 최댓값은 25.07이다. 꼬리 쪽 한 점에서 직접 합은 $6.9\times10^{-42}$(참값과 같은 크기)를 주지만, FFT 합성곱은 $7.1\times10^{-16}$ 을 준다. 전체 최대 오차 $1.1\times10^{-14}$ 는 최댓값 대비 $4\times10^{-16}$ 로 기계 정밀도 그대로인데, 꼬리 값은 26자리가 틀렸다.

대부분의 신호처리에서는 이게 문제가 아니다. 하지만 확률분포의 합성곱(꼬리 확률이 중요한 위험 분석), 큰 정수 곱셈(정확한 반올림이 필요), 동적 범위가 넓은 스펙트럼에서는 치명적이다. 큰 정수 곱셈이 부동소수점 FFT 대신 정수 위의 수론 변환(NTT)을 쓰는 이유가 이것이다³. 부동소수점 연산의 상대오차 감각으로 FFT 합성곱을 보면 안 된다.

7. 주변 정리들

• 상관 정리 — 상호상관 $\sum_m a_m b_{m+n}$ 은 한쪽 스펙트럼에 켤레를 취한 곱 $\overline{\hat a}\,\hat b$ 다. 자기상관의 푸리에 변환이 파워 스펙트럼이라는 위너-힌친 정리가 그 특수형이다.
• 곱셈 정리(쌍대) — 시간 영역에서 윈도 함수를 곱하면 스펙트럼은 윈도 스펙트럼과 합성곱된다. 누설(leakage)의 정체다.
• 토플리츠 → 순환 임베딩 — 비주기 합성곱 행렬(토플리츠)을 두 배 크기 순환 행렬에 묻으면 FFT로 행렬-벡터 곱을 할 수 있다. 영채움을 행렬 언어로 한 것이고, 순환 행렬로 토플리츠 계를 전처리기하는 스트랭·찬 전처리도 같은 뿌리다.
• 임의 길이 DFT — 블루스타인 알고리즘은 반대로 DFT 하나를 합성곱으로 바꾼 뒤 이 정리로 푼다. 합성곱 정리가 FFT를 쓰고, FFT가 합성곱 정리를 쓰는 재귀 구조다.

8. 관련 문서

• 고속 푸리에 변환 · 푸리에 변환 · 블루스타인 알고리즘 · 윈도 함수
• 디지털 필터 · 합성곱 신경망 · 이산 코사인 변환 · 하한 합성곱
• 스펙트럴 방법 · 에발트 합산 · 주기경계조건 · 포아송 방정식
• 순환 행렬 · 토플리츠 행렬 · 수론 변환

9. Footnotes

1. 순환 행렬은 「성분이 뭐든 고유벡터는 이미 정해져 있는」 드문 행렬족이다. 고유벡터를 미리 알면 고유값 계산은 FFT 한 번이다. 이게 반칙이 아니면 뭐가 반칙인가. ↩

2. 이름은 「저장」인데 하는 일의 핵심은 「버리기」다. 오염된 앞 $M-1$ 개를 미련 없이 버리는 쪽이 계산이 더 깔끔하다는 교훈. ↩

3. 소수 $p$ 를 법으로 하는 정수 위에서 1의 거듭제곱근을 골라 DFT를 하면 반올림이 아예 없다. 「오차를 줄인다」가 아니라 「오차라는 개념을 없앤다」 쪽의 해법이다. ↩