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

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

Среди различных возможностей обоснования понятия сложности, предназначенного для решения вышеназванных проблем, одним из наиболее перспективных является информационный подход, который отличается большой универсальностью и общностью. Но до сих пор отсутствовало математическое обоснование соответствующей оценки сложности. Хотя уже в начале 60-х годов известным японским ученым Са-тоси Ватанабе была выдвинута идея использовать для характеризации сложности системного объекта информационную завис&юсть между его компонентами / I, 2 /, до сих пор практических численных результатов по этому методу получить не удалось, ибо использованный вероятностный подход к определению понятия информации не подходит для изучения свойств единичных объектов, которые не имеют статистического характера. Также при этом подходе не учитываются все необходимые взаимосвязи между компонентами рассматриваемого объекта для получения оценки, отражающей сложность известных на практике реализаций. Зато в алгебраической структурной теории автоматов Дж. Хартманиса и Р. Стирнза / 3 /, представляющей собой развитый и перспективный аппарат декомпозиции ДУУ, предложен необходимый комбинаторный подход к определению понятия информации, используя понятие разбиения в качестве алгебраического эквивалента информации. Однако при сравнении разбиений они остались только на качественном уровне, используя для этой цели отношение частичного порядка. При таком подходе невозможно оценивать количественно информационную зависимость в системе декомпозиционных разбиений. Следовательно, отсутствует и количественная оценка эффективности для декомпозиции. Из вышеприведенного следует, что выработка математического аппарата комбинаторной теории информации, позволяющей получить универсальные оценки сложности для широкого класса различных ДУУ, достаточно хорошо согласующейся с практическими оценками сложности, имеет большую актуальность.

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

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

Основные научные результаты настоящей работы следующие:

1. Показано, что разбиение как алгебраическая интерпретация информации имеет однозначно определенную количественную оценку в виде энтропии.

2. Выявлены информационные свойства систем разбиений и введено понятие информационной связки СИС) для систем разбиений. Показано, что ИС отражает сложность объектов, представимых в виде систем разбиений.

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

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

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

Апробация работы" Научные и практические результаты диссертации докладывались и обсуждались на:

— постоянно действующем семинаре «Теория проектирования дискретных устройств» в Таллинском политехническом институте (Таллин,.

1979);

— УШ Всесоюзном совещании по проблемам управления (Таллин,.

1980);

— XXIII Всесоюзной школе-семинаре им. М. А. Гаврилова по теории дискретных систем (Таллин, 1981);

— научном семинаре Института проблем передачи информации АН СССР (Москва, 1981);

— научном семинаре по синтезу ДУУ Института проблем управления (Москва, 1984);

— семинаре по алгебре Тартуского государственного университета (Кяэрику, 1982);

— Всесоюзной конференции «Проблемы преобразовательной техники» (Киев, 1983).

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

выводы.

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

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

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

ЗАКЛЮЧЕНИЕ

.

В работе получены следующие основные результаты:

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

II) Выявлены информационные свойства систем разбиений и введено понятие информационной связки (ИС) для систем разбиений, которое количественно учитывает всевозможные взаимозависимости в системе разбиений. Показано, что ИС отражает сложность объектов, представимых в виде систем разбиений.

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

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

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

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