Введение к работе
Актуальность проблемы. При созданий систем управления динамическими объектами и моделирующих комплексов различного назначения возникает необходимость в разработке аппаратурных и алгоритмически-программных средств, выполняющих цифровую обработку информации в режиме реального времени и в векторном режиме. Для их функционирования в ритме эксперимента необходимо создание математического аппарата дискретных преобразований в ортогональных и неортогональных базисах, который дает возможность синтеза высокоэффективных по быстродействию алгоритмов обработки информации, реализуемых как на ЗВМ общего назначения, так и на проблемно-ориентированных комплексах.
С использованием алгоритмических, аппаратурных и программных средств в указанных выше системах решаются задачи фильтрации, сжатия и восстановления сигналов, кодирования и декодирования, тестового контроля, формирования случайных процессов с управляемыми спектральными характеристиками,- основанные на применении прямого и обратного преобразований Фурье, преобразования Лапласа, дифференциально-тейлоровского преобразования и других. Тесная связь преобразований Фурье и Лапласа позволяет с помощью операторных методов описывать поведение системы на языке теории спектров, лежащей в основе частотного подхода к анализу систем.
В последние годы в связи с интенсивным развитием цифровой вычислительной техники, внимание исследователей стали привлекать полные системы прямоугольных-ортогональных функций Уолша, Хаара, Ви-ленкина * Крестенсона, Виленкина - Понтрягина, для которых существуют быстрые вычислительные процедуры. Следует отметить, что спектральная обработка в базисах Уолша, Хаара, комплексных прямоугольных и других функций в наибольшей степени удовлетворяет современной элементной базе и тенденциям ее развития. В своя очередь использование кусочно-постоянных систем функций обусловливает задачу построения инвариантов обобщенного спектрального преобразования, изоморфных аналогичным характеристикам в требуемом базисе, т.е. взаимного отображения спектральных характеристик в различных базисах. Некоторые общие результаты по данному вопросу имеют важное теоретико-прикладное значение. Однако их практическое использование вызывает ряд затруднений, поскольку установленные аналити-
ческие соотношения не доведены до уровня математических моделей, допускающих разработку на их основе методов синтеза алгоритмических, аппаратурных и программных средств. Существующие частные инженерные подходы для синтеза средств взаимных спектральных отображений (ВСО) в дискретных базисах нэ удовлетворяют требованиям практических задач и, как следствие, не могут служить основой для создания специального аппарата рабочего проектирования средств данного назначения. Таким образом, возникла необходимость в совершенствовании математических моделей средств ВСО и уменьшении вычислительной сложности алгоритмов дискретных преобразований.
Решению указанных вше задач посвящены работы ученых: Байды Н.П., Бондаренко В.М., Бутакова Е.А., Васильева В.В., Верланя А.Ф., Гуляева В.А., Додонова А,Г,, Евдокимова В.Ф., Задираки В.К., Каткова А.Ф., Кузьмина И.В., Кухарева Г.А., Лабунца В.Г., Омель-ченко В.А., Пойды В.Н., Цухова Т.Е., Садыхова і.X., Чеголина П.М., Ярмолика В.Н., Ярославского Л.П., Ахмеда Н., Опенгейма А.В., Ра-бинера І.Р., Шафера Р.В. и др., в которых исследования методов ВСО проводятся в двух направлениях, заключающихся в проведении теоретических исследований дискретных преобразований в ортогональных и неортогональных базисах, а также аппаратурной и алгоритмически-программной реализации этих преобразований в различных научно-тех~ нических задачах.
Вместе с тем, анализируя достигнутые результаты, можно отметить, что отсутствие единого подхода к разработке средств ВСО и специальных методов синтеза существенно сказывается на эффективности применения кусочно-постоянных базисов дискретных функций в задачах цифровой обработки сигналов.
В насте азе время цифровую обработку сигналов используют"повсюду, включая радиолокацию, сейсмографию, радиоастрономию и медицинскую электронику. Активно разрабатываются и находят спрос процессоры - специализированные цифровые компьютеры для обработки сигналов. Такое широкое использование порождает еще более широкий спрос на цифровые процессоры, применяемые в некоторых случаях в массовых масштабах.
Одним из путей удовлетворения этих потребностей является выбор разумно построенных алгоритмов. Вместо того, чтобы повышать быстродействие процессора от одного миллиона умножений в секунду
до пяти миллионов умножений а секунду, можно для некоторых задач так организовать вычисления, чтобы быстродействия в один миллион умножений в секунду оказалось достаточно.
В настоящее время нет определенного, сформулированного в литературе, направления применения широкого класса ортогональных дискретных преобразований (ОДП) в решении различных научно-технических задач. Поэтому автором в настоящей работе предпринимается попытка систематизированного исследования и применения широкого класса ОДП в различных научно-технических задачах.
Приведенные выше аргументы позволяют сделать вывод об актуальности теоретических исследований дискретных преобразований в ортогональных и неортогональных базисах, а также алгоритмически-программной реализации этих преобразований в различных научно-технических задачах.
Цельа диссертационной работы является дальнейшее теоретическое исследование ортогональных дискретных "преобразований и разработка эффективных и быстродействующих алгоритмов для анализа и математического моделирования научно-технических задач."
Поставленная цель достигается разработкой математического аппарата обобщенных кронекеровских яроизведеняй (ОКП) матриц и использование этого аппарата для распараллеливания и векторизации матриц Уояша и Фурье и разработкой на этой основе быстродействующих и высокоэффективных алгоритмов для рассматриваемых в диссертационной работе научно-лехничвекта задач.
Диссертация выполнена в соответствии с республиканской программой разработки эффективных методов, алгоритмов и программ анализа и математического моделирования научно-технических задач "Проект задания по, направлений I (п,1> Перечня"приказа Мин. ВУЗ УССР № 243", планами ^абот по хоздоговорным и гос&щжетным темам Института химии нефти и Института оптики атмосферы ТФ СО АН СССР.
Основные задачи исследований;
исследование алгоритмов быстрых преобразований Уолша;
разработка математического аппарата ОКП матриц. Использование математического аппарата ОКП для распараллеливания и вектори-
'зации матриц Уолша и Фурье; .
разработка алгоритмов быстрых преобразований Уолша и Фурье без перестановки исходных данных в виде закона двоичной инверсии и обратного кода Грея;
исследование структуры алгоритмов преобразований Уолша и
использование этих алгоритмов в реальном масштабе времени и в векторном режиме для компьютеров с архитектурой команд типа ОКМД (одна команда, много данных);
анализ векторных алгоритмов преобразований Фурье и Уолша с использованием алгоритмов расщепления и Д^ентлмэна - Сзнде;
разработка методов решения систем линейных алгебраических уравнений (СЛАУ) с нормальными, теплицевыми и симметрическими матрицами с применением ОДП Фурье, Уолша, дискретного косинусного преобразования и др. ,* ..
применение. ОДП Ьурье, Уолша для решения первой краевой задачи (Дирихле) для уравнения Гельмгольца в различных областях;
-разработка алгоритмов: распознавания органических смесей,
сжатия и "восстановления" спектральной информации; сжатия двумер
ных изображений и восстановления оригинала по изображению; тесто
вого контроля операционных устройств и процессоров с использова
нием ОДП Уолша; кодирования и декодирования к^дов Рида-Маллера
первого порядка. .,:.
Отмеченные вкае задачи при их комплексном решении позволяют развить дальше теоретическую базу ОДП Уолша и Фурье, разработать высокоэффективные и быстродействующие алгоритмы решения МНОГИХ научно-технических задач в режиме реального времени и в векторном режиме для компьютеров.с архитектурой типа ОКМД.
Методы исследования. Методика исследования состоит в использовании кронекеровских'и разработке обобщенных кронекеровских произведений матриц для факторизации матриц'ОДП, удобных для реализации их в реальном масштабе времени, а такие в векторном рсжиііе. Зто положение дает возможность использовать быстрые алгоритми ряда ОДП при решениях СЛАУ, .-^аевых задач уравнений Гельмгольца, при определении отном.-йлышх концентраций органических смесей, для цифрового моделирования изображений, сжатия информации, тестового контроля цифровых устройств и'ЭВЫ, а также для кодирования и декодирования кодов Рида-Маллера первого порядка (РЫ-1).
Научная ноеизна работы заключается в том, что в ней впервые:
-
Введены определения ОВД матриц и рассмотрены их основные свойства,-
-
На основе ОКП матриц получены алгоритмы факторизации матриц Фурье и Уолша.
-
Получен алгоритм перехода из базиса Уолша в базис Фурье.
-
Рассмотрена организация векторных вычислений алгоритмов
быстрых преобразований Фурье и Уолва;
-
Разработаны алгоритмы решения СЛАУ с использованием быстрых преобразований Фурье и Уолша.
-
Предложены алгоритмы решения задачи Дирихле для уравнения Гельмгольца с применением ОДП Уолша»
-
Разработаны алгоритмы количественного и качественного анализа органических смесей и корректировки оптических спектров смесей.
-
Созданы алгоритмы сжатия и восстановления спектральной информации.
-
Разработаны новые и модифицированы некоторые известные алгоритмы восстановления изображений.
-
Разработаны алгоритмы тестового контроля арифметических и логических операций ЭВМ.
-
Получены и модифицированы ряд алгоритмов кодирования и декодирования кодов PM-I.
Практическая ценность работы состоит в том, что полученные результаты ьж>гут быть использованы:
-
При восстановлении оригиналов изображений.
-
При определении относительных концентраций органических смесей и корректировке оптических спектров.
-
При решении первой краевой задачи для уравнения Гельмгольца с постояянмйП и переменными коэффициентами,
-
При сжатии и восстановлении спектральной информации и кодировании изображений.
-
Для проведения алгоритмически-программного контроля ЭВМ и цифровых устройств.
-
Для декодирования кодов РМ-І. -
Реализация результатов. Разработанные в диссертации алгоритмы и программы внедрены в организациях и учебных заведениях, занимающихся разработкой, изучением и внедрениеи алгоритмически-программных средств, выполняющих цифровую обработку сигналов в режиме времени, близком к реальному, в том числе в НИИ "Аккорд", в Харьковском государственном университета при выполнении НИР, Черкасском инженерно-технологическом институте, зарегистрированы в ГОСФАП. Годовой экономический эффект от внедрения алгоритмически-программного комплекса для контроля логических и арифметических операций персональных ЭВМ в НИИ "Аккорд" составляет 25000 рублей (в ценах 1991 г.). Внедрение результатов диссертации в учебный
процесс также дает большой технический эффект и имеет важное значение для повышения качества педагогического процесса в вузах соответствующего профиля.
Апробация работы. Основные положения диссертации докладывались и обсуждались на конференциях и семинарах: Международных конференциях по алгебре (г. Новосибирск, 1989, г. Барнаул,1991), Международных конференциях по локальным вычислительным сетям (г.Рига, 1990, 1992), Международной конференции "Проблемы функционирования информационных сетей" (г.Новосибирск,1991), Международной конференции "Актуальные проблемы фундаментальных наук" (два доклада) (г.Москва, Г99І), УІИ Всесоюзной конференции "Измерительные информационные системы" (г.Ташкент, 1987), XI Всесоюзном семинаре "Теория информации" ЦП ВНТО РЭС им, А.С. Полова (г.Ульяновск, 1989), Всесоюзной конференции "Диалог "Человек - ЭВМ" (г.Свердловск, 1989), Всесоюзной конференции "Математическое и имитационное моделирование в системах проектирования и управления" (г.Чернигов, 1990), П Всесоюзной конференции "Проблемы и перспективы развития цифровой звуковой техники" (г.Ленинград, 1990), Республиканской конференции-"Внедрение САПР - путь совершенствования инженерного труда и качества разработок" (г.Винница, 1987), Республиканской конференции "Методы и средства измерений в области электромагнитной совместимости".(г.Винница, 1987), Республиканской конференции "Информатика и автоматизация в регионах" (два доклада) (г.Винница, 1988), Республиканской конференции "Методические проблемы использования ТСО в учебном процессе" (г.Сумы, 1989), Республиканской конференции "Функционально ориентированные вычислительные системы" (г.Харьков, 1990), Украинской республиканской школе-семинаре "Вероятностные модели и обработка случайных сигналов и полей" (два доклада) (г.Черкассы, 1991), Республиканском семинаре "Статистический синтез и анализ информационных систем" (г.г. Москва - Черкассы, 1992) и других форумах.
Публикации. По теме диссертации опубликовано 54 работы, из них 16 работ опубликовано з центральных журналах и 6 работ опубликовано в республиканских сборниках научных трудов.
Научные результаты, выносимые на защиту: ..
I. Обобяенные кронёкеровские произведения матриц и их свой
ства. „
-
Способы факторизации матриц Фурье и Уолша и их математическое обоснование.
-
Быстрые алгоритмы ортогональных дискретных преобразований.
-
Организация векторных вычислений ОДП Фурье и Уолша.
-
Применение и использование быстрых алгоритмов ОДП Фурье и Урлиа пр!: решении СЛАУ с теплицевыми и симметрическими матрицами.
-
Решение первой краевой задачи для уравнения Гельмгольца с использованием ОДП Уолша.
?. Решение задачи цифрового моделирования двумерных изображений.
-
Количественный и качественный анализ многокомпонентных органических сыесей.
-
Алгоритмы сжатия и восстановления спектральной информации . и изображений.
-
Организация тестового контроля запоминающих устройств и логических и арифметических операций ЭВМ.
-
Способы кодирования и декодирования кодов Рида-Маллера первого порядка.
Достоверность полученных в диссертации результатов подтверждена численними экспериментами, приведенными в работе, путем, их сравнения с эталонными..данными, и с результатами расчетов, полученных с помощью известных программ, а также необходимыми математическими доказательствами.
Таким образом, в диссертации разработан ряд теоретических положений, совокупность которых можно квалифицировать как новое достижение в развитии перспективного направления "Ортогональные дискретные преобразования и их применение". Внедрение алгоритмов и программ, реализующих отмеченные теоретические положения, позволит внести значительный вклад в совершенствование методов цифровой обработка информации, что в конечном счете приведет к уменьшению затрат на ЭВМ, а также к снижении аппаратурной сложности микропроцессорной техники.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Общий объем основного текста 283 страниц,, рис. 39 и табл. 4. Список литературы включает 214 наименований.