реклама на сайте
подробности
 
 Wiki Wiki  Photo Photo  Forum Forum  Reviews Reviews  Help (!) Help (!)
 
> Алгоритм ускоренного преобразования фурье на 2**N - 1 точек
Костян
сообщение Jan 15 2013, 13:23
Сообщение #1


Знающий
****

Группа: Свой
Сообщений: 740
Регистрация: 24-07-06
Из: Minsk
Пользователь №: 19 059
Подскажите, существует ли ускоренный алгоритм преобразования фурье на 2**N - 1 точек (например 255 или 511 точек) ?
Go to the top of the page
 
+Quote Post
 
 Start new topic
Ответов
thermit
сообщение Jan 15 2013, 14:12
Сообщение #2


Знающий
****

Группа: Участник
Сообщений: 781
Регистрация: 3-08-09
Пользователь №: 51 730
Цитата
Костян:
не в скорости дело, нужна циклическая свертка на такое кол-во отчетов.


Сделайте на 512. Если результат свертки имеет длину 511, последний отсчет выкидывается, ибо будет равен 0.
Go to the top of the page
 
+Quote Post
Костян
сообщение Jan 15 2013, 14:28
Сообщение #3


Знающий
****

Группа: Свой
Сообщений: 740
Регистрация: 24-07-06
Из: Minsk
Пользователь №: 19 059
QUOTE (thermit @ Jan 15 2013, 13:12) *
Сделайте на 512. Если результат свертки имеет длину 511, последний отсчет выкидывается, ибо будет равен 0.

Так не получиться. Для линейной свертки бы подошло, а для циклической - нет.

QUOTE
У Блейхута не смотрели? Там есть целая глава по коротким сверткам.

Спасибо. Интересная книжка. Блейхута знал по теории кодирования. Алгоритм Виноградова просматриваю, возможно он поможет. Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.

Пока лишь в голове держу вариант БПФ с разными основаниями. Например 255 хорошо разбивается на radix2,radix5 и radix17. 5 куда не шло, но 17 существенно увеличит время рассчета при таком кол-ве точек.
Go to the top of the page
 
+Quote Post
Serg76
сообщение Jan 15 2013, 14:52
Сообщение #4


Профессионал
*****

Группа: Участник
Сообщений: 1 050
Регистрация: 4-04-07
Пользователь №: 26 775
Цитата(Костян @ Jan 15 2013, 18:28) *
Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.

В том то и дело, что алгоритм для "длинных" сверток строится на основе секций из коротких сверток.
Go to the top of the page
 
+Quote Post
Костян
сообщение Jan 15 2013, 14:54
Сообщение #5


Знающий
****

Группа: Свой
Сообщений: 740
Регистрация: 24-07-06
Из: Minsk
Пользователь №: 19 059
QUOTE (Serg76 @ Jan 15 2013, 13:52) *
В том то и дело, что алгоритм для "длинных" сверток строится на основе секций из коротких сверток.

Спасибо. Догадывался. Посмотрю.
Go to the top of the page
 
+Quote Post
Serg76
сообщение Jan 15 2013, 15:06
Сообщение #6


Профессионал
*****

Группа: Участник
Сообщений: 1 050
Регистрация: 4-04-07
Пользователь №: 26 775
Цитата(Костян @ Jan 15 2013, 17:54) *
Спасибо. Догадывался. Посмотрю.

Но будьте осторожны, на самом деле применение данных алгоритмов совсем не означает,
что Вы получите ожидаемый результат. в чистом виде применение данных алгоритмов
имеет выигрыш с точки зрения количества используемых операций сложения/умножения,
но в них не учитываются "накладные" расходы для хранения промежуточных результатов,
переиндексация и др., которые тоже потребляют машинное время и причем немалое. в свое
время тоже пытался реализовать быструю линейную свертку для фильтрации, все получилось,
но результаты оказались плачевными sad.gif. "быстрый" фильтр по скорости оказался на порядок
хуже, нежели классическая реализация. так что хорошо еще раз все взвесьте.
Go to the top of the page
 
+Quote Post

Сообщений в этой теме
- Костян   Алгоритм ускоренного преобразования фурье на 2**N - 1 точек   Jan 15 2013, 13:23
- - Serg76   Неужели так критично по скорости, что нельзя добав...   Jan 15 2013, 13:40
|- - Костян   QUOTE (Serg76 @ Jan 15 2013, 12:40) Неуже...   Jan 15 2013, 13:51
|- - Serg76   Цитата(Костян @ Jan 15 2013, 17:51) не в ...   Jan 15 2013, 14:00
|- - Костян   QUOTE (Serg76 @ Jan 15 2013, 14:06) на са...   Jan 15 2013, 15:30
- - thermit   ЦитатаКостян: Так не получиться. Для линейной свер...   Jan 15 2013, 15:39
|- - Костян   QUOTE (thermit @ Jan 15 2013, 14:39) Чуде...   Jan 16 2013, 12:05
- - eugen_pcad_ru   Когда-то давно читал про это. По моему называется ...   Jan 16 2013, 05:11
- - TSerg   Можно тут взглянуть http://exfile.ru/396643   Jan 16 2013, 07:47
- - thermit   ЦитатаКостян: Возмите длину сигнала x и y равной 1...   Jan 17 2013, 08:37
- - alex_os   Цитата(thermit @ Jan 17 2013, 12:37) 2-й ...   Jan 18 2013, 04:54

 

Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

RSS Текстовая версия Сейчас: 3rd August 2025 - 13:01
Рейтинг@Mail.ru


Страница сгенерированна за 0.01427 секунд с 7
ELECTRONIX ©2004-2016