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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #21  
Старый 06.12.2009, 22:15
Алексей1981

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

Не, Я считал так: y=F*x, это действительная часть, мнимая вычислялась по собственной матрице yi=Fi*xi. Часть x это действительная матрица, заданная по условию. Т.к. дпх вычисляется в комплексных числах а матрица чисто действительная, то xi это нулевая матрица. Хотя матрица Fi и не нулевая, но при умножении на xi все равно получается нулевая. Вот сейчас сижу и думаю, где же ошибка? Ответы сравниваю с примером на первой странице...
  #22  
Старый 06.12.2009, 22:20
Алексей1981

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

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

Потом умножили: Fx = (A + Bi)x = Ax + Bx i. Где вы здесь увидели умножение на ноль???
Т.е. я хотел сказать, что матрица F вычисляется вообще независмо от других матриц, она самостоятельна, как константа.
  #23  
Старый 06.12.2009, 22:48
гость

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

Ну, я назвал вашу Fi как B.

Сообщение от Алексей1981 Посмотреть сообщение
Не, Я считал так: y=F*x, это действительная часть, мнимая вычислялась по собственной матрице yi=Fi*xi.
вот здесь ошибка. Мнимая часть вектор F*x - это Fi * x.
  #24  
Старый 06.12.2009, 23:29
Алексей1981

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

Сообщение от гость Посмотреть сообщение
вот здесь ошибка. Мнимая часть вектор F*x - это Fi * x.
Действительно, все получилось. Интересно, полез по книгам читать, почему так.
  #25  
Старый 06.12.2009, 23:48
гость

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

Сообщение от Алексей1981 Посмотреть сообщение
Действительно, все получилось. Интересно, полез по книгам читать, почему так.
Как почему? Тут элементарная алгебра - дистрибутивные, ассоциативные и коммутативные свойства операций сложения и умножения. Все они (кроме коммутативности умножения) справедливы и для матричных выражений. Доказывается из определений, и соответствующих свойств действительных и комплексных чисел.

F = Fr + Fi * i
F*x = (Fr + Fi * i) * x = Fr * x + (Fi * i) * x = Fr * x + (Fi * x) * i.
  #26  
Старый 07.12.2009, 00:21
Алексей1981

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

Сообщение от гость Посмотреть сообщение
Как почему? Тут элементарная алгебра - дистрибутивные, ассоциативные и коммутативные свойства операций сложения и умножения. Все они (кроме коммутативности умножения) справедливы и для матричных выражений. Доказывается из определений, и соответствующих свойств действительных и комплексных чисел.

F = Fr + Fi * i
F*x = (Fr + Fi * i) * x = Fr * x + (Fi * i) * x = Fr * x + (Fi * x) * i.
Спасибо большое за объяснение. Полез дальше разбираться, т.к. за эти пару дней уже понял как вычислить ДПФ, хотя самостоятельно уже недели две занимаюсь, но так и не допонял все. Теперь все вроде сложилось. Остальное вроде уже не так сложно... Но если что спрошу .
Правда на днях все таки разобрался еще и с ДПХ самостоятельно по книге. Но там нет комплексных чисел...
  #27  
Старый 13.12.2009, 15:45
Алексей1981

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

БПФ
Очень хотел разобраться самостоятельно с алгоритмом быстрого преобразования, но как то туго идет. Опять непонятки с поворачивающими множителями. На данный момент понял, что принцип быстрого преобразования сводится к последовательному разбиению вектора на два: четные и нечетные компоненты, получившиеся два вектора разбиваются по этому же принципу на четыре и так далее, до тех пор, пока не останутся вектора с всего двумя значениями. Дпф которых сводится к операциям сложения. Но, ладно, со сложением понятно здесь, с вычитанием что из чего нужно вычитать? Опять таки при объединении играет роль что с чем складывать, ведь один из множителей приходится домножать на поворачивающий множитель... Вот если бы опять глянуть на конкретный пример рассчета БПФ, думаю встанет все на свои места. В прошлый раз пример очень сильно помог расставить все на свои места, с минимумом дополнительных вопросов.
  #28  
Старый 13.12.2009, 20:11
гость

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

