BGC.Mathematics.Fourier Class Reference

Support for Fourier Transforms. Borrows heavily from Mathnet.Numerics. More...

Collaboration diagram for BGC.Mathematics.Fourier:

Static Public Member Functions
static void	Forward (Complex32[] samples)
static void	Inverse (Complex32[] spectrum)
static void	Forward (Complex64[] samples)
static void	Inverse (Complex64[] spectrum)

Static Private Member Functions
static void	Radix2ForwardParallel (Complex32[] data)
	Radix-2 generic FFT for power-of-two sample vectors (Parallel Version). More...
static void	Radix2InverseParallel (Complex32[] data)
	Radix-2 generic FFT for power-of-two sample vectors (Parallel Version). More...
static void	Radix2Forward (Complex32[] data)
	Radix-2 generic FFT for power-of-two sized sample vectors. More...
static void	Radix2Inverse (Complex32[] data)
	Radix-2 generic FFT for power-of-two sized sample vectors. More...
static void	Radix2Reorder (Complex32[] samples)
	Radix-2 Reorder Helper Method More...
static void	Radix2Step (Complex32[] samples, int exponentSign, int levelSize, int k)
	Radix-2 Step Helper Method More...
static void	BluesteinForward (Complex32[] samples)
static void	BluesteinInverse (Complex32[] spectrum)
	Bluestein generic FFT for arbitrary sized sample vectors. More...
static Complex32 []	BluesteinSequence32 (int n)
	Generate the bluestein sequence for the provided problem size. More...
static void	Radix2ForwardParallel (Complex64[] data)
	Radix-2 generic FFT for power-of-two sample vectors (Parallel Version). More...
static void	Radix2InverseParallel (Complex64[] data)
	Radix-2 generic FFT for power-of-two sample vectors (Parallel Version). More...
static void	Radix2Forward (Complex64[] data)
	Radix-2 generic FFT for power-of-two sized sample vectors. More...
static void	Radix2Inverse (Complex64[] data)
	Radix-2 generic FFT for power-of-two sized sample vectors. More...
static void	Radix2Reorder (Complex64[] samples)
	Radix-2 Reorder Helper Method More...
static void	Radix2Step (Complex64[] samples, int exponentSign, int levelSize, int k)
	Radix-2 Step Helper Method More...
static void	BluesteinForward (Complex64[] samples)
static void	BluesteinInverse (Complex64[] spectrum)
	Bluestein generic FFT for arbitrary sized sample vectors. More...
static Complex64 []	BluesteinSequence64 (int n)
	Generate the bluestein sequence for the provided problem size. More...
static void	Rescale (Complex32[] samples)
	Fully rescale the FFT result. More...
static void	Rescale (Complex64[] samples)
	Fully rescale the FFT result. More...
static void	SwapRealImaginary (Complex32[] samples)
	Swap the real and imaginary parts of each sample. More...
static void	SwapRealImaginary (Complex64[] samples)
	Swap the real and imaginary parts of each sample. More...

Private Attributes
const int	BluesteinSequenceLengthThreshold = 46341
	Sequences with length greater than Math.Sqrt(Int32.MaxValue) + 1 will cause k*k in the Bluestein sequence to overflow (GH-286). More...

Detailed Description

Support for Fourier Transforms. Borrows heavily from Mathnet.Numerics.

Definition at line 41 of file Fourier.cs.

Member Function Documentation

BluesteinForward() [1/2]

static void BGC.Mathematics.Fourier.BluesteinForward ( Complex32 []  samples )

inlinestaticprivate

Definition at line 250 of file Fourier.cs.

References BGC.Mathematics.Complex32.Conjugate().

        {
            int n = samples.Length;
            Complex32[] sequence = BluesteinSequence32(n);

            // Padding to power of two >= 2N–1 so we can apply Radix-2 FFT.
            int m = ((n << 1) - 1).CeilingToPowerOfTwo();
            Complex32[] b = new Complex32[m];
            Complex32[] a = new Complex32[m];

            CommonParallel.Invoke(
                () =>
                {
                        // Build and transform padded sequence b_k = exp(I*Pi*k^2/N)
                        for (int i = 0; i < n; i++)
                    {
                        b[i] = sequence[i];
                    }

                    for (int i = m - n + 1; i < b.Length; i++)
                    {
                        b[i] = sequence[m - i];
                    }

                    Radix2Forward(b);
                },
                () =>
                {
                        // Build and transform padded sequence a_k = x_k * exp(-I*Pi*k^2/N)
                        for (int i = 0; i < samples.Length; i++)
                    {
                        a[i] = sequence[i].Conjugate() * samples[i];
                    }

                    Radix2Forward(a);
                });

            for (int i = 0; i < a.Length; i++)
            {
                a[i] *= b[i];
            }

            Radix2InverseParallel(a);

            float nbinv = 1.0f / m;
            for (int i = 0; i < samples.Length; i++)
            {
                samples[i] = nbinv * sequence[i].Conjugate() * a[i];
            }
        }

