О сложности мультиплексорных функций в некоторых классах схем

Власов, Никита Вадимович

О сложности мультиплексорных функций в некоторых классах схем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Власов, Никита Вадимович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «О сложности мультиплексорных функций в некоторых классах схем»

Автореферат диссертации на тему "О сложности мультиплексорных функций в некоторых классах схем"

Московский государственный университет имени М. В. Ломоносова

На правах рукописи

Власов Никита Вадимович

О сложности мультиплексорных функций в некоторых классах схем

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

5 ДЕК 2013

Москва — 2013

005542845

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор

Ложкин Сергей Андреевич

Официальные оппоненты: доктор физико-математических наук,

профессор кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова Кочергин Вадим Васильевич

кандидат физико-математических наук, ведущий инженер по разработке программного обеспечения в филиале компании «Ментор Графике Девелопмент Сервисез Лимитед» (Ирландия)

Шиганов Александр Евгеньевич Ведущая организация: Институт системного анализа РАН Защита диссертации состоится 20 декабря 2013 года в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В.Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/ в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан «20» ноября 2013 года.

Ученый секретарь диссертационного совета

к. т. н, ведущий научный сотрудник - В. А. Костенко

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

Актуальность темы. Теория синтеза управляющих систем является одним из основных разделов дискретной математики и математической кибернетики1,2'3. Она возникла в 30-40-х годах прошлого века в связи с необходимостью проектирования и логического описания дискретных вычислительных устройств различного типа. К. Шеннон4,5 дал строгую математическую постановку задачи синтеза управляющих систем, положив тем самым начало соответствующей теории, исследования в которой ведутся с тех пор непрерывно. В целом, в теории синтеза управляющих систем изучаются модели различных дискретных преобразователей сигналов, их сложность, надёжность и другие характеристики.

Интерес к этой области знания обусловлен, прежде всего, возможностью применения полученных результатов при проектировании оптимальных или близких к оптимальным по определённым характеристикам схем, при изучении их поведения и надёжности, при тестировании схем и т.д. Кроме того, результаты, полученные для решения задачи синтеза, находят применение в других областях дискретной математики.

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

1Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.:

Изд-во МГУ, 1984. - 137 с.

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

3Ложкин С. А. Лекции по основам кибернетики. — М.: Издательский отдел ф-та

ВМиК МГУ, 2004. — 251 с.

4Shannon С. Е. A symbolic analysis of relay and switching circuits. Trans. AIEE, 1938,

v. 57, pp. 713-723.

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

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

Задача синтеза в общем виде состоит в построении для заданной системы ФАЛ такой реализующей её схемы из заданного класса, на которой достигается минимальное значение исследуемого функционала сложности. Указанное значение считается сложностью данной системы ФАЛ в рассматриваемом классе схем относительно изучаемого функционала. В теории синтеза выделяют при этом два основных направления: «массового» и «индивидуального» синтеза.

Методы «массового» или, как его ещё называют, универсального синтеза позволяют единообразно строить схемы для произвольных ФАЛ. Критерием качества таких методов являются обычно получаемые с их помощью верхние оценки функции Шеннона, которая зависит от натурального аргумента п, равна сложности самой сложной ФАЛ от п булевых переменных (БП) и, как правило, при п = 1,2,... асимптотически совпадает со сложностью почти всех ФАЛ от этих БП.

Методы массового синтеза применимы к любой ФАЛ и позволяют для почти всех ФАЛ получать схемы, сложность которых близка к оптимальной. При этом, однако, сложность схем, получаемых с их помощью для конкретных (индивидуальных) ФАЛ, может быть далека от оптимальной, в связи с чем и возникает необходимость решения соответствующей задачи индивидуального синтеза.

Одним из самых распространённых и широко используемых классов ФАЛ является класс «управляющих» ФАЛ, к числу которых относятся и так называемые мультиплексорные ФАЛ. Будем называть мультиплексор-ной (квазимультиплексорной) ФАЛ порядка п и ранга г ФАЛ от п «адресных» и г «информационных» БП, которая существенно зависит от всех этих БП, но на любом наборе значений адресных БП имеет только одну (соответственно, не более, чем одну) существенную информационную БП.

Наиболее распространённым вариантом мультиплексорной ФАЛ является мультиплексорная ФАЛ порядка п и ранга 2П, которая считается

стандартной мультиплексорной ФАЛ порядка п (мультиплексором порядка п) и обозначается При этом под стандартной квазимультиплексор-ной ФАЛ порядка п понимается квазимультиплексорная ФАЛ, которая получается из ФАЛ /i„ в результате подстановки констант вместо части её информационных БП.

Стандартная мультиплексорная ФАЛ, мультиплексорные ФАЛ общего вида и квазимультиплексорные ФАЛ часто применяются как в теоретических исследованиях, так и при синтезе интегральных схем. Данные ФАЛ обычно являются составной частью подсхем выбора из памяти и коммуникационных подсхем, что вызывает необходимость их оптимизации по различным параметрам: площади, задержке, энергопотреблению и т. д. Мультиплексорные ФАЛ используются как в теории индивидуального синтеза при синтезе оптимальных и близких к оптимальным схем, так и в теории массового синтеза при разработке универсальных методов построения схем и изучении поведения функции Шеннона. Кроме того, ФАЛ мультиплек-сорного типа находят применения в вопросах тестирования и исследования надёжности схем.

В иностранной литературе6'7 мультиплексорная ФАЛ ßn обычно называется storage access function (т. е. «функция доступа к памяти») либо lookup function (т. е. «функция поиска»), что подчёркивает сферу её применений.

