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

г М ;

I

АКАДЕМИЯ НАУК БЕЛОРУССКОЙ ССР ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ИНСТИТУТ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ

На правах рукописи Крот Александр Цихайяович

УДК 681.5:681.325

АНАЛИЗ И ГЕНЕРИРОВАНИЕ ИИОШЩСЕНЫХ ПОТОКОВ В ЗАДАЧАХ МОДЕЛИРОВАНИЯ ДИНАМИЧЕСКИХ СИСТЕМ НА ОСНОВЕ ПОЛИНОМИАЛЬНОЙ АЛГЕБРЫ

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

05.13.01 - Управление в технических системах

Автореферат

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

Минск - 1991

Работа выполнена в ордена Трудового Красного Знамени Институте технической кибернетики АН БССР

Научный консультант:

Официальные оппоненты:

Заслуженный деятель науки и техники БССР, доктор технических наук, профессор П.И. Чеголин

доктор технических наук, профессор A.A. Туник

доктор технических наук, профессор В.А. Мищенко

доктор технических наук А.К. Иикелсон

Ведшая организация: Институт кибернетики АН УССР им. В. У. Глушкова

Защита состоится » I " октября 1991 г. в Ю00 час. на заседании Специализированного совета Д.006.24.01 при Институте технической кибернетики АН БССР (220012, г. Минск, ул. Сур-ганова, 6,конференц-зал).

С диссертацией мохно ознакомиться в библиотеке института. Автореферат разослан ш/Ош ЫЮАсЬ 1991 г.

" ' - / . о Ч - I -

/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Проблема моделирования динамических систем приобрела в последнее время возрастающее значение в связи с широким использованием цифровых ЭВМ в научно-исследовательских и проектно-конструкторских работах. Существующие методы моделирования динамических объектов спираются на различные, часто не связанные между собой математические модели, допускает решение только отдельных задач. Отсутствие единого подхода к моделированию динамических объектов в автоматизированных системах обработки информации и управления приводит к необходимости изменения алгоритмического и программного обеспечения таких систем при идентификации, анализе, синтезе динамических объектов с различными свойствами (например, стационарности или нестационарности, линейности или нели^зйности).

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

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

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

Основные задачи исследования. В соответствии с поставленной в диссертационной работе целью,исследования проведены в следующих направлениях:

- дальнейшее развитие теории полиномиальных вычетов примени-

- г -

тельно к проблеме спектрального представления цифровых сигналов в ортогональных базисах и обобщение основных положений цифрового спектрального анализа на основе полиномиального подставления сигналов;

- разработка дискретных моделей нестационарных линейных динамических систем (ЛДС), стационарных нелинейных динамических систем 1НДС), нестационарных НДС с Юдиных позиций полиномиального и спектрального представлений процессов;

- разработка концепции обобщенного спектрального анализа в биортогональных базисах собственных функций оператора нестационарной ЛДС;

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

- синтез ускоренных алгоритмов оптимального дискретного управления ЛДС с использованием теории полиномиальных вычетов;

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

Методы исследования. Результаты работы получены в процессе теоретических и экспериментальных исследований.

Теоретические исследования в работе проводились на основе методов полиномиальной алгебры, теории систем и теории случайных функций, теории групп, колец и полей, матричной алгебры, функционального анализа, теории функций комплексного переменного, теори] автоматического управления, а экспериментальные исследования вьп^ нялись с помощью моделирования на ЭВМ в составе цифровых автоматизированных систем обработки, управления и идентификации сигналов и изображений.

Научная новизна. На основа единого подхода к полиномиально--спектральноыу представлению цифровых сигналов и динамических систем лично автором диссертации получены следующие новые научные ре»ультаты:

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

- введен новый класс ЛДС, инвариантных относительно операто-

ра К- сдвига, — Кы- стационарных ДЦС — ив рамках теоретшсо--полиномиальных представлений разработана спектральная теория К„-- стационарных ДЦС и Км- стационарных случайных процессов;

- разработаны основные положения обобщенного спектрального анализа К- стационарных случайных процессов в неортогональных (биортогональных) базисах собственных функций операторов Кн-

-стационарных ЛДС в циклическом векторной подпространстве;

-- в русле теории К^- стационарных систем предложена модель квазистациснарных ЛДС и случайных процессов, а в сочетании с фунж-диональнш разложением Винера-Вольтерра получена модель квазистационарных НДС;

- обоснован принцип вычислительного дуализма между стацио -нарными и стационарными ЛДС и на его основе разработан метод собственны4- преобразований в различных полях для синтеза дефективных алгоритмов цифровой обработки одномерных (многомерных) сигналов и решения проблем идентификации и моделирования стационарных ДЦС и НДС;