Here is the call graph for this function:

BluesteinForward() [2/2]

static void BGC.Mathematics.Fourier.BluesteinForward ( Complex64 []  samples )

inlinestaticprivate

Definition at line 470 of file Fourier.cs.

References BGC.Mathematics.Complex64.Conjugate().

        {
            int n = samples.Length;
            Complex64[] sequence = BluesteinSequence64(n);

            // Padding to power of two >= 2N–1 so we can apply Radix-2 FFT.
            int m = ((n << 1) - 1).CeilingToPowerOfTwo();
            Complex64[] b = new Complex64[m];
            Complex64[] a = new Complex64[m];

            CommonParallel.Invoke(
                () =>
                {
                    // Build and transform padded sequence b_k = exp(I*Pi*k^2/N)
                    for (int i = 0; i < n; i++)
                    {
                        b[i] = sequence[i];
                    }

                    for (int i = m - n + 1; i < b.Length; i++)
                    {
                        b[i] = sequence[m - i];
                    }

                    Radix2Forward(b);
                },
                () =>
                {
                    // Build and transform padded sequence a_k = x_k * exp(-I*Pi*k^2/N)
                    for (int i = 0; i < samples.Length; i++)
                    {
                        a[i] = sequence[i].Conjugate() * samples[i];
                    }

                    Radix2Forward(a);
                });

            for (int i = 0; i < a.Length; i++)
            {
                a[i] *= b[i];
            }

            Radix2InverseParallel(a);

            float nbinv = 1.0f / m;
            for (int i = 0; i < samples.Length; i++)
            {
                samples[i] = nbinv * sequence[i].Conjugate() * a[i];
            }
        }

Here is the call graph for this function:

BluesteinInverse() [1/2]

static void BGC.Mathematics.Fourier.BluesteinInverse ( Complex32 []  spectrum )

inlinestaticprivate

Bluestein generic FFT for arbitrary sized sample vectors.

Definition at line 304 of file Fourier.cs.

        {
            SwapRealImaginary(spectrum);
            BluesteinForward(spectrum);
            SwapRealImaginary(spectrum);
        }

BluesteinInverse() [2/2]

static void BGC.Mathematics.Fourier.BluesteinInverse ( Complex64 []  spectrum )

inlinestaticprivate

Bluestein generic FFT for arbitrary sized sample vectors.

Definition at line 524 of file Fourier.cs.

        {
            SwapRealImaginary(spectrum);
            BluesteinForward(spectrum);
            SwapRealImaginary(spectrum);
        }

BluesteinSequence32()

static Complex32 [] BGC.Mathematics.Fourier.BluesteinSequence32 ( int  n )

inlinestaticprivate

Generate the bluestein sequence for the provided problem size.

Parameters

n	Number of samples.

Returns

Bluestein sequence exp(I*Pi*k^2/N)

Definition at line 322 of file Fourier.cs.

        {
            float s = Mathf.PI / n;
            Complex32[] sequence = new Complex32[n];

            // TODO: benchmark whether the second variation is significantly
            // faster than the former one. If not just use the former one always.
            if (n > BluesteinSequenceLengthThreshold)
            {
                for (int k = 0; k < sequence.Length; k++)
                {
                    float t = (s * k) * k;
                    sequence[k] = new Complex32(Mathf.Cos(t), Mathf.Sin(t));
                }
            }
            else
            {
                for (int k = 0; k < sequence.Length; k++)
                {
                    float t = s * (k * k);
                    sequence[k] = new Complex32(Mathf.Cos(t), Mathf.Sin(t));
                }
            }

            return sequence;
        }

BluesteinSequence64()

static Complex64 [] BGC.Mathematics.Fourier.BluesteinSequence64 ( int  n )

