FFTアルゴリズムとDFTアルゴリズムC言語実装(詳細を与える)

宣言:

         《      》    
        （DFT）        （FFT）    
      C   FFT  ，         FFT         。

構想を書く:

  FFT            ，                
                   ，              
                     
                          

コードセクション
逆順コード:

for (int I = 1; I < N1; I++)						//        
	{
		if (I < J)
		{
			T = x[I];
			x[I] = x[J];
			x[J] = T;
		}
		K = LH;
		if (J >= K)
		{
			do
			{
				J = J - K;
				K = K / 2;
			} while (J >= K);
		}
		J = J + K;
	}

##逆順コード解釈:

 J             。
  N=2^M，M               N/2，               N/4，N/8，……，2，1。
  ，             J+N/2。      0（J=N/2），        0（J=J-N/2），      1（J+N/4）。
     1 ，      0、1 ，   0（J

##FFTコード:

for (L = 1; L <= M; L++)							//FFT  
	{
		B = (int)(pow(2, L - 1));
		for (J = 0; J < B; J++)
		{
			P = (int)(J*pow(2, M - L));
			for (k = J; k < N; k = (int)(k + pow(2, L)))
			{
				K1 = k + B;
				complex wn, t;
				Wn_i(N, P, &wn);
				c_mul(f[K1], wn, &t);					//。。。。。。。。。。。。
				c_sub(f[k], t, &(f[K1]));				//    
				c_plus(f[k], t, &(f[k]));				//。。。。。。。。。。。。
			}
		}
	}

##FFTコード解釈:

 L  ，             B=2^(L-1)  
   B        ；            2^L  2^(M-1)   
     （ 1 ）  ，    ，   M   
    L    ，    B        ，         ，          2^(M-L)   

##複素関数定義と演算コード部分:

void c_plus(complex a, complex b, complex *c)			//    
{
	c->real = a.real + b.real;
	c->imag = a.imag + b.imag;
}
void c_sub(complex a, complex b, complex *c)			//    
{
	c->real = a.real - b.real;
	c->imag = a.imag - b.imag;
}
void c_mul(complex a, complex b, complex *c)			//    
{
	c->real = a.real*b.real - a.imag*b.imag;
	c->imag = a.real*b.imag + a.imag*b.real;
}

void Wn_i(int n1, int i, complex *Wn)				//  FFT    
{
	Wn->real = cos(2 * PI*i / n1);
	Wn->imag = -sin(2 * PI*i / n1);
}

完全なコードを確認するにはこちらをクリックしてください←
##フルコード実装の機能:

1.    ：
 -             
 -      FFT DFT    
2.    ：
 -             DFT   FFT