DFT: 회전과의 내적

샘플 $N$개가 있을 때, 그 안에 어떤 속도의 회전이 얼마나 들어 있는지 어떻게 잴까? 4장에서는 신호에 들어 있는 성분을 그 성분과의 내적으로 쟀다. DFT는 같은 계산을 샘플 $N$개에 쓴다.

샘플 N개와 회전 N개

DTFT는 수열을 더해 주파수가 연속인 함수를 내놓는다. 여기서 컴퓨터가 가진 것은 샘플 $N$개이다. DFT는 이 기록이 한 주기(시간으로 $NT_s$)로 반복된다고 보고 유도한다.

샘플 $N$개가 되풀이된다면 그 안의 회전도 $N$샘플 뒤에 처음 자리로 돌아와야 한다. 그렇지 않으면 한 주기가 끝나고 다음 주기가 시작하는 이음매에서 페이저가 갑자기 튄다. 그래서 쓸 수 있는 회전은 $N$샘플 동안 정확히 정수 바퀴를 도는 회전뿐이다. $N$샘플 동안 $k$바퀴를 도는 회전은 샘플마다 $\Omega_k=2\pi k/N$씩 돈다. $k=0,1,\ldots,N-1$로 서로 다른 회전이 $N$개 있다($k=N$은 $k=0$과 같은 수열이다).

$e_k$는 앞 절의 $e^{j\Omega n}$에서 $\Omega$를 $\Omega_k$로 둔 것이다. 주기 $2\pi$인 $\Omega$ 축을 $N$개 점으로 나눈 것과 같다.

내적으로 재기

4장에서 복소 신호의 내적은 둘째 신호에 켤레를 붙여 곱하고 적분한 값이었다. 수열에서는 적분 대신 합을 쓴다. 입력 $x[n]$과 회전 $e_k[n]$의 내적이 이산 푸리에 변환(discrete Fourier transform, DFT)이다.

지표가 둘이다. $n$은 시간 지표, $k$는 주파수 지표이고, 둘 다 $0,1,\ldots,N-1$이다. $N$은 샘플 수이다. 켤레 때문에 지수의 부호가 음수가 되고, DFT에서 곱하는 기준 회전은 시계 방향으로 돈다.

내적이 왜 성분을 재는지는 입력이 회전 하나일 때 보인다. $x[n]=e_m[n]$이면 곱은 $x[n]\overline{e_k[n]}=e^{j2\pi(m-k)n/N}$이다. $k=m$이면 곱이 모두 1이라 $X[m]=N$이다. $k\ne m$이면 단위원의 같은 자리를 반복해서 지날 수도 있지만 합은 0이다. 공비를 $r=e^{j2\pi(m-k)/N}$로 두면 $r^N=1$, $r\ne1$이므로 등비수열의 합은

이다. 그래서 $X[k]$는 입력에 회전 $e_k$가 얼마나 들어 있는지를 잰다. 서로 다른 두 회전의 내적이 0이라는 이 성질이 직교이다.

기록을 주기적으로 반복해서 보든 기록 밖을 0으로 두든, DFT는 같은 $N$개 값만 합하므로 $X[k]$는 같다. 기록 밖을 0으로 둔 수열의 DTFT를 $X_0(\Omega)$라고 하면

이다. DFT 값은 이 DTFT 곡선 위의 점이다. 한편 뒤에서 구할 역 DFT(IDFT)의 기저는 $e^{j2\pi k(n+N)/N}=e^{j2\pi kn/N}$이므로, 복원식을 기록 밖까지 이어 쓰면 $N$샘플마다 반복된다. 그래서 주기적으로 보는 해석도 자연스럽다.

$X[k]$는 $n=0$부터 곱을 한 항씩 더해 얻는다. 입력이 실수이면 곱 $p[n]=x[n]e^{-j\theta_n}$($\theta_n=2\pi kn/N$)은 실수 곱 두 번이다. 실수부는 $x[n]\cos\theta_n$, 허수부는 $-x[n]\sin\theta_n$이다. 복소평면에서 새 곱을 앞 곱의 끝에 이어 붙이면 마지막 끝점이 $X[k]$이다. 아래 그림의 계산 표에는 더한 샘플마다 $x[n]$, Re $p[n]$, Im $p[n]$과 두 누적합이 한 줄씩 남고, $\theta_n$이 $2\pi$ 이상이면 $2\pi$의 정수배를 뺀 값($0\le\theta_n<2\pi$)을 ≡ 뒤에 함께 적는다.