inlinestaticprivate

Generate the bluestein sequence for the provided problem size.

Parameters

n	Number of samples.

Returns

Bluestein sequence exp(I*Pi*k^2/N)

Definition at line 536 of file Fourier.cs.

        {
            float s = Mathf.PI / n;
            Complex64[] sequence = new Complex64[n];

            // TODO: benchmark whether the second variation is significantly
            // faster than the former one. If not just use the former one always.
            if (n > BluesteinSequenceLengthThreshold)
            {
                for (int k = 0; k < sequence.Length; k++)
                {
                    float t = (s * k) * k;
                    sequence[k] = new Complex64(Mathf.Cos(t), Mathf.Sin(t));
                }
            }
            else
            {
                for (int k = 0; k < sequence.Length; k++)
                {
                    float t = s * (k * k);
                    sequence[k] = new Complex64(Mathf.Cos(t), Mathf.Sin(t));
                }
            }

            return sequence;
        }

Forward() [1/2]

static void BGC.Mathematics.Fourier.Forward ( Complex32 []  samples )

inlinestatic

Definition at line 43 of file Fourier.cs.

Referenced by BGC.Audio.Filters.CarlileShuffler._Initialize(), BGC.Audio.Filters.ConvolutionFilter._Initialize(), BGC.Audio.Filters.MultiConvolutionFilter._Initialize(), BGC.Audio.Visualization.Spectrogram.Decompose(), BGC.Audio.Filters.PhaseVocoder.Read(), BGC.Audio.Filters.ConvolutionFilter.Read(), BGC.Audio.Filters.FramedPhaseReencoder.Read(), BGC.Audio.Filters.MultiConvolutionFilter.Read(), BGC.Tests.TestOverlapAdd.TestNewFFTs(), and BGC.Audio.Filters.SinglePassPhaseReencoder.TimeShift().

        {
            if (samples.Length.IsPowerOfTwo())
            {
                if (samples.Length >= 1024)
                {
                    Radix2ForwardParallel(samples);
                }
                else
                {
                    Radix2Forward(samples);
                }
            }
            else
            {
                BluesteinForward(samples);
            }

            Rescale(samples);
        }

Here is the caller graph for this function:

Forward() [2/2]

static void BGC.Mathematics.Fourier.Forward ( Complex64 []  samples )

inlinestatic

Definition at line 86 of file Fourier.cs.

        {
            if (samples.Length.IsPowerOfTwo())
            {
                if (samples.Length >= 1024)
                {
                    Radix2ForwardParallel(samples);
                }
                else
                {
                    Radix2Forward(samples);
                }
            }
            else
            {
                BluesteinForward(samples);
            }

            Rescale(samples);
        }

Inverse() [1/2]

static void BGC.Mathematics.Fourier.Inverse ( Complex32 []  spectrum )

inlinestatic

Definition at line 64 of file Fourier.cs.

Referenced by BGC.Audio.Filters.CarlileShuffler._Initialize(), BGC.Audio.Synthesis.NoiseAudioClip._Initialize(), BGC.Audio.Synthesis.STMAudioClip._Initialize(), BGC.Audio.AnalyticStreams.AnalyticNoiseStream.Initialize(), BGC.Audio.Synthesis.FrequencyDomainToneComposer.Read(), BGC.Audio.Filters.PhaseVocoder.Read(), BGC.Audio.Filters.ConvolutionFilter.Read(), BGC.Audio.Filters.FramedPhaseReencoder.Read(), BGC.Audio.Filters.MultiConvolutionFilter.Read(), BGC.Tests.TestOverlapAdd.TestNewFFTs(), and BGC.Audio.Filters.SinglePassPhaseReencoder.TimeShift().

        {
            if (spectrum.Length.IsPowerOfTwo())
            {
                if (spectrum.Length >= 1024)
                {
                    Radix2InverseParallel(spectrum);
                }
                else
                {
                    Radix2Inverse(spectrum);
                }
            }
            else
            {
                BluesteinInverse(spectrum);
            }

            //Asymmetrical rescaling...
            //Rescale(spectrum);
        }

Here is the caller graph for this function:

Inverse() [2/2]

static void BGC.Mathematics.Fourier.Inverse ( Complex64 []  spectrum )

inlinestatic

