Skip to content

Instantly share code, notes, and snippets.

@helios2k6

helios2k6/DFT.cs

Last active November 14, 2016 03:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save helios2k6/1c658c76378b2bfe1eba9bbaebf867a2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save helios2k6/1c658c76378b2bfe1eba9bbaebf867a2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. helios2k6 revised this gist Nov 14, 2016. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions DFT.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -51,8 +51,8 @@ private static Complex[] DFTUsingFFT(Complex[] input)
    Complex[] evenPoints = input.Where((c, i) => i % 2 == 0).ToArray();
    Complex[] oddPoints = input.Where((c, i) => i % 2 == 1).ToArray();

    Complex[] evenDft = DFT3(evenPoints);
    Complex[] oddDft = DFT3(oddPoints);
    Complex[] evenDft = DFTUsingFFT(evenPoints);
    Complex[] oddDft = DFTUsingFFT(oddPoints);

    for (int k = 0; k < N / 2; k++)
    {
  2. helios2k6 revised this gist Nov 14, 2016. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion DFT.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -20,7 +20,6 @@ private static Complex[] DFTSlightlyFaster(Complex[] input)
    int N = input.Length;
    Complex[] output = new Complex[input.Length];

    // Even Computation
    for (int k = 0; k < input.Length; k++)
    {
    var evenSum = new Complex();
  3. helios2k6 revised this gist Nov 14, 2016. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions DFT.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,4 @@
    private static Complex[] DFT(Complex[] input)
    private static Complex[] DFTDirectComputation(Complex[] input)
    {
    int N = input.Length;
    Complex[] output = new Complex[input.Length];
    @@ -15,7 +15,7 @@ private static Complex[] DFT(Complex[] input)
    return output;
    }

    private static Complex[] DFT2(Complex[] input)
    private static Complex[] DFTSlightlyFaster(Complex[] input)
    {
    int N = input.Length;
    Complex[] output = new Complex[input.Length];
    @@ -38,7 +38,7 @@ private static Complex[] DFT2(Complex[] input)
    return output;
    }

    private static Complex[] DFT3(Complex[] input)
    private static Complex[] DFTUsingFFT(Complex[] input)
    {
    int N = input.Length;
    Complex[] output = new Complex[input.Length];
  4. helios2k6 created this gist Nov 14, 2016.
    74 changes: 74 additions & 0 deletions DFT.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,74 @@
    private static Complex[] DFT(Complex[] input)
    {
    int N = input.Length;
    Complex[] output = new Complex[input.Length];
    for (int k = 0; k < input.Length; k++)
    {
    var sum = new Complex();
    for (int n = 0; n < input.Length; n++)
    {
    sum += input[n] * WFunction(N, k * n);
    }
    output[k] = sum;
    }

    return output;
    }

    private static Complex[] DFT2(Complex[] input)
    {
    int N = input.Length;
    Complex[] output = new Complex[input.Length];

    // Even Computation
    for (int k = 0; k < input.Length; k++)
    {
    var evenSum = new Complex();
    var oddSum = new Complex();
    for (int m = 0; m < N / 2; m++)
    {
    evenSum += input[2 * m] * WFunction(N / 2, k * m);
    oddSum += input[2 * m + 1] * WFunction(N / 2, k * m);
    }

    oddSum = oddSum * WFunction(N, k);
    output[k] = evenSum + oddSum;
    }

    return output;
    }

    private static Complex[] DFT3(Complex[] input)
    {
    int N = input.Length;
    Complex[] output = new Complex[input.Length];

    if (input.Length == 1)
    {
    output[0] = input[0];
    }
    else
    {
    Complex[] evenPoints = input.Where((c, i) => i % 2 == 0).ToArray();
    Complex[] oddPoints = input.Where((c, i) => i % 2 == 1).ToArray();

    Complex[] evenDft = DFT3(evenPoints);
    Complex[] oddDft = DFT3(oddPoints);

    for (int k = 0; k < N / 2; k++)
    {
    output[k] = evenDft[k] + WFunction(N, k) * oddDft[k];
    output[k + N / 2] = evenDft[k] - WFunction(N, k) * oddDft[k];
    }
    }

    return output;
    }

    private static Complex WFunction(
    int N,
    int expOfW
    )
    {
    return new Complex(Math.Cos((2 * Math.PI / N) * expOfW), -Math.Sin((2 * Math.PI / N) * expOfW));
    }