DFT의 생각

핵심 질문

신호 안에 어떤 주파수가 들어 있는지 어떻게 찾을 수 있을까?

교과서 설명

DFT는 길이 $N$ 인 신호 $x[n]$ 을 주파수 성분 $X[k]$ 로 바꾼다.

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

1. $k$ 번호는 무엇을 뜻할까?

$N$ 은 샘플 개수, $n$ 은 샘플 번호, $k$ 는 검사하는 주파수 번호다. 오른쪽의 $e^{-2\pi i kn/N}$ 은 복소평면에서 도는 회전 손잡이다.

$k$ 는 $N$ 개 샘플을 한 묶음으로 보았을 때 검사 파동이 그 안에서 몇 바퀴 도는지 세는 번호다. $k=0$ 은 돌지 않는 상수 성분, $k=1$ 은 한 바퀴, $k=2$ 는 두 바퀴를 뜻한다. 뒤쪽 번호는 반대 방향 회전처럼 볼 수 있다. 예를 들어 $N$ 개 중 $N-k$ 번은 $k$ 번 도는 파동의 반대 방향 짝이다.

여기에는 중요한 약속이 숨어 있다. DFT는 길이 $N$ 인 유한 배열을 한 주기로 반복한다고 약속하고, 그 한 주기 안에서 정수 번 회전하는 파동들과 비교한다. 이 말은 원래의 연속 신호가 실제로 영원히 반복된다고 단정하는 것이 아니다. 다만 지금 손에 든 $N$ 개의 표본만으로 계산할 때, 양끝을 원형으로 이어 붙인 주기 신호처럼 다루겠다는 뜻이다. 그래서 $k=1$ 은 이 한 주기 안에서 정확히 한 바퀴, $k=2$ 는 정확히 두 바퀴 도는 기준이 된다. 이 원형 해석은 뒤에서 길이를 고정한 DFT 곱셈이 순환 합성곱으로 나타나는 이유와도 연결된다.

여기서 기본 회전값을 $\omega_N=e^{-2\pi i/N}$ 라고 쓰면 DFT 식은 더 짧아진다.

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

이 장에서는 먼저 이 식을 “주파수별 점수”로 읽는다. 행렬과 다항식으로 보는 관점은 다음 장에서 한 번에 정리한다. 지금은 $k$ 를 하나 고정하고, 모든 샘플 $x[n]$ 을 검사 회전값과 곱해 더한다고 생각하면 된다.

2. 검사 회전값을 곱해 더하기

각 항은 다음처럼 볼 수 있다.

x[n]e^{-2\pi i kn/N}

즉, $x[n]$ 이라는 막대 하나를 복소평면 위의 작은 벡터로 바꾼다. 그 벡터들을 모두 더했을 때 크게 남으면 그 $k$ 주파수가 신호 안에 강하게 들어 있다는 뜻이다.

3. 복소 내적에서는 왜 켤레를 쓸까?

조금 더 수학적으로 말하면, DFT는 신호와 검사 파동을 비교하는 복소 내적처럼 볼 수 있다. 실수 배열에서는 같은 위치끼리 곱해 더하지만, 복소수에서는 검사 파동의 켤레를 곱해 방향을 맞춰 비교한다. 그래서 반대 방향 회전값 $e^{-2\pi i kn/N}$ 이 식에 들어간다고 이해할 수 있다.

검사 파동을

v_k[n]=e^{2\pi i kn/N}

라고 두면, 그 켤레는 $\overline{v_k[n]}=e^{-2\pi i kn/N}$ 이다. 따라서 DFT는

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

로 쓸 수 있다. 즉 $X[k]$ 는 신호 $x$ 를 $k$ 번째 기본 파동 방향으로 비추어 본 점수다. 이 자료의 정규화에서는 기본 파동의 길이 제곱이 $N$ 이므로, 실제 좌표 계수처럼 읽으려면 보통 $\frac{X[k]}{N}$ 이 나타난다.

복소 내적이 낯설다면 “검사 파동을 다시 기준 방향으로 돌려 놓고 더한다”고 생각하면 된다. 신호가 실제로 $k$ 번째 기본 파동과 같은 방향이라면 각 샘플은 대략

x[n]\approx c\,v_k[n]

꼴이다. 여기에 검사 파동의 켤레를 곱하면

x[n]\overline{v_k[n]}\approx c\,v_k[n]\overline{v_k[n]}=c

가 된다. 단위원 위의 복소수는 길이가 $1$ 이므로 $v_k[n]\overline{v_k[n]}=|v_k[n]|^2=1$ 이기 때문이다. 따라서 맞는 주파수에서는 여러 항이 같은 방향으로 쌓이고, 맞지 않는 주파수에서는 항들의 방향이 계속 달라져 서로 지워진다.

조금 더 천천히 말하면, 켤레는 검사 파동의 회전을 거꾸로 돌리는 장치다. 신호가 정말 $v_k$ 방향으로 돌고 있었다면 $\overline{v_k}$ 를 곱하는 순간 그 회전이 멈춘 것처럼 같은 방향 값들이 남는다. 반대로 맞지 않는 주파수라면 거꾸로 돌려도 여전히 여러 방향으로 흩어지므로 합이 작아진다.

작은 예로 $N=4$ , $k=1$ 이면 검사 파동은

v_1=[1,i,-1,-i]

이고 켤레는

\overline{v_1}=[1,-i,-1,i]

이다. 신호 $x=[1,0,-1,0]$ 와 비교하면

X[1]=1\cdot1+0\cdot(-i)+(-1)\cdot(-1)+0\cdot i=2

가 되어 점수가 남는다. 반대로 맞지 않는 검사 파동을 쓰면 양수와 음수, 서로 다른 회전 방향이 섞여 합이 작아진다.

4. 선형성과 행렬 관점

중요한 성질: 선형성

DFT는 더하기와 상수배를 보존한다. 두 신호 $a[n]$ , $b[n]$ 의 DFT를 각각 $A[k]$ , $B[k]$ 라고 하면
$\operatorname{DFT}(a+b)[k]=A[k]+B[k]$
상수 $c$ 에 대해서도
$\operatorname{DFT}(ca)[k]=cA[k]$
즉 신호를 더한 뒤 DFT한 결과는 각각 DFT한 결과를 더한 것과 같다. 여러 파동을 더한 신호에서 여러 주파수 막대가 함께 나타나는 이유도 이 성질과 잘 맞는다.

선형성은 합 기호의 분배법칙에서 바로 나온다. 예를 들어 $a+b$ 의 DFT를 계산하면

\begin{aligned} \operatorname{DFT}(a+b)[k] &=\sum_{n=0}^{N-1}(a[n]+b[n])\omega_N^{kn}\\ &=\sum_{n=0}^{N-1}a[n]\omega_N^{kn} +\sum_{n=0}^{N-1}b[n]\omega_N^{kn}\\ &=A[k]+B[k] \end{aligned}

이다. 상수배도 같은 방식으로

\operatorname{DFT}(ca)[k] =\sum_{n=0}^{N-1}ca[n]\omega_N^{kn} =cA[k]

가 된다.

심화 관점으로는 DFT를 행렬 곱셈으로도 볼 수 있다. 이 문단은 지금 완전히 이해하지 못해도 뒤의 FFT 흐름을 따라가는 데 큰 문제는 없다. $W$ 를

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

로 정의하면

X=Wx

이다. 역 DFT가 가능한 이유는 이 행렬의 행들이 서로 직교하기 때문이다. 더 정확히는 $W^{-1}$ 이 거의 켤레전치 행렬과 같고, 크기를 맞추기 위해 $\frac1N$ 이 붙는다.

W^{-1}=\frac{1}{N}\overline{W}^{\,T}

5. 크기, 위상, 실제 진폭 읽기

$X[k]$ 는 보통 복소수다. 그래서 두 가지 정보를 가진다.

|X[k]|=\sqrt{\operatorname{Re}(X[k])^2+\operatorname{Im}(X[k])^2}

$|X[k]|$ 는 그 주파수가 얼마나 강한지를 나타내고, $X[k]$ 의 방향 각도는 그 주파수가 어디서 시작했는지를 나타낸다. 이 시작 위치 정보를 위상이라고 부른다.

다만 $|X[k]|$ 가 항상 원래 사인파의 진폭과 바로 같은 것은 아니다. 이 자료의 정의에서는 DFT에는 $\frac{1}{N}$ 을 붙이지 않으므로, 값의 크기는 샘플 개수 $N$ 의 영향을 받는다. 또 실수 신호의 코사인 성분은 보통 $k$ 와 $N-k$ 의 켤레복소수 짝으로 나뉘어 나타난다. 처음에는 정확한 진폭 환산보다 “어느 막대가 상대적으로 큰가”를 먼저 보자.

주의: DFT 크기와 실제 진폭은 다르다

이 자료의 약속에서는 DFT 쪽에 $\frac{1}{N}$ 을 붙이지 않는다. 그래서 같은 진폭의 파동이라도 샘플 개수 $N$ 이 커지면 $|X[k]|$ 도 커질 수 있다. 실수 코사인은 보통 $k$ 와 $N-k$ 두 칸에 나뉘므로, 일반적인 코사인 진폭은 $A=\frac{2|X[k]|}{N}$ 처럼 환산해서 읽는다. $k=0$ 평균 칸과 짝수 $N$ 의 Nyquist 칸은 예외다.

실수 신호의 스펙트럼을 조금 더 정확히 읽으려면 앞쪽 막대와 뒤쪽 막대를 한 쌍으로 보아야 한다. 예를 들어 길이 $N$ 인 배열 안에 정확히 $k_0$ 번 도는 코사인 하나만 있다고 하자.

x[n]=A\cos\left(\frac{2\pi k_0 n}{N}\right)

오일러 공식으로 코사인을 두 방향 회전의 평균으로 쓸 수 있다.

\cos\theta=\frac{e^{i\theta}+e^{-i\theta}}{2}

그래서 진폭 $A$ 는 보통 $k_0$ 와 $N-k_0$ 두 칸에 반씩 나뉘어 나타난다.

|X[k_0]|=\frac{AN}{2},\qquad |X[N-k_0]|=\frac{AN}{2}

따라서 $k_0$ 가 $0$ 도 아니고, 아래에서 말할 Nyquist 칸도 아니라면 코사인의 진폭은 대략 다음처럼 읽을 수 있다.

A=\frac{2|X[k_0]|}{N}

예를 들어 $N=8$ 이고 $x[n]=2\cos\left(\frac{2\pi\cdot2n}{8}\right)$ 이면 진폭은 $A=2$ 이다. 이때 $|X[2]|=|X[6]|=\frac{2\cdot8}{2}=8$ 이 된다.

실수 신호에서는 이 두 칸이 항상 서로 짝을 이룬다. 수식으로는

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

이다. 켤레복소수는 크기가 같고 허수부 부호만 반대이므로, 실수 신호의 스펙트럼은 앞쪽 절반과 뒤쪽 절반이 거울처럼 대응된다.

예외도 있다. $k=0$ 은 평균 성분이라 짝이 따로 없다. 이때는

\text{평균}=\frac{X[0]}{N}

으로 읽는다. 또 $N$ 이 짝수일 때 $k=\frac{N}{2}$ 는 Nyquist 칸이라고 부르는 특수한 칸이다. 이 파동은 한 칸마다 부호가 바뀐다.

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

$k=\frac{N}{2}$ 는 자기 자신이 반대 방향 짝이므로 두 칸으로 나뉘지 않는다. 그래서 이 칸의 크기는 일반적인 코사인 쌍처럼 두 배해서 읽지 않는다.

6. 역 DFT로 되돌리기

DFT는 정보를 버리는 계산이 아니다. 모든 $X[k]$ 를 알고 있으면 원래 신호로 되돌릴 수 있다.

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

이 식을 역 DFT라고 한다. DFT의 지수에는 $-$ 가 있고, 역 DFT에는 $+$ 가 있다는 점을 기억해 두자.

왜 되돌릴 수 있을까? 핵심은 서로 다른 검사 회전들이 한 바퀴 동안 서로 지워진다는 성질이다. $k,\ell$ 이 $0$ 부터 $N-1$ 사이의 번호일 때 다음이 성립한다.

\sum_{n=0}^{N-1}\omega_N^{(k-\ell)n} = \begin{cases} N,& k=\ell\\ 0,& k\ne \ell \end{cases}