- синтезирован ряд эффективных алгоритмов вычисления одномерного и двумерного дискретного преобразования Фурье (ДП8), циклической свертки (ЦС) действительных (эрмитово-симметричнвк)(Прсле-довательностей на основе метода синтеза неизбыточных алгорйтмои действительного быстрого преобразования Фурье (ДЦВ1Й), метода собственных преобразований в различных полях и показано, что данньв ■ алгоритмы имеют наименьшие вычислительные затраты и лучшие показатели быстродействия и точности по сравнении с известными;

- получены оценки минимальной вычислительной сложности и синтезированы быстрые алгоритмы для вычисления полиномиальных вычетов, обобщенной Кы- свертки, преобразования Вандермонда и показано их применение для решения динамических задач оптимального дискретного управления;

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

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

рования динамических объектов и цифровой обработки сигналов.

Практическая ценность. Разработанные автором модели К„--стациокарных (квазистационарных) ЛДС и НДС пригодны для исследования объектов (изделий машиностроения) в автоматизированных системах управления динамическими испытаниями, при реализации как одномерных, так и двумерных регулируемых нерекурсивных фильтров в цифровых системах обработки и идентификации фотографических изображений, при синтезе дискретных систем оптимального управления.

Полученные алгоритмы вычисления одномерного и двумерного действительного (эрмитова) ДП4 и ЦС использованы при исследовании стационарных процессов и полей, идентификации и моделирования стационарных ДДС и НДС, анализе и генерировании процессов со сдви-гсм-сжатием во времени, а также изображений, подверженных деформациям сд ига, масштабирования и поворота.

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

Связь темы с планами основных научных работ. Исследования и разработки по теме диссертации выполнены в соответствии с

- заданием 04.04 Республиканской межотраслевой комплексной научно-технической программы по информатике "Разработать быстрые алгоритмы и программное обе-печение для цифровой обработки одномерных и двумерных массивов" (утверждена постановлением Совета Министров БССР от 16.11.1988 г., № 327 и распоряжением Президиума АН БССР от 9.12.1988 г., № 662), по которому автор диссертации является ответственным исполнителем;

- планом научных работ Института технической кибернетики

АН БССР по проблеме I.I3.5 темы 7 (Машиностроение - 28) "Разработка методов моделирования автоматизированных систем управления экспериментальны«! исследованиями" (№ гос. per. 0186.0080396);

- планом научных работ Института технической кибернетики АН БССР по проблеме 1.13.5 темы 14 (Машиностроение - 29) "Теория

и методы имитационного моделирования" (IP гос. per. 01 .и.90032109);

- техническими заданиями на НИР по теме "Лоток", где автор диссертации является ответственным исполнителем по разделу "Анализ", НИ0КР АС0ВИ, рядом договоров с научно-исследовательскими учреждениями и с промышленными предприятиями страны, выполняемых

в Институте технической кибернетики АН БССР.

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

- при создании алгоритмического и программного обеспечения режимов двумерной цифровой фильтрации, спектрального анализ» сжатия информации для систем обработки и идентификации фотографических изображений в н.п.о. "Точные приборы" (г. Ыссква);

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

- при доработке существующего и создании нового программного обеспечения режимов спектрального анализа, генерирования и идентификации для автоматизированных систем управления испытаниями автомобильных конструкций в Научно-техническом центре п.о. "АвтоВАЗ" (г. Тольятти);

- при разработке многопроцессорной системы управления динамическими испытаниями автомобилей в УГК п.о."АвтоВАЗ" (г. Тольятти) ; • ■

- при создании ускоренных процедур и программ спектральной обработки сигналов в реальном масштабе времени для совершенствования программного обеспечения информационно-вычислительной системы контроля и идентификации процессов в НИИ "Алгоритм" н.п.о. "Кибернетика" АН УзССР (г. Ташкент);

- при реализации комплекса программ, выполняющих эффективные алгоритмы расчета двумерного ДШ, в подсистеме вторичной обработки радиоастрономических изображений в Институте прикладной астрономии АН СССР (г. Ленинград);

- для разработки архитектуры и функциональных схем основных блоков ряда микросхем, а также специализированного комплекта СБИС для построения параллельно-конвейерных процессоров цифровой обработки сигналов в СКТБ п.о. "Интеграл" (г. Минск).

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

Комплекс программ, реализующих синтезированные в работе ал-

горитмы вычисления одномерного и двумерного ДПФ и ЦС, приняты в Государственный фонд алгоритмов и программ СССР.

Апробация работы. Основные результаты работы докладывались и обсуждались на Всесоюзной конференции "Перспективныэ методы планирования и анализа экспериментев при исследовании случайных полей и процессов" (г. Нальчик, ноябрь 1982 г.). Всесоюзной научно-технической конференции "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов" (г. Рига, ноябрь 1983 г.), Республиканской научно-технической конференции "Цифровые методы обработки сигналов в задачах радиолокации, связи и управления" (г. Свердловск, май 1984 г.), П Всесоюзном симпозиуме "Статистические измерения и применение микромашинных средств в измерениях" (г. Рига, ноябрь, 1984 г.), Всесоюзной ниучно-техни-ческой конференции "Моделирование - 85. Теория, средства, применение" (г. Киев, апрель 1985 г.), Всесоюзной конференции "Методы и микроэлектронные устройства цифрового преобразования и обработки информации" (г. Москва, ноябрь 1985 г.), Всесоюзной конференции "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов" (г. Рига, ноябрь 1986 г.), П Всесоюзной конференции по актуальны« проблемам информатики и вычислительной техники "ИНФСРМАТИКА-87" (г. Ереван, октябрь 1987 г.), Всесоюзной научно-технической конференции "Моделирование - 88. Проблемы моделирования динамических систем" (г. Кишинев, июнь 1988 г.), Зональной конференции "Обработка информации в автоматизированных системах научных исследований" (г. Пенза, апрель, 1989 г.), XX Международном симпозиуме по автоматической технологии и автоматизации "15АТА-89" (Италия, г. Флоренция, май 1989 г.), XI Всесоюзном совещании по проблемам управления (г. Ташкент, сентябрь 1989 г.), Международной конференции молодых ученых "КОУАСОУ - 89" (ЧСФР, г. Ковачов, октябрь 1989 г.). Научно-технической конференции "Цифровые методы в задачах управления (г„ Днепропетровск, октябрь 1989 г.), Международной конференции по цифровой обработке сигналов "1_БР1С - 90" (г. Рига, апрель 1990 г.).

Публикации. По теме диссертации опубликовано 5? печатных работ, в том числе монография "Дискретные модели динамических систем на основе полиномиальной алгебры". - Минск: Навука I тэхн!ка, 1390. — 312 с.

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

работу, отмеченную премией Ленинского комсомола Белоруссии в области науки и техники за 1990 год, а результаты исследований по созданию и внедрению средств автоматизации испытаний изделий в машиностроении удостоены премии комсомола Микщинн в области науки и техники за 1987 год.

Структура и объем работы. Диссертация состоит из введения, семи глав и заключения, изложенных на 369 страницах машинописного текста, иллюстрирована 82 рисунками и таблицами, размещенными на 75 страницах. Список литературы содержит 263 наименований; приложения составляют 95 страниц, в том числе акты о внедрении

- 23 страницы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе показано, что полиномиальное представление дискретных сигналов на конечных интервалах обобщает их спектральное представление в базисах различных ортогональных функций. Посредством выбора полинома-делителя и затем вычисления полиномиальных вычетов можно находить коэффициенты различных ортогональных преобразований. Это делает возможным обобщение ортогональных дискретных преобразований в рамках введенных' теоретико-полиномиальных преобразований (ТПП):

№2), ке г.; (1а)

где дискретно-временный сигнал {.х^ — последовательность значений непрерывного сигнала х(1) з заданные моменты времени

(гЛ - шаг дискретизации), представленные числовым рядом п>0,1.....N-1 (Ы — длительность временного интервала). Цифровой сигнал получается из дискретно-временного сигнала в результате квантования его но уровню, т.е.

— область определения^ — область значений цифрового сигнала);

f(•) — некоторый функционал от дискретных переменных п и к (соответственно временногоп и частного к индексов). Например, {(ллЬ^^к1"") - скалярное произведение векторов

л *1т=(К<-1.....^Ло^'пе^^ 5 представляющих числа

п и к в системе счисления по основанию т.;

О-«. — примитивный корень степени т, полученный из решения уравнения 2^1=0 в кольце V, т.е. - корень полинома ;

С(2) — делитель полинома над полем разложения ЯсЧ (с(г)\ I (.Х^О) , такой, что обеспечивает невырожденность преобразования (1а) — 0(0^)* 0. Например, если Кп.кХн1"? к1т)> и С(г) = =2^-1 • это означает существование примитивного корня 2 степени •т. в кольце полиномов У12]/(2т+1), т.е. ШосЦг"^)» так как

Отличительной особенностью ТПП (1а,б) от других дискретных преобразований является то, что вычисления в них выполняются в два этапа, сначала в полиномиальном кольце УСЗ]/((2^1)/с(2)), а затем в кольце V . Другими словами, ТПП осуществляют отображения последовательностей чисел ХЛе\/ в последовательности полиномов Хк(.2)вУ[2]/((2^1)/С(2)) и затем в последовательности коэффициентов ТПП . т-е-

V—ЧМ/(<а-1)/ссм)—V. (2)

Отображение V-*-УЕЯЛи™ 1)/С(2)) позволяет сократить число арифметических операций при вычислении ТПП (точнее, заменить умножения в V более тривиальными операциями сложения и сдвига полиномиальных массивов в кольце \Д21/((211)/С(а)) , ь также оптимально "спроектировать" желаемую структуру феобразования.

В работе рассмотрены ТПП, позволяющие обобщать дискретные ортогональные преобразования следующих видов: 1) с сепарабельным (разделимьм)едром; 2) с несепарабельным ядром; 3) с ядром типа кронекеровского произведения сепарабельных или несепарабельных ядер.

Итак, обобщение дискретных ортогональных преобразований посредством ТПП позволяет:

- перенести структуру известных ортогональных преобразований (Фурье, Виленкина-Крестенсона, Хаара, Хартли, Меллина, Чебышева

и т.д.) в другие числовые поля и, следовательно, выполнять цифровой спектральный анализ в других арифметиках (например, гармонический анализ в конечных полях посредством теоретико-числовых преобразований (ТЧП));

- синтезировать ноше дискретные преобразования с желаемыми свойствами, вытекающими из противоречивых требований практики к быстродействию и точности вычислений, объемам используемой памяти ЭВМ (примером может служить синтез псевдо-ТЧП на основе ТПП

путем выбора различных полиномов-делителей с(2) в (1а), (2));

