Введение к работе
Актуальность. Научно-технический прогресс, возрастающая сложность и интенсификация деятельности человека в различных областях предъявляют новые качественные и количественные требования к сбору, хранению и обработке информации. Градационные информационные технологии обеспечивают лишь ограниченный рост производительности труда. Выход из этого положения специалистами видится в создании новых информационных технологий, базирующихся на широком использовании достижений вычислительной техника, математических и прикладных научных дисциплин.
Характерной особенностью развития современных информационных технологий является резкое увеличениз количества задач, решаемых с помощью цифровых методов. Современные цифровые системы сбора и обрзботки информации используются автономно или входят в качестве подсистем в различные системы контроля и управления, моделирования и проектирования, автоматизации научных исследований, технической и медицинской диагностики и т.д. Весьма высока роль цифровых методов в сетях интегрального обслуживания.
Первостепенную роль в этих системах выполняют' моделирование и обработка сигналов, доминирующее положение в которых занимают методы цифровой обработки сигналов (ЦОС). Неоспоримые достоинства ЦОС - точность и гибкость (программируемость) обработки делают это направление развития средств обработки сигналов самым перспективным для большинства приложений.
Многие приложения ЦОС требуют создания быстродействующих и 1 экономичных средств обработки сигналов. Это связано с усложнением решаемых задач, повышением требований к результатам обработки и расширяющимся применением. систем ЦОС реального времени.
Основными путями повышения производительности средств ЦОС являются следующие: технологический, архитектурный и алгоритмический. Наиболее эффективный путь - алгоритмический, ориентированный на использование оптимальных или близких к ним алгоритмов. В качестве .критериев оптимальности часто используются такие характеристики алгоритмов ЦОС, как точность, быстродействие и машинная память. Установлено, что для некоторых классов задач ЦОС создание тзкизс алгоритмов может дать тот же эффект, что и использование новой элементной базы и новых поколений ЭВМ.
В ЦОС весьма интенсивные исследования проводятся в области создания алгоритмов оптимальных по быстродействию или близких к ним ( быстрых алгоритмов, алгоритмов с сокращённой, вычислительной сложностью). В основе большинства таких алгоритмов ЦОС лежат быстрые спектральные преобразования, т.е. разработка быстродействующих средств обработки сигналов тесно связана с обобщенной спектральной теорией. Спектральный подход является весьма эффективным для ускорения решения многих вадач ЦОС.
При решении задач ЦОС спектральными методами своей общностью выделяется метод дискретных ортогональных преобразований (ДОП), который предполагает представление и обработку сигналов в дискретном ортогональном базисе (ДОБ). Широкое применение ДОП в ЦОС связано прежде всего с разработкой быстродействующих методов вычисления бысгрык ДОП (ЕДОП) и созданием на их основе программно-аппаратных средств, зачастую, позволяющее обеспечивать функционирование системы ЦОС в реальном масштабе времени.
Теория ДОП. достигла к настоящему времени высокого уровня развития. Различные, .теоретические и практические вопросы этой теории рассматривались в большом количестве работ учёных зарубежных стран и стран СНГ. Весьма еысок вклад в развитие теории и практики ДОП учёных стран СНГ, среда которых отметим Агаяна С.С., Ефимова А.В., Задирака В.К., Крота А.А.,. Кухарева Г.А., Лабунца В.Г., Садыхова Р.Х., Солодовникова А.И., Трахтмана A.M., Чеголи-на П.М. и Ярославского Л.П. Среди ученых Узбекистана -известны прикладными работами в этой области Абдуллаев Д.А. и Мусаев М.М.'
Достижения в области теории ДОП хотя и составляют значительную часть обобщенной спектральной теории, однако немаловажен кслад в эту теорию достижений в области построения и . изучения косоугольных дискретных базисов. Практическая важность этих исследований связана с тем, что при решении отдельных задач ЦОС косоугольные даскре.ныа базисы оказываются весьма эффективными.
Однако ряд результатов обобщённой спектральной теории не занимает должного места в . ЦОС. Этому есть несколько причин, среди которых выделяют следующие: отсутствие алгоритмов БДОП для ряда известных базисов, широкое использование для решения задач ЦОС дискретных преобразований многофункционального харзктера (дискретного преобразования Фурье, преобразований Уолша и т.д.).
Последняя причина ведёт к тому, что часто пренебрегают возможностью построения тоеых или модификации известных ДОП и наделения их специфическими свойствами, необходимыми для эффективного решения конкретной задачи. ї- діє ДОП относят к классу преобразований по специальным системам базисных функций.
В теории ДОЛ предложено тожество специальных ДОБ. Однако в теоретическом плане класс специальных дискретных базисов является недостаточно изученным, исключение составляют отдельные представители класса. Как правило, многие специальные ДОБ рассматриваются Фрагментарно, изолированно друг от друга, бел должного выявления существующих их взаимосвязей между собой и базисами других классов. Поэтому возникает необходимость развития методологии синтеза специальных ДОП, обобщения результатов исследования отдельных типов ДОБ и трактовки их многих свойств на основе общего для ют математического аппарата.
Во многих приложениях широкое гфименение находят цифроори-ентированнне.ДОБ. Наиболее популярны в ЦОС дискретные базисы Уолша, Хаара и некоторые их обобщения. Однако большинство этих ДОБ определено при размерности конечного интервала, равной целой степени двойки (tf=2nJ. Это весьма' жёсткое ограничение на размерность обрабатываемого сигнала диктует параметры алгоритмов и средств ЦОС, реализуемых на основе базисов рассматриваемого типа.- Построение наиболее рациональных алгоритмов и устройств обработки сигналов требует иного подхода: приложения ЦОС должны диктовать выбор наиболее подходящих порядков преобразований и типа ДОП. При' этом весьма важной является ориентированность ал горитмов на эффективную реализацию средствами недвоичной логики. Особый интерес к мультиуровневой элементной базе, связан с тем, что создание структур средств ВТ, оптимальных по совокупности технических параметров, возможно лишь с использованием многозначного представления информации.
В связи с изложенным, построение новых' специальных систем базисных функций и обобщения ряда традиционных Д05, в .. первую очередь Оазисов Уолша и Хаара, в рамках единого математического аппарата является актуальной задачей. Практическая значимость синтезируемых ДОБ в ЦОС во многом будет определяться 18ЯИЧИЄМ алгоритмов БДОП и возможностью построения простых и экономичных
6 средств их реализации- Важное прикладное значение имеют также исследования, направленные.на расширение областей практического применения специальных ДОП в.задачах ЦОС, особенно, при синтезе алгоритмов моделирования и обработки сигналов, ориентированных на эффективную реализацию'средствами г-ичной (г>2) арифметики.
Диссертационная работа направлена на решение указанных проблем. Актуальность теки диссертации подтверждается тем, что она выполнена в раусах ряда НИР по решению важнейших комплексов проблем Республики Узбекистан, в том числе выполненных в соответствии с программами фундаментальных исследований Академии наук Республики Узбекистан: "Математические методы моделирования и управления в народном хозяйстве на основе новых поколений вычислительной техники" и "Исследования в области кибернетики, информатики, алгоритмизации, математического моделирования и автоматизации управления".
Цели и задачи исследогчшя. Основными целями диссертационной работы являются:
-
развитие теоретических исследований по синтезу и анализу дискретных преобразований в ортогональных и косоугольных обобщённых базисах;
-
разработка методов, алгоритмов и іфоірзммно-аппаратннх средств ЦОС на основе дискретных преобразований.
Достижение указанных целей исследования составляет решение научной проблемы по развитию теории дискретных преобразований и их приложений к решению задач ЦОС.
Поставленные цели определили основные задачи исследования:
-
разработка методологии построения обобщённых ортогональній базисов кусочно-полиномиалькых фуакций (КШ) и обобщённых дискретных систем Радемахера и Уо'лша;
-
исследования свойств синтезированных систем да .фетных функций и преобразований по ним;
-
создание алгоритмов БДОП в синтезированных ортогональных базисах, а такяе структур .спецпроцессоров быстрых' преобразований;
-
разработка математического гшарата полиномиально-полных спектрально-све*рточннх преобразований дискретных сигналов;
-
разработка методов и алгоритмов линейного и устойчивого оценивания полирошал/ных моделей цифровых сигналов;
-
анализ применений различиях ДОП в задаче сжатия стохастических дискретных сигналов;
-
разрзо*отка методов, алгоритмов и средств ЦОС;
-
разработка «алгоритмического обеспечения задач цифровой обработки сейсмических сигналов.
В большинстве случаев поставленные задачи решаются в одномерной и двумерной постановках. Полученные результаты очевидном образом обобщаются на многомерный случай.
Объекты исследования. Объектами исследования являются методы построения дискретных систем базисных функций и факторизации их матриц преобразований; методы гналитических исследований свойств ДОБ; методы, алгоритмы и вычислительные структуры решения задач ЦОС.
Методы исследования. Методологическую основу теоретической части работы составляют основные положения и методы ЦОС, теории ДОП, матричной алгебры, теории сложности вычислений, регрессионного анализа, метода проектирования цифровых вычислительных устройств. Экспериментальные исследования проведены с использованием математического моделирования на ЭВМ.
Научная ковпзкз. Научная новизна исследования заключается в том, что п пбм впервые развиты теоретические и прикладные поло-гения, дэяяда возможность синтеза и анализа новых ортогональных и косоугольных обобщенных дискретных базисов и создания методов, алгоритмов и средств ЦОС нз осносе дискретных преобразования.
Основными научными результатами, составляющими новизну исследования, являются следующие:
-
классификация действительнозначных ДОБ на классы моноразностных и полиразностннх базисов и определение ряда параметров и характеристик моноразностных ба-гисов;
-
определение новых классов специальных ДОБ (обобщённы:; базисов КПФ vi Хессенбергз ) и их семейств;
-
разработка методов построения базисов трЗх семейств обобщенных базисов КПФ;
-
построение обобщённой дискретной системы Радемахера и косоугольного обобщения системы дискретных функций Уолша;
-
Изучение СВОЙСТВ СИНТеЗИрОВаННЫХ ДИСКреТЯЫХ боЗИСОВ к
преобразований; в них;
-
создание алгоритмов БДОП в синтезированных оазисах, а также струят:'.} спецпроцессоров быстрых преобразований, защищенных авторскими свидетельствами на изобретения;
-
построение математического аппарата нового вада дискретных преобразований - полиномиально-полных спектрально-сЕёрточных преобразований;
-
разработка и изучение сложности новых методов и алгоритмов линейного и устойчивого параметрического оценивания полиномиальных моделей цифровых сигналов на основе дискретных преобразований;
-
разработка методов и алгоритмов ЦОС (сжатия данных, выделения моментных признаков и нерекурсивной фильтрации) на основе дискретных преобразований;
10) разработка алгоритмов цифровой обработки сейсмических
сигналов.
Практическая ценность Полученные в диссертационной работе результаты расширяют теорию дискретных преобразований в ортогональных и косоугольных базисах и могут способствовать новым исследованиям в этой области. Прикладные результаты работы могут найти применение в различных областях приложений ЦОС.
Предложенные метода и алгоритмы параметрического оценивания ЕМ ыогут быть использованы рри моделировании сигналов и с;штезэ алгоритмов решения іг^рокого круга задач ЦОС (интерполяции, сглаживания, экстраполяции, дифференцирования, сегментации и т.д.).
Разработанные поточные структуры СП быстрых преобразований позволяет вести обработку дашшх в реальном времени и ыогут использоваться в составе системы ЦОС с аппаратной поддержкой ре-изния задач сжатия, фильтрации- обк<фужения и распознавания сигналов спектральными методами.
Проведённый анализ эффективности ряда ДОП в задачах квази-осратимого СД позволил получить ранжировку исслэдуемых преобразований по объективным показателямсжатия и сформулировать реко-мзндацки по их практическому исгользованию
Разработанные метода, алгоритма и структуры спецпроцессоров огатия данных могут быть использованы при создании средств сжатая информации в-системах сбора, передачи, обработки и хранения цифровых сигналов и изображений различного назначения.
Предложенные методы и алгоритмы выделения моментных признаков могут бить использованы при создании систем распознавания образов различного назначения.
Методы и алгоритмы цифровой обработки сейсмических сигналов могут быть использованы при создании и совершенствовании автоматизированных систем сейсмического контроля, а таксе при решении аналогичных задач в других системах ЦОС.
Практическую ценность имеет разработанный комплекс подпрограмм для решения задач ЦОС, который может быть использован в вычислительных системах для исследований в области ЦОС.
Реализация результатов работы. Диссертационная работа выполнена в рамках ряда НИР по программе фундаментальных исследований АН РУз, проведённых в НИИ "Алгоритм", Институте Кибернетики и НИИ Системных Исследований НПО "Кибернетика". Основные положения работы использованы при проведении э'.тас НИР (гос. per. №/*: 01910052722, 01910040523, OI950004I83) И ОКР "Материх-МПО".
Разработанные алгоритмы и программы цифровой обработки сигналов и изображений использованы при создании математического и программного обеспечений автоматизированной системы сейсмического контроля и системы обработки изображений САЙТ.
Аппробация работы. Основные положения и результаты диссертационной работы доложены и обсуждены на более чем 15 Международных, Всесоюзных и Республиканских научно-технических конференциях, симпозиумах и семинарах, в том числе: на Y Всесоюзном симпозиуме "Проблемы создания преобразователей формы информации" (г.Киев ,-1984), на научно-технической конференцій "Разработка систем технического зрения и их применение в промышленности" (г.Устинов, 1986), на XIII Всесоюзной научно-технической конференции "Измерительные информационные системы" (г.Ташкент, 1987), на IY Всесоюзном симпозиуме по вычислительной томография (г.Ташкент, 1989), на конференции "Перспективные информационные технологии в анализе изображений и распознавании образов" (г.Ташкент, 1992), на конференции "Цифровые сети и системы связи Республики Узбекистан" (г.Ташкэнт, 1994), нз Международной конференции "Ияїеллектуализаций систем управления и обработки информации" (г.Ташкент, 1994), на Международной конференции "йзї-ематическое моделирование и вычислительный эксперимент" (г.Ташкент, 1994),
10 на конференции "Проблемы информатики и управления, перспективы их решения". (г.Ташкент, 1996).
Основные положения диссертации обсуждены на Проблемном Совете АН РУз "Математическое моделирование и вычислительный эксперимент" (г.Таикент, 1935), а такае . на семинарах лаборатории "Математическое моделирование" Института Кибернетики НПО "Кибернетика" (г.Ташкент, 1990-1396).
Публикации. По результатам выполненных исследований опубликовано 52 работа, включая 45 статей и тезисов докладов, I препринт, 5 авторских свидетельств на изобретения. Кроме того, материалы работы отражены в 6 отчетах о НИР.
Научные результаты, выносимые на защиту. На защиту выносятся следувдие полоаения:
-
теоретические положения, совокупность которых является вкладом в развитие теории дискретных преобразований (синтез и анализ нових семейств преобразований в ортогональных и косоугольных дискретных базисах, построение аппарата полиномиально--полных спектрально-сБёрточных преобразований);
-
мьтода ЦОС (параметрического оценивания ЕМ, сжатия данных, видалення моментных признаков и цифровой свёртки);
-
вычислительные алгоритмы на основе дискретних преобразований, реализупцие как известные, так и предложенные методы ЦОС;
-
структурные решения спецпроцессоров быстрых преобразований и устройств сжатия данных;
-
алгоритмы цифровой обработки, сейсмических сигналов.
Структура и объбн. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованной литературы из 236 наименований и приложений. Объем работа 236 страниц основного машинописного текста, 19 страниц списка литературы и 45 страниц приложения.
На протяжении ьсей работы автор пользовался добрыми советами и неизменной поддержкой научного консультанта члена-корреспондента АН РУз, доктора физико-математических наук, профессора Абуталиева Ф.Б., за что выражает ему искренни* признательность.
II содггашш работы
ВВЕДШЕЕ. Во введении приведён краткий обзор достижений обобщённой спектральной теории в разработав вопросов, связанных с синтезом и анализом дискретных систем базисных функций, обоснована актуальность проблематики исследований и. определены их цели и задачи. Кратко охарактеризованы научная новизна и практическая ценность полученные результатов и сформулированы основные положения, выносимые на защиту. Приведены сведения об ап-пробации работы и публикациях и краткое содержание по глазам.
