Математические модели для интеллектуализации синтеза комбинационных схем

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДЛЯ ИНТЕЛЛЕКТУАЛИЗАЦИИ

СИНТЕЗА КОМБИНАЦИОННЫХ СХЕМ

МАТИ-РГТУ им. К.Э. Циолковского,

г. Москва

E-mail: [e-mail]

Введение. При проектировании многопроцессорных вычислительных и управляющих систем особое место занимает синтез комбинационных схем. В работе исследуются представления булевой функции f, зависящей от переменных x1 , …, xn , n = 2, 3, …, в классе формул F в некотором функционально полном базисе G ={ g1 , …, gk } и/или в классе комбинационных схем (схем S из соответствующих базису G функциональных элементов – ФЭ, причем для функций и реализующих их ФЭ используются одни обозначения, что не помешает пониманию). Целью изучения различных представлений такой функции является минимизация ее основных показателей сложности. В первом случае получаем суперпозиционную формулу F в базисе G, во втором случае – схему (с ветвлением и без) S из ФЭ, и соответствующие значения показателей сложности (качества) этого представления, включая случаи получения достижимых верхних-нижних или минимальных оценок сложности. Полученные результаты полезны при разработке алгоритмов интеллектуального синтеза дискретных логических управляющих и вычислительных устройств. В работе используются, в основном, базисы G1 = {&, Ú,` } и G2 = {&, Å, 1}.

Сложность (качество) представления булевой функции f в заданном базисе Gi, i =1, 2, в классе формул F (или схем S) определяется при помощи соответствующих функционалов [1]: LБ(f, G ) – суммарное число вхождений символов переменных в формулу F , реализующую функцию f в базисе G (часто также называется сложностью); LF(f , G ) - число подформул в F; DepF(f , G ) -глубина F ; LS(f , G ) - число ФЭ в схеме S (для схем без ветвления LF = LS ) ; DepS(f, G ) - глубина схемы S, определяемая как наибольшее число ФЭ в цепочке, среди всех цепочек, соединяющих вход с выходом. Для принятых обозначений также используем сокращения, например, LБ(f ) или просто LБ .

Вопросам представления булевых функций посвящено большое число работ, из которых выделим -, относящиеся к проблематике сложности. В [2-4] отмечается, что булева функция f (2) =x1 Å x2=`x1×x2Ú x1×`x2 в базисе G2 имеет сложность LБ =2, а в базисе G1 - LБ =4, т. е. функция в разных базисах может иметь различные значения сложности LБ. Представляют интерес вопросы: во сколько раз или как может измениться сложность LБ(f (n), G) функции f (n) при переходе из G1 в G2 (и наоборот). показал, что сложность LБ почти всех булевых функций асимптотически не зависит от базиса, и, тем не менее, имеющиеся результаты, относящиеся к асимптотическим подходам, неполны [2-4]. В других работах изучается зависимость между минимальными значениями глубины и сложности эквивалентных формул [5-8].

1. Функциональные уравнения - ФУ. В [10-12] изложен конструктивный способ построения новых функций из уже заданных на основе рекурсивных определений (ФУ). Пусть X={ x1 , …, xn } - множество булевых переменных, рекурсию определим следующим образом

f (n1+n2)(X) = h ( f (n1)(X1), f (n2)(X2)), (1)

где X1ÈX2 = X, X1ÇX2 = Æ, êX1 ê= n1 ³ 1, êX2 ê= n2 ³ 1, n1³ n2 (для определенности) и n = n1 + n2, h(2) и g(2) - двухместные булевы функции, задающие начальные условия (н. у.), причем f (2)= g(2) .

Назовем (1) основным функциональным уравнением (ФУ). При n1= n–1, n2 = 1 это будет ФУ типа 1, которое принимает вид

f (n) = h ( f (n-1) , xn); (2)

при n =2s, s = 1,2,…, n1 = n2 = n/2 это будет ФУ типа 2

f (n)(X) = h ( f (n/2)(X1), f (n/2)(X2

2. ФУ для простых классов функций. Рассмотрим основные типы ФУ для классов функций &, Ú, Å и ~ , обладающих свойствами коммутативности и ассоциативности (операции), что позволяет получать для них ФУ одинаковым образом. Пусть, например, булева функция f (n) - n-местная дизъюнкция над множеством X переменных, gÚ (2) - базисная функция и h(2)=gÚ (2). Из (2) получаем следующее ФУ типа 1

f (n)(X)= h(2)( f (n-1) , xn)= (f (n-1) Ú xn), (4)

n= 3, 4, … . Заметим, что ФУ (2) и (3) порождают семейства ФУ для рассматриваемых показателей сложности, т. е. на основе (4) для функционалов сложности устанавливаем рекуррентные соотношения – ФУ:

LБ(f (n), gÚ (2) ) = LБ(f (n-1), gÚ (2) )+1, LF (f (n), gÚ (2) ) = LF (f (n-1), gÚ (2) )+1,

Dep F(f (n), gÚ (2))= Dep F( f (n-1), gÚ (2) )+ 1, (5)

н. у.:LБ( f (2),gÚ (2))=2,LF(f (2),gÚ (2))=1, LF(h(2),gÚ (2))=1, Dep F(f (2),gÚ (2))=1. (6)

Откуда по индукции получаем LБ(f (n),gÚ (2))=n,

LF (f (n),gÚ (2))=LS (f (n),gÚ (2))=Dep F(f (n),gÚ (2))=DepS(f (n),gÚ (2))= n -1. (7)

Если n =2s, s = 1,2,…, то n1=n2=n/2 и из (3) получаем ФУ типа 2

f (n)(X) = h( f (n/2)(X1), f (n/2)(X2)) = (f (n/2)(X1) Ú f (n/2)(X2)), (8)

для показателей которого устанавливаем рекуррентные соотношения

LБ(f (n)(X),gÚ (2)) =2LБ(f (n/2)(X1), gÚ (2)), LF (f (n),gÚ (2))=2LF (f (n/2)(X1), gÚ (2))+1, Dep F(f (n), gÚ (2))=Dep F( f(n/2)(X1), gÚ (2))+1,

LS (f (n), gÚ (2) ) = LS (f (n/2)(X1), gÚ (2) )+LS (f (n/2)(X2), gÚ (2) )+1,

Dep S(f (n), gÚ (2)) = Dep S( f(n/2)(X1), gÚ (2) )+ 1, (9)

откуда, используя начальные условия (н. у.) (6), по индукции получаем

LБ(f (n), gÚ (2)) = n, LF (f (n), gÚ (2)) = n-1= LS (f (n), gÚ (2) ),

DepF(f (n), gÚ (2))= s= log2n = é log2n ù = DepS (f (n), gÚ (2)). (10)

Замечание 1. Показатели сложности (7) и (10) получены ранее, причем (10) получены для n ³ 2 [1]. Здесь они получены новым методом – ФУ, причем, ФУ типа 1 определяет алгоритм последовательной декомпозиции, минимальной по числу подформул и максимальной по глубине, а ФУ типа 2 - распараллеливающей декомпозиции, минимальной по числу подформул и по глубине (формально ФУ1 ³ ФУ2 ).

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

Рассмотрим применение ФУ для получения показателей сложности пре-дставления n-местной дизъюнкции f (n) = x1Ú … Ú xn в разных базисах.

3.1. Показатели сложности в базисе G1. Они есть (7) и (10) - min.

3.2. Представление и сложность в базисе G2 на основе ФУ типа 1 (два варианта; класс схем с ветвлением). Применяя ФУ типа 1, вариант 1 (ФУ типа 1-1), получаем рекуррентное соотношение

f (n) = h ( f (n-1), xn)=( f (n-1) × xn Å f (n-1) Å xn), n=2,3,…, (11)

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

LБ(f (n), G2 )= 2n + 2n-1- 2 = 3×2n-1 - 2, LF(f (n), G2 ) = 3× (2n-1 - 1),

LS(f (n), G2 ) = 3× (n - 1), DepF ( f (n), G2 )=DepS ( f (n), G2 )= 2×(n - 1). (12)

Для (11) вариант 2 применения ФУ дает ФУ типа 1-2

f (n) = h ( f (n-1), xn)=( f (n-1) ×( xn Å 1) Å xn), n=2,3,… . (13)

откуда аналогично п.2 индукцией по n получаем

LБ(f (n), G2 )= 3n - 2, LF(f (n), G2 ) =3×(n - 1), LS(f (n), G2 ) = 3×(n - 1),

DepF ( f (n), G2 )=DepS ( f (n), G2 )= 3×(n - 1). (14)

3.3. Представление и сложность в базисе G2 на основе ФУ типа 2 (n = 2s, s = 1,2,…). Аналогично п.3.2 получаем ФУ:

типа 2-1 f (n)= (h(2)( f1 (n/2) , f2 (n/2)))= ( f1 (n/2) f2 (n/2) Å f1 (n/2) Å f2 (n/2)

и выражения для показателей сложности

LБ(f (n), G2 ) = 4s = n2, LF( f (n), G2 ) = n2 – 1, LS(f(n), G3)=3×(n-1),

DepF( f (n), G2)=DepS( f (n), G2 )= 2× élog2 nù; (16)

типа 2-2 и выражения для показателей сложности

f (n)= (h(2)( f1 (n/2) , f2 (n/2))) = ( f1 (n/2) ( f2 (n/2)Å1) Å f2 (n/2)) (17)

s=log2 n , LБ(f (n), G2 ) = (3s+1-1) / 2, LF( f (n), G2 ) = 3(3s-1) / 2,

LS(f(n), G3)=3×(n-1), DepF( f (n), G2)=DepS( f (n), G2 )= 3× élog2 nù. (18)

3.4. Сравнение показателей сложности на основе ФУ типа 1 и –2. Для обоих типов ФУ для варианта 2 получено: уменьшение значений показателей LБ и LF, сохранение - LS, увеличение - DepF и DepS.

4. Интеллектуализация синтеза комбинационных схем

Совершенствовать систему синтеза можно по разным направлениям, в том числе, повышая интеллектуальный интерфейс, организуя взаимодействие системы с пользователем на основе понятий и терминов предметной области (хранение, использование и пополнение представленных в статье результатов в базе знаний). Методы оставляют широкую свободу в выборе элементной базы (логические-ИС, оптические и др. элементы). Понимая выводимость как получение и применение рекуррентных соотношений, для продукционной модели представления знаний можно применять, например, правила: Если (fi(k), Gj ), то (F, LБ(ik), LF(ik), DepF(ik), LS(ik), DepS(ik)); причем для правильного условия обеспечивается правильное (минимальное или близкое к нему по одному или нескольким показателям) заключение (и истинность импликации).

[1] Чебурахин дискретных управляющих систем и математическое моделирование: алгоритмы, программы. М.: Физматлит, 2004.

[2] Черухин сравнения булевых базисов. http://mech. math. msu. su/department/dm/dmmc/Science/boolb. htm. 2005.

[3] О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960.

[4] О реализации линейных функций в базисе {&, Ú, Ø} //ДАН СССР. 1961. Т. 136. №3, с. 553-555.

[5] О соотношении между сложностью и глубиной формул. Методы дискретного анализа в синтезе управляющих систем, вып. 32, Новосибирск, 1978, с. 76-94.

[6] О связи между глубиной и сложностью эквивалентных формул и о глубине монотонных функций алгебры логики // Проблемы кибернетики. Вып. 38. М.: Наука, 1981, с. 269-271.

[7] Редькин минимальности некоторых схем из функциональных элементов // Проблемы кибернетики, 1970, вып. 23.

[8] Чебурахин и показатели сложности формул. Тез. докл. конф. ”Проблемы теоретической кибернетики” (Пенза, 23-28 мая 2005 г.). М.: Изд-во МГУ, 2005, с. 166.

[9] Успенский о вычислимых функциях. М.: 1960.

[10] Мальцев и рекурсивные функции. М.: 1965.

[11] , Летичевский теория проектирования вычислительных систем. М.: Наука, 1988.

[12] Чебурахин булевых функций для интеллектуальных систем синтеза цифровых ИС // Изв. РАН. ТиСУ. №

[13] Чебурахин уравнения и сложность булевых функций в разных базисах // Труды VII Межд. конф. “Дискретные модели в теории управляющих систем”. М.: “МАКС Пресс”, 2006.