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

РГ6 од

_ 9 &ВГ 1293

АКАДЕМИЯ НАУК УКРАИНЫ ИНСТИТУТ ПРОБЛЕМ МОДЕЛИРОВАНИЯ В ЭНЕРГЕТИКЕ

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

КОЖУХОВСКИЙ АНДРЕЙ ДМИТРИЕВИЧ

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

Специальность 05.13.16 - применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

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

Киев - 1993

Работа выполнена в Черкасском инженерно-технологическом институте

Официальные оппоненты: доктор технических наук, профессор Бутаков Евгений Артемович доктор технических наук, профессор Додонов Александр Георгиевич доктор технических наук Катков Александр Федорович

Ведущая организация: Киевский политехнический институт

.7 I .-/(. ОС

Защита состоится г. в I '_час.

на заседании специализированного Совета Д 016.61.01 по защите диссертаций при Институте проблем моделирования в"энергетике АН Украины (252660, Киев - 164, ул. Генерала Наумова, 15)

С диссертацией можно ознакомиться в библиотеке Института проблем моделирования в энергетике АН Украины

Автореферат разослан " ■_хддз г.

Ученый секретарь специализированного

Совета Д 016.61.01,

кадц. техн. наук —^

Э.П.Семагина

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

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

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

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

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

Решению указанных вше задач посвящены работы ученых: Байды Н,П., Бонцаренко В.М,, Бугакова S.A., Васильева В.В., Верланл А.Ф., Гуляева В.А., Додонова А,Г,, Евдокимова В.$., Зацираки В.К., Каткова А.Ф., Кузьмина И.В., Кухарева Г.А., Лабунца В.Г., Омель-ченко В.А., Пойды В.Н., Цухова Г.Б., Садыхова I .X., Чеголина П.М., Ярмолика В.Н., Ярославского Л.П., Ахмеда Н., Опенгейма A.B., Ра-бинера 1.Р., Шафера Р.В. и др., в которых исследования методов ВСО проводятся в двух направлениях, заключающихся в проведении теоретических исследований дискретных преобразований в ортогональных и неортогональных базисах, а также аппаратурной и алгоритмически-программной реализации этих преобразований в различных научно-тех~ нических задачах.

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

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

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

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

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

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

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

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

Диссертация вкйолнена в соответствии с республиканской программой разработки эффективных Методов, алгоритмов и программ анализа и математического моделирования научно-технических задач "Проект Задания по, направленно I (п,1) Перечня "приказа Мин. ВУЗ УССР № 243", планами ^абот по хоздоговорным и гос&щжетным темам Института химии нефти и Института оптики атмосферы ТФ СО АН СССР.

Основные задачи исследований:

- исследование алгоритмов быстрых преобразований Уолша;

- разработка математического аппарата ОКП матриц. Использование математического аппарата ОКП для распараллеливания и вектори-

'зации матриц Уолша и Фурье; .

- разработка алгоритмов быстрых преобразований Уолша и Фурье без перестановки исходных данных в виде закона двоичной инверсии и обратного кода Грея;

- исследование структуры алгоритмов преобразований Уолша и

использование этих алгоритмов в реальном масштабе времени и в векторном режиме для компьютеров с архитектурой команд типа ОКМД (одна команда, много данных);

- анализ векторных алгоритмов преобразований Фурье и Уолша с использованием алгоритмов расщепления и Дкентлмэна - Сзнде;

- разработка методов решения систем линейных алгебраических уравнений (СЛАУ) с нормальными, теплицевыми и симметрическими матрицами с применением ОДП Фурье, Уолша, дискретного косинусного преобразования и др.; ..

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

-разработка алгоритмов: распознавания органических смесей, сжатия и "восстановления" спектральной информации; сжатия двумерных изображений и восстановления оригинала по изображению; тестового контроля операционных устройств и процессоров с использованием ОДП Уолша; кодирования и декодирования к~дов Рида-Маллера • первого порядка.

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

Методы исследования. Методика исследования состоит в использовании кронекеровских'и разработке обобщенных кронекеровских произведений матриц для факторизации матриц'ОДП, удобных для реализации их в реальном масштабе времени, а такие в векторной рсзжге. Это положение дает возможность использовать быстрые алгоритма ряда ОДП при решениях СЛАУ, "грешных задач уравнений Гедьмгольиа, при определении отног..сЛЬнкх концентраций органических смесей, для цифрового моделирования изображений, сжатия информации, тестового контроля цифровых устройств и'ЭВМ, а также для кодировании и декодирования кодов Рида-Маллера первого порядка (РЫ-1).

Научная ноеизна работы заключается в том, что в ней впервые:

1. Введены определения ОВД матриц и рассмотрены их основные свойства,-

2. На основе ОКП матриц получены алгоритмы факторизация матриц Фурье и Уолша.

3. Получен алгоритм перехода из базиса Уолша в базис Фурье.

4. Рассмотрена организация векторных вычислений алгоритмов

быстрых преобразований Фурье и Уолва;

5. Разработаны алгоритмы решения СЛАУ с использованием быстрых преобразований Фурье и Уолша.

6. Предложены алгоритмы решения задачи Дирихле для уравнения Гельмгольца с применением ОДП Уолта»

7» Разработаны алгоритмы количественного и качественного анализа органических смесей и корректировки оптических спектров смесей.

8. Созданы алгоритма сжатия и восстановления спектральной информации.

9. Разработаны новые и модифицированы некоторые известные алгоритмы восстановления изображений.

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

11. Получены и модифицированы ряд алгоритмов кодирования и декодирования кодов РМ-1.

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

1. При восстановлении оригиналов изображений.

2. При определении относительных концентраций органических смэсай и корректировке оптических спектров.

3. При решении первой краевой задачи для уравнения Гельмгольца с постойнныма": и переменными коэффициентами,

4. При сжатии и восстановлении спектральной информации и кодировании изображений.

5. Для проведения алгоритмически-программного контроля ЭВМ и цифровых устройств.

6. Для декодирования кодов РМ-1.

Реализация результатов. Разработанные в диссертации алгоритмы и программы внедрены в организациях и учебных заведениях, занимающихся разработкой, изучением и внедрением алгоритмически-программных средств, выполняющих цифровую обработку сигналов в режиме времени, близком к реальному, в том числе в НИИ "Аккорд", в Харьковском государственном университета при выполнении НИР, Черкасском инженерно-технологическом институте, зарегистрированы в ГО®АЛ. Годовой экономический эффект от внедрения алгоритмически-программного комплекса для контроля логических и арифметических операций персональных ЭВМ в НИИ "Аккорд" составляет 25000 рублей (в ценах 1991 г.). Внедрение рбзультатов диссертации в учебный

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

Апробация работы. Основные положения диссертации докладывались и обсуждались на конференциях и семинарах: Международных конференциях по алгебре (г. Новосибирск, 1989, г. Барнаул,199I), Международных конференциях по локальным вычислительным сетям (г.Рига, 1990, 1992), Международной конференции "Проблемы функционирования информационных сетей" (г.Новосибирск,1991), Международной конференции "Актуальные проблемы фундаментальных наук" (два доклада) (г.Москва, 1991), УЩ Всесоюзной конференции "Измерительные информационные системы" (г.Ташкент, 1987), XI Всесоюзном семинаре "Теория информации" ЦП ВНГО РЭС им, A.C. Полова (г.Ульяновск, 1989), Всесоюзной конференции "Диалог "Человек -• ЭВМ" (г.Свердловск, 1989), Всесоюзной конференции "Математическое и имитационное моделирование в системах проектирования и управления" (г.Чернигов, 1990), II Всесоюзной конференции "Проблемы и перспективы развития цифровой звуковой техники" (г.Ленинград, 1990), Республиканской конференции "Внедрение САПР - путь совершенствования инженерного труда и качества разработок" (г.Винница, 1987), Республиканской конференции "Методы и средства измерений в области электромагнитной совместимости".(г.Винница, 1987), Республиканской конференции "Информатика и автоматизация в регионах" (два доклада) (г.Винница, 1988), Республиканской конференции "Методические проблемы использования ТСО в учебном процессе" (г.Сумы, 1989), Республиканской конференции "Функционально ориентированные вычислительные системы" (г.Харьков, "" 1990), Украинской республиканской школе-семинаре "Вероятностные модели и обработка случайных сигналов и полей" (два доклада) (г.Черкассы, 1991), Республиканском семинаре "Статистический синтез и анализ информационных систем" (г.г. Москва - Черкассы, 1992) и других форумах.

Публикации. По теме диссертации опубликовано 54 работы, из них 16 работ опубликовано з центральных журналах и б работ опубликовано в республиканских сборниках научных трудов.

Научные результаты, выносимые на защиту: ..

I. Обобщенные кронёкеровские произведения матриц и их свойства. _

2. Способы факторизации матриц Фурье и Уолша и их математическое обоснование.

3. Быстрие алгоритмы ортогональных дискретных преобразований.

4. Организация векторных вычислений ОДП Фурье и Уолша.

5. Применение и использование быстрых алгоритмов ОДП Фурье и Урлаа при решении СЛАУ с теплицеЕыми и симметрическими матрица.«!.

6. Решение первой краевой задачи для уравнения Гельмгольца с использованием ОДП Уолша.

?. Решение задачи цифрового моделирования двумерных изображений.

8. Количественный и качественный анализ многокомпонентных органических сиесей.

9. Алгоритмы сжатия и восстановления спектральной информации . и изображений.

10. Организация тестового контроля запоминающих устройств и логических и арифметических операций ЭВМ.

11. Способы кодирования и декодирования кодов Рида-Маллера первого порядка.

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

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Общий объем основного текста 283 страниц,, рис. 39 и табл. 4. Список литературы включает 214 наименований.

СОДЕРКШЕ РАБОТЫ

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

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

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

Исследуются основные способы формирования ВКФ. Аналитически ВКФ могут быть подучены с помощью обобщенных функций Радеиахера

Хт,х)=ехр[(-сгж/р) еп,Ь(х/р*~т}], «>.■

