Об алгоритме (забытом ?) online вычисления корреляции. Опции

[on_river]

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

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

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

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


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

P.S.

Скажите мне, что я изобрел "колесо" :-).

[on_river]

Для blackfin.

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

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

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

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

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

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

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

[blackfin]

Мой кругозор, мои "познания" в теме очень ограничены, если не сказать - совсем никакие.
...
Что скажете ?

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

— Куда мне отсюда идти?
— А куда ты хочешь попасть?
— А мне все равно, только бы попасть куда-нибудь.
— Тогда все равно куда идти. Куда-нибудь ты обязательно попадешь.