DFT 행렬과 직교

$X[0]$ 부터 $X[N-1]$ 까지의 내적 $N$ 개를 한꺼번에 쓰면 어떤 모양이 될까? 회전 $N$ 개를 한 행렬에 모으면, 서로 다른 회전이 직교한다는 것도 한눈에 보인다.

행렬로 쓰기

모든 $k$ 의 DFT를 한꺼번에 쓰면 행렬 곱이 된다. $\mathbf X=W\mathbf x$ 이고 $W[k,n]=e^{-j2\pi kn/N}$ 이다.

\mathbf X=\begin{bmatrix}X[0]\\X[1]\\\vdots\\X[N-1]\end{bmatrix},\qquad \mathbf x=\begin{bmatrix}x[0]\\x[1]\\\vdots\\x[N-1]\end{bmatrix}

W=\begin{bmatrix}1&1&\cdots&1\\1&w&\cdots&w^{N-1}\\\vdots&\vdots&\ddots&\vdots\\1&w^{N-1}&\cdots&w^{(N-1)^2}\end{bmatrix}

여기서 $w=e^{-j2\pi/N}$ 이다.

$\mathbf X$ 와 $\mathbf x$ 는 $N\times1$ 이고 $W$ 는 $N\times N$ 복소 행렬이다. 행은 주파수 $k$ , 열은 시간 $n$ 이다. 행 $k$ 는 앞 절의 회전 $e_k$ 에 켤레를 취한 것이다. 그래서 $X[k]$ 는 입력 $\mathbf x$ 와 행 $k$ 의 원소를 자리마다 곱해 더한 값, 곧 앞 절의 내적이다.

원소는 모두 4장에서 본 1의 $N$ 제곱근이고, 크기가 1이라 페이저 하나로 그릴 수 있다. 각이 $-2\pi kn/N$ 인 페이저를 원소 자리에 놓으면 행렬 전체가 페이저 그림이 된다.

행 $k$ 에서는 열을 하나 넘길 때마다 페이저가 $-2\pi k/N$ 씩 돈다. $N$ 개 샘플 동안 $k$ 바퀴 돈다.
행 0은 모든 페이저가 0을 가리키는 직류 성분이다. $N$ 이 짝수이면 행 $N/2$ 는 $+1,-1$ 을 번갈아 가리킨다.
$W[k,n]=W[n,k]$ 라 행렬은 대칭이다.

행 $N-k$ 는 행 $k$ 의 켤레이다.

\begin{aligned} W[N-k,n]&=e^{-j2\pi(N-k)n/N}\\ &=e^{j2\pi kn/N}=\overline{W[k,n]} \end{aligned}

두 행의 페이저는 같은 속도로 반대 방향으로 돈다. 그래서 bin $N-k$ 는 음의 주파수 $-k$ 를 나타낸다. $N=8$ 이면 행 2와 행 6이 한 쌍이다. 앞 절에서 본 실수 신호의 대칭 $X[N-k]=\overline{X[k]}$ 는 행렬에서 이 두 행의 관계로 보인다.

$N=8$ , 입력 $\mathbf x=[1,2,0,-1,0,0,0,0]^{\mathsf T}$ 이면 $\mathbf X=W\mathbf x$ 의 한 bin $X[1]$ 은 행 1의 페이저를 $x[n]$ 과 자리마다 곱해 더한 값이다. 열 $n$ 마다 페이저 $W[1,n]$ 에 $x[n]$ 을 곱해 늘이거나 뒤집고, 그 곱을 앞의 곱들 끝에 이어 붙이면 페이저 합의 끝이 $X[1]$ 이다. $x[n]=0$ 인 열은 더할 것이 없다. $x[n]$ 이 0이 아닌 자리는 $n=0,1,3$ 뿐이라 $X[k]=W[k,0]+2W[k,1]-W[k,3]$ 이고, 행 1에서는 $1\cdot1+2(0.707-j0.707)+(-1)(-0.707-j0.707)=3.121-j0.707$ 이다. 입력이 실수이므로 $X[8-k]$ 는 $X[k]$ 의 켤레이다.

위 줄은 입력 x[n], 오른쪽 열은 X[k], 복소평면의 화살표 하나는 곱 하나(지나간 곱은 흐리게 남는다)이고, 곱(주황)과 누적합(초록)은 그림, 표, 식에서 같은 색, 페이저 그림 면의 색은 페이저 방향을 한 번 더 나타낸다. 계산 표에는 열마다 W[k,n], x[n], 곱, 누적합이 소수 셋째 자리로 반올림되어 한 줄씩 남고, 곱과 합은 화면에 적힌 값끼리 계산하며 끝점 단계는 같은 자리까지 적은 정확한 값과 비교한다. 값은 반올림한 수로 이어서 계산하므로 정확한 값과 끝자리가 조금 다를 수 있다.

해 보기