N = 8이고 입력은 한 주기의 코사인 x[n] = cos(2πn/8)이며, ①의 점 (n, cos θₙ, −sin θₙ)이 바닥과 뒷벽에 진 투영이 ②의 두 줄 cos θₙ(파랑)과 −sin θₙ(보라), ③의 파랑·보라 막대가 지금까지 더한 ΣRe와 ΣIm이다. ②의 세로 한 줄이 샘플 하나이고(넓은 화면에서는 x[n] 스템 옆에 샘플값을 적는다), 값은 반올림한 수로 이어서 계산하므로 정확한 값과 끝자리가 조금 다를 수 있다.

bin과 물리 주파수

$X[k]$ 하나가 차지하는 주파수 자리를 bin(주파수 bin)이라고 한다. bin $k$의 회전은 샘플마다 $2\pi k/N$을 돌고, 1초에 샘플이 $f_s$개 있다. 그래서 bin $k$는 물리 주파수 $f_k=k\,f_s/N$(Hz)에 해당하고, 주파수 간격은 $\Delta f=f_s/N$이다.

$k>N/2$인 bin은 음의 주파수 $(k-N)f_s/N$에 해당한다. 앞 절에서 본 대로 $2\pi-\Omega$는 $-\Omega$와 같은 회전이기 때문이다. $N$이 짝수이면 $k=N/2$는 따로 본다. 이 bin에서는 $+f_s/2$와 $-f_s/2$가 같은 샘플을 준다.

이 장의 $X[k]$는 $N$으로 나누지 않은 값이다. $X[0]$은 샘플의 합이고 평균은 $X[0]/N$이다. 진폭 1인 복소 지수가 bin $k$에 정확히 놓이면 $|X[k]|=N$이고, 진폭 1인 코사인은 $k$와 $N-k$에 $N/2$씩 나뉜다.

예를 들어 $\cos(\pi n/8)$은 16개 샘플마다 되풀이된다. $N=16$으로 한 주기를 DFT 하면 $\cos(2\pi\cdot1\cdot n/16)$이므로 $X[1]=X[15]=8$이고 나머지 bin은 0이다. FFT는 같은 DFT 값을 더 적은 계산으로 구하는 알고리즘이다.

실수 신호와 복소 신호

위 그림의 코사인은 bin 1에서 4를 주었는데, bin 7에서도 똑같이 4를 준다. 주파수가 하나뿐인 신호가 왜 두 bin에 서고, 복소 톤이면 어떻게 될까?

4장의 Euler 공식을 샘플에 쓰면 이유가 보인다. bin $k$의 코사인은 반대로 도는 두 회전의 합이다.

$e_{N-k}[n]=e^{-j2\pi kn/N}$은 $e_k$와 같은 속도로 반대 방향으로 도는 회전이다. 그래서 진폭 1인 코사인은 bin $k$와 bin $N-k$에 $N/2$씩 선다. 복소 톤 $e_k[n]$은 한 방향으로만 도는 회전 하나라서 bin $k$ 한 곳에만 $N$이 선다. 4장('복소 지수의 회전')에서도 φ = 0일 때 f의 부호를 바꾸면 점이 반대로 돌고, 코사인 투영은 그대로인 채 사인 투영의 부호만 바뀌었다. 코사인만 보아서는 도는 방향을 알 수 없다.

입력이 실수이면 두 bin의 값은 켤레이다. bin $N-k$의 회전은 bin $k$의 회전과 같은 속도로 반대 방향으로 돌고, 실수 $x[n]$은 켤레를 취해도 그대로이기 때문이다.

따라서 $|X[N-k]|=|X[k]|$이다. $X[0]$과 ($N$이 짝수일 때) $X[N/2]$는 실수이다. 첫째 줄에서 둘째 줄로 넘어갈 때 $\overline{x[n]}=x[n]$을 썼으므로, 입력이 복소수이면 이 대칭은 성립하지 않는다. 6장에서 연속 신호의 대칭 $X(-f)=\overline{X(f)}$가 허수부가 언제나 0인 신호에서만 성립한 것과 같은 이유이다.

N = 8, fₛ = 8 Hz, f = 1 Hz이고, 가로축은 bin k를 주파수 k·fₛ/N(k > N/2이면 (k − N)fₛ/N)으로 바꾼 것, 스템은 X[k]의 실수부(파랑)와 허수부(보라)이다. 그림 아래 줄은 붉은 점으로 표시한 bin 1의 값 X[1]과 그 크기, 위상이다.