java Stuck on a point of my programme

[Original Poster]

hello all,

 

I am trying to Generate an Inverse Discrete Fourier Transform on a square wave and display the time domain information on a graph (should be a sinc function sin(x)/x).....

 

basically I cant do an IDFT... I can do a DFT but an IDFT is lost on me.... was wondering if anyone can help me... my basic square wave is 32 0s 64 1s and 32 final 0s... im not using complex data as you can see this is very basic but im lost on the topic of digital signal processing :(

[Andre S. Veteran]

It's been a long time and I never really got into the math of it, but it's really just matter of translating a mathematical formula as Java code, which is straightforward as long as you understand the formula. Here's what seems like a clear definition of the inverse DFT: http://mrl.cs.vsb.cz/people/gaura/dzo/idft_en.pdf

[snaphat (Myles Landwehr) Member]

Simple, start with the DFT in C from here and do the following:

 

(1) Switch the computations of the real and imaginary parts of x[n] to use the real and imaginary parts of your frequency domain signal x[k].

(2) Normalize the output. This step depends on what field you are in as mentioned here. I'm using the signal processing normalization below.

 

Like so:

    // Calculate iDFT of x using brute force
    // Assumes x[] is zero'd out.
    // Note: you should switch n and k variables because they are backwards in this code.
    // Note: input frequency signal assumed to be split into real and imaginary parts.
    for (k=0 ; k<N ; ++k)
    {
        // Real part of X[k]
        ///Changed x[n] ===> Xre[n] below:
        for (n=0 ; n<N ; ++n) x[k] += Xre[n] * cos(n * k * PI2 / N);
         
        // Imaginary part of X[k]
        ///Changed x[n] ===> Xim[n] below:
        for (n=0 ; n<N ; ++n) x[k] -= Xim[n] * sin(n * k * PI2 / N);
        
        x[k] /= N; //Normalize here.
    }

I briefly checked this with Mathematica and it appeared to work. You should test yourself though. One thing to note is that the result will not be consistent with wolfram alpha because it is using the default mathematica normalization of 1/sqrt(N).

[Original Poster]

 

Simple, start with the DFT in C from here and do the following:

 

(1) Switch the computations of the real and imaginary parts of x[n] to use the real and imaginary parts of your frequency domain signal x[k].

(2) Normalize the output. This step depends on what field you are in as mentioned here. I'm using the signal processing normalization below.

 

Like so:

    // Calculate iDFT of x using brute force
    // Assumes x[] is zero'd out.
    // Note: you should switch n and k variables because they are backwards in this code.
    // Note: input frequency signal assumed to be split into real and imaginary parts.
    for (k=0 ; k<N ; ++k)
    {
        // Real part of X[k]
        ///Changed x[n] ===> Xre[n] below:
        for (n=0 ; n<N ; ++n) x[k] += Xre[n] * cos(n * k * PI2 / N);
         
        // Imaginary part of X[k]
        ///Changed x[n] ===> Xim[n] below:
        for (n=0 ; n<N ; ++n) x[k] -= Xim[n] * sin(n * k * PI2 / N);
        
        x[k] /= N; //Normalize here.
    }

I briefly checked this with Mathematica and it appeared to work. You should test yourself though. One thing to note is that the result will not be consistent with wolfram alpha because it is using the default mathematica normalization of 1/sqrt(N).

 

 

so if this is my dft (excuse the mess) what would i need to do... btw you are saving my life helping me (seriously I AM ON THE EDGE) I really dont understand this... I can see what its doing like its english... but doesnt mean i understand what its doing

	public static void dft() throws FileNotFoundException
	{
		/
		double rad_per_sample, sin_accum, cos_accum;
		double cos_val, cos_prod, sin_val, sin_prod;
		int sample_size = 256;
		int scale = 0;
		
		rad_per_sample = ((2 * Math.PI)/sample_size);
		scale = sample_size/2;
				
		for(int freq = -128; freq < sample_size/2; freq++)
		{
			sin_accum = cos_accum = 0.0;
			for (int i = 0; i < sample_size; i++)
			{
				cos_val = Math.cos(rad_per_sample * freq * i);
				cos_prod = cos_val * data[i];
				cos_accum += (cos_prod / scale);
				
				sin_val = Math.sin(rad_per_sample * freq * i);
				sin_prod = sin_val * data[i];
				sin_accum -= (sin_prod / scale);
				double mag = Math.sqrt(Math.pow(cos_accum, 2) + Math.pow(sin_accum,2));
				
				System.out.println(mag);
			}
			
			real_val[freq + 128] = cos_accum;
			imag_val[freq + 128] = sin_accum;
			double mag = Math.sqrt(Math.pow(cos_accum, 2) + Math.pow(sin_accum,2));
			//System.out.format("Line: %f and data i %f\n " , freq, cos_accum);
			System.out.println(mag);
			
		}

[snaphat (Myles Landwehr) Member]

Well the first thing is that you code is doing some shifting with frequency that doesn't make sense and is resulting incorrect output from your DFT. There's no reason to try to apply shifting to center your signal around zero because these output points represent sinusoidal harmonic multiples of your fundamental frequency. In detail, the data point x(k) is at frequency k*2*pi/N. Without loss of generality, if you want x(-k), it is going to be some multiple of your fundamental frequency, see here. The main point is, you'll get half a square wave or half a sync function in the positive direction, but since we are talking about sinusoidal harmonics which are periodic at the fundamental frequency, the negative spectrum is a mirror of the positive which gives you the full sinc.

 

Secondly, I don't understanding your scaling factor (1/(sampling rate/2)). It doesn't match what you normally see in different domains. 

 

Here's the modified code:

        //Remove frequency shift.
        for(int freq = 0; freq < sample_size; freq++)
        {
            sin_accum = cos_accum = 0.0;
            for (int i = 0; i < sample_size; i++)
            {
                cos_val = Math.cos(rad_per_sample * freq * i);
                cos_prod = cos_val * data[i];
                cos_accum += (cos_prod / scale);
                
                sin_val = Math.sin(rad_per_sample * freq * i);
                sin_prod = sin_val * data[i];
                sin_accum -= (sin_prod / scale);
                double mag = Math.sqrt(Math.pow(cos_accum, 2) + Math.pow(sin_accum,2));
                
                System.out.println(mag);
            }
            
            real_val[freq] = cos_accum;
            imag_val[freq] = sin_accum;
            double mag = Math.sqrt(Math.pow(cos_accum, 2) + Math.pow(sin_accum,2));
            //System.out.format("Line: %f and data i %f\n " , freq, cos_accum);
            System.out.println(mag);
        }

Here is the DFT based off of the modified code. The modifications are no different from what I listed above:

//idft
        for(int freq = 0; freq < sample_size; freq++)
        {
            sin_accum = cos_accum = 0.0;
            for (int i = 0; i < sample_size; i++)
            {
                cos_val = Math.cos(rad_per_sample * freq * i);
                cos_prod = cos_val * real_val[i]; //Switch in RE{x[f]}
                cos_accum += (cos_prod/2); // odd scaling here due to your dft scaling.
                
                sin_val = Math.sin(rad_per_sample * freq * i);
                sin_prod = sin_val * imag_val[i]; //Switch in IM{x[f]}
                sin_accum -= (sin_prod/2); //odd scaling here due to your dft scaling.
            }
            
            data[freq] = cos_accum + sin_accum; // change here.
        }