Цель диссертации. Целью диссертации является разработка методов синтеза схем, которые реализуют ФАЛ мультиплексорного типа и глубина (сложность) которых либо оптимальна, либо близка к оптимальной, а также методов получения нижних оценок глубины и сложности указанных ФАЛ, позволяющих, в частности, обосновывать оптимальность построенных схем на уровне асимптотических оценок высокой степени точности (АОВСТ).

Научная новизна. Все полученные в диссертации результаты являют-

6Tardos G., Zwick U. The communication complexity of the universal relation. Proceedings of the I2th Annual IEEE Conference on Computational Complexity (CCC), 1997, pp. 247-259.

7Wegener I. The complexity of Boolean functions. Teubner, Stuttgart: John Wiley & Sons Ltd, and B. G, 1987, 458 pp.

ся новыми. В данной работе впервые установлено точное значение глубины стандартной мультиплексорной ФАЛ порядка п, п ^ 20, а также получены АОВСТ для её сложности. Предложены новые методы синтеза схем для мультиплексорных ФАЛ, разработан новый подход к получению нижних оценок сложности ФАЛ мультиплексорного типа.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты, касающиеся сложности и глубины реализации мультиплексорных ФАЛ, могут, по мнению автора, быть использованы как при синтезе интегральных схем, содержащих мульти-плексорные ФАЛ в качестве подсхем, так и в теоретических исследованиях. Разработанный подход к доказательству нижних оценок может, по мнению автора, быть использован при исследовании сложности реализации ФАЛ близких к ФАЛ мультиплексорного типа.

Методы исследования. Результаты диссертации получены с использованием методов синтеза схем, ориентированных на получение асимптотических оценок высокой степени точности, а также методов доказательства нижних оценок, основанных на технике использования свойства незабива-емости переменных.

Публикации и апробирование. По теме диссертации опубликовано 7 печатных работ {1]-[7], из которых статьи [3, 5, 7] — в изданиях, рекомендованных ВАК. Результаты диссертации докладывались на семинарах кафедры математической кибернетики факультета ВМК МГУ, а также докладывались и обсуждались на следующих конференциях и семинарах:

1. IX международный семинар «Дискретная математика и её приложения» (Москва, МГУ, 18-23 июня 2007 г.);

2. XV международная конференция «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.);

3. XVI международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 20-25 июня 2011 г.);

4. XI международный семинар «Дискретная математика и её приложения» (Москва, 18-23 июня 2012 г.)

Структура и объём работы. Диссертация состоит из введения, двух глав и списка литературы. Текст изложен на 90 страницах. Список литературы включает 66 наименований.

Краткое содержание диссертации

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

Пусть В = {0,1} — булево множество, = {жъ ... ,хп,...} — счётный упорядоченный алфавит (входных) булевых переменных (БП), принимающих значения из В. При этом будем считать, что любая ФАЛ /, / : Вп ->• В, зависит от набора БП х = (хн,... где Вп — единичный п-мерный куб, а х^, ] £ [1 ,п], — БП, которая связана с ]-м разрядом указанного куба.

Введём основные классы схем, в которых будет происходить реализация исследуемых ФАЛ.