같은 주파수끼리는 모든 항이 같은 방향으로 쌓여 $N$ 이 되고, 다른 주파수끼리는 원 위를 고르게 돌아 합이 $0$ 이 된다. 그래서 역 DFT에서 모든 $X[k]$ 를 다시 섞으면 맞는 성분만 남고, 마지막에 $\frac{1}{N}$ 을 곱해 원래 크기로 되돌린다.

역 DFT가 실제로 원래 값을 되돌리는 과정도 한 번 펼쳐 보자. 복원한 값을 $\hat{x}[n]$ 이라고 쓰면

\begin{aligned} \hat{x}[n] &=\frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{2\pi i kn/N}\\ &=\frac{1}{N}\sum_{k=0}^{N-1} \left(\sum_{t=0}^{N-1}x[t]e^{-2\pi i kt/N}\right)e^{2\pi i kn/N}\\ &=\sum_{t=0}^{N-1}x[t]\left(\frac{1}{N}\sum_{k=0}^{N-1}e^{2\pi i k(n-t)/N}\right) \end{aligned}

괄호 안의 합은 $n=t$ 일 때만 $1$ 이 되고, $n\ne t$ 일 때는 $0$ 이 된다. 즉 다른 위치에서 온 성분은 직교합 때문에 사라지고, $t=n$ 인 항만 남는다.

\hat{x}[n]=x[n]

그래서 DFT는 단순히 “정보를 요약해서 버리는 계산”이 아니라, 서로 직교하는 회전 기준으로 좌표를 바꾸었다가 다시 원래 좌표로 돌아올 수 있는 변환이다.

직관 비유

친구들이 같은 박자로 박수를 치면 소리가 크게 들린다. 서로 다른 박자로 치면 소리가 섞여서 잘 들리지 않는다. DFT는 각 박자에 맞춰 봤을 때 얼마나 잘 맞는지를 재는 과정이다.

예제

상수 신호는 변화가 없으므로 $k=0$ 성분이 크다.

x=[1,1,1,1]\quad\Rightarrow\quad X[0]=4

이번 챕터의 실험실에서는 길이 $8$ 인 신호를 사용한다.

x[n]=\cos\left(\frac{2\pi\cdot2n}{8}\right)

그래서 $k=2$ 가 잘 맞는다. 실수 신호에서는 반대 방향 회전 짝도 같이 나타나므로 $k=6$ 도 크게 보인다.

여기서 $N=8$ 이므로 $k=6$ 은 $8-2$ 이다. 이것은 $2$ 바퀴를 반대 방향으로 도는 검사 파동처럼 읽을 수 있다.

이때 $X[2]$ 와 $X[6]$ 은 켤레복소수 짝으로 나타난다. 크기는 같고, 회전 방향 정보는 반대로 들어 있다.

신호가 여러 기본 파동의 합이면 DFT 점수표에서도 여러 막대가 동시에 커진다. 예를 들어

x[n]=2\cos\left(\frac{2\pi n}{N}\right)+\sin\left(\frac{4\pi n}{N}\right)

는 $k=1$ 계열과 $k=2$ 계열이 함께 섞인 신호다. DFT는 “가장 큰 하나”만 찾는 도구가 아니라, 각 $k$ 가 얼마나 들어 있는지 모두 재는 점수표다.

다만 실제 신호가 항상 정수 번호 $k$ 에 딱 맞는 것은 아니다. 길이 $N$ 인 관측 구간 안에서 2.5바퀴 도는 파동을 잘라 보면, DFT가 검사하는 $k=2$ 나 $k=3$ 어느 한쪽과도 완전히 일치하지 않는다. 이때 에너지가 한 막대에만 모이지 않고 주변 여러 $k$ 로 퍼져 보이는데, 이를 스펙트럼 누설 또는 leakage라고 부른다.

