Оригинальные методы реализации булевых функций в классах формул и схем из функциональных элементов в разных базисах (стр. 1 )

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

“ABOUT COMPLEXITY OF REALIZATION OF

SYMMETRIC POLYNOMIALS ZHEGALKINA”

Abstract.

Original methods, ways of realization Boolean functions, including symmetric, in classes of formulas and circuits from functional elements in different bases are offered. Thus up to a stage of synthesis estimations for various parameters of complexity - quality (forthcoming) synthesis that allows to improve them are deduced. For multicriteria minimization are allocated cases when reduction of one parameter of quality attracts to increase of another. Methods are recommended for intellectualization of the automated synthesis of logic circuits.

Ключевые слова:

Булевы функции; формулы; схемы из функциональных элементов; анализ; синтез; декомпозиция; размерность; сложность; показатели качества; минимизация; функциональные и разностные уравнения; многокритериальная оптимизация.

УДК :681.31

, проф., д. т.н., МАТИ-РГТУ им.

МАТЕМАТИЧЕСКАЯ ЛОГИКА И

НЕКОТОРЫЕ ЕЕ ПРИЛОЖЕНИЯ

ПРИЛОЖЕНИЯ. РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ ИЗ ОТДЕЛЬНЫХ КЛАССОВ В РАЗЛИЧНЫХ БАЗИСАХ

*Работа выполнена при финансовой поддержке РФФИ (грант

№ укр р).

Оглавление

7. Основные понятия и определения

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

7.2. Булевы функции, базисы, формулы и схемы, показатели

сложности

7.3 Примеры реализации булевых функций

8. Функциональные и разностные уравнения

8.1. Функциональные уравнения

8.2. Разностные уравнения

8.3. Некоторые эквивалентности на основе ФУ

9. Элементарные симметрические булевы функции

9.1. Элементарные симметрические полиномы (ЭСП) Жегалкина

9.2. Сложность функций из простых классов

9.3. Сложность ЭСП Жегалкина F2(n)

9.4. Сложность ЭСП Жегалкина F3(n)

9.5. Сложность ЭСП Жегалкина Fi(n) и Fn-(i-1)(n)

9.6. Краткая функциональная характеристика методов

9.7. Нижние оценки сложности ЭСП Жегалкина

10. Сложность реализации n-местной дизъюнкции в разных базисах

11. Сложность реализации линейной функции

11.1. Сложность на основе функционального уравнения типа 1

11.2. Сложность на основе функционального уравнения типа 2

12. Сложность булевых функций класса импликаций

12.1. Функции из класса импликаций

12.2. Сложность функций из класса ФЛП

12.3. Сложность в базисе G1

12.4. Сложность на основе ФУ типа 3

12.5. Сравнение методов

12.6. Сложность функций из класса ФПЛ

13. Мультиплексоры

14. Многокритериальная минимизация показателей сложности синтеза формул и схем

14.1. Сложность скобочных формул

14.2. Глубина булевых формул на основе кода

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

14.4. Таблицы с результатами для интеллектуализации синтеза

15. Некоторые числовые функции

15.1. Функция y = éxù

15.2. Функция y = ëxû

15.3. Функция y = {x}

Заключение

Литература

7. Основные понятия и определения

7.1. Проблема оптимальной реализации булевых функций из отдельных классов в разных базисах. Рассматривается проблема представления определенной булевой функции в классах формул и - схем из функциональных элементов (ФЭ) в разных базисах. Причем функции, в основном, характеризуются канонической или скобочной формой задания. Возможно также задание вектором ее значений. Задача, в общем случае, имеет много решений, качество-сложность получаемых при этом формул и схем оценивается при помощи дискретных функционалов. Начальным показателем сложности является размерность булевой функции – число переменных. Ее обобщением будем считать число символов переменных в формуле. Остальные рассматриваемые показатели качества (число подформул и глубина формулы; число ФЭ и глубина схемы) являются производными этого показателя в большей или меньшей степени. Повышение надежности схемы выполняется неявно (специальных методов повышения надежности здесь не рассматривается) [31].