Пусть Б = {(/?!,..., <рь} — полный в Рг базис функциональных элементов (ФЭ), где г'-й, г е [1,6], ФЭ реализует базисную ФАЛ <р{(хх,... ,хк<), а его сложность («вес») и глубина (задержка) равны 1. Далее будем рассматривать, в основном, стандартный базис Во = {хх • Х2, V х2,хх} и так называемый унимодальный базис ¡У2, состоящий из всех ФАЛ вида х"1 -х^2 и х'1 V где х? = хи х\ = г = 1,2, и а^ ст2 е В.

Схемой из функциональных элементов (СФЭ) над базисом Б будем называть ориентированный ациклический граф Е, в котором все истоки и только они помечены символами различных БП из множества X и считаются входами схемы, все остальные вершины помечены символами ФАЛ из базиса Б, а часть вершин схемы кроме того, объявлена её выходами. При этом входящие в любую вершину V схемы Е дуги упорядочены, а их число, равное к, и порядок соответствуют количеству и порядку БП, от которых зависит связанная с V базисная ФАЛ <р(хь..., Хк)- Считается, что в указанной вершине V данной схемы реализуется ФАЛ <р(/ь ■■•,/&), где /¿, г е [1,&], — ФАЛ, реализованная в той вершине Е, из которой в вершину V идёт дуга с номером г. Предполагается, что схема Е реализует

систему ФАЛ, состоящую из тех ФАЛ, которые реализованы в её выходных вершинах.

Формулой над базисом Б будем называть СФЭ с 1 выходом, в которой из каждой вершины, отличной от входов и выхода, исходит одна дуга.

Формулу над базисом Б0, в которой все ФЭ «-.» расположены над БП, будем называть формулой с поднятыми отрицаниями. Для произвольной формулы Т над базисом Б0 с поднятыми отрицаниями определим, как обычно, «моделирующую» её структурно и функционально 7г-схему £. При этом произвольной БП х{ и её отрицанию х,, рассматриваемым как «простейшие» формулы, сопоставим 7г-схему из одного контакта, помеченного х* и соответственно, а записи Т = Т&Рг (? = Т\ V Т2) сопоставим 7г-схему £, которая представляет собой последовательное (соответственно параллельное) соединение 7г-схем и Е2, сопоставленных формулам и Заметим, что любая тг-схема является «моделью» указанного вида для некоторой формулы с поднятыми отрицаниями.

Через £(Е) (£(£*)) будем обозначать сложность СФЭЕ (соответственно сложность -к-схемы £*), то есть число ФЭ в £ (соответственно контактов в Е*). Сложность формулы Т, то есть сложность соответствующей ей СФЭ, будем также обозначать через Ь{.Т), а её ранг, то есть число символов БП в записи Т, — через ЩГ). Под глубиной !>(£) одновыходной СФЭ или формулы £ будем понимать максимальную длину цепей от входов Е к её выходу. Заметим, что ранг формулы над базисом Б0 с поднятыми отрицаниями равен сложности моделирующей её 7г-схемы.

Под схемной (формульной) сложностью ФАЛ / в базисе Б будем понимать величину £§(/) (соответственно (/)), равную минимальной сложности тех СФЭ (соответственно формул) над базисом Б, которые реализуют ФАЛ /. Аналогичным образом определяется сложность Ь7Г(/) ФАЛ / в классе п-схем, а также её глубина £>в(/) в базисе Б, равная минимальной глубине реализующих ФАЛ / СФЭ над Б, которая, очевидно, всегда достигается на некоторой формуле.

В базисе Д>, кроме приведённых выше «полных» функционалов сложности, будем рассматривать также «частичные» функционалы сложности £&,у(£) и и&,у(Е), которые учитывают сложность и глубину только ФЭ «&» и «V» схемы Е. При этом через £|у(/), 2?&,у(/) и будем обо-

значать значения введённых «частичных» функционалов сложности для

ФАЛ / в классе формул и СФЭ соответственно.

Пусть Д = (<5о,••• ,<5(1-1) — упорядоченное разбиение куба Вп на й, й < 2™, компонент. Тогда мультиплексорной ФАЛ разбиения Д называется ФАЛ

/хд (х1,...,х„,уо,...,у<1-1) = УоХа0 V... ^-1X^-1)

гДе Х<5< — характеристическая ФАЛ компоненты 5{, г 6 [0, й — 1], причём первые п переменных этой ФАЛ называются её «адресными», а оставшиеся й — её «информационными» БП. Мультиплексорную ФАЛ тривиального разбиения булева куба порядка п на 2П компонент мощности 1, упорядоченных в соответствии с лексикографическим порядком связанных с ними наборов, будем называть стандартной мультиплексорной ФАЛ цп порядка п или просто мультиплексором порядка п.

Любая мультиплексорная ФАЛ рд, где Д — разбиение куба Вп на <1 компонент, считается мультиплексорной ФАЛ порядка п и ранга <1. Ту ФАЛ, которая получается из мультиплексорной ФАЛ / порядка п подстановкой констант вместо части (возможно, пустой) её информационных БП, будем называть связанной с / квазимультиплексорной ФАЛ порядка п и ранга г, где г — число оставшихся информационных БП. При этом квази-мультиплексорные ФАЛ, получающиеся в результате подстановки нулей, считаются нулевыми, а квазимультиплексорные ФАЛ порядка п и ранга г, связанные с ФАЛ //„, называются стандартными квазимультиплексорны-ми ФАЛ порядка п и ранга г или, иначе, квазимультиплексорами порядка п и ранга г. Будем называть информационной областью квазимультиплексора множество тех наборов значений его адресных БП, на которых он равен одной из своих информационных БП.

Кроме того, во второй части введения формулируются в виде теорем 1-6 полученные в диссертации оценки сложности реализации стандартной мультиплексорной ФАЛ и квазимультиплексорных ФАЛ в рассматриваемых классах, а также оценки глубины реализации указанных ФАЛ.

Теорема 1. Для последовательности квазимультиплексорных ФАЛ ¡и„ порядка п, где п = 2,3,... и ранга г, г = г(п), где 3 < г(п) < 2П, справедливы соотношения:

и {-¡Ли) = + 1 = + 1 ^ 2 ■ Г- +

3 п \п/

Ьс{рп) = (Д„) ^ 2 • г + ^^ - 0{п),

Пфп) > -0&,у(Дп) = > Г1ойг] + 1,

причём второе неравенство выполняется при условии ^ = о(г(п)).

Теорема 2. При п = 2,3,... ¿ля мультиплексорной ФАЛ цп справедливы неравенства:

2П+1 + ЩйТ!)) -1 < = ^Ы <

Теорема 3. При п = 1,2,... ¿ля мультиплексорной ФАЛ цп справедливы неравенства:

Теорема 4. Яри п = 1,2,... для мультиплексорной ФАЛ цп справедливы неравенства:

2П+1 + - о («) ^ ££>„) < ьваы < <

<2"+1 + С(п).2?+0(п2?), где С(п) = 2, если п четно, и С(п) = если п нечётно.

Теорема 5. Для мультиплексорной ФАЛ/х„, п = 1,2,..справедливы соотношения:

1- = = 2;

(Мп(х,у)) = Оия(цп(х,у)) = п + 2, если 1 < п ^ 5 или п > 20;

3. n-f 2 < D^y(fin(x,y)) = Du2(fin(x,y)) < n + 3, если 5 < n < 20.

Теорема 6. Пусть для n = 1,2,... и натуральных последовательностей г = r(n) < 2п, d = d(n) < п выполнены условия

r(n) n-d(n) = o(n).

Тогда для любой последовательности нулевых квазимультиплексоров Дп, п = 1,2,..., порядка п и ранга г(п) таких, что информационную область

можно представить в виде объединения непересекающихся граней размерности не меньше нем d(n) куба Вп, выполняются соотношения

Ь*@п) - 1 = £&(£„) = ¿£v(£„) = 2r(n) + ^ + о (,

п \ п /

3 п \ п J п \ п )

л/2

