Функциональная и вычислительная эффективность RLS-алгоритмов в арифметике действительных чисел для многолучевых адаптивных антенных решеток

Заключение. Предложенные методы синтеза и взаимного преобразования передаточной функции могут непосредственно использоваться при проектировании перестраиваемых аналоговых и цифровых фильтров различного назначения.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Змий Б.Ф., Ланнэ А.А. Синтез линейных цепей с управляемыми характеристиками // Теоретическая электротехника. - 1983. - № 35. - C. 26-36.

2. Pavan S., Tsividis Y. Time-scaled networks - Properties and applications in the design of programmable analog filter // IEEE Transactions on Circuits and Systems. - Part II. - Vol.47, № 2, February 2000. - Р. 161-165.

3. Тепин В.П., Тепин А.В. Параметрические и автопараметрические системы с хаотической динамикой // Известия ЮФУ. Технические науки. - 2011. - № 6 (112). - C. 84-93.

4. Тепин В.П., Тепин А.В. Управление динамическим хаосом: синхронизация параметрических гиперхаотических систем // Труды Международного конгресса по интеллектуальным системам и информационным технологиям (IS&IT’11). Научное издание в 4-х томах. Т. 1. - М., Физматлит, 2011. - C. 440-447.

5. Айчифер Э. Цифровая обработка сигналов: практический подход. - 2-е из.: Пер. с англ.

- М.: Изд. дом «Вильямс», 2004. - 992 с.

6. Тепин В.П., Тепин А.В. Программируемые цифровые фильтры: синтез законов управления передаточной функцией // Известия ЮФУ. Технические науки. - 2011. - № 1. - C. 50-57.

Статью рекомендовал к опубликованию д.т.н., профессор Я.Е. Ромм.

Тепин Владимир Петрович - Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет»; e-mail: vtepin@gmail.com; 347928, г. Таганрог, пер. Некрасовский 44; тел.: 88634613116; кафедра систем автоматического управления; доцент.

Тепин Алексей Владимирович - e-mail: alexey.tepin@gmail.com; кафедра систем автоматического управления; аспирант.

Tepin Vladimir Petrovich - Federal State-Owned Autonomy Educational Establishment of Higher Vocational Education “Southern Federal University”; e-mail: vtepin@gmail.com; 44, Nekrasovskiy, Taganrog, 347928, Russia; phone: +78634613116; the department of automatic control systems; associate professor.

Tepin Alexey Vladimirovich - e-mail: alexey.tepin@gmail.com; the department of automatic control systems; postgraduate student.

УДК 621.396.67

В.И. Джиган

ФУНКЦИОНАЛЬНАЯ И ВЫЧИСЛИТЕЛЬНАЯ ЭФФЕКТИВНОСТЬ КЬ8-АЛГОРИТМОВ В АРИФМЕТИКЕ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ

ДЛЯ МНОГОЛУЧЕВЫХ АДАПТИВНЫХ АНТЕННЫХ РЕШЕТОК

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

Адаптивная антенная решетка; ЯЬ8-алгоритм; линейные ограничения; действительная арифметика; комплексная арифметика.

V.I. Djigan

PERFORMANCE AND COMPUTATIONAL EFFICIENCY OF REAL-VALUED ARITHMETIC RLS ALGORITHMS FOR MULTY-BEAM ADAPTIVE ARRAYS

The paper considers a computational procedure for one of possible algorithms of weight coefficients computing in multi-beam adaptive arrays for constant modulus signal processing. The introduced algorithm is linearly constrained Recursive Least Squares algorithm. Some conditions that allow to reduce most of operations to the real number arithmetic are specified. The fragments of the algorithm relating to linearly constraints and Kalman coefficients computing are given. Estimation of computing procedure complexity is considered. The simulation and results demonstrate the efficiency of the algorithm.

Adaptive array; RLS-algorithm; linear constraints; real-valued arithmetic; complex-valued arithmetic.

