1 




#include <vector>
using std::vector;

#include <complex>
using std::complex;
using std::polar;

typedef complex<double> Complex;

#define Pi 3.14159265358979323846

// direct Fourier transform
vector<Complex> dF( const vector<Complex>& in )
{
 const int N = in.size();

 vector<Complex> out( N );

 for (int k = 0; k < N; k++)
 {
  out[k] = Complex( 0.0, 0.0 );

  for (int n = 0; n < N; n++)
  {
   out[k] += in[n] * polar<double>( 1.0, - 2 * Pi * k * n / N );
  }
 }

 return out;
}

// inverse Fourier transform
vector<Complex> iF( const vector<Complex>& in )
{
 const int N = in.size();

 vector<Complex> out( N );

 for (int k = 0; k < N; k++)
 {
  out[k] = Complex( 0.0, 0.0 );

  for (int n = 0; n < N; n++)
  {
   out[k] += in[n] * polar<double>(1, 2 * Pi * k * n / N );
  }

  out[k] *= Complex(  1.0 / N , 0.0 );
 }

 return out;
}

誰が言うことができます、何が悪いのですか？

たぶん私はこのアルゴリズムの実装の詳細を理解していません...しかし私はそれを見つけることができません）））

また、畳み込みを計算する必要があります。

しかし、テスト例が見つかりません。

アップデート

// convolution. I suppose that x0.size == x1.size
vector convolution( const vector& x0, const vector& x1) 
{
    const int N = x0.size();



vector<Complex> tmp( N );

for ( int i = 0; i < N; i++ )
{
    tmp[i] = x0[i] * x1[i];
}

return iF( tmp );




}

4

3 に答える 3

2

I really don't know exactly what your asking, but your DFT and IDFT algorithms look correct to me. Convolution can be performed using the DFT and IDFT using the circular convolution theorem which basically states that f**g = IDFT(DFT(f) * DFT(g)) where ** is circular convolution and * is simple multiplication.

To compute linear convolution (non-circular) using the DFT, you must zero-pad each of the inputs so that the circular wrap-around only occurs for zero-valued samples and does not affect the output. Each input sequence needs to be zero padded to a length of N >= L+M-1 where L and M are the lengths of the input sequences. Then you perform circular convolution as shown above and the first L+M-1 samples are the linear convolution output (samples beyond this should be zero).

Note: Performing convolution with the DFT and IDFT algorithms you have shown is much more inefficient than just computing it directly. The advantage only comes when using an FFT and IFFT(O(NlogN)) algorithm in place of the DFT and IDFT (O(N^2)).

于 2010-11-22T15:44:42.017 に答える
1

「離散フーリエ変換（DFT）を計算するための」FFTWライブラリとそのC＃ラッパーを確認してください;）多分これも;）

幸運を！

于 2010-11-22T13:12:43.300 に答える
0

変換は問題ないように見えますが、プログラムには畳み込みを行っているものは何もありません。

更新: 畳み込みコードは、要素ごとの乗算の前に、最初に入力を順方向変換する必要があります。

于 2010-11-22T13:11:10.077 に答える