Я пытаюсь реализовать в C # для моего собственного обучения алгоритм FFT, описанный здесь:
https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
в разделе «Переупорядочение данных, инверсия битов иразместить алгоритмы ".
Мой код выглядит следующим образом, с некоторой перегрузкой оператора фона для структуры" cplx ", что позволяет мне выполнять арифметику с этими объектами.
Bitreverse, кажется, работает нормально, итак же, как и вычисление «тиддл-фактора», поэтому я не уверен, где я ошибся. Код выглядит очень похожим на псевдокод, указанный на вики-странице.
public cplx[] FFT(cplx[] x)
{
//Bitreverse Copy
cplx[] a = BitReverse(x);
//Number of points
int n = a.Length;
for (int s = 1; s <= Math.Log(n); s++)
{
int m = (int)Math.Pow(2,s);
cplx w_m = Omega(m);
for (int k = 0; k < n; k += m)
{
cplx w = new cplx(1, 0);
for(int j = 0; j < m/2; j++)
{
cplx t = w * a[k + j + (m / 2)];
cplx u = a[k + j];
a[k + j] = u + t;
a[k + j + (m / 2)] = u - t;
w = w * w_m;
}
}
}
return a;
}
Я тестирую его с входным массивом исходного импульса с 8 выборками, который должен давать постоянный вывод.
Вместо этого я получаю 4 единицы и 4 нуля в указанном порядке.
В качестве отступления я предполагаю, что в псевдокоде:
for k = 0 to n-1 by m
Относится к * 1020. * хотя я не уверен, что это правильно.
Надеюсь, кто-то может пролить свет на мою некомпетентность!
Приветствия.
Вот код для бит-реверса и вычисления омеги.
private int Rev(int x, int k)
{
int reversed = 0;
for (int i = 0; i < k; i++)
{
reversed |= (x & (1 << i)) != 0 ? 1 << (k - 1 - i) : 0;
}
return reversed;
}
public cplx[] BitReverse(cplx[] x)
{
cplx[] r = new cplx[x.Length];
int bits = (int)Math.Log(x.Length, 2);
for(int k = 0; k < x.Length; k++)
{
r[Rev(k, bits)] = x[k];
}
return r;
}
private cplx Omega(int m)
{
float x = (- 2 * (float)Math.PI) / m;
return new cplx((float)Math.Cos(x), (float)(Math.Sin(x)));
}