Click here to Skip to main content
15,877,859 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello. I have been testing my Discrete Fourier Transform program for 1 dimensional data (written in using C++).

For the following test input data,
REAL[0]=  0.000,   IMAG[0]=  0.000
REAL[1]= +1.000,   IMAG[1]=  0.000
REAL[2]=  0.000,   IMAG[2]=  0.000
REAL[3]=  0.000,   IMAG[3]=  0.000
REAL[4]=  0.000,   IMAG[4]=  0.000
REAL[5]=  0.000,   IMAG[5]=  0.000
REAL[6]=  0.000,   IMAG[6]=  0.000
REAL[7]=  0.000,   IMAG[7]=  0.000

The correct expected results are(should have constant magnitude in the transform domain; in this case, the squareroot of "real[x] squared imag[x] squared" equals 0.125 in every case):
REAL[0]=  0.125,   IMAG[0]= +0.000
REAL[1]= +0.088,   IMAG[1]= -0.088
REAL[2]= +0.000,   IMAG[2]= -0.125
REAL[3]= -0.088,   IMAG[3]= -0.088
REAL[4]= -0.125,   IMAG[4]= +0.000
REAL[5]= -0.088,   IMAG[5]= +0.088
REAL[6]= +0.000,   IMAG[6]= +0.125
REAL[7]= +0.088,   IMAG[7]= +0.088

However, my program returns the following results:

Real[0]: 0.125          Imag[0]:  0
Real[1]: 0.0883883      Imag[1]:  -0.0883883
Real[2]: 7.65404e-018   Imag[2]:  -0.125
Real[3]: -0.0883883     Imag[3]:  -0.0883883
Real[4]: -0.125         Imag[4]:  -1.53081e-017
Real[5]: -0.0883883     Imag[5]:  0.0883883
Real[6]: -2.29621e-017  Imag[6]:  0.125
Real[7]: 0.0883883      Imag[7]:  0.0883883

Below is my program. I would appreciate guidance in learning where the error lies and how to fix my this, thank you!

 bool inverse = false;
 int n = 8;
 double gRe[8] = {0,1,0,0,0,0,0,0};
 double gIm[8] = {0,0,0,0,0,0,0,0};
 double GRe[8] = {0,0,0,0,0,0,0,0};
 double GIm[8] = {0,0,0,0,0,0,0,0};

for(int w = 0; w < n; w++)
  GRe[w] = GIm[w] = 0;
  for(int x = 0; x < n; x++)
    double a = -2 * pi * w * x / float(n);
    if(inverse) a = -a;
    double ca = cos(a);
    double sa = sin(a);
    GRe[w] += gRe[x] * ca - gIm[x] * sa;
    GIm[w] += gRe[x] * sa + gIm[x] * ca;
    GRe[w] /= n;
    GIm[w] /= n;

Each meaningful test consists of stimulus, expected result, actual result an a comparator that compares the expected and the actual result.
If you compare the actual versus the expected result here, you see that you have a precision issue.
The expected result seems to be on three figures only. Make sure you compare with the respective precision.
Share this answer
[no name] 19-Oct-15 11:49am    
A 5.
Andreas Gieriet 19-Oct-15 16:02pm    
Thanks for your 5!
Patrice T 19-Oct-15 14:23pm    
Andreas Gieriet 19-Oct-15 16:02pm    
Thanks for your 5 too!
To me it looks like your results are correct to 15 significant digits, which is what was to be expected calculating in type double. So there is nothing to complain about. I assume your reference results were taken from a book and only the first three digits after the decimal were printed. So that is the reason of the discrepancy.

You are probably aware that your method of computation is relatively inefficient. There are so-called Fast Fourier algorithms that require much less computational work. Just use google and see what they do and how they save many multiply and add operations.
Share this answer
binaryoffset 19-Oct-15 9:46am    
Thanks but at this stage I am simply implementing 1D DFT (FFT will come later).
[no name] 19-Oct-15 11:49am    
A 5.
Patrice T 19-Oct-15 14:28pm    
a 5 too
Your problem is that the "correct expected results" are rounded to 3 decimals and not your "actual results".

You just need to format your output to 3 decimals.
Said otherwise, the problem is in code that display the result, code that you didn't showed.
Share this answer
nv3 19-Oct-15 9:38am    
I guess the author didn't like your answer -- but wrongly so. My 5.
Patrice T 19-Oct-15 14:26pm    
Not the author, rather a platinum member, the downvote was -16 reputation points.
nv3 19-Oct-15 16:56pm    
Whoever it was should have had the courage to comment on his downvote. So I hope you don't get frustrated by this.
Patrice T 19-Oct-15 17:07pm    
Courage and downvoting rarely fit togehter :)
No frustration, I have already been downvoted many times :-)
binaryoffset 19-Oct-15 9:45am    
You're quick to judge about the author not liking an answer.
Thanks ppolymorphe, I appreciate your comment.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900