Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Быстрые и дискретные преобразования фурье

Автор: PILOT 8.4.2002, 20:07

Может встречал кто, хорошие описания сабжа (книги, инет, живые люди, участники конференции-тоже живые

)?
Не горит, но дымится...

СУВ.

Автор: Dicobraz 9.4.2002, 13:24

Есть такая книга - "Дискретные преобразования при обработке цифровых сигналов". Супер. Только тяжко это все

Есть еще guides различные - у меня две книги есть на винте (англ.), часть одной - на русский (в моем переводе). (меняю на пароль

)
Могу прислать.

http://www.dspguide.com/

Автор: podval 9.4.2002, 13:30

Есть хорошая книга "Быстрые алгоритмы в цифровой обработке сигналов", автора только запамятовал. У меня есть хорошая программка по вычислению БПФ, по-моему именно по этой книге сделана. В домашнем компе покопаюсь и выложу завтра здесь для всеобщего обозрения. Наверняка пригодится кому-нибудь. Вообще литературы много всякой, можно обратить внимание на таких авторов, как Рабинер, Голд, Шаффер. Если вообще заинтересуют быстрые алгоритмы, то есть еще такое быстрое преобразование Хартли, работает быстрее БПФ за счет вещественного ядра, описано у него (у Хартли) в книжке (название не помню, давно дело было, склероз

). Прекрасно работает быстрое преобразование в базисе Уолша. Можно почитать Маклеллан, Рейдер "Применение теории чисел в цифровой обработке сигналов", но там специфические вещи, зато очень поучительные.
Прога за мной!

Автор: Dicobraz 9.4.2002, 13:40

Да, кстати, если нужна быстрая библиотека - у Интела на сайте валяется очень неплохая. И компилятор иховый. Да и быстрая, наверное. Проверял функции, а не скорость. Причем есть и под Линукс и под Винду. А серийник на astalavista.box.sk есть.

Автор: podval 9.4.2002, 14:46

Вот для самообразования есть http://www.dsp.sut.ru/book/index.htm
См. лекцию 4.

Автор: PILOT 11.4.2002, 18:59

НУ-у-у!
Крута! Сайт существует, скачан и обработан. Спасибо.
Господарищи, вспомните авторов пожалуйста, а то библиотекарь сильна ругается, однако

СУВ.
ЗЫ.
Было у отца 3 сына, банкир, министр, а третий ворота закрывал...

Автор: podval 11.4.2002, 20:56

Долго молчал, т.к. на работе Инет навернулся до конца месяца. Однако, как и обещал, привожу код с БПФ. Пользуйтесь!

Код


/*
Основная функция, реализующая БПФ.
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>
*/

З.Ы. Если главный админ сочтет нужным, то можно это повторить в разделе "Разное" или "Технологии", на усмотрение.

Автор: podval 11.4.2002, 21:55

Цитата(PILOTIK @ 11.4.2002, 19:59)

Господарищи, вспомните авторов пожалуйста, а то библиотекарь сильна ругается, однако

Дык фамилии я и так назвал. Ну если еще фамилию Ланнэ встретишь, то бери и читай. В библиотеке сначала обратись к библиографу, ей ругаться не положено

Автор: PILOT 13.4.2002, 13:06

За данные спасибо.
А насчет библоиграфа я пошутил.

За програмку отдельное спасибо.
Интересно, можно ли приобрести пододобную литературу (а то выписывать уже как-то неприлично). Просто привык дома сидеть разбираться и пробовать, пробовать, пробовать.
Кстати БПФ мне нужен для контроллера (это я не к тому, чтобы все дружно присылали проги на ASM для ATmega163), так что если кто-то знает какие-нибудь еще способы быстрого перехода в частотную область приму с благодарностью.

СУВ.
ЗЫ.
-Мама, смотри какая машина, прям как дом!
-Я тебе миллион раз говорила: не преувеличивай!!!

Автор: podval 13.4.2002, 20:13

Если говорить о быстрых способов, то их много. Найди все-таки книжку Хартли, у него крутой способ описан. Прикинь, какая экономия хотя бы на операциях умножения с вещественными числами, а не с комплексными. Да и вообще алгоритмов БПФ много разновидностей. Раз уж любишь читать, приведу кое-какой списочек (он проверен не одним поколением

).

Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. - М.:
Мир, 1978. - 848 с.
Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. -М.: Мир, 1989.
448 с.
Применение цифровой обработки сигналов/ Под ред. Э.Оппенгейма. -М.: Мир,
1980. 552 с.
Арро И.О. Обобщенный алгоритм дискретного преобразования Фурье// Изв. вузов: Радиоэлектроника, № 10, с.5-10.
Гольденберг А.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов:
Справочник. -М: Радио и связь, 1985. 312 с.
Демидов В.М. Алгоритм усеченного БПФ и его реализация// Радиотехника, 1988. № 2, С.91-92.
Цифровой процессор обработки сигналов TMS32010 и его применение/ под ред. А.А.Ланнэ. -Л.: ВАС, 1989. (в этой книге расписана реализация БПФ на этом ЦПОС с программкой, но эта книга вышла в Военной академии связи, где Ланнэ когда-то работал, так что найти можно только в библиотеке академии или искать авторские экземпляры по всей СНГ. Лучшая книга для практика!

Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в
управлении, связи и других областях. -М.: Наука, 1989. 496 с.
Фурье-процессор на основе микропроцессорного комплекта К589/ А.В.Егошин,
Ю.Ю.Мальгин, С.А.Терехов, ЯА.Фурман// Изв. вузов: Радиоэлектроника. 1984.
Т.27, № 8. с.86-87.

На первое время хватит?

Автор: PILOT 14.4.2002, 23:19

Спасибо, podval.
И все-таки

Ты из МИФИ?
Ведь именно там большая статуя (со всеми причендалами), бредущая к знаниям уже 2-3 года?

СУВ.
"...Не матерился я в детском саду... Нет!...Так я спокойно говорю, мол, Иванов, аккуратнее пожалйста, а то ты мне капаешь за шиворот раскаленным оловом..."

Автор: podval 15.4.2002, 20:58

Цитата(PILOTIK @ 15.4.2002, 00:19)

И все-таки

Ты из МИФИ?

Неа

Автор: PILOT 16.4.2002, 20:59

Жаль

СУВ.