2г(п) + — у/ф) - О (n) ^ Lgv((2n) < Ь$2(рп) < Lc(/Í„) <

«S 2г(п) + С(п) • V^W + О ,

£>(&) = flogr(n)l+0(l),

где С(п) = 2, если п четно, и С(п) = если п нечётно.

Первая глава посвящена доказательству верхних оценок сложности и глубины реализации мультиплексорных ФАЛ.

В разделе 1.1 диссертации вводятся некоторые понятия и определения, связанные с реализацией мультиплексорных ФАЛ, а также доказывается ряд вспомогательных утверждений, которые используются в дальнейших построениях. В частности, устанавливается минимальная глубина реализации как элементарных конъюнкций и дизъюнкций, так и формул более сложного вида. Также в данном разделе приводятся некоторые определения и факты, связанные с разбиением булева куба на непересекающиеся единичные сферы, доказывается верхняя оценка глубины реализации характеристической ФАЛ произвольной единичной сферы такого разбиения.

Кроме того, в разделе 1.1 доказываются некоторые оценки глубины стандартной мультиплексорной ФАЛ цп при п = 1,..., 5.

В разделе 1.2 доказываются верхние оценки глубины мультиплексорной ФАЛ 6, в стандартном базисе Бо и в унимодальном базисе U2 для функционалов сложности (глубины) ■D&>v(/), D(f) и Du2{î). При этом построение оптимальных и близких к оптимальным по глубине схем производится следующим образом. Набор входных адресных БП х = (zi,..., хп) делится на три части, и булев куб от БП первой части разбивается на непересекающиеся единичные сферы. Далее строится декартово произведение каждой компоненты такого разбиения и каждого набора куба от второй группы адресных БП. На каждой компоненте построенного разбиения булева куба от первых двух групп адресных БП мультиплексорная ФАЛ ¡лп моделируется с помощью одной адресной БП либо её отрицания, что позволяет построить формулу в стандартном базисе, реализующую ФАЛ ¡лп и имеющую глубину не более п + 3 для функционалов сложности £>&,v(/) и Du2{f)- Далее для значений п ^ 20 часть построенных компонент отбрасывается, а затем группируется вместе так, чтобы итоговая формула имела глубину не более п + 2. Основным результатом раздела 1.2 является следующая лемма8.

Лемма 1 (6). Для мультиплексорной ФАЛцп, где п > 5, справедливо: = DU2{nn{x,y)) «S n + З, если 5 < п < 20,

Dby(nn{x,y)) - DU2{nn(x,y)) sSn + 2, еслип > 20.

В разделе 1.3 рассматриваются вопросы оптимальной по сложности реализации ФАЛ /лп в классах 7г-схем и формул с получением для этой сложности верхних АОВСТ в классе 7г-схем и близких к АОВСТ верхних оценок в классе формул. В качестве основного метода синтеза в данном разделе используется техника так называемых m-регулярных разбиений булева куба9, которая позволяет моделировать системы ФАЛ от m БП на компоненте такого разбиения с помощью одной БП или её отрицания.

8 Здесь и далее в круглых скобках приводятся номера соответствующих лемм в тексте диссертации.

9Ложкин С. А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучших оценок высокой степени точности // Вестник Московского университета. Сер. 1, Математика, Механика. — 2007. — №3. — С. 20-26.

При синтезе 7г-схем в данном разделе набор адресных БП делится на несколько частей, а булев куб от первой группы БП разбивается на т-регулярные компоненты, на каждой из которых строится дополнительное подразбиение таким образом, чтобы на любой полученной компоненте ФАЛ /лп совпадала либо с адресной БП, либо с её отрицанием. В классе формул, кроме того, используется дополнительное подразбиение для минимизации числа ФЭ «-1», входящих в формулу. Получаемые при этом 7г-схемы и формулы имеют требуемую сложность.

Основными результатами раздела 1.3 являются утверждения, в которых устанавливаются верхние оценки сложности реализации ФАЛ рьп в указанных классах схем.

Лемма 2 (8). В базисе Дз имеется формула с поднятыми отрицаниями Тп(х, у), которая реализует ФАЛ рп(х, у) и для которой

071 / 9™ \

п \n\ogn;

Следствие.

- 1 = ь$20*п) = ^ 2"+* (1 + ^+0 )) •

Лемма 3 (9). В базисе Бо имеется формула у), которая реализует ФАЛ ц„(х, у) и для которой

ЦГп(х, у)) < 2П+1 (1 + - + 0 ) ) .

V п \nlognJ)

Следствие.

\ п \n\ogn))

В разделе 1.4 доказываются верхние оценки сложности мультиплек-сорных ФАЛ в классе СФЭ, для чего набор адресных БП ФАЛ делится на две части длины10 и соответственно, для каждой из которых строятся мультиплексоры соответствующего порядка, которые используют общие элементарные конъюнкции от адресных БП. Таким образом, устанавливается справедливость следующей леммы.

10 Через [а] ([а_|) обозначается ближайшее к а сверху (соответственно снизу) целое число.

Лемма 4 (12). В базисе В0 имеется СФЭ £п, которая реализует ФАЛ п > 2, и для которой

¿(E) s$2n+1+2-2Í +0(п2*), если п — четное число,

3\/2

£(£) ^ 2n+1 Н—— • 2' + О (п2*) , если п — нечётное число. Следствие.

¿£,v(Mn) ^ b£>n) ^ lc(ßn) < 2" + С(п) • 2? + О (п ■ 2?), где С(п) = 2, если п четно, и С(п) = если п нечётно.

Кроме того, в разделе 1.4 полученные в разделах 1.2 и 1.3, а также в данном разделе верхние оценки сложности и глубины стандартных муль-типлексорных ФАЛ обобщаются на некоторый класс квазимультиплексор-ных ФАЛ.

Лемма 5 (13). Пусть для п = 1,2,... и натуральных последовательностей г = г(п) ^2п, d = d{n) sí п выполнены условия

r{n) > 2d(-n\ n-d(n) = o(n).

Тогда для любой последовательности нулевых квазимультиплексоров Дп, п = 1,2,..., порядка п и ранга г(п) таких, что информационную область ßn моокно представить в виде объединения непересекающихся граней размерности не меньше чем d(n) куба Вп, выполняются соотношения

¿ЧДп) - 1 - = п) < 2г(п) +ГМ+0(ГЩ

п \ п J

Lb,v(ßn) < Lg (fin) ^ Lc(fin) < 2r(n) + C(n) ■ л/^ñj + o(n $/r(ñ)) , D(ßn) < (bgr(n)l +0(1), где C(n) = 2, если n четно, и C(n) = если n нечётно.

Вторая глава посвящена описанию нового подхода к доказательству нижних оценок сложности ФАЛ мультиплексорного типа. Также в ней устанавливаются нижние оценки глубины и сложности реализации стандартной мультиплексорной ФАЛ и квазимультиплексорных ФАЛ.

В разделе 2.1 вводятся такие понятия как незабиваемое множество БП и незабиваемая БП11. Для БП, входящих в такие множества, удаётся установить способ их вхождения в схему, который характеризуется тем, что ФАЛ, реализуемая данной схемой, сохраняет существенную зависимость от незабиваемой БП после любой подстановки констант вместо других БП из указанного множества. Информационные БП квазимультиплексорной ФАЛ образуют незабиваемое множество её переменных.

На основе свойств незабиваемости множества информационных БП доказываются следующие леммы, в которых устанавливаются нижние оценки глубины стандартной мультиплексорной ФАЛ и квазимультиплексорных ФАЛ.

Лемма 6 (15). Для любой формулы Тп в базисе Во, реализующий мулътиплексорную ФАЛ /хп , п ^ 2, справедливы соотношения:

Du п) = Djj2 (J-n) ^ n + 2.

Лемма 7 (16). Для квазимультиплексорной ФАЛ ßn порядка п и ранга г, г ^ 2, выполняется неравенство

D(fin) > DuAßn) = Du2(ßn) ^ Rogr] + 1.

Из лемм 1 и 6 следует справедливость теоремы 5, а из леммы 7 — нижняя оценка последнего из соотношений теоремы 1.

В разделе 2.2 приводится описание нового подхода к доказательству нижних оценок сложности ФАЛ мультиплексорного типа. Он заключается в разбиении входных БП схемы, реализующей заданную ФАЛ, на несколько специальных групп, определённых структурой схемы. Далее происходит подстановка констант вместо всех или почти всех БП в каждой из таких групп и последующее упрощение схемы. Затем производится анализ структуры полученной схемы и оценивается её сложность на основе

11Алсксеев В. В., Ложкин С. А. Элементы теории графов, схем и автоматов. — М.: Издательский отдел ф-та ВМиК МГУ, 2000. — 58 с.

невозможности устранения при этом части оставшихся переменных данной ФАЛ. При этом исследуются подсхемы определённого вида, которые являются характерными для получаемых квазимультиплексорных ФАЛ, и изучаются закономерности и ограничения в пределах таких подсхем, за счёт которых удаётся установить число дополнительных ФЭ, входящих в схему. В данном разделе формулируются и доказываются вспомогательные утверждения, позволяющие делать выводы о строении схем, реализующих квазимультиплексорные ФАЛ.

В разделе 2.3 разработанный подход применяется для доказательства нижних оценок сложности квазимультиплексорных ФАЛ в классах 7г-схем и формул в стандартном базисе, приведённых в следующих утверждениях.

Лемма 8 (20). Для любой формулы Тп с поднятыми отрицаниями в базисе Бо, реализующей квазимулътиплексорную ФАЛ порядка п и ранга г, где 2п, справедливо неравенство

П{Гп) > 2 • г + -4т-п + 1

Следствие. Для квазимулътиплексорной ФАЛ ¡ип порядка п и ранга г, п ^ 2, г = г(п), 3 ^ г(п) < 2П, справедливы соотношения

Ь*($п) = (£„) + 1 = Ь%уСрп) + 1>2-г+

71 ~т" X

Лемма 9 (22). Для произвольной формулы Тп в базисе Бо, реализующей квазимулътиплексорную ФАЛ~рп порядка п и ранга г, где п = 2,3,.. г = г(п), 1 ^ г (га) ^ 2™ и ~ = о(г(п)), справедливо неравенство

Ь{Тп)>2-г + 1 .1_0(1).

3 п \п/

Следствие. Для квазимулътиплексорной ФАЛ ¡5„ порядка п и ранга г, п > 2, г = г(п), 1 < г(п) <2" = о(г(п)), справедливо неравенство

3 п \п/

Следствия из лемм 2, 3, 8 и 9 доказывают справедливость теорем 2 и 3.

В разделе 2.4 на основе указанного подхода устанавливаются нижние оценки сложности квазимультиплексорных ФАЛ в классе СФЭ.

Лемма 10 (23). Для любой СФЭ £„ в базисе Во, реализующей ква-зимулътиплексорную ФАЛ ]2п порядка п и ранга г, п ^ 2, г = г(п), 1 ^ г(п) < 2п, справедливо:

Следствие. Для квазимулътиплексорной ФАЛ Дп порядка п и ранга г, п ^ 2, г = T'(n), 1 ^ г(п) < 2™, справедливо неравенство

