автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Оптимизация рекуррентных алгоритмов и процессоров пространственной обработки сигналов

. Р -1 зл

ОДЕССКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

на правах рукописи

ЗАХАРОВ ВИКТОР ВАСИЛЬЕВИЧ

уда 621.396. 96: 621. 391. 26

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

05.12.13 - Устройства радиотехники и средств связи 05.12.04. - Радиолокация и радионавигация

Автореферат диссертации на соискание ученой степени кандидата технических наук

Одесса - 1992

Работа выполнена на кафедре ¡радиотехнических систем Одесского политехнического института

Научный руководитель - доктор технических наук, профессор Свердлик Мзиулим Бенияминович.

Официальные оппоненты: доктор технических наук, профессор Кисель Виталий Андреевич, кандидат технических наук, зав. отделом СШБ Мелешкевич Александр Николаевич.

Ведущая организация - научно-производственное объединение " Квант" (г.Киев).

ии

Защита состоится 21 января 1993 г. в 15 «а заседании специализированного совета Д 068.19.01 по присуждению ученой степени кандидата технических наук в Одесском ордена Трудового Красного знамени политехническом институте по адресу: 270044, г.Одесса, пр. Шевченко, 1, конференцзал ДК ОПИ.

Автореферат разослан 7 декабря 1092 г.

Ученъ "и секретарь ' ' у

оо

ОБЩАЯ ХАРЛКТЕРЯСШ'Л РЛШТЫ ■ Актуальность' темы. В последнее зрзмя для эффективного подавления помок е радиолокации щрское распространенно получши адаптивные актешше решетки (ДАР).

Эффективность работы ААР во шюгом определяемся возможное-гимн реализации весьма сложных алгоритмов пространственной об-работам сигналов. Основными показателе'эффективности алгоритмов адаптации является быстродействие процесса адаптаяии и его вычислительная сложность.

В последнее время в связи с бурлим развитием цифровой техники предпочтение отдается, гса>; правило, прямая алгоритмам пространственной обработки, позволяющий!, в стеган от градиентных алгоритмов, определить оптимальный весовой зектор га конечное число арифметических операций, что позволяет суцест-' вешзо ускорить сходимость и преодолеть зависимость ее от распределения собственных значений корреляционной матриц!.* (КЫ).

В условиях априорной неопределенности при веема ограниченном объеме обучавдей выборки нзибольаее распространение по -лучили регуляризованнье рекурреитгыэ алгорлтг.!а, ииеидие доса-точ:;о вксокуо скорость сходикссти, равную 2р~1 . где р - число источников помех заздеЯствукврсх на ААР. В зависимости от оргагшзац!!!! вычислительной процедуры они имеют различную вычислительную сложность: 0(Ь!?'С\) Для алгоритмов, исаользу-ети операции ¡«ад штрицага и 0(МК ) яля алгоритма, ис-пояьгукцих операции над векторами, где Д/ - рае!,юр репеткя, ¡{ - число независимых обучающих векторов.

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

Одним из путай снижения чувствительности алгоритмов к ошибкам вычислений явллсзся коди^асация известного векторного рекуррентного алгоритма, использумцего гоздестьо Вудбери, основанная на применении Солее устойчивых ьа'геааткчееккх процедур при обрат,8йки регулярпзоьанкей оценю', ЕМ, что позволяет снизить требования, к разрядное?;; до.

Очевидно, что известка! алгоритм и его ыодифшкщин -будут шэь- рааиг-сше пмасдиеяыш© сясвдосги а раэхшао разрядности еряфкетичссхии операций, в свяаи с этим ерзгшитедышй анализ аягоритысв только ко вычислительной слоквоеги или только по требуемой разрядности арсфмеягаеаои опорациД и® позволяет однозначно ответить на вопрос, какой яа алгоритмов является г.редпочткгелькей. Такое сравнение кокет быть проведано толы,о по некоторой комплексно«* мере сдоэиости,учктьшаодзй как. ылкслитедьиую слоиюсть алгоритмов, так ц требуеыу» равряд-кость вшолнекия аря<и:зтическкх операций. ,

Таким образом, актуальность теш обусловлена необходимости разработки и коследсвганя ргкуррентккя адаптивных алгоритмов более УСТ0Й-1ИЕ1Х-: к ошбкаы вычислений, поаводшим полу-.

чить выигрыш по требуемой разрядности ЛО и комплексной мере ! сложности по сравнении с извесяшм алгоритмом.

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

Нетоды проведения исследований. При реаеяии поставленных » диссертации задач использовалась аналитические я икисли-тельиае методы современного ыахеыахяпэдгаго аппарата, а «цепко:

а) аппарат теории вероятностей и математической статистики;

