Синтез схем контактного типа с ограничениями на смежные контакты тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Шиганов, Александр Евгеньевич

• Шиганов, Александр Евгеньевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Шиганов, Александр Евгеньевич

Введение

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

Основные определения и формулировка полученных результатов

Глава 1. Представление функций на основе специальных универсальных множеств. Некоторые вопросы суперпозиции схем

§ 1.1. Селекторные разбиения множества переменных булевых функций

§ 1.2. Универсальные множества функций и способы их построения

§ 1.3. Некоторые вопросы суперпозиции и синтеза ориентированных контактных схем

Глава 2. Синтез оптимальных по весу ориентированных контактных схем с ограниченной полустепенью исхода

§ 2.1. Построение универсальных множеств для некоторых функций

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

§ 2.3. Оценки числа схем из некоторых классов ориентированных контактных схем.

Глава 3. Синтез оптимальных по сложности ориентированных контактных схем с ограниченной полустепенью исхода

§ 3.1. Некоторые сведения из теории полислов.

§ 3.2. Верхние оценки сложности ориентированных контактных схем с ограниченной полустепенью исхода.

Глава 4. Синтез оптимальных по сложности ориентированных и итеративных контактных схем с ограниченной степенью

§ 4.1. Верхние оценки сложности схем с ограниченной степенью

4.1.1. Синтез итеративных контактных схем.

4.1.2. Синтез ориентированных контактных схем.

§ 4.2. Нижние мощностные оценки функций Шеннона.

Введение диссертации (часть автореферата) на тему «Синтез схем контактного типа с ограничениями на смежные контакты»

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

Теория дискретных управляющих систем является важным разделом дискретной математики и математической кибернетики [16,24,33]. Она занимается изучением математических моделей дискретных преобразователей информации, то есть устройств, осуществляющих требуемое преобразование наборов входных значений в выходные. К числу примеров подобных устройств относятся различные виды интегральных схем.

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

Одна из основных задач теории управляющих систем - задача синтеза, -состоит в построении для заданной системы функций F реализующей её схемы Е из заданного класса, на которой достигается оптимальное значение заданного «"показателя» эффективности. В качестве показателя эффективности традиционно используется функционал L, который ставит в соответствие каждой схеме Е из заданного класса некоторое неотрицательное действительное число Ь(Е), называемое её сложностью. Решение задачи синтеза для системы функций F состоит в нахождении схемы Е, обладающей минимальной сложностью среди всех схем из заданного класса, реализующих F.

Понятие полноты заданного класса управляющих систем означает, что схемами из этого класса можно реализовать любую булеву функцию. В этом случае можно определить сложность произвольной булевой функции, как минимальную сложность схемы, которая ее реализует. В теории дискретных управляющих систем рассматривается асимптотическая постановка задачи синтеза, которая была впервые предложена К. Шенноном [3]. В этой постановке вводится функция Ь{п) от натурального аргумента п, названная впоследствии функцией Шеннона, которая равна максимальной сложности булевой функции от п переменных при ее реализации схемами из заданного класса. Таким образом, Ь{п) характеризует сложность реализации самой «трудной» функции от п переменных в заданном классе схем. Далее изучается поведение функции L(n) при растущих значениях п.

В работе [3] был установлен порядок 271/п функции Шеннона LKC(n), связанной со сложностью контактных схем, где под сложностью понималось общее число контактов схемы. Асимптотическое значение 2п/п этой функции Шеннона было позже получено О. Б. Лупановым [19]. Изучение основных классов схем продолжилось в работах О. Б. Лупанова [20,21,23], где им была установлена асимптотика функций Шеннона, связанных с классом релейно-контактных схем, классом схем из функциональных элементов и формул над произвольным полным конечным базисом.

Среди различных моделей дискретных управляющих систем можно выделить классы систем «преобразующего» («функционального») и «проводящего» («контактного») типов. В системах «преобразующего» или «функционального» типа схемы обычно строятся по определенным правилам из элементов априорно заданного базиса. Каждый элемент базиса реализует некоторую булеву функцию (базисную функцию) и обладает определенной сложностью. Граф схемы задает последовательность операций суперпозиции базисных функций. Примерами управляющих систем «преобразующего» типа являются класс схем из функциональных элементов и класс формул, построенных из элементов конечного полного базиса (см., например, [33]) и др. При реализации булевых функций схемами из перечисленных моделей учитываются такие меры сложности, как общее число элементов в схеме, сумма сложностей элементов, из которых состоит схема, задержка или время срабатывания схемы, площадь (объем) геометрической реализации схемы на плоскости (в пространстве) и т.д.