Сообщение от Алексей1981 Посмотреть сообщение
Очень хотел разобраться самостоятельно с алгоритмом быстрого преобразования, но как то туго идет. Опять непонятки с поворачивающими множителями. На данный момент понял, что принцип быстрого преобразования сводится к последовательному разбиению вектора на два: четные и нечетные компоненты, получившиеся два вектора разбиваются по этому же принципу на четыре и так далее, до тех пор, пока не останутся вектора с всего двумя значениями. Дпф которых сводится к операциям сложения. Но, ладно, со сложением понятно здесь, с вычитанием что из чего нужно вычитать? Опять таки при объединении играет роль что с чем складывать, ведь один из множителей приходится домножать на поворачивающий множитель... Вот если бы опять глянуть на конкретный пример рассчета БПФ, думаю встанет все на свои места. В прошлый раз пример очень сильно помог расставить все на свои места, с минимумом дополнительных вопросов.
Ты Кормена открывал? Там приведен псевдокод, тебе осталось лишь его зареализовать на чем-нибудь (естественно, для начала, не на ассемблере), а потом ты можешь пройтись дебаггером, посмотреть все множители, слагаемые, вычитаемые и т.п., все что душе угодно.
  #29  
Старый 15.12.2009, 19:18
_persicum_

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

В последнее время много занимался плавучим и целочисленным FFT в связи с его применением в реализации быстрых кодов Рида-Соломона. Прогу (бинарь) можно взять тут.
hxxp://file.qip.ru/file/109465225/ed7e7ff/crc32.html
Излишне даже говорить, что применение FFT позволило реализовать тысячекратно более быстрые и мощные коды, чем те, что имеются в программах ICEECC и QuickPAR.

FFT это не так уж и сложно, нужно только запастись корнями 2,4,8,16 и т.д. степени из единицы, и с их помощью раз за разом строить twiddle-факторы, которые используются в бабочке-fft вида L+wR, L-wR. Несколько советов:

1) следует обязательно опираться на готовые реализации, в меньшей степени на алгоритмы в псевдокоде и совсем забить на теоретические формулы (типа как все замечательно получается и сколько всего сокращается). Средний ум может только проследить логику готового кода, но никак не написать его с нулевого уровня. Там есть хитрые трюки с реверс-битами и некоторые другие.
2) нужно иметь как рекурсивный вариант процедуры, так и нерекурсивный, причем обязательно! Рекурсивный вызывает нерекурсивный, пока данные помещаются в кеше.
3) не следует тянуться к чисто вещественным реализациям вместо комплексных или полукомплексных, равно как и к БПХартли, поскольку комплексные числа дают ускорение на SSE2 и хорошо грузятся в 128-разрядные регистры. А вещественные с разбросанными/упакованными мнимыми и реальными частями будут тормозить
4) если только целью работы не является курсач на асме, следует забить на асм и сосредоточиться на самом алгоритме.
5) существуют FFT c более сложными бабочками, не двойными, а четверными и даже восьмерными бабочками – так называемые radix-4 и radix-8 FFT, так что какой смысл в асм-оптимизации, если исходный радикс-2 алгоритм не самый быстрый по своей природе? Правда, радикс-8 работает не в 8-раз быстрее, а процентов на 30%. Высокие радиксы содержат очень мало умножений.
6) под винды есть хорошая(мощнейшая!) FFTW3.DLL, которая реализует многопоточное FFT с SSE2. Но фишка даже не в этом, а в том, что она поддерживает не только 2^n, но и k*2^n точек, это избавляет пользователя от массивных набивок нулями чтобы достичь размера 2^n (достаточно только чуток нулей до ближайшего k*2^n)
7) FFT – это старье, сейчас все стараются зарелизить фильтры через БПУолша или БПХаара, которые не содержат умножений вообще, поскольку базисные функции там прямоугольные. Сами преобразования гораздо проще чем FFT, а вот их разумное применение гораздо сложнее =))) поскольку циклическую свертку так просто не получить, нужно сильно исхитряться.
8) есть еще одна фишка – DIT и DIF, в русском вольном переводе это нарезка исходных данных или нарезка выходных данных (через реверс-бит перетасовку). Вот с этим я совершенно не разобрался. Многие алгоритмы более эффективны, если применять конкретно DIT или DIF, тогда фазу реверс-бит можно опустить. У меня в проге все сделано на DIT, выходные частоты не требуют перестановки. В общем, работает и ладно.
  #30  
Старый 15.12.2009, 20:47
_реrsicum_

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

Ага, похоже автору нужно прошить FFT на асме в микруху...
Тут путь только один, берешь сишную процедуру которых вагон переводишь ее на свой арм и все. Сам ты как и любой другой нивжисть не сможет реализовать FFT почитывая разные книженки про методы типа разделяй и властвуй и т.п.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача 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