Skip to content

Instantly share code, notes, and snippets.

@helios2k6
Last active Nov 14, 2016
Embed
What would you like to do?
DFT Implementations, including FFT
private static Complex[] DFTDirectComputation(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[] DFTSlightlyFaster(Complex[] input)
{
int N = input.Length;
Complex[] output = new Complex[input.Length];
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[] DFTUsingFFT(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 = DFTUsingFFT(evenPoints);
Complex[] oddDft = DFTUsingFFT(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));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment