Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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

answer = compute_dft(unsorted_v)

for item in answer:

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.

share|improve this question

migrated from physics.stackexchange.com Jun 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? –  J. M. Jun 17 '13 at 1:07

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.