FFT forward/backward mixed up

[GoogleCodeExporter]

=== What steps will reproduce the problem?
1. Please, run the following testcase. I've used AForge 2.0.0.0

public class AForgeFFTTestCase : ITestCase
    {
        public void Run()
        {
            int _fftSize = 512;

            uint _samples = (uint)_fftSize;
            double _frequency = 5000.0;
            double _samplingRate = 22050;
            double _amplitude = 128.0;
            double _phaseShift = 0.0;

            float[] wave = new float[_samples];
            double theta = 2.0 * System.Math.PI * _frequency / 
_samplingRate;
            for (int i = 0; i < _samples; i++)
                wave[i] = (float)(_amplitude * System.Math.Sin((i + 
_phaseShift) * theta));

            /** with MATLAB:
             >> framesPerSecond = 22050;
             >> sinusoid = 128.0 * sin( (0:framesPerSecond*5 - 1) * 2.0 * 
pi * 5000.0 / framesPerSecond ) 
             >> (sinusoid(1:512))

                ans =

                  Columns 1 through 7

                         0  126.6375   36.8564 -115.9109  -70.5909   
95.3662   98.3461

                  Columns 8 through 14

                  -66.7437 -117.7711   32.4678  127.2205    4.5583 
-125.8939  -41.1982

                  Columns 15 through 21

                  113.9036   74.3485  -92.2653 -101.2013   62.8118  
119.4819  -28.0380

                  ...ommitted
            */

            Debug.Assert(wave != null, "wave != null", "wave generated 
successfully");

            Complex[] _fftBuffer = new Complex[_fftSize];

            for (int j = 0; j < _fftSize; j++)
            {
                _fftBuffer[j].Re = wave[j];
                _fftBuffer[j].Im = 0;
            }
            Debug.WriteLine(string.Format("Before: {0}", EnumerableToString
(_fftBuffer)));
            /** 
             Before: (0, 0); (126,637496948242, 0); (36,8563766479492, 0); 
(-115,910873413086, 0); (-70,5908966064453, 0); (95,3662109375, 0); 
(98,3461303710938, 0); (-66,7437057495117, 0); (-117,771110534668, 0); 
(32,4677848815918, 0); (127,220481872559, 0); (4,55826330184937, 
0); ...ommitted             */

            FourierTransform.FFT(_fftBuffer, 
AForge.Math.FourierTransform.Direction.Forward);

            Debug.WriteLine(string.Format("After Forward: {0}", 
EnumerableToString(_fftBuffer)));
            /** with AForge:
             After Forward: (-0,0458090426400294, 0); 
(-0,0458066206615185, 0,00105319706189377); (-0,0457993759660467, 
0,00210677633330208); (-0,0457872413338016, 0,00316119805173783); 
(-0,045770078427684, 0,00421679018622292); (-0,0457482659113295, 
0,00527399339489622); (-0,0457214565257012, 0,0063331735845501); 
(-0,0456897318091003, 0,0073947941995166); (-0,0456530160518512, 
0,00845928020578105); (-0,0456113922318836, 
0,00952683736828639); ...ommitted             */
            /** with MATLAB:
             >> fft(sinusoid(1:512))

                ans =

                  1.0e+004 *

                  Columns 1 through 3

                  -0.0023            -0.0023 - 0.0001i  -0.0023 - 0.0001i

                  Columns 4 through 6

                  -0.0023 - 0.0002i  -0.0023 - 0.0002i  -0.0023 - 0.0003i

                  Columns 7 through 9

                  -0.0023 - 0.0003i  -0.0023 - 0.0004i  -0.0023 - 0.0004i

                  ...ommitted
             */

            for (int j = 0; j < _fftSize; j++)
            {
                _fftBuffer[j].Re = wave[j];
                _fftBuffer[j].Im = 0;
            }
            Debug.WriteLine(string.Format("Before: {0}", EnumerableToString
(_fftBuffer)));
            /** 
             Before: (0, 0); (126,637496948242, 0); (36,8563766479492, 0); 
(-115,910873413086, 0); (-70,5908966064453, 0); (95,3662109375, 0); 
(98,3461303710938, 0); (-66,7437057495117, 0); (-117,771110534668, 0); 
(32,4677848815918, 0); (127,220481872559, 0); (4,55826330184937, 
0); ...ommitted             */

            FourierTransform.FFT(_fftBuffer, 
AForge.Math.FourierTransform.Direction.Backward);

            Debug.WriteLine(string.Format("After Backward: {0}", 
EnumerableToString(_fftBuffer)));

            /** with AForge:
             After Backward: (-23,454229831695, 0); (-23,4529897786975, 
-0,53923689568961); (-23,4492804946159, -1,07866948265066); 
(-23,4430675629064, -1,61853340248977); (-23,4342801549742, 
-2,15899657534613); (-23,4231121466007, -2,70028461818686); 
(-23,409385741159, -3,24258487528965); (-23,3931426862594, 
-3,7861346301525); (-23,3743442185478, -4,3311514653599); 
(-23,3530328227244, -4,87774073256263); (-23,329093652554, 
-5,42627460778816); (-23,302566397391, -5,97687617389112); 
(-23,2734572712276, -6,5297997031653); (-23,2416841844246, 
-7,0852801124324); (-23,2071971812932, -7,64348553412925); ...ommitted    
*/
            /** with MATLAB:
              >> ifft(sinusoid(1:512))
                ans =

                  Columns 1 through 3

                  -0.0458            -0.0458 + 0.0011i  -0.0458 + 0.0021i

                  Columns 4 through 6

                  -0.0458 + 0.0032i  -0.0458 + 0.0042i  -0.0457 + 0.0053i

                  Columns 7 through 9

                  -0.0457 + 0.0063i  -0.0457 + 0.0074i  -0.0457 + 0.0085i

                    ...ommitted
             */
        }

        private string EnumerableToString(IEnumerable collection)
        { // that's for pretty-print
            string separator = "; ";
            string res = "", sep = "";
            foreach (var obj in collection)
            {
                if (obj is IEnumerable)
                {
                    res += sep + "[" + EnumerableToString(obj as 
IEnumerable) + "]";
                }
                else
                {
                    res += sep + obj;
                }
                sep = separator;
            }
            return res;
        }
    }

2. Notice MATLAB code snippets in comments along the code. Run them in 
MATLAB. I've used MATLAB 7.7.0 (R2008b).

3. Compare results.

=== What is the expected output? What do you see instead?
Expected: MATLAB fft & AForge FourierTransform.Direction.Forward - the 
same results;
MATLAB ifft & AForge FourierTransform.Direction.Backward - the same 
results;

Instead the results are swapped: fft & Backward - same; ifft & Forward - 
same.

=== Please use labels and text to provide additional information.
FourierTransform, FFT, FourierTransform.Direction

Original issue reported on code.google.com by babak.j...@gmail.com on 14 Jun 2009 at 12:57

[GoogleCodeExporter]

I've faced the same problem today. Indeed it is somehow weird that the 
directions are swapped. The probability of introducing a subtle bug into the 
code is just huge.

Original comment by ciumac.s...@gmail.com on 29 Dec 2010 at 1:08

[GoogleCodeExporter]

I believe this is caused due to the same error that I posted (issue 221). If 
you add a negative sign to the Imaginary part of the Twiddle Calculation, you 
can fix this issue.

Original comment by Monkeyha...@gmail.com on 10 Jun 2011 at 9:46