С) аппарат линейкой алгебры и матричный анализ;

в) современные численные ыетодл и методы програкадрова-

ш:я;

г)" методы моделирования па ЭВМ радиофизических стохастические процессов и алгоритмов их обработки.

Научная новизна. На зещигу.выносится следуведе результата, впервые полученные ига Езерзие достаточно подробно развитие з настоящей работе.

1. Католика сценка разрядности цифровых устройств (ЦУ) гектора весовых коэффициентов (ВЕК), аналого-цифрового преобразователя (АЦП), арифметических операций (АО), при конечном

числе обучаодвх векторов у. клшиенгш арм$ивхичсвкюс оперслдай с плавающей запятой для алгоритмов с ¡шпаередотЕеакым обращением оценки корреляционной матрицы к рекуррепгких.

2. Сразгштелышй анализ адаптивных прямых алгоритмов по требуемой разрядности ЦУ при выполнении ариф^егичеогах операций с шавахдей запятой.

3. Оценки разрядности ЛО вря использовании арк£четеки с фк.ко2роваш:ой запятой в рекуррентных алгоритмах, неходка анализа оиибск касштабирозашй и их илкимпзация.

4. Синтез кода-Зикащ:»! векторного рекуррентного регудяри-ооЕаааого адгории-а, испояьзукящх со сраваешв с иаоестаым алгоритмом бокее устойчивые к оиабкам вычислений иатегешпеские процедур;.

5. Сразиигелъшй авалю вгьоотаого и дода£нщ|раьашвд ад-горигкоз по личлелнгельной слогаоети, требуемой разрядности АО и камвдешгэз коре- слояаюста, учитыкшадй как их вычислительную с&акяосгь тш: и тробуе.иуа разрядность АО.

'Прагккческая цгппоеть результатов работа состоит в том,-что сайтогировапы кодаЗзкацш рекуррентного регуляризоваииого аягерю-л., погзл-fi^D епкг.чь anaapa-r/pir/ю саозаюсть процессоров по сраядогвэ с працезгороа, ргадкзувдкм известный алго-риг» и предохеш спзсс5и аппаратурой. реализации шгефгцяро-сашик смсрыиоа. Результаты раЗол: ь»гу? кайтк практическое прозпри ярэокюроьаюз! систек свяси, ралвогска'деи, ра-кажазоздйк,

Внедрение'научных результатов. Получении? в диссертация результаты внедрены в научно-исследовательском институте радиофизики it;«, ait. Расплетина (г.Носета), что подтверждается соответствующим актом.

Апробация работы. Основные положения диссертации доклады-валксь и обсуждались на Республиканских конференциях молодых исследователей, СПИ, Одесса, 198S - 1S92 г. г.

Публикации. По теме диссертация опубликованы работа C1...SJ.

Объем и структура диссертационной работы. Диссертация состоит из'поста разделов, приложения и списка литературы, мкв-чакдего в себя 85 наименования. Объем диссертации составляет ISO страниц, ¡включая 154 страниц основного текста, 13 страниц рисунков, б страниц таблиц и 9 страниц списка литературы.

СОДЕРЖАВ® РАБОТЫ В первом разделе диссертаций проведен анализ дятератур-1 их источников, из которых следует:

- н&вестные методам определения требуемой разрядности ЦУ не являются достаточно обх;и.и!, „ait как не могут быть, яслользо-ваиы при конечной объеме обучающих векторов и кэ могут Сыть применены для регудшризованкых алгоршггв пространственной обработали (как рекуррентных так и нерекуррентных).

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

Сформулированы цели и задач;; диссергациокой работы:

- разработка гцитой методики определения требуемой разря- ■ дкости ЦУ процессоров адаптивней пространственной обработки

сигб2л0в,

- синтез (модификация) рекуррентных адаптивных алгоритмов пространственной обработок

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

Второй раздел диссертации посвящен разработка единцой методики определения требуемой разрядности ЦУ в примах адаптивная ajtropsmsax прокгранствепной обработка сигналов, исподьэую-

максимально правдоподобную и регуляризованную оценки корреляционной матрицу: о непосредственном обращением ь&ксЕьадько правдоподобной оцемш Ш (НОМ Ш), с непосредственным обращение.'; . егуляризовакисй оценки 1Ш (II0M РО), рекуррентным обращенном регудяриаованной оцонки Kb! (POM РО).

осяоаанки предложенной методики получены оцени требуемой разрядности БЕЕ. - , АЦД - S , АО при использовании ари&мыкки с ящагакдей запятой - . Полученные оценки

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

