1D Fast Fourier Transform

Question

Quel algorithme est le suivant?

Je comprends à partir du code source suivante est:

1. dir est la direction de la FFT: forward = 1, = -1 inverse.
2. x est la partie réelle
3. y est la partie imaginaire

Qu'est-ce m ici?

Si x = {1, 1, 1, 1, 0, 0, 0, 0}, et, y = {} 0,0,0,0,0,0,0,0,0, quelle serait la valeur de m?

 //Inplace 1D FFT 
     public static void FFT1D(int dir, int m, ref double[] x, ref double[] y) 
     { 
      long nn, i, i1, j, k, i2, l, l1, l2; 
      double c1, c2, tx, ty, t1, t2, u1, u2, z; 
      /* Calculate the number of points */ 
      nn = 1; 
      for (i = 0; i < m; i++) 
       nn *= 2; 
      /* Do the bit reversal */ 
      i2 = nn >> 1; 
      j = 0; 
      for (i = 0; i < nn - 1; i++) 
      { 
       if (i < j) 
       { 
        tx = x[i]; 
        ty = y[i]; 
        x[i] = x[j]; 
        y[i] = y[j]; 
        x[j] = tx; 
        y[j] = ty; 
       } 
       k = i2; 
       while (k <= j) 
       { 
        j -= k; 
        k >>= 1; 
       } 
       j += k; 
      } 
      /* Compute the FFT */ 
      c1 = -1.0; 
      c2 = 0.0; 
      l2 = 1; 
      for (l = 0; l < m; l++) 
      { 
       l1 = l2; 
       l2 <<= 1; 
       u1 = 1.0; 
       u2 = 0.0; 
       for (j = 0; j < l1; j++) 
       { 
        for (i = j; i < nn; i += l2) 
        { 
         i1 = i + l1; 
         t1 = u1 * x[i1] - u2 * y[i1]; 
         t2 = u1 * y[i1] + u2 * x[i1]; 
         x[i1] = x[i] - t1; 
         y[i1] = y[i] - t2; 
         x[i] += t1; 
         y[i] += t2; 
        } 
        z = u1 * c1 - u2 * c2; 
        u2 = u1 * c2 + u2 * c1; 
        u1 = z; 
       } 
       c2 = Math.Sqrt((1.0 - c1)/2.0); 
       if (dir == 1) 
        c2 = -c2; 
       c1 = Math.Sqrt((1.0 + c1)/2.0); 
      } 
      /* Scaling for forward transform */ 
      if (dir == 1) 
      { 
       for (i = 0; i < nn; i++) 
       { 
        x[i] /= (double)nn; 
        y[i] /= (double)nn; 
       } 
      } 
     } 

Answer 1

La mise en œuvre de la FFT que vous avez posté est limité aux entrées de taille 2 ^m. Ici, m spécifie donc indirectement la taille de la taille du bloc FFT. Ainsi, par votre exemple avec x = {1,1,1,1,0,0,0,0} et y={1,1,1,1,0,0,0,0} étant des tableaux de taille 8 = 2 , m serait égal à 3.

Notez qu'il n'y a pas de contrôles supplémentaires pour la taille des tableaux x et y alors assurez-vous ils sont au moins de cette taille.