где р - простое число, ¿-Т^Г, <£ = 10рРМ", т=0Д..., оС, Х-0,1у,4Г-1у 61Ъ£('}~ целая часть. В зависимости от параметра р «окно получать различные базисные функции. Базисная система ВКФ на интервалв[0,№) определяется как произведение соответствующих обобщенных функций Радеиахера, Рассматриваются без доказательства основные свойства системы БКФ. Показана также целесообразность использования в качестве базиса системы обобщенных функций Хаара (0$Х).

Рассматриваются алгоритмы быстрых преобразований ВКФ. и (»X. Полученные алгоритмы быстрых преобразований БКФ и СФХ могут быть

положены в основу создания специализированных вычислителей в базисах В© и ОФХ, что предполагает оперативное исследование р -ичных нестационарных случайных процессов и систем.

Множество непрерывных функций действительного переменного

{'рП/Ш}" {{О $)> (Ь)г" } называется ортогональным на интервале &0^0+Т)> если

если тФП, (2)

где через _/»р обозначается А = I множество

называется ортонормированным.

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

Если {Х(П)} означает последовательность X (П/)( 1Ъ-

1 конечных действительных или комплексных чисел, то дискретное или конечное преобразование Фурье этой последовательности определяется"

ХтЫкп} о)

где 6Хр(-(/ 27С/Н), Ь=1/-Т. Зкспоненциальные функции

а . ЫИ

V/ " в (3) являются ортогональными.

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

ния обратного ДШ (0Д1Й). Приведено обобщение ДГЭ и ОД® на двумерный случай для обработки сигналов.

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

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

Проанализировано понятие частости дискретной функции. Исследуются функции Радемахера, представляющие периодическую, ортогональную, но не полную систему функций. Вводятся функции Уолша и определяются следующие упорядочения функций Уолша: естественное (по Адамару), или функции Уоляа-Адамара; диадичесяоё (по Пэли), или функции Уолша-Пэли; по частости (по Качмажу), или функции Уолша-Качмажа. Вводятся ортогональные дискретные функции Уолпа-, которые подразделяются согласно их способам упорядочения: ОДП Уолша-Апама-ра, Уолша-Пэли и Уолша-Качмажа. Представлены непрерывные и дискретные функции соответствующих упорядочений при N = 8. Указывается также их связь между собой. Рассматриваются алгоритмы быстрых преобразований Уолша (БПУ) в матричном виде, что является простым и удобным для их реализации на ЭВМ. Рассматривается пример распараллеливания быстрых алгоритмов ОДП Фурье и Уолша. Форцула для определения времени счета по программе алгоритма ОДП Уолаа-Адамара имеет вид:

%Ьо$.гК>Ьоб*. + Ьг, (4)

где"Ьвц-Ч. — время вычисления одной операции по схеме, Ьобм. -время обмена между процессорами, К. - число процессоров, Ъ - разрядность входного сигнала, % - время выборки из памяти одного

разряда. Степень распараллеливания вычислительного процесса воз" молено довести до /2. В этом случае К = .Н/% и можно также

считать, что £ЬобМ. и 1 - равные примерно величины. Тогла

т*1ггь+{ш)(ъ-и+1}г. (5)

Рассматриваются ОКП матриц по строкам и по столбцам и исследуются их основные свойства, необходимые для факторизации матриц ряда ОДП. Кронекеровское произведение матриц А ® В определяется следующим образом: каждый элемент матрицы А перемножается на матрицу 8 . Кронекеровское произведение матриц по строкам

имеет вид Д © В у где матрица А кронекеровски перемножается на первую, затем на вторую строку матрицы В и т.д. Кронекеровское произведение матриц по столбцам имеет вид С— А © В 3 где матрица А кронекеровски перемножается на первый столбец, затем на второй столбец матрицы 8 и т.д.

Тео]эема_2. Пусть С- А © В, С'= А® 8 , С" = А © В .

Матрица С" приводится к матрице С ( С' ) перестановкой строк (столбцов).

Теорема I используется для доказательства.следующей простой, но важной теоремы.

Теорема 2. Пусть НСК-() и Н(/Г%) есть матрицы Уолша порядков «АГ* соответственно. Тогда И (.М*} ® Н(^Га) и Н№ ® НШя) есть матрицы Уолша порядка -N",2. •

