3

現在、Java で FFT アルゴリズムを実装しようとしていますが、少し問題があります。アルゴリズムの他のすべての部分をよくテストしましたが、うまく機能しているようです。

私が得ている問題は、基本ケースでは複素数配列が返され、基本ケース内にデータA[0]が入力されることです。基本ケースが実行された後、 for ループが実行され、 wherey0[0]およびare nully1[0]であることがわかります。これにより、基本ケースに割り当てられているにもかかわらず、かなり混乱しています。これは行に示されていますSystem.out.println

誰かが私のやり方の間違いを教えてくれますか?

    //This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) { 
    double real, imag;
    Complex A0[] = new Complex[((int) Math.ceil(N/2))]; 
    Complex A1[] = new Complex[((int) Math.ceil(N/2))];
    Complex[] omega = new Complex[N];
    Complex[] y = new Complex[N];
    Complex[] y0 = new Complex[((int) Math.ceil(N/2))];
    Complex[] y1 = new Complex[((int) Math.ceil(N/2))]; 

    //base case
    if (N == 1) {
        return A;
    }
    else {
        real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
        imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;
        omega[N-1] = new Complex(real, imag);
        omega[0] = new Complex(1, 0);
        A0 = splitInput(A, 1);
        A1 = splitInput(A, 0);
        //recursive calls
        y0 = FFT(A0, N/2);
        y1 = FFT(A1, N/2);
        for (int k = 0; k < ((N/2)-1); k++) {
            System.out.print("k: " + k + ", y0: " + y0[k]); System.out.println(", y1: " + y1[k]);
            y[k] = y0[k].plus(omega[k].times(y1[k]));
            y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
            omega[0] = omega[0].times(omega[N]);
        }
        return y;
    }
}

要求された私の splitInput メソッドのコードは次のとおりです

//This method takes a double array as an argument and returns every even or odd
//element according to the second int argument being 1 or 0
private static Complex[] splitInput(Complex[] input, int even) {
    Complex[] newArray = new Complex[(input.length/2)];

    //Return all even elements of double array, including 0
    if (even == 1) {
        for (int i = 0; i < (input.length/2); i++) {
            newArray[i] = new Complex(input[i*2].re, 0.0);
        }
        return newArray;
    }
    //Return all odd elements of double array
    else {
        for (int i = 0; i < (input.length/2); i++) {
            newArray[i] = new Complex (input[(i*2) + 1].re, 0.0);
        }
    return newArray;
    }
}

編集:私はあなたの提案に従ってコードを更新しましたがy[k] = y0[k].plus(omega[k].times(y1[k]));、y0&y1はまだnull基本ケースの後にあるため、行からヌルポインター例外を取得しています:(さらにアイデアはありますか?更新されたアルゴリズムは次のとおりです

//This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) { 
    double real, imag;
    Complex[] omega = new Complex[N];
    Complex[] y = new Complex[N];
    Complex[] A0;
    Complex[] A1;
    Complex[] y0;
    Complex[] y1;

    //base case
    if (N == 1) {
        return A;
    }
    else {
        real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
        imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;;
        omega[N-1] = new Complex(real, imag);
        omega[0] = new Complex(1, 0);
        A0 = splitInput(A, 1);
        A1 = splitInput(A, 0);
        //recursive calls
        y0 = FFT(A0, N/2);
        y1 = FFT(A1, N/2);
        for (int k = 0; k < ((N/2)-1); k++) {
            y[k] = y0[k].plus(omega[k].times(y1[k]));
            y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
            omega[0] = omega[0].times(omega[N-1]);
        }
        return y;
    }
}
4

2 に答える 2

2

いくつかの考え：

ここにあるものと同じくらい頻繁に何かが繰り返されるのを見るときはいつでもMath.ceil(N/2)、それは独自の名前付き変数を持つことを正当化すると思います。(変数に名前を付けるのは必ずしも簡単ではないことはわかっていますが、読みやすくするためには不可欠です。)

Complex A0[] = new Complex[((int) Math.ceil(N/2))];
Complex A1[] = new Complex[((int) Math.ceil(N/2))];

N==1の場合、計算結果は になることに注意してくださいnew Complex[0]。N == 1これが何をするのかはわかりませんが、メモリ割り当ての前に基本ケースのチェックを行うと思います。

Complex[] y0 = new Complex[((int) Math.ceil(N/2))];
Complex[] y1 = new Complex[((int) Math.ceil(N/2))];
/* ... */
    y0 = FFT(A0, N/2);
    y1 = FFT(A1, N/2);

new Complex[...]これらの配列には実際には何も格納しないため、これらの配列の割り当てをスキップできると思います。

Complex[] omega = new Complex[N];
/* ... */
        omega[0] = omega[0].times(omega[N]);

これがまだ爆発していないことに驚いています。例外が発生omega[N]するはずです。IndexOutOfBounds

于 2011-12-24T00:45:46.983 に答える
1

飛び出す問題：

  1. (int) Math.ceil(N/2)あなたはまだint除算を行っているので、Math.ceil()は効果がなく、分割配列はおそらく奇数に対して正しくありませんn
  2. あなたは と にしかデータを入力omega[0]しませomega[N-1]ん。NullPointerExceptionomega[1]N >= 6
  3. omega[N]、sarnold によっても言及されているように
  4. と を割り当てA0、A1後で の結果を割り当てます。splitInput
于 2011-12-24T00:46:44.300 に答える