eng
За десятилетия своего существования адаптивная обработка сигналов претерпела существенные изменения, пройдя путь от простейших градиентных до сложных рекурсивных алгоритмов по критерию наименьших квадратов (НК). Несмотря на преимущества сложных алгоритмов, на практике продолжают использовать простые алгоритмы, поскольку они имеют несложное математическое описание и требуют для реализации минимальных вычислительных ресурсов.
Рассматриваемая в предлагаемой статье библиотека содержит около 400 алгоритмов адаптивной фильтрации (АФ), которые могут быть использованы в качестве моделей/прототипов, в частности при проектировании различных радиотехнических устройств и систем, при изучении методов современной обработки сигналов, при реализации микропроцессорных (МП) БИС (например, серии "Мультикор"), разработанных НПЦ "Элвис". Данная библиотека является составной частью прикладной библиотеки алгоритмов и программ указанных БИС. Использование элементов этой библиотеки позволяет ускорить разработку приложений, а использование сложных алгоритмов АФ – добиться высокого качества этих приложений.
Рассматриваемая в предлагаемой статье библиотека содержит около 400 алгоритмов адаптивной фильтрации (АФ), которые могут быть использованы в качестве моделей/прототипов, в частности при проектировании различных радиотехнических устройств и систем, при изучении методов современной обработки сигналов, при реализации микропроцессорных (МП) БИС (например, серии "Мультикор"), разработанных НПЦ "Элвис". Данная библиотека является составной частью прикладной библиотеки алгоритмов и программ указанных БИС. Использование элементов этой библиотеки позволяет ускорить разработку приложений, а использование сложных алгоритмов АФ – добиться высокого качества этих приложений.
Адаптивная обработка сигналов – важная составная часть современной цифровой обработки сигналов (ЦОС). Результаты исследований, полученные в области адаптивной обработки сигналов, широко используются в современных изделиях электронной техники, радиотехники, связи и ряда других областей. Например, алгоритмы АФ являются неотъемлемой частью таких устройств, как эхо-компенсаторы, выравниватели электрических и акустических каналов, адаптивные антенные решетки.
На практике в таких устройствах в основном используются адаптивные фильтры, функционирующие на основе простейших градиентных алгоритмов по критерию наименьшего среднеквадратичного отклонения (СКО/LMS) или нормализованного СКО [1]. Такой выбор объясняется наименьшей вычислительной сложностью (числом арифметических операций, требуемых для выполнения одной итерации алгоритма в течение интервала дискретизации обрабатываемого сигнала) и алгоритмической простотой по сравнению с другими алгоритмами АФ. Вычислительная сложность простейших адаптивных алгоритмов равна 2N арифметических операций – умножений со сложениями (действительных или комплексных, в зависимости от вида обрабатываемого сигнала), где N – число весовых коэффициентов адаптивного фильтра. Однако такие алгоритмы обладают низкой эффективностью (медленной сходимостью и остаточными ошибками на выходе фильтра в установившемся режиме, зависящими от величины шага сходимости). Эти недостатки особенно проявляются при обработке нестационарных сигналов.
Простые алгоритмы можно рассматривать как частные случаи более сложных рекурсивных алгоритмов наименьших квадратов (Recursive Least Squares, RLS) [2] или алгоритмов аффинных проекций (Affine Projections, AP) [3]. Более сложные адаптивные алгоритмы обеспечивают более высокие показатели качества: большую скорость сходимости, меньшее значение ошибки в установившемся режиме по сравнению с простейшими алгоритмами. Однако сложные RLS- и AP- алгоритмы менее популярны в приложениях, поскольку для их реализации требуется больше вычислительных ресурсов. Так, для AP-алгоритмов эта сложность оценивается как O(NL), для быстрых (Fast AP – FAP), т.е. вычислительно эффективных алгоритмов, – как O(NL), для RLS-алгоритмов – как O(N2), и быстрых RLS-алгоритмов – O(N). Здесь L – размер проекции (длина скользящего окна, на котором определяется градиент).
Успехи микроэлектроники последних лет в области создания высокопроизводительных цифровых сигнальных процессоров (ЦСП) [4] допускают эффективную реализацию сложных AP- и RLS- алгоритмов [5], которые лишены большинства недостатков, свойственных простым алгоритмам АФ. А наличие прикладных библиотек [6] позволяет использовать проверенные вычислительные процедуры, что существенно ускоряет разработку адаптивных приложений.
ПНЦ "Элвис" имеет уникальную вычислительную платформу "Мультикор" и пополняемую библиотеку алгоритмов АФ [7], которые позволяют эффективно выполнять при ЦОС различные проекты с применением методов АФ.
Данная библиотека содержит около 400 алгоритмов: простых LMS-, NLMS-алгоритмов (включая алгоритмы в частотной области); AP- и FAP-алгоритмов, а также ряд RLS-алгоритмов (включая быстрые алгоритмы) без ограничений и с линейными ограничениями. Библиотека предлагает пользователям различных платформ вычислительные процедуры АФ – как известные, так и оригинальные.
Все эти алгоритмы разработаны для применения в многоканальных адаптивных фильтрах с неодинаковым числом комплексных весовых коэффициентов в каналах (рис.1). Алгоритмы для одноканальных фильтров или фильтров с действительными весовыми коэффициентами являются частными случаями данного решения. Структура отдельного канала многоканального фильтра представлена на рис. 2. Каждый канал – это фильтр с конечной импульсной характеристикой (КИХ), обрабатывающий входной дискретный сигнал xm(k). Его выходной сигнал ym(k) формируется на основе взвешенного суммирования задержанных отсчетов входного сигнала:
...
Здесь k – дискретное время, а Nm – число весовых коэффициентов фильтра m-го канала. Взвешивание осуществляется с помощью весовых коэффициентов hNm(k) = [h0,m, h1,m, ... , hNm - 2,m, hNm - 1,m]T, закон изменения которых определяется алгоритмом АФ. Вектор сигналов многоканального (M-канального) адаптивного фильтра формируется из векторов сигналов отдельных каналов как
...
а вектор весовых коэффициентов – как
...
Здесь и далее полужирными строчными символами обозначены векторы, а полужирными прописными – матрицы. Символы T и H означают транспонированный и эрмитово-сопряженный (транспонированный и комплексно-сопряженный, обозначаемый символом, – на рис. 2), соответственно. Нижние индексы N и Nm означают размерность векторов и квадратных матриц.
В зависимости от решаемой задачи и типа обрабатываемого сигнала адаптивные фильтры могут быть одноканальными или многоканальными с действительными или комплексными весовыми коэффициентами. Так, эхо-компенсатор модема проводного канала связи может рассматриваться как два независимых адаптивных фильтра для подавления сигналов ближнего и дальнего эха или как двухканальный адаптивный фильтр. В зависимости от типа модуляции, используемой в модеме, такой фильтр может иметь действительные или комплексные весовые коэффициенты. Компенсатор акустического эха – это одноканальный адаптивный фильтр, а компенсатор стереоэха – это два двухканальных адаптивных фильтра с одинаковым числом действительных коэффициентов в каналах. Одноканальный выравниватель каналов связи можно рассматривать как двухканальный адаптивный фильтр с неодинаковым числом весовых коэффициентов в каналах. Нелинейные полиномиальные адаптивные фильтры и адаптивные фильтры с бесконечной импульсной характеристикой (БИХ) могут тоже рассматриваться как многоканальные с неодинаковым числом весовых коэффициентов в каналах. Узкополосные адаптивные антенные решетки – это многоканальные адаптивные фильтры с одним комплексным весовым коэффициентом в каждом канале, а широкополосные гидроакустические решетки – это многоканальные адаптивные фильтры с одинаковым числом действительных весовых коэффициентов в каналах.
Таким образом, необходимость такой сложной структуры адаптивных фильтров, как у фильтра на рис.1, обусловлена рядом практических задач. Возможность использования неодинакового числа весовых коэффициентов в каналах фильтра позволяет уменьшить требования к вычислительным ресурсам при реализации адаптивного фильтра, поскольку эти ресурсы пропорциональны полному числу
весовых коэффициентов фильтра, равному N = SM m=1Nm .
В рассматриваемой библиотеке основную часть (около 300 единиц) составляют RLS-алгоритмы АФ, некоторые из которых представлены в работе [2]. Они являются результатом решения задачи минимизации по критерию НК-функционала вида:
...
Здесь d(k) – требуемый сигнал (рис.1). Параметр l служит для экспоненциального взвешивания обрабатываемых сигналов. При обработке нестационарных сигналов этот параметр обеспечивает возможность регулирования следящих свойств адаптивного фильтра в небольших пределах. Допустимое значение параметра l ограничено числом весовых коэффициентов фильтра как max{1-0,4/Nm} Ј l Ј 1, т.е. не может быть сколь угодно малым для обеспечения слежения за быстроменяющимися сигналами. Если значение параметра – меньше указанной нижней границы, то адаптивный фильтр становится неустойчивым (т.е. на практике параметр l – это число, близкое к 1).
Если минимизация функционала E(k) осуществляется при условии CHNJhN(k), где CNJ и fJ – матрица J линейных ограничений и J значений ограничивающих параметров, соответственно, то RLS-алгоритм называется линейно-ограниченным [8]. Здесь двумя нижними индексами обозначен размер (NxJ) прямоугольной (не транспонированной) матрицы.
Решением рассматриваемой задачи (1) является вектор весовых коэффициентов адаптивного фильтра, известный как винеровское решение и определяемый как
...
где RN(k) – корреляционная матрица сигналов адаптивного фильтра, а rN(k) – вектор взаимной корреляции cN(k) и d(k). Если в уравнении (1) p=1, то определение корреляционной матрицы и вектора взаимной корреляции осуществляется на бесконечном окне с экспоненциальным взвешиванием (рис. 3), а если p=k-L+1, то на скользящем окне с экспоненциальным взвешиванием (рис.4). Подобно экспоненциальному взвешиванию, скользящее окно – это прием, позволяющий осуществлять обработку нестационарных сигналов. В оценках матрицы RN(k) и вектора rN(k), определяемых на скользящем окне, присутствует конечное число выборок, равное L. Значение L определяется интервалом стационарности обрабатываемых сигналов T=L/Fs, где Fs – частота дискретизации. Вычислительная сложность RLS-алгоритмов со скользящим окном примерно в два раза больше сложности алгоритмов с бесконечным окном, что является результатом обработки нестационарных сигналов. Дополнительным фактором увеличения вычислительной сложности алгоритмов является умножение ряда переменных, участвующих в вычислениях, на параметр l. При обработке стационарных сигналов и в ряде случаев при обработке нестационарных сигналов параметр l можно исключить из вычислений, т.е. установить равным единице. Это соответствует случаям равномерного взвешивания сигналов (рис. 5 и 6).
Как уже отмечалось, при обработке нестационарных сигналов, предельное значение параметра l не может быть сколь угодно малым, так как при этом адаптивный фильтр становится нестабильным. К этому же приводит и конечное число выборок L в случае использования скользящих окон. Действие обоих факторов приводит в результате к тому, что корреляционная матрица RN(k) становится плохо обусловленной и необратимой, что и вызывает нестабильность адаптивного фильтра.
Одним из эффективных путей сохранения обратимости плохо обусловленной корреляционной матрицы является ее динамическая регуляризация [9]. Однако этот прием в RLS-алгоритмах приводит к увеличению примерно в два раза, по сравнению с обычными алгоритмами, вычислительной сложности алгоритмов с регуляризацией. Регуляризацию корреляционной матрицы можно применять в алгоритмах с бесконечным и скользящим окнами.
В основе большинства RLS-алгоритмов лежат методы обращения корреляционной матрицы (см., например, [2]), которые необходимо применять в уравнении (2). В силу последовательного характера модификации этой матрицы за счет применения скользящего окна или динамической регуляризации все вычисления в RLS-алгоритмах, обусловленные независимыми потоками обрабатываемых данных, также носят последовательный характер. Это является причиной двух- или четырехкратного увеличения вычислительной сложности рассматриваемых RLS-алгоритмов в случае их реализации с помощью одного ЦСП. В работе [10] рассмотрены приемы, на основе которых был разработан ряд RLS-алгоритмов, ориентированных на параллельные вычисления. В таких алгоритмах параллельные потоки данных, обусловленные модификацией корреляционной матрицы адаптивного фильтра, за счет скользящего окна и регуляризации, могут обрабатываться независимо, т.е. параллельно. Это позволяет уменьшить вычислительную нагрузку на один процессор при наличии двух или четырех ЦСП. Такие процессоры сейчас могут быть интегрированы в одной БИС, что позволяет строить компактные устройства обработки сигналов.
Итак, все RLS-алгоритмы АФ в рассматриваемой библиотеке можно представить в виде дерева со следующими четырьмя основными типами на первом от корня уровне:
· с бесконечным равномерным окном;
· с бесконечным экспоненциально взвешенным окном;
· со скользящим равномерным окном;
· со скользящим экспоненциально взвешенным окном.
Каждый из них, на следующем уровне, может быть двух типов: с динамической регуляризацией корреляционной матрицы или без нее. Любой из этих алгоритмов, в свою очередь, может использоваться без ограничений или с линейными ограничениями. И, наконец, на самом последнем уровне эти алгоритмы могут быть реализованы без распараллеливания (с помощью одного ЦСП) или с распараллеливанием (с помощью двух или четырех ЦСП).
Базовые RLS-алгоритмы по используемым процедурам делятся на алгоритмы, работающие на основе:
· леммы об обращении матриц (ЛОМ): на не быстрые, с вычислительной сложностью O(N2), и быстрые, с вычислительной сложностью O(N); из них быстрые, в свою очередь, делятся на алгоритмы: Калмана (Fast Kalman – FK), трансверсального фильтра (Fast Transversal Filter – FTF), последовательной оценки апостериорной ошибки (Fast A Posteriori Error Sequential Technique – FAEST) и стабилизированного алгоритма FAEST;
· QR-разложения матрицы входных сигналов адаптивного фильтра: прямого разложения (не быстрый) с операциями извлечения квадратного корня и без них или обратного разложения с операциями извлечения квадратного корня (с делением на не быстрый алгоритм с преобразованиями Хаусхолдера или быстрый и не быстрый алгоритмы с вращениями Гивенса) или без этих операций с делением на быстрый и не быстрый алгоритмы с вращениями Гивенса.
Исключение операций извлечения квадратного корня достигается с помощью масштабирования переменных [11]. В состав QR-RLS-алгоритмов входят быстрые алгоритмы. В основе их построения лежат приемы [2], использующие перестановочные матрицы. Эти приемы позволяют получать вычислительные процедуры M-канальных фильтров с неодинаковым числом весовых коэффициентов в каналах Nm в виде последовательности M однотипных процедур вспомогательных фильтров с одинаковым числом весовых коэффициентов,
равным N. Напомним, что N = SM m=1Nm – это полное число весовых
коэффициентов многоканального фильтра.
Вторыми по численности в библиотеке являются AP- и FAP-алгоритмы, включая AP-алгоритмы с линейными ограничениями [12]. Многообразие этих алгоритмов определяется использованием модифицированных процедур линейного предсказания, лежащих в основе быстрых RLS-алгоритмов АФ со скользящим окном. Такие процедуры используются как составная часть FAP-алгоритмов. В случае использования параллельных процедур RLS-алгоритмов со скользящим окном, число параллельно обрабатываемых потоков данных равно 2M.
Небольшую часть библиотеки представляют широко известные LMS- и NLMS-алгоритмы АФ, включая такие алгоритмы с переменным шагом сходимости и алгоритмы с линейными ограничениями. Переменный шаг сходимости также используется в AP-FAP-алгоритмах библиотеки. Кроме того, в библиотеку входят LMS- и NLMS-алгоритмы в частотной области (с использованием процедур быстрого преобразования Фурье – БПФ).
Эффективность применения RLS-алгоритмов АФ по сравнению с простейшими LMS- и NLMS-алгоритмами на примере задачи подавления электрического эха отмечена в публикации [5]. Далее, на рис. 7–10 представлены результаты сравнительного моделирования RLS-алгоритмов с линейными ограничениями и бесконечными/скользящими окнами без использования/с использованием динамической регуляризации корреляционной матрицы трехканального адаптивного фильтра с неодинаковым числом весовых коэффициентов в каналах [2] при обработке нестационарных (речевых) сигналов.
Из рис. 7 следует, что заданное ограничение 0 дБ АЧХ адаптивного фильтра на выбранных частотах 1 и 2 кГц обеспечивается обоими алгоритмами: с бесконечным и скользящими окнами. На рис. 7 вертикальные стрелки указывают на частоты ограничений, а горизонтальная пунктирная линия означает уровень ограничения АЧХ. Однако в алгоритмах со скользящим окном (благодаря их следящим свойствам) такой параметр, как увеличение возвратных потерь на эхо (Echo Return Loss Enhancement – ERLE) [5], достигает более высокого значения, чем в алгоритмах с бесконечным окном (см. рис. 8). Улучшение алгоритмов обеспечивается путем введения динамической регуляризации обращения корреляционной матрицы (см. рис. 9 и 10). Значение параметра ERLE, достигаемое с помощью алгоритма с регуляризацией, в среднем не хуже, чем при использовании алгоритма без регуляризации. Таким образом, данные результаты демонстрируют целесообразность использования скользящего окна и динамической регуляризации корреляционной матрицы при обработке нестационарных сигналов с помощью адаптивных фильтров на основе RLS-алгоритмов. Цена такого улучшения – увеличение вычислительной сложности алгоритма, а значит и увеличение требований к ресурсам ЦСП, реализующего такой алгоритм.
Все алгоритмы библиотеки имеют программные MATLAB-прототипы. Функции алгоритмов могут быть использованы для построения моделей различных адаптивных устройств, при проектировании различных радиотехнических систем. Кроме того, алгоритмы библиотеки интегрированы в графический интерфейс пользователя (ГИП) (рис. 11).
ГИП – это инструмент, с помощью которого можно исследовать свойства интересуемого алгоритма с помощью внутренних тестовых сигналов или исследовать работу адаптивного фильтра в составе устройства. В последнем случае используются внешние сигналы, передаваемые ГИПу в виде файлов.
ГИП позволяет выбирать интересуемый алгоритм, определять число каналов адаптивного фильтра (одноканальный или многоканальный) и тип используемой арифметики (действительная или комплексная). Параметры, зависящие от типа алгоритма, расположены в нижней части ГИП. Это – число каналов адаптивного фильтра, число коэффициентов в каждом канале, число коэффициентов импульсных откликов в каналах идентифицируемой линейной системы, амплитуды входных сигналов фильтра, уровень шума на входе требуемого сигнала, частота дискретизации, длина скользящего окна при вычислении ERLE, число итераций алгоритма, шаг сходимости (в LMS-, NLMS-, AP- и быстрых AP- алгоритмах), параметр экспоненциального взвешивания сигналов и параметры начальной и динамической регуляризации (в RLS-алгоритмах), коэффициенты стабилизации (в быстрых RLS-алгоритмах), длина скользящего окна (в RLS-алгоритмах со скользящим окном), число ограничений, частоты ограничений и значения ограничиваемого параметра (в линейно ограниченных алгоритмах).
Результатом моделирования любого из имеющихся алгоритмов АФ является набор графиков, отображаемых в центре ГИП. Это графики входных сигналов адаптивного фильтра xm(k); вектора весовых коэффициентов адаптивного фильтра hN(k) и векторов коэффициентов отдельных каналов hNm(k); импульсного отклика идентифицируемой линейной системы hN и ее отдельных каналов hNm; расстояния между импульсными откликами 10log10{||hN(k) - hN||22 / ||hN||22} и 10log10{||hNm(k) - hNm||22 / ||hNm||22}; АЧХ, ФЧХ, группового времени задержки (ГВЗ) фильтров отдельных каналов и всего адаптивного фильтра; требуемого сигнала d(k); аддитивного шума z(k) на входе требуемого сигнала; зашумленного требуемого сигнала d(k)+z(k); выходного сигнала адаптивного фильтра y(k) = hHN(k-1)aN,c(k); зашумленного сигнала ошибки aN,c(k)=d(k)-y(k)+z(k); не зашумленного сигнала ошибки d(k)-y(k); ERLE, определяемого как
...
где B – длина скользящего окна, определяемая интервалом стационарности обрабатываемых сигналов.
ГИП является достаточно простым с точки зрения пользования инструментом. В начале его работы отображается только ограниченный набор параметров управления и выводятся сообщения о следующих действиях. Параметры, не используемые в выбранном алгоритме, недоступны для ввода или модификации. Неправильный ввод параметра сопровождается предупреждающим сообщением, а кнопки управления становятся доступными только после изменения значений неправильных параметров на правильные. Рис.11 показывает, как выглядит ГИП после окончания моделирования и нажатия одной из кнопок вывода графиков.
Каждый из графиков может иметь масштаб по оси "X", определяемый длиной отображаемого вектора данных. Кроме того, график можно просмотреть на выбранном участке в пределах этой длины. Для вывода графиков однородных параметров (например, входных сигналов многоканального фильтра) используется один и тот же масштаб по оси "Y", определяемый динамическим диапазоном совокупности значений всех однородных параметров. Каждый из графиков может быть также отображен в автоматически выбираемом масштабе по оси "Y". Графики, воспроизводимые в центральной части ГИП, можно дополнительно выводить в отдельном стандартном окне для последующего копирования, сохранения или печати. Входные/выходные сигналы моделирования могут быть сохранены в файлах данных и использованы в качестве тестовых векторов при переносе алгоритмов на другие языки программирования и вычислительные платформы.
Некоторые вычислительные процедуры рассмотренных алгоритмов уже вошли в состав прикладной библиотеки алгоритмов и программ БИС серии "Мультикор" [7], т.е. существуют в виде функций на языке программирования ассемблер этих БИС. Оценки требуемых ресурсов ЦСП для реализации этих алгоритмов приведены в публикации [5]. В настоящее время ведется разработка быстрых лестничных алгоритмов АФ [13] и их реализация в качестве функций БИС серии "Мультикор".
Таким образом, в настоящей работе представлена богатая библиотека алгоритмов АФ. Эта библиотека может служить полезным инструментом для инженеров и исследователей, которые используют адаптивную обработку сигналов в своих разработках. Библиотека может также найти применение в учебных курсах современной обработки сигналов, обработки речи и ряда других дисциплин. Библиотека – ключ к быстрому решению многих прикладных задач, в которых требуется применение методов современной АФ. Она постоянно пополняется за счет разработки новых алгоритмов АФ и их реализации на языке ассемблер БИС серии "Мультикор".
Литература
1. Уидроу Б., Стирнз С. Адаптивная обработка сигналов / Пер. с англ. под ред. Шахгильдяна В.В. – М.: Радио и связь, 1989. – 440 с.
2. Джиган В.И. Многоканальные RLS- и быстрые RLS-алгоритмы адаптивной фильтрации. – Успехи современной радиоэлектроники, 2004, №11, с.48–77.
3. Gay S.L. A fast converging, low complexity adaptive filtering algorithm. – Third International Workshop on Acoustic Echo Control. – Plestin les Greves, France, 1993, p.223–226.
4. Солохина Т. и др. Сигнальные контроллеры компании "ЭЛВИС": первая линейка отечественных DSP. – ЭЛЕКТРОНИКА: НТБ, 2005, №7, с.70–77.
5. Джиган В.И. и др. Подавление электрического эха на базе контроллеров "Мультикор". – ЭЛЕКТРОНИКА: НТБ, 2004, №8, с.26–31.
6. Джиган В.И. Библиотека алгоритмов адаптивной фильтрации. – Доклады 6-й Международной конференции "Цифровая обработка сигналов и ее применения (DSPA-2004)". Том 1. – Москва, 31 марта – 2 апреля 2004, с.89–94.
7. http://www.multicore.ru/news/adaptiv_filter.shtml
8. Resende L.S. at al. A fast least-squares algorithm for linearly constrained adaptive filtering. – IEEE Trans. Signal Processing, 1996, vol.44, N.5, p.1168–1174.
9. Gay S.L. Dynamically regularized fast RLS with application to echo cancellation. – Proc. ICASSP'96, May 1996, p.957–960.
10. Djigan V.I. RLS adaptive filtering algorithms based on parallel computations. – Radio Engineering: Proceedings of Czech and Slovak Technical Universities and URSI Committers. – 2005, vol.14, N.3, p.28–36.
11. Hsieh S.F. at al. A unified square-root-free approach for QRD-based recursive least squares estimation. – IEEE Trans. Signal Processing, 1993, vol.41, N.3, p.1405–1409.
12. Джиган В.И. Уменьшение вычислительных затрат в линейно-ограниченном алгоритме аффинных проекций. – В кн.: Труды 60-й научной сессии, посвященной Дню радио. Москва, 11–13 мая 2005 г.
13. Джиган В.И. Многообразие лестничных RLS-алгоритмов адаптивной фильтрации. – Цифровая обработка сигналов, 2005, №3, с.2–12.
На практике в таких устройствах в основном используются адаптивные фильтры, функционирующие на основе простейших градиентных алгоритмов по критерию наименьшего среднеквадратичного отклонения (СКО/LMS) или нормализованного СКО [1]. Такой выбор объясняется наименьшей вычислительной сложностью (числом арифметических операций, требуемых для выполнения одной итерации алгоритма в течение интервала дискретизации обрабатываемого сигнала) и алгоритмической простотой по сравнению с другими алгоритмами АФ. Вычислительная сложность простейших адаптивных алгоритмов равна 2N арифметических операций – умножений со сложениями (действительных или комплексных, в зависимости от вида обрабатываемого сигнала), где N – число весовых коэффициентов адаптивного фильтра. Однако такие алгоритмы обладают низкой эффективностью (медленной сходимостью и остаточными ошибками на выходе фильтра в установившемся режиме, зависящими от величины шага сходимости). Эти недостатки особенно проявляются при обработке нестационарных сигналов.
Простые алгоритмы можно рассматривать как частные случаи более сложных рекурсивных алгоритмов наименьших квадратов (Recursive Least Squares, RLS) [2] или алгоритмов аффинных проекций (Affine Projections, AP) [3]. Более сложные адаптивные алгоритмы обеспечивают более высокие показатели качества: большую скорость сходимости, меньшее значение ошибки в установившемся режиме по сравнению с простейшими алгоритмами. Однако сложные RLS- и AP- алгоритмы менее популярны в приложениях, поскольку для их реализации требуется больше вычислительных ресурсов. Так, для AP-алгоритмов эта сложность оценивается как O(NL), для быстрых (Fast AP – FAP), т.е. вычислительно эффективных алгоритмов, – как O(NL), для RLS-алгоритмов – как O(N2), и быстрых RLS-алгоритмов – O(N). Здесь L – размер проекции (длина скользящего окна, на котором определяется градиент).
Успехи микроэлектроники последних лет в области создания высокопроизводительных цифровых сигнальных процессоров (ЦСП) [4] допускают эффективную реализацию сложных AP- и RLS- алгоритмов [5], которые лишены большинства недостатков, свойственных простым алгоритмам АФ. А наличие прикладных библиотек [6] позволяет использовать проверенные вычислительные процедуры, что существенно ускоряет разработку адаптивных приложений.
ПНЦ "Элвис" имеет уникальную вычислительную платформу "Мультикор" и пополняемую библиотеку алгоритмов АФ [7], которые позволяют эффективно выполнять при ЦОС различные проекты с применением методов АФ.
Данная библиотека содержит около 400 алгоритмов: простых LMS-, NLMS-алгоритмов (включая алгоритмы в частотной области); AP- и FAP-алгоритмов, а также ряд RLS-алгоритмов (включая быстрые алгоритмы) без ограничений и с линейными ограничениями. Библиотека предлагает пользователям различных платформ вычислительные процедуры АФ – как известные, так и оригинальные.
Все эти алгоритмы разработаны для применения в многоканальных адаптивных фильтрах с неодинаковым числом комплексных весовых коэффициентов в каналах (рис.1). Алгоритмы для одноканальных фильтров или фильтров с действительными весовыми коэффициентами являются частными случаями данного решения. Структура отдельного канала многоканального фильтра представлена на рис. 2. Каждый канал – это фильтр с конечной импульсной характеристикой (КИХ), обрабатывающий входной дискретный сигнал xm(k). Его выходной сигнал ym(k) формируется на основе взвешенного суммирования задержанных отсчетов входного сигнала:
...
Здесь k – дискретное время, а Nm – число весовых коэффициентов фильтра m-го канала. Взвешивание осуществляется с помощью весовых коэффициентов hNm(k) = [h0,m, h1,m, ... , hNm - 2,m, hNm - 1,m]T, закон изменения которых определяется алгоритмом АФ. Вектор сигналов многоканального (M-канального) адаптивного фильтра формируется из векторов сигналов отдельных каналов как
...
а вектор весовых коэффициентов – как
...
Здесь и далее полужирными строчными символами обозначены векторы, а полужирными прописными – матрицы. Символы T и H означают транспонированный и эрмитово-сопряженный (транспонированный и комплексно-сопряженный, обозначаемый символом, – на рис. 2), соответственно. Нижние индексы N и Nm означают размерность векторов и квадратных матриц.
В зависимости от решаемой задачи и типа обрабатываемого сигнала адаптивные фильтры могут быть одноканальными или многоканальными с действительными или комплексными весовыми коэффициентами. Так, эхо-компенсатор модема проводного канала связи может рассматриваться как два независимых адаптивных фильтра для подавления сигналов ближнего и дальнего эха или как двухканальный адаптивный фильтр. В зависимости от типа модуляции, используемой в модеме, такой фильтр может иметь действительные или комплексные весовые коэффициенты. Компенсатор акустического эха – это одноканальный адаптивный фильтр, а компенсатор стереоэха – это два двухканальных адаптивных фильтра с одинаковым числом действительных коэффициентов в каналах. Одноканальный выравниватель каналов связи можно рассматривать как двухканальный адаптивный фильтр с неодинаковым числом весовых коэффициентов в каналах. Нелинейные полиномиальные адаптивные фильтры и адаптивные фильтры с бесконечной импульсной характеристикой (БИХ) могут тоже рассматриваться как многоканальные с неодинаковым числом весовых коэффициентов в каналах. Узкополосные адаптивные антенные решетки – это многоканальные адаптивные фильтры с одним комплексным весовым коэффициентом в каждом канале, а широкополосные гидроакустические решетки – это многоканальные адаптивные фильтры с одинаковым числом действительных весовых коэффициентов в каналах.
Таким образом, необходимость такой сложной структуры адаптивных фильтров, как у фильтра на рис.1, обусловлена рядом практических задач. Возможность использования неодинакового числа весовых коэффициентов в каналах фильтра позволяет уменьшить требования к вычислительным ресурсам при реализации адаптивного фильтра, поскольку эти ресурсы пропорциональны полному числу
весовых коэффициентов фильтра, равному N = SM m=1Nm .
В рассматриваемой библиотеке основную часть (около 300 единиц) составляют RLS-алгоритмы АФ, некоторые из которых представлены в работе [2]. Они являются результатом решения задачи минимизации по критерию НК-функционала вида:
...
Здесь d(k) – требуемый сигнал (рис.1). Параметр l служит для экспоненциального взвешивания обрабатываемых сигналов. При обработке нестационарных сигналов этот параметр обеспечивает возможность регулирования следящих свойств адаптивного фильтра в небольших пределах. Допустимое значение параметра l ограничено числом весовых коэффициентов фильтра как max{1-0,4/Nm} Ј l Ј 1, т.е. не может быть сколь угодно малым для обеспечения слежения за быстроменяющимися сигналами. Если значение параметра – меньше указанной нижней границы, то адаптивный фильтр становится неустойчивым (т.е. на практике параметр l – это число, близкое к 1).
Если минимизация функционала E(k) осуществляется при условии CHNJhN(k), где CNJ и fJ – матрица J линейных ограничений и J значений ограничивающих параметров, соответственно, то RLS-алгоритм называется линейно-ограниченным [8]. Здесь двумя нижними индексами обозначен размер (NxJ) прямоугольной (не транспонированной) матрицы.
Решением рассматриваемой задачи (1) является вектор весовых коэффициентов адаптивного фильтра, известный как винеровское решение и определяемый как
...
где RN(k) – корреляционная матрица сигналов адаптивного фильтра, а rN(k) – вектор взаимной корреляции cN(k) и d(k). Если в уравнении (1) p=1, то определение корреляционной матрицы и вектора взаимной корреляции осуществляется на бесконечном окне с экспоненциальным взвешиванием (рис. 3), а если p=k-L+1, то на скользящем окне с экспоненциальным взвешиванием (рис.4). Подобно экспоненциальному взвешиванию, скользящее окно – это прием, позволяющий осуществлять обработку нестационарных сигналов. В оценках матрицы RN(k) и вектора rN(k), определяемых на скользящем окне, присутствует конечное число выборок, равное L. Значение L определяется интервалом стационарности обрабатываемых сигналов T=L/Fs, где Fs – частота дискретизации. Вычислительная сложность RLS-алгоритмов со скользящим окном примерно в два раза больше сложности алгоритмов с бесконечным окном, что является результатом обработки нестационарных сигналов. Дополнительным фактором увеличения вычислительной сложности алгоритмов является умножение ряда переменных, участвующих в вычислениях, на параметр l. При обработке стационарных сигналов и в ряде случаев при обработке нестационарных сигналов параметр l можно исключить из вычислений, т.е. установить равным единице. Это соответствует случаям равномерного взвешивания сигналов (рис. 5 и 6).
Как уже отмечалось, при обработке нестационарных сигналов, предельное значение параметра l не может быть сколь угодно малым, так как при этом адаптивный фильтр становится нестабильным. К этому же приводит и конечное число выборок L в случае использования скользящих окон. Действие обоих факторов приводит в результате к тому, что корреляционная матрица RN(k) становится плохо обусловленной и необратимой, что и вызывает нестабильность адаптивного фильтра.
Одним из эффективных путей сохранения обратимости плохо обусловленной корреляционной матрицы является ее динамическая регуляризация [9]. Однако этот прием в RLS-алгоритмах приводит к увеличению примерно в два раза, по сравнению с обычными алгоритмами, вычислительной сложности алгоритмов с регуляризацией. Регуляризацию корреляционной матрицы можно применять в алгоритмах с бесконечным и скользящим окнами.
В основе большинства RLS-алгоритмов лежат методы обращения корреляционной матрицы (см., например, [2]), которые необходимо применять в уравнении (2). В силу последовательного характера модификации этой матрицы за счет применения скользящего окна или динамической регуляризации все вычисления в RLS-алгоритмах, обусловленные независимыми потоками обрабатываемых данных, также носят последовательный характер. Это является причиной двух- или четырехкратного увеличения вычислительной сложности рассматриваемых RLS-алгоритмов в случае их реализации с помощью одного ЦСП. В работе [10] рассмотрены приемы, на основе которых был разработан ряд RLS-алгоритмов, ориентированных на параллельные вычисления. В таких алгоритмах параллельные потоки данных, обусловленные модификацией корреляционной матрицы адаптивного фильтра, за счет скользящего окна и регуляризации, могут обрабатываться независимо, т.е. параллельно. Это позволяет уменьшить вычислительную нагрузку на один процессор при наличии двух или четырех ЦСП. Такие процессоры сейчас могут быть интегрированы в одной БИС, что позволяет строить компактные устройства обработки сигналов.
Итак, все RLS-алгоритмы АФ в рассматриваемой библиотеке можно представить в виде дерева со следующими четырьмя основными типами на первом от корня уровне:
· с бесконечным равномерным окном;
· с бесконечным экспоненциально взвешенным окном;
· со скользящим равномерным окном;
· со скользящим экспоненциально взвешенным окном.
Каждый из них, на следующем уровне, может быть двух типов: с динамической регуляризацией корреляционной матрицы или без нее. Любой из этих алгоритмов, в свою очередь, может использоваться без ограничений или с линейными ограничениями. И, наконец, на самом последнем уровне эти алгоритмы могут быть реализованы без распараллеливания (с помощью одного ЦСП) или с распараллеливанием (с помощью двух или четырех ЦСП).
Базовые RLS-алгоритмы по используемым процедурам делятся на алгоритмы, работающие на основе:
· леммы об обращении матриц (ЛОМ): на не быстрые, с вычислительной сложностью O(N2), и быстрые, с вычислительной сложностью O(N); из них быстрые, в свою очередь, делятся на алгоритмы: Калмана (Fast Kalman – FK), трансверсального фильтра (Fast Transversal Filter – FTF), последовательной оценки апостериорной ошибки (Fast A Posteriori Error Sequential Technique – FAEST) и стабилизированного алгоритма FAEST;
· QR-разложения матрицы входных сигналов адаптивного фильтра: прямого разложения (не быстрый) с операциями извлечения квадратного корня и без них или обратного разложения с операциями извлечения квадратного корня (с делением на не быстрый алгоритм с преобразованиями Хаусхолдера или быстрый и не быстрый алгоритмы с вращениями Гивенса) или без этих операций с делением на быстрый и не быстрый алгоритмы с вращениями Гивенса.
Исключение операций извлечения квадратного корня достигается с помощью масштабирования переменных [11]. В состав QR-RLS-алгоритмов входят быстрые алгоритмы. В основе их построения лежат приемы [2], использующие перестановочные матрицы. Эти приемы позволяют получать вычислительные процедуры M-канальных фильтров с неодинаковым числом весовых коэффициентов в каналах Nm в виде последовательности M однотипных процедур вспомогательных фильтров с одинаковым числом весовых коэффициентов,
равным N. Напомним, что N = SM m=1Nm – это полное число весовых
коэффициентов многоканального фильтра.
Вторыми по численности в библиотеке являются AP- и FAP-алгоритмы, включая AP-алгоритмы с линейными ограничениями [12]. Многообразие этих алгоритмов определяется использованием модифицированных процедур линейного предсказания, лежащих в основе быстрых RLS-алгоритмов АФ со скользящим окном. Такие процедуры используются как составная часть FAP-алгоритмов. В случае использования параллельных процедур RLS-алгоритмов со скользящим окном, число параллельно обрабатываемых потоков данных равно 2M.
Небольшую часть библиотеки представляют широко известные LMS- и NLMS-алгоритмы АФ, включая такие алгоритмы с переменным шагом сходимости и алгоритмы с линейными ограничениями. Переменный шаг сходимости также используется в AP-FAP-алгоритмах библиотеки. Кроме того, в библиотеку входят LMS- и NLMS-алгоритмы в частотной области (с использованием процедур быстрого преобразования Фурье – БПФ).
Эффективность применения RLS-алгоритмов АФ по сравнению с простейшими LMS- и NLMS-алгоритмами на примере задачи подавления электрического эха отмечена в публикации [5]. Далее, на рис. 7–10 представлены результаты сравнительного моделирования RLS-алгоритмов с линейными ограничениями и бесконечными/скользящими окнами без использования/с использованием динамической регуляризации корреляционной матрицы трехканального адаптивного фильтра с неодинаковым числом весовых коэффициентов в каналах [2] при обработке нестационарных (речевых) сигналов.
Из рис. 7 следует, что заданное ограничение 0 дБ АЧХ адаптивного фильтра на выбранных частотах 1 и 2 кГц обеспечивается обоими алгоритмами: с бесконечным и скользящими окнами. На рис. 7 вертикальные стрелки указывают на частоты ограничений, а горизонтальная пунктирная линия означает уровень ограничения АЧХ. Однако в алгоритмах со скользящим окном (благодаря их следящим свойствам) такой параметр, как увеличение возвратных потерь на эхо (Echo Return Loss Enhancement – ERLE) [5], достигает более высокого значения, чем в алгоритмах с бесконечным окном (см. рис. 8). Улучшение алгоритмов обеспечивается путем введения динамической регуляризации обращения корреляционной матрицы (см. рис. 9 и 10). Значение параметра ERLE, достигаемое с помощью алгоритма с регуляризацией, в среднем не хуже, чем при использовании алгоритма без регуляризации. Таким образом, данные результаты демонстрируют целесообразность использования скользящего окна и динамической регуляризации корреляционной матрицы при обработке нестационарных сигналов с помощью адаптивных фильтров на основе RLS-алгоритмов. Цена такого улучшения – увеличение вычислительной сложности алгоритма, а значит и увеличение требований к ресурсам ЦСП, реализующего такой алгоритм.
Все алгоритмы библиотеки имеют программные MATLAB-прототипы. Функции алгоритмов могут быть использованы для построения моделей различных адаптивных устройств, при проектировании различных радиотехнических систем. Кроме того, алгоритмы библиотеки интегрированы в графический интерфейс пользователя (ГИП) (рис. 11).
ГИП – это инструмент, с помощью которого можно исследовать свойства интересуемого алгоритма с помощью внутренних тестовых сигналов или исследовать работу адаптивного фильтра в составе устройства. В последнем случае используются внешние сигналы, передаваемые ГИПу в виде файлов.
ГИП позволяет выбирать интересуемый алгоритм, определять число каналов адаптивного фильтра (одноканальный или многоканальный) и тип используемой арифметики (действительная или комплексная). Параметры, зависящие от типа алгоритма, расположены в нижней части ГИП. Это – число каналов адаптивного фильтра, число коэффициентов в каждом канале, число коэффициентов импульсных откликов в каналах идентифицируемой линейной системы, амплитуды входных сигналов фильтра, уровень шума на входе требуемого сигнала, частота дискретизации, длина скользящего окна при вычислении ERLE, число итераций алгоритма, шаг сходимости (в LMS-, NLMS-, AP- и быстрых AP- алгоритмах), параметр экспоненциального взвешивания сигналов и параметры начальной и динамической регуляризации (в RLS-алгоритмах), коэффициенты стабилизации (в быстрых RLS-алгоритмах), длина скользящего окна (в RLS-алгоритмах со скользящим окном), число ограничений, частоты ограничений и значения ограничиваемого параметра (в линейно ограниченных алгоритмах).
Результатом моделирования любого из имеющихся алгоритмов АФ является набор графиков, отображаемых в центре ГИП. Это графики входных сигналов адаптивного фильтра xm(k); вектора весовых коэффициентов адаптивного фильтра hN(k) и векторов коэффициентов отдельных каналов hNm(k); импульсного отклика идентифицируемой линейной системы hN и ее отдельных каналов hNm; расстояния между импульсными откликами 10log10{||hN(k) - hN||22 / ||hN||22} и 10log10{||hNm(k) - hNm||22 / ||hNm||22}; АЧХ, ФЧХ, группового времени задержки (ГВЗ) фильтров отдельных каналов и всего адаптивного фильтра; требуемого сигнала d(k); аддитивного шума z(k) на входе требуемого сигнала; зашумленного требуемого сигнала d(k)+z(k); выходного сигнала адаптивного фильтра y(k) = hHN(k-1)aN,c(k); зашумленного сигнала ошибки aN,c(k)=d(k)-y(k)+z(k); не зашумленного сигнала ошибки d(k)-y(k); ERLE, определяемого как
...
где B – длина скользящего окна, определяемая интервалом стационарности обрабатываемых сигналов.
ГИП является достаточно простым с точки зрения пользования инструментом. В начале его работы отображается только ограниченный набор параметров управления и выводятся сообщения о следующих действиях. Параметры, не используемые в выбранном алгоритме, недоступны для ввода или модификации. Неправильный ввод параметра сопровождается предупреждающим сообщением, а кнопки управления становятся доступными только после изменения значений неправильных параметров на правильные. Рис.11 показывает, как выглядит ГИП после окончания моделирования и нажатия одной из кнопок вывода графиков.
Каждый из графиков может иметь масштаб по оси "X", определяемый длиной отображаемого вектора данных. Кроме того, график можно просмотреть на выбранном участке в пределах этой длины. Для вывода графиков однородных параметров (например, входных сигналов многоканального фильтра) используется один и тот же масштаб по оси "Y", определяемый динамическим диапазоном совокупности значений всех однородных параметров. Каждый из графиков может быть также отображен в автоматически выбираемом масштабе по оси "Y". Графики, воспроизводимые в центральной части ГИП, можно дополнительно выводить в отдельном стандартном окне для последующего копирования, сохранения или печати. Входные/выходные сигналы моделирования могут быть сохранены в файлах данных и использованы в качестве тестовых векторов при переносе алгоритмов на другие языки программирования и вычислительные платформы.
Некоторые вычислительные процедуры рассмотренных алгоритмов уже вошли в состав прикладной библиотеки алгоритмов и программ БИС серии "Мультикор" [7], т.е. существуют в виде функций на языке программирования ассемблер этих БИС. Оценки требуемых ресурсов ЦСП для реализации этих алгоритмов приведены в публикации [5]. В настоящее время ведется разработка быстрых лестничных алгоритмов АФ [13] и их реализация в качестве функций БИС серии "Мультикор".
Таким образом, в настоящей работе представлена богатая библиотека алгоритмов АФ. Эта библиотека может служить полезным инструментом для инженеров и исследователей, которые используют адаптивную обработку сигналов в своих разработках. Библиотека может также найти применение в учебных курсах современной обработки сигналов, обработки речи и ряда других дисциплин. Библиотека – ключ к быстрому решению многих прикладных задач, в которых требуется применение методов современной АФ. Она постоянно пополняется за счет разработки новых алгоритмов АФ и их реализации на языке ассемблер БИС серии "Мультикор".
Литература
1. Уидроу Б., Стирнз С. Адаптивная обработка сигналов / Пер. с англ. под ред. Шахгильдяна В.В. – М.: Радио и связь, 1989. – 440 с.
2. Джиган В.И. Многоканальные RLS- и быстрые RLS-алгоритмы адаптивной фильтрации. – Успехи современной радиоэлектроники, 2004, №11, с.48–77.
3. Gay S.L. A fast converging, low complexity adaptive filtering algorithm. – Third International Workshop on Acoustic Echo Control. – Plestin les Greves, France, 1993, p.223–226.
4. Солохина Т. и др. Сигнальные контроллеры компании "ЭЛВИС": первая линейка отечественных DSP. – ЭЛЕКТРОНИКА: НТБ, 2005, №7, с.70–77.
5. Джиган В.И. и др. Подавление электрического эха на базе контроллеров "Мультикор". – ЭЛЕКТРОНИКА: НТБ, 2004, №8, с.26–31.
6. Джиган В.И. Библиотека алгоритмов адаптивной фильтрации. – Доклады 6-й Международной конференции "Цифровая обработка сигналов и ее применения (DSPA-2004)". Том 1. – Москва, 31 марта – 2 апреля 2004, с.89–94.
7. http://www.multicore.ru/news/adaptiv_filter.shtml
8. Resende L.S. at al. A fast least-squares algorithm for linearly constrained adaptive filtering. – IEEE Trans. Signal Processing, 1996, vol.44, N.5, p.1168–1174.
9. Gay S.L. Dynamically regularized fast RLS with application to echo cancellation. – Proc. ICASSP'96, May 1996, p.957–960.
10. Djigan V.I. RLS adaptive filtering algorithms based on parallel computations. – Radio Engineering: Proceedings of Czech and Slovak Technical Universities and URSI Committers. – 2005, vol.14, N.3, p.28–36.
11. Hsieh S.F. at al. A unified square-root-free approach for QRD-based recursive least squares estimation. – IEEE Trans. Signal Processing, 1993, vol.41, N.3, p.1405–1409.
12. Джиган В.И. Уменьшение вычислительных затрат в линейно-ограниченном алгоритме аффинных проекций. – В кн.: Труды 60-й научной сессии, посвященной Дню радио. Москва, 11–13 мая 2005 г.
13. Джиган В.И. Многообразие лестничных RLS-алгоритмов адаптивной фильтрации. – Цифровая обработка сигналов, 2005, №3, с.2–12.
Отзывы читателей