Пусть где 1Ь - натуральное число;

и/01- П- ~ стандартная матрица Уолша-Адямара второго Ь-Я порядка.

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

Следствие 3. НрСг^-НШф НЩФ- Ф ,

П раз

= НШ® Н(2)0...®Н(2).

—--г---

раз

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

НР (2л+<) = ЛЕг(>-1} ® Шпф Н(2)]= = П& Еа<^>©[Еа<И' § Н(2)].

Рассматривается алгоритм быстрого-преобразования Фурье (БПФ) с использованием функций Уолша. Этот алгоритм позволяет получать выходную последовательность в естественном порядке. Он удобен также тем, что дает возможность одновременного вычисления спектральных коэффициентов Уолша и Фурье. Преобразование Фурье вектора X можно записать в матричной форме: Хр Я* X 7 а преобразование Уолша-Адамара -

Отсюда,

Хр = Р Хн - (Ш) Р Нь ХН > где Р матри-

ца преобразования Фурье, Нн и Н{г ~ матрицы прямого и обратного преобразований Уолша-Адамара соответственно. Таким образом, (1/К) Р НИ, ~ матрица перехода от базиса функций Уолша в

базис функций Фурье. Приведен пример матрицы перехода при ,ЛГ = 8, ГЪ « 3. Подпрограмма, реализующая описанный выше алгоритм, приведена в приложении.

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

ций в векторном режиме. Задача векторизации программ в этом случае разбивается на два этапа: I) выявление параллелизма, имеющегося в программе; Z) реализация этого параллелизма при помощи векторных команд определенного компьютера..

В диссертационной работе уделяется внимание первой подзадаче векторизации, которая выполняется для ряда компьютеров с архитектурой типа ОКМД,

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

Третья глава посвящена применению и использованию алгоритмов преобразований Фурье и Уолша при решении СЛАУ, задачи Дирихле для уравнения Гельмгольца, анализу органических смесей, сжатию и восстановлению спектральной информации, а также разработке алгоритмов заполнения пробелов экспериментальных данных.

Рассматриваются применения ОДП Фурье и Уолша к решениям СЛАУ с .нормальными и теплицевьши матрицами. В том случае, когда СЛАУ имэет нормальную матрицу, к ней применима теорема Шура, которая утверждает, что мо^но найти ортогональное преобразование, которое диагонализирует эту матрицу. Но на практике это преобразование найти не всегда просто. Поэтому приходится использовать те ортогональные преобразования, алгоритмы которых известны и хорошо разработаны, а затем применять итерационные методы. Для ряда прикладных задач возникает вопрос решения СЛАУ с нормальными матрицами.

