edu.mines.jtk.dsp
Class FftReal

java.lang.Object
  edu.mines.jtk.dsp.FftReal

public class FftReal
extends java.lang.Object

Fast Fourier transform of real-valued arrays. The FFT length nfft equals the number of real numbers transformed. The transform of nfft real numbers yields nfft/2+1 complex numbers. (The imaginary parts of the first and last complex numbers are always zero.) For real-to-complex and complex-to-real transforms, nfft is always an even number.

Complex numbers are packed into arrays of floats as [real_0, imag_0, real_1, imag_1, ...]. Here, real_k and imag_k correspond to the real and imaginary parts of the complex number with index k.

When input and output arrays are the same array, transforms are performed in-place. For example, an input array rx[nfft] of nfft real numbers may be the same as an output array cy[nfft+2] of nfft/2+1 complex numbers. By "the same array", we mean that rx==cy. In this case, both rx.length and cy.length equal nfft+2. When we write rx[nfft] (here and below), we imply that only the first nfft floats in the input array rx are accessed.

Transforms may be performed for any dimension of a multi-dimensional array. For example, we may transform the 1st dimension of an input array rx[n2][nfft] of n2*nfft real numbers to an output array cy[n2][nfft+2] of n2*(nfft/2+1) complex numbers. Or, we may transform the 2nd dimension of an input array rx[nfft][n1] of nfft*n1 real numbers to an output array cy[nfft/2+1][2*n1] of (nfft/2+1)*n1 complex numbers. In either case, the input array rx and the output array cy may be the same array, such that the transform may be performed in-place.

In-place transforms are typically used to reduce memory consumption. Note, however, that memory consumption is reduced for only dimension-1 in-place transforms. Dimension-2 (and higher) in-place transforms save no memory, because of the contiguous packing of real and imaginary parts of complex numbers in multi-dimensional arrays of floats. (See above.) Therefore, dimension-1 transforms are best when performing real-to-complex or complex-to-real transforms of multi-dimensional arrays.

Version:

2005.03.21

Author:

Dave Hale, Colorado School of Mines

Constructor Summary

FftReal(int nfft)
Constructs a new FFT, with specified length.

Method Summary

void	complexToReal(int sign, float[] cx, float[] ry) Computes a complex-to-real fast Fourier transform.
void	complexToReal1(int sign, int n2, float[][] cx, float[][] ry) Computes a complex-to-real dimension-1 fast Fourier transform.
void	complexToReal1(int sign, int n2, int n3, float[][][] cx, float[][][] ry) Computes a complex-to-real dimension-1 fast Fourier transform.
void	complexToReal2(int sign, int n1, float[][] cx, float[][] ry) Computes a complex-to-real dimension-2 fast Fourier transform.
int	getNfft() Gets the FFT length nfft for this FFT.
static int	nfftFast(int n) Returns an FFT length optimized for speed.
static int	nfftSmall(int n) Returns an FFT length optimized for memory.
void	realToComplex(int sign, float[] rx, float[] cy) Computes a real-to-complex fast Fourier transform.
void	realToComplex1(int sign, int n2, float[][] rx, float[][] cy) Computes a real-to-complex dimension-1 fast Fourier transform.
void	realToComplex1(int sign, int n2, int n3, float[][][] rx, float[][][] cy) Computes a real-to-complex dimension-1 fast Fourier transform.
void	realToComplex2(int sign, int n1, float[][] rx, float[][] cy) Computes a real-to-complex dimension-2 fast Fourier transform.
void	scale(int n1, float[] rx) Scales n1 real numbers in the specified array by 1/nfft.
void	scale(int n1, int n2, float[][] rx) Scales n1*n2 real numbers in the specified array by 1/nfft.
void	scale(int n1, int n2, int n3, float[][][] rx) Scales n1*n2*n3 real numbers in the specified array by 1/nfft.

Methods inherited from class java.lang.Object

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

Constructor Detail

FftReal

public FftReal(int nfft)

Constructs a new FFT, with specified length. Valid FFT lengths can be obtained by calling the methods nfftSmall(int) and nfftFast(int).

Parameters:

nfft - the FFT length, which must be valid.

Method Detail

nfftSmall

public static int nfftSmall(int n)

Returns an FFT length optimized for memory. The FFT length will be the smallest valid length that is not less than the specified length n.

Parameters:

n - the lower bound on FFT length.

Returns:

the FFT length.

Throws:

java.lang.IllegalArgumentException - if the specified length n exceeds the maximum length supported by this implementation. Currently, the maximum length is 1,441,440.

nfftFast

public static int nfftFast(int n)

Returns an FFT length optimized for speed. The FFT length will be the fastest valid length that is not less than the specified length n.

Parameters:

n - the lower bound on FFT length.

Returns:

the FFT length.

Throws:

java.lang.IllegalArgumentException - if the specified length n exceeds the maximum length supported by this implementation. Currently, the maximum length is 1,441,440.

