11.6.2. ВЫЧИСЛЕНИЕ КОРРЕЛЯЦИОННЫХ ОЦЕНОК

Быстрое преобразование Фурье можно эффективно использовать для вычисления оценки автокорреляции

где (Если из было вычтено выборочное среднее, то является оценкой автоковариации.) Если вспомнить, что то становится ясно, что вычисления в (11.72) нужно проводить только для положительных значений т. Ключом к пониманию применения быстрого преобразования Фурье при расчете является тот факт, что есть дискретная свертка Предположим, что мы вычислим от и умножим на Тогда обратное ДПФ от соответствует круговой свертке т. е. круговой корреляции. Пополняя последовательность нулями и вычисляя -точечное ДПФ, можно добиться того, чтобы значения круговой корреляции совпадали с автокорреляцией на интервале

Чтобы понять, каким образом следует выбирать рассмотрим рис. 11.4. На рис. 11.4 а показаны две последовательности

Рис. 11.4. Вычисление оценки автоковариации: а) для последовательности длиной N; б) используемые в круговой корреляции

для конкретного значения . На рис. 11.46 показаны две последовательности участвующие в круговой корреляции, соответствующей . Ясно, что круговая корреляция будет равна при , если не перекрывается (заворачиваясь) с при Из 11.46 видно, что этого перекрытия не будет при

Таким образом, можно вычислить при следующим образом:

1. Сформируем -точечную последовательность, добавляя к нулей.

2. Вычислим -точечное ДПФ:

3. Вычислим -точечное обратное ДПФ:

4. Тогда получим

Если мало, то наиболее эффективным методом может быть простой расчет по (11.72). При этом количество вычислений пропорционально . В противоположность этому вышеприведенная процедура требует количества вычислений, пропорционального Так что для достаточно больших М эта процедура более эффективна. Точное пороговое значение М конечно зависит от конкретной реализации алгоритма БПФ, но можно ожидать, что это значение будет меньше

Как было видно, для уменьшения дисперсии оценки нужно увеличить . В таких случаях может быть неудобно или невозможно эффективно вычислять требуемое -точечное ДПФ. Однако так как М обычно много меньше то можно разбить входной сигнал на секции аналогично тому, как это делалось в § 3.9 для вычисления свертки. Чтобы понять, как это делается, перепишем (11.72) в следующем виде:

где При этом учтено, что считается равным нулю вне интервала , и поэтому верхний предел в (11.72)

можно заменить на Производя соответствующие преобразования, можно записать к

Если определить

Чтобы вычислить (11.73), целесообразно определить -точеч-ные последовательности

Тогда круговая корреляция

равна при если Типичные последовательности изображены на рис. 11.5. Если есть -точечные ДПФ от то при

Рис. 11.5. Две -точечные последовательности, необходимые для вычислении вклада отрезка в оценку автоковариации

Если вместо (11.74) вычислять к

Таким образом, можно вычислить М значений посредством вычисления и одного -точечного обратного ДПФ.

Отметим, что приведенная процедура применима также для вычисления оценки взаимной корреляции Предположим, что имеются выборочные реализации двух последовательностей длиной Как и прежде, определим

в данном случае

при Тогда, используя (11.76) и (11.77), получим

При вычисляется точно так же, только х и у меняются местами, так как

Рэйдер [10] показал, что можно значительно уменьшить объем вычислений при вычислении оценок автокорреляции в частном случае На рис. 11.6 изображены два набора последовательностей при Из этого рисунка

Из (11.81) следует, что

Следовательно, можно найти по (11.82), а не с помощью вычисления отдельных БПФ. Кроме того, два преобразования можно вычислить, используя только одно БПФ. Таким образом, процедура вычисления сводится к следующему:

1. Сформировать последовательность

и вычислить -точечное преобразование Положить по определению .

Рис. 11.6. Набор последовательностей, в которых первая половина совпадает с последней половиной при

2. Для сформировать

и вычислить -точечное преобразование Положить по определению Затем для вычислить

3. Наконец, пусть и -точечное обратное ДПФ от Тогда

Таким образом, в частном случае вычисления нужно вычислить К преобразований и одно обратное преобразование.