- заменить значительную часть умножений в данном числовом поле V более тривиальными операциями сложения и сдвига полиномов в полиномиальном кольце \Д2]/(12"^1)/ССг)) , а значит, разрабатывать более эффективные алгоритмы для вычисления различных ортогональных преобразований над V .

ТПП определяют обобщенную структуру дискретных ортогональных преобразований над алгебраическими полями, содержащими примитивные корни из единицы или обобщенные тригонометрические функции. Это позволяет трактовать ТПП как метод построения ортогональных базисов в заданном алгебраическом поле и способ перехода «с различным полям для данной структуры преобразования. Выбирая характеристические параметры ТПП (например,N,0^.и С.(2)), можно проводить цифровой спектральный анализ дискретных сигналов в различных ортогональных базисах. Например, на основе ТШ обобщены и синтезированы следующие дискретные ортогональные преобразования: дискретное преобразование Фурье (ДГЙ); 'ГЧП Мерсенна, Ферма и псевдо-ТЧП Нуссбаумера, Дюбуа-Венетсаноцулоса; дискретные преобразования Уолша-Адамара (-Пэли, -Качмажа), Виленкина-Крестексо-на, ТЧШК; полиномиальные преобразования• (ПП) Нуссбаумера, многомерные Ш1; дискретное преобразование Хаара, обобщеннее преобразования Хаара; дискретное преобразование Меллина (ДШ), ТЧП Меллина; дискретные преобразования Чебышева, Хартли, косинус-ДШ, ТЧП Хартли и Чебышева; композиция ДПЗ-ДПМ.

В приложении к данной главе исследованы некоторые важные свойства ТПП (линейности, ортогональности, временной и частотной задержки, обобщенной свертки, инвариантности энергетического спектра относительно обобщенного сдвига).

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

Отмечена важная роль циклостационарных ЛДС (или ДДС, инвариантных к циклическому сдвигу) для цифрового моделирования дискретных стационарных ЛДС на конечных временных интервалах. Поскольку одно- и многомерные циклостационарные ЛДС описываются посредством одно- и многомерных ЦС, собственнши преобразованиями

которых являются соответственно одно- и многомерные ДШ, целью исследований настоящей главы явился синтез эффективных по количеству арифметических операций, быстродействию, точности, структуре, объемам используемой памяти алгоритмов вычисления одно-, многомерных ДШ и ЦС.

На основе разложения полинома 2."-1»(2м-, М= 7? в (1а) и метода дихотомии в работе дан вывод рекурсивного алгоритма комплексного БШ по постоянному основанию, а с использованием дополнительного разложения 2.,1*1=(2Н/-4Х21Ч/+ р,— алгоритма комплексного БШ по расщепляемому основанию.

Используя принцип вычислительного дуализма между ДШ и ЦС» автором модифицирован алгоритм Рейдера и предложен усовершенствованный подход к вычислению ДШ длиной р — простое число на основе циклической и косоциклической корреляций длин (р - I)/2; показано, что предложенный алгоритм требует теоретически минимального числа умножений.

Разработан новый метод синтеза рекурсивных алгоритмов действительного БШ (АДБШ), неизбыточньх по числу арифметических операций для действительнозначных данных и содержащих только две элементарные базовые операции типа "бабочка". Синтезирован ДЦБШ по основанию 2 с рекурсивной структурой; предложены три модификации АДБШ по основанию 2.

На основе данного метода разработан новый эффективный ДДБПФ по расщепляемому основанию — АДБПФ-РО, основанный на разложении действительного N - точечного ДШ на действительное N/2- точечное ДШ и деэ действительные N/4 - точечные Д®, содержащий только две элементарные базовые операции ДЦБШ (см. рис. I). В основу АДБПФ-РО положен вышеупомянутый алгоритм комплексного БШ по расщепляемому основанию и свойства эрмитовой симметрии весовых множителей и коэффициентов ДПФ, нечетно-временного ДШ (НВДП2) действительных последовательностей, учитываемые на кавдом этапе алгоритма.

Граф-схема АДБПФ-РО длиной N = 16 дана на рис.1. Вычислительная сложность АДБШ-РО определяется соотношениями:

МСыьСм/аК^ы^+г; (3)

Как показано в работе, АДБШ-РО сокращает в среднем в 1,6 раза общее количество операций по сравнению с алгоритмом действительного БШ Кули-Тьюки, в 1,5 раза — по отношению к алгоритму действительного БШ Рейдера-Бреннера, в 1,2 раза — относи-

I. Граф-схема 16-точечного АДБПФ-РО

Г Н^п!

ЩлнГ"

2. Схема декомпозиции циклостаронарной ЛДС на ряд

К : стационарных ЛДС, 1

тельно Б1Й Бергланда; ДЦБПФ-РО содержит на 25%-45% меньше сложений, чем модификации ДЦБВД по основанию 2 (при совпадающем количестве умножений).

В работе показано, что ДБП5-Р0 имеет примерно равное число операций, отнесенных на один отсчет длины исходной последовательности, по отношению к действительнозначному алгоритму Винограда (при этом АДБПФ-РО имеет более регулярную структуру — см. рис. I). По структурной сложности и числу базовых операций разработанный ДЦБШ-РО превосходит лучшие зарубежные аналоги (например, алгоритм действительного БЛФ Дюамеля).

Проведен сравнительный анализ по точности вычислений новых алгоритмов действительного БО$— АДБП5 по основанию 2 и АДБГЫ-РО; уточненный статистический анализ этих алгоритмов в арифметике с фиксированной запятой показал, что ДЦБПФ-РО среди рассмотренных алгоритмов имеет наименьшую вычислительную погрешность: .уровень шума округления в ДЦБПФ-РО в 1,8 раза ниже по сравнению с алгоритмом действительного Б1Н Кули-Тьюки и в 1,4 раза ниже по сравнению с ДЦБШ по основанию 2. Показано, что отношение сигнал/нум в АДБПФ увеличивается на 7,4 дБ для каждого разряда, добавляемого к длже регистра. Вывод относительно более низкой вычислительной погрешности, присущей ДЦБГО-РО по сравнению с другими алгоритмами, справедлив и для арифметики с плавающей запятой, что подтверждается экспериментальными данными, приведенными в работе.

На основе методики АДБПФ-РО разработан новый алгоритм вычисления НВДПФ действительных последовательностей — действительный НВБПФ-РО, позволяющий сократить количество арифметических операций в среднем на 25% по сравнению с традиционным подходом. Предложен новый подход к вычислению действительного точечного ДЛ5 ( Н-2 ), основанный на алгоритме обратных полиномиальных преобразований (АОПП-Д) в сочетании с алгоритмом действительного НВБПФ-РО, который позволил сократить вычислительные затраты относительно построчно-столбцового алгоритма Б ГЦ в 2—3 раза. Показано, что алгоритмы на основе полиномиальных преобразований целесообразно использовать для эффективного вычисления ТЯП, заданных над конечными вычислительными структурам;, (например, ■ для расчета двумерного ТЧГК или одномерного ТЧПВЮ.

В диссертации разработан новый метод синтеза рекурсивных алгоритмов эрмитова БГ№ (АЭБГШ, неизбыточных по числу арифмети -ческих операций для эрмитова-симметричных данных и содержащих только две элементарные базовые операции. АЭБГК являются алгорит-

мами обратного БЩ для коэффициентов Д® действительных последовательностей при замене комплексных весовых мчожителей на комплексно-сопряженные.

Синтезирован АЭБШ по расщепляемо^ основанию (ЛЭБШ-РО), позволяющий обрабатывать эрмитово-симметричные последовательности с наименьшими вычислительными затратами. Этот алгоритм имеет быстродействие, аналогичное АДБ115-Р0.

Предложен эффективный алгоритм вычисления действительной ЦС с помощью АЦБПФ-РО и АЭБШ-РО; вычислительная сложность такого подхода определяется соотношениями: ММ-СМ/Яи^Ч-ЗУЪ, (4)

В приложении к главе описан алгоритм вычисления ЦС, который использует только АДБГКБ-РО и обладает упрощенной структурной схемой по сравнению с алгоритмом ЦС, полученным на основе АДБЛФ-РО и АЭБШ-РО. Показано применение двух изложенных алгоритмов расчета действительных ЦС для ускоренного вычисления действительной линейной свертки.

Разработанные эффективные алгоритмы вычисления действительного (эрмитова) одно- и двумерного ДПФ и ЦС нашли широкое применение в спектральном анализе и моделировании одно- и двумерных стационарных случайных процессов и ДДС. Например, АДБПФ-РО я АОПП-Д используются для вычисления оценок спектра мощности одно-и двумерного стационарного случайного процесса, АЭБ1Э-РС — для генерирования стационарных случайных процессов (полей); алгоритмы вычисления ЦС на основе АДБПФ-РО /АЭБПФ-РО или только АДБПФ-РО в сочетании с методом перекрытия с суммированием применяются для идентификации и моделирования стационарных ЛДС с помощью ЭВМ.

В третьей главе введен новый класс линейных динамических систем (ЛДС), инвариантных относительно оператора Км- сдвига, — Км- стационарных ЛДС и разработана спектральная теория представления и исследования К„- стационарных ДДС и процессов, заданных на конечных интервалах.

Оператор стационарной ЛДС в матричной форме имеет вид:

гк:

яж:

(5)

где Км— матричный оператор обобщенного Кн- сдвига со

структурой матрицы Фробениуса 0 10

к:

0 0 1

т.. 0,1, ...,N4,

0 0 0 ... 1 ^м V Я-"-« • • •

трансформирующий импульсную переходную характеристику ДДС в зависимости от начала отсчета, т — символ транспонирования. Фундаментальным свойством операторов обобщенного сдвига и Км- стационарной ЛДС является коммутативность этих операторов, т.е. К^/^ЗП'^ы^К^ Это означает, что они имеют одинаковый набор собственных функций, причем собственные значения для оператора обобщенного Км- сдвига находятся как корни полинома

) , так как ¿¿(К^ЛЕ^М.

Определены роль и место К„- стационарных ЛДС среди классов ДДС, инвариантных относительно операторов обобщенного сдвига(0Х). В связи с этим доказан рад теорем и следствий из них. Обобщено положение о едином собственном преобразовании — СП0С — для операторов сдьига и систем, порожденных данным 00С, на случай неортогонального несимметричного СП0С. Как следствие этого, доказано, что СПОС операторов Км- сдвига и К^- стационарных ДДС описывается неортогональным преобразованием Вандермонда. Это означает, что свойство СПОС для операторов обобщенного К^- сдвига и К„- стационарной ЛДС имеет следующий вид:

>т'Ск)ЗД.....О; (7а)

■ (76)

где Дм— матрица СПОС.

Показано, что • К„- стационарные ЛДС обобщают традиционные цик лостационарные, т.е. ЛДС, инвариантные к циклическому сдвигу (в (о), (б) необходимо положить ), а также могут

моделировать ряд ЛДС, инвариантных относительно других типов 00С (например, относительно параметрического сдвига, если в (5), (6) положить

Исследованы свойства неортогоньльных СПОС.Доказано, что для СПОС справедливы свойства обобщенной Кд- свертки:

х аГ-УДЧ^Л^), Ч,«^, (8)

где — обобщенная К- свертка векторов I и7Г,

и- символ поэлементного произведения векторов. Из (8) непосред -

ственно следует свойство коммутативности для обобщенной Км--свертки: Х^п^ТС^Х.

Исследован класс дискретных случайных процессов, инвариантных относительно 00С Показано, что таковым является векторное циклическое подпространство оператора сдвига, где ат— порождающий вектор Базксом М- мерного циклического подпространства Ск1ат1 является множество линейно-независимых векторов {атК™ |то»0,1,...ЛН}, так как, согласно теореме Гамильтона-Кэли, К^Кн V .Л

Исследованы алгебраические свойства операторов Км- сдвига и циклического векторного подпространства 00С К^. Показано, что степени матричных 00С образуют бесконечную циклическую муль-типликатиьн.уи группу, причем обратные элементы группы также имеют структуру операторов обобщенного К^- сдвига:

I.

К =

А N

ж.

(9)

V0-

о С

Матричный оператор К^1 является с опро воздающим для полинома

Показано, что циклическое подпространство С^^Т инвариантно относительно оператора т.е. ХтКмеСк[а',]) если ХгеСк1а,3.

Б диссертационной работе введены обобщенные понятия згаитар-ности, эрлитова сопряжения к инволюции для 00С , позволяющие строить обобщенную спектральную теорию в базисаос СПОС аналогично традиционному Фурье-анализу. Так, согласно условию унитарности для 00С имеем: ^

(II)

где ~ — символ эрмитова сопряжения. В свою очередь, операция эрмитова сопряжения оператора включает операции инволюции и транспонирования: ^

Кн=(*От, (12)

где * — символ инволюции (аналога понятия комплексного сопряжения) . С учетом соотношений (9) - (12) действие операции эволюции на 00С Кмзаключается в преобразовании 00С Кмк операторуКнсо структурой матрицы Фробениуса, являющейся сопровождающей полинома ^(Г) вида (10), в транспонировании К.м относительно побочной диагонали. С учетом введенных обозначений имеем:

КМ??. «3)

где Ъ- - символ транспонирования относительно побочной диагонали.

В диссертации с учетом введенных инволютивных 00С (13) построено расширенное векторное циклическое подпространство С^[ат], для которого С^Са-^с

Исследованы свойства дискретных сигналов на временном интервале длиной N, принадлежащих циклическому векторному подпространству, — реализаций К,^ стационарного случайного процесса: отмечено свойство бесконечности ансамбля Кн- стационарных случайных процессов; показано, что при подходящем выборе элементов

матричного оператора Кммодель Км- стационарных процессов обобщает квазистационарные; рассмотрен физический смысл процессов, порожденных 00С Км. В работе показано, что К,»~ста-цлонарные ДДС — подкласс нестационарных ЛДС, ядро оператора которых линейно разделимо по времени возбуждения и моменту наблюдения данной ДДС.

В работе показано, что спектральный анализ К^ стационарных процессов и ДО целесообразно проводить на основе биортогональ-ных базисов СПОС в циклическом векторном подпространстве Данный вывод базируется на следующих фактах:

1) Каноническое описание ДДС достигается в базисах СПОС,

но в случае Км- стационарной ЛДС они не являются, вообще говоря, ортогональными; с другой стороны, ортогонализованные базисы не являются собственными для данного оператора ЛДС, в связи с чем возникает потребность развития спектрального анализа в базисах прямого и обратного неортогона/.-ного СПОС, т.е. в биортогональных базисах СПСС.

2) Некоторые положения спектрального анализа в биортогональ-ш.тх базисах СПОС Км- стационарных ЛДС и процессов разрабатывались относительно действительного векторного подпространства Я14/К . Но в связи с тем, что энергетический К„- спектр сигналов из

не обладает свойством инвариантности к Кн~ сдвигу, был шеден более широкий класс сигналов — циклическое векторное подпространство С^аЧ , в котором та трудность устраняется.

В связи с вышеизложенным, спектральный анализ в биортогонань-ньк базисах СПОС К(1- стационарных ДДС и процессов из циклического векторного подпространства является наиболее универсальным по сравнению с другими возможными подходами.

Е диссертации разработаны осношые положения обобщенного

спектрального анализа в биортогональных базисах СПОС Кн- стационарных процессов в циклическом векторном подпространстве. Прежде всего исследовано семейство СПОС для операторов обобщенного Км- сдвига и ЛДС.

Введено понятие сопряженного векторах*в циклическом векторном подпространстве . На его основе даны определения энергии сигнала в подпространстве СГ^СЙ1"] :

Ех= ХГХ' , Хте С^ [5.4;

а также взаимной обобщенной К»г корреляции сигналов в Ск£ат] :

и взаимного энергетического К^- спектра сигналов в подпространстве С* [5Т] •

к ' (15)

В частности, при х»7С соотношения (14) и (15) определяют соответственно обобщенную Кы- автокорреляцию энергетический К-автоспектр 5 я . Как показано в работе * между ними существует однозначная взаимосвязь на основе пары прямого и обратного СПОС, описываемая аналогом теоремы Винера-Хинчина. Показана инвариантность энергии и энергетического автоспектра относительно Кн- сдвига в циклическом векторном подпространстве Ск[<хт3 ; также доказано, что матрица СПСС диагонализирует ковариационную матриц/ Кн- стационарного процесса.

Получены временные и частотные условия квазистационарности Для К"м- стационарных ДЦС:

; (16а)

При выполнении частотного условия квалистациснашости (166) базисная функция СПОС стремится к базисной функции ДП$: Ак—ехрС-^як/М). Поскольку величина <ок»1хкМ соответствует частоте к -й функции ДГНг, то может трактоваться как частота к- функции СПОС,

а величина ^к=-^аг^лкимоет смысл линейной частоты к- функции СПОС, что соответствует уравнению Ван-дер-Поля. Поскольку свободные колебания, возникающие в ДОС, описываются функциями СПОС, в работе сделан вывод о наиболее простом (каноническом) спектральном анализе кваэистационарных ЛДС в биортогональном базисе собственных колебаний, возникающих в линейных системах после прекращения внешнего воздействия.

Разработана спектральная модель К - стационарных процессов и ДЦС, полученная на основе заданного энергетического Коспектра

и обратного СПОС.

В четвертой глава обоснован и разработан принцип вычислительного дуализма между циклостационаркыми и Км- стационарными ЛДС, позволяющий сводить выполнение ЦС к расчету рада обобщенных К„-

- сверток меньших размеров и, наоборот, вычисление обобщенной К^-

- свертки проводить посредством ее погружения в ЦС вдвое больших размеров.

Введено ТПП-СПОС по МссЦ(г):

Хк=ХС2)ЛосКг-Хк),Лкв7. к,о.....N-1, (17б)