Пусть имеется СЛАУ Л Х- У , где А - нормальная матрица порядка Решение СДАУ будем искать в виде

Х- (А*А)~1 А* V л*

/\ vn in гл | ? ,Где /-j _ матрица эрмитово сопряжен-

ная к А . Используем метод расщепления матрицы и запишем ее в

виде А = £-С, где G, - матрица, ортогонально подобная диагональной матрице (X . Тогда

X~TiT(AitA)"1T'iA)e Y, где Т-ода, Т~1 -

обратное преобразование к Т .

D=Т(А'АГ1 Г' =<ищ jp^ä? '-> ШГсё]

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

где (£ - параметр регуляризации. При решении СЛАУ методами ОДП Фурье, Уолша возможно использовать векторные алгоритмы этихпреобразований, полученные в главе 2.

Рассмотрены также итерационные алгоритмы решения СЛАУ с теп-лицевыми матрицами.

Пусть имеется СЛАУ АХ~ У) где А - теплздева матрица.

Решение СЛАУ происходит по схеме

ВХ-СХ+ у, где В — невырожденная матрица с простым обращением. Матрицу ß можно получить следующим образом: TAT'1 = 5 J J5- CtCCLQ S j I ~ ОДП Фурье или Уолша, Положим

ТАГ'1» j>.

Тогда

В * = Т 1J) iT • Итерационный процесс сходится, если

i/B-'CIKt

Рассматривается прямой способ решения СЛАУ с теплицевой матрицей. Для этого матрица А представляется в виде А-В А B^j где В= [Etf' О JJ"] j Ejf 0/Г ~ единичная и нулевая матрицы порядка Jf ; А - циклическая матрица порядка

2JV ,

первая строка которой имеет вид

{СЬо, 0, (1.^+1, Я^+г,..., (1-2, &-1}.

Тогда = В+ , где В* и (в*)+ - псев-

дообратные матрицы к В и 8* ; Ь - символ транспонирования А = Р Г А р ; Л — диагональная матрица; Р и р '

прямое и обратное преобразования Фурье.

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

Рассматриваются способы разделения спектров многокомпонентных органических смесей: по методу наименьших квадратов (ЫШ), методу винеровской цифровой фильтрации и методу регуляризации по А.Н. Тихонову, Все эти три способа предполагают использование быстрых алгоритмов ОДП Фурье, Уолша, дискретного косинусного преобразования Чебьшева (ДКПЧ),

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

Оптический спектр поглощения смеси представим в виде

где (/ - номер точки отсчета спектра смеси, соответствующий определенному волновому числу СУ (см"1), ¿=1,171 ; ^ - номер компонентов в смеси; П* - число компонентов; ПЪ~ число точек

спектра смеси (Wl^-ft)} ])i (Ш}~ поглощение смеси в С -й точке.

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

Сьсиц}2.

Решая СЛАУ относительно концентраций компонентов смеси С ^ > можно найти ее количественный состав. Запишем условие задачи в

матричной форме: J)—ДС} где D - вектор-столбец оптических плотностей; А - матрица коэффициентов сиеси; С - вектор-столбец концентраций. Тогда С~ (АТА Г1 J) или

где Ат - транспониоованная матрица к А . Для уменьшения влияния случайных ошибок вводятся аееовые коэффициенты: "UA. (J>hi ) } где Sj>i ~ дисперсия измерения оптических плотностей или

ы ~ 1 ' Матрица весовых коэффициентов диагональная. Вопрос о выборе числа аналитических точек решается в каждом случае различно. Обычно достаточно выбрать 60 - 130 точек спектра. Таким образом, нормальная

система уравнений сводится к решению СЛАУ АХ~ Уf . где А -вещественно-симметрическая положительно-определенная матрица порядка ГУI .

В качестве примера на рис. I приведен спектр кривой из растворов химически чистых (х.ч.) карбазола, антрацена и фенантрена в х.ч. гексане. На рис. 2 приведены полученные расчетным путем спектры компонентов: антрацена (I), карбазола (2) и фенантрена (3). Были получены концентрации: антрацена - Ci = 4,346*10

моль/Л; карбазола - Cz * 14,21 ЧО"6 моль/Л; фенантрена -

С$ = 17,8* 10""® моль/Л. Здесь J) - оптическая плотность поглощения, ^р - волновое число.

2 40-

е>А стоя

Рис. I.

48 96 М к5. М3836 У>403гСМя1

М М 42 333$ ))> 10 , см'

Рис. 2.

Рассматривается алгоритм машинной, корректировки спектров. Он заключается в вычислении взаимной корреляционной функции (ВКФ) модельной смеси и суперпозиций ее компонентов. Приводятся рекомендации по выбору числа точек отсчета спектров, что позволяет снизить ресурсы ЭВМ: повысить быстродействие и уменьшить объем требуемой оперативной памяти ЭВМ.

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

нтальные данные до 40 - 50 %.

Четвертая глава посвящена рассмотрению методов и алгоритмов обработки двумерных изображений.

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

ленное на его приближение к исходному изображению (оригиналу) и __

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

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