По практическим соображениям показатели качества (функционалы) минимизируем. При представлении функций в классе формул для минимизации показателей сложности используются эквивалентные преобразования, включая получение скобочных формул, - в классе схем для минимизации числа ФЭ применяется ветвление их выходов [1-6].

Большая трудоемкость получения оптимального по какому-либо показателю решения, неизбежно использующего алгоритмы переборного характера, привела к отказу от стандартных подходов постановки задачи и ее решения [1-6]. В связи с этим изучаются различные подходы к разработке алгоритмов синтеза, заметно отличающихся по трудоемкости от переборных. В их числе имеется асимптотический подход, основывающийся на функции Шеннона. Используя его, [1] первым разработал метод и получил асимптотическую оценку числа элементов схемы, реализующей булеву функцию. Затем, развивая метод, асимптотическая оценка для глубины схемы получена в работе [8].

Зависимость между минимальными значениями глубины и сложности эквивалентных формул изучалась в работах [9-10] и были получены верхние оценки для глубины булевой функции. Представляя линейную функцию схемой из ФЭ, аналитически получил показатель сложности по числу ФЭ в схеме и доказал его минимальность [11].

В работах , и предложено ограничить трудоемкость синтеза и в ограниченном классе искать алгоритмы, приводящие к схемам наилучшего качества. В этих же работах показано, что в классе алгоритмов, заметно отличающихся по трудоемкости от переборных, далеко не всегда удается получить решение, сколько-нибудь близкое к оптимальному [3 -5 ].

Несмотря на имеющиеся успехи в области синтеза схем, однако, в целом, в теории булевых функций нет полных ответов на следующие вопросы. Как использование скобочных формул, математических моделей, улучшают качество проектируемых схем из ФЭ? Как ветвление выходов ФЭ позволяет минимизировать их число в схеме? Как зависит трудоемкость синтеза от результатов минимизации перечисленных выше показателей (как они связаны)? С помощью каких средств можно уменьшить трудоемкость синтеза и др.? В научной литературе приводятся и исследуются примеры, когда одна функция в некотором базисе имеет меньшие значения показателей сложности по сравнению с другим базисом, другая же функция, наоборот [2, 12, 13]. Для таких задач интересны ответы на вопросы: во сколько раз или как может измениться сложность функции при переходе из одного базиса в другой (и наоборот).

Имеющихся ответов на все эти вопросы в известных публикациях недостаточно [1-13]. Причем в [15] сказано: "Асимптотические оценки важны не только с точки зрения понимания сложности получаемых схем, но и как способ оценки качества алгоритмов синтеза. Однако при построении схем для конкретных функций асимптотически наилучшие методы синтеза часто не дают хороших результатов".

Тем не менее, поиск минимальных решений может быть успешным, но искать его следует на основе классификации множества булевых функций, совершенствования методов декомпозиции с привлечением понятия строение-структура [2-6, 31]. Поэтому в качестве математических моделей, для большей части рассматриваемых задач, выбраны симметрические булевы функции и их представления в классе формул и – схем из ФЭ.

Отметим, что синтезируемые схемы применяются при проектировании различных дискретных логических устройств для вычислительной и управляющей техники [14, 15].

Используемые обозначения:

éxù для приближения чисел с избытком ( наименьшее целое, не меньшее числа x ); ë x û для приближения чисел с недостатком ( наибольшее целое, не большее числа x ); следующие логические операции обозначаются двумя способами: конъюнкция как & или × (точка-знак умножения), но точкой иногда обозначается также арифметическое умножение; отрицание как Ø или надчеркивание над переменной, например, ` x; эквивалентность как Û. В записи формул для простоты иногда внешние скобки опускаем.

7.2. Булевы функции, базисы, формулы и схемы, показатели

сложности. Пусть f ( f (n) или f (X) ) - булева функция, зависящая от n существенных переменных из множества X={x1,…,xn}. Для функции f(n) и задающей ее формулы иногда используем одно обозначение, то есть под символом f(n) в зависимости от содержания абзаца понимаем функцию или задающую ее формулу.

Под базисом, в общем случае, понимаем произвольную конечную функционально полную систему булевых функций G={ gi ô i = 1, 2, ..., k }. В теоретических исследованиях и приложениях часто рассматривают базисы G1 = {&, Ú,` )} и G3 ={&, Å, 1} для всех булевых функций и - G2= {&, Ú} для монотонных функций.

При представлении булевой функции f(n) суперпозиционной формулой F над множеством функциональных символов применяются конструктивные операции из некоторого их множества W (перестановка элементарных конъюнкций-дизъюнкций в формуле, а в ней - переменных; замена подформулы новой переменной; вынесение общих множителей за скобки, обратные им операции и другие, а также эквивалентности) [4, 20]. Ниже они поясняются, поэтому обозначения последовательности проводимых операций опускаем. В качестве меры сложности-качества представления функции f формулой F или схемой S из ФЭ определяем соответствующие показатели (функционалы):

LБ(f, G) - число букв в формуле F, реализующей (задающей) функцию f, в классе формул в заданном базисе G;

LF(f , G ) - число подформул в F ;

DepF(f , G) - глубина F ;

LS(f , G ) - число ФЭ (ЛЭ) в схеме S;

DepS(f , G ) - глубина S, определяемая как наибольшее число ФЭ в цепочке, среди всех цепочек, соединяющих вход с выходом.

Постановка задачи. Итак, рассматривается, в основном, задача представления определенной булевой функции f(n) суперпозиционной формул F или схемой из функциональных элементов S в разных базисах G. При этом необходимо не только получить выше перечисленные показатели сложности, но и минимизировать их.

Между собой эти показатели имеют сложные связи. Один из главных показателей есть - LБ, он минимизируется за счет привлечения аппарата булевой алгебры и расширения класса моделей (скобочных формул) при реализации булевых функций. При этом в первую очередь, исключаются фиктивные переменные, не влияющие на значения функции. Уменьшение показателя LБ влечет уменьшение - LS. Это все приводит к увеличению надежности системы (специальных методов повышения надежности здесь не рассматривается). Заметим, что от показателя LБ разным образом зависят остальные из перечисленных выше показателей. При многокритериальной минимизации показателей качества синтеза – минимизация одного показателя качества может приводить к уменьшению или к возрастанию другого показателя (других). Например, минимизация LБ в классе скобочных формул (и затем реализация) приводит к минимизации LF и может приводить к уменьшению, или оставлять без изменения, или увеличивать глубину суперпозиционной формулы F (схемы S). В таких случаях при синтезе необходимо устанавливать приоритетность показателей.

При синтезе схем посредством минимизации показателя LS, наряду с отмеченным преобразованием формул к скобочному виду, является использование ветвления выходов ФЭ [4, 16]. Причем оно может быть (повторяемость переменных в формуле позволяет применять ветвление), но может и отсутствовать (такова повторяемость). Интуитивно, в общем случае, понятно, что, чем меньше различаются значения показателей LБ и n (сложности формулы по числу букв и размерности функции), тем меньше возможностей для применения ветвления и, наоборот, чем больше различаются значения показателей LБ и n, тем больше возможностей для применения ветвления. Итак, ветвление важное средство для минимизации показателей сложности синтезируемых схем, связанное с повторяемостью переменных в формуле (с показателем LБ). Но уменьшение показателя LS таким способом может приводить к увеличению глубины DepS схемы S (см. примеры раздела 7.3).

При синтезе схем применяется структурно-функциональная параллельная декомпозиция и DepS =DepF , если включается условием минимизации глубины DepF [28-35].

