# What to look for in a discrete fourier transform

I was attempting to do a discrete Fourier transform through a computer program on a list of numbers. Before doing that I decided to test it by running through a list of 1000 numbers which I created by summing 20 sine waves which were created by the formula sin(2*pi*integer between 1 and 1000/ desired frequency). Based upon my understanding of the DFT I should have got a 0 for all values except for my twenty desired frequencies of 8, 13, 13, 14, 18, 23, 25, 32, 33, 38, 41, 48, 51, 64, 73, 79, 82, 85, 91, and 100. Some of my first outputs were:

0 : (-140.00101976200014-0j)
1 : (-140.50548903670193-3.1117640585553277j)
2 : (-142.0510770346883-6.33051372898894j)
3 : (-144.74035295772114-9.776661681575883j)
4 : (-148.76670548437778-13.601419744876273j)
5 : (-154.45783389980753-18.014310511371548j)
6 : (-162.3639888189583-23.333771555566614j)


From this program in python 3.2:

import cmath

def compute_dft(input):

n = len(input)
output = [0] * n
for k in range(n):
s = 0
for t in range(n):
s += input[t] * cmath.exp(-1j * 2 * cmath.pi * t * k / n)
output[k] = -s
return output


print(answer.index(item), ":", item)


I then went and checked the program on some examples of a DFT online and found that the answers it spit out were the same as the examples answers, which led me to wonder if my expectations of the output was wrong.

Any advice on resolving my problem would be much appreciated.

-

## migrated from physics.stackexchange.comJun 17 '13 at 0:58

This question came from our site for active researchers, academics and students of physics.

That depends. What formula (including the normalization) for the DFT are you using? –  Ｊ. Ｍ. Jun 17 '13 at 1:07

Your input is not the sum of sine functions. I think if you print out the values of s, you'll find that it has complex values. Replace

cmath.exp(-1j * 2 * cmath.pi * t * k / n)


with

cmath.sin(2 * cmath.pi * t * k / n)


and you should be set.

Also, due to finite precision arithmetic, you may see some tiny terms outside the 20 frequencies you expect to see.

-

JM: I used the formula FreqX[k] = sum(Timex[k] * e^(-2j*pi*k*n/N).

As for the normalization I really don't know what that means, which is probably a contributing factor to the lack of finding the appropriate answer.

Thanks for any help you can give. I've been looking this up for a week and have yet to figure it out.

-
Hi, and welcome to scicomp! This is not really an answer to the question. You could modify your question to state the formula that you have used or consider adding a comment to your question. All the best. –  Subodh Jun 17 '13 at 4:35