FFT를 이용한 inverse FFT

Forward fft: 

$$ {\tt fft}(x+iy)=X + i Y = \sum(x +i y) (W_r + i W_i)$$

$$=\sum  (x W_r - y W_i ) + i (x W_i + y W_r)$$

Inverse fft:

$$ {\tt ifft}(X+iY)= \frac{1}{N}\sum(X +i Y) (W_r - i W_i)$$

$$= \frac{1}{N} \sum  (X W_r + Y W_i ) + i (-X W_i + Y W_r)$$

$$ =\frac{1}{N}\sum \left(XW_r - (-Y) W_i\right) +(-i) \left(XW_i + (-Y)W_r\right) $$

$$ = \frac{1}{N}\left[{\tt fft}(X-iY) \right]^* = \frac{1}{N}\left[{\tt fft}((X+iY)^*)\right]^*$$

또는 

$$ \frac{1}{N} {\tt fft}(Y+iX)= \frac{1}{N} \sum(Y +i X) (W_r + i W_i)$$

$$=\frac{1}{N} \sum  (Y W_r - X W_i ) + i (Y W_i + X W_r)\\= y + i x$$