Сравнение дизъюнктивных нормальных форм (ДНФ), полиномов Жегалкина и других формул на основе их строения (вектора рангов элементарных конъюнкций) применяется также при сравнении простых функций по их строению. Например, отношение проще в одном классе простых функций (g&(2) < g&(3) -отношение строгого предшествования). Такой подход может быть использован при сравнении базисов на основе следующего определения [31-34].

Определение 7.1. Базис G назовем порождающим, а базис G¢ - порожденным, если базис G¢ получен из базиса G добавлением по крайней мере одной новой базисной функции (с увеличением местности имеющейся в базисе функции или функции-формулы другого строения), что обозначается G < G¢.

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

Упорядочивание множества базисов отношением предшествования (на основе определения 7.1), отлично от упорядочивания [2, 12, 13].

Рассмотрим пример построения упорядоченного множества базисов для базиса G1 = {&, Ú,` }. В обозначении порожденного добавляется второй меняющийся индекс (номер члена последовательности), например, запишем для функциональных символов

G1,1 = { g&(2), gÚ(2), gØ (1), g&(3)},

G1,2 ={g&(2), gÚ(2), gØ (1), g&(3), g®(2)},

G1,3={g&(2), gÚ(2), gØ (1), g&(3), g®(2), gÅ (2) } и т. д.

В общем случае будем говорить, что последовательность Gi,j, j = 1, 2, …, k, порождается базисом Gi , i=1,2,3 и др.

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

Утверждение 7.1. Пусть порождающий базис G2, а порожденный базис G¢= G2 È G0, где базисные функции gj ÎG0 – конъюнкция или дизъюнкция, местности больше двух, а также бесповторные монотонные ДНФ. Тогда для верхних оценок сложности представления функции f (n) в классе формул в базисах G2 и G¢ выполняются соответственно неравенства

LF(f (n), G2) ³ LF(f (n), G¢) и DepF(f (n), G2) ³ DepF(f (n), G¢). (7.1)

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

Если при помощи функции g удается только увеличивать значение показателя качества (или повторить имеющееся), то представление функции f (n) в базисе G¢ всегда можно выполнять в порождающем базисе G2. Он содержится в порожденном базисе G¢. В таком случае для оценок показателей качества в утверждении 7.1 получаем равенство, то есть всегда существует реализация функции без понижения качества.

Ввиду определенной свободы выбора базисной функции g утверждение 7.1 несложно проверяется в классах функций & и Ú.

Напомним факты, используемые ниже. Для функции f(n), например, из класса & в базисе g&(n¢ ), n¢ ³2, показатели сложности вычисляются следующим образом (аналогично для функций из классов Ú и Å) [31]:

LF(f& (n), g&(n¢ )) = é(n –1)/(n¢ –1)ù и DepF(f&(n), g&(n¢ )) = élogn¢ nù; (7.2)

если функция f(n) задается монотонной ДНФ, то ее глубина в базисе G¢={g&(n¢ ), gÚ(m¢ )}È G2, n¢ ³2 и m¢ ³ 2, характеризуется следующей верхней оценкой

DepF(f (n), G¢) = élogn¢ r1ù + élogm¢ mù. (7.3)

Итак, в силу неубывания функции éxù при n¢ ³3 разность

LF(f&(n), g&(2 )) – LF(f& (n), g&(n¢ )) = n –1– é( n –1)/( n¢ –1)ù ³ 0, то есть первое неравенство в (7.1) выполняется.

При этом функция logn¢ n убывает при возрастании n¢ для конкретного n и выполняется второе неравенство в (7.1), так как

DepF(f&(n), g&(2 )) – DepF(f& (n), g&(n¢ )) = élog2 nù – élogn¢ nù ³ 0.

Обобщением рассмотренного случая является задание функции f(n) ДНФ или скобочной формулой. Рассмотрение их для утверждения (7.1) приводит к подформулам fi из классов функций & и Ú понимаемых следующим образом. Исходная функция f(n) представляется в виде суперпозиции функций fi, i=1,2,…, p, из выше рассмотренных классов, для которых утверждение выполняется. Число переменных в подформуле fi есть ее сложность. Подформулу fi назовем максимальной, если она содержит наибольшее число букв (или равное) среди всех таких подформул суперпозиции, то есть удаление в ней любой переменной или, наоборот, добавление новой переменной из X приводит к формуле, которая не реализует функцию f(n).

Для ДНФ, обозначая элементарные конъюнкции (ЭК), ранга больших 1, за новые переменные, получаем задание функции f(n) такой суперпозицией, для функций которых утверждение выполняется. Причем максимальная подформула это ЭК максимального ранга.

Если в скобочной формуле f(n) сложность максимальной подформулы равна 1, то это крайний случай. Вычисление по такой формуле однозначно определено. Для него несложно привести пример базисной функции g, когда добавление в базис G¢ функции g позволяет уменьшить показатели LF и DepF.

Пример 7.1. Представить функцию f(7) = (((x1Úx2) x3 Ú x4 ) x5 Ú x6 ) x7 в базисе G2 и выбрать g таким образом, чтобы в базисе G¢={g(3)}È G2 уменьшить показатели сложности LF и DepF.

В базисе G2, начиная с дизъюнкции x1Úx2, последовательно получаем формулу F и оценки ее сложности LF(f(7), G2) = 6 и DepF(f(7), G2)=6. Далее в качестве базисной функции g выбираем - g(3)(t1, t2, t3) = (t1Út2) t3 . Тогда в базисе G¢, начиная с (x1Úx2) x3, аналогично получаем -

f(7) = g(3)(g(3)(g(3)(x1,x2, x3), x4, x5), x6, x7) и LF(f(7), G¢) =3, DepF (f(7), G¢)=3.

Итого, рассмотренный пример в частном крайнем случае подтверждает утверждение 7.1, которое будет иметь место и для базиса G3 .

Теперь для функции f (n), используя декомпозицию в базисах Gi , i=2, 3, получаем, что для строго упорядоченного конечного множества базисов

Gi < Gi,1 < G i,2 <… < G i, k (7.4)

следует

LF1(f (n), G i)max ³ LF2(f (n), G i,1) ³... ³ LFk(f (n), G i, k), (7.5)

DepF1(f (n), G i) max ³ DepF2(f (n), G i,1) ³ ... ³ DepFk(f (n), G i, k), (7.6)

т. е. выбирая определенные последовательности (7.4), пополняемые новыми базисными элементами, будем уменьшать оценки (7.5) и (7.6) сложности представления булевых функций в различных базисах.

Замечание 7.1. Из (7.5) и (7.6) следует, что порождающие базисы Gi, i=1,2,3, в своих последовательностях доставляют максимальные значения показателей сложности (верхние оценки) суперпозиционной формулы F. Поэтому, в первую очередь, следует изучать сложность реализации булевых функций в порождающих базисах.

Качество реализации функции f в классе формул в базисах G и G¢ характеризуется неравенствами (7.1), которое переносится изоморфно на получаемую схему без ветвления.

При сравнении базиса G1, например, с базисом G4={gШ(2)} (штрих Шеффера) суммарную сложность по числу подформул получим при представлении функций базиса G1 в базисе G4 и, наоборот, при представлении функции базиса G4 в базисе G1 . Обозначаем суммарную сложность базиса G1 в базисе G4 по числу подформул через LG1-G4, а соответствующую сложность базиса G4 в базисе G1 через LG4-G1. В первом случае получаем

g&( x1, x2) = x1×x2 = gШ(gШ ( x1, x2), gШ ( x1, x2)) и LF(g&(2), G4) =3;

gÚ( x1, x2) = x1Úx2 = g1(g1( x1, x1), g1( x2, x2)) и LF(gÚ (2), G4) =3;

gØ(x1)= `x1= g1( x1, x1) и LF(gØ(2), G4) =1 и суммарная сложность (из G1 в G4) LG1-G4=7.

Аналогично,

gШ ( x1, x2) = gØ (g& (x1, x1)) и LG4-G1= LF(g1 (2), G1) =2.

Отсюда эффективность базисов характеризуется отношением

LG4-G1/LG1-G4 = 2/7.

В [33-36] получены оценки показателя LБ для функций fÚ (n) и fÅ(n) в базисах G1 и G3:

LБ(fÚ (n), G1 )= n, (7.7)

LБ(fÚ (n), G3 )= n 2n-1, (7.8)

LБ(fÚ (n), G3 )= 3 2n-1- 2, (7.9)

LБ(fÚ (n), G3 )= n2, n=2s, s=1,2, … , (7.10)

LБ(fÅ (n), G3 )= n, (7.11)

LБ( fÅ(n), G1 )= 2n + 2n-1- 2 = 3 2n-1 -

Из (7.7) и (7и (7.9), (7.7) и (7.10), (7.12) и (7.11) ) определяем:

LБ(fÚ (n), G3 ) / LБ(fÚ (n), G1 )= 2n-1 ,

LБ(fÚ (n), G3 ) / LБ(fÚ (n), G1 )= (3 2n-1- 2 ) / n,

LБ(fÚ (n), G3) / LБ(fÚ (n), G1 )= n, n=2s, s=1,2, …,

LБ(fÅ(n), G1) / LБ(fÅ(n), G3 )= (3 2n-1- 2 ) / n.

Из этих соотношений следует, что отношение значений сложности LБ представления функции f(n) зависит от класса функций, базиса и метода представления. Аналогично получаем для других показателей сложности.

7.3 Примеры реализации булевых функций. Рассмотрим примеры представления произвольной булевой функции f(n), задаваемой ДНФ, с целью изучения влияния средств реализации (скобочных формул и ветвление выходов ФЭ) на получение величины показателя качества этого представления (в классах формул и схем) [43-46].

Пример 7.2. Булева функция f (4) задается ДНФ FДНФ =x1x2x3 Úx1x2x4. Представить ее в базисе G1 (соответствующих ФЭ), минимизируя оценки показателей сложности, в классе формул (в классе схем с ветвлением и без). Исходные данные: r = (3, 3), n = 4, n0 =2, n1 =1, n2 =1.

1.1. В классе ДНФ получаем: f (4)= gÚ (g& (g&( x1, x2), x3), g& (g&(x1, x2), x4)) ;

LБ(FДНФ, G1 )=6, LF(FДНФ, G1 )= 5, Dep F(FДНФ, G1 )= 3.

1.2. В классе скобочных формул получаем

FДНФ = x1x2x3 Ú x1x2x4 = x1x2(x3 Ú x4) = Fскоб = g& (g&( x1, x2), gÚ ( x4, x5)) ;

Lб(Fскоб, G1 ) = 4, LF(Fскоб, G1 ) = 3, Dep F( Fскоб, G1 ) = 2.

1.3. В классе схем без ветвления (на основе ДНФ) получаем значения показателей сложности (см. рис. 7.1): LS(FДНФ, G1 )=5, Dep S(FДНФ, G1 )=3.

1.4. В классе схем с ветвлением (на основе ДНФ) получаем значения показателей сложности (см. рис. 7.2): LS(FДНФ, G1 )=4, Dep S(FДНФ, G1 )=3.

1.5. В классе схем без ветвления (на основе скобочной формулы) получаем значения показателей сложности (см. рис. 7.3):

LS(Fскоб, G1 ) = 3, Dep S( Fскоб, G1 ) = 2.

FДНФ

Ú

&

&

&

&

x3

x1

x2

x1

x2

x4

Рис. 7.1. Схема без ветвления (реализация ДНФ)