IFFT: 주파수에서 다시 원래 신호로

핵심 질문

FFT로 옮긴 값을 어떻게 다시 원래 계수 배열로 되돌릴 수 있을까?

교과서 설명

DFT는 길이 $N$ 인 배열 $x[n]$ 을 주파수 값 $X[k]$ 로 바꾼다.

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

여기서 이 자료의 약속은

\omega_N=e^{-2\pi i/N}

이다. 역변환은 이 과정을 거꾸로 해서 $X[k]$ 들로부터 원래 $x[n]$ 을 복원한다.

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

식의 모양을 비교해 보자. DFT는 $\omega_N^{kn}$ 을 쓰고, 역 DFT는 $\omega_N^{-kn}$ 을 쓴다. 즉 회전 방향만 반대로 돌린다. 그리고 마지막에 전체 길이 $N$ 으로 나누어 크기를 되돌린다.

이 역 DFT를 FFT와 같은 분할 정복 구조로 빠르게 계산한 것이 IFFT다.

왜 방향을 반대로 돌릴까?

DFT는 원래 신호를 여러 회전 기준으로 분해한다. 다시 합칠 때는 분해할 때 썼던 회전을 반대로 돌려 각 성분을 원래 위치에 맞춰야 한다.

복소수에서 회전 방향을 반대로 만든다는 말은 켤레 복소수를 쓴다는 뜻과 같다. 단위원 위의 복소수는 길이가 $1$ 이므로

\omega_N^{-1}=\overline{\omega_N}

이다. 따라서 IFFT에서는 기본 회전값을

e^{2\pi i/N}

처럼 반대 방향으로 잡으면 된다.

왜 $N$ 으로 나눌까?

DFT와 역 DFT를 이어서 쓰면 같은 성분끼리는 $N$ 번 쌓인다. 서로 다른 성분끼리는 단위원근의 직교합 때문에 사라진다.

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

그래서 마지막에 $\frac{1}{N}$ 을 곱해야 원래 크기가 된다. 이 나눗셈을 빠뜨리면 모양은 맞아도 모든 값이 $N$ 배로 커진 결과가 나온다.

작은 예로 $N=2$ 에서 $x=[1,2]$ 를 보자. DFT는

X[0]=1+2=3,\qquad X[1]=1-2=-1

이다. 이제 역변환을 하면

x[0]=\frac{3+(-1)}{2}=1,\qquad x[1]=\frac{3-(-1)}{2}=2

가 되어 원래 배열이 돌아온다.

FFT 코드에서는 무엇만 바뀔까?

FFT의 재귀 구조는 그대로 쓸 수 있다. 달라지는 것은 두 가지다.

inverse 모드에서는 회전각의 부호를 반대로 쓴다.
계산이 끝난 뒤 모든 값을 $N$ 으로 나눈다.

즉 같은 butterfly 구조에서

E[k]+\omega_N^kO[k],\qquad E[k]-\omega_N^kO[k]

를 쓰되, IFFT에서는 $\omega_N$ 대신 반대 방향 회전값을 넣는다. 그래서 실전 구현에서는 보통 fft(a, false)는 FFT, fft(a, true)는 IFFT가 되도록 한 함수로 합친다.

정수 계수 다항식 곱셈에서는 IFFT 뒤 결과가 $9.999999999$ 또는 $10.000000001$ 처럼 나올 수 있다. 이것은 복소수 실수 계산의 오차이므로 마지막에는 가까운 정수로 반올림한다.

합성곱과의 연결

FFT 합성곱은 다음 흐름으로 끝난다.

a,b \xrightarrow{\text{FFT}} A,B \xrightarrow{\text{same }k\text{끼리 곱하기}} C \xrightarrow{\text{IFFT}} c

여기서 $c$ 가 우리가 원하는 계수 배열이다. 따라서 FFT만 알고 IFFT를 빼면 합성곱 알고리즘은 완성되지 않는다. 주파수 영역에서 곱한 값을 다시 계수 영역으로 가져오는 마지막 문이 IFFT다.

직관 비유

퍼즐 조각을 색깔별로 분류해서 계산했다면, 마지막에는 다시 원래 그림 모양으로 조립해야 한다. FFT가 분류라면 IFFT는 조립이다. 조립할 때 방향을 거꾸로 맞추고, 분류 과정에서 커진 크기를 $N$ 으로 나누어 되돌린다.

예제

다음 두 배열의 합성곱을 FFT로 계산한다고 하자.

a=[1,2],\qquad b=[3,4]

결과 길이는 $3$ 이므로 길이 $4$ 로 zero padding한다.

a=[1,2,0,0],\qquad b=[3,4,0,0]

그다음 두 배열을 FFT해서 $A$ , $B$ 를 얻고, 같은 번호끼리 곱해 $C[k]=A[k]B[k]$ 를 만든다. 이 $C$ 는 아직 계수 배열이 아니다. 마지막에 IFFT를 해야

c=[3,10,8,0]

이 나오고, 앞의 세 칸 $[3,10,8]$ 이 선형 합성곱 결과가 된다.

손풀이 체크

IFFT에서 회전 방향은 FFT와 비교해 어떻게 바뀔까?

답 보기
반대로 바뀐다.
IFFT 마지막에 왜 $N$ 으로 나누어야 할까?

답 보기
같은 성분이 합쳐지며 $N$ 배로 쌓이므로 원래 크기로 되돌려야 한다.
FFT 합성곱에서 IFFT는 어느 단계에 쓰일까?

답 보기
주파수 영역에서 같은 $k$ 끼리 곱한 뒤, 그 결과를 계수 배열로 되돌릴 때 쓴다.

다음으로 이어지는 생각

이제 FFT, 자리별 곱셈, IFFT가 모두 준비되었다. 마지막으로 zero padding을 왜 충분히 해야 하는지까지 확인하면 빠른 다항식 곱셈 알고리즘이 완성된다.