DFT의 세 얼굴

핵심 질문

같은 DFT 식을 왜 주파수 점수, 행렬 변환, 다항식 평가로 모두 볼 수 있을까?

교과서 설명

DFT에는 한 가지 공식이 있다.

X[k]=\sum_{n=0}^{N-1}x[n]e^{-2\pi i kn/N}

하지만 이 식은 세 가지 언어로 읽을 수 있다. 먼저 각 관점을 짧게 잡아 보자.

해석 관점: $X[k]=\sum x[n]e^{-2\pi i kn/N}$ 는 주파수 $k$ 와 얼마나 잘 맞는지 보는 점수다.

선형대수 관점: $X=Wx$ 는 푸리에 행렬에 의한 좌표 변환이다.

다항식 관점: $X[k]=A(\omega_N^k)$ 는 다항식을 단위원근에서 평가한 값이다.

세 줄은 서로 다른 계산이 아니다. 같은 계산을 어떤 목적에 맞춰 말하느냐만 다르다.

1. 해석: 주파수별 점수

가장 먼저 익숙해져야 할 얼굴은 점수표다.

X[k]=\sum_{n=0}^{N-1}x[n]e^{-2\pi i kn/N}

$k$ 를 하나 고정하면, DFT는 모든 샘플 $x[n]$ 에 검사 회전값을 곱해 더한다. 신호가 그 $k$ 번 회전과 잘 맞으면 항들이 비슷한 방향으로 쌓여 큰 값이 남는다. 잘 맞지 않으면 여러 방향으로 흩어져 서로 지워진다.

그래서 이 관점에서는 $X[k]$ 를 이렇게 읽는다.

X[k]\approx \text{주파수 }k\text{가 신호 안에 얼마나 들어 있는지 보는 점수}

이 설명은 DFT 실험실에서 막대그래프를 볼 때 가장 직접적으로 쓰인다. 막대가 크면 그 주파수 번호가 강하게 보인다는 뜻이다.

2. 선형대수: 좌표 변환

이번에는 같은 식을 행렬 곱셈으로 묶어 보자. DFT 쪽 회전값을

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

라고 두면

X[k]=\sum_{n=0}^{N-1}x[n]\omega_N^{kn}

이다. 여기서 $W$ 라는 행렬을

W_{k,n}=\omega_N^{kn}

로 만들면 모든 $k$ 에 대한 식을 한 줄로 쓸 수 있다.

X=Wx

이 말은 DFT가 입력 배열 $x$ 를 푸리에 행렬 $W$ 로 곱해 새로운 좌표 $X$ 로 바꾸는 계산이라는 뜻이다. 원래 좌표에서는 시간이나 위치 번호 $n$ 으로 신호를 본다. 바뀐 좌표에서는 주파수 번호 $k$ 별 성분으로 신호를 본다.

좌표 변환이라는 말이 어렵다면, 같은 물체를 다른 눈금자로 재는 것이라고 생각해도 된다. 원래 배열은 “몇 번째 샘플 값인가?”라는 눈금이고, DFT 결과는 “몇 번 회전하는 파동 성분인가?”라는 눈금이다.

이 관점이 중요한 이유는 역변환 때문이다. 푸리에 행렬의 서로 다른 행들은 한 주기 동안 서로 직교한다. 그래서 모든 $X[k]$ 를 알고 있으면 다시 원래 $x[n]$ 으로 돌아올 수 있다.

3. 다항식: 단위원근에서 평가

마지막 얼굴은 다항식이다. 배열 $x[0],x[1],\dots,x[N-1]$ 을 다항식의 계수로 놓자.

A(z)=x[0]+x[1]z+x[2]z^2+\cdots+x[N-1]z^{N-1}

이제 $z$ 자리에 $\omega_N^k$ 를 넣으면

\begin{aligned} A(\omega_N^k) &=x[0]+x[1]\omega_N^k+x[2](\omega_N^k)^2+\cdots+x[N-1](\omega_N^k)^{N-1}\\ &=\sum_{n=0}^{N-1}x[n]\omega_N^{kn}\\ &=X[k] \end{aligned}

즉 DFT는 계수 배열로 저장된 다항식 $A(z)$ 를 단위원 위의 점

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

에서 차례로 평가한 값들의 모음이다.

이 관점은 다음 장부터 중요해진다. 다항식을 곱할 때는 계수끼리 직접 섞는 계산이 복잡하지만, 여러 점에서의 값으로 바꾸면 같은 점에서 값끼리 곱하면 된다. FFT가 다항식 곱셈에 쓰이는 이유가 여기서 시작된다.

세 관점을 언제 쓰면 좋을까?

DFT 결과 그래프를 읽을 때는 첫 번째 얼굴, 즉 주파수 점수 관점이 가장 편하다. “어느 막대가 큰가?”를 보는 상황이다.

역 DFT, 직교성, 정보가 사라지지 않는 이유를 설명할 때는 두 번째 얼굴, 즉 행렬에 의한 좌표 변환 관점이 편하다.

FFT로 다항식 곱셈이나 합성곱을 빠르게 계산하는 이유를 설명할 때는 세 번째 얼굴, 즉 다항식 평가 관점이 편하다.

정리하면 DFT를 새 공식 세 개로 외우는 것이 아니다. 하나의 식을 상황에 맞게 세 문장으로 번역하는 것이다.

작은 예제

$N=4$ 이고

x=[1,2,0,0]

라고 하자. 이 배열을 다항식 계수로 보면

A(z)=1+2z

이다. 여기서 $\omega_4=e^{-2\pi i/4}=-i$ 이므로

X[1]=A(\omega_4)=1+2(-i)=1-2i

이다. 같은 값을 주파수 점수 관점으로 쓰면

X[1]=\sum_{n=0}^{3}x[n]e^{-2\pi i n/4}

이고, 행렬 관점으로는 $X=Wx$ 의 두 번째 행과 $x$ 를 곱한 결과다. 계산값은 모두 같다.

손풀이 체크

$X[k]=\sum x[n]e^{-2\pi i kn/N}$ 을 점수 관점으로 읽으면 무엇을 보는 것일까?

답 보기
주파수 $k$ 와 신호가 얼마나 잘 맞는지 보는 점수다.
$X=Wx$ 에서 $W$ 는 어떤 역할을 할까?

답 보기
시간/위치 좌표의 배열 $x$ 를 주파수 좌표의 배열 $X$ 로 바꾸는 푸리에 행렬이다.
$A(z)=x[0]+x[1]z+\cdots+x[N-1]z^{N-1}$ 라면 $X[k]$ 는 다항식 관점에서 무엇일까?

답 보기
$A(\omega_N^k)$ , 즉 다항식을 $k$ 번째 단위원근에서 평가한 값이다.

다음으로 이어지는 생각

이제 세 번째 얼굴을 자세히 보자. 다항식을 계수 배열로 저장한다는 말부터 정리하면, DFT가 왜 빠른 곱셈으로 이어지는지 볼 수 있다.