因为我不想自己实现，所以我正在寻找一个好的Java FFT实现。首先我使用了这个Princeton FFT，但是我的分析器告诉我，由于它使用对象，它并不真正快速。所以我又谷歌了一下，找到了这个Columbia FFT，它更快。也许你们中的某一个知道另一个FFT实现？我想要“最好”的一个，因为我的应用程序需要处理大量的声音数据，用户不喜欢等待... ;-)
祝好。
5个回答
32
- Kieren Johnstone
4
看起来很有趣，我稍后会去查看。 :) - InsertNickHere
我已经接受了你的答案，尽管我没有使用它，但很多人都参考了这个库。 - InsertNickHere
4注意，FFTW受GPL许可证保护。（提供非自由版本，使用限制更少的许可证） - Jason S
6Apache Commons的FastFourierTransformer类怎么样？ - kamaci
21
对于那些不能使用JNI的纯Java解决方案，这里提供了一个迟到的选择。JTransforms
- basszero
1
JTransforms的API不如Apache Commons FastFourierTransformer好用，但速度更快。 - Bohumir Zamecnik
16
我在Java中编写了一个FFT函数。
我已经将它发布到公共领域，所以你可以在任何地方使用这些函数（包括个人或商业项目）。只需在致谢中引用我的名字并发送给我你的作品链接，就可以了。
这个函数非常可靠。我已经将它的输出与Mathematica的FFT进行了对比，一直到小数点后第15位都是正确的。我认为这是一个非常出色的Java FFT实现。我在J2SE 1.6版本上编写并在J2SE 1.5-1.6版本上进行了测试。
如果你计算指令的数量（它比完美的计算复杂度函数估计要简单得多），你会清楚地看到，即使这个版本没有经过任何优化，它仍然非常出色。如果有足够的需求，我计划发布优化版本。
如果对你有帮助，请告诉我，并随意提出任何评论。
我在这里分享相同的代码：
/**
* @author Orlando Selenu
* Originally written in the Summer of 2008
* Based on the algorithms originally published by E. Oran Brigham "The Fast Fourier Transform" 1973, in ALGOL60 and FORTRAN
*/
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 readability).
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 bit reverse 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;
}
}
编辑：2022年5月5日。嗯...超过10年后，我将代码发布到GitHub上，以免丢失：https://github.com/hedoluna/fft 欢迎大家贡献和给我发送意见 :) 谢谢！
- alcor
8
1请问您能在网页上说明许可证吗？另外，请说明您希望如何引用。 - stackoverflowuser2010
1嗨@stackoverflowuser2010，许可证在http://www.wikijava.org/wiki/WikiJava:GFDL，所以只需链接到代码，并写上我的名字（Orlando Selenu）：）你的项目是什么？ - alcor
谢谢。正在开发Android应用，需要一个FFT实现。 - stackoverflowuser2010
报告一个损坏的链接 - meet thakkar
谢谢@meetthakkar，我会尽快恢复它。与此同时，您可以在这里找到它：https://web.archive.org/web/20150922044939/http://www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29 - alcor
显示剩余3条评论
6
我猜这取决于你正在处理什么。如果你要计算一个较长时间内的FFT，你可能会发现它需要一些时间，这取决于你想要多少频率点。然而，在大多数音频情况下，它被认为是非平稳的（也就是说，信号的均值和方差随时间变化太大），因此进行一次大的FFT（周期图PSD估计）并不是准确的表示。相反，你可以使用短时傅里叶变换，将信号分成较小的帧并计算FFT。帧大小取决于统计数据变化的速度，对于语音通常为20-40毫秒，对于音乐我认为略高一些。
如果你从麦克风采样，这种方法很好，因为它允许你每次缓冲一个帧，计算FFT并提供用户感觉是“实时”的交互。因为20毫秒很快，我们无法真正感知到这么小的时间差异。
我开发了一个小型基准测试，用于测试FFTW和KissFFT C库在语音信号上的差异。是的，FFTW经过高度优化，但当您只使用短帧、为用户更新数据并仅使用小fft大小时，它们非常相似。这里有一个示例，演示如何使用badlogic games的LibGdx在Android上实现KissFFT库。我在几个月前开发的一个名为Speech Enhancement for Android的Android应用程序中，使用重叠帧实现了该库。
如果你从麦克风采样，这种方法很好，因为它允许你每次缓冲一个帧，计算FFT并提供用户感觉是“实时”的交互。因为20毫秒很快，我们无法真正感知到这么小的时间差异。
我开发了一个小型基准测试，用于测试FFTW和KissFFT C库在语音信号上的差异。是的，FFTW经过高度优化，但当您只使用短帧、为用户更新数据并仅使用小fft大小时，它们非常相似。这里有一个示例，演示如何使用badlogic games的LibGdx在Android上实现KissFFT库。我在几个月前开发的一个名为Speech Enhancement for Android的Android应用程序中，使用重叠帧实现了该库。
- digiphd
4
- Jay R.
2
@JasonS 我纠正了他的链接。 - alcor
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接