Быстрое преобразование Фурье.

[lozty]

Привет!
Может кто знает или писал сам быстрое преобразование Фурье с прореживанием по частоте?
Пытаюсь сделать уже ооочень долго :-\ или может кто наметанным галзом скажет в чем ошибка:

Используется синтаксис C

for (k = n-1; k >0; k--)
   {
      double Wk = (-2 * 3.14159) / (1 << k);
      for (int j = 0; j < (1 << (n-k)); j++)
      {
         for (int r = 0; r < (1 << (k - 1)); r++)
                  {     
            int u = j * (1 << k) + r;
            int v = u + (1 << (k - 1));
            
            double Wkr = Wk * r;
            double Sn = sin(Wkr);
            double Cs = cos(Wkr);
            
            double ReY1 = re[u] + re[v];
            double ImY1 = im[u] + im[v];
            double ReY2 = Cs * re[u] - Sn * im[u] - Cs * re[v] + Sn * im[v];
            double ImY2 = Sn * re[u] + Cs * im[u] - Sn * re[v] - Cs * im[v];

            re[u] = ReY1;
            re[v] = ReY2;
            im[u] = ImY1;
            im[v] = ImY2;
 
         
            
         }
      }
   }

Буду очень благодарна :)

[VLarin]

А в Numerical Recipes in C не смотрели? Там глава 12 посвящена FFT, есть теория и код на С.

[Sanyok]

Вы не могли бы полностью текст процедуры привести? Т.е, начиная от объявления (тип возвр. значения, входные аргументы) и заканчивая оператором return.

[Sanyok]

Признаюсь, в БПФ я полный профан (до сих пор не могу понять, как этот алгоритм работает ). Единственное, что меня в приведенном коде напрягает - это то, что элементы массива re[u] и re[v] используются раньше, чем были проинициализированы...

То есть, если принимать во внимание только приведенный текст, получается, что элементам re[u] и re[v] было присвоено какое-то значение уже после того, как они были использованы в вычислениях.

Вот использование их:

            double ReY1 = re[u] + re[v]; 
            double ImY1 = im[u] + im[v]; 

А инициализация на несколько строк позже:

            re[u] = ReY1; 
            re[v] = ReY2;

Может, эти элементы (re[u] и re[v]) были инициализированы раньше (до входа в цикл)?

[lozty]

Честно говоря в программировании я полный профан, так что функция я не делала, а сделала прямо так, в программе, а перемееные re[u] и т.д. были считаны из файла c входным сигналом:
ifstream f ("input_signal.txt");
f >> dn;
for(i = 0; i < (1 << n); ++i)
f >> re[i] >> im[i];

[Sanyok]

Вы Вашу прогу не пробовали по шагам проходить?

Еще - совет из разряда идиотских, но если как-то поможет... Попробуйте это БПФ просто прсчитать на бумажке для маленького числа элементов N (для 4-х, например, т.е. для n=2), так, как по-вашему разумению, должна считать ваша прога, и потом просто пройдите Вашу прогу по шагам в отладчике и сравните значения переменных с тем, что Вы посчитали. Может, наткнетесь на какой-нить глюк, которого сразу не разглядишь...

Удачи.