Показывается, что цифровая обработка изображений может быть сведена к анализу манипуляций с большими матрицами, связанных с выполнением таких операций обработки, как преобразование-, разложение, представление и реставрация. Рассматриваются некоторые из таких операций с использованием аппарата матричной алгебры и, в частности, векторных внешних произведений. Множество возможных ортогональных систем для разложения изображения бесконечно. Рассматриваются и обсуждаются некоторые из них: преобразование тождественности, преобразование Хаара, преобразование Уолша-Адамара, преобразование Фурье и др. Показывается, что энергия изображения стремится сосредоточиться на нескольких избранных коэффициентах. Следовательно , чтобы обеспечить хорошее воспроизведение исходной картины, требуется сохранить лишь немногие члены разложения. Поскольку приведенные разложения унитарны, энергия изображения преобразуется так, что несколько больших коэффициентов разложения представляю? большую долю энергии изображения. Таким образом, для сохранения в изображении важной информации требуется лишь небольшое

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

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

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

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

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

Ясследуются алгоритмы восстановления изображений. Если матрица импульсной характеристики системы является теплицевой и симметрической, то ее можно представить как циркулянтную и преобразование Фурье обеспечит диагонализацию этой матрицы, т.е. теплицевы симметрические матрицы могут быть аппроксимированы матрицами-циркулянтами. Наилучшие результаты получаются в случае, когда матрица импульсной характеристики имеет большой порядок и не достаточно коррелированные отсчеты изображения (относительно быстрое уменьшение корреляции между близко находящимися отсчетами изображения). В этом случае можно использовать итерационный алгоритм, приведенный в главе 3. Приводятся рекомендации по выберу параметра регуляризации при нахождении оригинала. Рассматривается также итерацион-

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

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

входного сигнала и импульсной функции системы

$(x$=fff(i>i) h(x-s, y-DcLldfi,

- 1SO

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

ШтТ,пТ)пРн (m,tb)e(C0,M-l]x[0,H-1]); ?ma = 1 rt

Ц О в иных случаях. (?)

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

Q-Kl=Zm.?oZn=o -frkn hn-m,i-ruf (8)

где 1к1=$(КТ,1Т)}КРг*Н,(рТ,(1Т).

Требуется определить отсчеты входного сигнала в прямоугольной области ОсДЖСК-ьКаЗхСЦг*]), где , Кл , I* ,

Ь% - границы прямоугольной области.

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

М^^)* Предлагается способ формирования импульсных функций. Пусть функция Н-(Х) задается Я -дискретными значениями (¡10, ) • Импульсную функцию Ьгпредста-

вим в ьиде теплицевой матрицы, где первая строка и первый столбец состоят из элементов (Ко1 \bjf~l)) а все элементы, сто-

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

цева матрица

