[Py|수치해석] 무식하게 DFT

DFT (discrete fourier transformation), FFT가 이것보다 효율적인 거란 말이지. 알았어 다음 포스팅은 그거다. DFT의 정의는 http://en.wikipedia.org/wiki/Fast_Fourier_transform 에서.

#!/usr/bin/env python

### DFT Bruteforce
### didn't check if this coding gives the right answer. I just followed the
### definition.

### by DwYoon

N_DATA = 1024
#N_DATA = 16

import cmath
import random

# populate raw data using random generator
# you can change this to use your own data set
x = []
for i in xrange(N_DATA):
        x.append(random.random())

## Following is the definition of discrete fourier transformation
## essentially, it approximates frequency of the give data.

##       N-1          /   2 pi i      \
## X   = sum x   exp |  - ------- n k  |
##   k   n=0   n      \     N         /

## What computer is good at is computing, don't think much, we just follow
## the given definition.

X = []
for k in xrange(N_DATA):
        Xk = 0 # initialize Xk
        # do summation over n = [ 0, ..., N-1 ]
        for n in xrange(N_DATA):
                Xk += (x[n] * cmath.exp( - 2*cmath.pi*1j*n*k/N_DATA ) )
                #                      /   2 pi i      \
                #      x          exp |  - ------- n k  |
                #        n             \     N         /
        X.append(Xk)

# check the result. Do beutify this to see the meaning clearly.
print x
print "-------------------------"
print X