DFT는 데이터 분석 및 알고리즘 개발에 가장 흔히 사용되는 알고리즘 중 하나이다. 본 포스팅에서는 DFT의 기초적인 이론이나 주요 특성 등을 다루지 않는다. 학교를 졸업한 지 오래되서인지 개발을 하다보면 아주 기본적인 내용임에도 불구하고 부호가 헷갈린다거나 하는 등의 이유로 수식을 몇 줄 끄적이게 되는 경우가 있는데 이런 몇 가지 경우에 대하여만 간략히 메모를 남긴다.

참고로 본 포스팅에서는 FFT와 DFT의 용어를 혼용하여 사용한다. (둘의 출력이 같기 때문에 논리의 전개에 큰 무리가 없다.)

본 포스팅의 일부 내용은 아래 링크의 강의 노트를 참고하였다.
https://eeweb.engineering.nyu.edu/iselesni/EL713/zoom/dftprop.pdf

FFT and Inverse FFT (IFFT)

이 글을 읽는 사람이라면 FFT는 푸리에 변환이고, IFFT는 역푸리에 변환이라는 사실 정도는 잘 알고 있을 것이다. 그렇다. 내가 굳이 여기서 이 사실을 한 번 더 강조하려는 것은 아니다. 아래 내용을 이해하는데 있어 FFT와 IFFT의 출력이 어떻게 다른지 이해하면 도움이 되기 때문에 노파심에 이 장을 추가하였다. 아주 자세한 설명은 생략한다. 이해가 되지 않으면 DFT와 IDFT의 정의식으로부터 왜 이런 결론이 도출되는지 곰곰이 생각해보면 될 것이다.

• FFT와 IFFT는 복소평면에서 서로 반대되는 방향으로의 위상회전 속도를 측정한다.

• FFT는 시계방향으로의 위상회전 속도(즉, 각속도)를 discrete하게 변경해가며 입력신호 $x[n]$에 해당 각속도로 회전하는 성분이 얼마나 있는지를 내적을 통해 측정한다. 반면, IFFT는 반시계방향으로의 FFT 변환을 하는 것과 같다.

• 앞에서 말한 위상의 회전 속도, 즉 각속도는 샘플 간 위상의 변화량이므로 aliasing-free 조건에서 최대 $\pm\pi$ 범위 내에서 표현된다. 그렇기 때문에 FFT(IFFT)의 출력스펙트럼 범위가 $\pm \pi$인 것이다.

• 30도, 60도, 90도와 같이 위상이 변하는 신호가 있을 때, 우리가 FFT와 IFFT에게 위상회전 간격이 얼마냐고 물어본다면 FFT는 +30도 간격으로 회전한다고 대답할 것이고, IFFT는 -30도 간격으로 회전한다고 대답할 것이다. 따라서, FFT는 +30도 위치에 피크를 생성하는 반면, IFFT는 -30도 위치에 피크를 생성한다.

• 즉, 동일한 입력 신호에 대하여 FFT의 출력과 IFFT의 출력은 scale을 제외하면 0번째 bin을 제외하고는 서로 뒤집힌 형태(즉, time-reversed 형태)와 같다. 예를 들면, 다음과 같다.

  $\begin{aligned} & \mathbf{x} \xrightarrow{\text{FFT}} \ [X(0), \ X(1), \ X(1),\ \cdots, \ X(N-1)] \\ & \mathbf{x} \xrightarrow{\text{IFFT}} [X(0), \ X(N-1), \ X(N-2),\ \cdots, \ X(1)]/N \end{aligned}$

• 위 식의 관계를 일반화하여 다음과 같이 쓸 수 있다.

  $X_{FFT}[k] = X_{IFFT}[mod(-k, N)] / N$

FFT of Time-Reversed Input

DFT 입력 시퀀스 $x[n]$, $0 \leq n \leq N-1$이 있을 때, time-reversal 연산은 다음과 같이 정의된다.

여기서 $mod(n, N)$은 $N$에 대한 $n$의 modulo 연산을 의미한다. modulo 연산에 대한 자세한 내용은 위키를 참고하면 된다. 여기서는 본 글을 읽는 사람들의 이해를 돕기 위한 목적으로 modulo 연산의 간단한 예시를 아래와 같이 남기는 걸로 대신한다.

따라서 식 (1)은 다음과 같이 쓸 수 있다.

예를 들어, $x[n] = (1,2,3,4)$라고 하면, $g[n]=(1,4,3,2)$가 된다. 만약, $g[n]=(4,3,2,1)$과 같이 만들고 싶다면 Time-reversal 후 circular shiting을 적용하면 된다.

자, 이제 $g[n]$의 푸리에 변환 결과가 어떻게 되는지 살펴보자.

여기서 첫 번째 줄에서 두 번째 줄로 넘어가는데 있어 $mod(-n,N)=m$으로 치환하였다. $-n$과 $m$은 modulo-$N$에 대하여 합동인데 두 값의 범위가 $0$에서 $N-1$까지 이므로 $n=mod(-m,N)$도 성립한다.

결과가 흥미롭다. 식 (4)의 4번째 줄을 보면 time-teversal을 적용한 뒤 FFT를 하게 되면 time-reversal 적용 이전 값에 IFFT를 수행한 결과가 $1/N$배 scaling 된 것과 동일한 결과를 얻게 된다. FFT를 먼저하고 그 결과를 time-reversal하더라도 ($1/N$배 scaling 된) IFFT 연산 결과를 얻을 수도 있다. 즉, FFT 변환 이전에 time-reversal을 하던지 이후 time-reversal을 하던지 결과가 같다. 이와 같이 FFT와 IFFT는 서로 위상을 반대로 회전하는 것에 불과하기 때문에 하나를 이용하여 다른 하나의 결과를 얻을 수 있다. FFT를 이용하여 IFFT 결과를 얻는 다른 방법을 하나 더 살펴보기로 한다.

FFT of Complex Conjugated Input

이번에는 $g[n] = x^{*}[n]$일 경우, FFT 결과를 살펴보기로 한다. 바로 $G[k]$를 유도해보자.

식 (5)의 결과와 식 (4)의 결과를 비교해보자. 무언가 비슷하지 않은가? 그렇다. (5)의 결과는 (4)의 결과에 complex conjugate 연산을 적용한 것에 불과하다. 따라서 입력 샘플에 complex conjugate를 한 후 FFT를 하고, FFT 결과에 다시 complex conjugate을 하면 $1/N$배 scaling된 IFFT 결과를 얻을 수 있다. 즉,

Summary

• Time-reversal과 complex conjugate 연산을 사용하면 FFT로 IFFT 혹은 반대의 연산 결과를 얻을 수 있다.
• IFFT와 FFT는 위상 회전 방향이 서로 반대이기 때문에 어찌보면 당연한 결과이다. 시간적으로 뒤집거나 conjugate 후 시계방향으로의 위상 변화를 관찰하는 것은 원래 신호의 위상변화를 반시계 방향으로 관찰하는 것과 같기 때문이다.
• 사람에 따라 FFT로 IFFT 연산 결과를 얻는 것이 큰 의미없이 느껴질 지 모르지만, 임베디드 환경에서는 하나의 라이브러리 혹은 함수로 두 가지 일을 할 수 있기 때문에 활용 측면에서 굉장히 유용하다고 할 수 있다.
• FFT로 IFFT를 계산하는 한 가지 방식이 더 있다. 이 방식과 앞서 살펴본 방식을 다음 포스트에서 총 정리하기로 한다.