2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Быстрое преобразование Фурье.
Сообщение10.11.2005, 23:22 


08/11/05
8
Привет!
Может кто знает или писал сам быстрое преобразование Фурье с прореживанием по частоте?
Пытаюсь сделать уже ооочень долго :-\ или может кто наметанным галзом скажет в чем ошибка:
код: [ скачать ] [ спрятать ]
Используется синтаксис 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;
 
         
           
         }
      }
   }

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

 Профиль  
                  
 
 
Сообщение11.11.2005, 13:38 


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

 Профиль  
                  
 
 
Сообщение11.11.2005, 15:53 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение11.11.2005, 16:20 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Признаюсь, в БПФ я полный профан (до сих пор не могу понять, как этот алгоритм работает :oops: :( ). Единственное, что меня в приведенном коде напрягает - это то, что элементы массива 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]) были инициализированы раньше (до входа в цикл)?

 Профиль  
                  
 
 
Сообщение11.11.2005, 19:43 


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

 Профиль  
                  
 
 
Сообщение12.11.2005, 00:30 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Вы Вашу прогу не пробовали по шагам проходить?

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

Удачи.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group