2

我目前正在为 Android 开发 Java。我尝试实现 FFT 以实现一种频率查看器。

实际上我能够做到，但显示根本不流畅。我添加了一些跟踪以检查代码每个部分的处理时间，事实是 FFT 需要大约 300 毫秒才能应用于我的复杂数组，它拥有 4096 个元素。而且我需要它花费不到 100 毫秒，因为我的线程（显示频率）每 100 毫秒刷新一次。我减少了初始数组，以便 FFT 结果只拥有 1028 个元素，并且它可以工作，但结果已被弃用。

有人有想法吗？

我使用了可以在 Internet 上找到的默认 fft.java 和 Complex.java 类。

有关信息，我计算 FFT 的代码如下：

int bytesPerSample = 2;
Complex[] x = new Complex[bufferSize/2] ;

for (int index = 0 ; index < bufferReadResult - bytesPerSample + 1; index += bytesPerSample)
{
// 16BITS = 2BYTES

    float asFloat = Float.intBitsToFloat(asInt);


    double sample = 0;
    for (int b = 0; b < bytesPerSample; b++) {
        int v = buffer[index + b];
        if (b < bytesPerSample - 1 || bytesPerSample == 1) {
                v &= 0xFF;
        }
                        sample += v << (b * 8);
     }

    double sample32 = 100 * (sample / 32768.0); // don't know the use of this compute...
    x[index/bytesPerSample] = new Complex(sample32, 0);
}


    Complex[] tx = new Complex[1024]; // size = 2048 

///// reduction of the size of the signal in order to improve the fft traitment time
for (int i = 0; i < x.length/4; i++)
{

    tx[i] = new Complex(x[i*4].re(), 0);

 }

// Signal retrieval thanks to the FFT
fftRes = FFT.fft(tx);
4

3 回答 3

2

我不了解 Java，但是您在输入数据和复杂值数组之间进行转换的方式似乎非常复杂。您正在构建两个复杂数据数组，其中只需要一个。

此外，它闻起来像您的复杂实部和虚部值是双倍的。这远远超出了您的需求，无论如何，ARM 在双算术方面的速度非常慢。是否有基于单精度浮点数的复杂类？

第三，您通过用零填充复数的虚部来对真实数据执行复数 fft。虽然结果是正确的，但它的工作量是直接的两倍（除非程序足够聪明，可以发现这一点，我对此表示怀疑）。如果可能的话，对您的数据执行真正的 fft 并节省一半的时间。

然后正如西蒙所说，整个问题就是避免垃圾收集和内存分配。

此外，您的 FFT 似乎没有准备步骤。这意味着例程 FFT.fft() 每次都在计算复指数。FFT 计算中最长的部分是计算复指数，这是一种耻辱，因为对于任何给定的 FFT 长度，指数都是常数。它们根本不依赖于您的输入数据。在实时世界中，我们使用 FFT 例程，我们在程序开始时计算一次指数，然后实际的 fft 本身将该 const 数组作为其输入之一。不知道你的 FFT 类是否可以做类似的事情。

如果你最终会使用 FFTW 之类的东西，那么你将不得不习惯于从 Java 调用 C 代码。还要确保您获得的版本支持（我认为）NEON、ARM 对 SSE、AVX 和 Altivec 的回答。值得仔细阅读他们的发行说明来检查。此外，我强烈怀疑 FFTW 只有在您要求它对单精度浮点数而不是双精度浮点数执行 FFT 时才能显着提高速度。

谷歌运气！

- 编辑 -

我的意思当然是“祝你好运”。快给我一个真正的键盘，这些触摸屏的不可靠......

于 2013-04-01T05:25:23.300 回答
0

First, thanks for all your answers. I followed them and made two test :

  • first one, I replace the double used in my Complex class by float. The result is just a bit better, but not enough.

  • then I've rewroten the fft method in order not to use Complex anymore, but a two-dimensional float array instead. For each row of this array, the first column contains the real part, and the second one the imaginary part. I also changed my code in order to instanciate the float array only once, on the onCreate method.

