11.4.1. Рекуррентный алгоритм (Калмана) наименьших квадратов

Рекуррентное по наименьшим квадратам (РНК) оценивание  можно сформулировать следующим образом. Допустим, мы наблюдаем векторы ,  и желаем определить вектор коэффициентов  эквалайзера (линейного или с обратной связью по решению), который минимизирует усреднённые во времени взвешенные квадраты ошибок

                               

где ошибки определяются так

                           

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

                                     

где  - матрица корреляций сигнала, определенная так

                        

а  - вектор взаимных корреляций

                            

Решение (11.4.6) равно

                                     

Матрица  родственна матрице статистических автокорреляций , в то время как вектор  родственен вектору  взаимных корреляций, определенных раньше. Подчеркнём, однако, что  не является тёплицевой матрицей. Мы также хотим напомнить, что для малых значений ,  может быть плохо обусловленной; следовательно, это обычно приводит к первоначальной добавке матрицы  к , где  - малая положительная константа, а  - единичная матрица. При показательном взвешивании по последним данным влияние прибавления  ослабевает со временем.

Теперь предположим, что мы имеем решение (11.4.9) для момента , то есть , и мы желаем вычислить . Неэффективно и, следовательно, непрактично решать систему  линейных уравнений для каждой новой сигнальной компоненты, которая принимается. Чтобы преодолеть эту трудность, мы поступим так. Сначала  можно вычислить рекуррентно следующим образом

                 (11.4.10)

Мы назовем формулу (11.4.10) обновляющее уравнение для .

Поскольку в (11.4.9) требуется обращение , используем соотношение для обращенных матриц

   (11.4.11)

Таким образом,  можно вычислить рекуррентно согласно (11.4.11).

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

                (11.4.12)

где  является скаляром, определяемым так

                         (11.4.13)

С этими определениями (11.4.11) приводится к виду

(11.4.14)

Предположим, что мы умножаем обе части (11.4.14) на . Тогда

     (11.4.15)

Следовательно, вектор калмановского усилия можно также определить как .

Теперь используем соотношение для обратных матриц для получения уравнения, определяющего  по . Поскольку

и

                    (11.4.16)

имеем

      (11.4.17)

Заметим, что  это выход эквалайзера в момент , то есть

                                          (11.4.18)

и

                       (11.4.19)

- это ошибка между желательным символом и его оценкой. Таким образом,  определяется рекуррентно согласно отношению

                    (11.4.20)

Остаточный СКО, получаемый при такой оптимизации, равен

           (11.4.21)

Для суммирования предположим, что мы имеем  и . Когда принимается новая сигнальная компонента имеем . Затем рекуррентные вычисления для обновления и  продолжаются так:

- вычисляется выход:

- вычисляется ошибка:

- вычисляется вектор калмановского усиления:

- вычисляется соотношение обратных матриц

- определяются коэффициенты

   (11.4.22)

Алгоритм, определяемый (11.4.22), назван прямой формой РНК или алгоритмом Калмана. Он подходит, когда эквалайзер имеет трансверсальную (прямая форма) структуру. Заметим, что коэффициенты эквалайзера меняются со временем на величину, равной ошибки , уменьшенной на вектор усиления Калмана . Поскольку  является -мерным каждый коэффициент ячейки в действительности управляется одним из элементов . Как следствие получается быстрая сходимость. В противоположность этому, алгоритм кратчайшего спуска, выраженный в новых обозначениях, определяется так

                  (11.4.23)

и единственным переменным параметром является размер шага ячейки .

Рис.11.4.1 иллюстрирует начальную скорость сходимости этих алгоритмов для канала с фиксируемыми параметрами , ,  и линейного эквалайзера с 11 ячейками. Отношение собственных значений для этого канала . Все коэффициенты эквалайзера были первоначально обнулены. Алгоритм кратчайшего спуска был реализован с . Превосходство алгоритма Калмана очевидно. Это особенно важно при отслеживании меняющегося во времени канала. Для примера, изменения во времени высокочастотного (ВЧ или КВ) ионосферного радиоканала слишком быстрые, чтобы их выравнивать градиентным алгоритмом, но алгоритм Калмана адаптируется достаточно быстро для отслеживания таких изменений.

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

Рис. 11.4.1. Сравнение скорости сходимости алгоритма Калмана и градиентного алгоритма.

Число вычислений или операций (умножений, делений и вычитаний) при расчете величин (11.4.22), пропорционально . Большинство из этих операций используется при определении . Эта часть вычислений также чувствительна к случайному шуму. Чтобы решить эту проблему были разработаны алгоритмы, которые избегают вычисления  согласно (11.4.14). Основа этих алгоритмов сводится к декомпозиции  в виде

                                  (11.4.24)

где  - нижняя треугольная матрица, чьи диагональные элементы – единицы, а  - диагональная матрица. Такая декомпозиция называется факторизацией (см. Бирман, 1977). Эта факторизация описывается в приложении D. В алгоритме факторизации  не обновляется, как в (11.4.14), а вычисляется. Вместо этого при помощи рекуррентного обновления формируется  и .

Алгоритмы НК часто используются в системах управления, которые включают в себя калмановскую фильтрацию. В цифровой связи, алгоритм НК Калмана используется в ФМ модеме с выравниванием на основе обратной связи по решению, спроектированном для передачи с высокой скоростью по ВЧ каналу с номинальной полосой частот 3 кГц. Этот алгоритм описан в статье Хшу (1982). Он имеет вычислительную сложность порядка  (умножения комплексных величин и делений на выходные символы). Для подробного ознакомления с алгоритмами НК в последовательном оценивании читателю рекомендуется книга Бирмана (1977).

Возможно также разработать РНК алгоритмы с вычислительной сложностью, которая возрастает линейно с числом коэффициентов эквалайзера . Такие алгоритмы обычно называются быстрыми РНК алгоритмами,  и они были описаны статьях Караяниса и др. (1983), Чиффи и Кайлата (1989) и Слока и Кайлата (1988).