DFT (Discrete Fourier Transform)

연속함수에서는 Fourier transform을 하면 되지만 discrete 에서는 DFT를 행한다.
waveform 이 interval T 로 sampled 되었다고 하면 , sample sequence 는  x(nT) = x(0) , x(1)
, x(2) , x(3) , x(4) , x(5) . . . . x[(N-1)T] 라 할수 있다.   (n = 0 . . . . . N-1 )

그래서 x(nT)의 DFT 는 frequency domain에서 X(k) = X(0) ,X(). . . X[(N-1)] 같은 복소수 값의 sequence를 갖는다.

DFT는 다음식과 같다.
         ( k = harmonic number of transform component )

그리고 중요한 DFT의 성질이 있는데 k번째의 요소와 k N 번째 요소를 비교하면

따라서 위 식은 DFT 는 주기 N에 대하여 periodic 하게 나타난다는 것이다.

Computational complexity of the DFT

만약 8-point 에 대해서 DFT를 실행한다고 하면 총 8*8 번의 complex곱을 실시해야하고 8* 7 번의 덧셈을 해야 한다. 그래서 N point DFT 는 N^2 과 N(N-1) 번의 곱과 합을 계산해야한다.
만약 N=1024 개 라면 엄청난 계산시간이 필요하다.  따라서 이 작업을 개선하기 위해서 나온 algorithm 이 FFT(Fast Fourier Transform) 이다.

  FFT (Fast Fourier Transform)
FFT는 DFT에 비해    의 complex 곱 계산량을번으로 낮출수가 있고  따라서 계산 속도도 훨씬 빠르다.
FFT 알고리즘은 radix-2 DIT(Decimation in Time) FFT , DIF(Decimation in frequency) FFT 등이  있는데 우선 DIT FFT를 살펴보자.

DFT의 식은 다음과 같다.

여기서이라고 하면

로 쓸수 있다.

여기서  몇가지 식을 유도하자.

또 이므로 다음 식과 같아진다.

이 식을 살펴보면 우측항은 N/2 point DFT (even-number , odd-number)로 이루어져   있는 걸 볼수 있다.
식을 간단히 표현하면

로 나타낼수 있고 , 따라서   를 위와 같은 방법으로 다시 나누면

이다.

마찬가지 방법으로 하면 ,위와 같이 모두 N/4 point DFT 로 나눌수가 있다.  이와 같이 N개의 point를 FFT를 할려면 로 정하고 ,각 계산 단계를 개로 나눌수 있다.

하나의 butterfly 계산 방법을 살펴보면 , 다음과 같은 경우

이 된다.

따라서 총 계산량은 그리고 각 단계 마다의 butterfly 개수를 곱한 것이 된다.

예를 들어 8-point 의 경우 r=3 , butterfly 개수 = 4개 , 그래서 12 번이 된다. DIF FFT의 경우는 모양은 비슷하나 butterfly 계산방법이 DIT FFT와는 좀 다르다.  컴퓨터로 많은 point의 FFT를 계산하기 위해서는 위와 같은 알고리즘을 적절한 language 로 coding 하여 사용하면 될 것이다.