Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 05.12.2009, 09:10
гость

 
Сообщений: n/a

Алгоритмы. Построение и анализ. Издание 2-е
Эта книга имелась ввиду под Корменом?
  #12  
Старый 05.12.2009, 14:52
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Алгоритмы. Построение и анализ. Издание 2-е
Эта книга имелась ввиду под Корменом?
Да, да. Там изложено быстрое пребразование фурье.
  #13  
Старый 05.12.2009, 14:55
гость

 
Сообщений: n/a

Цитата:
Я так понимаю какая то часть входного вектора берется мнимой
Действительно число x - это то же самое что комлексное x + 0i. Что непонятно-то?
  #14  
Старый 05.12.2009, 18:24
Алексей1981

 
Сообщений: n/a

Спасибо, теперь вроде все понятно.
Кстати, а можно делать вектор сразу комплексным, т.е. без дополнительной мнимой части? Вроде бы гдето встречал такой алгоритм, но не могу снова найти. Ведь это лишняя нагрузка в вычислениях. Там вроде бы половина вектора делалась действительной, а вторая половина мнимой... В этом случае я понимаю и матрица будет в два раза меньшего порядка?
  #15  
Старый 05.12.2009, 20:11
гость

 
Сообщений: n/a

Сообщение от Алексей1981 Посмотреть сообщение
Спасибо, теперь вроде все понятно.
Кстати, а можно делать вектор сразу комплексным, т.е. без дополнительной мнимой части? Вроде бы гдето встречал такой алгоритм, но не могу снова найти. Ведь это лишняя нагрузка в вычислениях. Там вроде бы половина вектора делалась действительной, а вторая половина мнимой... В этом случае я понимаю и матрица будет в два раза меньшего порядка?
Ты ведь все равно хочешь это на ассемблере реализовывать, так? Там нет команд для работы с комплексными числами, тебе все равно придется все переписывать через действительные. Вот когда будешь писать цикл, просто помни что у тебя во входе только действительные числа, т.е мнимая часть равна нулю. Короче, начинай кодить и сам все поймешь.
  #16  
Старый 05.12.2009, 20:12
гость

 
Сообщений: n/a

А матрицу нигде хранить не надо, вычисляй все ее значения на лету.
  #17  
Старый 06.12.2009, 02:28
Алексей1981

 
Сообщений: n/a

Матрицу по любому придется вычислять заранее(точнее синусы и косинусы), т.к. синусы и косинусы вычислить на ассемблере просто тупо тормознуто, хотя на любом другом языке еще тормознутее... Буду думать еще как все реализовать, да и в литературе сейчас проще уже найти ответ, когда вычисление реализовано в лоб и дает верные результаты. Есть хотя бы с чем сравнивать. Все это дело хочу реализовать на PIC18 микроконтроллере, для которого примеров не нашел... Только на AVR, которые больше подходят для этой цели. Но программа написана не мной и поэтому разбираться там с многочисленными умножениями дробных знаковых чисел крайне тяжело, да еще и в не общепринятых стандартах представления отрицательных чисел... Вобщем полный гимор... Проще разобраться и написать программу самостоятельно... Причем там применена еще и функция окна Хамминга, с которой придется тоже разбираться...
  #18  
Старый 06.12.2009, 02:51
гость

 
Сообщений: n/a

Если вам нужно **быстрое** преобразование Фурье, то матрицу нельзя хранить. Собственно, алгоритм FFT и состоит в том, как бы быстро умножить вектор на эту матрицу, не храня и не вычисляя ее явно.
  #19  
Старый 06.12.2009, 21:51
Алексей1981

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Если вам нужно **быстрое** преобразование Фурье, то матрицу нельзя хранить. Собственно, алгоритм FFT и состоит в том, как бы быстро умножить вектор на эту матрицу, не храня и не вычисляя ее явно.
Пока еще не разбирался, т.к. для этого нужно понять как вычисляется ДПФ в лоб.
Сейчас посчитал матрицу F(Правильность ее вычисления сверил с примером, только N взял 8 матрица совпала. Сейчас соответственно поставил 4 для правильности дальнейших вычислений. Теперь она состоит из одних плюс минус единиц...)), и умножил ее на вектор х. Причем из матрицы F и х брал только действительные и мнимые части по отдельности и получил две новые матрицы, действительную и мнимую. С действительной частью все ОК, ответы совпадают, а вот с мнимой вся матрица равна нулю, что вобщем то естественно при умножении на ноль... В ответах же мнимая часть не вся равна нулю. Я где то ошибся?
  #20  
Старый 06.12.2009, 22:05
гость

 
Сообщений: n/a

Итак, вы говорите, что F = A + Bi, где A, B - действительные матрицы.

Потом умножили: Fx = (A + Bi)x = Ax + Bx i. Где вы здесь увидели умножение на ноль???
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача 15. Помогите разобраться с решением Vlad Графы 3 27.05.2009 22:18
помогите разобраться с сортировкой lavan Сортировка и поиск 2 20.03.2009 19:48
Помогите разобраться с хи-квадратом subdmitry Математические алгоритмы 2 11.03.2009 01:11
Помогите разобраться с задачей Megov Задачи 2 07.10.2008 18:19
помогите разобраться Мёртвый Анархист Реализация, исходники, языки 13 23.01.2007 08:25