Сегодня адаптивные антенные решетки (ААР) широко используются в качестве антенн радиосистем различного назначения благодаря способности подавлять помехи, источники которых расположены в направлениях, отличных от направления на источник полезного сигнала. Если ААР строится на принципах цифровых антенных решеток [1], то при наличии достаточных вычислительных ресурсов она может быть легко трансформирована в многолучевую ААР, что расширяет ее функциональные возможности, например, позволяет одновременно принимать полезные сигналы от нескольких пространственно-разнесенных источников. Один из возможных алгоритмов вычисления весовых коэффициентов многолучевой ААР для приема сигналов с постоянной огибающей информационных символов рассмотрен в [2]. Это рекурсивный алгоритм по критерию наименьших квадратов (Recursive Least Squares, RLS) c линейными ограничениями, базирующийся на приемах [3-5]. С помощью этого алгоритма обеспечивается адаптивное подавление некоррелированных помех, источники которых расположены в неизвестных направлениях, а с помощью линейных ограничений обеспечивается поддержание заданного уровня диаграммы направленности (ДН) в основном луче и подавление коррелированных помех - полезных сигналов, принимаемых с известных направлений соседних лучей многолучевой ААР.

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

Если в ААР антенны располагаются симметрично относительно фазового центра, то корреляционная матрица R N принимаемых решеткой сигналов

xN (k) = k (k), x2 (k), . .., xn_1 (k), xn (k)] T = к (k), x2 (k), ..., X* (k), x* (k)]T (1) является персимметричной эрмитовой матрицей. Здесь xn (k) - сигнал, принимаемый n -й антенной; k - номер отсчета этого сигнала; N - число антенн ААР.

Обычно в адаптивных алгоритмах корреляционная матрица оценивается на возрастающем окне отсчетов как

1 K

RN = ТI xN

K k=1

где K - число отсчетов сигналов, участвующих в формировании оценки этой матрицы. Операция (2) называется прямым усреднением. Если K и входные

сигналы ААР являются стационарными, то ИN ~ ИN .

Использование прямого-обратного усреднения [6]

ИС [ХN

2К к =1 2

при оценке персимметричной эрмитовой корреляционной матрицы приводит к

улучшению адаптивного формирования ДН ААР, поскольку эта оценка является

более точной, так как

В уравнении (3) J- это перестановочная матрица.

Если в адаптивном алгоритме используется матрица (3) и вычисляются весовые коэффициенты, обладающие комплексно-сопряженной симметрией для антенн, расположенных симметрично относительно фазового центра ААР, то большую часть операций в этом алгоритме можно выполнить в арифметике действительных чисел. Причем результирующая сложность такого алгоритма получается примерно в два раза меньшей, чем у исходного алгоритма в арифметике комплексных чисел. Линейно-ограниченный КЬБ-алгоритм, построенный на этом принципе, рассмотрен в работе [7]. Применение этого алгоритма в однолучевой ААР, принимающей сигналы с постоянной огибающей информационных символов, приводится в [8], а в многолучевой ААР - в [9].

В настоящей статье рассматривается один из возможных вариантов вычислительной процедуры алгоритма [9]. В табл. 1 и 2 приведен алгоритм для одной под-решетки многолучевой ААР. Алгоритм состоит из части, связанной с линейными ограничениями (табл. 1), и части, связанной с вычислением векторов коэффициентов Калмана (табл. 2). В каждой из подрешеток алгоритмы различаются вектором f], определяющим ориентацию основного луча ДН подрешетки и провалы в направлении лучей соседних подрешеток. При получении алгоритма (табл. 1, 2) использованы приемы, аналогичные приемам, используемым при получении адаптивных КЬБ-алгоритмов с оценкой корреляционной матрицы, обрабатываемых сигналов на скользящем окне отсчетов [5]. Описание входных и выходных сигналов, а также переменных, используемых в алгоритме (табл. 1, 2), может быть найдено в [2, 5, 6, 9].

