3. Алгоритм адаптации с помощью метода наименьших квадратов (мнк)

Предположим, имеется адаптивный КИХ-фильтр L-го порядка, выход которого вычисляется как

_{где y[k] – выход фильтра, W[k] – вектор весовых коэффициентов фильтра, X[k] – вектор входного сигнала фильтра.}

Во многих используемых на практике алгоритмах адаптации модификация коэффициентов фильтра производится по следующему выражению:

где – шаг сходимости, – градиент функции среднеквадратической ошибки (СКО) (или оценка градиента) в момент k

Вычисление градиента функции СКО является затратным по времени. Вместо этого в качестве оценки можно взять значение . Тогда, взяв производную от по W (вектору весовых коэффициентов), получим значение оценки градиента:

где - ошибка, - вектор входного сигнала.

Имея такую простую оценку градиента, можно определить выражение для модификации вектора весовых коэффициентов:

Такой алгоритм модификации коэффициентов называется методом наименьших квадратов (МНК). Для удобства можно внести константу 2 в как . Тогда получается следующее выражение:

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

где - средняя мощность входного сигнала адаптивного фильтра, L – порядок фильтра.

Соответственно, чем больше порядок фильтра и мощность входного сигнала, тем меньше должен быть шаг сходимости.

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

Вычислительная сложность МНК-алгоритма 2L+1 умножений и 2L сложений на одну итерацию (L – порядок фильтра)

4. Условия сходимости алгоритма мнк

Основное условие сходимости алгоритма МНК – выполнение неравенства, ограничивающего значение шага сходимости :

,

где - наибольшее собственное значение корреляционной матрицы входного сигнала R ( ). Для КИХ-фильтров можно использоваь другое неравенство:

где - средняя мощность входного сигнала адаптивного фильтра, L – порядок фильтра. Чем больше порядок фильтра и мощность входного сигнала, тем меньше должен быть шаг сходимости.

Следует отметить, что неравенство, приведенное выше, характеризует границы выбора шага сходимости для сигналов с более-менее постоянной мощностью. В случае резких всплесков мгновенной мощности при слишком большом шаге сходимости процесс адаптации может стать расходящимся, несмотря на то, что средняя мощность сигнала мала. Поэтому при выборе шага сходимости следует также учитывать мгновенную мощность сигнала (мощность за отсчет).

5. Разновидности алгоритма мнк: стандартный мнк, нормализованный мнк, знаковый мнк

1. Стандартный МНК.

Модификация коэффициентов фильтра в МНК-фильтре производится следующим образом:

_{где W[k] – текущий вектор весовых коэффициентов фильтра, W[k+1] - вектор весовых коэффициентов фильтра на следующей итерации,} – шаг сходимости, e[k] – ошибка фильтра, X[k] – вектор входного сигнала.

Вычислительная сложность МНК-алгоритма 2L+1 умножений и 2L сложений на одну итерацию (L – порядок фильтра)

2. Нормализованный МНК (НМНК)

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

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

В результате постоянный шаг сходимости заменяется на переменный шаг сходимости . При этом на налагается ограничение:

Преимущество НМНК перед МНК в том, что выбрав определенный коэффициент , можно быть уверенным в том, что процесс адаптации не станет расходящимся при слишком большой мощности входного сигнала, а также будет иметь оптимальную скорость сходимости при малой мощности входного сигнала. При этом вычислительная сложность алгоритма НМНК не намного больше, чем МНК и составляет 2L+4 умножений и 2L+3 сложений на одну итерацию.

2. Знаковые разновидности МНК

Идея знакового МНК заключается в замене значений ошибки и вектора значений входного сигнала на знак ошибки и вектор знаков сигнала при вычислении вектора весовых коэффициентов. Это позволяет сократить количество вычислений на итерацию. Существуют три разновидности этого метода:

1. Алгоритм знака ошибки (Sign-error LMS, SELMS)

В этом алгоритме значение ошибки заменяется ее знаком:

Такая замена позволяет сократить одно умножение на итерацию, т. е. вместо 2L+1 умножений на итерацию у МНК получается 2L умножений на итерацию в SELMS (L – порядок фильтра).

2. Алгоритм знака сигнала (Sign-data LMS, SDLMS)

В этом алгоритме вектор значений входного сигнала заменяется вектором знаков сигнала:

Здесь уменьшение количества вычислений уже гораздо существеннее – L+1 умножений на одну итерацию.

3. Алгоритм двойного знака (Sign-sign LMS, SSLMS)

Этот алгоритм представляет собой комбинацию предыдущих, здесь используются и знак ошибки, и вектор знаков сигнала:

В таком алгоритме операция умножения используется только для вычисления свертки, т. е. алгоритм имеет всего L операций умножения на итерацию.

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