And the result... is worst !! Now it takes a little bit more than 500ms instead of 300ms. I don't know what to do now.

You can find below the initial fft fonction, and then the one I've re-wroten. Thanks for your help.

// compute the FFT of x[], assuming its length is a power of 2
public static Complex[] fft(Complex[] x) {
    int N = x.length;

    // base case
    if (N == 1) return new Complex[] { x[0] };

    // radix 2 Cooley-Tukey FFT
    if (N % 2 != 0) { throw new RuntimeException("N is not a power of 2 : " + N); }

    // fft of even terms
    Complex[] even = new Complex[N/2];
    for (int k = 0; k < N/2; k++) {
        even[k] = x[2*k];
    }
    Complex[] q = fft(even);

    // fft of odd terms
    Complex[] odd  = even;  // reuse the array
    for (int k = 0; k < N/2; k++) {
        odd[k] = x[2*k + 1];
    }
    Complex[] r = fft(odd);

    // combine
    Complex[] y = new Complex[N];
    for (int k = 0; k < N/2; k++) {
        double kth = -2 * k * Math.PI / N;
        Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
        y[k]       = q[k].plus(wk.times(r[k]));
        y[k + N/2] = q[k].minus(wk.times(r[k]));
    }

    return y;
}

public static float[][] fftf(float[][] x) {
    /**
     *  x[][0] = real part
     *  x[][1] = imaginary part
     */

    int N = x.length;

    // base case
    if (N == 1) return new float[][] { x[0] };

    // radix 2 Cooley-Tukey FFT
    if (N % 2 != 0) { throw new RuntimeException("N is not a power of 2 : " + N); }

    // fft of even terms
    float[][] even = new float[N/2][2];
    for (int k = 0; k < N/2; k++) {
        even[k] = x[2*k];
    }
    float[][] q = fftf(even);

    // fft of odd terms
    float[][] odd  = even;  // reuse the array
    for (int k = 0; k < N/2; k++) {
        odd[k] = x[2*k + 1];
    }
    float[][] r = fftf(odd);

    // combine
    float[][] y = new float[N][2];
    double kth, wkcos, wksin    ;
    for (int k = 0; k < N/2; k++) {
        kth = -2 * k * Math.PI / N;
        //Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
        wkcos = Math.cos(kth)   ;   // real part
        wksin = Math.sin(kth)   ;   // imaginary part

        //  y[k]       = q[k].plus(wk.times(r[k]));
        y[k][0] = (float) (q[k][0] + wkcos * r[k][0] - wksin * r[k][1]);
        y[k][1] = (float) (q[k][1] + wkcos * r[k][1] + wksin * r[k][0]);

        //  y[k + N/2] = q[k].minus(wk.times(r[k]));
        y[k + N/2][0] = (float) (q[k][0] - (wkcos * r[k][0] - wksin * r[k][1]));
        y[k + N/2][1] = (float) (q[k][1] - (wkcos * r[k][1] + wksin * r[k][0]));
    }

    return y;
}
于 2013-04-01T14:37:14.890 回答
0

其实我想我不明白一切。

  • 首先，关于 Math.cos 和 Math.sin ：你希望我如何不每次都计算它？你的意思是我应该只实例化整个值一次（例如将它存储在一个数组中）并将它们用于每个计算？
  • 其次，关于N % 2，确实不是很有用，我可以在函数调用之前进行测试。
  • 第三，关于西蒙的建议：我把他说的和你说的混在一起了，这就是为什么我用二维float[][]代替了Complex。如果这不是他的建议，那是什么？
  • 至少，我不是 FFT 专家，那么制作“真正的 FFT”是什么意思？你的意思是我的虚部没用？如果是这样，我不确定，因为稍后在我的代码中，我计算每个频率的幅度，所以 sqrt(real[i]*real[i] + imag[i]*imag[i])。而且我认为我的虚部不等于零...

谢谢 ！

于 2013-04-01T22:31:24.223 回答