Definition at line 107 of file Fourier.cs.

        {
            if (spectrum.Length.IsPowerOfTwo())
            {
                if (spectrum.Length >= 1024)
                {
                    Radix2InverseParallel(spectrum);
                }
                else
                {
                    Radix2Inverse(spectrum);
                }
            }
            else
            {
                BluesteinInverse(spectrum);
            }

            //Asymmetrical rescaling...
            //Rescale(spectrum);
        }

Radix2Forward() [1/2]

static void BGC.Mathematics.Fourier.Radix2Forward ( Complex32 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sized sample vectors.

Definition at line 172 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                for (int k = 0; k < levelSize; k++)
                {
                    Radix2Step(data, -1, levelSize, k);
                }
            }
        }

Radix2Forward() [2/2]

static void BGC.Mathematics.Fourier.Radix2Forward ( Complex64 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sized sample vectors.

Definition at line 393 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                for (int k = 0; k < levelSize; k++)
                {
                    Radix2Step(data, -1, levelSize, k);
                }
            }
        }

Radix2ForwardParallel() [1/2]

static void BGC.Mathematics.Fourier.Radix2ForwardParallel ( Complex32 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sample vectors (Parallel Version).

Definition at line 132 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                int size = levelSize;

                CommonParallel.For(0, size, 64, (u, v) =>
                {
                    for (int i = u; i < v; i++)
                    {
                        Radix2Step(data, -1, size, i);
                    }
                });
            }
        }

Radix2ForwardParallel() [2/2]

static void BGC.Mathematics.Fourier.Radix2ForwardParallel ( Complex64 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sample vectors (Parallel Version).

Definition at line 353 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                int size = levelSize;

                CommonParallel.For(0, size, 64, (u, v) =>
                {
                    for (int i = u; i < v; i++)
                    {
                        Radix2Step(data, -1, size, i);
                    }
                });
            }
        }

Radix2Inverse() [1/2]

static void BGC.Mathematics.Fourier.Radix2Inverse ( Complex32 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sized sample vectors.

Definition at line 187 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                for (int k = 0; k < levelSize; k++)
                {
                    Radix2Step(data, 1, levelSize, k);
                }
            }
        }

Radix2Inverse() [2/2]

static void BGC.Mathematics.Fourier.Radix2Inverse ( Complex64 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sized sample vectors.

Definition at line 408 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                for (int k = 0; k < levelSize; k++)
                {
                    Radix2Step(data, 1, levelSize, k);
                }
            }
        }

Radix2InverseParallel() [1/2]

static void BGC.Mathematics.Fourier.Radix2InverseParallel ( Complex32 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sample vectors (Parallel Version).

Definition at line 152 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                int size = levelSize;

                CommonParallel.For(0, size, 64, (u, v) =>
                {
                    for (int i = u; i < v; i++)
                    {
                        Radix2Step(data, 1, size, i);
                    }
                });
            }
        }

Radix2InverseParallel() [2/2]

static void BGC.Mathematics.Fourier.Radix2InverseParallel ( Complex64 []  data )

inlinestaticprivate

Radix-2 generic FFT for power-of-two sample vectors (Parallel Version).

Definition at line 373 of file Fourier.cs.

        {
            Radix2Reorder(data);
            for (int levelSize = 1; levelSize < data.Length; levelSize *= 2)
            {
                int size = levelSize;

                CommonParallel.For(0, size, 64, (u, v) =>
                {
                    for (int i = u; i < v; i++)
                    {
                        Radix2Step(data, 1, size, i);
                    }
                });
            }
        }

Radix2Reorder() [1/2]

static void BGC.Mathematics.Fourier.Radix2Reorder ( Complex32 []  samples )

inlinestaticprivate

Radix-2 Reorder Helper Method

Definition at line 202 of file Fourier.cs.

        {
            int j = 0;
            for (int i = 0; i < samples.Length - 1; i++)
            {
                if (i < j)
                {
                    Complex32 temp = samples[i];
                    samples[i] = samples[j];
                    samples[j] = temp;
                }

                int m = samples.Length;

                do
                {
                    m >>= 1;
                    j ^= m;
                }
                while ((j & m) == 0);
            }
        }

Radix2Reorder() [2/2]

static void BGC.Mathematics.Fourier.Radix2Reorder ( Complex64 []  samples )

inlinestaticprivate

Radix-2 Reorder Helper Method

