com.dixshtix.soundlab
Class FFTEngine

java.lang.Object
  |
  +--com.dixshtix.soundlab.FFTEngine

public class FFTEngine

extends java.lang.Object

Routines to implement high-performance Fourier transforms. These routines are optimized for accuracy, and are dependent on tables for most of their trig manipulations. One machines where sqrt() is faster than cos() and sin(), a modest improvement in efficiency over non-table-based routines has been observed.

Specifically, the Fourier Transforms here have been benchmarked to be more accurate at the reconstructions of white noise data than the popular Numerical Recipes routines that use trigonometric identities to speed up calculations of cosine and sine functions. Such identities are not numerically accurate on IEEE numbers and and can result in inconvenient errors at very large powers of two.

Normalization conventions adopted here put all scalar multiplication in the inverse transform. This must be accounted for in convolution routines.

Field Summary

private static int[][]	brtCache Bit-reversal table cache.
private static double[][]	trigCache Trigonometric table cache, ideally resulting in speed-ups.
(package private) static double	TWOPI Fast access to the constant: 2π.

Constructor Summary

FFTEngine()

Method Summary

static void	clearCache() Clear all caches.
private static double	cos(int index, int n, double[] table) Fast computation of cosine.
private static int[]	createBitReversalTable(int n) Create a bit-reversal table.
private static double[]	createTrigTable(int n) Create a trigonometric table.
static void	fft(double[] data, boolean isInverse) Replaces complex data[] by its discrete Fourier transform, if isInverse is false; or replaces data[] by its inverse discrete Fourier transform, if isInverse is true.
static void	fft1(double[] data, int nn, int isign) to be removed.
private static int[]	getBitReversalTable(int n, int m) Retrieve a (potentially) cached bit-reversal table.
private static double[]	getTrigTable(int n, int m) Retrieve a (potentially) cached trigonometric table.
private static int	logBaseTwo(int n) Compute the log base two.
static void	main(java.lang.String[] args) Test accuracy of fft routines.
static void	realFFT(double[] data) Calculates the Fourier Transform of a set of real data points.
static void	realfft(double[] data, boolean isInverse) Calculates the Fourier Transform of a set of real data points.
static void	realInverseFFT(double[] data) Calculates the Inverse Fourier Transform of a set of complex data points representing the complex positive frequencies.
private static double	sin(int index, int n, double[] table) Fast computation of sine.
private static void	swap(double[] array, int a, int b) Utility to swap two entries in an array.

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait

Field Detail

brtCache

private static int[][] brtCache

Bit-reversal table cache.

trigCache

private static double[][] trigCache

Trigonometric table cache, ideally resulting in speed-ups.

TWOPI

static double TWOPI

Fast access to the constant: 2π.

Constructor Detail

FFTEngine

public FFTEngine()

Method Detail

clearCache

public static final void clearCache()

Clear all caches.

swap

private static final void swap(double[] array,
                               int a,
                               int b)

Utility to swap two entries in an array.

logBaseTwo

private static final int logBaseTwo(int n)
                             throws java.lang.Exception

Compute the log base two.

Parameters:

n - A perfect power of two.

Throws:

java.lang.Exception - in the case n is not a perfect power of 2.

createBitReversalTable

private static final int[] createBitReversalTable(int n)

Create a bit-reversal table.

Parameters:

n - A perfect power of two.

getBitReversalTable

private static final int[] getBitReversalTable(int n,
                                               int m)

Retrieve a (potentially) cached bit-reversal table.

Parameters:

n - A perfect power of two.

m - Log base 2 of n.

createTrigTable

private static final double[] createTrigTable(int n)

Create a trigonometric table.

Parameters:

n - A perfect power of two.

cos

private static final double cos(int index,
                                int n,
                                double[] table)

Fast computation of cosine. Computes cosine(PI * index / n).

Parameters:

index - in the range 0 .. n

n - A power of 2.

table - As returned by getTrigTable(n, logBaseTwo(n)).

sin

private static final double sin(int index,
                                int n,
                                double[] table)

Fast computation of sine. Computes sine(PI * index / n).

Parameters:

index - in the range 0 .. n

n - A power of 2.

table - As returned by getTrigTable(n, logBaseTwo(n)).

getTrigTable

private static final double[] getTrigTable(int n,
                                           int m)

Retrieve a (potentially) cached trigonometric table.

Parameters:

n - A perfect power of two.

m - Log base 2 of n.

fft

public static void fft(double[] data,
                       boolean isInverse)
                throws java.lang.Exception

Replaces complex data[] by its discrete Fourier transform, if isInverse is false; or replaces data[] by its inverse discrete Fourier transform, if isInverse is true. data[] is a complex array of a length which MUST be an integer power of 2.

fft1

public static void fft1(double[] data,
                        int nn,
                        int isign)

to be removed.

realFFT

public static void realFFT(double[] data)
                    throws java.lang.Exception

Calculates the Fourier Transform of a set of real data points. Returns the complex positive frequencies. data[0] is the DC components, data[1] is the (real) Nyquist component.

realInverseFFT

public static void realInverseFFT(double[] data)
                           throws java.lang.Exception

Calculates the Inverse Fourier Transform of a set of complex data points representing the complex positive frequencies. data[0] is the DC component, data[1] is the Nyquist component. data[2] + i data[3] is the positive frequency corresponding to the fundamental frequency. Returns a real array, in place.

realfft

public static void realfft(double[] data,
                           boolean isInverse)
                    throws java.lang.Exception

Calculates the Fourier Transform of a set of real data points. If isInverse is false, returns the complex positive frequencies. data[0] is the DC components, data[1] is the (real) Nyquist component.

main

public static void main(java.lang.String[] args)

Test accuracy of fft routines.