Содержание к диссертации
Введение
1. Многоканальные rls-алгоритмы с квадратич ной вычислительной сложностью 29
1.1. RLS-алгоритм на основе леммы об обращении матрицы 30
1.2. Алгоритм на основе прямого QR-разложения 35
1.3. Алгоритмы на основе обратного QR-разложения 39
1.4. Исключение операций извлечения квадратного корня в алгоритмах на основе QR-разложения 45
1.5. Регуляризированные версии RLS-алгоритмов 49
1.6. Одновременное использование скользящего окна и регуляризации в RLS-алгоритмах 59
1.7. Сравнительные характеристики алгоритмов 63
1.8. Основные результаты главы 1 67
2. Многоканальные rls-алгоритмы с линейной вычислительной сложностью 68
2.1. Основные соотношения 69
2.2. Многоканальные быстрые RLS-алгоритмы с неодинаковым количеством весовых коэффициентов в каналах 75
2.3. Быстрые RLS-алгоритмы на основе леммы об обращении клеточных матриц 77
2.4. Быстрые алгоритмы на основе обратного QR-разложения 87
2.5. Регуляризированные версии быстрых RLS-алгоритмов 96
2.6. Одновременно использование скользящего окна и регуляризации в быстрых RLS-алгоритмах 109
2.7. Сравнительные характеристики алгоритмов 113
2.8. Основные результаты главы 2 115
3. Быстрые лестничные RLS-алгоритмы 117
3.1. Основные соотношения 118
3.2. Одноканальные лестничные RLS-алгоритмы со скользящим окном 123
3.3. Многоканальные лестничные RLS-алгоритмы с одинаковым количеством весовых коэффициентов в каналах 146
3.4. Регуляризированные версии лестничных RLS-алгоритмов 152
3.5. Сравнительные характеристики алгоритмов 161
3.6. Основные результаты главы 3 165
4. Многоканальные линейно-ограниченные RLS алгоритмы 167
4.1. Постановка задачи 167
4.2. Решение задачи для случая скользящего окна 175
4.3. Регуляризированные версии линейно-ограниченных RLS-алгоритмов 182
4.4. Сравнительные характеристики алгоритмов 187
4.5. Основные результаты главы 4 196
5. Параллельные RLS- и быстрые RLS-алгоритмы 198
5.1. Способ построения параллельных RLS-алгоритмов 198
5.2. RLS-алгоритмы, допускающие вычисления с помощью двух или четырех процессоров 204
5.3. Быстрые RLS-алгоритмы, допускающие вычисления с помощью двух или четырех процессоров 208
5.4. Быстрые лестничные RLS-алгоритмы, допускающие вычисления с помощью двух или четырех процессоров 216
5.5. Сравнительные характеристики алгоритмов 223
5.6. Основные результаты главы 5 227
6. Применение адаптивных алгоритмов 229
6.1. Особенности построения быстрых многоканальных алгоритмов аффинных проекций 230
6.2. Полиномиальные адаптивные фильтры 252
6.3 Инициализация RLS-алгоритмов 265
6.4. Моделирование алгоритмов адаптивной фильтрации 272
6.5. RLS-алгоритм, учитывающий структуру обрабатываемого сигнала 279
6.6. Создание прикладной библиотеки алгоритмов адаптивной фильтрации 291
6.7. Основные результаты главы 6 297
Заключение 299
Список литературы 304
Приложения 338
- Алгоритм на основе прямого QR-разложения
- Быстрые алгоритмы на основе обратного QR-разложения
- Многоканальные лестничные RLS-алгоритмы с одинаковым количеством весовых коэффициентов в каналах
- Регуляризированные версии линейно-ограниченных RLS-алгоритмов
Введение к работе
Современная радиотехника включает в себя большое число различных научно-технических областей. Одна из этих областей - цифровая обработка сигналов (ЦОС) - также состоит из ряда научно-технических направлений, среди которых важное место занимает адаптивная фильтрация. Адаптивные фильтры сегодня широко используются в оборудовании радиоэлектронных систем связи, радио- и гидролокации, автоматического управления, медицины, бытовой электроники [1].
Адаптивный фильтр является основным элементом компенсаторов сигналов электрического эха, возникающего при переходе из четырехпроводнои на двухпроводную линию связи [2-18]. Такие переходы используются в оборудовании телефонных станций, в модемах, включая модемы для цифровых выделенных линий [19, 20]. При проведении конференц-связи и при озвучивании помещений возникает акустическое эхо. Подобно сигналам электрического эха, акустическое эхо компенсируется с помощью адаптивных фильтров [21-37].
Адаптивные фильтры также используются для построения выравнивателей (эквалайзеров) каналов связи [10, 11, 13, 38-71] и выравнивателей акустических каналов при высококачественном воспроизведении звука [72-82].
Компенсация сигналов источников пространственно разнесенных помех в радиосистемах осуществляется с помощью адаптивных антенных решеток [83-94]. В диапазоне звуковых частот мешающие сигналы компенсируются с помощью адаптивных акустических (микрофонных) решеток [28, 29, 32, 36]. Антенные и акустические решетки вместе с алгоритмами управления весовыми коэффициентами представляют собой адаптивные фильтры.
В промышленных помещениях и кабинах летательных аппаратов компенсация шумов часто осуществляется с помощью активных компенсаторов шума [95-121]. Эти устройства тоже строятся на основе адаптивных фильтров.
Указанные приложения условно представлены на рис. 1. Основные области применения адаптивных фильтров не исчерпываются перечисленными
Адаптивные фильтры
НІМІЇ
Компенсаторы сигналов электрического эха
І І І І І I
Компенсаторы сигналов акустического эха
'Г I I I _
Выравниватели
электрических каналов
связи
Адаптивные антенные решетки
і І I
Адаптивные акустические решетки
t
Активные компенсаторы шума
Адаптивные
полиномиальные
фильтры
Рис. 1. Основные области применения адаптивных фильтров
7 выше. Например, часть вычислительных процедур ряда адаптивных алгоритмов (линейное предсказание) используется в устройствах сжатия речи (вокодерах) или в рассматриваемых в главе 6 других адаптивных алгоритмах - быстрых алгоритмах аффинных проекций. На основе линейных адаптивных фильтров строятся нелинейные полиномиальные адаптивные фильтры. Выделенные на рис. 1 жирными линиями приложения будут рассмотрены в качестве примеров применения представленных в диссертационной работе алгоритмов. Эффективность функционирования (длительность переходного процесса, уровень ошибок в установившемся режиме) перечисленных и других адаптивных устройств зависит от алгоритма, лежащего в основе адаптивного фильтра.
На практике в качестве алгоритмов адаптивной фильтрации обычно используются различные варианты простейшего с точки зрения вычислительной сложности градиентного алгоритма по критерию наименьшего среднеквадратичного отклонения (Least Mean Squares, LMS) [122]. Они характеризуются наименьшим числом арифметических операций среди других адаптивных алгоритмов. Однако LMS-алгоритмам свойственны известные недостатки, среди которых медленная сходимость и высокий уровень остаточных ошибок в установившемся режиме, зависящие от параметра, именуемого шагом сходимости.
Промежуточные по эффективности адаптивные алгоритмы - это быстрые алгоритмы аффинных проекций (Fast Affine Projections, FAP) [123-127]. В обозначенных выше терминах эффективность таких алгоритмов выше, чем у LMS-алгоритмов. Кроме того, FAP-алгоритмы имеют вычислительную сложность близкую к сложности LMS-алгоритмов в случае их использования в адаптивных фильтрах с большим количеством весовых коэффициентов (сотни, тысячи). Такие фильтры применяются, например, при решении задач подавления эхо-сигналов.
Самыми сложными с вычислительной точки зрения являются рекурсивные алгоритмы адаптивной фильтрации по критерию наименьших квадратов (Recursive Least Squares. RLSi, основные разновидности которых могут быть найдены в работ ах обзорною характера 1128-136). Эти алгоритмы привлека-
8 тельны тем, что они быстро сходятся и обеспечивают малые значения остаточных ошибок в установившемся режиме. RLS-алгоритмы представляют собой различные варианты процедур вычисления вектора весовых коэффициентов фильтров Винера.
Условная классификация адаптивных алгоритмов с точки зрения вычислительной сложности приведена на рис. 2. Различные аспекты получения, особенностей функционирования и применения известных видов RLS-алгоритмов адаптивной фильтрации, кроме перечисленных ранее публикаций, могут быть также найдены в ряде специализированных книг по адаптивной обработке сигналов, в книгах по ЦОС и в книгах по различным проблемам современной радиотехники [137-158].
LMS-алгоритмы относятся к вычислительно простым алгоритмам. Оценка сложности таких алгоритмов - 0(N) = 2N арифметических операций (сложений с умножениями, действительных или комплексных в зависимости от вида обрабатываемых сигналов), требуемых для выполнения одной итерации, где N - количество весовых коэффициентов адаптивного фильтра. К простым алгоритмам также относятся нормализованные LMS-алгоритмы (Normalized LMS, NLMS), в которых шаг сходимости нормализуется к средней энергии входного сигнала адаптивного фильтра.
LMS- и NLMS-алгоритмы для адаптивных фильтров также реализуются в частотной области [159] с использованием процедур быстрого преобразования Фурье (БПФ). В таких алгоритмах за счет блочной обработки средняя вычислительная сложность на одну итерацию меньше, чем у одноименных алгоритмов во временной области. Блочные алгоритмы используются в основном в задачах, где требуются адаптивные фильтры с большим количеством весовых коэффициентов. Адаптивные фильтры на основе LMS- и NLMS-алгоритмов в частотной области представляют собой многоканальные адаптивные фильтры с одним комплексным весовым коэффициентом в каждом из каналов. Такие фильтры имеют недостаток, заключающийся в задержке обрабатываемого сигнала. Частично этот недостаток устраняется в адаптивных фильтрах, содержащих
Рис. 2. Классификация адаптивных алгоритмов по сложности
10 несколько весовых коэффициентов в каждом из каналов многоканального фильтра [160]. Подполосные адаптивные фильтры [70] также представляют собой разновидность фильтров [160]. В подполосных адаптивных фильтрах разделение входного сигнала по частоте осуществляется с помощью банков фильтров и при обработке действительных сигналов используются действительные весовые коэффициенты, а не комплексные. Это уменьшает вычислительную сложность таких алгоритмов по сравнению с алгоритмами на основе БПФ.
Большинство алгоритмов адаптивной фильтрации базируется на безусловной минимизации функционалов: мгновенной или среднеквадратичной ошибки между требуемым и выходным сигналами адаптивного фильтра. В тоже время существуют задачи [161-164], решение которых требует использования приемов условной (линейно-ограниченной) оптимизации. Адаптивные алгоритмы с линейными ограничениями применяются, например, в задачах управления адаптивными антенными решетками и в задачах идентификации неизвестного импульсного отклика при ограничениях, накладываемых на значения амплитудно-частотной характеристики (АЧХ) на заданных частотах. Примеры решения последней задачи будут приведены в главе 6. Линейные ограничения применимы ко всем алгоритмам адаптивной фильтрации: от простых - до сложных (рис. 2).
К алгоритмам средней сложности относятся алгоритмы аффинных проекций (Affine Projections, АР), включая одноименные линейно-ограниченные алгоритмы, и их быстрые (вычислительно эффективные, т.е. с малым числом арифметических операций на одну итерацию) версии - FAP-алгоритмы. АР-алгоритмы представляют собой разновидности блочного NLMS-алгоритма. Длина блока, на котором вычисляются ошибки, равна L отсчетам обрабатываемых сигналов и именуется размером проекций. АР-алгоритмы получили популярность благодаря FAP-алгоритму, оценка вычислительной сложности которого - 0(n) + ()(l)-2N + ()(l). т.е. сравнима со сложностью NLMS-алгоритма при N » L .
Известные FAP-алгоритмы были получены для одноканальных адаптивных фильтров с действительными весовыми коэффициентами. В главе 6 эти алгоритмы получены для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах. В этой главе также будет рассмотрено применение в FAP-алгоритмах вычислительных процедур RLS-алгоритмов. Такое применение отсутствует в публикациях.
Вычислительная сложность RLS-алгоритмов - o(n2), а сложность быстрых RLS-алгоритмов - 0(n)>7N арифметических операций. До недавнего времени использование RLS-алгоритмов на практике было затруднено ограниченной производительностью цифровых устройств, применяемых для реализации адаптивных фильтров. В настоящее время возможность реализации сложных RLS-алгоритмов появилась благодаря успехам современной микроэлектроники в области создания высокопроизводительных цифровых сигнальных процессоров (ЦСП), в частности сверхбольших интегральных схем (СБИС) сигнальных контроллеров первой отечественной серии «Мультикор» [165-167], разработанных в Государственном унитарном предприятии г. Москвы Научно-производственном центре «Электронные вычислительно-информационные системы» (ГУП НИЦ «ЭЛВИС»).
На рис. 3. представлена классификация RLS-алгоритмов с точки зрения организации в них вычислительных процессов. Эта классификация применима ко всем рассматриваемым в диссертации алгоритмам, которые на рис. 3 условно выделены жирными линиями. На практике в основном используются адаптивные фильтры с конечной импульсной характеристикой (КИХ). Адаптивные фильтры с бесконечной импульсной характеристикой (БИХ) [144] в диссертационной работе не рассматриваются, так как они характеризуются многоэкстремальной природой минимизируемого в процессе работы функционала (среднеквадратичной ошибки), а значит неоднозначностью решения задачи адаптивной фильтрации.
Адаптивные фильтры могут быть одноканальными, многоканальными с одинаковым и неодинаковым количеством весовых коэффициентов в каналах.
RLS-алгоритмы
Для КИХ-фильтров
Для БИХ-фильтров
Одноканальные
С комплексными весовыми коэффициентами
Многоканальные,
с одинаковым количеством
весовых коэффициентов в
каналах
Многоканальные,
с неодинаковым количеством
весовых коэффициентов в
каналах
С действительными весовыми
коэффициентами
Без регуляризации корреляционной матрицы
С регуляризацией корреляционной матрицы
С бесконечным окном
Со скользящим окном
^т
С бесконечным окном
Со скользящим окном
Для реализации с помощью двух процессоров
Для реализации с помощью | одного процессора
Для реализации с помощью четырех процессоров
Последовательные
Последовательно-параллельные
Параллельные
Рис. 3. Разновидности реализаций адаптивных RLS-алгоритмов
Алгоритмы для многоканальных фильтров с одинаковым количеством весовых коэффициентов в каналах могут строиться на основе матричных вычислительных процедур. Такие алгоритмы будут рассмотрены в главе 3 применительно к адаптивным фильтрам с рекурсивно изменяемым порядком.
В литературных источниках большинство RLS-алгоритмов рассматривается применительно к одноканальным адаптивным фильтрам, рис. 4а. Такой фильтр представляет собой КИХ-фильтр, выходной сигнал которого определяется как y(k) = h"(k-\)xN(k), где h N(k) = [h(k),h(k-\),...,h(k-N + 2),
h(k-N + \)] - вектор весовых коэффициентов, a xN(k) = [x(k),x(k -1),...,
х(к - N + 2),х(к - N +1)] - вектор входных сигналов; х(к) - текущее значение
входного сигнала; к - индекс дискретного времени. В работе векторы будут обозначаться полужирными строчными символами, а матрицы - полужирными прописными. Нижние индексы N в обозначениях векторов и квадратных матриц обозначают число элементов (N и NxN, соответственно), а верхние индексы Т и Н - операции транспонирования и эрмитово сопряжения.
Вычисление весовых коэффициентов осуществляется с помощью адаптивного алгоритма путем минимизации априорной а{к) = d{k)-y{k) или апостериорной е(к) = d(k)-h"(k)xN(k) ошибки моделирования требуемого сигнала d(k). Природа сигнала d(k) определяется задачей, решаемой с помощью
адаптивного фильтра. Понятия «априорный» и «апостериорный» связаны со значением индекса дискретного времени в векторах весовых коэффициентов фильтра (/:-1) и к, соответственно. На практике (см. рис. 4а) в качестве выходного сигнала обычно используется сигнал а(к), что соответствует физической реализации адаптивного фильтра, т.е., на к-й итерации сигнал y(k) = h"(k -\)xN(k) формируется на основе использования весовых коэффициентов, вычисленных на предыдущей итерации.
Многоканальный адаптивный фильтр с неодинаковым количеством весовых коэффициентов в каналах услоино показан на рис. 46.
14
x(k) x(k-\) x(k-2) x(k-N + 2) x(k-N + l)
Адаптивный алгоритм
a(k)
a)
aNAk)
d{k)
хЛк)
x2(k)
xjk)
XM-\('C)
xM(k)
**
f—"
hHNl(k-l)%Nl(k)
-h"(*-l)x„(*)
hHN (k-l)xN (к)
VM-1
VM-1
К. ,(k-\)xN„ ,(k)
A.
KM(k-l)xNM(k)
Адаптивный алгоритм
6)
Рис. 4. Адаптивный (|)ильтр: a) - од
ііі, 6) - многоканальный
15 Здесь hJVo((^) = [hiiX(/:),hi2X(^),...,h^iX(/:),...,h7NM_|>Ж(*)Х„,*(*)Г " вект0Р весовых коэффициентов М -канального адаптивного фильтра состоит из векторов весовых коэффициентов каналов hN,,x() = k,m,xAm,x>-"Ая-2^Аа-ы.х]Т > а вектор сигналов Хл^ (*) = Iх*, (к^К2 (*)» -x!vm (*). -^., (*)>хі„ (*)] состоит из векторов сигналов отдельных каналов Хд, (fc) = Um (fc),xm(& -1),...,
xm(k-Nm+2),xm(k-Nm+\)\ . Суммарное количество весовых коэффициен-
м тов многоканального фильтра определяется как N = 'YNin. Быстрые RLS-
алгоритмы для многоканальных адаптивных фильтров будут построены с использованием перестановочных матриц [168, 169].
В литературных источниках адаптивные алгоритмы в основном представлены для фильтров с действительными весовыми коэффициентами. В сложных RLS-алгоритмах из-за необходимости комплексного сопряжения некоторых переменных переход от действительных к комплексным вычислениям часто неочевиден. Поэтому в диссертационной работе все алгоритмы получены в комплексной форме. Алгоритмы для адаптивных фильтров с действительными весовыми коэффициентами являются частным случаем комплексных алгоритмов при замене всех переменных и вычислений на действительные переменные и вычисления.
Большинство известных RLS-алгоритмов разработано для адаптивной фильтрации стационарных сигналов. Это выражается в вычислении присутствующей в алгоритмах корреляционной матрицы входных сигналов адаптивного фильтра или других переменных, зависящих от этой матрицы, на возрастающем окне отсчетов. При обработке нестационарных сигналов такие алгоритмы обладают низкой эффективностью, поскольку корреляционная матрица, оцениваемая на возрастающем окне, становится плохо обусловленной.
Одним из приемов, позволяющим следить за изменением нестационарных сигналов, является экспоненциальное взвешивание сигналов с помощью пара-
метра Л. Однако допустимое значение Л ограничено количеством весовых коэффициентов как (l-0,4/N)OT)
Приемом, позволяющим повысить эффективность адаптивных RLS-алгоритмов и не зависящим от порядка фильтра, является оценка корреляционной матрицы на скользящем окне, длина которого, выраженная числом отсчетов L, определяется интервалом стационарности обрабатываемых сигналов [129,171-177].
Из-за ограниченного числа отсчетов корреляционная матрица, определяемая на скользящем окне, в ряде случаев может быть плохо обусловленной, а адаптивный фильтр, как следствие, - нестабильным. Решением данной проблемы может служить динамическая регуляризация этой матрицы, рассмотренная в [178] для одноканального RLS-алгоритма с возрастающим окном.
Однако скользящее окно, возрастающее окно и регуляризация, или одновременно скользящее окно и регуляризация в алгоритмах адаптивной фильтрации практически не используются, так как повышают вычислительную сложность RLS-алгоритмов примерно в два или четыре раза по сравнению с алгоритмами с возрастающим окном без регуляризации.
В то же время, производительность многих современных ЦСП, например, СБИС сигнальных контроллеров отечественной серии «Мультикор», уже позволяет реализовать сложные алгоритмы ЦОС. Наличие этой элементной базы послужило одним из факторов целесообразности разработки алгоритмов адаптивной фильтрации нестационарных сигналов - математических процедур вычисления весовых коэффициентов адаптивного фильтра.
Большинство алгоритмов, представленных в диссертации, разработано для применения в многоканальных адаптивных фильтрах с неодинаковым количеством весовых коэффициентов в каналах. Такие фильтры, например, могут использоваться при реализации нелинейных полиномиальных фильтров, ком-
17 пенсаторов множественных эхо-сигналов, выравнивателей каналов связи и ряда других устройств.
Разработанные в рамках диссертационной работы RLS-алгоритмы со скользящим окном, с возрастающим окном и регуляризацией, со скользящим окном и регуляризацией получены в виде как последовательных, так и параллельных вычислительных процедур, ориентированных на реализацию с помощью двух или четырех ЦСП независимо от числа каналов адаптивного фильтра и количества весовых коэффициентов в каналах. Сигнальные контроллеры, содержащие несколько ЦСП в одной СБИС, в настоящее время проектируются в ГУП НПЦ «ЭЛВИС», что также определило актуальность разработки параллельных алгоритмов адаптивной фильтрации. Рассматриваемые в диссертации RLS-алгоритмы образуют множество последовательных, параллельных и последовательно-параллельных алгоритмов (рис. 3), предназначенных для реализации с помощью одного, двух или четырех процессоров. Параллельные алгоритмы разработаны на основе схожего с [179] метода.
Классификация основных разновидностей RLS-алгоритмов по наименованиям, известным в литературе в основном для случая одноканальной адаптивной фильтрации стационарных сигналов, приведена на рис. 5.
В основе RLS-алгоритмов с квадратичной вычислительной сложностью находится лемма об обращении матриц [156], а также прямое [180-183] и обратное [184, 185] QR-разложение матрицы входных сигналов с операциями извлечения квадратного корня и без таких операций [183, 188], с применением вращений Гивенса и преобразования Хаусхолдера [186, 187].
Быстрые RLS-алгоритмы с линейной сложностью разделяются на два класса: рекурсивные во времени и с рекурсивно изменяемым порядком.
В основе быстрых рекурсивных во времени алгоритмов находится лемма об обращении клеточных матриц [156]. Основными разновидностями таких алгоритмов являются быстрый алгоритм Калмана (Fast Kalman, FK), Fast Transversal Filter (FTF) и Fast a Posteriori Error Sequential Technique (FAEST) [146], стабилизированный l'AEST-алгоритм [170], а также быстрый алгоритм на
На основе леммы обращения матрицы
На основе леммы
обращения клеточных
матриц
Лестничные
Быстрый алгоритм Калмана
FTF-алгоритм
FAEST-алгоритм
ТТГ ~Zk
На основе прямого QR-
разложения с
использованием
вращений Гивенса
На основе обратного QR-
разложения с
использованием вращений
Гивенса
На основе обратного QR-
разложения с
использованием прсобразо-
ваний Хаусхолдсра
На основе априорных и
апостериорных
ошибок, без обратных
связей
На основе априорных и
апостериорных
ошибок, с обратными
связями
На основе априорных
ошибок, без обратных
связей
С операциями извлечения квадратного корня
Стабилизированный FAEST-алгоритм
На основе априорных
ошибок, с обратными
связями
На основе
апостериорных ошибок,
без обратных связей
Без операций извлечения квадратного корня
п: л
Быстрый RLS-алгоритм
на основе обратного
QR-разложения
Стабилизированный
быстрый RLS-алгоритм
на основе обратного
QR-разложения
На основе
апостериорных ошибок,
с обратными связями
С операциями извлечения квадратною корня
J-
Нормализованный на
основе апостериорных
ошибок, с обратными
связями
Без операций извлечения квадратного корпя
На основе QR-разложения, априорных ошибок, с обратными
Рис. 5. Разновидности адаптивных RLS-алгоритмов
На основе QR-разложения, апостериорных ошибок, с обратными связями
11а основе QR-разложения,
апо1"1ср|1орш>1\ ошибок, с
:>браіііі>і\пі сняіями. в просі
состоянии
19 основе обратного QR-разложения [189], который может быть реализован с операциями извлечения квадратного корня и без таких операций. В последнем случае к такому алгоритму применим метод стабилизации [170].
Особенностью быстрых лестничных фильтров является отсутствие в них вычисления весовых коэффициентов в явном виде. Это обусловлено тем, что вместо весовых коэффициентов используются другие переменные (коэффициенты отражения), являющиеся функциями от весовых коэффициентов. Как следствие, в лестничных алгоритмах выходной сигнал адаптивного фильтра у(к), требующий наличия вектора весовых коэффициентов h^ (А: — 1), не вычисляется. Основные разновидности лестничных алгоритмов приведены на рис. 5. Описания этих алгоритмов для случая фильтрации стационарных сигналов приводятся в [130,133,138, 143,146, 147,190-202].
В настоящей диссертации рассматривается получение вычислительных процедур RLS-алгоритмов, аналогичных представленным на рис. 5, в соответствие с допустимыми структурами (рис. 3): одноканальных, многоканальных с одинаковым и неодинаковым количеством комплексных весовых коэффициентов в каналах, со скользящим окном, с возрастающим окном и регуляризацией, со скользящим окном и регуляризацией одновременно, для реализации с помощью последовательных и параллельных вычислений.
Актуальность. Таким образом, отсутствие в литературных источниках описания математических процедур алгоритмов адаптивной фильтрации нестационарных сигналов, а также наличие современных высокопроизводительных ЦСП, в частности СБИС сигнальных контролеров отечественной серии «Муль-тикор», позволяющих реализовывать сложные RLS-алгоритмы, обусловили актуальность разработки математических моделей таких алгоритмов. Решению этой проблемы, а также связанных с нею задач, посвящена настоящая диссертационная работа.
Цель и задачи работы. Целью диссертационной работы является решение научной проблемы создания алгоритмических основ адаптивной фильтрации нестационарных сигналов, а также исследование эффективности порученных
20 RLS-алгоритмов при обработке сигналов в адаптивных антенных решетках, при построении вычислительных процедур FAP-алгоритмов, в нелинейной адаптивной фильтрации, в задачах подавления эхо-сигналов и при идентификации неоднородностей в проводных каналах связи.
Цель достигается путем решения следующих задач.
1. Для многоканальных адаптивных фильтров с неодинаковым количест
вом комплексных весовых коэффициентов в каналах со скользящим окном, с
возрастающим окном и регуляризацией, со скользящим окном и регуляризаци
ей:
получение математических процедур последовательных RLS-алгоритмов на основе леммы об обращении матрицы, а также на основе прямого и обратного QR-разложения с операциями извлечения квадратного корня и без таких операций;
получение математических процедур последовательных быстрых RLS-алгоритмов на основе леммы об обращении клеточных матриц, а также обратного QR-разложения с операциями извлечения квадратного корня и без таких операций;
получение математических процедур последовательных линейно-ограниченных RLS-алгоритмов.
Для одноканальных и многоканальных (с одинаковым количеством комплексных весовых коэффициентов в каналах) адаптивных фильтров со скользящим окном, с возрастающим окном и регуляризацией, со скользящим окном и регуляризацией получение математических процедур последовательных быстрых лестничных RLS-алгоритмов.
Получение математических процедур параллельных версий перечисленных выше разновидностей RLS-алгоритмов, ориентированных на реализацию с помощью двух или четырех ЦСП.
Для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах получение математических процедур FAP-алгоритмов и линейно-ограниченных версий таких алго-
21 ритмов.
Получение условий инициализации, обеспечивающих математическую эквивалентность RLS-алгоритмов друг другу в пределах классов, характеризуемых способом оценки корреляционной матрицы сигналов адаптивного фильтра: на скользящем окне, на возрастающем окне с регуляризацией, на скользящем окне с регуляризацией.
Исследование эффективности применения скользящего окна, возрастающего окна и регуляризации, скользящего окна и регуляризации в RLS-алгоритмах при решении задач идентификации с помощью многоканальных адаптивных фильтров, обрабатывающих нестационарные сигналы.
Исследование эффективности использования многоканальных адаптивных фильтров с неодинаковым количеством весовых коэффициентов в каналах для реализации полных и усеченных нелинейных полиномиальных фильтров, обрабатывающих нестационарные сигналы.
Получение математической процедуры адаптивного алгоритма идентификации неоднородностей в проводных каналах связи.
Создание тестовой среды для проверки работоспособности и исследования эффективности алгоритмов адаптивной фильтрации при решении прикладных задач.
10. Создание библиотеки алгоритмов и программ на основе полученных
математических процедур алгоритмов адаптивной фильтрации.
Научная новизна
Разработано семейство последовательных RLS-алгоритмов с линейной и квадратичной вычислительной сложностью, включая алгоритмы с линейными ограничениями, для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах.
Разработано семейство параллельных RLS-алгоритмов с линейной и квадратичной вычислительной сложностью, включая алгоритмы с линейными ограничениями, для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах.
Разработано семейство последовательных быстрых лестничных RLS-алгоритмов для одноканальных и многоканальных адаптивных фильтров с одинаковым количеством комплексных весовых коэффициентов в каналах.
Разработано семейство параллельных лестничных RLS-алгоритмов для одноканальных и многоканальных адаптивных фильтров с одинаковым количеством комплексных весовых коэффициентов в каналах.
Разработано семейство FAP-алгоритмов, включая алгоритмы с линейными ограничениями, для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах.
Получены условия инициализации, обеспечивающие математическую эквивалентность RLS-алгоритмов друг другу в пределах классов, характеризуемых способом оценки корреляционной матрицы сигналов адаптивного фильтра.
Разработан адаптивный алгоритм идентификации неоднородностей в проводных каналах связи, использующий непрерывные сигналы.
Практическая значимость результатов работы заключается в
разработке математических процедур около 400 разновидностей RLS- и FAP-алгоритмов, которые позволяют решать широкий круг задач адаптивной фильтрации сигналов;
разработке на языке программирования MATLAB библиотеки моделей алгоритмов адаптивной фильтрации, которые могут найти применение при исследовании поведения адаптивных фильтров в радиотехнических и телекоммуникационных системах различного назначения, могут быть использованы в учебных курсах и в качестве прототипов при реализации алгоритмов на различных вычислительных платформах;
разработке библиотеки адаптивной фильтрации для СБИС сигнальных контроллеров отечественной серии «Мультикор», позволяющей снизить время проектирования радиоэлектронных изделий за счет использования готового программного обеспечения и демонстрирующей вычислительные возможности этих контроллеров;
- разработке адаптивного метода идентификации неоднородностей в проводных линиях связи, нашедшего применение в измерительной технике и позволяющего получать одинаковое разрешение по дальности при измерениях как в коротких, так и в длинных линиях.
Достоверность материалов диссертационной работы подтверждена результатами моделирования, демонстрирующими математическую эквивалентность полученных алгоритмов адаптивной фильтрации друг другу в пределах классов, характеризуемых способом оценки корреляционной матрицы сигналов адаптивного фильтра, а также реализацией таких алгоритмов в виде функций для СБИС сигнальных контроллеров серии «Мультикор». Достоверность разработанного адаптивного алгоритма идентификации неоднородностей в проводных каналах связи демонстрируется его использованием в серийно выпускаемых измерительных приборах.
Личный вклад автора. Все приведенные в диссертации результаты получены автором лично. Это подтверждается тем, что 87 работ из 91 работы из списка публикаций по теме диссертации выполнены без соавторов.
Внедрение результатов работы. Результаты диссертационной работы в виде математических моделей алгоритмов и программного обеспечения внедрены в прикладной библиотеке алгоритмов адаптивной фильтрации для СБИС сигнальных контроллеров серии «Мультикор» ГУП НПЦ «ЭЛВИС» (г. Москва, Зеленоград); в виде библиотеки адаптивной фильтрации для СБИС сигнальных контроллеров серии «Мультикор» внедрены в Научно-конструкторском бюро вычислительных систем (г. Таганрог, Ростовская обл.); в виде библиотеки алгоритмов на языке программирования MATLAB внедрены в Научно-производственном предприятии Калужский приборостроительный завод «Тайфун» (г. Калуга) и в учебных курсах Самарской государственной академии путей сообщения (г. Самара); в виде адаптивного алгоритма идентификации неоднородностей проводных каналов связи внедрены в серийно выпускаемых с 2003 года анализаторах систем передачи и кабелей связи AnCom А-7 предприятия Аналитик-ТС (г. Москва), что подтверждено соответствующими актами.
24 Положения, выносимые на защиту
Последовательные и параллельные RLS-алгоритмы на основе леммы об обращении матрицы, а также на основе прямого и обратного QR-разложения с операциями извлечения квадратного корня и без таких операций для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах со скользящим окном, с возрастающим окном и регуляризацией, со скользящим окном и регуляризацией.
Последовательные и параллельные быстрые RLS-алгоритмы на основе леммы об обращении клеточных матриц, а также обратного QR-разложения с операциями извлечения квадратного корня и без таких операций для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах со скользящим окном, с возрастающим окном и регуляризацией, со скользящим окном и регуляризацией.
Последовательные и параллельные быстрые лестничные RLS-алгоритмы для одноканальных и многоканальных (с одинаковым количеством комплексных весовых коэффициентов в каналах) адаптивных фильтров со скользящим окном, с возрастающим окном и регуляризацией, со скользящим окном и регуляризацией.
Последовательные и параллельные линейно-ограниченные RLS-алгоритмы для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах со скользящим окном, с возрастающим окном и регуляризацией, со скользящим окном и регуляризацией.
FAP-алгоритмы, включая алгоритмы с линейными ограничениями, для многоканальных адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах.
Метод инициализации, обеспечивающий математическую эквивалентность RLS-алгоритмов друг другу в пределах классов, характеризуемых способом оценки корреляционной матрицы сигналов адаптивного фильтра.
Адаптивный алгоритм идентификации пеоднородностей в проводных
25 каналах связи, использующий непрерывные сигналы.
Апробация работы. Основные результаты работы были представлены и обсуждены на 31 конференции: 3-rd International Conference on Antennas, Radio-communication Systems & Means (ICARSM-97) (г. Воронеж, 1997), 5-й Международной конференции «Цифровая обработка сигналов и ее применения (DSPA-2003)» (г. Москва, 2003), 6-й Международной конференции «Цифровая обработка сигналов и ее применения (DSPA-2004)» (г. Москва, 2004), 10-й Международной конференции «Радиолокация, навигация, связь (RLNC-2004)» (г. Воронеж, 2004), 59-й научной сессии, посвященной Дню Радио (г. Москва, 2004), 2-й Всероссийской научной конференции «Проектирование инженерных и научных приложений в среде MATLAB» (г. Москва, 2004), 2-nd IEEE International Conference on Circuits and Systems for Communications (ICCSC-2004) (г. Москва, 2004), 4-th International Scientific and Practical Conference «Internet-Science-Education-2004 (ISE-2004)» (г. Винница, Украина, 2004), 2-nd International Conference on Information Systems and Technology (IST-2004) (г. Минск, Беларусь, 2004), 13-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2004), 7-й Международной конференции «Цифровая обработка сигналов и ее применения (DSPA-2005)» (г. Москва, 2005), 11-й Международной конференции «Радиолокация, навигация, связь (RLNC-2005)» (г. Воронеж, 2005), 6-th International Conference on Prospective Technologies in the Mass Media (г. Владимир, 2005), Всероссийской ежегодной научно-технической конференции «Наука, производство, технологии, экология» (г. Киров, 2005), 5-th World Scientific and Engineering Academy and Society (WSEAS) International Conference on Information Science, Communications and Applications (ISCA-2005) (г. Канкун, Мексика, 2005), 60-й научной сессии, посвященной Дню Радио (г. Москва, 2005), 8-th International Conference on Pattern Recognition and Information Processing (PRIP-2005) (г. Минск, Беларусь, 2005), 6-й Международной научно-практической конференции «Современные информационные и электронные технологии» (г. Одесса. Украина, 2005), St. Petersburg IHKH Chapters Interna-
26 tional Conference «Radio - That Connects Time. 110 Years of Radio Invention» (г. Санкт-Петербург, 2005), IEEE 7-th Emerging Technologies Workshop: «Circuits and Systems for 4G Mobile Wireless Communications» (г. Санкт-Петербург, 2005), 2-nd International Association of Science and Technology for Development (IASTED) International Multi-Conference on Automation, Control and Information Technology (г. Новосибирск, 2005), 2-й Всероссийской научно-технической конференции «Методы и средства обработки информации (МСО-2005)» (г. Москва, 2005), Всероссийской научно-технической конференции «Проблемы разработки перспективных микроэлектронных систем (МЭС-2005)» (г. Москва, 2005), 13-й Международной конференции «Информационные средства и технологии» (г. Москва, 2006), 5-й Международной научно-технической конференции «Электроника и информатика - 2005» (г. Москва, 2005), 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2005), 1-й Международной научно-технической конференции «Современные проблемы оптимизации в инженерных приложениях (IWOPE-2005)» (г. Ярославль, 2005), 8-й Международной конференции «Цифровая обработка сигналов и ее применения (DSPA-2006)» (г. Москва, 2006), 12-й Международной конференции «Радиолокация, навигация, связь (RLNC-2006)» (г. Воронеж, 2006), Всероссийской ежегодной научно-технической конференции «Наука, производство, технологии, экология» (г. Киров, 2006), 61-й научной сессии, посвященной Дню Радио (г. Москва, 2006).
Публикации. Результаты диссертационной работы опубликованы в 91 работе. Из них 33 статьи в журналах перечня ВАК: «Радиотехника», «Радиотехника и электроника», «Вопросы радиоэлектроники. Общетехническая серия», «Электросвязь», «Телекоммуникации», «Информационные технологии», «Измерительная техника», «Цифровая обработка сигналов», «Электроника: Наука, Технологии, Бизнес», «Оборонный комплекс - научно-техническому прогрессу России», «Известия высших учебных заведений. Радиоэлектроника», «Известия высших учебных заведений. Электроника», «Вестник МГТУ им. Н.Э. Баумана.
27 Серия «Приборостроение», «Вестник Московского государственного авиационного института (технического университета)», «Научный вестник Московского государственного технического университета гражданской авиации. Серия «Радиофизика и радиотехника», «Вестник Рязанской государственной радиотехнической академии», «Труды учебных заведений связи»; 4 статьи в других рецензируемых журналах, не входящих в перечень ВАК: «Успехи современной радиоэлектроники», «Radioengineering: Proceedings of Czech and Slovak Technical Universities and URSI Committers», «Signal Processing» (европейского научного издательства Elsevier), 50 статей в трудах перечисленных выше российских и международных (зарубежных) конференций и 4 работы в отчетах о НИР. На английском языке опубликовано 15 из перечисленных статей: 3 в журналах и 12 в трудах конференций.
Структура и объем диссертации. Диссертационная работа состоит из введения, 6 глав, заключения и приложения, содержит 342 страницы текста, включая 57 рисунков, 69 таблиц, 34 страницы списка используемой литературы из 324 наименований и 5 актов о внедрении ее результатов.
Помимо введения, диссертация содержит 6 глав, заключение и приложения.
В главе 1 рассматриваются вопросы построения многоканальных RLS-алгоритмов с квадратичной вычислительной сложностью для адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах, предназначенных для фильтрации нестационарных сигналов.
В главе 2 рассматриваются многоканальные быстрые RLS-алгоритмы с линейной вычислительной сложностью для адаптивных фильтров с неодинаковым количеством комплексных весовых коэффициентов в каналах, предназначенных для фильтрации нестационарных сигналов.
В главе 3 рассматриваются быстрые лестничные RLS-алгоритмы с линейной вычислительной сложностью для одноканальных и многоканальных адаптивных фильтров с одинаковым количеством комплексных весовых коэффициентов в каналах, предназначенных для фильтрации нестационарных сигналов.
В главе 4 рассматриваются линейно-ограниченные версии RLS-алгоритмов адаптивной фильтрации нестационарных сигналов.
В главе 5 рассматриваются параллельные версии алгоритмов, представленных в главах 1-4, которые могут быть реализованы с помощью двух или четырех процессоров.
Алгоритм на основе прямого QR-разложения
Вектор весовых коэффициентов адаптивного фильтра, эквивалентный (1.3), может быть также получен с помощью других разновидностей RLS-алгоритмов. Это алгоритмы на основе QR-разложения (факторизации Холецко-го) матрицы входных сигналов адаптивного фильтра. Известны два вида такого разложения: прямое [147,183] и обратное [184, 185].где Qkk(k) - ортонормированная матрица; RN (к) - верхняя треугольная матрица или QR-разложение матрицы XkN(k); 0(k_N)N - нулевая прямоугольная матрица. С помощью RA (к) корреляционная матрица выражается как
Здесь и далее размер прямоугольных (нетранспонированных) матриц будетобозначаться двумя нижними индексами. Например, нижний индекс kN обозначает прямоугольную матрицу с числом элементов, равным kxN. С помощью (1.8) уравнение (1.7) выражается как Уравнение (1.10) позволяет определить вектор весовых коэффициентов адаптивного фильтра какМатрицу RNx(k) можно получить с помощью вращений Гивенса [180—182], а выражение (1.11) - с помощью обратных подстановок. Такие подстановки являются источником дополнительных вычислительных затрат. Однако в большинстве задач адаптивной фильтрации требуется вычислять лишь сигнал ошибки aNl{k), а вычисление вектора hNx(k) носит лишь промежуточный характер.В [183] был представлен алгоритм адаптивной фильтрации, который позволяет получать значения aNl(k) без непосредственного вычисления hN (к).Этот алгоритм был применен для одноканального адаптивного фильтра с действительными весовыми коэффициентами. Аналогичный алгоритм (табл. 1.2) получен в диссертационной работе для многоканального адаптивного фильтра. Источником операций извлечения квадратного корня является рекуррентная процедура вычисления матрицы RN (к), осуществляемая на основе соотношения:Здесь I - единичная матрица. Переход от RN% (к-\) к R (к) осуществляется путем исключения вектора %N(k) в уравнении (1.12). Это исключение выполняют, исходя из условий
Уравнения (1.14) и (1.15) позволяют определить элементы матрицы вращений Гивенса как (1.2.2) - (1.2.4), что и является источником N операций извлечения квадратного корня. Аналогично N операций извлечения квадратного корня возникает при исключении данных из скользящего окна (рис. 1.16). В этом случае требуется использовать матрицу гиперболических вращений Гивенса, определяемую как
Оценка вычислительной сложности алгоритма (табл. 1.2) - 0[N2) арифметических операций. Она равна 57V2 + 20N операциям умножения, 2N2 +6N операциям сложения, 2N +1 операциям деления и 2N операциям извлечения квадратного корня. Операции извлечения квадратного корня могут быть выполнены с помощью ряда известных функциональных преобразований, например, с помощью вычислительной процедуры CORDIC [203].
В ряде задач, например, в задачах линейно-ограниченной адаптивной фильтрации (глава 4), в процессе работы адаптивного фильтра необходимо определять значения его весовых коэффициентов. Во избежание обратных подстановок, требуемых для вычисления весовых коэффициентов в алгоритмах на основе прямого QR-разложения, в [184] был предложен способ, позволяющий непосредственно определять обратную матрицу R x(&). Этот способ основанна обратном QR-разложении. Для случая одноканального адаптивного фильтра с действительными весовыми коэффициентами и возрастающим окном алгоритм на основе этого метода представлен в [185]. Многоканальный вариант такого фильтра с комплексными весовыми коэффициентами и возрастающим окном приведен в [259].
В настоящем разделе рассматриваются вопросы получения аналогичного алгоритма для многоканального адаптивного фильтра с комплексными весовыми коэффициентами и со скользящим окном. Такой алгоритм был представлен в работах [245, 249, 256].
Для получения матрицы R Nly(k) на каждой итерации RLS-алгоритма соскользящим окном при поступлении новых данных %х(к) выполняются вычисления: торов.RLS-алгоритм (табл. 1.3) содержит 2N операций извлечения квадратного корня, которые обусловлены вычислением переменных bN (к) и bN (к) вуравнениях (1.3.3) и (1.3.10) в течение N шагов i = l,...,N на каждой к-й итерации алгоритма адаптивной фильтрации. Кроме того, он содержит 5,5N2 +16N операций умножения, 3N2 +6N операций сложения и 2N операций деления. Следовательно, оценка вычислительной сложности RLS-алгоритма (табл. 1.3) равна 0[N2j арифметическим операциям.
Рассматриваемый далее RLS-алгоритм [244, 250] также базируется на обратном QR-разложении. Особенностью этого алгоритма является наличие в нем лишь двух операций извлечения квадратного корня на одну итерацию. В данном алгоритме для выполнения преобразований, аналогичных (1.17) и (1.21), вместо вращений Гивенса используется преобразование Хаусхолдера [186, 187]. Подобно матрице вращений Гивенса, ортогональная матрица Хаусхолдера позволяет определить матрицу R N\x(k) для уравнения расчета весовых коэффициентов адаптивного фильтра (1.11).
В случае скользящего окна пара преобразований Хаусхолдера определяется какУравнение (1.24) позволяет для поступающих новых данных ул (к) выполнить преобразование:ортогональная матрица.
Подобное преобразование выполняется с помощью (1.25) для данных 1N{k-L), обусловленных конечной длиной скользящего окна:
Параметры bN%u{k), uNiXv(k) и bN (к), uN (к) позволяют определить векторы коэффициентов Калмана gN (к) и gN (к), с помощью которых затем в два приема определяется вектор весовых коэффициентов адаптивного фильтра hN(k) = hN (к). Вычислительная процедура полученного RLS алгоритма со скользящим окном на основе обратного QR-разложения с использование преобразования Хаусхолдера представлена в табл. 1.4.
Оценка вычислительной сложности RLS-алгоритма (табл. 1.4) - 0\N2) арифметических операций. Она равна IN2 +WN операциям умножения, 6N2 +6N операциям сложения, двум операциям извлечения квадратного корня и двум операциям деления.
Таким образом, вычислительная сложность алгоритма (табл. 1.4) в части операций умножения и сложения несколько больше, чем у алгоритмов, представленных в табл. 1.2 и табл. 1.3. Однако в алгоритме (табл. 1.4) операций извлечения квадратного корня и операций деления в N раз меньше, чем в алгоритмах (табл. 1.2 и табл. 1.3).
В алгоритмах (табл. 1.2 и табл. 1.3) присутствуют операции извлечения квадратного корня. Несмотря на то, что в настоящее время существуют различные эффективные методы реализации такого функционального преобразования [203-206], эта реализация требует дополнительных вычислительных затрат. Исключить операции извлечения квадратного корня удается путем масштабирования ряда переменных, участвующих в вычислениях [183,187].
Полученные с помощью масштабирования варианты алгоритмов (табл. 1.2 и табл. 1.3) для многоканальных адаптивных фильтров с возрастающим окном приведены в работе [259]. В настоящей работе рассматриваются аналогичные RLS-алгоритмы для многоканальных адаптивных фильтров со скользящим окном. Полученные алгоритмы на основе обратного QR-разложения были также представлены в работах [251, 254].
Чтобы избавиться от операций извлечения квадратного корня в алгоритме на основе прямого QR-разложения (табл. 1.2), матрицы и векторы в уравнении (1.12) следует промасштабировать как
Быстрые алгоритмы на основе обратного QR-разложения
Быстрые RLS-алгоритмы адаптивной фильтрации могут быть также построены на основе QR-разложения матрицы входных сигналов адаптивного фильтра. В [147] показано, что обратное QR-разложение расширенной матрицы сигналов одноканального адаптивного фильтра с возрастающим окном Аналогичные соотношения существуют и для матриц на основе векторов вание:x N(k),x(k - N)\ и [.v(A ),x v(A )J . Используя нреобразоь для матрицы R +u (А:) и аналогичные преобразования для матриц на основе векторов \xTN(k),x(k- N)\ и [JC(),X (/:)J , устанавливаются следующие соот ношения: YN+2{k) - матрица вращений Гивенса. Из данных соотношений следует, что UJV,X ( )= u!v,x Это позволяет определить вектор коэффициентов Калмана как Поскольку вектор и(/ (к) является функцией параметров uNx (к-\), способом. Следуя указанным преобразованиям, в [207, 208] были получены быстрые RLS-алгоритмы с возрастающим окном на основе обратного QR-разложения. Недостатком таких алгоритмов является наличие в них операций извлечения квадратного корня, число которых пропорционально N. Таким же недостатком обладают и быстрые RLS-алгоритмы на основе прямого QR-разложения [209, 210]. В то же время одноканальный вариант быстрого RLS-алгоритма без операций квадратного корня был представлен в [189]. Многоканальный вариант этого алгоритма для адаптивного фильтра с возрастающим окном, требующий всего 2М операций извлечения квадратного корня на одну итерацию, представлен в [259], а многоканальный алгоритм со скользящим окном - в [256]. Алгоритм [256] также представлен в табл. 2.4. В основе получения этого алгоритма находятся приемы, аналогичные (2.64) -(2.68), а также некоторые из приемов, рассмотренных в разделах 2.1 - 2.3. Вычислительная сложность алгоритма (табл. 2.5) равна 14MJV + 47V операциям умножения, 10MN + 4N операциям сложения и AM операциям деления, т.е. оценивается как 0(N). Операции квадратного корня отсутствуют. Сравнивая (2.60) - (2.63) и переменные алгоритма (табл. 2.5): (2.5.2), (2.5.12), (2.5.19) и (2.5.29), можно заметить, что это отношения правдоподобия. Таким образом, быстрый RLS-алгоритм на основе обратного QR-разложения без операций извлечения квадратного корня является аналогом FAEST-алгоритма, в котором вместо априорных векторов коэффициентов Калмана t вычисляются апостериорные векторы g, связанные соотношениями (2.31) (2.34). Используя эти соотношения можно построить стабилизированную версию алгоритма (табл. 2.5). Такой 101 Таблица 2.11. Многоканальный регуляризированный быстрый RLS-алгоритм со скользящим окном на основе обратного QR-разложения с использованием вращений Гивенса без операций извлечения квадратного корня Многоканальный регуляризированный быстрый стабилизированный RLS-алгоритм со скользящим окном на основе обратного QR-разложения с использованием вращений Гивенса без операций извлечения квадратного корня ез учета разреженной структуры векторов сигналов регуляризации р(ц1)(к) вычислительная сложность алгоритмов настоящего раздела совпадает со сложностью алгоритмов, рассмотренных в разделах 2.3 и 2.4. 2.6. Одновременное использование скользящего окна и регуляризации в быстрых RLS-алгоритмах При одновременном использовании скользящего окна и регуляризации в быстрых RLS-алгоритмах корреляционная матрица входных сигналов многоканального адаптивного фильгра определяется выражением (1.40). Это, подобно RLS-алгоритмам с квадратичной вычислительной сложностью, обуславливает необходимость четырехкратного выполнения однотипных операций и в алгоритмах с линейной вычислительной сложностью. В части определения векторов коэффициентов Калмана эти операции определяются сигналами (2.47), (2.48), (2.69) и (2.72) Следствием применения регуляризации корреляционной матрицы сигналов адаптивного фильтра, оцениваемой на скользящем окне, является увеличение примерно в два раза вычислительной сложности регуляризированных алгоритмов со скользящим окном по сравнению с такими нерегуляризированными алгоритмами. Регуляризированная версия FK-алгоритма со скользящим окном (табл. 2.1) приведена в табл. 2.13. 113 Регуляризированные версии алгоритмов (табл. 2.2 - табл. 2.6) были получены аналогичным образом. В данной работе они не приводятся из-за объема таблиц. Модификации вычислительных частей этих алгоритмов аналогичны модификациям, отмеченным в разделе 1.6. Вычислительная сложность FK-алгоритма (табл. 2.13), подобно одноименному алгоритму без регуляризации (табл. 2.1), оценивается как 0(N) арифметических операций. Она в два раза больше вычислительной сложности алгоритма (табл. 2.1). Вычислительная сложность регуляризированных версий других алгоритмов из разделов 2.3 и 2.4 также в два раза больше вычислительной сложности соответствующих алгоритмов (табл. 2.2 - табл. 2.6), включая FAEST-алгоритм. 2.7. Сравнительные характеристики алгоритмов Сравнительные оценки вычислительной сложности быстрых RLS-алгоритмов со скользящим окном, рассмотренных в разделах 2.3 и 2.4, приведены в табл. 2.14. Аналогичной вычислительной сложностью обладают одноименные регуляризированные алгоритмы с возрастающим окном. Сложность регуляризированных алгоритмов со скользящим окном в два раза больше сложности алгоритмов, перечисленных в табл. 2.14. Здесь «Ст.» означает «стабилизированный», «без кв. кор.» - без квадратного корня. На рис. 2.1 приведены результаты сравнительного моделирования алгоритмов, перечисленных в табл. 2.14, с точки зрения их численных свойств. Номера линий на этом рисунке соответствуют номерам строк табл. 2.14. Рассматривалась задача, аналогичная задаче раздела 1.7. Из рис. 2.16 следует, что в данном эксперименте различие между достижимым значение параметра ERLE не превышает 8... 10 дБ. Также видно, что поведение быстрых RLS-алгоритмов на основе обратного QR-разложения близко к поведению стабилизированного FAEST-алгоритма, что свидетельствует о хороших численных свойствах таких алгоритмов. В случае применения рассмотренных алгоритмов в одноканальных адаптивных фильтрах (М =\) необходимость в использовании перестановочных 1. Для случая оценки корреляционной матрицы адаптивного фильтра на скользящем окне получено 7 разновидностей RLS-алгоритмов адаптивной фильтрации с линейной вычислительной сложностью. Это FK- алгоритм, FTF-алгоритм, FAEST-алгоритм и стабилизированный FAEST-алгоритм на основе леммы об обращении клеточных матриц, а также быстрые RLS-алгоритмы на основе обратного QR-разложения с использованием вращений Гивенса. Вычислительные процедуры алгоритмов на основе QR-разложения получены в форме, содержащей операции извлечения квадратного корня, и в форме, не содержащей такие операции. Кроме того получена стабилизированная версия алгоритма на основе обратного QR-разложения без операции извлечения квадратного корня. 2. Получено 7 разновидностей быстрых RLS-алгоритмов, аналогичных пункту 1, при оценке корреляционной матрицы на возрастающем окне и использовании динамической регуляризации. 3. Получено 7 разновидностей быстрых RLS-алгоритмов, аналогичных пункту 1, при оценке корреляционной матрицы на скользящем окне и использовании динамической регуляризации. 4. Сравнительные оценки вычислительной сложности быстрых RLS-алгоритмов, рассмотренных в разделах 2.3 и 2.4, приведены в табл. 2.14. Сложность быстрых RLS-алгоритмов в N раз меньше сложности алгоритмов, рассмотренных в главе 1. Это позволяет использовать такие алгоритмы в задачах, где требуются адаптивные фильтры с большим количеством весовых коэффициентов. 5. Быстрые RLS-алгоритмы, рассмотренные настоящей главе, могут быть использованы в многоканальных и одноканальных фильтрах для решения разнообразных задач адаптивной фильтрации стационарных и нестационарных сигналов.
Многоканальные лестничные RLS-алгоритмы с одинаковым количеством весовых коэффициентов в каналах
Подобно быстрым RLS-алгоритмам, рассмотренным в главе 2, лестничные RLS-алгоритмы также могут быть многоканальными. Один из способов построения многоканальных лестничных алгоритмов с неодинаковым количеством весовых коэффициентов представлен в [197]. Недостатком такого способа, помимо вычислительной сложности, является необходимость перестановки каналов в порядке возрастания или убывания количества весовых коэффициентов в каналах.
В тоже время, в случае адаптивных фильтров с одинаковым количеством весовых коэффициентов в каналах, лестничные алгоритмы могут быть построены с использованием выражений, сходных по структуре с выражениями для одноканальных алгоритмов. В таких алгоритмах часть переменных заменяется на матрицы и векторы. Из определения ошибки а(к) в многоканальном фильтре следует, что ее энергия содержит не только энергии ошибок отдельных каналов, но и взаимные коэффициенты корреляций этих ошибок. Задав эти переменные в виде матрицы, а также следуя основным приемам получения RLS- и быстрых RLS-алгоритмов (см. главы 1 и 2), можно получить матричные варианты лестничных алгоритмов для фильтров с одинаковым количеством весовых коэффициентов в каналах. При этом ошибки линейного предсказания представляются векторами с числом элементов М , а энергии этих ошибок - матрицами с числом элементов М хМ . Аналогичные приемы могут быть использованы и для получения многоканальных алгоритмов, рассмотренных в главе 2. Приемы получения многоканальных лестничных алгоритмов совпадают с приемами, рассмотренными в разделе 3.2.
В многоканальных фильтрах с одинаковым количеством весовых коэффициентов в каналах коэффициенты отражения становятся матрицами Г-Цп)(к),
Г м и(к) и вектором у м(к). Перестановочные матрицы для вычисления матрици вектора коэффициентов отражения при этом не требуются. С помощью данного способа получено шесть разновидностей многоканальных лестничных алгоритмов: на основе априорных и апостериорных ошибок, на основе только априорных ошибок, на основе апостериорных ошибок, на основе априорных и апостериорных ошибок с обратными связями, на основе априорных ошибок с обратными связями, и на основе QR-разложения без операций извлечения квадратного корня.
Другие разновидности лестничных алгоритмов (см. раздел 3.2) таким способом получить нельзя, так как ряд скалярных переменных, используемых в одноканальных алгоритмах, в многоканальных алгоритмах становятся некоммутируемыми матрицами, в результате чего некоторые произведения таких матриц невозможно заменить другими переменными. Многоканальный алгоритм, одноименный алгоритму (табл. 3.1), приведен в табл. 3.8. Структуры вычислений ошибок алгоритма (табл. 3.8) аналогичны структурам (рис. 3.1 и рис. 3.2), в которых, согласно (табл. 3.8), скалярные вычисления заменяются на век-торно-матричные и векторно-скалярные.
Для получения многоканального алгоритма, одноименного алгоритму (табл. 3.2), необходимо определить отношения правдоподобия:помощью которых векторы апостериорных ошибок линейного предсказанияа в алгоритме, одноименном алгоритму (табл. 3.5), также используются вычисления (3.77) - (3.80), в которых вычисления векторов априорных ошибок заменены вычислениями векторов апостериорных ошибок. Аналогичным образомполучен многоканальный алгоритм, одноименный алгоритму (табл. 3.6). Этоталгоритм приведен в табл. 3.9.
Таблица 3.9. Лестничный RLS-алгоритм со скользящим окном на основе априорных ошибок линейного предсказания и QR-разложения с использованием вращений Гивенса без операций извлечения квадратного корня (многоканальный, с одинаковым количеством весовых коэффициентов в каналах)Вычисления Ссылки
Алгоритмы, рассмотренные в настоящем разделе, эквивалентны многоканальным алгоритмам, рассмотренным в главах 2 и 3, при одинаковых количествах весовых коэффициентов в каналах. Арифметическая сложность представленных многоканальных алгоритмов (без учета операций обращения матриц энергии ошибок) примерно в М раз больше сложности одноканальных алгоритмов. При N » М и небольших значениях М арифметическая сложностьвыполнения операций [Е; ( )]" , [K%(k)Y, [Е; ( )]" И [Е ( )]" прак тически не сказывается на общей сложности алгоритмов.
Одним из широко используемых случаев, когда значение М мало и равно, например 2, является задача компенсации акустического стерео эха, ближнего и дальнего эха в модемах проводной связи (если выбрать Nm одинаковое),а также задача реализации усеченных полиномиальных адаптивных фильтров (см. главу 6). Для этих приложений, помимо алгоритмов, рассмотренных в главах 1 и 2, могут быть использованы и алгоритмы настоящего раздела.
Лестничные RLS-алгоритмы с возрастающим и скользящим окнами также могут регуляризироваться. При получении вычислительных процедур таких алгоритмов для фильтров с возрастающим окном вместо сигнала х(к - L) необходимо использовать сигнал р(к) в одноканальных фильтрах, и вместо вектора сигналов [х{(к -L),...,xM(k-L)\ необходимо использовать вектор сигналов[Р[(к- L),...,pM(k-L)]r в многоканальных фильтрах. В результирующих алгоритмах отсутствует множитель //, а также ряд слагаемых в уравнениях меняют знаки на противоположные. Пример одноканального регуляризированно-го алгоритма с возрастающим окном приведен в табл. 3.10. Аналогичным образом строятся другие версии одноканальных и многоканальных лестничных алгоритмов, рассмотренных в разделах 3.2 и 3.3. Структуры вычислений априорных ошибок в некоторых одноканальных алгоритмах с возрастающим окном и регуляризацией приведены на рис. 3.7 - рис. 3.9. Вычислительная сложность регуляризированных алгоритмов с возрастающим окном совпадает со сложностью алгоритмов со скользящим окном без регуляризации, т.е., подобно алгоритмам главы 2, она примерно два раза больше вычислительной сложности не-регуляризированных алгоритмов с возрастающим окном.
Регуляризированные версии линейно-ограниченных RLS-алгоритмов
Линейно-ограниченные RLS-алгоритмы с возрастающим окном, а также алгоритмы раздела 4.2, можно регуляризировать, подобно алгоритмам, рассмотренным в главах 1-3. Для этого при получении выражений, аналогичных (4.26) - (4.45), необходимо воспользоваться выражениями (1.7.2) и (1.7.4):и переменными %N{k) и PN( ) ЧТО соответствует регуляризированной корреляционной матрице (1.37). Полученные таким образом линейно-ограниченные версии регуляризированных алгоритмов с возрастающим окном приведены в табл. 4.4 - табл. 4.6. Вычислительная сложность алгоритма (табл. 4.6) примерно соответствует сложности алгоритма (табл. 4.3).
Для получении выражений, аналогичных (4.26) - (4.45), в случае регуля-ризированных RLS-алгоритмов со скользящим окном необходимо воспользоваться выражениями (1.13.2), (1.13.4), (1.13.6) и (1.13.8):регу ляризированной корреляционной матрице (1.40).
Полученная таким образом линейно-ограниченная версия регуляризиро-ванного алгоритма №3 со скользящим окном приведена в табл. 4.7. Вычислительная сложность алгоритма (табл. 4.7) примерно в два раза больше сложности алгоритма (табл. 4.3).Таблица 4.7. Линейно-ограниченный регуляризированный RLS-алгоритм №3 соскользящим окном Вычисления
В настоящем разделе приводятся сравнительные характеристики рассмотренных в настоящей главе линейно-ограниченных RLS-алгоритмов со скользящим окном и линейно-ограниченного NLMS-алгоритма 1216J на приме ре подавления с помощью 8-элементной эквидистантой ААР сигналов пространственно-разнесенных источников помех. Линейно-ограниченный NLMS-алгоритм представлен в табл. 4.8.
В рассматриваемой задаче, в отличие от обработки сигналов во временной области, линейно-ограниченные алгоритмы не используют сигнал d(k) иминимизируют сигнал на выходе ААР. Поскольку в алгоритмах вводится ограничение (требуемый уровень сигнала с известного направления полезного сигнала), то минимизация выходного сигнала ААР означает минимизацию компонент этого сигнала, обусловленных сигналами источников помех, расположенных в неизвестных направлениях. Алгоритмы раздела 4.2 и табл. 4.8 представлены в бщем виде, т.е. с использованием сигнала d(k). При моделированииААР значение этого сигнала полагалось равным нулю, т.е. d(к) = 0.
Направление на источник полезного сигнала совпадало с линией, перпендикулярной апертуре ААР (в{[) =0), т.е. с направлением максимума основного лепестка ДН. Сигналы двух источников помех располагались в направлениях, максимумов первых двух боковых лепестков ДН, т.е. в{1) =20 и 9,3) --20. Антенные элементы ААР предполагались всенаправленными. В качестве по лезного сигнала использовался нестационарный сигнал речи. Помехи моделировались стационарными сигналами (белым шумом). В среднем отношение сигнал-помеха на входе антенных элементов равнялось -20 дБ для каждой из помех. Аддитивный шум на входе антенных элементов отсутствовал.
Результаты моделирования NLMS-алгоритма при трех значениях масштабирующего множителя шага сходимости ju, равных 1; 0,1 и 0,01, представлены на рис. 4.3 - 4.5. Видно, что с уменьшением параметра // ошибки в принимаемом сигнале уменьшаются, но увеличивается длительность переходного процесса, что является известным свойством LMS- и NLMS-алгоритмов, распространяемым и на аналогичные линейно-ограниченные алгоритмы. На рисунках d - передаваемый полезный сигнал.
В то же время, RLS-алгоритм (рис. 4.6) демонстрирует превосходящие по сравнению NLMS-алгоритмом свойства как по уровням ошибок, так и по длительности переходного процесса, и не имеет такого параметра как шаг сходимости. Таким образом, известные свойства RLS-алгоритмов без ограничений также справедливы и в случае линейно-ограниченных RLS-алгоритмов. Длина скользящего окна при моделировании равнялась L = 256, что при частоте дискретизации fs = 8 кГц примерно соответствует интервалу стационарности речевого сигнала [148], оцениваемому в пределах 20.. .30 мс.
Наблюдаемые результаты также имеют объяснение в терминах значений ДН антенной решетки, см. рис. 4.7 и рис. 4.8. При моделировании задавалось ограничение уровня ДН АР в направлении на источник полезного сигнала, равное 0 дБ. Черным цветом показаны исходные ДН, серым - на к -й итерации алгоритма адаптивной фильтрации. Значения к соответствуют двум максимальным значениям ошибок сигнала на интервале наблюдения на выходе АР в случае NLMS-алгоритма. Из рис. 4.7 следует, что ошибки на выходе АР обусловлены «высоким» уровнем провалов в ДН, т.е. неполным подавлением сигналов помех, в то время как условие ограничения (прием полезного сигнала заданного уровня) выполняется на указанных, а также всех без исключения других итерациях алгоритма.