Definition at line 423 of file Fourier.cs.

        {
            int j = 0;
            for (int i = 0; i < samples.Length - 1; i++)
            {
                if (i < j)
                {
                    Complex64 temp = samples[i];
                    samples[i] = samples[j];
                    samples[j] = temp;
                }

                int m = samples.Length;

                do
                {
                    m >>= 1;
                    j ^= m;
                }
                while ((j & m) == 0);
            }
        }

Radix2Step() [1/2]

static void BGC.Mathematics.Fourier.Radix2Step ( Complex32 []  samples, int  exponentSign, int  levelSize, int  k  )

inlinestaticprivate

Radix-2 Step Helper Method

Parameters

samples	Sample vector.
exponentSign	Fourier series exponent sign.
levelSize	Level Group Size.
k	Index inside of the level.

Definition at line 233 of file Fourier.cs.

        {
            // Twiddle Factor
            float exponent = (exponentSign * k) * Mathf.PI / levelSize;
            Complex32 w = new Complex32(Mathf.Cos(exponent), Mathf.Sin(exponent));

            int step = levelSize << 1;
            for (int i = k; i < samples.Length; i += step)
            {
                Complex32 ai = samples[i];
                Complex32 t = w * samples[i + levelSize];
                samples[i] = ai + t;
                samples[i + levelSize] = ai - t;
            }
        }

Radix2Step() [2/2]

static void BGC.Mathematics.Fourier.Radix2Step ( Complex64 []  samples, int  exponentSign, int  levelSize, int  k  )

inlinestaticprivate

Radix-2 Step Helper Method

Parameters

samples	Sample vector.
exponentSign	Fourier series exponent sign.
levelSize	Level Group Size.
k	Index inside of the level.

Definition at line 454 of file Fourier.cs.

        {
            // Twiddle Factor
            float exponent = (exponentSign * k) * Mathf.PI / levelSize;
            Complex64 w = new Complex64(Mathf.Cos(exponent), Mathf.Sin(exponent));

            int step = levelSize << 1;
            for (int i = k; i < samples.Length; i += step)
            {
                Complex64 ai = samples[i];
                Complex64 t = w * samples[i + levelSize];
                samples[i] = ai + t;
                samples[i + levelSize] = ai - t;
            }
        }

Rescale() [1/2]

static void BGC.Mathematics.Fourier.Rescale ( Complex32 []  samples )

inlinestaticprivate

Fully rescale the FFT result.

Definition at line 566 of file Fourier.cs.

        {
            float scalingFactor = 1f / samples.Length;
            for (int i = 0; i < samples.Length; i++)
            {
                samples[i] *= scalingFactor;
            }
        }

Rescale() [2/2]

static void BGC.Mathematics.Fourier.Rescale ( Complex64 []  samples )

inlinestaticprivate

Fully rescale the FFT result.

Definition at line 578 of file Fourier.cs.

        {
            float scalingFactor = 1f / samples.Length;
            for (int i = 0; i < samples.Length; i++)
            {
                samples[i] *= scalingFactor;
            }
        }

SwapRealImaginary() [1/2]

static void BGC.Mathematics.Fourier.SwapRealImaginary ( Complex32 []  samples )

inlinestaticprivate

Swap the real and imaginary parts of each sample.

Parameters

samples

Sample Vector.

Definition at line 591 of file Fourier.cs.

        {
            for (int i = 0; i < samples.Length; i++)
            {
                samples[i] = new Complex32(samples[i].Imaginary, samples[i].Real);
            }
        }

SwapRealImaginary() [2/2]

static void BGC.Mathematics.Fourier.SwapRealImaginary ( Complex64 []  samples )

inlinestaticprivate

Swap the real and imaginary parts of each sample.

Parameters

samples

Sample Vector.

Definition at line 603 of file Fourier.cs.

        {
            for (int i = 0; i < samples.Length; i++)
            {
                samples[i] = new Complex64(samples[i].Imaginary, samples[i].Real);
            }
        }

Field Documentation

BluesteinSequenceLengthThreshold

const int BGC.Mathematics.Fourier.BluesteinSequenceLengthThreshold = 46341

private

Sequences with length greater than Math.Sqrt(Int32.MaxValue) + 1 will cause k*k in the Bluestein sequence to overflow (GH-286).

Definition at line 315 of file Fourier.cs.

---

The documentation for this class was generated from the following file:

• Mathematics/Fourier.cs