Справедливость теоремы 4 следует из лемм 4 и 10, а теоремы 1 — из леммы 7 и из следствий из лемм 6, 8, 9 и 10.

Кроме того, из леммы 5 и теоремы 1 следует справедливость теоремы 6.

Основные результаты диссертации

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

2. Разработаны новые методы получения нижних оценок сложности ФАЛ мультиплексорного типа; с помощью этих методов установлены новые, более точные оценки их сложности в классах 7г-схем, формул и схем из функциональных элементов (СФЭ).

3. Установлены асимптотические оценки высокой степени точности (АОВСТ) для сложности реализации стандартной мультиплексорной функции в классе 7г-схем и в классе формул в унимодальном базисе. Аналогичные оценки получены для некоторого класса мультиплексорных функций общего вида.

4. Получены близкие к АОВСТ оценки сложности реализации стандартной мультиплексорной функции в классах формул и СФЭ в стандартном и унимодальном базисах.

5. Установлено, что глубина стандартной мультиплексорной функции порядка п в унимодальном базисе равна п + 2, если п ^ 20.

Публикации по теме диссертации

[1] Ложкин С. А., Власов Н. В. О глубине мультиплексорной функции // Материалы IX Международного семинара «Дискретная математика и её приложения» (Москва, МГУ, 18-23 июня 2007 г.). - 2007. — С. 102105.

[2] Ложкин С. А., Власов Н. В. О сложности мультиплексорной функции в классе 7г-схем // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.). — 2008. — С. 76.

[3] Ложкин С. А., Власов Н. В. О сложности мультиплексорной функции в классе 7г-схем. // Ученые записки Казанского университета. Сер. Физ.-матем. науки. - 2009. - Т. 151, кн. 2. - С. 98-106.

[4] Власов Н. В. О сложности мультиплексорной функции в классе формул // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). — 2011. - С. 96-97.

[5] Ложкин С. А., Власов Н. В. О глубине мультиплексорной функции // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика. — 2011. — №2. — С. 40-46.

[6] Власов Н. В. О сложности мультиплексорной функции в классе схем из функциональных элементов // Материалы XI международного семинара «Дискретная математика и её приложения» (Москва, 18-23 июня 2012 г.). - 2012. - С. 100-101.

[7] Власов Н. В. О сложности мультиплексорной функции в классе формул // Вестник Нижегородского государственного университета им. Н. И. Лобачевского. — 2012. - №5. — С. 38-41.

Напечатано с готового оригинал-макета

Подписано в печать 18.11.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 387.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Власов, Никита Вадимович, Москва

Московский государственный университет имени М. В. Ломоносова

О сложности мультиплексорных функций в некоторых классах схем

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание учёной степени кандидата физико-математических наук

На правах рукописи

04201450124

Власов Никита Вадимович

Научный руководитель: д. ф.-м.н., профессор Ложкин Сергей Андреевич

Москва —2013

Оглавление

Введение 4

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

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

Глава 1. Реализация стандартных мультиплексоров и квазимультиплексоров в некоторых классах схем, верхние оценки их сложности. 28

1.1. Некоторые понятия и конструкции, связанные с реализацией

мультиплексорных ФАЛ..................... 28

1.2. Реализация мультиплексоров формулами с оптимизацией их глубины............................... 35

1.3. Реализация мультиплексоров 7г-схемами и формулами с опти-

мизацией их сложности...................... 42

1.4. Реализация мультиплексоров схемами из функциональных эле-

ментов. Обобщение полученных ранее результатов на некоторый класс квазимультиплексоров................ 49

Глава 2. Нижние оценки сложности (глубины) мультиплексорных функций в некоторых классах схем. 54 2.1. Операция стандартной подстановки констант. Нижние оценки

глубины мультиплексорных функций.............. 54

2.2. Канонические квазимультиплексорные схемы и формулы, осо-

бенности их структуры...................... 59

2.3. Нижние оценки сложности реализации квазимультиплексор-

ных функций 7Г-схемами и формулами............. 67

2.4. Нижние оценки сложности реализации квазимультиплексор-

ных функций схемами из функциональных элементов. ... 76

Литература 83

Введение.

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

Теория синтеза управляющих систем является одним из основных разделов дискретной математики и математической кибернетики ([14, 24, 45]). Она возникла в 30-40-х годах прошлого века в связи с необходимостью проектирования и логического описания дискретных вычислительных устройств различного типа. К. Шеннон в работах [62, 63] дал строгую математическую постановку задачи синтеза управляющих систем, положив тем самым начало соответствующей теории, исследования в которой ведутся с тех пор непрерывно. В целом, в теории синтеза управляющих систем изучаются модели различных дискретных преобразователей сигналов, их сложность, надёжность и другие характеристики.

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

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

предложенных Шенноном ([24, 63]). Эти соображения основаны на том, что число ФАЛ, которые зависят от п БП и имеют сложность не более, чем Ь, не может быть меньше числа попарно не эквивалентных схем от этих БП сложности не больше, чем Ь.

Среди подходов к решению задач массового синтеза стоит выделить широко известный метод Шеннона (см. [24, 63]), который основан на разложении реализуемой ФАЛ по части переменных и получении искомой схемы в виде суперпозиции двух «стандартных» схем. Метод Шеннона позволяет установить порядок функции Шеннона для сложности КС и СФЭ.

