biz.source_code.dsp.transform

Class Dft

java.lang.Object

biz.source_code.dsp.transform.Dft

public class Dft
extends Object

Discrete Fourier transform (DFT).

This class contains a collection of DFT-related methods. The current version is not yet a complete implementation of all the classic DFT functions and focuses on the conversion between a real signal and a complex spectrum.

See this Stackexchange entry for a discussion of magnitude normalization.

Constructor Summary

Constructors

Constructor and Description
Dft()

Method Summary

Modifier and Type	Method and Description
static Complex[]	directDft(double[] x) Computes the DFT on an array of real numbers and returns the complex result.
static Complex	directDftSingle(double[] x, int pos, int len, int relativeFrequency, boolean normalize) Computes the DFT on real numbers for a single frequency.
static Complex[]	directDftSpectrum(double[] x) Computes the DFT on an array of real numbers and returns the complex spectrum.
static Complex[]	goertzel(double[] x) Computes the DFT on an array of real numbers and returns the complex result.
static Complex	goertzelSingle(double[] x, int pos, int len, int relativeFrequency, boolean normalize) Computes the DFT on real numbers for a single frequency.
static Complex[]	goertzelSpectrum(double[] x) Computes the DFT on an array of real numbers and returns the complex spectrum.
static double[]	synthesizeFromSpectrum(Complex[] x, boolean odd) Computes a kind of inverse DFT on an array of complex numbers that represent a spectrum, and returns the result as an array of real numbers.

Methods inherited from class java.lang.Object

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

Constructor Detail

Dft

public Dft()

Method Detail

directDftSingle

public static Complex directDftSingle(double[] x,
                                      int pos,
                                      int len,
                                      int relativeFrequency,
                                      boolean normalize)

Computes the DFT on real numbers for a single frequency.

This is a reference implementation without any optimization. It's simple to understand, but slow.

Parameters:

x - The input values (samples).

pos - The index of the first value in x to be processed.

len - The number of values in x to be processed, starting at pos.

relativeFrequency - A frequency relative to len. It represents the number of sinusoidal oscillations within len and is normally within the range 0 (for DC) to len / 2. The absolute frequency is relativeFrequency * samplingRate / len.

normalize - true to normalize the magnitude of the result, so that it represents the amplitude of the sinusoidal frequency component.

Returns:

A complex number that corresponds to the amplitude and phase of a sinusoidal frequency component.

goertzelSingle

public static Complex goertzelSingle(double[] x,
                                     int pos,
                                     int len,
                                     int relativeFrequency,
                                     boolean normalize)

Computes the DFT on real numbers for a single frequency.

This version uses the Goertzel algorithm to compute the DFT. It produces the same results as directDft(double[]), but it's much faster.

Parameters:

x - The input values (samples).

pos - The index of the first value in x to be processed.

len - The number of values in x to be processed, starting at pos.

relativeFrequency - A frequency relative to len. It represents the number of sinusoidal oscillations within len and is normally within the range 0 (for DC) to len / 2. The absolute frequency is relativeFrequency * samplingRate / len.

normalize - true to normalize the magnitude of the result, so that it represents the amplitude of the sinusoidal frequency component.

Returns:

A complex number that corresponds to the amplitude and phase of a sinusoidal frequency component.

directDft

public static Complex[] directDft(double[] x)

Computes the DFT on an array of real numbers and returns the complex result.

This method calls directDftSingle(double[], int, int, int, boolean) with normalize = false.

Parameters:

x - The input values (samples).

Returns:

An array of complex numbers. It has the same size as the input array. The upper half of the array contains complex conjugates of the lower half.

goertzel

public static Complex[] goertzel(double[] x)

Computes the DFT on an array of real numbers and returns the complex result.

This method calls goertzelSingle(double[], int, int, int, boolean) with normalize = false.

Parameters:

x - The input values (samples).

Returns:

An array of complex numbers. It has the same size as the input array. The upper half of the array contains complex conjugates of the lower half.

directDftSpectrum

public static Complex[] directDftSpectrum(double[] x)

Computes the DFT on an array of real numbers and returns the complex spectrum.

This method calls directDftSingle(double[], int, int, int, boolean) with normalize = true for the frequencies from 0 to x.length / 2.

See synthesizeFromSpectrum(biz.source_code.dsp.math.Complex[], boolean) for the inverse function.

Parameters:

x - The input values (samples).

Returns:

An array of complex numbers that represent the amplitudes and phases of the sinusoidal frequency components. This is the normalized lower half of the DFT output.

goertzelSpectrum

public static Complex[] goertzelSpectrum(double[] x)

Computes the DFT on an array of real numbers and returns the complex spectrum.

This method calls goertzelSingle(double[], int, int, int, boolean) with normalize = true for the frequencies from 0 to x.length / 2.

See synthesizeFromSpectrum(biz.source_code.dsp.math.Complex[], boolean) for the inverse function.

Parameters:

x - The input values (samples).

Returns:

An array of complex numbers that represent the amplitudes and phases of the sinusoidal frequency components. This is the normalized lower half of the DFT output.

synthesizeFromSpectrum

public static double[] synthesizeFromSpectrum(Complex[] x,
                                              boolean odd)

Computes a kind of inverse DFT on an array of complex numbers that represent a spectrum, and returns the result as an array of real numbers.

This is a reference implementation without any optimization. It's simple to understand, but slow.

This is the inverse function for directDftSpectrum(double[]) and goertzelSpectrum(double[]).

Parameters:

x - Complex numbers that define the amplitudes and phases of the sinusoidal frequency components.

odd - If odd is true, 2 * x.length - 1 output values are generated. Otherwise 2 * x.length - 2 output values are generated.

Returns:

The sampled signal that is the sum of the sinusoidal components.