이산 푸리에 변환과 고속 푸리에 변환(Discrete and fast Fourier transforms)

소리를 녹음하면 컴퓨터에는 수의 목록이 남습니다. 1초에 수만 번, 그 순간의 공기 압력을 잰 값(표본)들입니다. 이 목록에 어떤 높이의 소리가 얼마나 섞였는지, 곧 어떤 진동수의 파동이 얼마나 들어 있는지 알고 싶다고 합시다. 푸리에 급수⁠(Fourier series)⁠는 주기함수⁠(periodic function)⁠를 진동수가 1, 2, 3, …배인 사인⁠(sine)⁠·코사인파의 합으로 나누지만, 계수를 얻으려면 곡선 전체를 알고 적분⁠(integral)⁠해야 합니다. 띄엄띄엄 잰 표본 N개만 가진 컴퓨터를 위한 판이 이산 푸리에 변환(DFT)입니다. '이산'은 값이 연속으로 이어지지 않고 떨어져 있다는 뜻입니다.

N = 4인 예로 시작합시다. 한 주기⁠(period)⁠를 넷으로 나누어 잰 표본이 $x = (5, 3, 1, 3)$이라 합시다. 사실 이 값들은 평균⁠(mean)⁠ 3에, 한 주기에 한 번 오르내리는 코사인파 $2\cos(2\pi j/4)$를 더한 것입니다. j = 0, 1, 2, 3에서 코사인⁠(cosine)⁠ 값이 1, 0, −1, 0이기 때문입니다. 이산 푸리에 변환은 이 사실을 표본만 보고 찾아냅니다. 재료는 복소수⁠(complex number)⁠ 평면의 단위원⁠(unit circle)⁠ 위에서 한 칸마다 시계 방향으로 4분의 1바퀴씩 도는 점 1, −i, −1, i입니다(i는 제곱하면 −1인 수). 한 칸 도는 것을 ω(오메가) = −i라 두면, k번째 결과 $X_k$는 j번째 표본에 $\omega^{jk}$를 곱해 모두 더한 값입니다. 행렬⁠(matrix)⁠로 적으면 이렇습니다.

$$\begin{bmatrix} X_0 \\ X_1 \\ X_2 \\ X_3 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{bmatrix} \begin{bmatrix} 5 \\ 3 \\ 1 \\ 3 \end{bmatrix} = \begin{bmatrix} 12 \\ 4 \\ 0 \\ 4 \end{bmatrix}$$

한 줄씩 확인할 수 있습니다. 첫 줄은 모두 1이라 표본의 합 5 + 3 + 1 + 3 = 12입니다. 둘째 줄은 5 − 3i − 1 + 3i = 4, 셋째 줄은 5 − 3 + 1 − 3 = 0, 넷째 줄은 5 + 3i − 1 − 3i = 4입니다. 읽는 법은 이렇습니다. $X_0/4 = 3$은 평균입니다. $X_1$과 $X_3$에는 한 주기에 한 번 도는 성분이 시계 방향과 반시계 방향으로 반씩 나뉘어 담기므로, $(X_1 + X_3)/4 = 2$가 코사인파의 진폭입니다. $X_2 = 0$은 +, −, +, −로 번갈아 뛰는 가장 빠른 성분이 없다는 뜻입니다. 거꾸로 X에서 표본을 되살리는 식도 거의 같은 모양이라(ω 대신 1/ω를 쓰고 N으로 나눔), 정보는 조금도 사라지지 않습니다.

일반적으로 표본 $x_0, x_1, \ldots, x_{N-1}$의 이산 푸리에 변환은 다음과 같습니다.

$$X_k = \sum_{j=0}^{N-1} x_j\,\omega^{jk}, \qquad \omega = e^{-2\pi i/N}$$

