реклама на сайте
подробности

 
 
 
Reply to this topicStart new topic
> Об алгоритме (забытом ?) online вычисления корреляции.
on_river
сообщение Oct 12 2017, 08:24
Сообщение #1





Группа: Новичок
Сообщений: 2
Регистрация: 12-10-17
Пользователь №: 99 720



Об алгоритме (забытом ?) online вычисления корреляции.
Плохо - когда не знаешь, а еще и забудешь.

1. Рассматривается поток отсчетов сигнала, последовательно поступающий в регистр (вектор) размерности N.
Вычислитель, при поступлении каждого нового отсчета вычисляет вектор значений размерности N
автокорреляционной функции.

2. Известно, вычисление в "лоб" требует выполнения O(n^2) операций, а с привлечением БПФ - O(n*log(n)).

3. Если к пункту 2 кто-либо добавит: "Известен и алгоритм с O(n), вот ссылка ...", буду очень благодарен - вопрос закрыт.


Искренне, с уважением, Владимир.

P.S.

Скажите мне, что я изобрел "колесо" :-).
Go to the top of the page
 
+Quote Post
blackfin
сообщение Oct 12 2017, 09:05
Сообщение #2


Гуру
******

Группа: Свой
Сообщений: 2 708
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(on_river @ Oct 12 2017, 11:24) *
3. Если к пункту 2 кто-либо добавит: "Известен и алгоритм с O(n), вот ссылка ...", буду очень благодарен - вопрос закрыт.

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

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

Например, при вычислении "скользящего среднего" все значения одной из функций под интегралом равны единице. Это позволяет вычислить одно значение интеграла корреляции в момент прихода N-го семпла с помощью одного сложения и одного вычитания.

Точно так же, если одна из функций под знаком интеграла корреляции комплексная экспонента, то "Алгоритм Герцеля" позволяет вычислить одно значение интеграла корреляции в момент прихода N-го семпла с помощью пяти сложений и трех умножений.

Если же одна из функций четна или нечетна относительно времени, то можно сократить вдвое число умножений.

И нужно иметь ввиду, что как правило, никто не вычисляет все N значений корреляционной функции для всех N*2 значений входного сигнала в момент прихода N-го семпла.

Вычисляют одно значение корреляционной функции для всех N значений входного сигнала в момент прихода N-го семпла.
Это значение затем сравнивают с порогом по критерию МП.
Go to the top of the page
 
+Quote Post
_pv
сообщение Oct 12 2017, 10:27
Сообщение #3


Гуру
******

Группа: Свой
Сообщений: 2 250
Регистрация: 8-04-05
Из: Nsk
Пользователь №: 3 954



если на каждый новый отсчёт не пересчитывать целиком через быстрое Фурье, а через обычное, но sliding DFT, то убрать один отсчёт/добавить новый будет пожалуй O(n).

https://www.dsprelated.com/showarticle/776.php
Go to the top of the page
 
+Quote Post
on_river
сообщение Oct 12 2017, 11:08
Сообщение #4





Группа: Новичок
Сообщений: 2
Регистрация: 12-10-17
Пользователь №: 99 720



Для blackfin.

Спасибо за Ваш ответ.

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

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

"И нужно иметь ввиду, что как правило, никто не вычисляет все N значений корреляционной функции для всех N*2 значений входного сигнала в момент прихода N-го семпла."
Мой кругозор, мои "познания" в теме очень ограничены, если не сказать - совсем никакие. Я делаю вывод - нарисовать алгоритм прямо здесь и сейчас и все тут.
Что скажете ?

"Вычисляют одно значение корреляционной функции для всех N значений входного сигнала в момент прихода N-го семпла."
Т.е. не существует приложений, которые выглядят приблизительно так:

1. Получаем новый отсчет
2. Обновляем значения вектора функции корреляции
3. Оперируем над ..., исследуем значения вектора в целом
к примеру, спектр там получить ...
...
Возврат к 1.

Искренне, с уважением, Владимир.





Go to the top of the page
 
+Quote Post
blackfin
сообщение Oct 12 2017, 11:47
Сообщение #5


Гуру
******

Группа: Свой
Сообщений: 2 708
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(on_river @ Oct 12 2017, 14:08) *
Мой кругозор, мои "познания" в теме очень ограничены, если не сказать - совсем никакие.
...
Что скажете ?

Скажу, что тогда вам не обязательно вычислять интеграл корреляции..
Можете вычислять любой понравившийся вам интеграл или функцию.
В природе есть много хороших и полезных функций.
Можете, к примеру, вычислять функцию Бесселя или Дзета функцию Римана.. biggrin.gif

Цитата
— Куда мне отсюда идти?
— А куда ты хочешь попасть?
— А мне все равно, только бы попасть куда-нибудь.
— Тогда все равно куда идти. Куда-нибудь ты обязательно попадешь.
Go to the top of the page
 
+Quote Post

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

 


RSS Текстовая версия Сейчас: 22nd November 2017 - 11:08
Рейтинг@Mail.ru


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