Другим известным методом синтеза является метод каскадов, предложенный Г. Н. Поваровым [29]. Как и метод Шеннона, он позволяет установить порядок сложности реализации почти всех ФАЛ в классах КС и СФЭ, хотя является технически более простым и удобным. Кроме того, метод каскадов позволяет получать хорошие схемы для ФАЛ с небольшим числом переменных и целого ряда последовательностей конкретных ФАЛ. Так, для линейной ФАЛ от п (п ^ 2) БП с помощью метода каскадов строится оптимальная контактная схема сложности (4п — 4).

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

В частности, О. Б. Лупанов разработал метод (см. [25, 26] и, например, [24]), который позволил установить асимптотическое поведение функции Шеннона и наличие эффекта Шеннона для сложности СФЭ, КС и целого ряда других классов схем. В основе метода ЛуПанова лежит представление каждой из тех ФАЛ, которые являются результатом разложения исходной ФАЛ по части переменных, в виде дизъюнкции вспомогатель-

ных ФАЛ определённого вида.

В дальнейшем множество указанных вспомогательных ФАЛ было названо С. А. Ложкиным (см. [14]) дизъюнктивно-универсальным множеством (ДУМ) функций. Обобщение ДУМ — так называемые ^-универсальные множества ФАЛ — позволило разработать метод синтеза, с помощью которого для ряда классов оказалось возможным строить такие схемы, сложность которых для почти всех ФАЛ не превосходит асимптотически оптимальных значений на уровне так называемых асимптотических оценок высокой степени точности (см. [16, 17]).

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

При решении задачи индивидуального синтеза, как и при решении задачи массового синтеза, верхние оценки получаются непосредственным построением схемы для заданной ФАЛ (системы ФАЛ). При доказательстве же нижних оценок сложности индивидуальных ФАЛ мощностной подход не применим, а для их получения используются особенности поведения самой ФАЛ. Поэтому в теории индивидуального синтеза доказательство нижних оценок, за исключением тривиальных оценок, связанных с числом существенных БП реализуемой ФАЛ (см., например, [57]), зачастую оказывается гораздо сложнее доказательства соответствующих верхних оценок.

Методы получения нижних оценок индивидуальной сложности заключаются, обычно, в нахождении таких свойств или особенностей поведения ФАЛ, из которых выводится та или иная нижняя оценка их сложности (см., например, [40]). При этом для вывода указанной нижней оценки

часто используется приём «забивающих» констант, связанный с подстановкой различных констант вместо части входных БП в схему, реализующую данную ФАЛ, и последующим устранением из неё определённого числа элементов.

Так, Б. М. Клосс и В. А. Малышев доказали указанным способом первую нижнюю оценку вида (2п — 0(1)) для сложности ФАЛ из некоторого класса в классе СФЭ над базисом из всех двуместных ФАЛ ([10]). К. Шнорр в работе [59] доказал нижнюю оценку (2п — 3) для сложности такой ФАЛ, из которой при подстановке констант вместо любых двух её переменных можно получить по крайней мере 3 различных ФАЛ, в классе СФЭ над базисом из всех двуместных ФАЛ. В. Поль ([58]) и Л. Стокмай-ер ([61]) получили нижние оценки, асимптотически равные 2, 5п, для некоторых ФАЛ от п БП в классе СФЭ над базисом из всех двуместных ФАЛ, что стало качественным улучшением нижних оценок, асимптотически равных 2гг. Их методы были использованы К. Шнорром ([60]) и Л. Блюм ([47]) для получения нижних оценок, асимптотически равных 3п.

Оценки более высокого порядка позволяет установить, например, метод Б. А. Субботовской ([36]), в котором нижняя оценка сложности исследуемой функции получается на основе сложности некоторых её подфункций. Этот метод заключается в последовательной подстановке констант О и 1 вместо БП исходной ФАЛ до получения ФАЛ, сложность которой легко может быть оценена снизу. Для сложности линейной ФАЛ в классе формул в стандартном базисе = {&, V, -•} с помощью этого метода удаётся получить нижнюю оценку порядка п3/2. В работах [37, 38] метод Субботовской применяется к другим похожим базисам.

С помощью обобщения метода Субботовской, предложенного А. Е. Андреевым в работе [2], могут быть получены ещё более высокие нижние оценки для сложности реализации некоторых ФАЛ формулами в базисе

Так, Андреев предложил пример ФАЛ, построенной с использованием универсальной функции Э. И. Нечипорука (см. [28]), для сложности которой в классе формул в стандартном базисе Eq с помощью указанного метода можно доказать нижнюю оценку, по порядку равную1

П 2

(log п)1 log log п

Позже И. Хастад ([54]) для функции Андреева доказал наивысшую известную на данный момент нижнюю оценку сложности в классе формул в стандартном базисе, которая по порядку равна

п3

7 о •

(log n)2 (log log п)

В. М. Храпченко в работе [44] предложил метод получения высоких нижних оценок в классе 7г-схем. Оценки получаются тем выше, чем чаще ФАЛ меняет своё значение при переходе к соседней точке булева куба.

Метод Нечипорука (см. [28]) позволяет получить нижние оценки вида (iogn) для контактных схем и вида для формул в произвольном конечном базисе. Эти оценки являются самыми высокими из известных для этих классов схем. Для класса формул в базисе, состоящем из всех двухместных ФАЛ, нижние оценки вида (nlogn) даёт метод Фишера-Майера-Патерсо-на ([50, 51]). А. А. Разборов в работах [30, 31] привёл метод получения экспоненциальных нижних оценок сложности ФАЛ в классе схем в базисе {&;, V} вида 2n(log2n). Андреев в работе [3] привёл пример последовательности ФАЛ, для которых указанная сложность имеет вид 2п3 °(1) и является максимальной в настоящее время.

