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

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

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

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


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

P.S.

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

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

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

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

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

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

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

Вычисляют одно значение корреляционной функции для всех N значений входного сигнала в момент прихода N-го семпла.
Это значение затем сравнивают с порогом по критерию МП.

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

https://www.dsprelated.com/showarticle/776.php

Для blackfin.

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

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

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

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

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

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

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

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