Testing Discrete Fourier Transform Program

Question

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,

C++

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):

C++

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:

VB

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!

C#

 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;
  }
  if(!inverse)
  {
    GRe[w] /= n;
    GIm[w] /= n;
  }
}

Posted 18-Oct-15 9:40am

binaryoffset

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Andreas Gieriet · Accepted Answer · 2015-10-18T10:05:00

Solution 2

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.
Regards
Andi

Posted 18-Oct-15 10:05am

Andreas Gieriet

Comments

[no name] 19-Oct-15 11:49am

A 5.

Andreas Gieriet 19-Oct-15 16:02pm

Thanks for your 5!
Cheers
Andi

Patrice T 19-Oct-15 14:23pm

+5

Andreas Gieriet 19-Oct-15 16:02pm

Thanks for your 5 too!
Cheers
Andi

nv3 · Accepted Answer · 2015-10-19T03:37:00

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.

Patrice T · Accepted Answer · 2015-10-18T10:30:00

Solution 3

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.

Posted 18-Oct-15 10:30am

Patrice T

Updated 18-Oct-15 20:50pm

v2

Comments

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.

Patrice T 19-Oct-15 14:27pm

You welcome