В управляющих системах «проводящего» или «контактного» типа реализация булевых функций осуществляется с помощью передачи сигналов по ребрам (дугам) графа схемы, называемых контактами. При этом проводимостью контактов «управляют» внешние или специальные внутренние булевы переменные. К системам «контактного» типа относятся класс контактных схем [20], класс релейно-контактных схем [23] и др.

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

Настоящая работа посвящена решению задачи синтеза в асимптотической постановке для некоторых классов схем «контактного» типа при наличии различных ограничений на смежные контакты схем. Перечислим основные результаты асимптотической теории синтеза, связанные с изучением схем «контактного» типа, а также укажем известные подходы к введению структурных ограничений и определению сложности схем.

Напомним, что функция Шеннона для сложности схем из функциональных элементов над произвольным полным конечным базисом Б асимптотически равна рБ2п/п, где рв - некоторая константа, зависящая от базиса Б [20]. Класс формул [21] над базисом Б является частным случаем класса схем из функциональных элементов, в которых выход любого элемента может быть соединен только с одним входом другого элемента. В работе [21] О. Б. Лу-паповым была установлена асимптотика1 рв2п/ log п функции Шеннона для сложности формул над базисом Б. Таким образом, введение «жёстких» ограничений на,структуру схемы повлияло на порядок функции Шеннона. В работе [22] О. Б. Лупанов изучал класс схем из функциональных элементов над базисом Б, являющийся промежуточным между классом схем без ограничений [20] и классом формул [21]. В нем выход любого элемента мог соединятся не более, чем с d входами других элементов, где d - константа. Было установлено, что при определенных соотношениях на величину d, а также сложность и число входов элементов базиса Б, асимптотика соответствующей функции Шеннона по-прежнему составляет рв2п/п.

Класс параллельно-последовательных схем (тг-схем) (см., например, [24]) -частный случай класса контактных схем, допускающих, в частности, геомет

ХВ данной работе основание 2 у логарифмов опускается. рическую реализацию на плоскости. Воспользовавшись соответствием между 7Г-схемами и формулами над базисом {&;, V, ->}, в которых знаки отрицания встречаются лишь над символами переменных, а также методом синтеза [21], можно получить асимптотическое значение 2П/ logn функции Шеннона L"(n), связанной со сложностью булевых функций в классе 7г-схем (см. также [24]).

В работе [7] А. Д. Коршуновым было изучено асимптотическое поведение функций Шеннона L^c(n) и LJ(n), связанных со сложностью реализации булевых функций контактными схемами и 7г-схемами соответственно с ограничением Л на степени вершин схем. При А ^ 3 была установлена асимптотика функции Шеннона L*c(ri) вида д^271/п, а для функции Шеннона Щ(п) было доказано, что при любом А ^ 3 она асимптотически равна 2П/ log п.

Представление булевых функций с помощью двоичных решающих диаграмм (Binary Decision Diagrams, BDD) было впервые предложено в [1]. Отметим, что BDD можно рассматривать, как ориентированную контактную схему с одним истоком, являющимся входом, и двумя стоками, являющимися выходами, в графе которой отсутствуют ориентированные циклы и из каждой вершины, отличной от выходов, исходят две дуги с противоположными пометками вида a^afj. Под размером BDD понимается количество вершин BDD, отличных от выходов. В другой интерпретации [8], BDD можно рассматривать как программу, состоящую из операторов условного перехода, не содержащую циклов и имеющую две точки останова 0 и 1. В каждом операторе условного перехода вычисляется значение одной из входных булевых переменных и в зависимости от вычисленного значения осуществляется переход либо в другой оператор программы, либо в одну из точек останова. Результат работы программы на заданном наборе переменных определяется той точкой останова, в которую приведет последовательность операторов перехода (путь вычисления). Под размером программы понимается количество содержащихся в ней операторов. В работе [1] была получена нижняя асимптотическая оценка 2п~1/п и верхняя асимптотическая оценка 2п+2/п для функции Шеннона 5BDD(n), связанной с реализацией булевых функций в классе BDD. Позднее в [8] для этой функции была установлена асимптотика 2 п/п.

Отметим, что для получения верхней оценки функции Шеннона, связанной со сложностью реализации булевых функций в заданном классе схем, обычно предлагается специальный метод синтеза, а соответствующая нижняя оценка устанавливается из т.н. мощностного неравенства, предложенного К. Шенноном [3]. Точность получаемых оценок можно характеризовать их относительной погрешностью, равной отношению разности между верхней и нижней оценками функции Шеннона к ней самой [13]. Будем также рассматривать г(п)-нормированную относительную погрешность (г(п)-НОП) оценок некоторой функции Шеннона L(n), равную величине относительной погрешности оценок, умноженной на г (га), где г (га) - растущая функция от натурального аргумента га.

