Синтез схем контактного типа с ограничениями на смежные контакты

• Автор: Шиганов, Александр Евгеньевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 124 с.

Общая характеристика работы
Основные определения и формулировка полученных результатов
Глава 1. Представление функций на основе специальных универсальных множеств. Некоторые вопросы суперпозиции схем 21 §1.1. Селекторные разбиения множества переменных булевых функций
§ 1.2. Универсальные множества функций и способы их построения 29 § 1.3. Некоторые вопросы суперпозиции и синтеза ориентированных контактных схем
Глава 2. Синтез оптимальных по весу ориентированных контактных схем с ограниченной полустепенью исхода
§ 2.1. Построение универсальных множеств для некоторых функций 40 § 2.2. Синтез ориентированных контактных схем на основе регулярных разбиений единичного куба и универсальных множеств
функций
§ 2.3. Оценки числа схем из некоторых классов ориентированных
контактных схем
Глава 3. Синтез оптимальных по сложности ориентированных контактных схем с ограниченной полустепенью исхода
§ 3.1. Некоторые сведения из теории полислов
§ 3.2. Верхние оценки сложности ориентированных контактных
схем с ограниченной полустепенью исхода
Глава 4. Синтез оптимальных по сложности ориентированных и итеративных контактных схем с ограниченной степенью 102 § 4.1. Верхние оценки сложности схем с ограниченной степенью
4.1.1. Синтез итеративных контактных схем
4.1.2. Синтез ориентированных контактных схем
§ 4.2. Нижние мощностные оценки функций Шеннона
Литература

Общая характеристика работы
Теория дискретных управляющих систем является важным разделом дискретной математики и математической кибернетики [16,24,33]. Она занимается изучением математических моделей дискретных преобразователей информации, то есть устройств, осуществляющих требуемое преобразование наборов входных значений в выходные. К числу примеров подобных устройств относятся различные виды интегральных схем.
Каждая математическая модель дискретного преобразователя информации, рассматриваемая в теории управляющих систем, характеризуется заданием набора базисных элементов, правил построения схем и законов их функционирования. Отметим, что схема традиционно задается графом определенного вида, а ее функционирование описывается системой функций алгебры логики (булевых функций). При этом говорится, что система функций реализуется схемой.
Одна из основных задач теории управляющих систем - задача синтеза, -состоит в построении для заданной системы функций К реализующей её схемы Е из заданного класса, на которой достигается оптимальное значение заданного «показателя» эффективности. В качестве показателя эффективности традиционно используется функционал В, который ставит в соответствие каждой схеме Е из заданного класса некоторое неотрицательное действительное число Е(Е), называемое её сложностью. Решение задачи синтеза для системы функций К1 состоит в нахождении схемы Е, обладающей минимальной сложностью среди всех схем из заданного класса, реализующих Р1.
Понятие полноты заданного класса управляющих систем означает, что схемами из этого класса можно реализовать любую булеву функцию. В этом случае можно определить сложность произвольной булевой функции, как минимальную сложность схемы, которая ее реализует. В теории дискретных управляющих систем рассматривается асимптотическая постановка задачи

функции ^ и схемы Тд2у ^, а также дополнительно переименовать выходы схемы Тд2у К При этом для г = 1 (I + 1) переменные из компонент
1 (2i+1) мощности 2* геометрического разбиения, порождённого разбиением D „
на множестве U, помечают дуги, исходящие из вершин дерева Т^и ^ глубины
(г — 1). Случай р = 21 полностью рассмотрен.
Теперь пусть р отлично от степени 2, тогда положим а = (р — 2Л-1)/2.
-Г) .. Г2Л—М
Возьмём функцию v , схему ТХи ' и разбиение Dx v , содержащее ком-
(2Л_1Л
поненты Y и >2, такие, что множество {Ух, У2} является ^ -селекторным. Для г — 1,2 разобьём множество У* на два непересекающихся множества Дд и Дд, такие, что
|Дгд| — Я, |^,21 = 2Л_2 — а.
(2^1—Ц
Применим лемму 2.3 к функциям ф = ф v ’ и фд>(/ и компонентам Zi = Zt, Z‘i = Дзд, а полученную в результате суперпозиции функцию и селекторное разбиение ее переменных обозначим через и соответственно. Пусть {фд|г = 1,2, j — 1 а} - использовавшаяся при этом система взаимно однозначных отображений множества переменных функций фи- Для каж-дого i ~ 1,2 и j = 1,,а присоединим к выходу схемы Тд ; с номером ((г — 1)2Л_1 + j) схему вида (2.5) и обозначим результат суперпозиции через Т^. При этом пометки входов присоединённых схем Tfl и пометки выходов схемы Гд2^ ^ с номерами ((г — 1)2Л_1 + j), где г — 1,2 и j = 1 а, снимаются, а выходы схем Тд2^ объявляются дополнительными выходами схемы
гп{р)
(р)
Нетрудно показать, что разбиение, порождённое разбиением Ид ' на множестве Прямых (соответственно итеративных) переменных функции фд?у, является геометрическим разбиением с основанием 2 кратности и (соответственно кратности (Л — 2)) высоты (h — 1) с v дополнительными компонентами (соответственно с (Л + 2) дополнительными компонентами), поэтому его энтропия не превосходит (2 log v + 5) (соответственно не превосходит (2 log Л + 7)).
Для завершения доказательства переименуем без отождествления переменные функции ф^ и схемы ТдР а также дополнительно переименуем вы-
(р)
ходы схемы Тд . □