행 2의 곱과 누적합을 따라가며 $X[2]$ 를 구하라.
관찰
행 2의 페이저는 열마다 −90°씩 돌아 $W[2,1]=-j$ , $W[2,3]=j$ 이다. 표의 곱은 $1$ , $2(-j)=-j2$ , $(-1)j=-j$ 이고, 누적합이 $1 \to 1-j2 \to 1-j3$ 으로 바뀌어 $X[2]=1-j3$ 이다.
행 6의 곱으로 $X[6]$ 을 구하고, 행 2와 비교하라.
관찰
$W[6,1]=j$ , $W[6,3]=-j$ 라 곱은 $1$ , $j2$ , $j$ 로 행 2의 곱의 켤레이다. 그래서 $X[6]=1+j3=\overline{X[2]}$ 이다. 행 6의 페이저는 행 2와 같은 속도로 반대 방향으로 돈다.
$N=4$ 에서 행 3의 곱으로 $X[3]$ 을 구하라.
관찰
입력이 $[1,2,0,-1]$ 이 되고 단계는 14개이다. 곱은 $1$ , $j2$ , $0$ , $j$ 이고 $X[3]=1+j3$ 이다. 아래 예제 1에서 $\mathbf X=[2,\;1-j3,\;0,\;1+j3]^{\mathsf T}$ 전체를 손으로 구한다.

행은 서로 직교한다

서로 다른 두 행은 직교한다. 앞 절에서 회전 하나를 입력으로 넣었을 때 본 성질을 행끼리 쓴 것이다.

\sum_{n=0}^{N-1}W[k,n]\,\overline{W[m,n]}=N\,\delta[k-m]

$\delta[k-m]$ 은 $k=m$ 일 때 1, 아닐 때 0이다. 같은 행끼리는 곱이 모두 1이라 합이 $N$ 이고, 다른 행끼리는 곱이 원 위에 고르게 놓여 합이 0이다.

행 $k=1$ 과 행 2의 내적도 같은 방식으로 계산한다. 열 $n$ 마다 행 2의 페이저 $W[2,n]$ 에 켤레를 취해 각의 부호를 바꾸고, 행 1의 페이저 $W[1,n]$ 과 곱해 각을 더한다. 그 곱 여덟 개를 이은 페이저 합의 끝이 내적이다. 행 1의 페이저는 열마다 −45°, 켤레를 취한 행 2의 페이저는 +90°씩 돌므로 곱의 페이저는 열마다 +45°씩 돈다. 그래서 곱은 원 위에 고르게 놓이고, 곱 여덟 개를 이은 페이저 합은 정팔각형을 그리며 원점으로 돌아와 내적이 0이다.

N = 8이고 그림의 '행 j'가 식의 m이며(식에서는 j가 허수 단위라 m을 쓴다), 페이저 그림의 윗줄은 행 1, 가운데 줄은 행 2의 켤레, 아랫줄은 두 페이저의 곱, 작은 단위원에 흐리게 남은 점은 지금까지 만든 곱, 복소평면의 끝점은 ⟨w₁, w₂⟩이다. 계산 표에는 열마다 두 페이저, 켤레, 곱, 누적합이 한 줄씩 남고, 곱(주황)과 누적합(초록)은 그림, 표, 식에서 같은 색이며, 값은 반올림한 수로 이어서 계산하므로 정확한 값과 끝자리가 조금 다를 수 있다.

해 보기

행 2, 열 1의 페이저가 켤레를 취하면 어디로 가는지 확인하라.
관찰
앞 단계에서 고른 행 2, 열 1의 페이저는 $1\times(-90^\circ)=-90^\circ$ , 곧 $W[2,1]=-j$ 이다. 켤레를 취하면 $90^\circ$ 가 되어 $\overline{W[2,1]}=j$ 이다. 다음 단계에서 곱의 각이 $-45^\circ+90^\circ=45^\circ$ 가 된다.
행 2와 행 6의 내적을 구하라.
관찰
곱이 열마다 180°씩 돌아 1과 −1이 번갈아 나온다. 페이저 합이 한 선분 위를 오가다 원점에서 멈춘다. 켤레 쌍도 서로 다른 두 행이라 직교한다.
행 2와 자기 자신의 내적을 구하라.
관찰
같은 행이라 켤레를 취한 페이저가 원래 페이저를 정확히 되돌려 곱이 모두 1이다. 페이저 합은 길이 8인 직선이고, 합은 N = 8이다.

켤레를 붙이지 않고 곱하면 결과가 달라진다. 행 2와 행 6처럼 반대로 도는 두 행은 곱이 모두 1이 되어 합이 $N$ 이 된다. 복소 회전의 직교를 재려면 켤레가 필요하다(4장 '켤레를 붙인 내적').

예제 1: 손으로 계산하는 N = 4 DFT

$N=4$ 이면 $w=e^{-j\pi/2}=-j$ 라 행렬 원소가 $1,-j,-1,j$ 뿐이다.

W_4=\begin{bmatrix}1&1&1&1\\1&-j&-1&j\\1&-1&1&-1\\1&j&-1&-j\end{bmatrix}

$\mathbf x=[1,\;2,\;0,\;-1]^{\mathsf T}$ 의 DFT를 행마다 구한다.

\begin{aligned} X[0]&=1+2+0-1=2\\ X[1]&=1+2(-j)+0\cdot(-1)+(-1)(j)=1-j3\\ X[2]&=1-2+0+1=0\\ X[3]&=1+2(j)+0\cdot(-1)+(-1)(-j)=1+j3 \end{aligned}

$X[0]$ 은 샘플의 합이고, 입력이 실수라 $X[3]=\overline{X[1]}$ 이다.