обобщающее неортогональное СПОС, и на его основе дана полиномиальная трактовка обобщенного К- сдвига и обобщенной Кы- свертки: — г) Ш 2£Х(2) Аоо1 <ЦЗ); (18а)

С использованием (18а,б) для случая, когда полином ^ф^П^^ЗО

- разложим над полем констант на ^взаимно неприводимые сомножители (^(2) , такие что , доказаны теоремы, согласно которым операторы обобщенного ^ - сдвига и Кн- стационарной ДЦС допускают представление:

(»а)

где Кт Н - (НГ 1 Н»;... ■ . А. М — оператор блочного СПОС (элементарных преобразований) над Ф , т.е. Ац»11^Ц , ¿¡¡е еЯсУ , Ф — символгрямой суммы матричных операторов. Соотношения (19 а, б) обобщают (7а, б) случай нелинейных сомножителей полинома <^.(2). На основа (196) обоснована декомпозиция стационарных ЛДС (в частности, циклостационарных ЛДС)на ряд Км4-

- стационарных, таких, что М«2.Ы;(рис. 2). Поскольку блочное СПОС в (19а,б) определяется над полем констант, оно вычисляется в арифметике рациональных чисел 0 посредством сумма-разностных операций. Это означает, что декомпозиция Км- стационарных ДЦС осуществляется на основе СПОС над 0 без выполнения действительных .умножений , т.е. может быть выполнено на основе быстрых вычислительных процедур.

Декомпозиция оператора, циклостационарной ЛДС на множество операторов К^т стационарных ДЦС меньших размеров (см. рис. 2) является одной из двух фаз принципа вычислительного дуализма между стационарными к К^ стационарными ДЦС.

В русле данного принципа разработан метод быстрых СПОС в различных полях для вычисления дискретных преобразований и сверток. Суть предложенного метода состоит в последовательном применении быстрых вычислительных процедур СПОС дискретных сверток для каждого поля , причем V^cV^- Другими словами, наряду с разложением матриц СПОС на слабозалолненные матрицы имеет место разложение поля Vt на подполя (например,QcRcС , где Q.R ,С — поля рациональных, действительных, комплексных чисел).

Характерной особенностью описанного метода является использование процедур быстрого СПОС для вычисления обобщенных сверток, составленных из собственных функций. Доказаны соответствующие теоремы. Согласно одной из них, если JN — унитарная и разложимая матрица СПОС, то матрица обобщенной свертки LN(íl,l>)»составленная на основе собственной функции также разлагается подобно матрице JN . Это позволяет почти в 2 раза уменьшить»ак число умножений, так и число сложений по сравнению с традиционнш способом, основанным на теореме сб обобщенной свертке в базисе СПОС.

В диссертации метод СПОС в различных полях широко представлен как метод вычисления одно-, двумерных ЦС и ДШ на основе композиций СПОС в рациональном Q , действительном R и полиномиальном R[2]/(Qí(*)) полях. Показано, что дискретное преобразование Хаара — блочное СПОС над Q для ЦС длиной N-¿*, нечетно-частотное Д10 (НЧДП5) — СПОС над С (или над R) для косоциклической свертки (КЦС) длиной N=2", ПП Нуссбаумера — СПСС над Rt2]/U"'ÍO для полиномиальной ЦС длиной N»2*.

Как видно из рис. 2, с помощью блочного СПОС над Q действительная ЦС длиной N-2 сводится к расчету двух-, четырех-,...., N/2 - точечных действительных КЦС. В свою очередь, КЦС действительных последовательностей псдсчитываются с использованием соотно -шения (8) на основе СПОС над R , имеющего вид НЧДПФ над R . В работе синтезирован алгоритм быстрого СПОС над R (Г7а,б) при Д.*."

Вычисление действительной КЦС на основе алгоритма быстрого СПОС над R для N>256 является более эффективным по сражению с рекурсивно-гнездовым алгоритмом Нуссбаумера (по числу сложений более, чем б 2 раза). Получен новый алгоритм расчета действительных ЦС на основе процедур быстрого СПОС над Q л R с наименьшей вычислительной сложностью (4), который по этому показателю эффективнее многих известных алгоритмов расчета ЦС.

Разработан новый алгоритм БШ-СПСС над 0 и Я, позволяющий выполнять действительное ДПФ с наименьшими вычислительными затратами полностью в арифметике действительных чисел К . Поскольку вычислительная сложность БШ-СПСС над 0 и & идентична вычислительной сложности АДБИ-РО (3), сравнительный анализ АДБПФ-РО с другими известными алгоритмами действительного Б® полностью перекосится на Б1И-СП0С над С) н Я . Сопоставление алгоритма БМ-СДОС над О,Я и АДБШ-РО по другим критериям эффективности показывает, что они имеют примерно равную точность вычислений, однако ДЦБПФ-РО имеет более регулярную структуру, чем БПФ-СПОС над 0 иЙ , что приводит к более высокому быстродействию АДБ1Й--Р0.

Разработан новый алгоритм вычисления двумерного действк -тельного ДПФ полностью в действительной арифметике на основе ПС и СПОС над , позволивший существенно уменьшить общее число операций умножения и сложения по сравнению с традиционным построчно-столбцовым алгоритмом Б1Й, исходным алгоритмом Нуссбаумера и предложенньы АОПП-Д. Его вычислительные затраты определяются соотношениями:

Отмечено, что обратное одно-, двумерное ДПФ действительных последовательностей целесообразно выполнять на основе разработанных алгоритмоь вычисления одно-, двумерного действительного ДГЙ.

Синтезирован ноеый эффективный алгоритм вычисления двумерной действительной ЦС на основе процедур китайской теоремы об остатках (КТО), ПП и СПОС над Й , экратинпий общее число арифметических операций по сравнению с алгоритмом на основе построчно-столбцового Б® Рейдера-Бреннера и исходньм алгоритмом Нуссбаумера, базирующимся только на ПП. Показано, что для синтезированного алгоритма М^-^Ч&^И-б/бНО/ь,

Разработаны эффективные подходы к вычислению действительных ДС в арифметике с фиксированной запятой на основе алгоритмов сплетения БЛФ-СПОС над й и Р. с ТЧЛ Гаусса или ТЧП Ферма с БГЙ-СПОС над 3 и R, позволяющие дополнительно сократить число умножений за счет использования более простых операций сдвига и сложения чисел. В работе предложена также транспонированная форма гибридного алгоритма Власенко-Лаппа вычисления одномерного действи -тельного ДПФ, которая обеспечивает однократное применение разработанного алгоритма выполнения двумерного действительного ДПФ

на основе ПП и СНОС над (I и позволяет по сравнении с алгоритмом БП5-СП0С над (3 и К уменьшить число умножений, но за счет значительного увеличения числа сложений.

Разработан новый алгоритм расчета двумерной действительной ЦС коротких длин 16x16 с параллельной структурой , основанный на быстрых процедурах КТО, ПП и модифицированных ПП. Предложенный алгоритм требует для реализации меньшего числа умножений и сложений по сравнению с алгоритмами Агарвала-Кули, НуссСаумета и на основе ПП и СЛОС над й .

Синтезированы алгоритмы вычисления действительных Д1Й и ЦС на основе процедур быстрого СПОС над полями рациональных О , гауссовских С}[1] и комплексных С чисел. Они явились результатом сочетания двух разработанных методов — быстрого СПОС в различных полях и ДЦБПФ-РО. Как следствие этого, предложенные алгоритмы расчета действительного одно-, двумерного Д1Й, ЦЧДГЙ, КЦС и ЦС имеют регулярную структуру и наименьшие вычислительные затраты, эквивалентные вычислительным затратам алгоритмов на основе СПОС над СЗ, Я , ЯМ/и*"? 1) (например, алгоритмы действительного НЧБП5--Р0 и быстрого СПОС над К имеют совпадающее число арифметических операций). В работе приведены граф-схемы разработанных алгоритмов.

В пятой главе показано применеие теории Км- стационарных-систем и разработанных алгоритмов вычисления многомерных ДГЙ и дискретных сверток на основе процедур быстрого СПОС в различных полях для решения проблем идентификации и моделирования стационарных НДС, а также синтеза новых классов квазкетационарных НДС с использованием функциональных радов Винера-Вольтерра.

Отмечено, что методом, дающим полное решение задач идентификации и моделирования НДС, является подход, использующий ря^ы из ортогональных функционалов Винера-Всльтерра. Показана необходимость использования модели циклостационарюй НДС в задачах анализа и синтеза стационарных дискретных ВДС посредством цифровых ЭВМ; получен вид дискретных ортогональных функционалов Винера-Еольтерра на конечных временных интервалах относительно случайной последовательности {х^ с гауссовским законом распределения, представляющих собой многомерные разделимые ЦС.

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

посредством их ДЖг-образов.

Доказано, что использование разработанных алгоритмов БПФ--СЯХ (АДБПФ-РО) и Ш на этапах идентификации и генерирования фоцессов с выхода циклостационарной НДС позволило существенно сократить вычислительные затраты по сравнению с взаимокорреляционным методом Ли-Шетцена и спектральным Френча-Бутца: на этапе идентификации число действительных арифметических операций уменьшилось примерно в 2/3* N1- ! раз по сравнению с методом Ли--Шетцена; на этапе генерирования сократилось в 2Ь раз число умножений и в раз число сложений по сравнению с методом Френча--Бутца; при этом общее число ЦС, необходимых для компьютерного моделирования циклостационарной НДС, составляет лишь 0(1^и*1) , что эквиналентно выполнению действительных умножений

и 0(5Ы1"^^) действительных сложений ( N— длина временного интервала, и — порядок разложения в ряде Винера-Вольтерра).

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

В работе отмечено, что каноническое описание динамической системы достигается, если ее анализ проводится в базисе тестирующих воздействий: для стационарных ДЦС — гармонические функции, для Км- стационарных ДЦС — собственные функции, для стационарных НДС — случайные стационарные функции, для К„- стационарных .ВДС — случайные Кн- стационарные функции. Этот результат является отражением принципа инвариантности в задачах идентификации динамических систем.

Метод полиномиальной алгебры, применяемый в работе, позволил

описать на единой основе модели дискретных динамических систем в виде полиномиальных сравнений: для циклостационарной ДДС это — полиномиальное сравнение по модулю кругового полинока 2M-i , для К^- стационарной ДДС — полиномиальное сражение (186) по модулю произвольного полинома ty(2), для циклостационарной НДС — многомерное полиномиальное срагаение по модулям кругового полинома, для К- стационарной НДС — многомерное полиномиальное сравнение (20) по модулям произвольного полинома.

В шестой главе показано, что синтез дискретных систем управления возможен на основе теории KN- стационарных ДЦС, поскольку минимальное решение полиномиальных уравнений эквивалентно решению обобщенных К- сверток.

Получено полиномиальное уравнение причинной Км- стационарной ДДС в виде:

HU)XU)^(a)p(3)=Y(2), (21)

где с^(з) — характеристический полином оператора К- сдвига, Н(2),Х(2) и Y (г) — полиномиальное представление соответственно импульсной переходной характеристики , входного {х^ и выходного процессов KN- стационарной ДЦС. Вследствие взаимозаменяемости полиномовН(2)и XCÓ^CÍи р(2) в (21), полином р(2) имеет смысл полинома-модуля. Для решения (21) относительно неизвестных "^(2) и р(2) необходимо, чтобы выполнялось условие взаимной простоты полиномовН(Х) и т.е. НСД (Н(2), q(2))=i . Доказано предложение, согласно которому условие взаимной простоты заданных полиномов Н(2) и в полиномиальном уравнении (21) эквивалентно условию линейной независимости векторов-строк оператора KN--стационарной ДЦС: ^или условию практической управляемости Калмана).

Предложена модель квазистационарних систем посредством оптимизации причинных К- стационарных ДЦС. Показано, что минимальное решение правильного полиномиального уравнения заданного вида приводит к наибольшей близости полиномов <^,(2) и Хн-1 , что эквивалентно выполнению временного условия квазистационарности (16а).

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

да Й(ЗЕ)-А<2)№ов1яи), где Гп.а*,<}пе\К<1»ёЯ),«1ед.АСй-и и

равна:

При этом верхняя граница минимального числа умножений = 2- получена относительно ненормированного полинома-модуля 0,(2). »

Получен эффективный алгоритм вычисления полиномиальных вычетов с использованием методики, изложенной в доказательстве леммы, и ускоргнных алгоритмов действительного Б1Й — АДБП$-Р0 и БПФ -СПОС над 0 и Я ; показано, что предложенный алгоритм в N раз эффективнее традиционного алгоритма Кнута.

Доказано, что теоретическое минимальное число умножений для вычисления обобщенной Км- свертки — произведения (186) полиномов но модулю произвольного полинома <^,(2), коэффициенты которого не принадлежат й — полю констант в смысле Винограда, в 3 раза больше аналогичной оценки для случая, когда коэффициенты полинома <^,(2) принадлежат полю констант Фс^, и составляет [А.пап(Ы)-6Ы-5. Тем самым обобщен метод Винограда о минимальных оценках произведения полиномов по модулю полинома на случай полинома-модуля произвольного вида. По методу, предложенному в данной теореме, получены алгоритмы расчета коротких обобщенных К- сверток (N610) с минимальным числом арифметических операций О (6М), а также алгоритмы вычисления обобщенных К^ сверток больших длин на основе процедур действительного БШ-СПОС посредством следующего числа действительных умножений и сложений:

Доказано существование а. оритма быстрого преобразования Вандермонда (БПВ) для расчета (17а, б) с теоретически возможной мультипликативной оценкой 0 ) и реальной 0 ),