Заметим, что некоторые из приведённых выше нижних оценок сложности связаны с реализацией достаточно «искусственных» ФАЛ. Вместе с тем, одним из основных направлений индивидуального синтеза являет-

:Все логарифмы в данной работе берутся по основанию 2.

ся разработка приёмов синтеза схем, а также получение верхних и нижних оценок сложности «естественных» ФАЛ или систем ФАЛ и, в частности, ФАЛ, встречающихся в приложениях. Хотя некоторые нижние оценки сложности таких ФАЛ уже были приведены, рассмотрим результаты данного направления более подробно, так как именно ему посвящена настоящая диссертация.

Для сложности целого ряда «естественных» ФАЛ известны точные или близкие к ним оценки сложности. Среди них стоит выделить оценки сложности линейной ФАЛ 1°п порядка п, а £ {0,1}, где 1°п = Х\®.. .®хп®сг. Как в классе СФЭ в стандартном базисе Д) = так и в клас-

се контактных схем сложность линейной ФАЛ 1°п порядка п, п ^ 2, равна (4п — 4) (см. [33]). Метод Храпченко позволяет установить нижнюю оценку сложности линейной ФАЛ порядка п в классе 7г-схем, равную п2 (см. [41]). С. В. Яблонский ([46]) доказал верхнюю оценку указанной сложности, равную |п2 в общем случае, и равную п2, если п = 2к, к = 1,2,.. то есть для указанных п известно точное значение сложности линейной ФАЛ.

В ряде работ рассматривалась ФАЛ зп{хь ..., хп) — монотонная симметрическая ФАЛ с порогом 2, которая равна 1, если число единиц среди значений БП х\,...,хп больше одной, и равна 0 в противном случае. Р. Е. Кричевский в работе [12] доказал, что сложность ФАЛ 5П в классе 7г-схем равна2

[_1о§п\ • 2^ + ([1оётг] - 2)(п - 2^).

Аналогичный результат устанавливается в работе [15] для случая, когда контакты разных БП могут иметь различные веса.

Большая часть работ, относящихся к теории индивидуального синтеза, тесно связана с одним из направлений теории сложности — иссле-

2Через [а] ([а]) обозначается ближайшее к а сверху (соответственно, снизу) целое число.

дованием сложности реализации ФАЛ и систем ФАЛ, задающих арифметические операции. Н. П. Редькин в работе [32] доказал, что сложность сумматора порядка п, то есть системы ФАЛ, задающей сложение двух п-разрядных двоичных чисел, в классе СФЭ в базисе {&, V, 0, -i} в точности равна (5п — 3). Однако, глубина построенной при этом схемы указанной сложности оказалась равной (2п — 1), что значительно превосходит нижнюю оценку этого параметра, равную [log п]. Известно, что в стандартном базисе Бо существуют СФЭ, реализующие сложение и вычитание двух п-разрядных чисел со сложностью (9п — 5) и (lin — 5) соответственно (см., например, [1]). Храпченко в работе [42] привёл метод построения СФЭ в произвольном базисе, реализующих сумматор порядка п с линейной относительно п сложностью и асимптотически оптимальной глубиной, которая имеет логарифмический порядок роста. Позже в работе [43] он доказал нижнюю оценку глубины реализации сумматора порядка п в стандартном базисе, равную logn + (1 — о(1)) log log log п.

Известным методом умножения двух n-разрядных двоичных чисел является метод Карацубы ([9]), позволяющий реализовать с его помощью СФЭ сложности О (nlog3). Обобщением метода Карацубы является алгоритм Тоома-Кука, предложенный А. Л. Тоомом в [39] и усовершенствованный С. Куком в его кандидатской диссертации [48]. Алгоритм Тоома-Кука позволяет строить СФЭ, реализующую умножение двух n-разрядных чисел со сложностью О (п1+е) для любого наперёд заданного положительного е. Ещё более эффективным методом реализации умножения является метод Шёнхаге-Штрассена, предложенный в 1971 году (см. [64]), который позволяет получать СФЭ для умножения двух n-разрядных чисел сложности О (п log п log log п). Только спустя 35 лет указанная верхняя оценка была улучшена в работе [52] до величины3 О (nlogn 2°(log п)). Однако, послед-

3Через log* п обозначается величина гтп{г ^ 0 : log'-1'' п ^ 1}, где log'0' п — п, а

ние три подхода реально применимы только для очень больших значений параметра п.

Наряду с исследованием сложности «арифметических» систем ФАЛ широко изучалась также сложность реализации «управляющих» ФАЛ и сложность (совместной) реализации систем таких ФАЛ. Доказано, в частности, что сложность реализации так называемого универсального многополюсника порядка п, то есть системы всех ФАЛ от п БП, в классе СФЭ в произвольном базисе с единичными весами элементов равна 22"—п (см. [1]). В работе [63] Шеннон построил универсальный контактный многополюсник с 1 входом и 22" выходами, имеющий сложность асимптотически равную 2 ■ 22" , и только много позднее С. А. Ложкиным и М. А. Кошкиным в работе [23] было доказано, что он является асимптотически оптимальным.

На основе предложенного в работе [23] подхода её авторами был развит достаточно общий метод получения нижних и верхних оценок сложности реализации «больших» систем ФАЛ контактными и обобщёнными контактными схемами, имеющими линейную относительно мощности системы асимптотику роста с коэффициентом большим единицы. С помощью этого метода в [22] была установлена асимптотика для контактной сложности дизъюнктивного дешифратора порядка п от п БП, то есть системы всех элементарных дизъюнкций (ЭД) ранга п, для системы всех ФАЛ от п БП из произвольного ненулев