Введение к работе
Актуальность темы. Одной из основных задач кибернетики является задача синтеза управляющих систем. Здесь наиболее известны и достаточно полно исследованны схемы из функциональных элементов и контактные схемы. Асимптотическое поведение функции Шеннона, когда за меру сложности принимается количество элементов, изучено О.БЛупановым достаточно давно. Эти классические модели сыграли основополагающую роль в развитии теории сложности управляющих систем. Вместе с тем они не учитывают ряд важных характеристик, существенных для реальных электронных устройств, особенно современных интегральных схем, что ограничивает применение таких моделей на практике.
Одной из таких характеристик является объем, занимаемый элементами схемы. В основе структуры и схем из функциональных элементов, и контактных схем лежит граф, а за сложность схем принимается в одном случае - число вершин графа, а в другом - число ребер. Предполагается, что и вершины, и ребра графа не имеют линейных размеров, поэтому вопрос об объеме или площади, занимаемой схемой, вообще лишен смысла. Однако, элементы реальных интегральных схем занимают некоторый вполне определенный объем, соединяются между собой проводниками, имеющими толщину и длину, и не исключено, что это может стать серьезной проблемой при проектировании реальных интегральных схем.
В 1967 году А.Н.Колмогоровым и Я.М.Барздинем было показано, что если учесть объемные характеристики элементов и соединений схемы, то вполне может оказаться, что активные элементы схемы будут занимать ничтожно малый объем по сравнению с объемом всей схемы. Поскольку при производстве реальных схем на такие важные характеристики как быстродействие, надежность и даже стоимость влияет не только количество активных элементов, но и размеры схемы (причем весьма существенно), то вопрос о линейных размерах схемы представляется довольно важным.
Первые существенные результаты в построении и исследовании математических моделей, учитывающих размеры схемы были получены тогда же, в 1967 году, когда в работах А.Д.Коршунова и С.С.Кравцова были описаны клеточные и объемные схемы из функциональных элементов, и было показано, что функция Шеннона (необходимая и
достаточная сложность схемы, реализующей «самую плохую» булеву
функцию, зависящую от п переменных) имеет порядок 2" (напомним, для обычных схем из функциональных элементов функция Шеннона
асимптотически равна 2"/п). В дальнейшем клеточные схемы из функциональных элементов и близкие к ним модели исследовались в работах А.Альбрехта, Ю.Громковича и Б.Шустера, Н.А.Шкаликовой, Х.Пападимитриу и М.Сипсера, а также других авторов.
А.А.Сапоженко и С.АЛожкиным была продемонстрирована принципиальная возможность описывать реальные интегральные схемы на языке схем близким к контактным и релейно-контактным, были отмечены определенные преимущества такого описания. Поэтому представляется интересным рассматривать различные модели контактных и релейно-контактных схем, мерой сложности которых служит такая важная для интегральной технологии характеристика, как площадь, занимаемая схемой.
В работах Ю.Г.Таразевича была введена в рассмотрение модель контактной схемы, уложенной в плоскую целочисленную решетку (в настоящей диссертации эта модель называется однослойной контактной схемой). Благодаря тому, что схема укладывается в решетку, становится возможным учесть пространственные характеристики элементов схемы.
Однако, использование данной модели плоских контактных схем в качестве математического прототипа реальных интегральных схем все еще довольно затруднительно. Обязательно учитывать еще и следующее обстоятельство: для того, чтобы реальный «контакт» начал функционировать, нужно каким-либо образом «сообщить» ему значение соответствующей переменной. В реальной интегральной схеме это можно сделать, подведя проводники, по которым будут подаваться значения переменных, к затворам транзисторов (то есть, контактов). Но, во-первых, эти проводники и сами должны иметь вполне определенные линейные размеры, а во-вторых, при прокладке проводников могут возникнуть сложности чисто топологического характера. Все это, несомненно, может повлиять на структуру и, следовательно, на сложность схемы.
В настоящей работе рассматриваются модели контактных схем, учитывающие необходимость подавать управляющее воздействие на контакты, изучается сложность реализации такими схемами булевых функций и систем функций.
Цель работы.
-
Построение модели контактных схем, учитывающей как объемные характеристики элементов схемы, так и необходимость подачи на контакты управляющего воздействия.
-
Оценка функции Шеннона.
-
Исследование сложности реализации схемами данной модели конкретных булевых функций.
-
Количественная оценка стоимости учета объемных характеристик элементов схемы и необходимости подачи на контакты управляющего воздействия.
Общая методика исследования. Работа основана как на уже известных методах исследования сложности управляющих систем (мошностной метод Шеннона, метод Нечипорука, метод рассеченных схем), так и на новых, разработанных автором, методах. Все верхние оценки сложности получены с помощью конструктивных доказательств. Кроме того, при получении некоторых оценок используется аппарат математического анализа и перечислительной комбинаторики.
Научная попита. Все основные результаты работы являются новыми:
-
Построена модель двухслойных контактных схем, учитывающая объемные характеристики элементов схемы и необходимость подачи на контакты управляющего воздействия.
-
Получен порядок функции Шеннона для двухслойных контактных схем.
-
Получен ряд нетривиальных нижних оценок сложности реализации конкретных булевых функцих двухслойными контактными схемами.
-
Установлена связь между сложностью реализации булевых функций клеточными схемами из функциональных элементов и ориентированными двухслойными контактными схемами.
-
Найдена точная по порядку количественная оценка стоимости учета необходимости подачи на контакты управляющего воздействия.
Теоретическая и практическая ценность. Работа носит, в основном, теоретический характер. Главное научное значение работы, по мнению автора, состоит в описании и исследовании модели контактных схем, учитывающей две важные для реальных интегральных схем особенности: учет объемных характеристик элементов схемы и необходимость подачи на контакты управляющего воздействия. В работе проводится всестороннее исследование влияния этих особенностей на сложность схемы.
Апробация работы. Результаты работы докладывались на IV Межгосударственном семинаре по дискретной математике (МГУ, февраль 1993г.), X международной конференции по проблемам теоретической кибернетики (Саратов, июнь 1993г.), VI школе-семинаре «Синтез и сложность управляющих систем» (Минск, ноябрь 1993г.), семинаре «Математические вопросы кибернетики» под руководством член-корр. РАН С.В.Яблонского (МГУ, ноябрь 1996г.), семинаре «Математическая теория синтеза управляющих систем» под руководством член-корр. РАН О.Б.Лупанова (МГУ, май 1997г.).
Публикации. Основные результаты диссертации опубликованы в работах автора [1-6].
Структура и объем диссертации. Диссертация состоит из введения и семи глав, некоторые из которых разбиты на параграфы. Полный объем диссертации составляет 77 страниц машинописного текста. В работе содержится 26 рисунков, список литературы содержит 31 наименование.