Class DiscreteFourierTransform
- All Implemented Interfaces:
DataTransform<Access1D<?>,
MatrixStore<ComplexNumber>>
- Direct Known Subclasses:
DiscreteFourierTransform.FFT
,DiscreteFourierTransform.FullMatrix
,DiscreteFourierTransform.Single
The fast Fourier transform (FFT) is an algorithm for computing the DFT; it achieves its high speed by storing and reusing results of computations as it progresses.
Calling the factory method newInstance(int) will return an FFT implementation if the size is a power of 2, and a full matrix implementation otherwise.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic final class
(package private) static final class
(package private) static final class
(package private) static final class
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final int[][]
(package private) static final DiscreteFourierTransform.Directive
(package private) static final DiscreteFourierTransform.Directive
private final int
private static final ComplexNumber[][]
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static void
static int[]
getBitReversedIndices
(int size) static Access1D
<ComplexNumber> getUnitRoots
(int size) final void
inverse
(Access1D<?> input, Mutate2D.ModifiableReceiver<ComplexNumber> output) final MatrixStore
<ComplexNumber> inverse
(Access1D<ComplexNumber> input) static MatrixStore
<ComplexNumber> inverse2D
(MatrixStore<?> input) (package private) static int[]
lookupIndices
(int size) (package private) static ComplexNumber[]
lookupRoots
(int size) private static ComplexNumber[]
lookupRootsExponent
(int exponent) static DiscreteFourierTransform
newInstance
(int size) Will return a functioning instance for any size, but if you want fast transformation (FFT) it needs to be a power of 2.static <M extends Mutate2D>
MnewVandermonde
(Factory2D<M> factory, int size) static MatrixC128
newVandermondeMatrix
(int size) private static void
reverseBits
(int[] indices) Function to perform bit-reversal on indicesstatic MatrixStore
<ComplexNumber> sample
(DoubleUnaryOperator function, PrimitiveFunction.SampleDomain sampleDomain) Sample, and transform, a function using the Discrete Fourier Transform.static MatrixStore
<ComplexNumber> sample
(PeriodicFunction function, int nbSamples) static <N extends Comparable<N>>
MatrixStore<N> shift
(MatrixStore<N> matrix) There is a symmetry in the DFT matrix.(package private) int
size()
(package private) static int
toPowerOf2Exponent
(int size) transform
(double... input) final MatrixStore
<ComplexNumber> abstract void
transform
(Access1D<?> input, DiscreteFourierTransform.Directive directive, Mutate2D.ModifiableReceiver<ComplexNumber> output) final void
transform
(Access1D<?> input, Mutate2D.ModifiableReceiver<ComplexNumber> output) static MatrixStore
<ComplexNumber> transform2D
(MatrixStore<?> input) Perform a 2D Discrete Fourier Transform on the input matrix.static void
transform2D
(MatrixStore<?> input, DiscreteFourierTransform.Directive directive, TransformableRegion<ComplexNumber> output)
-
Field Details
-
BIT_REVERSED_INDICES
private static final int[][] BIT_REVERSED_INDICES -
UNIT_ROOTS
-
DEFAULT
-
INVERSE
-
mySize
private final int mySize
-
-
Constructor Details
-
DiscreteFourierTransform
DiscreteFourierTransform(int size)
-
-
Method Details
-
getBitReversedIndices
public static int[] getBitReversedIndices(int size) -
getUnitRoots
-
inverse2D
-
newInstance
Will return a functioning instance for any size, but if you want fast transformation (FFT) it needs to be a power of 2. -
newVandermonde
-
newVandermondeMatrix
-
sample
public static MatrixStore<ComplexNumber> sample(DoubleUnaryOperator function, PrimitiveFunction.SampleDomain sampleDomain) Sample, and transform, a function using the Discrete Fourier Transform. -
sample
- See Also:
-
shift
There is a symmetry in the DFT matrix. The first half of the rows (and columns) are the complex conjugates of the second half. Furthermore, the first half correspond to positive frequencies, and the second half to negative frequencies.Re-arranging the elements of a matrix, shifting the first and second halves of the rows (and columns), puts the zero-frequency term in the middle, and the conjugate pairs at equal distances from the centre.
This is useful when displaying the 2D DFT matrix as an image.
To revert the shift, simply call shift(MatrixStore) again. However, this will not work correctly if there's an odd number of rows or columns. In that case the second call will not correctly revert the position of the zero-frequency term – it will end up in the last row/column instead of in the first.
-
transform2D
Perform a 2D Discrete Fourier Transform on the input matrix. The output will be a complex matrix of the same size. -
transform2D
public static void transform2D(MatrixStore<?> input, DiscreteFourierTransform.Directive directive, TransformableRegion<ComplexNumber> output) -
lookupRootsExponent
-
reverseBits
private static void reverseBits(int[] indices) Function to perform bit-reversal on indices -
generate
-
lookupIndices
static int[] lookupIndices(int size) -
lookupRoots
-
toPowerOf2Exponent
static int toPowerOf2Exponent(int size) -
inverse
-
inverse
-
transform
- Specified by:
transform
in interfaceDataTransform<Access1D<?>,
MatrixStore<ComplexNumber>>
-
transform
public abstract void transform(Access1D<?> input, DiscreteFourierTransform.Directive directive, Mutate2D.ModifiableReceiver<ComplexNumber> output) -
transform
-
transform
-
size
int size()
-