Table of Contents
우리는 일상에서 다양한 형태의 신호를 접한다. 음악, 음성, 이미지 등은 모두 신호의 한 형태이며, 이를 효과적으로 분석하고 처리하기 위해서는 신호를 시간 영역뿐만 아니라 주파수 영역에서도 바라볼 필요가 있다. 주파수 영역에서 신호를 해석하면 내재된 패턴을 더욱 명확하게 분석할 수 있으며 필터링, 압축, 특성 추출과 같은 여러 신호 처리 기법을 적용할 수 있게된다.
그러나 컴퓨터에서 이 모든 과정을 처리하기 위해서는 시간 영역과 주파수 영역의 신호 모두 이산적인 값을 가져야 한다. 이 과정에서 주어진 이산 신호를 주파수 영역에서 분석하려면 이산 푸리에 변환(DFT)이 필요하다. 더 나아가, 연산량을 줄여 효율적으로 변환하는 방법인 고속 푸리에 변환(FFT)이 요구된다. 이번 글에서는 DFT가 무엇인지 그리고 FFT를 통해 연산량을 어떻게 줄였는지 살펴보려고 한다.
Discrete Fourier Transform
일반적인 푸리에 변환은 신호를 시간 영역에서 주파수 영역으로 변환하는 도구이다. 그러나 우리가 다루는 대부분의 신호는 디지털 신호이고, 이산적인 값들로만 표현된다. 문제는 이러한 이산 신호를 변환하더라도 주파수 영역에서는 여전히 연속적인 값을 갖는다는 점이다. 이를 해결하기 위해 등장한 것이 이산 푸리에 변환이다.
An example of discret-time Fourier transform (DTFT)
이산 신호의 주파수 변환을 수행할 때, 주파수 영역의 값도 연속적이라면 데이터를 완벽하게 분석할 수 없다. 하지만, 입력 신호가 주기성을 갖는다면 주파수 영역에서도 이산적인 값들만 존재한다. 즉, 주파수 영역에서도 특정 구간을 등간격으로 샘플링하게 되면, 유한 개의 값으로 주파수 정보를 표현해 낼 수 있다.
DFT는 이러한 개념을 기반으로 신호를 주파수 영역에서 고정된 개수의 점으로 샘플링하여 표현한다. 수식으로 DFT를 표현하면 다음과 같다:
\[X(\Omega)=\mathscr{F} \{ x[n] \}=\sum_{n=0}^{N-1} x[n] e^{-j\Omega n}\] \[X_M(\Omega)=X(k\Delta\Omega)=\sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{M}k n}, \quad k=0, 1, \dots, N-1\]주파수를 등간격으로 샘플링한다고 했는데, 몇 개의 값으로 샘플링해야할지 생각해봐야 한다. 주어진 신호가 길이 $N$이라면, DFT에서는 정확히 $N$개의 주파수 성분을 계산하게 된다. 그 이유는, 주어진 신호가 길이 $N$일 때 시간 영역의 표본 수가 $N$개 이므로, 주파수 영역에서도 동일한 개수의 정보를 유지하기 때문이다.
Twiddle factor
DFT의 핵심 개념 중 하나는 회전 인자(twiddle factor)이다. 이는 복소 평면에서 주파수 성분을 나타내는 요소로, 특정 주파수 성분을 계산할 때 회전하는 패턴을 갖는다. 회전인자는 다음과 같이 정의된다:
\[W_N^{kn} =e^{-j\frac{2\pi}{N}kn}\]이 회전 인자는 복소평면에서 $N$개의 점을 균등하게 나누어 배치한 형태로 볼 수 있으며, DFT 연산을 단순화하는 역할을 한다.
twiddle factor
Resolution
DFT를 통해 얻어진 주파수 성분들의 간격은 해상도(resolution)라고 하며, 이는 신호 속에 존재하는 주파수 성분을 얼마나 정밀하게 분석할 수 있는지를 나타낸다. DFT의 해상도는 다음과 같이 정의된다:
\[\Delta F = \frac{1}{N} \quad \text{or} \quad \Delta \Omega=\frac{2\pi}{N}\]조금 전 수식을 보면, DFT를 적용했을 때 twiddle factor의 배수에 해당하는 주파수 성분들만 검출하게 된다. 그 주파수 성분들을 더욱 세밀하게 검출하다보면 원래 신호가 가지고 있던 모든 주파수 성분들을 찾아낼 것이다. 즉, 분석할 수 있는 주파수 간격은 신호의 길이 $N$이 길수록 더욱 세밀해진다.
하지만, 만약 아날로그 신호 $x(t)$에서 디지털 신호 $x[n]$으로 변환할 때 충분한 샘플을 획득하지 못해 적은 $N$이 선정되었다면, 해상도를 높이기 위해 zero-padding을 추가해볼 수 있다. Zero-padding을 추가하면 더욱 세밀하게 주파수 대역을 살펴볼 수 있어 어느정도 보간의 효과를 줄 수 있다.
Circular convolution
DFT에서는 신호가 주기적으로 반복된다고 가정하기 대문에, 일반적인 컨볼루션을 그대로 적용하면 왜곡이 발생할 수 있다. 이를 해결하기 위해 등장한 개념이 원형 컨볼루션(Circular convolution)이다. 주기신호를 사용해 기존의 선형 컨볼루션을 적용하게 되면 값이 발산할 수도 있는 문제를 해결한다.
\[y[n]=\sum_{m=0}^{N-1} x[m]h[n-m]=x[n] \circledast h[n]\]원형 컨볼루션은 주기가 같은 신호에서만 진행이되며, 이를 시각화해서 나타내면 동심원을 통한 계산으로 볼 수 있다. 원형 컨볼루션은 일반적인 컨볼루션과 달리, 신호가 한 주기를 기준으로 회전하며 연산이 수행된다.
circular convolution
Fast Fourier Transform
DFT는 이산 시간 신호를 이산 주파수 영역에서 해석할 수 있는 강력한 변환도구 이지만, 연산량이 $\mathcal{O}(N^2)$ 만큼 요구된다는 단점이 있다. 신호의 길이가 길어질수록 계산 비용이 기하급수적으로 증가하기 때문에, 이를 효율적으로 계산하는 방법이 필요하다.
FFT는 DFT의 계산량을 획기적으로 줄이는 방법으로, 신호를 짝수와 홀수 인덱스로 나누어 재귀적으로 계산하는 방식을 사용한다. 이를 분할 정복(divide and conquer) 방식으로 접근하면 최종적으로 $\mathcal{O}(N \lg N)$의 연산량으롤 줄일 수 있다. FFT의 기본 아이디어는 다음과 같이 DFT 공식을 변형하는 것으로 시작한다.
문제는 $N$개의 샘플을 가진 신호를 절반씩 나누어 처리했기 때문에, 우리가 얻은 결과는 $N/2$ 크기의 변환 결과이다. 하지만 원래 신호의 길이는 $N$이므로, 전체 주파수 대역을 구성하려면 상위 절반의 주파수 성분도 고려해야 한다. 그렇기 때문에 $X[k + N/2]$ 도 계산해주어야 한다.
\[\begin{aligned} X[k] &= E[k]+e^{-j\frac{2\pi}{N}k}O[k] \\ X[k+N/2] &= E[k + N/2] + e^{-j\frac{2\pi}{N}(k+N/2)} O[k + N/2] \\ &= E[k] - e^{-j\frac{2\pi}{N}k} O[k] \end{aligned}\]
Summary
- DFT는 이산 시간 신호를 주파수 영역에서 이산적으로 표현하는 방법으로, DTFT에서 샘플링을 한 것과 같다.
- 회전 인자는 DFT를 계산하는데 사용되며, 해상도는 입력 신호의 길이 $N$에 따라 달라진다.
- 주기 신호에 대한 컨볼루션은 한 주기에 대해서만 컨볼루션을 하는 원형 컨볼루션을 적용한다.
- FFT는 DFT의 연산량을 크게 줄인 기법으로 분할-정복 방식을 활용한다.
Start the conversation