Рассматриваемая в предлагаемой статье библиотека содержит около 400 алгоритмов адаптивной фильтрации (АФ), которые могут быть использованы в качестве моделей/прототипов, в частности при проектировании различных радиотехнических устройств и систем, при изучении методов современной обработки сигналов, при реализации микропроцессорных (МП) БИС (например, серии "Мультикор"), разработанных НПЦ "Элвис". Данная библиотека является составной частью прикладной библиотеки алгоритмов и программ указанных БИС. Использование элементов этой библиотеки позволяет ускорить разработку приложений, а использование сложных алгоритмов АФ – добиться высокого качества этих приложений.
На практике в таких устройствах в основном используются адаптивные фильтры, функционирующие на основе простейших градиентных алгоритмов по критерию наименьшего среднеквадратичного отклонения (СКО/LMS) или нормализованного СКО [1]. Такой выбор объясняется наименьшей вычислительной сложностью (числом арифметических операций, требуемых для выполнения одной итерации алгоритма в течение интервала дискретизации обрабатываемого сигнала) и алгоритмической простотой по сравнению с другими алгоритмами АФ. Вычислительная сложность простейших адаптивных алгоритмов равна 2N арифметических операций – умножений со сложениями (действительных или комплексных, в зависимости от вида обрабатываемого сигнала), где N – число весовых коэффициентов адаптивного фильтра. Однако такие алгоритмы обладают низкой эффективностью (медленной сходимостью и остаточными ошибками на выходе фильтра в установившемся режиме, зависящими от величины шага сходимости). Эти недостатки особенно проявляются при обработке нестационарных сигналов.
Успехи микроэлектроники последних лет в области создания высокопроизводительных цифровых сигнальных процессоров (ЦСП) [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.