public class FFT extends Object
FFT
class provides methods for computing the
FFT (Fast-Fourier Transform), inverse FFT, linear convolution,
and circular convolution of a complex array.
It is a bare-bones implementation that runs in n log n time, where n is the length of the complex array. For simplicity, n must be a power of 2. Our goal is to optimize the clarity of the code, rather than performance. It is not the most memory efficient implementation because it uses objects to represent complex numbers and it re-allocates memory for the subarray, instead of doing in-place or reusing a single temporary array.
This computes correct results if all arithmetic performed is without floating-point rounding error or arithmetic overflow. In practice, there will be floating-point rounding error.
For additional documentation, see Section 9.9 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Modifier and Type | Method and Description |
---|---|
static Complex[] |
cconvolve(Complex[] x,
Complex[] y)
Returns the circular convolution of the two specified complex arrays.
|
static Complex[] |
convolve(Complex[] x,
Complex[] y)
Returns the linear convolution of the two specified complex arrays.
|
static Complex[] |
fft(Complex[] x)
Returns the FFT of the specified complex array.
|
static Complex[] |
ifft(Complex[] x)
Returns the inverse FFT of the specified complex array.
|
static void |
main(String[] args)
Unit tests the
FFT class. |
public static Complex[] fft(Complex[] x)
x
- the complex arrayx
IllegalArgumentException
- if the length of x
is not a power of 2public static Complex[] ifft(Complex[] x)
x
- the complex arrayx
IllegalArgumentException
- if the length of x
is not a power of 2public static Complex[] cconvolve(Complex[] x, Complex[] y)
x
- one complex arrayy
- the other complex arrayx
and y
IllegalArgumentException
- if the length of x
does not equal
the length of y
or if the length is not a power of 2public static Complex[] convolve(Complex[] x, Complex[] y)
x
- one complex arrayy
- the other complex arrayx
and y
IllegalArgumentException
- if the length of x
does not equal
the length of y
or if the length is not a power of 2public static void main(String[] args)
FFT
class.args
- the command-line arguments