Ьо И/* Кг ¡ы Ко Ьи * • ■ И/к-а.

Кк-

■1

И»о

Представим искаженное изображение в виде:

а=ир, с»)

где С - матрица яркости искаженного изображения, Н - матрица импульсной характеристики, системы, Р - матрица яркости истинного изображения. Заметим, что такой способ представления искаженно-, го изображения совпадает с известным. Для нахождения истинного изображения необходимо решить СЛАУ, Ввиду того, что матрица И -

симметрическая и в большинстве случаев положительно определенная.

то решение СЛАУ (9) в этих случаях не представляет труда. Для этого достаточно в матрицах Яи С. выделить столбцы

и решить относительно их СЛАУ (9). Таким образом, для решения СЛАУ = необходимо выполнить два прямых преобразова-

ния Фурье и одно обратное.

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

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

Рассматривается тестовый контроль ЭВМ, основанный на методе избыточных переменны*. Исследуются способы тестового контроля по спектральным коэффициентам ортогональных преобразований. В качестве ОДП можно использовать преобразования Фурье, Уолша, Хартли и др. Рассмотренный способ заключается в подсчете коэффициентов булевых функций.по ортогональному базису и их сравнение с эталонными. Полный набор спектральных коэффициентов позволяет использовать теорию спектрального разложения булевых функций для анализа достоверности контроля работы ЭВМ. При использовании самоконтроля вычислений коэффициентов Уолша-Пэли и Фурье в методе избыточных переменных можно снизить вычислительные ресурсы, в результате чего отпадает необходимость получения и хранения эталонных коэффициентов, а также уменьшается время сравнения вычисленных ко-э<ЗДициентов с заданными. Рассматриваются два случая применения

организации контроля проверки вычислений коэффициентов Фурье и

Уолша-Пэли. __

Пусть ХС) — входные и выходные отсчеты данных.

Тогда ^ _лГ

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

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

Введем следующие обозначения: 1ц(0) и -матри-

цы порядка

К , состоящие из нулей и единиц: и

Ср (№) - инверсные матрицы .по отношению к матрицам Уолша-

Адамара и Уолша-Пэли соответственно/ Установим следующий способ контроля правильности выполнения логических операций (наличие ошибок выявляется отсутствием нулей или единиц в разрядах):

Си, (Ю © сн ш = сР (ю © ср сю=ь, (о) ; Ск(АГ) © СШ) = Ср(Ю®Ср(Ю = 1к С1).'

Контроль арифметических операций процессора возможно также проводить с помощью матриц Уолша

(1 /Ю И!ь(ЮНц(Ю = (1/ЮИр(!:иИр(т= Ек,

где БлГ - единичная матрица порядка N .

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

ционных устройств и процессоров в микроЭВМ совместно с' преобразованиями Уолша.

Обозначим: X - прямой иод, X' - обратный код, X" -

дополнительный код операнда X . Рассмотрим следующие соотношения:

X+X'=Zn-1*11...H} (Ю)

Х+Г=2* = ОО...00; cid

X-X"+X2-1=U.»11; (I2)

Х-Х"+Х2 = 00... (I3)

Соотношения (10) - (13) можно использовать в качестве контрольных, так как в пределах разрядной сетки Zn~1 - И ••• 14 j

0000 и наличие ошибок в операциях приводит к тому,

что не во всех разрядах контрольного слова будут содержаться одни единицы или нули соответственно. Применяя соотношения. (10) - (13)

к строкам или столбцам матриц ChtАЛ и СрШ}, можно получить первую строку этих матриц 00 ... 00 или ей инверсную II ... II. Локализация константных неисправностей типа "нуль или единица" в этом случае не представляет труда.

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

Определение. Косиндромом булевой функции с полным перебором аргументов назовем величину

NF(0,0,..;0). (14)

Теорема. Косиндром булевой функции

н?т..,о)=тр0 niu (i5)

где ПИ - спектральные коэффициенты преобразований Уолша или Фурье, нумеруемые в порядке возрастания от 0 до • Очевидно, что косиндром булевой функции может принимать только

два значения: I/ или Я .

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

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

2(ггь)=а/М)1^0 Х(Ь)У(т+М, т-О^М.

Известно, что коэффициенты ВКФ можно находить с помощью алгоритма БПФ. На рис. 3 приведена структурная схема вычисления ВКФ.

-

Рис. 3.

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

т.е. величина будет всегда неотрицательной. Если

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

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

Суть второго критерия в следующем. В случае совпадения вычисляемых коэффициентов и известных (эталонных) величины {2 т),

будут иметь наибольшую величину при 171=0, т.е. Х(о)-гпа%) если последовательности {Х(К}} и (У(М) не являются идентичными, то наибольший коэффициент ВКФ будет смещен от 171 - О • Второй критерий используется во

временной области.

В приложении I рассматриваются алгоритмы кодирования и декодирования' кодов Рида-Маллера первого порядка.

В приложении 2 описаны подпрограммы, реализующие предложенные в диссертационной работе алгоритмы быстрых преобразований Уолша-Адамара, Уолша-Пэли'и Уолша-Качмажа. Сделано их сравнение с БПФ для различных ЭВМ, Приводятся акты внедрения и использования результатов диссертационной работы.

заключение;

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

1. Исследованы способы формирования обобщенных дискретных базисов Виленкина-Крестенсона и обобщенных функций Хаара в р -ичных системах счисления. Рассмотрена целесообразность использования обобщенных ортогональных преобразований для решения практических задач. Приведены алгоритмы быстрых преобразований Виленкина-Крестенсона функций (ВКФ) и обобщенных функций Хаара (ОФХ) и показана наглядность алгоритмов вычисления коэффициентов ВКФ и ОФХ в виде графов.

2. Проведен теоретический анализ рядов, интегрального и дискретного преобразований Фурье, показана их взаимосвязь и практическое применение. Рассмотрен физический смысл величин, входящих в -дискретное преобразование Фурье (ДГЩ. Приведены основные свойства интегрального и дискретного преобразований Фурье. Проведен подробный анализ вычислительных затрат ДПФ.

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

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

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

6. Разработан математический аппарат обобщенных кронекеровс-

ких произведений (ОКП) матриц и доказываются их основные свойства. С использованием ОКП получены математические описания факторизации матриц Уолша и Фурье.

7. Получены алгоритмы быстрых преобразований Уолша и Фурье без перестановки исходных данных в виде закона двоичной инверсии и обратного кода Грея. Исследована структура алгоритмов преобразований Уолша и указаны области применения спектрального анализа в реальном масштабе времени.

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

9. Предложены способы решения систем линейных алгебраических уравнений (С1йУ) о нормальными, теплицевыми и симметрическими матрицами. Все способы решения СЛАУ рассматриваются в частотной области с применением ОДП Фурье, Уолша, дискретного косинусного преобразования и др., что снижает число обусловленности СЛАУ. ОДП устойчивы к ошибкам округления, быстродействующие, сокращают объем требуемой оперативной памяти ЭВМ. При решении СЛАУ использованы векторные алгоритмы преобразований Уолша и Фурье. Разработаны способы решения первой краевой задачи (Дирихле) для уравнения Гельмгольца э прямоугольной и односвязной областях с применением ОДП Фурье и Уолша. Рассмотрены и проанализированы ряд итерационных алгоритмов для решения первой краевой задачи Дирихле для уравнения Гельмгольца.

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

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

12. Рассмотрены способы реставрации оригинала изображения с

линейной импульсной функцией с применением ОДП Фурье и Уолша. Предложены алгоритмы восстановления искаженных изображений: а) путем реиения СЛАУ с теплицезой симметрической матрицей большого порядка; б) итерационный алгоритм путем решения СЛАУ с помощью метода расщепления импульсной функции и ОДП Фурье, Уолша и др.; в) итерационный алгоритм с использованием невязок решения СЛАУ и параметров регуляризации; г) итерационный алгоритм ' решения :СЛАУ с помощью циркулянтной матрицы и метода проекций.

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

14. Предложены способы тестового контроля ЭВМ на основе ме-. тода избыточных переденных с использованием ОДП Уолша и Фурье,

операционных устройств и процессоров с использованием ОДП Уолша. Разработан способ самоконтроля проверки правильности выполнения логических и арифметических операций ЭВМ. Модифицирован ряд известных тестов, таких как "Шахматный код", "Четность и нечетность", а также получены новые способы тестового контроля. Предложен способ тестового контроля правильности выполнения логических и арифметических операций вычислительных устройств с использованием синдрома и косиндрома булевых функций. Разработан способ тестового контроля ЭВМ с использованием взаимно-корреляционной функции к приведены два критерия выполнения этого способа контроля.

15. Разработаны алгоритмы кодирования и декодирования кодов Рида-Маллера первого порядка (РМ-1) -с использованием быстрых преобразований Уолша-Адал;ара и Уолша-Пзли дЛя реализации их в режиме реального времени и в векторном режиме для компьютеров с архитектурой команд типа.ОКИД. Проведен сравнительный анализ декодирования кодов РМ-1 с помощью векторных алгоритмов указанных выие преобразований и других известных алгоритмов. Предложены алгоритмы декодирования кодов РМ-1 способом генерации всех элементов последовательностей для матриц Уолша-Адамара и Уолша-Пэли.

16. В рамках диссертационной работы создан ряд подпрограмм ' быстрых преобразований Уолша и Фурье, зарегистрированных в ГОСФАП и внедренных на производстве и в учебном процессе.

Основные положения диссертации опубликованы в следующих работах

1. Алгоритмы восстановления изображений / В.И. Быков, А.Д. Кожуховский, А.И. Литвин, A.B. Матухно // Вероятностные модели и обработка случайных сигналов и полей: Тез. докл. Украинской республиканской школы-семинара,- Черкассы, 1991,- С. 126.

2. Алгоритмы восстановления изображений / А.Д. Кожуховский, A.B. Матухно, А.И. Литвин, Н.В. Молчунов // Электрон, моделирование.-1992.- Т.14.- »I.- С. 10-12.

3. Быков В.И., Кожуховский А.Д., Литвин А.И. Организация диагностирования ЛВС и ЛВС // АВТ.- 1992.- №2.- С. 66-68.

4. Вычисления интегралов с логарифмической особенностью J А.Д. Ко. жуховский, ИД. Коваленко, А.И. Литвин, С.Д. Симонженков // Актуальные проблемы фундаментальных наук. Тез. докл. Ыекдунар. науч.- технич. конференции,- П.: 1991.- С. 74.

5. Вычисления функций Дебая и интегралов Клаузена / А.Д. Кожуховский, И.Л. Коваленко, А.И. Литвин, С.Д. Симонженков // Актуальные проблем фундаментальных наук. Тез. докд. Междунар, науч.-технич. конференции, - 11.: 1991.- С. 101-104.

6. Гнатив Л.А., Кожуховский А.Д., Литвин А.И. Алгоритмы быстрых преобразований для кодов Рида-Маллера и Хзммянга // Автоматика,- 1990,- №4.- С. 74-77.

7. Гнатиз Л.А., Кожуховский А.Д., Литвин А.И. Организация векторных вычислений ортогональных преобразований Уолпа // Автоматика.- 1991.- М,- С. 87-91.

8. Зайцев А.П., Кожуховский А.Д., Литвин А.И. О некоторых алгоритмах сжатия спектральной информации^- Томск, 1986.- 14 е.- Деп.

в ВИНИШ 23.05.86.- » 3765. - В 86.

9. Зайцев А.П., Кожуховский А.Д., Литвин А.И. Об алгоритмах быстрых преобразований Уолша.- Томск, 1986.- 20 е.- Деп. в ВИНИТИ 23.05.S6,- * 3764 - В 86.

10. Кожуховский А.Д. Алгоритмы сжатия и интерполяции сигналов // Проблемы и перспективы развития цифровой звуковой техники.-Д.: 1990,- С. 23-24.

11. Кожуховский А.Д. Алгоритмы преобразования Уолша-Пэли и их применение для декодирования кодов Рида-Ыаллера // Изв. ВУЗ-ов. Радиоэлектроника,- 1991.- Т. 34.- Ж,- С. 63-67.

12. Кожуховский А.Д. Алгоритмы сжатия спектральной информации.-Черкассы, 1992.- 7 е.- Деп. в УкрНШНТИ 21.01.92.-£65-Ук 92.

13. Кожуховский А.Д. Использование преобразования Уолта в заполнении пробелов экспериментальных данных // Гибрид, вычиси. машины и комплексы.- К.: Наук, думка, 1992.-Вып. 15.- С. 19-21.

14. Кожуховский Л.Д. Использование преобразования Уодша-Пзди для декодирования кодов Рида-Мадлера // Вероятностные модели и-обработка случайных сигналов и полей.- Черкассы, 1991.- С. 47.

15. Кожуховский А.Д. Контроль цифровых схем ЭВМ // УСкМ.- 1991.- . Ш.-С. 26-29.

16. Кожуховский А.Д. Способы разделения спектров многокомпонентных смесей.- Черкассы, 1991,- 14 с.-Деп. в УкрНИИНТЙ 25.04.91.-

$ 577 - У к 91.

17. Кожуховский А.Д., Ларикова Л.Н., Литвин, А.И. Тестовый контроль ЭШ с использованием ортогональных дискретных преобразований// УСА- 1987.- К.- С. 7-8.

18. Кожуховский А.Д., Девагшшков А.А., Литвин А.И. Быстрые алгоритмы декодирования кодов Рида-Мадлера // Радиотехника.- 1992.-№ 7-6.- С. 50-53.

19. Кожуховский А.Д., Литвин А.И. Векторизация алгоритмов быстрого преобразования Уолша-Пэди // Теория информации. Ч.^Z.~ Удоя- , ковок, 1989.-С. 61-62.

20. Кожуховский А.Д., Литвин А.И, Использование преобразований Уолша-Адамара в информационно-поисковых системах // Диалог "Человек-ЭШ".'Ч.З.-Свердловск, 1989.-С. 40. .

21. Конуховский А.Д., Литвин А.И. Алгоритмы решения систем линейных алгебраических уравнений. Свидетельство $ ЮТ // ЦНШШ. Специализированное отделение отраслевого фонда алгоритмов и программ систем автоматизации проектных работ для технологической подготовки производства и автоматизированных систем управления технологическим процессом ОМП САПР-Т и АСУТП.41.: 1989.6 с.

22. Кожуховский А.Д., Литвин А.И. Алгоритмический контроль правильности вычислений преобразований Уолша и Фурье, основанный на методе избыточных переменных // Электрон, моделирование.-1990.- Т.12,- №2,- С. 77-78.

• 23. Кожуховский А.Д., Литвин А.И. Контроль цифровых схем ЭШ с помочью преобразований Уолта и Фурье // Локальные вычислительные

сети (ДОКСЕТЬ 90). Тез. докл. Мекдунар, науч.-техн. конф.-Рига, 1990.- С. 379-382.

24. Колуховсний А.Д., Литвин А.И. Организация тестового контроля ЭВМ // УСиМ.- 1990.- £2.- С. 39-42.

25. Кожуховский А.Д., Литвин А.И, Способы определения вектор-последовательностей матриц Уолпа // Изв. БУЗ-ов. Радиоэлектроника.- 1990.- М.- С. 96.

26. Кожуховский А.Д., Литвин А.И. Программно-алгоритмический контроль логических и арифметических операций в ыикроЭВМ // Функционально-ориентированные вычислительные системы.- Харьков, 1990.- С. 96.

27. Кожуховский А.Д.} Литвин А.й. Контроль цифровых схем ЭШ с помощью преобразований Уолиа и Фурье // Изв. ВУЗ-ов. Радиоэлектроника.- 1990.- №12.- С. 81-84.

28. Кожуховский А.Д., Литвин А.И. Итерационные методы восстановления изображений // Статистический синтез и анализ информационных систем*- Москва-Черкассы, 1992.- С. 117-119.

29. Кожуховский А.Д., Литвин А.И. Способы определения вектор-последовательностей матриц Уолса // Проблемы функционирования информационных сетей СШИС 91). Тез. докл. Цевдунар. науч.-техн. кокф.- Новосибирск, 3§91.- С. 125-130.

30. Ко.?ухогский А.Д.,-Литвин А.И. О возможности векторизации быстрого преобразования Уолша-Пэли // Электрон, моделирование.-

Т. 13.- КЗ.- С. 14-15.

31. Коауховский А.Д,, Литвин Л.И. О распараллеливании алгоритмов ■ преобразований Уолиа //Гибрид, вычисл. машины и комплексы.-К.: Наук, думка, 1990.- Был. 13.- С. 34-39.

32. Кожуховский А.Д., Литвин А.И. Организация векторных вычислений преобразований Уолша-Адамара // Гибрид, вычисл. машины и комплексы. - К.: Наук, думка, 1992.- Вып.14.- С. 38-41.

33. Кожуховский А.Д., Литвин А.И. Решение систем линейных алгебраических уравнений-с использованием ортогональных дискретных преобразований // Вычислит, и прикладная математика,- К.: Лыбидь, 1992.- Вып.74.- С. 17-19,

34. Козуховский А.Д., Литвин А.И., Мельник А.А. Способы сокращения избыточности информации,- Черкассы, 1992.- II е.- Деп. в УкрИНТЭИ 09.07.92.- № 1040 - Ук 92.

35. Кожуховский А.Д.» Литвин А.И., Серафинович Л.П. Генерирование

псевдослучайных чисел с нормальным законом распределения // Методические и технические проблемы использования ТСО в учебном процессе,- Суш, 1989.- С. 163-164.

36. Кожуховский А.Д., Симонженков С.Д., Литвин А.И. Математическое моделирование двухточечных краевых задач // Математическое и имитационное моделирование в системах проектирования и управления.- Чернигов, 1990.- С. 44-46.

37. Кожуховский А.Д., 'Симонженков С.Д., Литвин А.И. Методика численного интегрирования функций Ферми-Дирака.и Фойгта // Вычислит. и прикладная математика,- К.: Лыбидь, 1991.'- Выл. 75.-

С. 98-103. .

38. Литвин А.И., Кожуховский А.Д. Алгоритм корректировки спектров поглощения органических смесей,- Черкассы, 1992.- 12 е.- Деп. в УкрНИИНГИ 25.02.92.- » 221 - Ук 92.

39. Литвин А.Й., Кожуховский А.Д, Обобщение кронекеровского произведения матриц и его применение // Тез. докл. Ыевднар. конф, по алгебре,- Новосибирск, IS89.- С. 34.

40. Об алгоритмах преобразований Уолса-Дэли, Фурье и Хартли / Я.И. Капицкий, А.Д. Кожуховский, E.Ù. Дапчук, А.И. Литвин,-Винница, 1987,- 14 е.- Деп. в УкрНИИНТИ 30.01.0?.-» 550-Ук 87.

41. Обобщенные кронекеровские произведения матриц и их-приложения/ В,И. Быков, А.Д. Кожуховский, O.K. Росошек, А.И. Литвин, В.А. Иванова // Электрон, моделирование.« 1991,- Т. 13.-!?5.-С. 14-19.

42. Обобщенные кронекеровские произведения матриц к их приложения/ А.Д. Кожуховский, А.И, Литвин, В,А. Иванова, O.K. Росошек // Тез, докл. Мездунар. конф. по алгебре,- Барнаул, I99I.-C.67.

43. Организация диагностирования ЛВС и ЦВС / В.И. Быков, А.Д. Кожуховский, А.И. Литвин, И,Н. Гевко, О.В. Подгорный // Локальные вычислительные сети (ЛОКСЕТЪ 92), Тез, докл. Мезвдунар. науч.-техн..конф.- Рига, 1992.- С. II0-II3.

44. Структура алгоритмов преобразований Уолша/Л.А. Гнатив, В.К, Задирака, А.Д. Кожуховский, А.И. Литвин // Автоматиха.-1992.-£2.- С. 76-80.