Для указанных выше оценок [19], [7] и [8] функций Шеннона LKC(ra), Ьд°(га) и <S'BDD(ra) соответственно величина га-НОП составляла 0(л/п). Оценки [21] и [7] функций Шеннона 1Л(га) и Щ(п) соответственно для классов 7г-схем, а также оценки функции Шеннона, связанной со сложностью формул над произвольным полным конечным базисом, были получены с log га-НОП вида O(loglogra).

Работа С. А. Ложкина [9] положила начало исследованиям, связанным с уточнением известных оценок функций Шеннона для основных классов схем. В частности, в [9] изучался класс ориентированных контактных схем, т.е. контактных схем из ориентированных контактов, и для соответствующей функции Шеннона LOKC(ra) были получены асимптотические оценки, имеющие га-НОП вида 0(1). В работе [11] С. А. Ложкиным был предложен термин асимптотические оценки высокой степени точности (АОВСТ), для обозначения оценок некоторой функции Шеннона L(n) с г(га)-НОП вида 0(1), где г (га) асимптотически равно отношению 2п/Ь(п).

В работах [10-14] был изложен общий подход к получению верхних асимптотических оценок функций Шеннона, который в т.ч. позволяет получать АОВСТ для функций Шеннона, связанных с реализацией булевых функций в основных классах управляющих систем. В частности, в этих работах были получены АОВСТ для сложности формул над произвольном полным конечным базисом, для сложности схем из функциональных элементов с ограничениями на ветвления выходов элементов определенного типа, а также для сложности т.н. функционально-проводящих схем, класс которых обобщает некоторые распространенные классы схем.

Отметим, методы синтеза [11] позволяют установить асимптотическое значение 2п~1/п функции Шеннона £икс(?г), связанной с реализацией булевых функций в классе итеративных контактных схем, который является модификацией класса релейно-контактных схем [23]. При этом полученные оценки будут иметь n-НОП вида O(l), т.е. будут являться оценками высокой степени точности.

В работе [25] рассматривались схемы из функциональных элементов над произвольным полным базисом Б и элементом задержки, в которых допускались ветвления выходов только элементов задержки, а параметр t задавал максимальное допустимое количество ветвящихся элементов задержки в схеме. При некоторых ограничениях на величину t — t(n) были получены АОВСТ для соответствующей функции Шеннона.

В последнее время активно изучаются различные подклассы BDD, в которых вводятся определенные ограничения на структуру BDD (см, например, [2,4,5,15]). Так, например, рассматриваются упорядоченные (строго) ^-считывающие BDD, в которых каждый путь вычисления разбивается на к непересекающихся сегментов, таких, что на каждом сегменте каждая переменная встречается не более одного раза (соответственно в точности один раз) и переменные встречаются в определенном порядке, одинаковом для всех сегментов и путей вычисления. Упорядоченные 1-считывающие BDD являются «удобной» структурой данных для внутреннего представления некоторых булевых функций в системах автоматизированного проектирования интегральных схем (см., например, [2]). Исследуются вопросы о возможности реализации булевых функций упорядоченными (строго) ^-считывающими BDD полиномиальной сложности, а также вопросы существования нижних экспоненциальных оценок для сложности булевых функций в этих классах BDD (см. [5]). Отметим, что при к ^ 2 асимптотическое значение 2п/п для сложности упорядоченных ^-считывающих и строго ^-считывающих BDD приводится в работе [15]. При этом полученные оценки имеют n-НОП вида o(logn). Там же получены асимптотические оценки для сложности BDD общего вида с n-НОП вида o(logn).