При этой оценки для адгоришзз ЕС!.! ЫП при конечном объеме обучающих векторов, а такйз для регудяризовакиых алгоритмов (¡гак рег^ррентша так и нерзкур'гкткых) получены впервые.

Ьнагиз получоиках вкреякшй показывает, что основными па, растрами, определяемой гребевагаш к-разрядности ЦУ являются: рг.ггер р—л-тэт - // , гсеокэеио ¡ммезо/яум па зходе АР - оС , допуетт.^:? средние аотегд в отношении сягнал/помогигтм (ОС'ГГЛ) за счет коиотвей разрядности ЕВ$, АЦП, Ю - ^к » »/{я» , число обучввго« векторов - К и ветачияа относительного ва-раммра регуляризации . где 0РТг- параметр рог/-

лярнзац'гП. 61/ - модность пут.

3 алгоритмах НШ НО, КОМ к» разрядность ДУ ела "а сазтеит от числа обучав?;»: векторов, в алгоритмах РОИ РО разрядность ПУ уволдапваетса пропорционально ¡\ и для доепшшя потерь, аналогичны:: полученная з алгоритмах НСЛ ГО требуемся ьознгяш разрядности ПУ, на ведамиу (Кг) ¿о^ к*

Экспериментально угоЧНЗШ ОДйШ И !В»«й?Я ГрЖГЦМ изменения величины огяоеатолыюгэ '¡;атй1.-:5чарй рэгулйрийашз! пщ гоз-

дейстпй« пп ДР сяйсчй ',гочоч!шх вошя »а фне нойимх.

Показано, им зьйор порхисЯ Су'/д ) и ввтжя () гртч'пщ величины у/ л соответствии с выросшем

¡-и '

/V 4 10,

где Дг!:,! ({^р/ - минимальное сойсгпенное значсш:е регуляри-зовапной оценки К21 на числа прев;лзэип;их чпето-пукпвые, величина которого приближенно равна ¡.яркости исодеиев мгсеясшюго йс-.гу ч помеха.

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

С учетом уточненных границ величины параметра регуляризации проведен сравнительный анализ перечисленных алгоритмов по требуемой разрядности цифровых устройств ( ВВК, АЦП, АО), который показал, что при заданных потерях в эффективности Е:Ь лучшим с точки зрения точности Еьиисдений являются алгор!'т;.-ш о непосредственным обращением регуляризовашюй оценки корреляционной матрицы, худаиы - с рекуррентным обраденкем регуляризовашюй оценки корреляционной матрицы. Промежуточное значение по требуемо;! разрядности занимают алгоритму с непосредственным обращение!,: максимально правдоподобной оценки корреляционной натркцы.

В третье;/, разделе подучены оценки требуемой разрядности АО в рекуррепткш: алгоритмах при вычислениях с фиксированней

сумма (¡м- разрядности, полученной при вычислениях с плававдей

цапятей и дополнительной разрядности - Сжп , которая зависит от прг'меяяемопз метода масштабирования цифровых операндов при выполнении АО с фиксированной запятой.

На основании статистического метода анализа осибок квантования и представлгыя базовой опесащш ре^гррентноп' адго-

Ч

ритма - скалярного произведение двух векторов Д \ и х при выполнении-ДО с фиксированной запятой в виде

определена ка;

II V

.£[2$ = = Р„[Ш-[М- -[ЩШ^

где Л? - результирующая ошибка за счеу введения масштаби-рувдих множителей, Ас- вектор оаябки масштабирования на 1-й этапе, Р^ - матрица перестановок, состоящая из О и 1, определяющая последовательность выполнения операций сложения на г*-м этапе вычислительного процесса, I);- касштабирукщая диагональная ыатгаца с элемента}® равными ■ -1/2' ■

% - число разрядов на которое сдвигаются операнды перед выполнением АО ( 1 - 0,1,2 ... и т.д.), 4 .. О - знак поэлементного умножения,

предложена методика, позволяющая оценить дисперсию выходной

2

оьябки за счет сдвигов ( иЛ1) при выполнении АО с фиксированной запятой и использовании различных методов масштабирования.

Получена оценки дисперсии ошибок за счет сдвигов длл вычислительной процедуры, заданной общей масштабирующей матрицей fr.Dk и матрицами перестановок P¿ и проведен синтез вычислительной процедуры (определены матрицы р^ и коэффициенты с1с), имеющей минимальное значение .

Показано, что при условии использования >Т1-входовых сумматоров шиишльаое значение будет иметь вычислительная

процедура, матрицы j*j которой в |аадсй строке кыеат Ш единиц .

Иредлюкены кеходы иаскабирогашш, исподьаущце епраорную ииформрдкл о кориашюы распределении зходлых векторов. Тюка-за:'о, что в этом случае Еояг<га& касптаСируадего цаохнтеяя выбираемся равным d - , в то кэ среми для методов то-ытазарованкя, но исьольэзадих зтой ив&и&вишк cl - ■{f ff .

Предложена неаодкка ышашзацаи диеперсш; результирующей сшбка за счет сдвигов для заданно;', матрица!.;-: f^ к шжке-лем d. ецчксяктсльпой процедура при ьозтацвом масвгабирова-дк:. Ереялэ:г.еиийя метода» позсолгет • при заданны:: ¿Есгр;лт р; ouраде-лить ккозателк cl>' так, чтобы исключить roa-KiorjiocTb переполнения к в то же »реш -ишвшакговать величину

С. •

IIojiynsHii юэтюдавде о ценит J требуеьт» разряд-

ное V- АО в pc-j.7PpíFí¿:t« алгоритмах при вглисяекшх с фютяро-шакой езгаш>£ раэдмчкых ыегодов ^асатг^ирогания.

ВроЕедеа сраыаяельний акажй требуемой раздодоста АО й рзкурренхнид огпцздогх при Екгасгешйг с фиксированной загадай и кигояьзсзгнш-î медузу методов шсЕгаЗировшшя: - уасшгабнровачга но входу шшггеслеы cí-ifH;

- пощ-ггшпоа шсисАб'.5рсюа»:э №кшзс«гки C¡Li~ '//2» 1,а наядой

«*». = > Cl = Y/Wj

- шгдаабароваигэ ьо'кходу-шдалт&ге« ' cL-i ¡W i

- иозхакюэ масегайдре^лкпе шкшгаеляна, c/t' = //2

Показало, что требуемая р едкость лучшего из предло-яежых методов масштабирования (гьк-тавньЛ метод при практически совпадает с треоуемой разрядность» АО при испол! -госатш блочиоплзвавдея запятой,

Удксималъкая разрядность АО требуется при маезтабпровангш •со сходу шдагселе« с1~ '¡/Н . Промежуточные значения занимав? методы маевтабкрозания по входу мнешиелем

по-

отап'гь:;! - шезятегем ¿--¡/н При этем разрядность ДО при лучше» нетоде иаставвроваЕия отяичаэтел от разрядности ¿0 при зугаси кетодо «астегбарогания аз водкчину

Четвертой раздел яоелязэя еаятезу кодоФЭДФОзаш;* рекуррентных рзгуляризовантс: алгорктноя, позволяет^ снизить требования к раарядиоегд АО по срагиеяя» с известна! гекторнцм алгоритмом. Показано. что наиболее е^енживкыы способом ежп/.з-шш разрядности ДО в регудяркзоЕакнж алгоритмах является £?<к-торигация ТО ЯМ па матрицы более простой структуры.

На основании тождества Иорисола-Будберз дзя обрааеккя матриц

Г / Г . </■л-< V ,

К'р - (.1,/. ^Ак А а I

гда л ., ™ ] СС( ! 'Хг '..>. -. • • ♦ -;ОСк| - прямоугольная кагрнца

обучазда шкор<зв размера ¡\| X \( ,

Лк- = 6}>1 - матрица размера ,

■ \ - «дттчная ¡ш-рда размера , ,

сивдое^-идо ыодифжацки известного векторного рекуррентного

алгоритма, использующие наиболее устойчивые к ошибкам округлений вычислительные процедуры, такие как LL - преобразование Холенного, QR - преобразование Хаусхолдера, ортогональное преобразование Грама-Шмидта.

Получены оценки вычислительной сложности и требуемой разрядности арифметических операций в кодифицированных алгоритмах. При этой под вычислительной сложностью понимается число комплексных операций умкожений-сдс.'мгнкЯ, а под требуемой разрядностью АО минимальное число разрядов при котором достигается потери в эффективности не превышающие 3db при К' ~ 2р~ 1 • Проведено сравнение полученных оценок с оценками известного алгоритма . Показано, что отношения вычислительных сложностей модифицированных алгоритмов Холецкого, Хаусхолдера, Грама-и известного алгоритма - Сг* , &Н , (7 зависит от .отношения - К ■' Ú , причем для алгоритма Хаусхолдера эта зависимость очень слабая и в широком диапазоне указанного от-нощэния составляет приближенно 1.Б pasa.

Для алгоритмов Холецкого и Грама-Шмидта при увеличении отношения К / N вычислительная сложность увеличивается по сравнению с ивве^гным алгоритмом, так например, при K/N << 1 1 . а при К'/М -1 -G »1.33, Q -2.00.

Наряду с некоторым повыпешен вычислительной сложности в модифицированных алгоритмах иыеет место снижение требуемой разрядности АО, что является следствием применена* более устойчивых вычислительных процедур. Установлено, что величина &bfic¿> называющая снижение разрядности арифметических

опершей в модифицированных алгоритмах но сравнению с известным при \(~2р~ / . приближенно равна Н^/р Так при изменении величины hjU/^t в пределах 10.. .60 <jb, величина лЬм„ изменяется от 1 до б разрядов. С другой стороны, при К~ и одинаковых разрядностях АО модифицированные алгоритму позволят здфектавво давить помехи- интенсивностью на 6...14 db болюе чем известный алгоритм.

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

Сравнительна анализ известного и дояМяяйровзшшс алгоритмов по комплексной кере сложности показал-.

- для алгоритмов Холецкого и Грана-й.ядта виигркп еаписит от отношений и <i/fi , причем при увеличении отношншл

К / N здигрш уменьшается, а при увеличения отгосгаая - увеличивается. Так при !wM « ! и изменении а диапазоне 10...60 оЬ вынгрьш составляет для алгоритма Холецкого 1.00 ... 1.49, Грат- Шмидта 1.18 ... 1.63 раза, при К / М - 5 чля алгоритма Яолецкого mtrpua состзвляс"

0.71 ... 1.05, для алгоритма Граш-Шмидта 0.59 ... 0.82. - в алгоритме Хаусходдэра вьыгрыа ко зависит от отаопэниз 1ч / (V к составляет для указанного диапазона иакснекг-й отко-ш&ккя &//■! величину 0.79 ... 1.50.

Соотношения ыезду алгоритмами по .комплексной ыере слодкс-стя в.савасикооги от откоаеюй К / N' и & f /V праьедс-иы в таблица, в которой принята следу аде обозначения: ГО -алгоритм Грама-Пмндта, 1 - алгоркхм Холсцкого, "Н - адгорюу Хаусхолдара, паз - известный алгоритм.

К/К' d/ß (db)

10 20 so 40 50 50

ГШ Ш га ГШ ГШ ГШ

X.1I33 X X X X - у

КЛ)<<1 н изв кзв. К, изв н Н

К К КЗВ изз

ИЗБ иг-в изв.Х X 1/ X

К/М-0.5 X V' Kü.H пзв,Н,ГШ н.гш н.га

га, к П2.Н язв ИЗВ

кзи ИЗБ кзв «зз,И Н Н

K/N-1 н н Н • X V

X X X Ш ;:зз изв

ш ГШ • ГШ ГШ Ш

В представленной таблице верхний алгоритм в кгадом из приведен.-ж случаев является лучкьм в сшсле шшв.*'"«^ кок-плекской меры слояаюсги, так при \( / N << 1 лучт-а: является алгоритм Гра:,;а-й,:ндт?; при К / N - 0.5 и мшжяши

d / /'■! < SOdb - кзвестай алгоритм, а при Ы //' > Äkto / I '

алгоритм Холецкого; при K/N -1 н отнесении d/j'i < 4СИ*Ь

- известны)! елгоруды, а 40сЬ алгоритм Хаужолщега.

В пятом раздело исследованы вопроси аппаратурной реализации кодифицированных алгоритмов.

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

Проведен выбор элементной базы ИЫС и требуемой разрядности арифметических устройств для известного процессора ( $т ) и синтезированного, использующего алгоритм Хаусхолдера ( Уис ).

Проведен сравнительный анализ аппаратурных затрат на реализацию указанных процессоров.

Показано, что при использовании элементной базы ИУС серии 1802 в случае, когда Ьизз Ьпа, < 16 еит и не требуется распараллеливания устройств умножения, гак для известного процессора, так-и синтезированного, нет принципиальных различий между аппаратурной сложностью известного и синтезированного процессора.

Для ситуаций, когда £ < 16 бит, а > 16 бит,

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

Как показали результаты хоздоговорной ЙП\ винолкяешя НИЛ "Радиоэлектроника" в интересах ЮШРФ им. академика Расплетина, применение синтезированного процессора, использукдего

рекуррентный адаптивный алгоритм Хаусхолдера в реальной цифровой адаптивной система позволят обеспечить возможность эффективного полавлешхй псшэх при аппаратурных затратах в несколько раз иже чек; в сдаствущих системах ; научная новизна технической разработки подгверздена реиекиеы патентной экспертизы 2НКИГПЭ о выдаче автору патента по заявке N 5003166/09/060951/.

В вестом раздала подведены итога работы и основные результаты , которые сводятся к следующему.

Проведен цикл исследований, направленных на синтез моди-¿гцлрованиах адаптивных алгоритмов пространственной обработки сигналов устойчивых к ошбкг»' вычислений, ср&вкитеяьвыа шшиз коБестного г; дада&адировгааш алгоритмов по вычислительной с:.'.поста, требуемой разрядности выполнения арифметических операциз к комплексной ыере сло.тлостн, а талте проработку вопросов аппаратурной реализации тдйфицированных алгоритмов.

1. Разработана сданная методика оценки разрядности цифровых устройств (ДУ) -„ вектора весовых коэффициентов (£БК), аналого-цифрового преобразователя (Щ1), арифметических операций (АО) в ярамах авторствах адаптивной пространственной обработки, позволяющая получить расчетные соотношения при вычислениях с плаьаацеЯ . я фассировашшой гапятой , которые справедливы, как при конечной объеме 'Обуча&цих векторов, таг: и в установив-веисц резкиые, и провести с едангах повиздй сравнительный анализ прзшх адгоритшв по требуемой разрядности ЦУ.

8. Предавши шдафшяккд кзгестгсго рекурреигвого регуля-ркговишаго векторного адгор$ша, исиользугяцце более устойчн-

вис к ссибк&и шршсг.еглй ыатокаткческие прсцецури, ««и'.о к:« метод квадрата« ¡сорней Хслецкого, ОВ разложение Хлусхолдера, '.ртогоиалкзация Грема-йедта « проведено исследование их ктмвноети. Получелн оценки ючиашг?л>ио1 сложности и требуемо.» рагрядпоетз ЛО з ьр)дкЛ{г?»рсеу1,5'}: алгоритм, Проп-гдоно сравнение получшгих оценок с сцоккакн известного игорат^«.. Проведен ерап;:':гелышЛ анализ дадйфнцарованпых и известного алгоритмов по кокплгксноЯ нерэ слжнсстк.

3. 1{сслслзва:пл вопроси аппаратурной геа-ггватаи сиптегиро-ваккого адаптивного алгоритма. доодьзутего пре-обрасогагае :йус"слйерс.. Прсзедсш схемотехническая ,1осгт.б01кл ^'/ккциояалъ-ных узлов сраьзитедьииЛ анализ аппаратурой:! --атрат на реали-?еца» вроцзссороз, используй-:,!;;; извески-Я и сшгейрироггнйьи алгорнгк Хаусхолдера, гиЗранноЯ слемснаюЛ бзвн.

основные ада

1. Полученные аналитические оценки требуемой разрядности иийхшг устройств (ЦУ) показали, что при оадаяш потерях в 5$1'сктаз1юсти 3<Ь лучшим с точка гренки точности шшеяэпкл являются алгор.«ш с пспоередстзснш/м "решением регуллрнсо-ззквоЯ оценки »дарреяяциетюй ьагркцы <ком РО), хугаяш - с ре-куррентнии обращением регударлзовашюй оценки корреляционной \mvxw (ГСМ РО), разрядность ¡сотого дет достоекия пегерь г» оК---!шгснг)С'1и аналогпч::? :>: получений-! в алгоритмах ПОМ Т'О ело-дуст подоите на'гздичияу } 6г<2„ !'(■ • гло /\ - число обу^лда векторов. Прокеточчое значение ло ?ребуа:оЯ р^ряд-«ости гаш-гсот адгеритиц с кепосредстзсчшьи обравекюи ¡ячеи-

кааьно правдоподобной оценки корреляционной матрицы (НСМ МП).

2. Требуемая разрядность АО в рекуррентных алгоритмах при . вычислениях с фиксированной запятой зависит от применяемого метода масштабирования. Минимальная разрядность АО требуется при поэтапном методе масштабирования и величине ыаситабпруюце-го и:ож!теля с[ = -//'/77 , где (V - размер реиетки; требуемая разрядность АО в этом случае приближается к разрядности АО вря вычислениях с бяочноплавающей запятой. Максимальная разряд-' ность АО требуется при масштабировании по входу и величине масштабирующего ынояителя При этом разрядность АО при

дучием методе масштабирования отличается от разрядности АО при худшем методе масштабирования на величину //}

Промежуточное значение по разрядности АО занимают методы масштабирования по входу при величине масштабпрукдего * мнохнтеля СЫ/Ш и поэтапный при величине масатабируодего множителя

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

3.1. Отношение вычислительных слелюстей кодифицировангш алгоритмов Холецкого, Хаусхолдера, Грама - Ыидта к известного алгоритма зависит от отношения К </ М . причем для алгоритма Хаусхслдера эта зависимость очень слабая и составляет приближенно 1.5 раза. Для алгоритмов Холецкого и Грама - Емкдта при К / М « х указанное отношение приближенно равно единице для обоих алгоритмов, при \( / Н -1 соответственно 1.зз и г.оо. ,

3.2. Наряду с некоторым повышением вычислительной сложности, в модифицированных алгоритмах иметг место снижение требуемой разрядности АО по сраьнению с известным алгоритмом, что является следствием применения более устойчивых вычислительных процедур. Установлено, что величина на которую мо;кет быть снижена разрядность АО слабо зависит от помеховой ситуации и приближенно равна (-"//4) (о^ Йс1 /Ц , где - отнесение помеха/иум на входе АР, р - величина относительного параметра регуляризации. С другой сторона при одинаковых разрядностях АО и ¡(= . где р - число помех, модифицированные алгоритмы позволяют эффективно давить помехи интенсивностью на 6...14 сЬ больше чем известный алгоритм.

3.3. Выигрыш по комплексной мере слс.таости для алгоритмов Холецкого и Грама-Шмидта зависит от отношений \\ /и

с1 /у'/ . При изменении \{/ ¡\| в пределах от 1/М до 1, а величины в диапазоне 10. ..60 йЬ выигрыа составляет для алгоритма Холецкого 0.71 ... 1.49, Грат-Шмидта 0.59,. .1.63 раза. В алгоритме Хаусхолдера ваигрыа не зависит от отношения К / ¡V и составляет для указанного' диапазона изменений с/ /у"*-' величину 0.79 ... 1.10.

4. Сравнительный анализ аппаратурных затрат на реализацию процессоров, использующих известный и синтезированный алгоритм Хаусхолдера, показал:

4.1, При использовании элементной Сазы ИКС серии 1802 в случае, когда не требуется применения методов распараллеливания устройств умножения,, как для известного процессора, так и

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

4.2. Для ситуаций, когда известный процессор на заданной элементной бззе может быть реализован только с использованием распараллеливания выигрыш в аппаратурной сложности синтезированного процессора но сравнении с известным ыокет достигать нескольких раз, что стало возможным благодаря снижеяи» требований,!: разрядности АУ в процессоре, использущем - модифицированный алгоритм Хаусхолдера.

Процессор, использующий преобразование Хаусхолдера, принят к внедрению в современный радиолокационный комплекс,-а оригинальность технической разработки подтверздена решением патентной экспертизы Е1ШИГПЭ о выдаче автору патента по заявке Н 5003165/09/030951/.

Основные■результаты диссертации опубликованы в работах:

1. Свердлик Н.Б., Захаров В.В. Модифицированные рекуррентные алгоритма пространственной обработки с повышенной устойчивость» к саибкам вычислений. Радиоэлектроника.-1991. - N4.

- С.62 - 66.(Изв. выси. учеб. заведений).

2. Захаров В.В. Сравнительный анализ методов масштабирования в процессорах пространственной обработки сигналов использующих операции с фиксированной запятой //Радиоэлектроника.

- 1SS0. - HQ. - С.? - 12.(Изв. высы. учеб, заведений).

3. Захаров В.В. Методы масштабирования, нспользувяие априорную информацию о нормальном распределении входных векторов //радиоэлектроника.- 1991. - N11. - 0.46 - 50. (Изв. выси. учеб. заведений). .

4. Захаров В.В. Оценки разрядности цифровых устройств в процессорах адаптивной пространственной обработки //Радиозлек-

5. Захаров З.В. Методы снижения требований к разрядности в цифровых алгоритмах пространственной обработки, использующих операции с фиксированной запятой //Сборник рефератов депонированных рукописей. 1990, вып. 1, НИМИ.

6. Захаров В.В. Эффективный алгоритм пространственной обработки сигналов //Сборник рефератов депонированных рукописей, 1990, вып. 1, ВИМЙ.

7. Захаров Б.В. Модифицированный алгоритм пространственной обработки, использующий преобразование Хаусхолдера. //Сборник рефератов депонированных рукописей, 199С, вып. 6, ВШИ.

3. Заявка N 5003166/09/060951, ШИ^НОКЗ 23/00. Адаптивная антенная система. Захаров В.В. - Полож. реи. ЕНИИГПЭ от 26.06.92 .

тропика.- 1992. -.N4 . - С.4 - 12 .(Изв. высш. учеб. заведений).

С0И1

В.В. Захаров

Ьап, № -ко !/.!£. и