1D高速フーリエ変換

Question

次のアルゴリズムはどれですか？

私は、次のソースコードから理解することである：

1. dirは、FFTの方向である：フォワード= 1、逆= -1。
2. xは
3. y実部で、ここでmは何虚部

のですか？

x = {1,1,1,0,0,0,0}、およびy = {0,0,0,0,0,0,0,0,0}の場合、 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

あなたが投稿したFFTの実装は、サイズ2 ^mの入力に限定されています。ここでmは間接的にFFTブロックサイズのサイズを指定します。だから、​​3210とy={1,1,1,1,0,0,0,0}はサイズ8 = 2 、mの配列された状態でご例えば配列xとyの大きさのための追加チェックがないこと3.

ノートに等しくなるようにしてください彼らは少なくともそのサイズです。