java - definicion - fftw
FFT confiable y rápida en Java (5)
Escribí una función para la FFT en Java: http://www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29
Está en el dominio público para que pueda usar esas funciones en todas partes (proyectos personales o comerciales también). Solo cíteme en los créditos y envíame solo un enlace de tu trabajo, y estás bien.
Es completamente confiable. Revisé su salida contra la FFT de Mathematica y siempre fueron correctas hasta el decimoquinto dígito decimal. Creo que es una muy buena implementación de FFT para Java. Lo escribí en la versión J2SE 1.6 y lo probé en la versión J2SE 1.5-1.6.
Si cuenta el número de instrucciones (es mucho más simple que una estimación perfecta de la función de complejidad computacional), puede ver claramente que esta versión es excelente, incluso si no está optimizada en absoluto. Estoy planeando publicar la versión optimizada si hay suficientes solicitudes.
Avíseme si fue útil y dígame cualquier comentario que desee.
Comparto el mismo código aquí:
/**
* @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;
}
}
ya que no quiero hacerlo solo, estoy buscando una buena implementación de FFT para Java. Primero usé este aquí FFT Princeton pero usa objetos y mi profiler me dijo que no es realmente rápido debido a este hecho. Así que busqué en Google nuevamente y encontré este: FFT Columbia, que es más rápido. ¿Tal vez alguno de ustedes conoce otra implementación de FFT? Me gustaría tener el "mejor" porque mi aplicación tiene que procesar una gran cantidad de datos de sonido y a los usuarios no les gusta esperar ... ;-)
Saludos.
FFTW es la ''transformada de Fourier más rápida en el oeste'', y tiene algunas envolturas de Java:
¡Espero que ayude!
Supongo que depende de lo que estás procesando. Si está calculando la FFT durante un período prolongado, es posible que tarde un tiempo, dependiendo de la frecuencia que desee. Sin embargo, en la mayoría de los casos para el audio se considera no estacionario (es decir, las señales significan y la varianza cambia a lo largo del tiempo), por lo que tomar una FFT grande ( estimación de PSD del Periodograma ) no es una representación precisa. Alternativamente, podría usar la transformada de Fourier de corta duración, mediante la cual divide la señal en cuadros más pequeños y calcula la FFT. El tamaño del fotograma varía según la velocidad con la que cambian las estadísticas, para el habla suele ser de 20 a 40 ms, para la música supongo que es un poco más alta.
Este método es bueno si está tomando muestras del micrófono, ya que le permite almacenar cada fotograma a la vez, calcular el fft y dar lo que el usuario siente como una interacción en "tiempo real". Porque 20ms es rápido, porque realmente no podemos percibir una diferencia de tiempo tan pequeña.
Desarrollé una pequeña marca de referencia para probar la diferencia entre FFTW y KissFFT c-libraries en una señal de voz. Sí FFTW está muy optimizado, pero cuando solo se toman cuadros cortos, se actualizan los datos para el usuario y se usa solo un tamaño de fft pequeño, ambos son muy similares. Aquí hay un ejemplo de cómo implementar las bibliotecas de KissFFT en Android usando LibGdx por badlogic games. Implementé esta biblioteca usando marcos superpuestos en una aplicación para Android que desarrollé hace unos meses llamada Speech Enhancement para Android .
Tarde a la fiesta, aquí como una solución java pura para aquellos cuando JNI no es una opción. JTransforms