полученной в результате сочетания метода дихотомии и разработанного метода приведения полиномов. Показано преимущество предложенного алгоритма БПВ по сравнению с процедурой Ньютона и схемой Горнера, а также с алгоритмом Ахо-Хопкрофта-Ульмана. Показано, что на больших длинах N предложенный алгоритм БПВ значительно эффективнее М -кратного использования схемы Горнера.

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

ления (синтез оптимальных экстраполяторов, фильтров). Таким образом, разработанные алгоритмы обобщенной K,j- свертки дат? возможность синтезировать быстрые алгоритмы управления дискретнши динамическими объектами.

В седьмой главе на основе предложенных спектральных моделей и разработанных алгоритмов создано программное обеспечение (ПО) автоматизированных цифровых систем обработки информации и управления. Система обработки и идентификации фотографических изображений (СС®И) включает устройство ввода фотоизображений, управляющую ЭВМ на базе CM-I420 (или IBM РС/АТ-286) и устройство вывода (хранения) цифровых изображений. В работе приведена структура и состав технических средств СОИФИ. К основным алгоритмам функционирования СО®Я относятся: цифровая фильтрация (низкочастотная, высокочастотная,полосовая, инверсная, согласованная) изображений, сжатие информации (данных), идентификация изображений. Функционирование СОИФИ основано на спектральных представлениях двумерных сигналов. Так, в основу процедур цифровой фильтрации, сжатая и едентификации изображений положены разработанные алгоритмы вычисления двумерных действительных ДП5 и ЦС на основе СПОС в различных полях — рациональном, действительном, полиномиальном. Это позволило в 2 раза увеличить быстродействие и на 1-2 порядка снизить вычислительную погрешность спектральных преобразований по сравнению с традиционными алгоритмами построчно-столбцового БПФ.

Предложена организация ПО СОИФИ "РОТОК"» включапцего сегмент-программы основных режимов функционирования СОИФИ —■ цифровой фильтрации, цифрового спектрального анализа, сжатия данных, идентификации изображений по их спектральным признакам. Программная реализация разработанных фильтров нижних и верхних пространственных частот позволила сократить время цифровой фильтрации более чем в 2 раза и улучшить визуальное качество цифровых изображений посредством подавления шумов, вцделения или сглаживания границ и контуров. В работе приведены примеры фильтрации цифровых фотоизображений . Программная реализация процедур сжатия данных дала возможность в 2-4 раза сократить объем хранимой или передаваемой информации на основе спектрального представления цифровых изображений. Включение в ПО СОИФИ программных разработок, реализующих двумерные обобщенные К,- свертки и двумерное БИВ, позволяет совершенствовать СОИФИ.

Алгоритмическое и программное обеспечение режимов функциони-

рования СОШИ внедрено в НИР по теме "Поток" (раздел "Анализ") и НИОКР АСОВИ, которые выполнялись на основе договоров ¡ТГК АН БССР с н.п.о. ''Точные приборы" (г. Москва) и н.п.о. "Геофизика" (г. Москва). Комплекс программ, реализующих ускоренные процедуры расчета двумерного ДПФ на основе метода СПОС в различных полях, внедрен в подсистему вторичной обработки радиоастрономических изображений в Институте прикладной астрономии АН СССР (г.Ленинград ).

Результаты исследований автора, направленных на разработку быстрых алгоритмов и соответствующих программ вычисления двумерных Д® и сверток на основе метода собственных преобразований в различных полях вошли состажой частью в работу "Создание и практическое применение средств цифровой обработки сигналов и изображений", удостоенную премии Ленинского комсомола Белоруссии в об- . ласти науки и техники 1990 года.

Функционирование систем управления динамическими испытаниями (СУДИ) объектов также основано на спектральных предствлениях процессов. Замкнутая цифровая СУДИ включает объект испытаний, устройство связи с объектом и управляющую ЭВМ. В работе приведена структура и состав технических средств СУДИ. К основным алгоритмам функционирования СУДИ относятся: идентификация характеристик объекта, спектральный анализ информационных потоков с выходов объекта, управление и генерирование выходных воздействий. Режимы идентификации, спектрального анализа и генерирования базируются на многократном использовании алгоритмов БПФ, на реализацию которых расходуется примерно 2/3 всего времени работы СУДИ. На основе разработанных алгоритмов — АДБМ-РО, АЭБГЦ-РО, БП5-СП0С — создано программное обеспечение режимов спектрального анализа и генерирования случайных процессов. В диссертации экспериментально доказано, что предложенные алгоритмы для всех размерностей обладает максимальным быстродействием среди традиционно используемых алгоритмов действительного БПФ Кули-Тьюки, Рейдера-Бреннера, Берглан-да и, как следствие этого, позволяют расширить в 1,5-2 раза, полосу частот обрабатываемого сигнала, имеьт наименьшую вычислительную погрешность. Комплекс программ, реализующих процедуры спектрального анализа и генерирования случайных процессов на основе разработанных алгоритмов использован при создании ПО автоматизированных СУДИ автомобильных конструкций в НТЦ п.о. "АвтоВАЗ" (г. Тольятти). Он позволил в 1,5-2 раза сократить время вычисления

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

Дальнейшее совершенствование ПО СУДИ связано с реализацией режимов функционирования СУДИ (спектрального анализа, генерирования, идентификации и управления) для моделирования нестационарных и нелинейных объектов. В этой связи весьма перспективными являются процедуры спектрального анализа и генерирования Кн-ста-ционарных случайных процессов в биортогональных базисах СПОС, а также ускоренные алгоритмы многомерного спектрального анализа и генерирования стационарных случайных полей.

Расширение возможностей ГЮ СУДИ за счет моделирования нестационарных и нелинейных объектов потребовало дополнительных вычислительных затрат, в связи с чем рассмотрен вариант многопроцессорной СУДИ на базе мин и-ЭВМ на линии с быстродействующим периферийным процессором (БПП) типа ''Электроника МТ-70". Показано, что при сохранении основных режимов функционирования и самой структуры ПО СУДИ функции между вычислительными средствами в многопроцессорной СУДИ распределены таким образом, что на БПП возложена реализация режимов спектрального анализа и генерирования случайных процессов. Разработанная при участии автора многопроцессорная СУДИ также.внедрена в УГК п.о. "АвтоВАЗ".

Результаты исследований автора по разработке к совершенствованию СУДИ вошли составной частью в работу 'Тазработка и внедрение комплекса алгоритмических и программно-технических средств автоматизации испытаний изделий в машиностроении", удостоенную премии Минского обкома комсомола и Минского областного правления Союза научных и инженерных обществ СССР, в области науки и техники 1987 года.

Часто во многих информационно-вычислительных системах (в том числе, в СУДИ) требуется реализовать режим рабсты в реальном масштабе времени. Существенным компонентом алгоритмического и программного обеспечения таких систем являются быстрые алгоритмы и программы цифрового спектрального анализа, применение которых в многоканальной информационно-вычислительной системе контроля и идентификации(ИЕСКИ) сигналов описано в приложении к даньой главе. Программные модули, выполнявшие ускоренные процедуры спектральной обработки сигналов в реальном масштабе времени на основе синтезированных АДБШ-РО и АЭБП2-Р0, внедрены в состав ПО ИВСКИ в НИИ "Алгоритм" н.п.о. "Кибернетика" АН УзССР (г. Ташкент).

Программы, реализующие синтезированные авторш новые алгоритмы вычисления одно- и двумерного действительного ДПФ и ДО, приняты в Государственный фонд алгоритмов и программ СССР. Предложенные алгоритмы также приняты к использованию в СКГБ и.о. "Интеграл" (г. Минск) для разработка архитектуры и функциональных схем основных блоков ряда микросхем для систем цифровой обработки сигналов и изображений.

В заключении сформулированы основные результаты и выводы по диссертационной работе.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ I. Развитие и применение аппарата полиномиальной алгебры для задач спектрального представления дискретных сигналов на конечных интервалах.

2. Разработка и исследование новой модели нестационарных линейных динамических систем —Кн-стационарных ЛДС.

3. Развитие и обобщение основных положений спектрального представления К- стационарных ЛДС и процессов в дискретных би -

ортогональных базисах собственных функций.

4. Построение в русле теории К- стационарных систем модели квазистационарных ЛДС и случайных процессов, обобщающей традиционную иодель стационарных ЛДС и случайных процессов, а также разработка на основе функционального разложения Винера-Вольтерра модели квазистациоьарных НДС.

5. Открытие и обоснование принципа вычислительного дуализма между стационарными и К- стационарными ЛДС.

6. Разработка нового метода собственны:: преобразований в различных полях для синтеза эффективных алгоритмов спектрально-корреляционной обработки цифровых сигналов.

7. Разработка нового метода синтеза неизбыточных алгоритмов действительного быстрого преобразования Фурье (АДБП5) одномерных и двумерных последовательностей.

8. Синтез эффективных (по числу ари(|ыетических- операций, быстродействию, точности, структуре) алгоритмов вычисления одномерного и двумерного действительного ДП2 i; ЦС на основе разра -

ботаяных методов собственных преобразований в различных полях и АДБПФ, позволяющих сократить общее число арифметических операций в 2-3 раза, повысить быстродействие в 1,5-2 раза, снизить погрешность вычислений на 1-2 порядка для больших размерностей обрабатываемых массивов.

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

10. Разработка программного обеспечения режимов спектрального анализа, фильтрации, генерирования информационных потоков на основе предложенных алгоритмов для автоматизированных цифровых систем обработки и идентификации ? ^тоизображений, систем управления динамическими испытаниями объектов и информационно-вычислительных с..стем реального времени на предприятиях министерства общего машиностроения, автомобильной и электронной промышленности (н.п.о.

"Точные приборы", г. Москва; НТЦ п.о. "АвтоВАЗ", г. Тольятти; СКТБ п.о. "Интеграл", г. Минск), в научно-исследовательских учреждениях (НИИ "Алгоритм" н.п.о. "Кибернетика" АН УзССР, г. Ташкент; Институт прикладной астрономии АН СССР, г. Ленинград). -

Все вьшесказанное позволяет сделать вывод о том, что в диссертационной работе осуществлена разр? "отка новых теоретических . положений. совскупиось которых можно квалифицировать как новое крупное достижение в развитии теории, методов и алгоритмов анализа и генерирования сигналов для задач моделирования динамических объектов в автоматизированных цифровых .системах обработки информации и управления.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Осношые результаты диссертации изложены в следующих работах:

1. Крот A.M. Дискретные модели динамических систем на основе полиномиальной алгебры. — Мн.гНавука } тэхн!ка,1990.- 312 с.