В работе [26] описан класс схем контактного типа, представляющий собой математическую модель интегральных схем на дополняющих МОП-транзисторах (КМОП схем). В этой модели замыкающий (соответственно размыкающий) контакт переменной Х{ соответствует n-МОП или р-МОП транзистору, на затвор которого подаётся значение Xi (соответственно а контактная схема описывает соединения между истоками и стоками транзисторов. Отметим, что одно из естественных ограничений, которое можно вводить в подобных моделях, является ограничение степеней вершин контактной схемы. В работе [26] установлена асимптотика 271+1/п функции Шеннона, связанной со сложностью КМОП схем, для случая, когда контакты разрешается помечать только символами «внешних» булевых переменных. В другой модели КМОП схем [6] допускается использование в качестве пометок контактов специальных «внутренних» булевых переменных, реализуемых в вершинах схемы. Для соответствующей функции Шеннона в работе [6] получена асимптотика вида 2п/п.

Перейдем к описанию классов схем, рассматриваемых в диссертации. Начнем с описания классов ориентированных контактных схем, в которых ограничена одна из полустепеней вершин.

В данной работе вводится класс ориентированных контактных схем с ограничением Л на полустепень исхода вершин схемы и ограничением v на количество различных булевых переменных, которые используются среди пометок исходящих дуг. При таком определении произвольная BDD принадлежит указанному классу схем при А.= 2, v = 1. Под сложностью ориентированной- контактной схемы понимается, как обычно, число контактов в ней. В работе разработаны новые методы синтеза, позволяющие установить асимптотические оценки сложности схем из класса , при v = Л, а также при Л = 2 и v — 1, имеющие n-НОП вида log log п + O(l). Предложенные методы синтеза позволяют также получить асимптотические оценки сложности BDD и сложности упорядоченных /с-считывающих BDD при k ^ 4 с 77.-НОП вида log log п + O(l). Таким образом, получены более точные, по сравнению с работой [15], асимптотические оценки соответствующих функций Шеннона для классов BDD.

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

В первом подходе для произвольных действительных положительных чисел w' и w", где w" > w', вес вершины v ориентированной контактной схемы Е полагается равным w', если в v заходит не более одной дуги и и>" иначе. Вес схемы равен сумме весов её вершин. Для функций Шеннона, связанных с весом схем класса весом BDD, а также весом упорядоченных (строго) ^-считывающих BDD при k ^ 2 в работе получены асимптотические оценки, являющиеся оценками высокой степени точности.

Следующая постановка задачи синтеза, предлагаемая в работе, состоит в том, что сложность булевой функции / определяется как минимальная сложность схемы из класса^/(Л.гУ>-°кс) реализующей / и имеющей не более t вершин, в которые заходит более одной дуги. При некоторых ограничениях на t ~ t(n) в работе получены оценки высокой степени точности для соответствующих функций Шеннона, связанных с классом и классами BDD.

Теперь опишем рассматриваемые в диссертации классы схем контактного типа, в которых накладывается ограничение на степени вершин. Отметим, что используя методы синтеза [7] можно получить асимптотическое значение j~2n/n (верхнюю оценку ^2п/п) для функции Шеннона L°KC(n) (соответственно L"KC(n)), связанной со сложностью ориентированных контактных схем (соответственно итеративных контактных схем), в которых степени вершин ограничены константой Л. При этом оценки для функции Шеннона L™(n) можно получить с п-НОП вида 0(у/п).

Метод синтеза, предложенный в настоящей работе позволяет установить асимптотические оценки функции Шеннона L°KC(n), для которых п-НОП составляет logn + log logn + 0(1). Также в работе описан новый асимптотически оптимальный метод синтеза, из которого вытекает асимптотика д^-2п1/п функции Шеннона L"KC(n). При этом оценки, полученные для функции Шеннона L"KC(n) имеют п-НОП вида 0{^Jn\ogn).

Основные результаты работы представлены в [17,18,28-32].

Основные определения и формулировка полученных результатов

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

Напомним основные понятия теории графов.

Набор Е вида (G,Vr, V"), где G = (V, Е) - граф с множеством вершин V и множеством ребер Е, а V' и V" - упорядоченные выборки из V длины р и q соответственно называется (р,ц)-сетъю. При этом i-я вершина выборки V' (соответственно выборки V") называется i-м входным полюсом или входом (соответственно i-м выходным полюсом или выходом) сети Е. Будем называть сеть Е = (G, VV") ориентированной (соответственно неориентированной) если граф G является ориентированным (соответственно неориентированным).

Число ребер, инцидентных вершине v графа G, т.е. степень вершины v, будем, как обычно, обозначать через deg^v). Пусть v - вершина ориентированного графа G, тогда обозначим через degj(v) (соответственно deg^(v)) полустепень захода вершины v, т.е. число дуг, заходящих в v (соответственно полустепень исхода вершины v, т.е. число дуг, исходящих из v). Напомним, что вершина v ориентированного графа G называется стоком (соответственно истоком), если deg^(v) — 0 (соответственно degj(v) = 0).

Буквами булевой переменной Х{ будем называть Х( и Xi.

Неориентированная сеть Е с входами а\,. ,ар, выходами &i,.,bq, в которой все ребра помечены буквами переменных xi,.,xn, называется (р, д)-контактной схемой ((р, q)-KC) от переменных xi,. ,хпк обозначается E(#i,., хп) или E(ai,., ар] &i,., bq\х\,., хп). Ребра КС называются контактами. При этом контакт, помеченный буквой Х{ (буквой х\) называется замыкающим (соответственно размыкающим). Обозначим множество всех контактных схем через UKG.

Напомним, что в графе G = (V:E) последовательность, состоящая из ребер ei,. ,еп, где ег- = (vi,vi+i) G Е, называется (vi — vn+i) путём графа G. Если все ребра пути различны, то он называется цепью, а если, кроме того, различны все его вершины, то - простой цепью. Цепь, начальная и конечная вершина которой совпадают, называется циклом.

Пусть Е - КС от переменных х\,., хп и пусть vi, V2 ~ вершины Е. Определим функцию проводимости gVuV2(x\,. ,хп) между вершинами vi и vi, как булеву функцию, которая равна 1 на наборе а — (о^,., ап) € {0,1}п тогда и только тогда, когда в схеме Е существует (vi — V2) цепь, состоящая из контактов, помеченных буквами х^1,., х%п ■ При этом будем говорить, что функция gVl,v2 реализуется между вершинами vi,V2- Отметим, что функции проводимости gVl,v2 и gV2,vl совпадают.

Положим по определению, что если v - вершина (1, т)-КС Е, то в v реализуется функция проводимости между входом и вершиной v, и что Е реализует набор функций (Д,., /то), где Д - функция проводимости между входом и г-м выходом схемы Е, г = 1,. ,ш. Также будем говорить, что (р, д)-КС E(sci,., хп) реализует матрицу из р строк и q столбцов, состоящую из булевых функций от переменных xi,.,xn так, что на пересечении г-й строки и j-ro столбца стоит функция проводимости между г-м входом и j-м выходом схемы Е, г = 1,. ,р, j = 1,., q. Схемы Е' и Е", реализующие матрицы F' и F" соответственно, называются эквивалентными, если2 F' = F".

Аналогично определяется структура и функционирование ориентированной контактной схемы (ОКС) с тем исключением, что граф ОКС является ориентированной сетью. При этом отметим, что если v\ и г>2 - различные вершины ОКС Е, то в общем случае функции проводимости gVuv2 и 9v2,vх могут не совпадать. Обозначим через Ыокс множество всех ОКС.

Пусть р ^ 1. Назовем р-входовой двоичной решающей диаграммой (p-BDD) любую (р, 2)-ОКС Е(я1,., хп), граф которой не содержит ориентированных циклов, входы Е и только они являются истоками, выходы являются стоками и из каждой вершины Е, отличной от выходов, исходит-пара противоположных контактов, помеченных буквами Х{ и х^ где г е [1, п]. При этом выходы p-BDD Е помечены 0 и 1, и считается, что Е реализует столбец функций проводимости между входами и выходом, помеченным 1.

Обозначим через UBDD класс всех ОКС, являющихся p-BDD для некоторого р ^ 1. Для удобства в обозначении произвольной схемы Е из класса ubdd будем иногда опускать указание числа входов схемы и называть схему Е двоичной решающей диаграммой (BDD). Отметим, что определение 1-входовой BDD совпадает с традиционным определением двоичной решающей диаграммы или ветвящейся программы (см., например, [4,5]).

Будем также рассматривать BDD с некоторыми структурными ограничениями. Зафиксируем порядок булевых переменных xi,. ,хп. Назовем BDD Е от переменных xi,.,xn упорядоченной (строго) k-считывающей с по

2Равеиство булевых функций, как обычно, будем рассматривать с точностью до добавления или изъятия несущественных переменных. рядком переменных х\,. ,хп, если произвольная простая цепь из входа в выход Е разбивается на к сегментов, таких, что:

1. на каждом сегменте переменные встречаются в порядке xi,. ,хп]

2. на каждом сегменте каждая переменная встречается не более одного раза (соответственно в точности один раз).

Множество всех упорядоченных ^-считывающих (соответственно строго fc-считывающих) с порядком ., хп BDD обозначим через Uk~OBDD(x 1,., хп) (соответственно через Uk-SOBDD(xi,., хп)). Введем также класс Uk-°BDD (Uk-S0BDD), содержащий все упорядоченные /с-считывающие (соответственно строго к-считывающие) BDD.

Пусть в (1, т)-КС Е(а; b\,., Ът\ х\,., хп) переменная Xi входит без отрицаний, а функция /j, реализуемая в выходе bj, не зависит от переменной Х{. В этом случае определим операцию присоединения переменной Х{ к выходу bj, в результате которой вершине, помеченной bj, сопоставляется внутренняя переменная и, выходная пометка bj снимается, а все пометки Х{ заменяются на пометку и. Полученная таким образом схема Е' зависит от переменных х\,., Xi-i,Xi+i,. • •, хп, имеет входной полюс а и выходные полюса Ь\,., ., bm. Пусть v - вершина схемы Е, и пусть gatV - функция, которая в ней реализуется, тогда по определению положим, что в схеме Е' в вершине v реализуется функция ga,v(xъ • • • > ^г-ъ fji xi+ь • • • > хп)- Функционирование схемы Е' представляет собой набор функций, реализуемых в ее выходах. Теперь пусть 1 < ji < . < ^ т и 1 ^ i\ < . < ^ п -наборы индексов и пусть переменные х^,., Х{к входят в схему Е без отрицаний, а каждая из функций fjt,., fjk не зависит существенно от переменных а. ,Xik. В этом случае определим операцию одновременного присоединения переменных х^,., Х{к к выходам bj1,., bjk соответственно, состоящую в последовательном выполнении операций присоединения переменной х^ к выходу bjx, ., переменной Х{к к выходу bjk. При этом выходу bjt сопоставляется внутренняя переменная Ujt, t = 1,. ,к. Нетрудно убедиться в том, что при выполнении указанных условий на функции ,., fjk введённая операция определена корректно и её результат не зависит от порядка, в котором применяются однократные операции присоединения переменной к выходу. Схема, полученная в результате присоединения переменных к выходам, называется итеративной контактной схемой (ИКС) на базе КС Е. Множество всех ИКС обозначим через ЫИКС.

Для КС (ОКС) Е и натурального Л обозначим через М>А(Е) множество вершин v схемы Е, таких, что degs(i>) > Л. Для ОКС Е положим М>Л(Е) (соответственно М~Л(Е)) - множество вершин v схемы Е, таких, что deg£(i;) > Л (соответственно deg^f) > Л). Если £' - ИКС на базе КС Е, то положим М>Л(Е') = М>л( Е).

Для вершины v ОКС Е обозначим через число различных булевых переменных, которые встречаются среди пометок дуг, исходящих из v. Пусть г/(Е) = тах^(^)) где максимум берется по всем вершинам Е.

Обозначим через множество всех ОКС Е, таких, что множество М~Л(Е) является пустым и z/(E) ^ и. Таким образом, класс содержит схемы, в которых из каждой вершины исходит не более Л дуг, а среди пометок этих дуг используются буквы не более, чем г/ различных булевых переменных. Отметим, что из введённых определений следует, что WBDD С

Пусть Е - схема, принадлежащая одному из введенных выше классов ЫА, тогда сложностью 1/(Е) схемы Е называется число контактов в Е. Отметим, что если Е является BDD, то L(Е) - четное и число вершин Е равно величине (L(E)/2 + 2). В предположении, что класс

UA является полным, т.е. что любую булеву функцию можно реализовать некоторой схемой из класса ЫА, для булевой функции / определим величину LA(f), называемую сложностью f относительно функционала ЬА, как минимальное значение величины L(Е) на множестве тех схем Е из ЫА, которые реализуют /. Для натурального п определим, как обычно, функцию Шеннона ЬА(п)

LA(n) = max LA(f). f(xi,.,xn)

Пусть дополнительно известно, что для натурального Л множество схем Е класса ЫА, таких, что степени вершин Е не превосходят Л, является полным. Тогда для булевой функции / определим ЬА(/), как минимальное значение величины L(Е) на множестве схем Е из ЫА, реализующих /, таких, что М>Л(Е) = 0. Введём соответствующую функцию Шеннона LA (п)

L?(n) = max LA{f).

J(Xi,.,Xn)

Пусть г; - вершина ОКС Е. Для положительных действительных величин w' и го", где w" > w', введем понятие веса Ww^w»{v) вершины v следующим образом: w' 1 degJO) < 1, w\ degj(i/)>l.

Вес WW'iW"(E) схемы E есть сумма весов вершин Е.

Пусть UA - один из введенных выше классов ОКС с ограничением на полу степени исхода вершин. В предположении, что класс ЫА является полным, для булевой функции / определим величину WA,w„(f), называемую весом / относительно функционала WA, w„, как минимальное значение величины WW')Wit(Е) на множестве тех схем Е из ЫА, которые реализуют /. Пусть для натурального параметра t подмножество схем Е класса UA, таких, что IM+^E)! < t, является полным. Тогда определим LA(f, £), как минимальное значение величины L(Е) на множестве схем Е из ЫА1 реализующих /, таких, что IM+^E)! ^ t. Введём функции Шеннона WA, „(п) и LA(n,t)

Ww>,w»{n) = ™ах WA,iW„(f), f{xi,.,xn)

LA(n,t) = max LA{f,t). f(xi,.,xn)

Точность оценок некоторой функции Шеннона L{n) будем характеризовать их относительной погрешностью (ОП), т.е. отношением разности между верхней и нижней оценками функции Шеннона к ней самой [13]. Также введём n-нормированную относительную погрешность (n-НОП) оценок функции Шеннона L{n), равную величине относительной погрешности, умноженной на п. Асимптотическими оценками функции Шеннона L(n) высокой степени точности будем называть оценки с n-НОП вида 0(1).

Перечислим основные результаты для введенных функций Шеннона. Первая серия результатов относится к поведению функций Шеннона для веса ориентированных контактных схем и BDD.

Теорема 1. Для любых натуральных X и и, где а таксисе положительных вещественных величин w' и w", где w" > w', при п = 1,2,. справедливо3

Теорема 2. Для любого натурального k ^ 2, а также положительных вещественных величин w' и w", где w" > w', при п = 1,2,. справедливо 0) fb\ /I / п \ п w^(n) = 0*2. (г + 21ogn±0(l)^ (4)

W.W . .

П V 71

Отметим, что полученные асимптотические оценки (1)-(4) являются оценками высокой степени точности.

В диссертации также установлено, что если в определении веса WW>JW»(E) ОКС Е учитывать с весом w" вершины, в которые заходит более d дуг, где d - натуральная константа, а все остальные вершины учитывать с весом гс/, то асимптотика соответствующих функций Шеннона по-прежнему составляет 2п/п для класса и(х>иУокс и w' 2п/п для классов BDD.

Перечислим результаты для функций Шеннона, связанных со сложностью ориентированных контактных схем и BDD при наличии растущего ограничения t = t(n) на число вершин с полустепенью захода больше 1.

Теорема 3. Для любых натуральных X и и, где при п — 1,2,. и t = t{n), гдеА logt{n) = Г2(тг) и t(n) не превосходит 2п/п2, справедливо

L<V>-okc( t) = * . , , 2" т- (l ± О (-)).

А-1 log^ + ^lognV \nJJ

3Равенство r(n) — pin) ±0{q{n)) означает, что |r(rc) — p(n)| = 0(g(n)).

4Равенство p(n) = f2(q(n)) означает, что р(п) = 0(q(n)) и д(тг) = 0(р(тг)).

Теорема 4. Для любого натурального к ^ 2 при п = 1,2,. и £ = где £(п) —► оо при тг —> оо и t(n) не превосходит 2п/п2, справедливо и если, кроме того, log t(n) = шо

Отметим, что асимптотические оценки, приведенные в теореме 3 и в теореме 4 для класса BDD и класса упорядоченных ^-считывающих BDD при k ^ 2, являются оценками высокой степени точности.

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

Теорема 5. Для любых натуральных X и и, где при п = 1,2,. справедлива нижняя оценка

А-1 п1 п / а также в случае р = 1, X — 2 ив случае и — А при п = 1,2,. справедлива верхняя оценка ь<А,,)-окс(п) ^ . ^ Л + Wlogn + loglogn + Q(l)\ Л — 1 п \ п )

Теорема 6. Для любого натурального k ^ 4 при п = 1,2,. справедливы оценки

ОП+1 / / 1 \ \ ОП+1

-—(l-of-l ) <Lfc-0BDD' ' 1 п V \п J / + loglogn + 0(m п \ п J

Легко видеть, что асимптотические оценки, приведенные в теоремах 5, 6 имеют п-НОП вида log log п + 0(1).

Наконец, приведем результаты для функций Шеннона, связанных со сложностью итеративных и ориентированных контактных схем, в которых степени вершин ограничены константой А.

Теорема Т. Для любого натурального А ^ 3 при п — 1,2,. справедливы оценки

LoKc(n) ^ Л • ^ f 1 4- -Alogrc + loglogn + Q(l) А — 2 п I п

Таким образом, оценки для функции Шеннона L°KC(n) имеет n-НОП вида log n -f log log п + O(l).

Теорема 8. Для любого натурального А ^ 3 при п = 1,2,. справедливы оценки

А 22 / logn - От А . £ /1 + 0 flgSg) V

2А — 2 п \ п J 2А — 2 п \ \ \/п J J

В диссертации также установлено, что нижние оценки, перечисленные в теоремах 1-8, справедливы для сложности и веса - относительно соответствующих функционалов, - почти всех булевых функций от п переменных.

Отметим, что методы синтеза, используемые в диссертации при доказательстве верхних оценок теорем 1, 3 и 5 для класса ОКС с ограниченной полустепенью исхода, могут быть применены для получения аналогичных результатов в модели ОКС с ограниченной полустепенью захода.

Дальнейшее изложение будет построено следующим образом. Глава 1 содержит вспомогательные определения и утверждения, необходимые для получения верхних оценок функций Шеннона. В ней вводятся такие понятия, как селекторное разбиение переменных булевой функции, каноническая матрица булевой функции, универсальное множество функций и др. Там же приводятся простейшие методы синтеза схем. В главе 2 описывается метод синтеза схем из класса ^/(Л'г/)-°кс На основе регулярных разбиений единичного куба и универсальных множеств функций, позволяющий установить верхние оценки в теоремах 1-4. Также в главе 2 доказываются верхние оценки числа схем определённого вида из класса и классов BDD, которые затем используются при получении мощностных неравенств, позволяющих установить нижние оценки в теоремах 1-6. В третьей главе описан новый метод синтеза для получения верхних оценок теорем 5 и 6. Доказательство верхних и нижних оценок теорем 7 и 8 ведётся в главе 4 диссертации. При этом доказательство верхней оценки теоремы 7 основано на использовании метода синтеза главы 3, в то время как верхние оценки теоремы 8 получены с использованием нового метода синтеза.

Список литературы диссертационного исследования кандидат физико-математических наук Шиганов, Александр Евгеньевич, 2010 год

1. Lee С. Y. Representation of switching circuits by binary-decision programs. Bell. Sys. Tech. J., vol. 38, 1959. - pp. 985-999.

2. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD Foundations and Applications. Springer-Verlag, 1998. - p. 267.

3. Shannon С. E. The synthesis of two-terminal switching circuits. Bell Syst. Techn. J., 1949, v.28, N-l, pp. 59-98.

4. Wegener I. The complexity of Boolean functions. Teubner (Stuttgart)/Wiley (Chichester), 1987. p. 457.

5. Wegener I. Branching programs and binary decision diagrams. SIAM Publisher, 2000. p. 408.

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

7. Коршунов А. Д. Об асимптотических оценках сложности контактных схем заданной степени // Дискретный анализ. Сб. науч. тр. Вып. 5. Новосибирск: Ин-т математики СО АН СССР, 1965. С. 35-63.

8. Кузьмин В. А. Оценка сложности реализации булевых функций программами простого типа. // Методы Дискретного анализа, 29, 1976. -С. 11-39.

9. Ложкин С. А. О синтезе ориентированных контактных схем // Вестник МГУ. Вычислительная математика и кибернетика. 1995. - №2. - С. 3642.

10. Ложкин С. А., О синтезе некоторых типов схем на основе сдвиговых разбиений, порожденных универсальными матрицами // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1996. М. С. 62-69.

11. Ложкин С.А. Асимптотические оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука, 1996. С. 189-214.

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

13. Ложкин С. А., О сложности реализации произвольных булевых функций в некоторых классах BDD // Труды Международной школы-семинара "Дискретная математика и математическая кибернетика" (Ратмино, 31 мая 3 июня 2001 г.). - М.: МАКС Пресс, 2001. - С. 18-19.

14. Ложкин С. А. Лекции по основам кибернетики. М.: Изд-во МГУ, 2004. -256 с.

15. Лупанов О. Б. О синтезе контактных схем // ДАН СССР. -1958. Т. 119, М. - С. 23-26.

16. Лупанов О. Б. Об одном методе синтеза схем // Известия вузов, Радиофизика. 1958. - Т. 1, т. - С. 120-140.

17. Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960. - С. 6180.

18. Лупанов О. Б. Об одном классе схем из функциональных элементов (формулы с конечной памятью) // Проблемы кибернетики. 1962. Вып. 7. С. 61-114.

19. Лупанов О. Б. О сложности реализации функций алгебры логики релейно-контактными схемами // Проблемы кибернетики. Вып. 11. М.: Наука, 1964. - С. 25-48.

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

21. Никитин А. А. О сложности реализации функций алгебры логики в некоторых классах автоматных схем // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1999. №3. С. 4149.

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

23. Ху. Т. Целочисленное программирование и потоки в сетях. М.: Мир -1974. - 520 с.

24. Шиганов А. Е. Асимптотические оценки высокой степени точности для сложности схем из некоторых классов // Сборник тезисов лучших дипломных работ 2006 года. М.: Издательский отдел фак-та ВМиК, 2006, С. 73-74

25. Шиганов А. Е. О сложности ориентированных контактных схем с ограниченной полустепеныо исхода // Проблемы теоретической кибернетики. Тезисы докл. XV Международной конф. Казань: Отечество, 2008. С. 133.

26. Шиганов А. Е. О синтезе ориентированных контактных схем с некоторыми ограничениями на смежные контакты // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2009. т. С. 46-52.

27. Шиганов А. Е. О сложности ориентированных контактных схем с ограниченной полустепенью исхода // Учен. зап. Казан, ун-та. Сер. Физ.-матем. науки. 2009. - Т. 151, кн. 2 - С. 164-172.

28. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. -384 с.