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

1 Введение

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

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

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

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

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

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

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

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

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

§3. Асимптотические оценки функций Шеннона для случая с.ф.э. на транзисторах

§4. Случай всюду определенного базиса дляф.э. на транзисторах

ДОБАВЛЕНИЕ. Асимптотические оценки функций Шеннона с учетом канальной глубины.

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

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

Шеннона L(n), которая равна сложности оптимальной реализации самого сложного оператора из рассматриваемого класса.

В настоящей работе рассматривается класс с.ф.э., являющийся математической моделью схем на КМОП-транзисторах, которая близка к модели, описанной в работах А. А. Сапоженко и С. А. Ложкина [16], а также О. М. Касим-Заде [11]. Схемы строятся из многозначных функциональных элементов (ф.э.), на выходе которых, помимо булевских значений О (низкий потенциал) и 1 (высокий потенциал), допускаются следующие неопределенности:

1) * - "полезная" неопределенность типа "высокий импеданс", или "отключенное состояние", когда выход элемента отрезан от источников питания;

2) 0 - "плохая" неопределенность типа "короткое замыкание", когда в элементе существует проводящая цепь между источниками питания с высоким и низким потенциалом;

3) 1' (0') - "плохая" неопределенность типа "слабое значение", когда источник питания с высоким (низким) потенциалом соединен с выходом цепью, лучше проводящей, наоборот, низкий (соответственно, высокий) потенциал.

С формальной точки зрения высокий импеданс на выходе схемы или ф.э. понимается как неоднозначность в допустимой конфигурации для данной схемы или ф.э., или, иначе, как третье значение. Тем самым неопределенность типа высокий импеданс близка к значению 2 у В. В. Тарасова [17] и отличается от неопределенности недоопределенной функции у JI. А. Шоломова [19] и А. Е. Андреева [1], где булевская функция от п переменных задана на некотором подмножестве множества {0, Х}п , а ее значения на остальных входных наборах хотя и неизвестны, но это опять-таки либо О, либо 1. Короткое же замыкание играет в рассматриваемых в диссертации схемах роль обычной неопределенности как в случае частичной функции у Р. В. Фрейвалда [18] . В отличие от всех вышеназванных работ, существуют исследования, рассматривающие три и более значений на выходах КМОП-схем как определенные значения /t-значной логики, например, у Ю. А. Виноградова [3,4] .

Заметим, что в данной работе, в отличии от [18], короткое замыкание считается нежелательным значением и не синтезируется на выходах схем. В то же время значение похожее на третье значение в [17], рассматривается как допустимое при изучении вопросов полноты и синтеза.

В диссертации изучается класс многозначных с.ф.э., то есть схем из многозначных ф.э., при построении которых используется обычная операция суперпозиции, а также объединение выходов ф.э. внутри схемы по типу проводного "или". При этом допускается появление на выходах ф.э. неопределенностей всех рассматриваемых типов. Подклассом этого класса является класс непротиворечивых высокоимпедансных с.ф.э., в которых разрешено появление на выходах схемы только булевских значений и высокого импеданса. Каждая такая схема из ф.э. с « входами и w выходами реализует всюду определенный высокоимпедансный оператор (при w=l - функп цию), который отображает множество {0,1} во множество т

0,1,*} . Важным подклассом класса всюду определенных высокоимпедансных операторов (функций) является класс булевских операторов (функций).

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

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

1. Виноградов Ю.А. О синтезе четырехзначных квазикомплиментарных МОП-схем. Математические вопросы кибернетики: вып. 8. - М., Наука, 1999. - С. 298-300.

2. Долгополова А.В. Асимптотическое поведение функции Шеннона для одного класса схем из функциональных элементов // Вестник московского университета. Сер. 15. Вычислительная математика и кибернетика. М., 1997. № 1. С. 37-41.

3. Долгополова А. В. О синтезе схем из функциональных элементов с неопределенностями двух типов. М., 1995. Деп. в ВИНИТИ 06.07.95 № 2032 В95.

4. Долгополова А.В. О сложности схем из функциональных элементов на транзисторах // Проблемы теоретической кибернетики. Тезисы докладов XI Всесоюзной конференции (сентябрь 1990 г.,г. Волгоград). Волгоград, 1991, часть I (2). - С. 39.

5. Долгополова А.В. О сложности схем из функциональных элементов на транзисторах // Сборник трудов семинара по дискретной математике и ее приложениям (Москва, февраль 1990 г.). М.; Изд-во механико-математич. факультета МГУ, 1997. - С. 110-112.

6. Касим-Заде О.М. О сложности реализации булевых функций в одной модели электронных схем // Матем. Вопр. Киберн. М., 1989.Вып. 2.

7. Коршунов А.Д. О нижних оценках сложности контактных схем, реализующих попарно ортогональные функции алгебры логики // Дискретный анализ. Новосибирск, 1964. Вып. 2. С. 42-47.

8. Ложкин С. А. Асимптотические оценки высокой степени точности для сложности управляющих систем // Диссертация на соискание ученой степени доктора ф.-м. наук. М., МГУ. 1997.

9. Лупанов О.Б. Асимптотические оценки сложности управляющих систем // Изд-во МГУ, 1984.

10. Лупанов О.Б. Об одном подходе к синтезу управляющих систем принципе локального кодирования // Проблемы кибернетики; Сб. Статей. Вып. 14 - М. Наука, 1965. - С. 31-110.

11. Сапоженко А.А., Ложкин С.А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах -МОПД- схемы // Микроэлектроника. 1983. - Т. 12, вып. 1.С. 42-47.

12. Тарасов В. В. Критерий полноты для не всюду определенных функций алгебры логики // Проблемы кибернетики; Сб. Статей. Вып. 30, М., Наука, 1975. С. 319-325.

13. Фрейвалд Р.В. О полноте частичных функций алгебры логики // ДАН СССР. 1966. - Т. 167, Т 6. - С. 1249-1250.

14. Шоломов Л. А. О реализации не до определенных булевых функций схемами из функциональных элементов // Проблемы кибернетики; Сб. Статей. Вьш. 21, М., Наука, 1969. С. 215-226.

15. Яблонский С.В. Введение в дискретную математику, М. Наука. 1979.РИСУНКИ.