принимает наибольшее значение. Здесь необходимо сделать замечание относительно критерия (1.23). Если длина второй последовательности остается постоянной, то этого нельзя сказать о фрагментах первой последовательности, которые все время меняются. Выравнивание длин этих фрагментов значительно увеличивает трудоемкость операции, поэтому при быстрых вычислениях пренебрегают эти обстоятельством. Необходимые вычисления в (1.23) можно выполнить непосредственно, однако оказалось, что вычисление с помощью ДПФ, которое реатизовано в виде алгоритма быстрого преобразования, оказывается более эффективным. Идея вычисления основывается на (1.21). Чтобы свести ситуацию к случаю обычной свертки, прежде всего надо сделать обе последовательности равными по длине. Для этого вторую из них дополним нулями таким образом, чтобы она имела длину N. Для функций оставим прежние обозначения и введем функцию и(к) = д{—к). Тогда лг- 1 c(n) = ^ f (k)u(n —к) = w(n), к =О где w(n) — свертка функций w —f *и. ДПФ от и U(к) = Y j u{n) e-2n->kn/N = ] Г ff( - n ) e - 2*Jfc(-»)/w = G(k). п п Теперь для подсчета корреляции вычисляют преобразование Фурье от / и д, составляют произведение F(k)G(k) , после чего находят обратное преобразование от этого произведения. Еще раз подчеркнем, что вычисление по этой схеме оказывается значительно эффективнее по сравнению с прямым вычислением согласно (1.23). Однако надо учесть, что все функции считаются периодическими с периодами N и процедура свертки также является циклической. Хотя с(п) определена для всех п, в задаче имеет смысл рассматривать значения с(п) при 0 < п < N —М. Для того чтобы получить истинные
RkJQdWJsaXNoZXIy MTExODQxMg==