Java中可靠且快速的FFT
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3287518/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Reliable and fast FFT in Java
提问by InsertNickHere
since I don't want to do it on my own, I am searching for a good FFT implementation for java. First I used this one here FFT Princetonbut it uses objects and my profiler told me, that its not really fast due to this fact. So I googled again and found this one: FFT Columbiawhich is faster. Maybe one of you guys know another FFT implementation? I'd like to have the "best" one because my app has to process a huge amount of sound data, and users don't like waiting... ;-)
因为我不想自己做，所以我正在为 java 寻找一个好的 FFT 实现。首先我在这里使用了这个FFT 普林斯顿，但它使用了对象，我的分析器告诉我，由于这个事实，它并不是很快。所以我再次用谷歌搜索并找到了这个：更快的FFT Columbia。也许你们中的一个人知道另一种 FFT 实现？我想要“最好的”，因为我的应用程序必须处理大量的声音数据，而用户不喜欢等待......;-)
Regards.
问候。
采纳答案by Kieren Johnstone
FFTW is the 'fastest fourier transform in the west', and has some Java wrappers:
FFTW 是“西方最快的傅立叶变换”，并且有一些 Java 包装器：
Hope that helps!
希望有帮助！
回答by Jay R.
回答by basszero
Late to the party - here as a pure java solution for those when JNI is not an option.JTransforms
迟到了——这里是一个纯 Java 解决方案，适用于那些无法选择 JNI 的人。J变换
回答by alcor
I wrote a function for the FFT in Java: http://www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29
我用 Java 为 FFT 编写了一个函数：http: //www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29
It's in the Public Domain so you can use those functions everywhere (personal or business projects too). Just cite me in the credits and send me just a link of your work, and you're ok.
它属于公共领域，因此您可以在任何地方使用这些功能（个人或商业项目也是如此）。只需在学分中引用我，然后将您的作品链接发送给我，您就可以了。
It is completely reliable. I've checked its output against the Mathematica's FFT and they were always correct until the 15th decimal digit. I think it's a very good FFT implementation for Java. I wrote it on the J2SE 1.6 version, and tested it on the J2SE 1.5-1.6 version.
这是完全可靠的。我已经根据 Mathematica 的 FFT 检查了它的输出，它们在第 15 位十进制数字之前总是正确的。我认为这是一个非常好的 Java FFT 实现。我是在J2SE 1.6版本上写的，在J2SE 1.5-1.6版本上测试过。
If you count the number of instruction (it's a lot much simpler than a perfect computational complexity function estimation) you can clearly see that this version is great even if it's not optimized at all. I'm planning to publish the optimized version if there are enough requests.
如果您计算指令的数量（它比完美的计算复杂度函数估计要简单得多），您可以清楚地看到这个版本很棒，即使它根本没有优化。如果有足够的请求，我计划发布优化版本。
Let me know if it was useful, and tell me any comment you like.
让我知道它是否有用，并告诉我您喜欢的任何评论。
I share the same code right here:
我在这里分享相同的代码：
/**
* @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;
}
}
回答by digiphd
I guess it depends on what you are processing. If you are calculating the FFT over a large duration you might find that it does take a while depending on how many frequency points you are wanting. However, in most cases for audio it is considered non-stationary (that is the signals mean and variance changes to much over time), so taking one large FFT (Periodogram PSDestimate) is not an accurate representation. Alternatively you could use Short-time Fourier transform, whereby you break the signal up into smaller frames and calculate the FFT. The frame size varies depending on how quickly the statistics change, for speech it is usually 20-40ms, for music I assume it is slightly higher.
我想这取决于您正在处理的内容。如果您在长时间内计算 FFT，您可能会发现它确实需要一段时间，具体取决于您想要的频率点数量。然而，在大多数情况下，音频被认为是非平稳的（即信号均值和方差随时间变化很大），因此采用一个大的 FFT（周期图 PSD估计）并不是一种准确的表示。或者，您可以使用短时傅立叶变换，将信号分解为更小的帧并计算 FFT。帧大小取决于统计数据变化的速度，对于语音，通常为 20-40 毫秒，对于音乐，我认为它略高。
This method is good if you are sampling from the microphone, because it allows you to buffer each frame at a time, calculate the fft and give what the user feels is "real time" interaction. Because 20ms is quick, because we can't really perceive a time difference that small.
如果您从麦克风采样，这种方法很好，因为它允许您一次缓冲每一帧，计算 fft 并给用户感觉是“实时”交互。因为 20ms 很快，因为我们无法真正感知到那么小的时差。
I developed a small bench mark to test the difference between FFTW and KissFFT c-libraries on a speech signal. Yes FFTW is highly optimised, but when you are taking only short-frames, updating the data for the user, and using only a small fft size, they are both very similar. Here is an example on how to implement the KissFFT libraries in Androidusing LibGdx by badlogic games. I implemented this library using overlapping frames in an Android App I developed a few months ago called Speech Enhancement for Android.
我开发了一个小基准来测试语音信号上 FFTW 和 KissFFT c 库之间的差异。是的 FFTW 是高度优化的，但是当您只拍摄短帧、为用户更新数据并且仅使用较小的 fft 大小时，它们都非常相似。下面是一个关于如何通过 badlogic 游戏使用 LibGdx在 Android 中实现KissFFT 库的示例。我在几个月前开发的名为Speech Enhancement for Android的 Android 应用程序中使用重叠帧实现了这个库。
