자연수의 곱, 합성곱을 위한 FFT를 설명하는 다른 블로그를 찾아가 보면 보통 학부생 수준의 배경지식을 요구하거나 구현만 알려주는 곳이 많습니다. 자세하게 증명하는 한국어 글이 없어서 되게 힘들었는데, 여러분은 힘들게 찾아보지 않았으면 해서 글을 써 보았습니다.
이 글은 FFT의 구현이 아니라 DFT, FFT를 이해하는 데 초점을 둡니다. 코드에 대한 설명은 하지 않습니다.
증명을 이해하기 위해선 아래의 배경지식이 필요합니다.
- 오일러 공식
- 삼각함수 (일반각에 대한 성질)
- 등비수열의 합
- 푸리에 변환
- 이산 푸리에 변환
- 고속 푸리에 변환
- 합성곱
- 최적화
푸리에 변환을 몰라도 나머지를 이해할 수 있으니 관심이 없다면 넘어가도 좋습니다.
고등학교 수준의 미적분에 대한 배경지식이 필요합니다.
여러 사인파가 더해진 함수 $h(x)$가 있습니다. 우리는 이 $h(x)$를 이루는 사인파들의 주파수를 알고 싶습니다.
먼저 여러 사인파가 더해진 함수를 생각하기 전에 하나의 사인파를 생각해 봅시다.
여기 주파수를 모르는 한 사인파 $f(x) = \sin ax$가 있습니다. 모른다고 가정합시다.
여기에 우리가 임의로 주파수를 정한 사인파 $g(x) = \sin bx$를 곱합니다.
$f(x)g(x)$를 삼각함수의 곱셈 정리를 이용해 나타내면
$$
f(x)g(x) = \sin ax \sin bx = \frac{\cos((a - b)x) - \cos((a + b)x)}{2}
$$
이를 적분함으로써 $f(x)$와 $g(x)$의 주파수가 일치하는지 확인할 수 있습니다.
$a \neq b$라면 분자의 두 $\cos$함수는 $-1$과 $1$ 사이에서 진동하므로 적분하면 진동 발산합니다.
$a = b$라면
$$
f(x)g(x) = \frac{1 - \cos 2ax}{2}
$$
이고 분자가 $0$과 $1$ 사이에서 진동하므로 적분은 양의 무한대로 발산합니다.
따라서 $h(x)$에 특정 주파수를 갖는 사인파가 있는지 알고 싶다면 곱해서 적분해보면 됩니다.
주파수가 같은 것만 양의 무한대로 발산하고, 나머지는 진동하기 때문입니다.
그런데 $h(x)$에 코사인파도 들어있다면 어떨까요? 코사인파를 곱하면 됩니다.
사인파와 코사인파의 곱은 진동 발산하므로 주파수가 같은 사인파 + 코사인파를 곱해서 적분하면 됩니다.
이는 오일러 공식을 이용해서 하나의 항 $e^{ix}$으로 나타낼 수 있습니다.
$e^{ix} = \cos x + i\sin x$이므로 실수부는 $\cos$, 허수부는 $\sin$이 됩니다.
시간 $t$에 따른 파동을 그리는 함수 $h(t)$의 푸리에 변환 $\hat h(x)$는 아래와 같이 정의됩니다.
여기서 $x$는 주파수입니다.
$$
\hat h(x) = \int_{-\infty}^{\infty}h(t)e^{-2\pi itx}dt
$$
물론 $h(t)$가 사인파의 합과 같은 경우 적분값이 진동 발산하여 값이 정의되지 않지만, 디랙 델타 함수를 이용해 나타내면 된다고 합니다. 그런 것 까지는 몰라도 되니까 넘어갑시다.
푸리에 역변환도 있습니다. $$ h(t) = \int_{-\infty}^{\infty}\hat h(x)e^{2\pi itx}dx $$
$e$의 지수의 부호만 바뀌었습니다. 곱한 코사인, 사인파를 다시 나누어 준 것이라 생각하면 됩니다.
푸리에 변환은 연속 함수를 변환합니다. 이를 실제 세상에 적용하려면 이산적인 데이터를 변환해야 합니다.
그래서 이산 푸리에 변환을 사용합니다.
길이 $N$의 데이터 배열을 $x$라 하면 이산 푸리에 변환된 데이터 $X$는 아래와 같이 정의됩니다.
여기서 $\exp(x) = e^x$입니다.
$$
X[k] = \sum_{n=0}^{N-1}x[n]\exp\left(-i\frac{2\pi kn}{N}\right)
$$
푸리에 변환은 모든 주파수에 대해서 곱했지만, 이산 푸리에 변환에서는 $N$개의 주파수에 대해서만 곱합니다.
여기서 $\omega = \exp\left(-i\dfrac{2\pi}{N}\right)$를 단위근, root of unity라고 합니다.
왜냐하면 $N$제곱하면 지수에 $2\pi$가 남아 오일러 공식에 의해 $1$이 되기 때문입니다.
이산 푸리에 변환에서 곱하는 값은 모두 $\omega^{kn}$입니다.
이 단위근의 성질 $w^N = 1$은 이산 푸리에 역변환을 이해하는 데 중요하게 쓰입니다.
이제 이산 푸리에 역변환에 대해 알아보겠습니다.
아래와 같습니다.
$$
x[n] = \frac{1}{N}\sum_{k=0}^{N-1}X[k]\omega^{-kn}
$$
성립함을 증명해 봅시다.
이산 푸리에 역변환을 다시 쓰면
$$
\begin{align*}
x[n] &= \frac{1}{N}\sum_{k=0}^{N-1}X[k]\omega^{-kn} \\
&= \frac{1}{N}\sum_{k=0}^{N-1}\sum_{r=0}^{N-1}x[r]\omega^{kr}\omega^{-kn} \\
&= \frac{1}{N}\sum_{r=0}^{N-1}x[r]\sum_{k=0}^{N-1}\omega^{k(r-n)} \\
&= \frac{1}{N}\sum_{r=0}^{N-1}x[r]S(r)
\end{align*}
$$
여기서 $S(r)$은 등비수열의 합 공식을 이용해 아래와 같이 쓸 수 있습니다. $$ S(r) = \begin{cases} N & (r = n) \\ \dfrac{1-\omega^{N(r-n)}}{1-\omega^{r-n}} & (r \neq n) \end{cases} $$
그런데 $\omega^N = 1$이므로 $r \neq n$이면 $S(r)$이 $0$이 됩니다.
따라서 $r = n$인 경우만 남기고 모두 $0$이 됩니다. 즉 $x[n]$이 총 $N$번 나오게 됩니다.
이는 나중에 한번 더 쓰이는 중요한 단위근의 성질입니다.
이산 푸리에 변환을 정의에 따라 계산하면 시간 복잡도가 $O(N^2)$이 됩니다.
이를 더 빠르게, $O(N\log N)$에 계산하는 알고리즘을 배워봅시다.
대표적으로 쓰이는 쿨리-튜키 알고리즘을 소개해 보겠습니다.
8개의 데이터 $x_0, x_1, x_2, \dots , x_7$가 있다고 생각해 봅시다.
각 $x$에 서로 다른 $8$가지 주파수를 갖는 사인·코사인파를 곱해야 합니다.
그런데 사인·코사인파의 주기적 특성을 이용하면 곱하는 값이 같은 경우가 생김을 알 수 있습니다.
데이터 중 짝수번째 데이터만 가져와 봅시다.
$x_0, x_2, x_4, x_6$ 로 4개입니다.
곱해야 할 수들은 $\exp\left(-i\dfrac{2\pi kn}{8}\right)$입니다.
여기서 $k$가 $0, 1, 2, 3$인 것과 $4, 5, 6, 7$인 것들끼리 비교해 봅시다.
$k = 0$이면 $\exp(0)$. $k = 4$이면 $\exp(-i\pi n)$
$k = 1$이면 $\exp\left(-i\dfrac{\pi n}{4}\right)$, $k = 5$이면 $\exp\left(-i\dfrac{5\pi n}{4}\right)$
$k = 2$이면 $\exp\left(-i\dfrac{\pi n}{2}\right)$, $k = 6$이면 $\exp\left(-i\dfrac{3\pi n}{2}\right)$
$k = 3$이면 $\exp\left(-i\dfrac{3\pi n}{4}\right)$, $k = 7$이면 $\exp\left(-i\dfrac{7\pi n}{4}\right)$
$k = a$인 경우와 $k = a + 4$인 경우 서로 $\pi$씩 차이남을 알 수 있습니다.
$\exp(i\theta)$가 $\cos$과 $\sin$의 합으로 나타내어 지고
$\sin(\theta + \pi) = -\sin \theta, \cos(\theta + \pi) = -\cos \theta$이므로
$n$이 짝수이면 $\pi$가 두번 더해져 $k = a$일 때와 $k = a + 4$일 때 값이 함숫값이 같음을 알 수 있습니다.
$n$이 홀수이면 부호만 다르겠지요.
일반화해서 데이터가 $N$개가 있을 때, $k = a$일 때 곱하는 값과 $k = a + \dfrac{N}{2}$일 때 곱하는 값을 비교해 봅시다.
$k = a$일 때는 $\exp\left(-i\dfrac{2\pi an}{N}\right)$입니다.
$k = a + \dfrac{N}{2}$일 때는 $\exp\left(-i\dfrac{2\pi an + \pi Nn}{N}\right) = \exp\left(-i\left(\dfrac{2\pi an}{N} + \pi n\right)\right)$입니다.
$\cos, \sin$에 들어가는 값이 $\pi n$만큼 더해졌습니다. $n$이 짝수인 경우 값이 같고,
$n$이 홀수인 경우 둘 모두 부호가 바뀜을 알 수 있습니다.
따라서 $k$가 $N$의 절반일 때까지만 $\cos, \sin$을 구해둔 뒤 $n$이 홀수인지 짝수인지에 따라
부호만 바꿔주면 된다는 것을 알 수 있습니다.
한편 이산 푸리에 변환을 짝수항과 홀수항으로 나눠서 쓰면 $$ X[k] = \sum_{n = 0}^{N/2 - 1} x[2n]\exp\left(-i\frac{2\pi k2n}{N}\right) + \sum_{n = 0}^{N/2 - 1} x[2n+1]\exp\left(-i\frac{2\pi k(2n+1)}{N}\right) $$
지수연산 부분을 정리하면 $$ X[k] = \sum_{n = 0}^{N/2 - 1} x[2n]\exp\left(-i\frac{2\pi kn}{N/2}\right) + \exp\left(-i\frac{2\pi k}{N}\right)\sum_{n = 0}^{N/2 - 1} x[2n+1]\exp\left(-i\frac{2\pi kn}{N/2}\right) $$
여기서 짝수항 부분과 홀수항 부분은 $N/2$크기의 이산 푸리에 변환과 같음을 알 수 있습니다.
짝수항 부분을 이산 푸리에 변환한 결과를 $E[k]$, 홀수항 부분을 $O[k]$라 합시다.
그렇다면 $X[k] = E[k] + \exp\left(-i\dfrac{2\pi k}{N}\right)O[k]$입니다.
이 식은 $k < \dfrac{N}{2}$일 때만 정의됩니다. 하지만 우리는 앞서 $k \geq \dfrac{N}{2}$일 때 짝수항에 곱하는 값은 같고 홀수항에 곱하는 값은 부호만 다르다는 것을 증명했습니다.
따라서 $X\left[k + \dfrac{N}{2}\right] = E[k] - \exp\left(-i\dfrac{2\pi k}{N}\right)O[k]$입니다.
분할정복을 이용하면 $O(N\log N)$에 값을 구할 수 있습니다.
홀수항과 짝수항을 분할하는 부분에서 알 수 있듯이 이 알고리즘은 $N$이 $2$의 거듭제곱일 때만 가능합니다. $N$이 $2$의 거듭제곱이 아닌 경우 0을 몇개 추가해 2의 거듭제곱이 되도록 만드는 제로 패딩 방법이 있습니다.
import cmath
def fft(x):
N = len(x)
if N <= 1:
return x
even = fft(x[0::2])
odd = fft(x[1::2])
twiddle_factors = [cmath.exp(-2j * cmath.pi * k / N) * odd[k] for k in range(N // 2)]
return [even[k] + twiddle_factors[k] for k in range(N // 2)] + [
even[k] - twiddle_factors[k] for k in range(N // 2)
]
이산 푸리에 변환을 $O(N\log N)$에 하는 법을 배웠습니다. 그런데 우리는 이것을 왜 배웠을까요?
바로 이산 푸리에 변환을 통해 합성곱을 할 수 있고, 합성곱으로 다항식의 곱셈을 할 수 있고, 다항식의 곱셈으로 두 수의 곱셈을 할 수 있기 때문입니다.
먼저 합성곱에 대해 알아봅시다. 합성곱은 두 배열의 연산으로, 길이가 $n$인 두 배열 $a, b$의 합성곱은 다음과 같습니다. $$ \begin{gather*} a * b = (c_0, c_1, c_2, \dots, c_{2n-2})\\ \text{where}\ c_k = \sum_{\substack{i, j \\ i + j = k}} a_ib_j \end{gather*} $$ $$ \begin{array}{|c|c|c|c|c|c|} \hline \backslash & a_0 & a_1 & a_2 & a_3 & \dots \\\hline b_0 & a_0b_0 & a_1b_0 & a_2b_0 & \color{blue}{a_3b_0} & \dots \\\hline b_1 & a_0b_1 & a_1b_1 & \color{blue}{a_2b_1} & a_3b_1 & \dots \\\hline b_2 & a_0b_2 & \color{blue}{a_1b_2} & a_2b_2 & a_3b_2 & \dots \\\hline b_3 & \color{blue}{a_0b_3} & a_1b_3 & a_2b_3 & a_3b_3 & \dots \\\hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\\hline \end{array} $$
위 표에서 대각선에 있는 것들을 합한 것이라 생각하면 됩니다.
이는 다항식의 곱셈과 같음을 알 수 있습니다.
$N-1$차 다항식 $f(x), g(x)$를
$f(x) = a_{N-1}x^{N-1} + a_{N-2}x^{N-2} + \dots + a_1x + a_0$,
$g(x) = b_{N-1}x^{N-1} + b_{N-2}x^{N-2} + \dots + b_1x + b_0$라 하면
$h(x) = f(x)g(x) = c_{2N-2}x^{2N-2} + c_{N-2}x^{N-2} + \dots + c_1x + c_0$임을 알 수 있습니다.
뜬금없지만 만약 $f(x)$에서 $x = w^k$를 대입하면 어떻게 될까요? $$ f(\omega^k) = a_n\omega^{k(N-1)} + a_{n-1}\omega^{k(N-2)} + \dots + a_1\omega + a_0 $$
함숫값이 이산 푸리에 변환과 같음을 알 수 있습니다. $$ f(\omega^k) = \sum_{n=0}^{N-1}a_n\exp\left(-i\frac{2\pi kn}{N}\right) = A[k] $$
$A[k]$를 이산 푸리에 역변환하면 다시 $a$를 얻을 수 있다는 것도 알 수 있습니다.
이를 이용하면 $a, b$를 이산 푸리에 변환한 뒤 각 원소를 곱하고 이산 푸리에 역변환하면 $c$를 구할 수 있습니다.
좀 더 자세히 살펴봅시다. $c$의 크기를 $N$이라 합시다. $h(x)$가 $N-1$차 다항식이라는 뜻입니다.
이산 푸리에 역변환의 정의에 따르면
$$
c[n] = \frac{1}{N}\sum_{k=0}^{N-1}C[k]\omega^{-kn}
$$
여기서 $C[k]$ 대신 $A[k]B[k]$를 넣어 성립함을 보이겠습니다. $$ c[n] = \frac{1}{N}\sum_{k=0}^{N-1}A[k]B[k]\omega^{-kn} $$
$a, b$의 크기가 $N$보다 작은데, $0$을 몇개 넣어 $c$의 크기인 $N$으로 맞춰주면 됩니다.
이산 푸리에 변환의 정의를 이용해 $A[k], B[k]$를 다시 쓰면
$$
c[n] = \frac{1}{N}\sum_{k=0}^{N-1}\left(\sum_{r=0}^{N-1}a[r]\omega^{kr}\right)\left(\sum_{s=0}^{N-1}b[s]w^{ks}\right)w^{-kn}
$$
여기서 이중합을 묶고 순서를 바꿔 적으면 $$ c[n] = \frac{1}{N}\sum_{r=0}^{N-1}\sum_{s=0}^{N-1}a[r]b[s] \left(\sum_{k=0}^{N-1}w^{k(r+s-n)}\right) $$
여기서 $w^{k(r + s - n)}$은 단위근의 성질에 의해 지수가 $0$이 아니라면 합하는 과정에서 서로 상쇄되고, $0$이 됩니다. 따라서 $r + s = n$인 경우의 값만 $N$번 나옵니다. 따라서 정리하면 $$ c[n] = \sum_{\substack{r, s \\ r + s = n}} a[r]b[s] $$
이는 합성곱의 정의에 부합합니다.
import cmath
def fft(x):
N = len(x)
if N <= 1:
return x
even = fft(x[0::2])
odd = fft(x[1::2])
twiddle_factors = [
cmath.exp(-2j * cmath.pi * k / N) * odd[k] for k in range(N // 2)
]
return [even[k] + twiddle_factors[k] for k in range(N // 2)] + [
even[k] - twiddle_factors[k] for k in range(N // 2)
]
def ifft(x):
N = len(x)
if N <= 1:
return x
even = ifft(x[0::2])
odd = ifft(x[1::2])
twiddle_factors = [cmath.exp(2j * cmath.pi * k / N) * odd[k] for k in range(N // 2)]
return [(even[k] + twiddle_factors[k]) / 2 for k in range(N // 2)] + [
(even[k] - twiddle_factors[k]) / 2 for k in range(N // 2)
]
def multiply(x, y):
res = ifft([i * j for i, j in zip(fft(x), fft(y))])
return [round(i.real) for i in res]
print(multiply([1, 0, 3, 4, 0, 0, 0, 0], [1, 2, 3, 4, 0, 0, 0, 0]))
이러한 구현 방식은 매번 짝수번째와 홀수번째를 분리해 새로 담아야 하고,
재귀함수라 메모리를 많이 사용한다는 단점이 있습니다.
$x = [x_0, x_4, x_2, x_6, x_1, x_5, x_3, x_7]$의 형태로 바꿔서 정렬하면 인접한 원소들끼리만 연산해도 됩니다.
위치가 어떻게 바뀌는지 이진수로 보면 규칙을 찾을 수 있습니다.
원래 인덱스 -> 바뀐 인덱스
0 (000) -> 0 (000)
1 (001) -> 4 (100)
2 (010) -> 2 (010)
3 (011) -> 6 (110)
4 (100) -> 1 (001)
...
비트를 좌우반전 시킨 곳으로 이동한다는 사실을 알 수 있습니다.
초기 위치 $b_2b_1b_0 (2)$를 $b_0b_1b_2 (2)$로 바꾸면 됨을 증명해 봅시다.
짝수인 원소들은 왼쪽으로, 홀수인 원소들은 오른쪽으로 이동해야 합니다.
이는 $b_0$에 따라 결정되므로 맨 앞에 $b_0$가 와야 합니다.
짝수인 원소들 중에서도 짝수번째 원소들(4의 배수)은 왼쪽으로, 아닌 원소들은 오른쪽으로 이동해야 합니다.
이는 $b_1$에 따라 결정되므로 $b_0$다음 $b_1$이 와야 합니다.
...
이와 같은 논리로 비트를 좌우반전하면 원하는 형태로 정렬된다는 것을 알 수 있습니다.
import cmath
def fft(x):
n = len(x)
for i in range(n):
rev = 0
j = 1
index = i
while j < n:
j <<= 1
index >>= 1
rev = (rev << 1) + (index & 1)
if i < rev:
x[i], x[rev] = x[rev], x[i]
length = 2
while length <= n:
e = cmath.exp(-2j * cmath.pi / length) # 단위근
for i in range(0, n, length):
w = 1
for j in range(length >> 1):
even = x[i | j]
odd = x[i | j | length >> 1] * w
x[i | j] = even + odd
x[i | j | length >> 1] = even - odd
w *= e
length <<= 1
return x
최대한 쉽게 설명해보고자 노력했습니다.
이해가 안가는 부분이 있거나 오류가 있다면 댓글로 남겨주시면 감사하겠습니다.

댓글 (1개) 댓글 쓰기
dohyeondol 1년 전
최근에 얄팍한 지식으로 FFT를 이해하느라 좀 힘들었는데, 좋은 글 감사합니다.