단위원근과 대칭

핵심 질문

단위원 위의 회전값들은 왜 FFT에서 재사용될 수 있을까?

교과서 설명

복소평면에서 단위원 위의 점들은 길이가 $1$ 인 복소수다. 이 점들 중에서 $N$ 번 곱하면 $1$ 로 돌아오는 값들을 $1$ 의 $N$ 제곱근이라고 부른다.

z^N=1

이 점들은 원을 똑같은 각도로 나눈 위치에 있다.

e^{2\pi i k/N}\qquad(k=0,1,\dots,N-1)

DFT에서는 보통 방향이 반대인 기본 회전값을 쓴다.

\omega_N=e^{-2\pi i/N}

그리고 그 거듭제곱들을 검사점으로 사용한다.

1,\omega_N,\omega_N^2,\dots,\omega_N^{N-1}

$N$ 이 짝수이면 반 바퀴 떨어진 점은 부호만 반대다.

\omega_N^{k+N/2}=-\omega_N^k

왜냐하면

\omega_N^{N/2}=e^{-2\pi i(N/2)/N}=e^{-\pi i}=-1

이므로

\omega_N^{k+N/2}=\omega_N^k\omega_N^{N/2}=-\omega_N^k

이기 때문이다. FFT의 butterfly에서 아래쪽 출력의 부호가 바뀌는 이유가 바로 이 식이다.

FFT에는 또 하나의 성질이 꼭 필요하다. $N$ 개의 점에서 하나를 골라 제곱하면, 각도가 두 배가 되면서 $N/2$ 개의 점 중 하나가 된다.

(\omega_N^k)^2=\omega_{N/2}^k

직접 펼치면

(\omega_N^k)^2=\left(e^{-2\pi i k/N}\right)^2=e^{-2\pi i k/(N/2)}=\omega_{N/2}^k

이 성질 때문에 짝수 차수와 홀수 차수로 나눈 식의 $x^2$ 자리에 들어가는 값들이 “절반 크기 DFT의 검사점”이 된다.

예를 들어 $N=8$ 이면 제곱한 값들은 길이 $4$ 짜리 단위원근 위로 모인다.

(\omega_8^k)^2=\omega_4^k

$k=0,1,2,3$ 과 $k=4,5,6,7$ 은 제곱한 뒤 같은 네 위치를 한 번 더 지난다. 그래서 길이 $8$ DFT 안에는 길이 $4$ DFT 결과를 재사용할 수 있는 구조가 숨어 있다.

원시 단위원근과 직교합

$\omega_N=e^{-2\pi i/N}$ 은 $N$ 번 곱하면 $1$ 이 된다.

\omega_N^N=e^{-2\pi i}=1

또 $0,1,\dots,N-1$ 번째 거듭제곱은 서로 다른 $N$ 개의 점을 만든다. 이 점들을 모두 $1$ 의 $N$ 제곱근이라고 부른다. 그중 $\omega_N$ 처럼 거듭제곱을 반복했을 때 $N$ 개의 점을 빠짐없이 지나가는 값을 원시 $N$ 제곱근 primitive root of unity라고 부른다.

여기서 “원시”라는 말은 “정확히 $N$ 번 돌아야 처음으로 $1$ 에 돌아온다”는 뜻에 가깝다. 어떤 수가 $N$ 번 곱해서 $1$ 이 된다고 해서 항상 원시는 아니다. 예를 들어 $N=4$ 에서 $-1$ 은

(-1)^4=1

이므로 $1$ 의 $4$ 제곱근이지만, 거듭제곱은

1,\ -1,\ 1,\ -1,\dots

처럼 두 점만 반복한다. 그래서 $-1$ 은 원시 $4$ 제곱근이 아니다. 반면 $\omega_4=-i$ 는

1,\ -i,\ -1,\ i

를 모두 지나간 뒤 다시 $1$ 로 돌아온다. 그래서 $\omega_4$ 는 원시 $4$ 제곱근이다. DFT에는 $N$ 개의 서로 다른 검사 방향이 필요하므로, 이렇게 모든 방향을 빠짐없이 만드는 원시 단위원근을 기본 회전값으로 쓴다.

단위원근의 가장 중요한 성질 중 하나는 기하급수 합이다. $r\ne1$ 일 때

1+r+r^2+\cdots+r^{N-1}=\frac{1-r^N}{1-r}

이 공식이 왜 나오는지도 한 줄씩 보면 어렵지 않다. 먼저

S=1+r+r^2+\cdots+r^{N-1}

라고 두고 양쪽에 $r$ 을 곱하면

rS=r+r^2+\cdots+r^{N-1}+r^N

