[신호및시스템] Phase 3-2 - 이산 푸리에 변환

이산 푸리에 변환

“이산 푸리에 변환(Discrete Fourier Transform)”은 이산시간 푸리에 변환(Discrete Time Fourier Transform) 과 다른 컨셉이다. 이걸 기억해야한다.

ㅤ

기존의 이산시간 푸리에 변환은 “n개의 신호($x[n]$)를 바탕으로 연속된 주파수 함수 ($X(\Omega)$)를 만들어내는 과정”이다. 이산시간 푸리에 변환은 몇 가지 특징을 가진다.

• 주파수 범위가 0~$2\pi$ 이며, $X$ 는 주기가 $2\pi$ 인 주기함수이다.
• DTFT는 무한 길이 신호에 대해 정의된다. (유한 길이 신호의 경우 나머지 영역을 모두 신호가 0인 구간이라 생각해, 무한 길이 신호라고 여겨 변환할 수 있다)
• DTFT의 결과는 주파수 도메인에 대한 연속함수이기 때문에, 컴퓨터가 처리하기 어렵다.

ㅤ

그래서 컴퓨터가 조금 더 편하게 다룰 수 있도록 하기위해서 주파수 영역에 대해서도 Discrete 하게 값을 다루는 “이산 푸리에 변환”이 필요하다.

ㅤ

DTFT를 통해 얻은 연속 주파수를 이산 주파수로 변환하기 위해서는 주파수 값들을 샘플링 해야한다.

• N개의 신호로부터 주파수 함수가 유도되었음 (N개의 신호 특성을 가지고 있음) 그러므로, N개의 주파수를 샘플링하면 더도말고 덜도말고 딱 필요한 만큼의 주파수를 샘플링할 수 있다. (푸리에 변환에서부터 역변환 시 N개 이상의 정보가 있어야 원래 신호로 돌아올 수 있다)
• 연속 주파수의 주기가 $2\pi$ 이므로, 샘플링 간격은 $\frac{2\pi}{N}$ 로 하여 균등하게 추출할 수 있다.

ㅤ

기존의 이산시간 푸리에 변환의 수식은 다음과 같이 정의된다.

$$
X(\Omega) = \sum_{n=-\infty}^{\infty}x[n]e^{-j\Omega n}
$$

ㅤ

앞서 작성한 DFT 의 특성에 따라서 기존 DTFT 수식을 변형해주어야 한다.

• N개의 샘플링이 필요하다.
• 주파수 $\Omega$ 에 대해서, k 번째 샘플링의 주파수를 $\frac{2\pi}{N}k$ 로 대치하여 샘플링 간격을 나누기

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

ㅤ

좌변이 k 번째 푸리에 변환 함수값이므로 단순하게 $X_k$ 라고 표기하면 아래 수식을 만들 수 있다. 이 수식이 이산 푸리에 변환 수식이다.

$$
X_k = \sum_{n=0}^{N-1}x[n]\cdot e^{-j\frac{2\pi}{N}kn}
$$

ㅤ

잘 살펴보면, 우변의 수식이 이산시간 푸리에 계수와 형태가 비슷하다는 것을 파악할 수 있다.

$$
X_k =N\cdot a_k
$$

ㅤ

이산 푸리에 변환의 특징

앞서 언급했던 것처럼, 컴퓨터가 연속 데이터를 처리하기 어려우므로 컴퓨터가 연산에 활용할 수 있도록 푸리에 변환의 결과인 주파수 도메인의 함수값을 이산 데이터로 샘플링하는 것이 이산 푸리에 변환이다.

ㅤ

k 번째 샘플링된 주파수 $X_k$ 는 특정한 주파수 특징을 가진다.

• $X_0$ : 신호의 평균 (주파수가 0일 때)
• $X_1$ : 기본 주파수 성분 ($\frac{2\pi}{N}$ … 1배 주파수)
• $X_2$ : 2배 주파수 성분 ($2\frac{2\pi}{N}$ … 2배 주파수)
• $X_k$ : k배 주파수 성분 ($k\frac{2\pi}{N}$ … k배 주파수)

ㅤ

주파수의 범위가 0 ~ $2\pi$ 이긴 하지만, Discrete 에서 표현할 수 있는 최대 주파수는 $\pi$ 이다.

• 복소평면에서 복소지수가 1, -1, 1, -1 만 반복하는게 가장 빠른 진동임.
• 주기가 $2\pi$ 이기에 $\frac{3}{2}\pi$ 는 $-\frac{1}{2}\pi$ 와 동일함. 즉, $\pi$보다 큰 주파수는 음의 주파수 (위상이 반대로)임.
• 샘플링 되어있기 때문에, 더 빠르게 변하는 신호는 접혀서 느린 주파수의 신호로 보일 수 밖에 없음.
• 다만 주기가 $2\pi$니깐 주파수의 범위는 $2\pi$ 까지이다.

ㅤ

DFT Matrix

DFT 에서 k 번째 주파수를 뽑아내는 수식을 잘 보면, 신호에 곱해지는 항이 항상 비슷한 형태를 가진다는 것을 알 수 있다.

