1D 고속 푸리에 변환

Question

다음 알고리즘은 무엇입니까?

어떤 I는 다음의 소스 코드에서 이해하기이다 :

1. dir은 FFT의 방향 : 순방향 = 1, 역 = -1.
2. x는
3. y 여기 m 무엇 허수

입니다 실수 부?

x = {1,1,1,0,0,0,0} 및 y = {000000000} 인 경우, 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 블록 크기의 크기를 지정합니다. 그래서 크기의 x = {1,1,1,1,0,0,0,0} 및 y={1,1,1,1,0,0,0,0}되는 배열을 사용하여 예를 들어 8 = ³ 2 m는 배열 x 및 y의 크기에 대한 추가 검사가 그렇게 확인이 없는지 3.

참고 동일한 것 그들은 적어도 그 크기입니다.