在Java中可靠和快速的FFT
因为我不想自己做，我正在寻找一个很好的Java的FFT实现。 首先，我在这里使用了FFT Princeton，但是它使用了对象，我的分析器告诉我，由于这个事实，它不是很快。 所以我再次search，发现这一个： FFT哥伦比亚更快。 也许你们中的一个人知道另一个FFT实现？ 我想有一个“最好”的，因为我的应用程序必须处理大量的声音数据，用户不喜欢等待… 😉
问候。
在晚会之后 – 这里作为纯JN解决scheme的那些JNI不是一个选项。 JTransforms
我在Java中为FFT写了一个函数： http : //www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29
它在公共领域，所以你可以在任何地方使用这些function（个人或商业项目）。 只要引用我的信用，只给我一个工作的链接，你没事的。
这是完全可靠的。 我已经检查了它的输出与Mathematica的FFT，他们一直是正确的，直到十五位十进制数字。 我认为这是Java的一个很好的FFT实现。 我把它写在J2SE 1.6版本上，并在J2SE 1.5-1.6版本上进行了testing。
如果你计算指令的数量（这比完美的计算复杂度函数估计简单得多），你可以清楚地看到，即使它没有被优化，这个版本也是很好的。 如果有足够的请求，我打算发布优化版本。
让我知道它是否有用，并告诉我你的任何评论。
我在这里分享相同的代码：
/** * @author Orlando Selenu * */ public class FFTbase { /** * The Fast Fourier Transform (generic version, with NO optimizations). * * @param inputReal * an array of length n, the real part * @param inputImag * an array of length n, the imaginary part * @param DIRECT * TRUE = direct transform, FALSE = inverse transform * @return a new array of length 2n */ public static double[] fft(final double[] inputReal, double[] inputImag, boolean DIRECT) { // - n is the dimension of the problem // - nu is its logarithm in base e int n = inputReal.length; // If n is a power of 2, then ld is an integer (_without_ decimals) double ld = Math.log(n) / Math.log(2.0); // Here I check if n is a power of 2. If exist decimals in ld, I quit // from the function returning null. if (((int) ld) - ld != 0) { System.out.println("The number of elements is not a power of 2."); return null; } // Declaration and initialization of the variables // ld should be an integer, actually, so I don't lose any information in // the cast int nu = (int) ld; int n2 = n / 2; int nu1 = nu - 1; double[] xReal = new double[n]; double[] xImag = new double[n]; double tReal, tImag, p, arg, c, s; // Here I check if I'm going to do the direct transform or the inverse // transform. double constant; if (DIRECT) constant = -2 * Math.PI; else constant = 2 * Math.PI; // I don't want to overwrite the input arrays, so here I copy them. This // choice adds \Theta(2n) to the complexity. for (int i = 0; i < n; i++) { xReal[i] = inputReal[i]; xImag[i] = inputImag[i]; } // First phase - calculation int k = 0; for (int l = 1; l <= nu; l++) { while (k < n) { for (int i = 1; i <= n2; i++) { p = bitreverseReference(k >> nu1, nu); // direct FFT or inverse FFT arg = constant * p / n; c = Math.cos(arg); s = Math.sin(arg); tReal = xReal[k + n2] * c + xImag[k + n2] * s; tImag = xImag[k + n2] * c - xReal[k + n2] * s; xReal[k + n2] = xReal[k] - tReal; xImag[k + n2] = xImag[k] - tImag; xReal[k] += tReal; xImag[k] += tImag; k++; } k += n2; } k = 0; nu1--; n2 /= 2; } // Second phase - recombination k = 0; int r; while (k < n) { r = bitreverseReference(k, nu); if (r > k) { tReal = xReal[k]; tImag = xImag[k]; xReal[k] = xReal[r]; xImag[k] = xImag[r]; xReal[r] = tReal; xImag[r] = tImag; } k++; } // Here I have to mix xReal and xImag to have an array (yes, it should // be possible to do this stuff in the earlier parts of the code, but // it's here to readibility). double[] newArray = new double[xReal.length * 2]; double radice = 1 / Math.sqrt(n); for (int i = 0; i < newArray.length; i += 2) { int i2 = i / 2; // I used Stephen Wolfram's Mathematica as a reference so I'm going // to normalize the output while I'm copying the elements. newArray[i] = xReal[i2] * radice; newArray[i + 1] = xImag[i2] * radice; } return newArray; } /** * The reference bitreverse function. */ private static int bitreverseReference(int j, int nu) { int j2; int j1 = j; int k = 0; for (int i = 1; i <= nu; i++) { j2 = j1 / 2; k = 2 * k + j1 - 2 * j2; j1 = j2; } return k; } } 我想这取决于你正在处理的是什么。 如果你正在计算一个很长的FFT时间，你可能会发现它需要一段时间，取决于你想要的频率点数。 然而，在大多数情况下，audio被认为是非平稳的（即信号均值和方差随时间变化很大），所以采用一个大的FFT（ 周期图PSD估计）不是一个精确的表示。 或者，您可以使用短时傅立叶变换，从而将信号分解成更小的帧并计算FFT。 帧大小取决于统计数据变化的速度，因为语音通常是20-40ms，音乐我认为它略高。
如果您从麦克风采样，此方法很好，因为它允许您一次缓冲每个帧，计算fft并给出用户感觉的是“实时”交互。 因为20ms很快，因为我们不能真正感觉到那么小的时差。
我开发了一个小的基准标记来testing语音信号上的FFTW和KissFFT c-libraries之间的差异。 是的，FFTW是高度优化的，但是当你仅仅使用短帧，为用户更新数据，并且只使用一个很小的尺寸时，它们都非常相似。 这里是一个关于如何在 badlogic游戏中使用LibGdx实现Android中的KissFFT库的例子。 我在几个月前开发的Android应用程序中使用重叠框架实现了这个库，称为Speech Enhancement for Android 。
我正在研究在Java中使用SSTJ进行FFT。 如果库可用，它可以通过JNIredirect到FFTW ，否则将使用纯Java实现。