На рис. 1-3 представлены результаты численного моделирования алгоритма [2] и алгоритма (табл. 1). Оттенки кривых на этих рисунках соответствуют процессам в многолучевой ААР, ДН которой на последней итерации алгоритмов показаны на рис. 3 кривыми аналогичных оттенков. Из рис. 2 следует, что алгоритм (табл. 1) обеспечивает в среднем на 3...5 дБ более глубокие провалы в ДН в направлениях на источники адаптивно подавляемых помех и в 1,5.2 раза более короткие переходные процессы, чем алгоритм [2]. Это свидетельствует о более высокой функциональной эффективности алгоритма в арифметике действительных чисел. Помимо алгоритма (табл. 2), для вычисления векторов Калмана в алгоритме (табл. 1) также могут быть использованы процедуры на базе леммы об обращении матрицы [7], обратного рИ-разложения без операций извлечения квадратного корня [8] или преобразования Хаусхолдера [9]. Подсчет эквивалентного числа арифметических операций в арифметике действительных чисел в различных вариантах алгоритма [2] и в аналогичных вариантах алгоритма, рассмотренного в настоящей статье, показывает, что число операций в последнем алгоритме примерно в два раза меньше, чем в первом, что свидетельствует о его более высокой вычислительной эффективности.

Таблица 1

ЬС НЬ8-алгоритм в арифметике действительных чисел

Вычисления

Ссылки

ІпШа^аНоп;]N (0) = 8~2і„, Qш (0) = См/ [СНСм/ ] 1, Ь N (0)=Q ш (0)Гу, к-; (0) = к-; (0), Сш = и N Сш,

Q„/

Рог к = 1,2,., К

Ум

г N,1 (к) = Яе[и N г N (к)] , ^1 (к) = 52

Вычисление 8 N д

_ /,1

1J +

_ J,1

Q 'мJ,1 (к) = [2MJ (к -1) - 8N,1 (к)иТд(к)] , т _

1 - ^,1 _ J,l

QMJ,1 (к) = QMJ,1 (к) + QMJ (0) [і_ CMJ QMJ,1 (к)]

^ ,1

hN,1

Ь N ,1 (к) = Ь N,1 (к) + Q мJ ,1 (к) [г^ CMJ Ь N ,1 (к)]

г N,2 (к) = Іш[и N г N (к)] , ^ (к) = 0

Вычисление 8 N

_ J,2

и/,2

QMJ,2(k) = [^^^^(к) - 8N (к)иТ,2(к)]

1J +

_ J ,2

QмJ (к) = QMJ,2 (к) + QмJ (0) [і[ - CMJQMJ,2 (к)]

^N,2

hм (к) = ЬN,2 (к) + ^ (к) [г, - [ ЬN,2 (к)]

ТНЇ

hN

End foг к

Таблица 2

Вычисление векторов ^ N (к) с помощью КЬ8-алгоритма на основе обратного ОК-разложения с операциями извлечения квадратного корня

Вычисления

Ссылки

ІпіїіаІігаІіоп: К N

7( У-1) N, у,1

(к) = 0, 1 < у < N, Ь^Кк) = 1 Рог і = 1,2,., N

аад

ь«(к) =

ї/кіГЧк )]2 + ади

^,1

^«(к) = Ь^/>(к )[ЬЛІ)l(k )]-1

Рог у = 1,2, ., і

Я

N ,у',1 '

«N,2,1

End йг у End foг і

8 N ,1 (к) = и ^^к )[ ,ї)(к )]

т

N, у, 2

:!2(к) = 0, 1 < у < N, Ь№2(к) = 1

Рог і = 1,2,., N

aЛi2

ЬЛЛІ)2

5N,i,2

С^і,2(к) = Ь^Чк ^(к )]

Рог у = 1,2, ., і

Яу

«,

End йг у End foг і

8N (к) = иNN2) (к^^(к)]-1

Результаты моделирования рассмотренного алгоритма приведены ниже.

к, номер итерации

а

х 10

-20

ш д -40

90 IX -60

-80

-100

1

1 2 3 4 5

к, номер итерации

б

x 10

Рис. 1. Переходные процессы в терминах ДН в направлении некоррелированной помехи: а — алгоритм в арифметике комплексных чисел; б — алгоритм в арифметике действительных чисел

0

К номер итерации

а

x 10

к, номер итерации б

x 10

Рис. 2. Переходные процессы в терминах усредненных по 100 реализациям ДН в направлении некоррелированной помехи: а - алгоритм в арифметике комплексных чисел; б — алгоритм в арифметике действительных чисел

0 4 4 4 4