$$
X_k = \sum_{n=0}^{N-1}x[n]\cdot e^{-j\frac{2\pi}{N}kn}
$$

ㅤ

만약 위 수식이 의미하는 바를 동일하게 행렬의 곱 형태로 나타낸다면 아래처럼 표현할 수 있다. 식의 복잡성을 낮추기 위해 N=4 라고 하자. 각 행렬 항의 요소는 $(k, n)$ 에 대해서 $e^{-jk\frac{2\pi}{N}n}$ 이므로, 아래처럼 정리된다.

$$
\left[
\begin{matrix}
X_0\\ X_1\\X_2\\X_3
\end{matrix}
\right] = \left[
\begin{matrix}
e^{-j0\frac{2\pi}{N}0} & e^{-j0\frac{2\pi}{N}1} & e^{-j0\frac{2\pi}{N}2} & e^{-j0\frac{2\pi}{N}3}\\
e^{-j1\frac{2\pi}{N}0} & e^{-j1\frac{2\pi}{N}1} & e^{-j1\frac{2\pi}{N}2} & e^{-j1\frac{2\pi}{N}3}\\
e^{-j2\frac{2\pi}{N}0} & e^{-j2\frac{2\pi}{N}1} & e^{-j2\frac{2\pi}{N}2} & e^{-j2\frac{2\pi}{N}3}\\
e^{-j3\frac{2\pi}{N}0} & e^{-j3\frac{2\pi}{N}1} & e^{-j3\frac{2\pi}{N}2} & e^{-j3\frac{2\pi}{N}3}
\end{matrix}
\right]\cdot \left[
\begin{matrix}
x[0]\\ x[1]\\x[2]\\x[3]
\end{matrix}
\right]
$$

위 값을 계산해주면 아래 행렬처럼 만들 수 있다.

$$
\left[
\begin{matrix}
X_0\\ X_1\\X_2\\X_3
\end{matrix}
\right] = \left[
\begin{matrix}
1&1&1&1\\
1&-j&-1&j\\
1&-1&1&-1\\
1&j&-1&-j
\end{matrix}
\right]\cdot \left[
\begin{matrix}
x[0]\\ x[1]\\x[2]\\x[3]
\end{matrix}
\right]
$$

ㅤ

이렇게 만들어지는 행렬 곱을 위한 복소 지수로 구성된 행렬 항을 DFT Matrix 라고 부른다.

ㅤ

이렇게 연산을 미리 수행해 행렬 형태로 준비해두면 각 항을 매번 계산할 필요가 없어 빠르게 신호에 대한 연산이 가능하다. 또 서로 영향을 미치지 않기 때문에 병렬 연산의 적용 또한 가능해진다!

ㅤ

DFT Matrix를 조금 더 계산에 용이하도록 Unitary Matrix로 만들어주기 위해 모든 항에 $\frac{1}{\sqrt{N}}$ 을 추가해준다. 대신 우측항에 $\sqrt{N}$을 곱해서 이를 상쇄한다.

• Unitary Matrix : $U^H\cdot U = I$ 가 되는 행렬.
• Orthogonal Matrix의 복소수 버전으로, $H$ 연산은 (전치 + 복소 켤레 연산)을 의미한다.
• 아래 처럼 행렬을 변환하면 왼쪽의 DFT Matrix가 Unitary Matrix 로 만들 수 있다.

$$
\left[
\begin{matrix}
\frac{1}{\sqrt{N}}e^{-j0\frac{2\pi}{N}0} & \frac{1}{\sqrt{N}}e^{-j0\frac{2\pi}{N}1} & \cdots & \frac{1}{\sqrt{N}}e^{-j0\frac{2\pi}{N}(N-1)}\\
\frac{1}{\sqrt{N}}e^{-j1\frac{2\pi}{N}0} & & & \\
\cdots& & & \cdots\\
\frac{1}{\sqrt{N}}e^{-j(N-1)\frac{2\pi}{N}0} & \cdots & & \frac{1}{\sqrt{N}}e^{-j(N-1)\frac{2\pi}{N}(N-1)}
\end{matrix}
\right]\cdot \left[
\begin{matrix}
\sqrt{N} x[0]\\ \sqrt{N} x[1]\\\cdots\\ \sqrt{N} x[N-1]
\end{matrix}
\right]
$$

ㅤ

Unitary Matrix로 행렬을 준비해두면 역행렬과 관련해 장점이 있다.

• DFT 행렬을 $D$ 라고 할 때, 주파수로부터 다시 신호를 추출하기 위해서는 $D^{-1}$ 을 이용하면 된다. (역변환)
• 역행렬을 만드는 과정이 매우 간단하다. 변환 과정에서 메모리 절약 및 연산량을 크게 줄일 수 있다.
• IDFT를 위해 별도의 복잡한 알고리즘 불필요하여 효율적이다.

ㅤ

$$
X = Dx\\D^{-1}X = x
$$

ㅤ

샤라웃

혁펜하임의 “퍼펙트” 신호 및 시스템 (Signals & Systems)

혁펜하임의 “퍼펙트” 신호 및 시스템 (Signals & Systems)