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

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

Оглавление
1 Введение

§1. Общая характеристика работы

§2. Основные понятия и обзор результатов

2 Проблема полноты и задача синтеза для класса высокоимпедансных схем из функциональных элементов

§1. Модель. Алгоритм распознавания полноты

§2. Верхние оценки функций Шеннона

§3. Нижние оценки функций Шеннона

3 Синтез схем из ф.э. на транзисторах

§1. Математическая модель с.ф.э. на транзисторах

§2. Соотношения мевду М(Е) и М(Е) для схем из ф.э. на

транзисторах в различных базисах
§3. Асимптотические оценки функций Шеннона для случая
с.ф.э. на транзисторах
§4. Случай всюду определенного базиса для с.ф.э.
на транзисторах
ДОБАВЛЕНИЕ. Асимптотические оценки функций Шеннона с учетом канальной глубины.
СПИСОК ЛИТЕРАТУРЫ
РИСУНКИ

Глава 1. Введение.
§1. Общая характеристика работы.
Основной задачей теории синтеза управлякзцих систем является изучение вопросов оптимальной реализации функций алгебры логики (ф.а.л.), или булевских функций, различными классами управляющих систем. Настоящая работа посвящена решению этой задачи для одного из традиционных классов управляющих систем - схем из функциональных элементов (с.ф.э.), но для более широкого класса функций - функций, принимающих, наряду с булевскими значениями, "полезное" неопределенное третье значение и допускающих, вообще говоря, "плохую" неопределенность двух типов. Такие схемы являются математической моделью некоторых видов современных электронных схем и, в частности, схем на КМОП-транзисторах (дополняющих транзисторах типа металл - окисел - полупроводник). Изучается также вопрос о перспективности использования с.ф.э. указанного вида для реализации ф.а.л.
Напомним вначале, что с.ф.э. строится по определенным правилам из элементов базиса - фиксированного (конечного или бесконечного) набора "элементарных" с.ф.э. Каждая с.ф.э. характеризуется неотрицательным действительным параметром, называемым сложностью, и тем функциональным оператором, который она реализует. Эти характеристики однозначно определяются строением с.ф.э. и априорно заданными характеристиками элементов базиса. Сложность с.ф.э., например, есть сумма "весов" (т.е. сложностей) всех элементов базиса, составляющих схему. Базис называется полным в некотором классе операторов, если любой оператор из этого класса можно реализовать схемой, построенной в данном базисе. Любой функциональный оператор реализуется, как правило, несколькими с.ф.э., из которых можно выбрать схему, оптимальную по сложности. Обычно изучается поведение так называемой функции

Шеннона Цп), которая равна сложности оптимальной реализации самого сложного оператора из рассматриваемого класса.
В настоящей работе рассматривается класс с.ф.э., являющийся математической моделью схем на КМОП-транзисторах, которая близка к модели, описанной в работах А. А. Сапоженко и С. А. Ложкина [16], а также О. М. Касим-Заде [11]. Схемы строятся из многозначных функциональных элементов (ф.э.), на выходе которых, помимо булевских значений 0 (низкий потенциал) и 1 (высокий потенциал), допускаются следующие неопределенности:
1) * - "полезная" неопределенность типа "высокий импеданс", или "отключенное состояние", когда выход элемента отрезан от источников питания;
2) 0 - "плохая" неопределенность типа "короткое замыкание", когда в элементе существует проводящая цепь между источниками питания с высоким и низким потенциалом;
3) 1' (0') - "плохая" неопределенность типа "слабое значение", когда источник питания с высоким (низким) потенциалом соединен с выходом цепью, лучше проводящей, наоборот, низкий (соответственно, высокий) потенциал.
С формальной точки зрения высокий импеданс на выходе схемы или ф.э. понимается как неоднозначность в допустимой конфигурации для данной схемы или ф.э., или, иначе, как третье значение. Тем самым неопределенность типа высокий импеданс близка к значению 2 у В. В. Тарасова [17] и отличается от неопределенности недоопределенной функции у Л. А. Шоломова [19] и А. Е. Андреева [1], где булевская функция от п переменных задана на некотором подмножестве множества {0,1}п , а ее значения на остальных входных наборах хотя и неизвестны, но это опять-таки либо 0, либо 1. Короткое же замыкание играет в рассматриваемых в диссертации схемах роль обычной неопределенности как в случае час-

Теорема 2.2.2. Для любого конечного базиса Б из многозначных ф.э., полного в классе Э7 , верно:

ЬБ(п)<рБ 1оё23 .

Доказательство.
Воспользуемся методом равномерного кодирования [15] .
ст- * -
Пусть / (х0 , , хп_{) - произвольная функция из 3 . Разо-
бьем набор всех значений функции / (длины 2” из 0,1 и *) на куски по к значений, где к - некоторое натуральное число (последний кусок, быть может, длины к '<к) . Каждый такой кусок длины к закодируем произвольным образом двоичной последовательностью длины / (последний кусок, быть может, длины /' чтобы 2і - о (21) < 3А < 21 . Отсюда получаем 1->1оё2Ъ,
< (2.2.3)

> Iog2 3, при I и к ->■ со.

Введем некоторые понятия теории чисел (см., например, [2], с.13-17). Пусть а - произвольное вещественное число, а д1 - целая часть числа а : цх = [а] . Тогда, если а - не целое, его мож-

но представить в виде а= q, +— , а, > 1 . Точно так же выбирается

д., = [(х7] и т.д. Если а - иррациональное, то этот процесс можно неограниченно продолжить: