Fast Fourier Transform

Forum 2005-2010 (read only) Software Bugs & Suggestions
1

I have problem about this code, it show error message "invalid conversion from 'void*' to double(*)[2]" Can anyone help me?

#include <stdlib.h>
#include <math.h>
#include <stdio.h>
/* macros */
#define TWO_PI (6.2831853071795864769252867665590057683943L)
/* function prototypes */
void fft(int N, double (*x)[2], double (*X)[2]);
void fft_rec(int N, int offset, int delta, double (*x)[2], double (*X)[2], double (*XX)[2]);

* This file defines a C function fft that, by calling another function       *
 * fft_rec (also defined), calculates an FFT recursively.  Usage:             *
 *   fft(N, x, X);                                                            *
 * Parameters:                                                                *
 *   N: number of points in FFT (must equal 2^n for some integer n >= 1)      *
 *   x: pointer to N time-domain samples given in rectangular form (Re x,     *
 *      Im x)                                                                 *
 *   X: pointer to N frequency-domain samples calculated in rectangular form  *
 *      (Re X, Im X)                                                          *
 * Here, N and X are given, and x is calculated.                              *
 ******************************************************************************/

void setup()
{
  
}

void loop()
{
  
}

/* FFT */
void fft(int N, double (*x)[2], double (*X)[2])
{
  /* Declare a pointer to scratch space. */
  double (*XX)[2] = malloc(2 * N * sizeof(double));
  /* Calculate FFT by a recursion. */
  fft_rec(N, 0, 1, x, X, XX);
  /* Free memory. */
  free(XX);
}

/* FFT recursion */
void fft_rec(int N, int offset, int delta, double (*x)[2], double (*X)[2], double (*XX)[2])
{
  int N2 = N/2;            /* half the number of points in FFT */
  int k;                   /* generic index */
  double cs, sn;           /* cosine and sine */
  int k00, k01, k10, k11;  /* indices for butterflies */
  double tmp0, tmp1;       /* temporary storage */

  if(N != 2)  /* Perform recursive step. */
    {
      /* Calculate two (N/2)-point DFT's. */
      fft_rec(N2, offset, 2*delta, x, XX, X);
      fft_rec(N2, offset+delta, 2*delta, x, XX, X);

      /* Combine the two (N/2)-point DFT's into one N-point DFT. */
      for(k=0; k<N2; k++)
        {
          k00 = offset + k*delta;    k01 = k00 + N2*delta;
          k10 = offset + 2*k*delta;  k11 = k10 + delta;
          cs = cos(TWO_PI*k/(double)N); sn = sin(TWO_PI*k/(double)N);
          tmp0 = cs * XX[k11][0] + sn * XX[k11][1];
          tmp1 = cs * XX[k11][1] - sn * XX[k11][0];
          X[k01][0] = XX[k10][0] - tmp0;
          X[k01][1] = XX[k10][1] - tmp1;
          X[k00][0] = XX[k10][0] + tmp0;
          X[k00][1] = XX[k10][1] + tmp1;
        }
    }
  else  /* Perform 2-point DFT. */
    {
      k00 = offset; k01 = k00 + delta;
      X[k01][0] = x[k00][0] - x[k01][0];
      X[k01][1] = x[k00][1] - x[k01][1];
      X[k00][0] = x[k00][0] + x[k01][0];
      X[k00][1] = x[k00][1] + x[k01][1];
    }
}
2

Except for the missing '/' to start the long (and somewhat untidy) comment beginning in line 10, this is valid C code.

However...

The Arduino IDE always makes C++ out of your sketch. See Footnote.

And...

In C++, the language does not allow assignment of a pointer value to a pointer of different type without a cast.

So...

If XX is supposed to be a pointer to an array of two doubles, you can try something like the following. (I added some, hopefully illuminating, comments.)

  /* 
   * Declare a pointer to scratch space.
   * A pointer to an array[2] of doubles.
   * Allocate enough space for N such arrays.
   *
   */
  double (*XX)[2] = (double (*)[2])malloc(2 * N * sizeof(double));

Regards,

Dave

Footnote:
In "real" C++ you wouldn't use malloc() at all. (At least I wouldn't; I would use new, but this is not an option with avr-gcc and avr-clib that we use with Arduino).

More importantly, in embedded systems with limited resources, I would look very carefully at any recursive functions. What is the worst-case depth? Are you sure you won't run out of RAM? Shouldn't you, at least, check the return value of malloc() to try to make sure that you could get some RAM when you need it? That way the program might be able to give some indication of a problem rather than crashing silently (and ignominiously).

3

I am a beginner for c programming. Do you have any idea to suggest me?

Best regard,

4

@Jetdapr:

...suggest...

I responded to your initial post by trying to show how to get your sketch to compile under the Arduino system. What other questions do you have?

I mean, for beginners in C, I doubt that taking someone else's code for a recursive FFT is the optimal learning path. As a matter of fact, I'm not sure that trying to program an Arduino system is the best way of learning C and/or C++. Really. I don't think so.

However...

I know that different people have different ways of learning (just as different people have different ways of trying to help).

So: How can we help?

Regards,

Dave