Σ(시그마)는 j = 0부터 N − 1까지 더하라는 기호이고, ω는 단위원을 N등분해 시계 방향으로 한 칸 간 점입니다(1의 거듭제곱근⁠(roots of unity)⁠, 오일러 공식⁠(Euler's formula)⁠). $X_k$는 한 주기에 k번 도는 파동이 표본에 얼마나 들어 있는지를, 크기와 어긋난 정도(위상⁠, phase⁠)까지 담은 복소수입니다. 성분들이 서로 섞이지 않고 하나씩 뽑혀 나오는 까닭은 행렬의 서로 다른 두 줄이 직교⁠(orthogonality)⁠하기 때문입니다. 한 줄의 수에 다른 줄의 수의 켤레(허수부⁠(imaginary part)⁠의 부호를 바꾼 수)를 짝지어 곱하면, 곱들이 단위원 위에 고르게 퍼진 점이 되어 정다각형⁠(regular polygon)⁠의 꼭짓점⁠(vertex)⁠처럼 합이 0이 됩니다. 위 행렬의 둘째와 넷째 줄이면 곱이 1, −1, 1, −1이라 합이 0입니다.

흔히 결과 N개가 서로 다른 N가지 진동수라고 생각하지만, 소리처럼 표본이 실수⁠(real number)⁠이면 $X_k$와 $X_{N-k}$는 같은 진동수의 두 반쪽입니다(위의 예에서 $X_1 = X_3$). 표본 N개로 구별할 수 있는 진동수는 한 주기에 N/2번까지이고, 그보다 빠른 파동은 더 느린 파동과 똑같은 표본을 남겨 구별되지 않습니다. 표본화 정리⁠(sampling theorem)⁠가 담긴 가장 높은 진동수의 두 배보다 촘촘히 재라고 하는 까닭입니다.

정의대로 계산하면 결과 N개마다 표본 N개를 곱해 더하니 곱셈이 약 $N^2$번 듭니다. 고속 푸리에 변환(FFT)은 같은 답을 훨씬 적은 계산으로 냅니다. 요령은 표본을 짝수 번째와 홀수 번째로 나누는 것입니다. 짝수 번째 표본에는 $\omega^2$의 거듭제곱이 곱해지는데, $\omega^2$은 단위원을 N/2등분한 점이라 짝수 번째끼리의 합은 길이 N/2의 변환 E가 됩니다. 홀수 번째끼리의 합도 $\omega^k$가 하나 더 붙을 뿐 길이 N/2의 변환 O입니다. 그러면 전체의 답은 다음과 같습니다.

$$X_k = E_k + \omega^k O_k, \qquad X_{k+N/2} = E_k - \omega^k O_k$$

둘째 식의 빼기는 반 바퀴 돌면 −1이라는 것($\omega^{N/2} = -1$)에서 옵니다. 위의 예에서 짝수 번째는 (5, 1), 홀수 번째는 (3, 3)입니다. 길이 2의 변환은 (a, b)를 (a + b, a − b)로 보내므로 E = (6, 4), O = (6, 0)입니다. 그러면 $X_0 = 6 + 6 = 12$, $X_1 = 4 + (-i) \times 0 = 4$, $X_2 = 6 - 6 = 0$, $X_3 = 4 - (-i) \times 0 = 4$로, 행렬로 구한 답과 같습니다.

길이 N의 문제가 길이 N/2의 문제 둘과 마무리 한 단계로 바뀌었습니다. 마무리에는 곱셈 N/2번과 덧셈 N번이 듭니다. N이 2의 거듭제곱이면 이 쪼개기를 길이 1까지 $\log_2 N$번 되풀이할 수 있고, 단계마다 드는 계산이 N에 비례하니 모두 $N \log_2 N$에 비례합니다. N = 1,024이면 $N^2$은 백만 남짓이고 $N \log_2 N$은 1,024 × 10으로 1만 남짓입니다. 문제를 반으로 나누어 풀고 합치는 이런 방법이 분할 정복⁠(divide and conquer)⁠이고, 계산량을 이렇게 N의 함수⁠(function)⁠로 어림하는 말이 점근 표기법⁠(asymptotic notation)⁠입니다. N이 2의 거듭제곱이 아니어도 N을 인수들로 쪼개는 비슷한 방법이 있습니다.

이 쪼개기는 두 번 발견되었습니다. 1805년 무렵 가우스는 소행성 팔라스와 주노의 관측값을 사인과 코사인⁠(sine and cosine)⁠의 합으로 보간⁠(interpolation)⁠하는 계산을 줄이려고 같은 방법을 원고에 적었지만 출판하지 않았고, 원고는 그가 죽은 뒤 1866년 전집에 실렸습니다. 널리 퍼진 것은 1965년 IBM의 제임스 쿨리와 프린스턴의 존 튜키가 발표한 뒤입니다. 튜키가 이 생각을 한 것은 대통령 과학 자문 위원회에서 소련의 핵실험을 나라 밖의 지진계로 잡아낼 방법을 논의하던 자리였다고 전합니다. 가우스의 원고에 같은 방법이 있었다는 것은 그 뒤에야 알려졌습니다.

오늘날 FFT는 신호를 진동수로 나누는 거의 모든 곳에 있습니다. 소리의 스펙트럼, 곧 진동수별 세기를 그리는 일이 그렇고, JPEG와 MP3가 쓰는 코사인판 변환(이산 코사인 변환⁠, discrete cosine transform⁠)도 같은 쪼개기로 빠르게 계산합니다. 두 수열의 한쪽을 뒤집어 밀어 가며 겹치는 칸끼리 곱해 더하는 합성곱⁠(convolution)⁠도 진동수 쪽에서는 성분끼리의 곱셈이 되므로, 큰 다항식⁠(polynomial)⁠이나 자릿수가 아주 많은 수의 곱셈이 FFT로 빨라집니다.

이어지는 곳. 곡선 전체를 쓰는 원래의 판은 푸리에 급수이고, 성분이 섞이지 않는 까닭인 '정다각형의 합은 0'은 1의 거듭제곱근에, 코사인만 쓰는 사촌은 이산 코사인 변환에, 표본을 얼마나 촘촘히 잡아야 하는지는 표본화 정리에 있습니다. 반씩 쪼개는 계산의 일반론은 분할 정복이고, FFT를 세상에 알린 사람의 이야기는 존 튜키에 있습니다. 푸리에의 사인과 코사인에서 FFT까지의 흐름은 「원에서 파동으로」가, JPEG와 튜키의 이야기는 「짧게 보내기」 6절이, 가우스의 소행성 계산은 「잃어버린 소행성」 7절이, FFT가 분배법칙⁠(distributive law)⁠으로 공통 인수를 묶어 내는 계산이라는 것은 「같은 계산, 다른 덧셈」 7절이 보여 줍니다.