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

[on_river]

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

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

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

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


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

P.S.

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

[blackfin]

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

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

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

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

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

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

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

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