2. Крот A.M. О классе дискретных квазистационарных линейных динамических систем //Доклады АН СССР. - 1990. - т.313, №6. -С. I376-1380.

3. Крот A.M. О мультипликативной сложности билинейных форм, для которых преобразование Вандермонда является собственны« // Доклады АН СССР. - 1990. - т. 314, № 6. - С. I3I2-I3I5.

4. Крот A.M. Об одном классе операторов обобщенного сдвига в

теории сигналов и систем. //Радиотехника и электроника. - 1986. -T.3I, № 8. - С. 1563-1570.

5. Крот A.M., Минервина Е.Б. Синтез алгоритмов дискретного теобразования Фурье для действительных последовательностей на основе полиномиальной алгебры //Радиотехника и электроника. -1987. - т. 32, № 6. — С. 1217-1229.

С. Крот A.M. Анализ линейных "динамических систем на основе полиномиальных преобразований числовых последовательностей. // Радиотехника и электроника. - 1988-т.33, № 7. - С. 1453-1466.

7. Крот A.M. Об одном классе дискретных случайных процессов, нестационарных относительно оператора обобщенного сдвига //Радиотехника и электроника..- 1988. - т. 33, № 12. - С. 2515-2523.

8. Крот A.M. Спектральный анализ класса нестационарных случайте процессов в дискретных биортогональных базисах. //Радиотехника и электроника. - 1989. - т. 34, № I. -С. 59-68.

9. Крот A.M., Минервина Е.Б. Алгоритмы быстрого преобразования Фурье для действительных и эрыитово-симметричных последовательностей //Радиотехника и электроника. - 1909. - т. 34, № 2.

- С. 369-376.

10. Крот А.М: Метод собственных преобразований в различных полях для вычисления циклических сверток и дискретного преобразования Фурье. /Дурнал вычислительной математики и математической физики. - 1989. - т. 29, № 5. - С. 675-692.

11. Крот A.M., Минервина Е.Б. Синтез алгоритмов БЯ5 по расщепляемому основанию для действительных и эрмитово-симметричных последовательностей. //Изв. ВУЗов СССР. Радиоэлектроника. -1989.

- т.32, № 12. - С. 12-17.

12. Крот A.M. Синтез быстрых алгоритмов собственных преобразований дискретных сверток в рациональном и действительном полях. //Радиотехника и электроника. - I990.-T. 35, № 2» - С.372-381.

13. Крот A.M. Единый подход к вычислению сверток и дискретного преобразования Фурье на основе собственных преобразований в рациональном и действительном полях. //Радиотехника и электрони-ku..-1990.-T. 35, > 4. - С. 805-815.

14. Крот A.M. О вычислительной сложности обобщенных Кд- сверток и алгоритма быстрого преобразования Вандермонда. /Дурнал вычислительной математики и математической физики. - 1990. - т.30,

№ 11. - С. 1625-1637.

15. Крот A.M.,Минервина Е.Б. Спектральное представление после-

довательностей на поле"классов вычетов. //Электронное моделирование. - I99I.-T. 13, » I. - С. 9-13.

16. Крот A.M. Эффективный алгоритм дискретного £урье-преобразования на основе цифровых"сверток //Изв. АН БССР, сер.физ.-техн. наук. - 1984. - № 3. - С. 105-113.

17. Чеголин П.М., Крот А,М. Развитие теоретико-полиномиальных преобразований для систем переработки экспериментальной информации. //Изв. АН БССР, сер физ.-техн. наук. - 1985. - № 2. - C.I04-I09.

18. Крот A.M., М1нерв!на А.Б. 1дэнтьф!кацыя нел!нейнай ды-нам1чнай с!стэмы I генерыраванне выхадных працзсау на основе па-л!нам!альных пераутварэнняу. //Весц! АН БССР, сер.ф!з.-тэхн. навук. - 1987.-» 4. - С. 82-88.

19. Чеголин Ü.M., Крот A.M., Абдурахманов Б.Х. Параллельное вычисление двумерной циклической свертки на основе быстрых пг ч-номиальных преобразований. //Изв. АН УзССР, сер. техн. наук. -1990. - № I. - С. 3-8.

20. Крот A.M. Метод теоретико-полиномиальных преобразований при построении дискретных преобразований над конечнши вычислительными структурами. //В кн.: Автоматизация проектирования в машиностроении. - Минск: Ин-т техн. кибернетики АН БССР, 1985-«.-С. 98-106. ■ .

21. Крот A.M. Применение операторов обобщенного сдвига для моделирования нестационарных процессов и систем. //В кн.: Алгоритмы и программно-аппаратурные средства- в системах испытания объектов. - Минск: Ин-т техн. кибернетики АН БССР, 1985. -С. 5-15.

22. Чеголин П.М., Крот A.M. Теоретико-полиномиальные функции и преобразования. //В сб.: Цифровые методы в управлении, радиолокации и связи. - Свердловск: УПИ им. С.М. Кирова, 1986. -С. 16-27.

23. Крот A.M. О вычислительной сложности билинейных форм, описывающих обобщенные дискретные свертки. //В сб.: Автоматизация испытаний технических объектов. - Минск: Ин-т техн. кибернетики АН БССР, Ivö9. - С.13-32.

24. Крот А.М.,Минервина Е.Б. Быстрьв алгоритмы гармонического анализа одномерных и двумерных действительных последовательностей. - Минск, 1988.-28 с. (Препринт/Мн-т техн. кибернетики

АН БССР: № 25).

25. Крот A.M.,Абдурахманов Б.Х. Эффективные алгоритмы приве-

деняя полиномов ■ быстрые процедуры дискретного преобразования Фурье. - Минск, £990. - 36 с. (Препринт/ Иь-т техн. кибернетики АН БССР, * 5).

26. Крот A.M. Синтез алгоритмов оптимального дискретного управления динамическими объектами на основа полиномиальных уравнена» и обобщенных KN- сверток» - Минск, 1990. - 46 с. (Препринт/ 'Лн-т техн. кибернетики АН БС>Р, №31).

27. Крот A.M., Абдурахманов Б.Х. Вычисление двумерной обобщенной KN- свертки с минимальной мультипликативной сложностью.

- Минск, 1991. - 28 с. (Препринт / Ин-т техн. кибернетики АН БССР, * 2).

28. Крот A.M., Чеголин ПоЫ. Теоретико-полиномиальные преобразования и алгоритмы для формирования спектральных коэффициентов. //Статистические измерения и применение микромавинных средств в измерениях: Тез.докл. П Всесоюзн. гшгоз.-Л.: 1984. ч.Ш. - С.33-36.

29. Крот A.M., Минервина Е.Б. Спектральный анализ и моделирование последовательностей на поле классов вычетов.//Методы и микроэлектронные средства цифрового преобразования и обработки сигналов: Тез.докл. научно-техн.Еонф. - Рига, 1986. - т.1<> - С. 185-188.

30. Krot A.M. Computation of the generalized tjj-convoluti-ons and the fast Vandermonde transform vith a minimal multiplicative complexity. //Proc. Latvian Signal Processing International conference. - Riga, 1990. - V.1. - P. 128-132.

31. trot A.M., Abdurakhmanov B.H. Computation plans of polynomial values for algorithms synthesis of discrete Fourier transform of short length. //Proc. Latvian Signal Processing International conference. - Riga, 199C. - V.1. - P. 133-137.

Подпасаво к печати 24.0€oI99I.

Формат 60x84 I/I60 Бумага типографское Обьом 2 печ.л. Tupas 100 БКЗо Заказ 1940 Беспяатпо,

Отпечатано не рогапрввтэ Института технической кибернетякя АН БССР. 220012, Миасв, ул. Cyprasosa,6.