Г і 7\

-20 М к\чМ Г %11» / / % / і Г" 1 1 \ ! ' Лі

щ ч[ 1] 1 Її

-40 ; Т! \ ґ ї

-60 1 1 - — 1 > J її '

-80 1

100 I і

-50 0 50

0, град.

а

0 44 4 4

г і 7\

-20 и. 1 і \ к\чМ Г %ІІ» / / % / і [-1 1 \ ! і' Лі

\пГ ш 1] 1 VI

-40 "”( і ТІ і Р ї

-60 і і - — 1 > J її ї

-80 1

100 і і

-50 0 50

0, град. б

Рис. 3. ДН в конце переходного процесса: а — алгоритм в арифметике комплексных чисел; б - алгоритм в арифметике действительных чисел

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Litva J., Lo T.K.-Y. Digital beamforming in wireless communications. - Artech House., 1996.

- 301 p.

2. Джиган В.И. Многолучевая адаптивная антенная решетка // Известия ЮФУ. Технические науки. - 2012. - № 2 (127). - C. 23-29.

3. Chen Y., Le-Ngoc T., Champagne B., Xu C. Recursive least squares constant modulus algorithm for blind adaptive array // IEEE Trans. Signal Processing. - 1985. - Vol. 33. - № 2.

- P. 1452-1456.

4. Resende L.S., Romano J.M.T., Bellanger M.G. A fast least-squares algorithm for linearly constrained adaptive filtering // IEEE Trans. Signal Processing. - 1996. - Vol. 44. - № 5.

- P. 1168-1174.

5. Джиган В.И. Многоканальные RLS- и быстрые RLS-алгоритмы адаптивной фильтрации // Успехи современной радиоэлектроники. - 2004. - № 11. - С. 48-77.

6. Huarng K.-C., Yeh C.-C. Adaptive beamforming with conjugate symmetric weights // IEEE Trans. Antennas and Propagation. - 1991. - Vol. 39, № 7. - P. 926-932.

7. Джиган В.И. Вычислительно эффективный линейно-ограниченный комплексный RLS-алгоритм в арифметике действительных чисел // Доклады 14-й Международной конференции «Цифровая обработка сигналов и ее применения (DSPA-2012)» (Российская академия наук: Институт проблем управления им. В.А. Трапезникова, 28-30 марта 2012 г.).

- М., 2012. - Т. 1. - С. 77-81.

8. Джиган В.И. Алгоритм с пониженной вычислительной сложностью для управления адаптивной антенной решеткой радиосистем цифровой связи // Вопросы радиоэлектроники. Серия «Общетехническая». - 2012. - № 2. - C. 97-106.

9. Djigan V.I. Multy-beam constant modulus adaptive arrays in real-valued arithmetic // Proceedings of the 10-th IEEE East-West Design & Test Symposium (EWDTS) (Kharkov National Technical University, September 14 - 17, 2012). - Kharkov, Ukraine. - P. 54-59.

Статью рекомендовал к опубликованию д.т.н. А.В. Гуреев.

Джиган Виктор Иванович - Открытое акционерное общество Научно-производственный центр «Электронные вычислительно-информационные системы» (ОАО НПЦ «ЭЛВИС»); e-mail: djigan@elvees.com; 124460, г. Москва, Зеленоград, Южная промышленная зона, пр. 4922, стр. 2; тел.: +74997311961; лаборатория перспективных исследований; д.т.н.; главный научный сотрудник.

Djigan Victor Ivanovich - Open Join Stock Company ELVEES R&D Center of Microelectronics; e-mail: djigan@elvees.com; Bld. 2, Pas. 4922, Southern Industrial Park, Zelenograd, Moscow, Russia, 124460; phone: +74997311961; advanced development laboratory; dr. of eng. sc.; principal researcher.

УДК 681.3.06

С.К. Буханцева

РАЗРАБОТКА АЛГОРИТМА РАСПОЗНОВАНИЯ РУКОПИСНЫХ СИМВОЛОВ НА ОСНОВЕ РАСТРОВОЙ ГРАФИКИ

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

Алгоритм; растровая графика; эталонные последовательности; сегментация; распознавание символа.