getNfft

public int getNfft()

Gets the FFT length nfft for this FFT.

Returns:

the FFT length.

realToComplex

public void realToComplex(int sign,
                          float[] rx,
                          float[] cy)

Computes a real-to-complex fast Fourier transform. Transforms a 1-D input array rx[nfft] of nfft real numbers to a 1-D output array cy[nfft+2] of nfft/2+1 complex numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

rx - the input array.

cy - the output array.

complexToReal

public void complexToReal(int sign,
                          float[] cx,
                          float[] ry)

Computes a complex-to-real fast Fourier transform. Transforms a 1-D input array cx[nfft+2] of nfft/2+1 complex numbers to a 1-D output array ry[nfft] of nfft real numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

cx - the input array.

ry - the output array.

realToComplex1

public void realToComplex1(int sign,
                           int n2,
                           float[][] rx,
                           float[][] cy)

Computes a real-to-complex dimension-1 fast Fourier transform. Transforms a 2-D input array rx[n2][nfft] of n2*nfft real numbers to a 2-D output array cy[n2][nfft+2] of n2*(nfft/2+1) complex numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

n2 - the 2nd dimension of arrays.

rx - the input array.

cy - the output array.

complexToReal1

public void complexToReal1(int sign,
                           int n2,
                           float[][] cx,
                           float[][] ry)

Computes a complex-to-real dimension-1 fast Fourier transform. Transforms a 2-D input array cx[n2][nfft+2] of n2*(nfft/2+1) complex numbers to a 2-D output array ry[n2][nfft] of n2*nfft real numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

n2 - the 2nd dimension of arrays.

cx - the input array.

ry - the output array.

realToComplex2

public void realToComplex2(int sign,
                           int n1,
                           float[][] rx,
                           float[][] cy)

Computes a real-to-complex dimension-2 fast Fourier transform. Transforms a 2-D input array rx[nfft][n1] of nfft*n1 real numbers to a 2-D output array cy[nfft/2+1][2*n1] of (nfft/2+1)*n1 complex numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

n1 - the 1st dimension of arrays.

rx - the input array.

cy - the output array.

complexToReal2

public void complexToReal2(int sign,
                           int n1,
                           float[][] cx,
                           float[][] ry)

Computes a complex-to-real dimension-2 fast Fourier transform. Transforms a 2-D input array cx[nfft/2+1][2*n1] of (nfft/2+1)*n1 complex numbers to a 2-D output array ry[nfft][n1] of nfft*n1 real numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

n1 - the 1st dimension of arrays.

cx - the input array.

ry - the output array.

realToComplex1

public void realToComplex1(int sign,
                           int n2,
                           int n3,
                           float[][][] rx,
                           float[][][] cy)

Computes a real-to-complex dimension-1 fast Fourier transform. Transforms a 3-D input array rx[n3][n2][nfft] of n3*n2*nfft real numbers to a 3-D output array cy[n3][n2][nfft+2] of n3*n2*(nfft/2+1) complex numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

n2 - the 2nd dimension of arrays.

n3 - the 3rd dimension of arrays.

rx - the input array.

cy - the output array.

complexToReal1

public void complexToReal1(int sign,
                           int n2,
                           int n3,
                           float[][][] cx,
                           float[][][] ry)

Computes a complex-to-real dimension-1 fast Fourier transform. Transforms a 3-D input array cx[n3][n2][nfft+2] of n3*n2*(nfft/2+1) complex numbers to a 3-D output array ry[n3][n2][nfft] of n3*n2*nfft real numbers.

Parameters:

sign - the sign (1 or -1) of the exponent used in the FFT.

n2 - the 2nd dimension of arrays.

n3 - the 3rd dimension of arrays.

cx - the input array.

ry - the output array.

scale

public void scale(int n1,
                  float[] rx)

Scales n1 real numbers in the specified array by 1/nfft. The inverse of a real-to-complex FFT is a complex-to-real FFT (with opposite sign) followed by this scaling.

Parameters:

n1 - 1st (only) dimension of the array rx.

rx - the input/output array[n1].

scale

public void scale(int n1,
                  int n2,
                  float[][] rx)

Scales n1*n2 real numbers in the specified array by 1/nfft. The inverse of a real-to-complex FFT is a complex-to-real FFT (with opposite sign) followed by this scaling.

Parameters:

n1 - the 1st dimension of the array rx.

n2 - the 2nd dimension of the array rx.

rx - the input/output array[n2][n1].

scale

public void scale(int n1,
                  int n2,
                  int n3,
                  float[][][] rx)

Scales n1*n2*n3 real numbers in the specified array by 1/nfft. The inverse of a real-to-complex FFT is a complex-to-real FFT (with opposite sign) followed by this scaling.

Parameters:

n1 - the 1st dimension of the array rx.

n2 - the 2nd dimension of the array rx.

n3 - the 3rd dimension of the array rx.

rx - the input/output array[n3][n2][n1].