누설이 생기는 이유는 DFT가 $N$ 개의 샘플을 한 주기로 반복한다고 약속하기 때문이다. 관측 구간 안에 2.5바퀴만 들어 있으면, 마지막 샘플 뒤에 같은 배열을 다시 붙일 때 끝점과 시작점이 매끄럽게 이어지지 않는다. 그래프를 반복해서 붙인 그림에는 갑작스러운 꺾임이 생기고, 이런 꺾임은 여러 주파수를 섞어야 표현된다. 따라서 “파동 하나면 막대 하나”라고 외우기보다, 관측 구간 안에 정수 개의 주기가 딱 들어올 때 가장 깨끗하게 한두 막대가 선명해진다고 이해해야 한다.

아주 작은 예시로 $N=4$ 에서 한 칸만 직접 계산해 보자.

x=[1,0,-1,0]

$k=1$ 일 때는 다음 합을 계산한다.

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

각 항을 표로 쓰면 이렇다.

\begin{array}{c|cccc} n&0&1&2&3\\ \hline x[n]&1&0&-1&0\\ e^{-2\pi i n/4}&1&-i&-1&i\\ x[n]e^{-2\pi i n/4}&1&0&1&0 \end{array}

따라서 $X[1]=2$ 이다. 직접 한 칸을 계산해 보면 DFT가 “검사 회전값을 곱해 더하는 점수”라는 뜻이 더 선명해진다.

정규화 위치는 책마다 조금 다를 수 있다. 이 자료에서는 DFT에는 $\frac{1}{N}$ 을 붙이지 않고, 역 DFT에만 $\frac{1}{N}$ 을 붙인다. 어떤 책은 DFT와 역 DFT에 $\frac{1}{\sqrt{N}}$ 씩 나누기도 한다.

눈으로 확인하는 순서

복소평면 화면에서는 각 항 $x[n]e^{-2\pi i kn/N}$ 을 벡터로 본다.

파동 비교 화면에서는 원래 신호와 검사 파동을 같은 좌표평면에 겹쳐 본다.

벡터 합 화면에서는 벡터들을 꼬리물기로 이어 붙여 $X[k]$ 가 어디에 도착하는지 작도한다.

주파수 점수표에서는 모든 $k$ 의 $|X[k]|$ 를 막대로 비교한다.

3D 지형 화면에서는 검사 주파수와 위상을 조금씩 바꿨을 때 점수가 어떤 모양을 만드는지 본다.

손풀이 체크

$x=[1,1,1,1]$ 일 때 $X[0]$ 은?

답 보기
$1+1+1+1=4$
$x=[1,0,-1,0]$ 일 때 위 예시처럼 $X[1]$ 은?

답 보기
$2$
$|3+4i|$ 가 DFT 결과의 크기라면 값은?

답 보기
$5$
$N=8$ 이고 $x[n]=2\cos\left(\frac{2\pi\cdot2n}{8}\right)$ 이면 큰 막대는 어느 칸에 나타나고, 각 크기는 얼마일까?

답 보기
$k=2$ 와 $k=6$ 에 나타나며, 각 크기는 $\frac{2\cdot8}{2}=8$ 이다.

다음으로 이어지는 생각

DFT 결과를 이용하면 다항식과 배열 곱셈도 빠르게 계산할 수 있다. 그 전에 같은 DFT 식을 점수, 행렬, 다항식이라는 세 언어로 한 번 묶어 보자.

DFT의 생각

DFT의 생각

핵심 질문

교과서 설명

1. $k$ 번호는 무엇을 뜻할까?

2. 검사 회전값을 곱해 더하기

3. 복소 내적에서는 왜 켤레를 쓸까?

4. 선형성과 행렬 관점

5. 크기, 위상, 실제 진폭 읽기

6. 역 DFT로 되돌리기

직관 비유

예제

눈으로 확인하는 순서

손풀이 체크

다음으로 이어지는 생각

이번 장에서 기억할 3문장

C++로 확인하기

DFT의 생각

핵심 질문

교과서 설명

1. kkk 번호는 무엇을 뜻할까?

2. 검사 회전값을 곱해 더하기

3. 복소 내적에서는 왜 켤레를 쓸까?

4. 선형성과 행렬 관점

5. 크기, 위상, 실제 진폭 읽기

6. 역 DFT로 되돌리기

직관 비유

예제

눈으로 확인하는 순서

손풀이 체크

다음으로 이어지는 생각

이번 장에서 기억할 3문장

C++로 확인하기

1. $k$ 번호는 무엇을 뜻할까?