Поиск:

Ответ в темуСоздание новой темы Создание опроса
> преобразования Фурье в С++, Как это сделать 
:(
    Опции темы
Гость_Александр
  Дата 22.8.2003, 16:34 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Народ! Как сделаь прямое и обратное преобразование Фурье ? Может, кто подскажет какой сайт? Или свое что кинет?
  Вверх
mr.DUDA
Дата 22.8.2003, 16:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: нет
Всего: 232
http://dsp-book.narod.ru/

А вообще-то на форуме есть отдельный раздел, посвященный технологиям и алгоритмам. Вот здесь лежит большой список ссылок, где можно найти кучу инфы по вопросу.

Это сообщение отредактировал(а) mr.DUDA - 22.8.2003, 16:59


--------------------
user posted image
PM MAIL WWW   Вверх
RAN
Дата 23.8.2003, 13:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Экс. модератор
Сообщений: 709
Регистрация: 14.3.2003
Где: Щёлково Моск.обл.

Репутация: нет
Всего: 6
Модератор: Не смотря на наличие в названии заветного слова "C++", тема не имеет с языком, как таковым, ничего общего. Перемещена из C++ в Технологии и алгоритмы
PM MAIL ICQ   Вверх
podval
Дата 23.8.2003, 16:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62
Код
/*
Функция, реализующая БПФ.
sig - массив входных данных, результат возвращается сюда же.
n - размер массива sig. Должен быть степенью двойки. Недостающие
   отсчёты дополняются нулями.
sn - массив размером n+1, представляющий ядро преобразования.
p = Log2(n) или n = pow(2,p), поэтому в принципе необязательно
   обе величины задавать в аргументах функции, это надо было
   в учебных целях и еще это в вычислительном смысле удобно.
*/
//---------------------------------------------------------------------------
void fft(complex<double> *sig, int p, complex<double> *sn, int n)
{
 complex<double> *spr = new complex<double>[n];
 int r2 = 1;
     r2 <<= (p - 1);
 int l1 = r2 + r2;
 for(int ir=1; ir <= p; ir++)
   {
    int i1 = p - ir + 1;
    int b = 1;
 b <<= (i1 - 1);
    int r = 1;
 r <<= (p - i1);
 r -= 1;
    int rm = r + 1;
    for(int mr = 1; mr <= rm; mr++)
      {
int m = mr - 1;
int r1 = b*m;
int r3 = b*(m + r + 1);
int l = r1 + r1;
int m31 = r1 + 1;
int m41 = r3 + 1;
for(int km = 1; km <= b; km++)
  {
   int k = km - 1;
   int m11 = k + l + 1;
   int m21 = m11 + b;
   int m51 = k + r1 + 1;
   int m61 = k + r2 + r1 + 1;
   spr[m51-1] = sig[m11-1] + sig[m21-1]*sn[m31-1];
   spr[m61-1] = sig[m11-1] + sig[m21-1]*sn[m41-1];
  }
      }
    for(int m = 0; m < l1; m++)
        sig[m] = spr[m];
   }
  for (int i=0; i < n;i++)
       sig[i] /= n;
delete[] spr; spr = 0;
}
//--------------------------------------------------------------------
/*
Пример работы с функцией fft
Здесь предполагается, что имеются некоторые данные, а
юзер хочет сделать БПФ применительно к выборке между отсчётами
с номерами от FFTBegin до FFTEnd
*/
  // в следующем цикле do...while готовятся данные для БПФ
  // а именно размер входного массива и показатель степени двойки

  int p1, n = 2, nn = 1;   // p1 = 2 в степени nn
  do {
     p1 = (n <<= 1); // p1 - сюда пишем размер преобразуемого массива
     nn += 1;        // nn - показатель степени двойки (p1 = pow(2,nn))
  } while((FFTEnd - FFTBegin) > p1);

  complex<double> *sig = new complex<double>[p1]; // массив входных данных
  complex<double> *vyx = new complex<double>[p1+1]; // ядро преобразования

  // готовим ядро преобразования
  double a = 2*M_PI/p1;
  double b1;
  for(int i=0; i < (p1+1); i++)
  {
     b1 = a*i;
     vyx[i] = complex<double>(cos(b1),sin(b1));
  }

  // здесь вставить ввод исходных данных в массив sig
  // обращаю внимание, что он complex!!!
  // это значит, что если данные представлены вещественными
  // числами, их надо привести к комплексному виду с нулевой
  // мнимой частью.

  // процедура БПФ
  fft(sig, nn, vyx, p1);


  // можно сделать и обратное преобразование, для этого надо слегка
  // переделать ядро (найти комплексно-сопряженные числа)

  for(int i=0; i < (p1+1); i++)
      vyx[i] = conj(vyx[i]);

  // а затем вызвать fft

/*
NB: для работы необходимо
#include<complex.h>
#include<math.h>
*/
PM WWW ICQ   Вверх
beif
Дата 31.8.2003, 11:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.8.2003
Где: Россия, Кемерово

Репутация: 1
Всего: 1
На WWW.WEBSOUND.RU я кажись видел FFT на С++... Да, точно, там... Тока не помню в каком разделе... Там их в принципе немного, поройся если надо... smile.gif
PM MAIL WWW ICQ   Вверх
Paradox
Дата 16.9.2003, 13:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1135
Регистрация: 18.11.2002
Где: Россия

Репутация: нет
Всего: 1
А еще лучше заглянуть во второй том Кнута и почитать... Про Фурье там точно есть


--------------------
---
PM MAIL WWW   Вверх
Alexei
Дата 10.10.2003, 17:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 382
Регистрация: 20.8.2003

Репутация: нет
Всего: 4
Цитата(podval @ 23.8.2003, 16:40)
Код
/*
n - размер массива sig. Должен быть степенью двойки.  

А нейзя тоже самое, только без этого?
PM MAIL   Вверх
podval
Дата 10.10.2003, 17:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62
конечно можно
PM WWW ICQ   Вверх
Alexei
Дата 11.10.2003, 08:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 382
Регистрация: 20.8.2003

Репутация: нет
Всего: 4
Так поможите, плииз
PM MAIL   Вверх
val
Дата 11.10.2003, 10:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Program developer
**


Профиль
Группа: Участник Клуба
Сообщений: 992
Регистрация: 14.1.2003
Где: г. Киев

Репутация: 1
Всего: 7
Цитата
QUOTE (podval @ 23.8.2003, 16:40)
CODE
/*
n - размер массива sig. Должен быть степенью двойки. 


А нейзя тоже самое, только без этого?


Можно... Длина в степень двойки необходима исключительно для повышения производительности алгоритма, особенно, если ты этот алгоритм устанавливаешь на DSP. Рекомендую оставить всё-таки длину в степень двойки, а оставшийся хвост дополнить нулями...


--------------------
Терпимость - величайшее благо человечества...
Ярчайший признак интеллекта – постоянно хорошее настроение…
PM MAIL ICQ   Вверх
Alexei
Дата 11.10.2003, 15:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 382
Регистрация: 20.8.2003

Репутация: нет
Всего: 4
Иногда надо пожертвовать чем-нить.Тем более, что быстрота нужна чаще при ловле блох.
Хочу подобрать поближе к реальным частотам.
PM MAIL   Вверх
val
Дата 11.10.2003, 15:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Program developer
**


Профиль
Группа: Участник Клуба
Сообщений: 992
Регистрация: 14.1.2003
Где: г. Киев

Репутация: 1
Всего: 7
Цитата
Тем более, что быстрота нужна чаще при ловле блох.


И при желании вписаться в "реальное время" при выволнении БПФ... ;)


--------------------
Терпимость - величайшее благо человечества...
Ярчайший признак интеллекта – постоянно хорошее настроение…
PM MAIL ICQ   Вверх
podval
Дата 11.10.2003, 19:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62
Цитата
Хочу подобрать поближе к реальным частотам.

Что имеется в виду?
Ничего страшного нет в том, если выборка дополнена нулями.
PM WWW ICQ   Вверх
Alexei
Дата 12.10.2003, 09:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 382
Регистрация: 20.8.2003

Репутация: нет
Всего: 4
Цитата(podval @ 11.10.2003, 19:28)
Ничего страшного нет в том, если выборка дополнена нулями.

Ничего.
Но я о том, что БПФ выдает результат соразмерно входному интервалу,а его можно изменять кратно 2.Соответсвенно результат далек от реального.
Задача та же:http://forum.vingrad.ru/index.php?act=ST&f=13&t=11739
2Val Что лучше:Получить ненужный результат(читай не верный) в приемлемое время, или нужный в неприемлемое?

Это сообщение отредактировал(а) Alexei - 12.10.2003, 09:18
PM MAIL   Вверх
Unregistered
Дата 4.12.2003, 19:42 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
www.fftw.org - Просто cool
  Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1012 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.