이다. 두 식을 빼면 가운데 항이 모두 사라져

S-rS=1-r^N

이 되고, 따라서 $(1-r)S=1-r^N$ 이다. $r\ne1$ 이면 양쪽을 $1-r$ 로 나눌 수 있으므로 위의 기하급수 공식이 나온다.

여기서 $r=\omega_N^m$ 이고 $m$ 이 $N$ 의 배수가 아니면 $r^N=1$ 이면서 $r\ne1$ 이다. 따라서

\sum_{n=0}^{N-1}(\omega_N^m)^n=0

가 된다. 분자는 $1-r^N=0$ 이고, 분모는 $1-r\ne0$ 이기 때문이다. 그림으로 보면 원 위에 같은 간격으로 놓인 화살표들을 모두 더하는 것과 같다. 정다각형의 꼭짓점 방향 화살표가 균형을 이루어 원점으로 돌아오므로 합이 $0$ 이 된다.

반대로 $m$ 이 $N$ 의 배수이면 $r=\omega_N^m=1$ 이다. 이때는 모든 항이 $1$ 이므로 합은 $N$ 이다.

\sum_{n=0}^{N-1}\omega_N^{mn} = \begin{cases} N,&m\equiv0\pmod N\\ 0,&m\not\equiv0\pmod N \end{cases}

이 직교합은 역 DFT, 주파수 분리, FFT의 재사용 구조를 모두 지탱하는 핵심 정리다.

실수 신호에서 생기는 켤레 대칭

입력 배열 $x[n]$ 이 모두 실수이면 DFT 결과에는 또 하나의 대칭이 생긴다.

X[N-k]=\overline{X[k]}

즉 앞쪽의 $k$ 번째 주파수 값과 뒤쪽의 $N-k$ 번째 주파수 값은 켤레 복소수 짝이다. 켤레 복소수는 실수부가 같고 허수부의 부호만 반대이므로, 크기는 서로 같다.

이 성질은 “실수 코사인은 양의 방향 회전과 음의 방향 회전이 한 쌍으로 합쳐진 것”이라는 사실과 연결된다. 그래서 실수 데이터의 FFT 결과를 보면 앞쪽 절반과 뒤쪽 절반이 거울처럼 대응된다. 실전 라이브러리에서 실수 전용 FFT가 계산량과 메모리를 줄일 수 있는 이유도 이 대칭 덕분이다.

처음 배울 때는 이 최적화를 직접 구현하지 않아도 된다. 다만 결과의 절반이 나머지 절반과 독립적인 새 정보가 아니라는 점을 알면, DFT 그래프에서 왜 양쪽 막대가 함께 나타나는지 이해하기 쉽다.

직관 비유

시계 숫자를 생각하자. 12칸짜리 시계에서 3시와 9시는 정확히 반대 방향이다. 한쪽 방향을 알면 반대편은 “부호만 바뀐 방향”으로 바로 알 수 있다. 단위원근도 원 위에서 이런 짝을 이룬다.

예제

$N=4$ 일 때 네 점은 다음과 같다.

1,\quad -i,\quad -1,\quad i

기본 회전값은

\omega_4=e^{-2\pi i/4}=e^{-i\pi/2}=-i

이다. 거듭제곱하면

\omega_4^0=1,\quad \omega_4^1=-i,\quad \omega_4^2=-1,\quad \omega_4^3=i

가 된다. 여기서 $\omega_4^0$ 과 $\omega_4^2$ 는 서로 반대이고, $\omega_4^1$ 과 $\omega_4^3$ 도 서로 반대다.

\omega_4^{0+2}=-\omega_4^0,\qquad \omega_4^{1+2}=-\omega_4^1

손풀이 체크

$N=8$ 이면 단위원 위의 점은 몇 개일까?

답 보기
$8$ 개
$\omega_4$ 의 값은?

답 보기
$-i$
$\omega_N^{k+N/2}$ 는 $\omega_N^k$ 와 어떤 관계일까?

답 보기
방향이 반대이므로 $-\omega_N^k$ 이다.
실수 입력의 DFT에서 $X[N-k]$ 는 $X[k]$ 와 어떤 관계일까?

답 보기
켤레 복소수 짝이다.

다음으로 이어지는 생각

이제 짝수/홀수로 나눈 작은 DFT 결과를 단위원근의 대칭으로 합치면 FFT의 핵심 구조가 나온다.

단위원근과 대칭

단위원근과 대칭

핵심 질문

교과서 설명

원시 단위원근과 직교합

실수 신호에서 생기는 켤레 대칭

직관 비유

예제

손풀이 체크

다음으로 이어지는 생각

이번 장에서 기억할 3문장

C++로 확인하기