УДК 519.7: 681.3

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДЛЯ ИНТЕЛЛЕКТУАЛИЗАЦИИ СИНТЕЗА ДИСКРЕТНЫХ ЛОГИЧЕСКИХ УПРАВЛЯЮЩИХ И ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ *

ã 2007 г.

МАТИ-РГТУ им.

Поступила в редакцию 20.12.06 г., после доработки 08.06.07 г.

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

Введение. Системы автоматического управления сложнейшими объектами и процессами, интеллектуальные пакеты прикладных программ, системы планирования вычислений, автоматизированного проектирования, экспертные системы - вот далеко не полный перечень аппаратных и программных средств, без которых немыслим сейчас научно-технический прогресс. Основная черта, выделяющая эти системы из всех остальных, состоит в том, что они содержат знания о той проблемной области, в которой работают, и о своих возможностях по решению задач в ней [1-4].

В значительной мере для описания, анализа и синтеза этих систем (устройств) используется аппарат математической кибернетики [2-7], из которого в работе в основном делается акцент на формулы алгебры

НЕ нашли? Не то? Что вы ищете?

______________________________________________________________________

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

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

Физическое проектирование таких систем в настоящее время характеризуется широким использованием достижений микроэлектроники [8,9]. Элементной базой для синтеза дискретных логических управляющих и вычислительных устройств выступают малые, средние, большие, сверхбольшие и ультрабольшие интегральные схемы (МИС, СИС, БИС, СБИС, УБИС). Стремительное развитие микроэлектроники, проявляющееся в постоянном совершенствовании и создании новых элементов базиса, содержащего микросхемы различной степени интеграции и различные микропроцессорные средства, с одной стороны, создает благоприятные предпосылки для проектирования новой высокопроизводительной и надежной вычислительной и управляющей техники, а с другой - ставит ряд трудно решаемых проблем перед разработчиками этой техники. Эти проблемы связаны: с выбором для каждой части синтезируемой системы наиболее соответствующего типа интегральные схемы (ИС); с минимизацией площади кристалла, глубины схемы, числа вентилей (логических элементов (ЛЭ)), суммарной длины проводников как между ИС так и между ЛЭ и других показателей качества (влияющих на быстродействие, надежность и многие другие характеристики), т. е. с рациональным использованием всех имеющихся возможностей выбранного базиса [8 - 12]. Таким образом, в общем случае для указанных мер сложности получаем оптимизационную многокритериальную задачу.

При этом в [13-15] отмечается, что одна булева функция может иметь различную сложность (по числу букв) в разных базисах. Так возникла задача сравнения базисов [14]. Если ограничиваться базисами, состоящими из двухместных функций, то для них получено полное описание структуры (отношения предшествования, эквивалентности), но в общем виде полное описание структуры базисов пока не доступно в виду ее сложности [13-15]. В других работах [16, 17] изучаются показатели сложности (число букв и глубина) эквивалентных формул в стандартном базисе и в общем виде установлена зависимость между минимальными значениями глубины и сложности эквивалентных формул [16]; в [17] указанная зависимость уточнена и приведены хорошие верхние оценки для глубины, при использовании известных оценок для их сложности.

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

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

1. Постановка задачи. Рассматривается представление произвольной булевой функции f(n) (или f ) над n-множеством X переменных x1 , …, xn в классе формул F в некотором базисе G ={ g1 , …, gk } или в классе схем S (с ветвлением и без) из соответствующих (базису G) функциональных элементов (ФЭ), которым в дальнейшем на других этапах синтеза сопоставляются ЛЭ интегральных схем. В первом случае получаем суперпозиционную формулу F в базисе G, во втором случае - схему S из ФЭ и соответствующие показатели сложности, качества (по числу букв в формуле - LБ, подформул - LF, глубине формулы - Dep F ; по числу ФЭ - LS , по глубине схемы - DepS) этого представления для обоих случаев. Значения показателей сложности рассматриваемой функции, а значит, и системы функций применяются для синтеза оптимальных (по различным показателям сложности) дискретных логических управляющих и вычислительных устройств. Другие показатели (выбор типа ИС, суммарная длина проводников и др.), представляющие также интерес для практики, в статье не рассматриваются.

Цель работы состоит в расширении круга знаний о предметной области синтеза дискретных логических управляющих и вычислительных устройств для качественного получения результатов синтеза с минимальной вычислительной сложностью. В [7, 18-20] изложен конструктивный способ построения новых функций из уже заданных на основе рекурсивных определений. Современная точка зрения на рекурсивные определения трактует их как специальный вид функциональных уравнений. Различные области их применения, а также компактность и структурированность позволяют ожидать хороших результатов в задачах, в которых особо остро ощущается проблема размерности. Поэтому в работе они применяются с целью выяснения различных вопросов сложности булевых функций, а также получения основного прототипа синтезируемой логической схемы.

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

2. Функциональные уравнения. Рассмотрим конструктивный метод задания булевой функции (класса булевых функций) при помощи функциональных уравнений (ФУ). В общем виде примитивную рекурсию определим следующим образом: пусть X = { x1 , x2 , …, xn } - множество булевых переменных, тогда

(2.1)

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

Если анализировать процедуру (2.1) справа налево, то получаем класс функций одного типа с возрастающим числом аргументов. Двигаясь слева направо (к заданной функции f (n) ) и применяя (2.1) к подфункциям до конца, осуществим полную декомпозицию f (n) в базисе функций g(2) и h(2), т. е. одним из методов декомпозиции булевых функций может являться метод поиска некоторого ФУ (2.1), рассматриваемого слева направо. При этом декомпозиция обладает дополнительными возможностями для определения значений различных показателей сложности булевых функций в разных базисах.

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

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

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

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

где конечное n-множество аргументов разбивается пополам (класс функции f (n) сохраняется, т. е. fi = fi (n/2)= f(n/2)(Xi), i=1, 2, индексы у функций - только для различия функций по аргументам), причем используются следующие одноместные функции f1=f(1)(x1)=x1 и f2=f(1)(x2) =x2. В общем случае, для заданного n =2,3,4,… (2.1) можно рассматривать как: уравнение относительно искомой функции f (n) = f (n1+n2), позволяющее конструктивно ее находить в определенном базисе с показателями сложности; метод декомпозиции заданной булевой функции f(n); метод получения новых эквивалентностей; метод вычисления определенных булевых формул. Поэтому решение некоторых типов логических задач (классов задач, варьируя начальными условиями) можно свести к получению таких уравнений.

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

Из (2.2) получаем следующее ФУ типа 1:

f (n)(X)= h(2)( f (n-1) , xn)= (f (n-1) & xn), (3.1)

n=2, 3, … Для показателей сложности (по числу букв, подформул и глубине формулы F ) устанавливаем рекуррентные соотношения

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,

причем 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.

Откуда по индукции

LБ(f (n), g&(2) ) = n, (3.2)

LF (f (n), g&(2) ) = n - 1, (3.3)

Dep F(f (n), g&(2))= n -1. (3.4)

Аналогично для схем из ФЭ (без ветвления)

LS (f (n), g&(2) ) = n - 1, (3.5)

DepS(f (n), g&(2))= n -1. (3.6)

Если n =2s, s = 1,2,…, то n1=n2=n/2 и из (2.3) приходим к ФУ типа 2

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

где X1ÈX2 = X, X1ÇX2 = Æ. Устанавливаем рекуррентные соотношения

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,

причем 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,

откуда индукцией по n имеем

LБ(f (n), g&(2) ) = n, (3.8)

LF (f (n), g&(2) ) = n - 1, (3.9)

DepF(f (n), g&(2))= s = log2n = é log2n ù . (3.10)

Замечание. Показатели сложности (3.2)-(3.4) и (3.8)-(3.10) совпадают с [22-24], принимая экстремальные значения, причем ФУ типа 1 определяет алгоритм последовательной декомпозиции (минимальный по числу подформул и максимальный по глубине), а ФУ типа 2 - параллельной декомпозиции (минимальный по числу подформул и глубине).

Подобным образом для схем из ФЭ (без ветвления)

LS (f (n), g&(2) ) = n - 1, (3.11)

DepS (f (n), g&(2))= s = log2n = é log2n ù . (3.12)

Сравнивая (3.5), (3.6) и соответственно (3.11), (3.12), дополним замечание: параллельная декомпозиция при синтезе схем позволяет получать требуемые минимальные значения по глубине (n >3) по сравнению с последовательной при равенстве по числу ФЭ [24].

4. Сложность n-местной дизъюнкции в базисе G3 на основе ФУ типа 2. Сложность представления n-местной дизъюнкции

f (n)= x1Ú x2 Ú … Ú xn (4.1)

в базисе G3 = {&, Å, 1} на основе ФУ типа 1 рассмотрена в [21], поэтому для сравнения представляет интерес получение аналогичных результатов с помощью ФУ типа 2. По числу случаев ФУ будет два – типа 2-1 и типа 2-2.

4.1. Случай n=2s, s =1,2,… На основе (2.3) для функции (4.1) и выделенного случая составляем ФУ типа 2-1 в базисе G3

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

с начальными условиями f (2)(x1 ,x2)=g(2)(x1, x2)=(x1x2Åx1Åx2) и h(2)( t1 , t2) = =(t1t2Åt1Åt2); используем обозначение, введенное ранее: fi = fi (n/2)= f (n/2)(Xi), i=1, 2. Заметим, что для оптимизации схемной реализации функции (4.2) эффективно ветвление, а также преобразование ФУ (4.2) к виду (типа 2-2)

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

ФУ (4.2) последовательно применяется для n = 2, 4, 8, …, позволяя получить любую заявленную функцию f (n), n = 2s, s = 1,2,…, в G3. Если рассматривать левую часть (4.2) как формулу в G1, а с правой частью повторять эти действия (разбиение функции на подфункции с одинаковым числом переменных и дальнейшее преобразование) необходимое число раз, то имеем эквивалентность в базисе G1 È G3.

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

LБ(f (n), G3 ) = 2×(LБ(, G3 )+LБ(, G3 )),

LF(f (n), G3 ) = 2×(LF(, G3 )+LF(, G3 ))+3,

LS(f (n), G3 )= LS(, G3 )+LS(, G3 )+3,

DepF( f (n), G3 )= DepF(, G3)+ 2,

DepS( f (n), G3 )= DepS(, G3)+ 2,

причем имеют место начальные условия fÚ(2) = gÚ(2) = x1x2Åx1Åx2,

h(2)( t1 , t2) = t1t2Åt1Åt2 , LБ(f (2), G3 )= LБ(h (2), G3 )= 4,

LF(f (2), G3 )= LF(h (2), G3 )= 3, LS(f (2), G3 )= LS(h (2), G3 )= 3,

DepF(f (2), G3) = DepF(h (2), G3) = 2, DepS(f (2), G3) = DepS(h (2), G3) = 2,

откуда индукцией по s приходим к выражениям

LБ(f (n), G3 ) = 4s = n2, (4.3)

LF( f (n), G3 ) = n2 – 1, (4.4)

LS(f(n), G3)=3×(n-1) (применялись схемы с ветвлением), (4.5)

DepF( f (n), G3)=DepS( f (n), G3 )=DepS(, G3)+2 = 2 élog2 nù. (4.6)

4.2. Обобщение на случай произвольного n (для случая разд. 4.1). Если n ³ 2 и n ¹ 2s, s = 1,2,…, то, используя известное свойство булевой алгебры, в формулу (4.1) дописываем повторяющихся слагаемых (функция сохраняется) и получаем соответственно N = LБ(f (n),G1) = =2s, s=élog2 nù , иначе (n=2s) N = LБ(f (n), G1)=n. Тогда (4.3)-(4.6) можно считать верхними достижимыми оценками соответствующих показателей сложности функции данного случая, причем они, безусловно, сохранятся при увеличении местности базисных функций

LБ(f (n), G3 ) £ N2,

LF( f (n), G3 ) £ N2 – 1,

LS(f (n), G3 ) £ 3 (N - 1),

DepF( f (n), G3) £ 2 élog2 Nù,

DepS( f (n), G3 ) £ 2 élog2 Nù.

В силу монотонности функционалов (4.3)-(4.6) находим также нижние оценки. Выразим все оценки через число переменных n.

< LБ(f (n), G3 ) £, (4.7)

– 1 < LF( f (n), G3 ) £ – 1, (4.8)

3 ( - 1) < LS(f (n), G3 ) £ 3 ( - 1), (4.9)

2×( élog2 n ù - 1) < DepF( f (n), G3) £ 2 élog2 n ù (4.10)

2×( élog2 n ù - 1) < DepS( f (n), G3 ) £ 2 élog2 n ù. (4.11)

В этих оценках значения показателей LS и DepS соответствуют схеме с ветвлением.

4.3. Сравнение показателей сложности на основе ФУ типа 1 и 2. Из синтеза минимальных по числу букв формул, как правило, автоматически следует оптимизация (включая минимизацию) по многим другим показателям на последующих этапах синтеза схем. При этом могут применяться дополнительные методы, относящиеся к оптимизации синтеза схемы по одному или нескольким показателям. Поэтому сравним результаты представления булевой функции на основе ФУ типа 1 и 2 по показателю LБ

LБ(f (n), G3 )типа1 - LБ(f (n), G3 )типа2 = 3×2n-1 - 2 - n2 = 0.

При n = 2 (s =1), т. е. для обоих типов ФУ имеем одну функцию (результаты совпадают). Для остальных значений s >1 разность положительна, что означает приоритетность, эффективность ФУ типа 2 по сравнению с типом 1 (по отмеченному показателю сложности; условно это отметим как ФУ1 ³ ФУ2).

5. Сложность n-местной линейной функции в базисе G1 на основе ФУ типа 2. Сложность представления n-местной линейной функции

f(n) = x1 Å x2 Å…Å xn (5.1)

в базисе G1 = {&, Ú,` } на основе ФУ типа 1 определена в [21], поэтому важны аналогичные результаты на основе ФУ типа 2.

5.1. Случай n=2s, s =1,2,… Используем далее технологию получения оценок сложности на основе ФУ. Для этого установим соответствующее ФУ типа 2 для n-местной линейной функции f(n) =x1 Åx2 Å…Åxn (n = =2s, s = 1,2,…,). Для (2.3) введем две функции (формулы) fi (n/2)= f(n/2)(Xi), i=1, 2, соответственно с переменными из X1={x1,…,xn/2} и X2={ xn/2+1,…,xn}. Эти функции для начальных условий и далее допускают два варианта задания их формулами. Рассмотрим их.

5.1.1.Функции для начальных условий задаются дизъюнктивной нормальной формой ДНФ f (2) =g(2)(x1, x2) = ( `x1 x2 Ú x1`x2 ) и h (2)(t1, t2) = =(`t1×t2 Ú t1×`t2 ), что приводит к ФУ типа 2-1 в базисе G1 ,

. (5.2)

ФУ (5.2) последовательно применяется для n = 2, 4, 8, …, позволяя получить любую заявленную функцию f (n), n = 2s, s = 1,2,…, в G1. Если рассматривать левую часть (5.2) как формулу в G3, а с правой частью повторять эти действия (разбиение линейной функции на подфункции с одинаковым числом переменных и дальнейшее преобразование) необходимое число раз, то подтвердим также эквивалентность в базисе G1 È G3.

ФУ (5.2), позволяет выполнить представление “сверху” (“от функции”) функции f (n) из базиса G3 в базисе G1, формируя параллельную структуру и устанавливая рекуррентные соотношения между соответствующими показателями сложности. Этот подход реализует декомпозицию (получение рекуррентного соотношения) “сверху”, а вычисления происходят распараллелено - “от аргументов”.

Вначале используем рекуррентные соотношения для показателей сложности

LБ(f (n), G1 ) = 2×(LБ(, G1 )+LБ(, G1 )),

LF(f (n), G1 ) = 2×(LF(, G1 )+LF(, G1 ))+5,

LS(f (n), G1 )= LS(, G1 )+LS(, G1 )+5,

Dep F( f (n), G1 )= DepF(, G1)+ 3,

DepS( f (n), G1 )= DepS(, G1)+ 3, n ³2,

причем имеют место начальные условия

f (2) =g(2)(x1, x2)=( `x1×x2 Ú x1×`x2), h(2)(t1, t2)=( `t1×t2 Ú t1×`t2 ) , LБ(f (2), G1)=4,

LF(f (2), G1 )= LF(h (2), G1 )= 5,

LS(f (2), G1 )= LS(h (2), G1 )= 5

DepF(f (2), G1) = DepF(h (2), G1) = 3,

DepS(f (2), G1) = DepS(h (2), G1) = 3,

откуда выводим, доказывая индукцией по s,

LБ(f (n), G1 ) = 2×(LБ(, G1 )+LБ(, G1 )) =…=

=2s-1× (LБ(f (2), G1 ) +…+ LБ(f (2), G1 )) =2s-1× 2s-1× 4 = 4s = n2. (5.3)

LF( f (n), G1 ) = 2×(LF(, G1 )+LF(, G1 ))+5=

= 4×LF(, G1 ) +5=4×(4×LF(, G1 ) +5) +5=…=

= 4s-1×(LF (f (2), G1)+ 4s-2×5 +…+ 42×5+ 4×5 + 5 =

= 5×(4s-1 + 4s-2+ …+ 1) = 5× (n2 – 1) /3, n = 2s и s ³ 2, (5.4)

LS(f (n), G1 ) = LS(, G1) + LS(, G1)+5 = … =

= LS(f (2), G1 ) + … +LS(f (2), G1 ) + 5×(2s-2 + …+ 2 + 1) =

=5×2s-1+ 5×(2s-1 - 1) = 5×(2s - 1)= 5×(n - 1), (5.5)

DepF( f (n), G1)= DepF(, G1) + 3 =…= DepF(f (2), G1 ) + 3×(s - 1) =

= 3×s = 3× log2 2s =3×log2 n=3 élog2 nù, (5.6)

DepS( f (n), G1 )= DepS(, G1)+ 3 = … =3×s = 3×log2 n=3 élog2 nù. (5.7)

5.1.2. Преобразуем функции для начальных условий f (2) = g(2)(x1, x2)= = и h(2)(t1, t2) =, получая ФУ типа 2-2 в базисе G1, (правая часть есть ФВ-формула; выполнено преобразование ФУ (5.2))

. (5.8)

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

LБ(f (n), G1 ) = 2×(LБ(, G1 )+LБ(, G1 )) = n2. (5.9)

DepF( f (n), G1)= DepF(, G1) + 3 = 3 élog2 nù, (5.10)

DepS( f (n), G1 )= DepS(, G1)+ 3 = 3 élog2 nù. (5.11)

Для остальных показателей рекуррентные соотношения и начальные условия будут следующие:

LF(f (n), G1 ) = 2×(LF(, G1 )+LF(, G1 ))+4,

LS(f (n), G1 )= LS(, G1 )+LS(, G1 )+4,

LF(f (2), G1 )= LF(h (2), G1 )= 4,

LS(f (2), G1 )= LS(h (2), G1 )= 4,

откуда имеем, доказывая индукцией по s,

LF( f (n), G1 ) = 2×(LF(, G1 )+LF(, G1 ))+4=

= 4×LF(, G1 ) +4=4×(4×LF(, G1 ) +4) +4=…=

= 4s-1×(LF (f (2), G1)+ 4s-2×4 +…+ 42×4+ 4×4 + 4 =

= 4×(4s-1 + 4s-2+ …+ 1) = 4× (n2 – 1) /3, n = 2s и s ³ 2, (5.12)

LS(f (n), G1 ) = LS(, G1) + LS(, G1)+4 = … =

= LS(f (2), G1 ) + … +LS(f (2), G1 ) + 4×(2s-2 + …+ 2 + 1) =

=4×2s-1+ 4×(2s-1 - 1) = 4×(2s - 1)= 4×(n - 1). (5.13)

Для показателей (5.5), (5.7), (5.11) и (5.13) применялась схема с ветвлением, причем для одного ФЭ использовалось не более одного ветвления.

5.2. Обобщение на случай произвольного n (для случая разд. 5.1.2). Ситуация аналогичная разд.4.3. Если n ³ 2 и n ¹ 2s, s = 1,2,…, то, дописывая в формулу (5.1) необходимое, минимальное число слагаемых, равных 0, получаем соответственно N = LБ(f (n), G1) = 2s, s=élog2 nù , иначе (n=2s) N =n. Аналогично разд.3.2 на основе (5.9)-(5.13) выразим нижние и верхние оценки показателей сложности для данного случая

< LБ(f (n), G1 ) £, (5.14)

4×(– 1) /3 < LF( f (n), G1 ) £ 4×(– 1) /3, (5.15)

4×( - 1) < LS(f (n), G1 ) £ 4×( - 1), (5.16)

3 ( élog2 n ù - 1) < DepF( f (n), G1) £ 3 élog2 n ù, (5.17)

3 ( élog2 n ù - 1) < DepS( f (n), G1 ) £ 3 élog2 n ù. (5.18)

Оценки рассматриваемых показателей сложности для линейной фун-кции f (n) = x1 Å x2 Å … Å xn Å1 получаются из результатов для (4.9)-(4.18) заменой n на n +1.

6. Синтез схемы на основе ФУ. Рассмотрим применение ФУ типа 1 для синтеза схемы из ФЭ. Требуемый алгоритм будет подобен таким же алгоритмам для функций из класса n-местных дизъюнкций и n-местных линейных функций при представлении их соответственно в базисе G3 и G1 . Поэтому сформулируем его для класса n-местных линейных функций, имея в виду, что он допускает обобщение на разные классы функций и базисы, а также различные начальные условия. Исходные данные: n-местная линейная функция f(n) =x1 Åx2 Å…Åxn, n = 2,3,…, и базис G1 = { g&(2), gÚ(2), gØ(1) }. Дальше можно действовать по двум вариантам: в базисе G1 получить функции f (2) = g(2)(x1, x2) = (`x1x2Úx1`x2 ) и h(2)(t1, t2) =( `t1×t2 Ú t1×`t2 ) и строить соответствующие им схемы, руководствуясь ФУ (см. (2.2) и разд.2), или использовать ниже следующий алгоритм 1.

Напомним, что ФУ типа 1 для классов простых булевых функций дает последовательную структуру (характеризуемую максимальной глубиной в отличие от ФУ типа 2 с минимальной глубиной), определяемую от выхода. Конструировать схему будем от входов (от начальных условий) к выходу. Задействованные ФЭ выражаем следующим образом: сохраняем обозначение функции, местность не указываем, а в нижний индекс через запятую записываем порядковый номер секции (см. ниже) и номер ФЭ в ней. Для отличия ФЭ от реализуемой им функции при записи последняя выделяется курсивом.

Алгоритм 1.

Ш а г 1. Присвоить k = 2 (k - число переменных), p=1; выбрать переменные x1 и x2 и первые пять ФЭ (будем говорить, что они образуют первую секцию, p =1): два - gØ, два - g& и один - gÚ; нумеруем их в порядке выполнения операций: gØ1, gØ2, g&3, g&4, gÚ5; переменной x1 сопоставляем вход ФЭ gØ1 , выход которого ставим в соответствие первому входу ФЭ g&3, и первый вход ФЭ g&4 (ветвление входа); переменную x2 приписываем к второму входу ФЭ g&3 и входу ФЭ gØ2 , выход которого направлен к второму входу ФЭ g&4 ; выходам ФЭ g&3 и g&4 соответствуют входы ФЭ gÚ5, имеющего выход, реализующий функцию f (k)(x1, x2) (так его и будем называть); результаты фиксируем в табл. 1.

Ш а г 2. Если k = n, то перейти к шагу 4.

Ш а г 3. Вычислить k = k +1, p=p+1; выбрать k-ю переменную xk и p-е пять таких же ФЭ (p-я секция), перенумерованные аналогично шагу 1; выходу f(k-1)(x1, x2, …, xk-1) (предыдущей части схемы) сопоставляем вход ФЭ gØ1 , выход которого адресуем к первому входу ФЭ g&3, и первый вход ФЭ g&4 (ветвление выхода ФЭ); переменную xk приписываем к второму входу ФЭ g&3 и входу ФЭ gØ2 , выход которого направляем к второму входу ФЭ g&4 ; выходам ФЭ g&3 и g&4 сопоставляем соответствующие входы ФЭ gÚ5, выход которого реализует функцию f (k)(x1, x2, …, xk) (так его и будем называть); результаты фиксируем в табл. 1; перейти к шагу 2.

Ш а г 4. Распечатать табл. 1, представляющую табличное описание схемы (с ветвлением) с числом N=5p ФЭ, состоящим из 2p ФЭ g&, p ФЭ gÚ, 2p ФЭ gØ .

Ш а г 5. Конец.

Для данного алгоритма синтеза логической схемы число итераций составляет n–1, в каждой из которых действия однотипны. Заполнение табл. 1 учитывает ее синтаксические и семантические особенности.

Как следует из результатов разд.3-4, при декомпозиции булевых функций, применяя ФУ типа 2 (2.3), минимизируется сложность и глубина формулы и глубина схемы. Причем для каждого этапа соответствующего алгоритма рекомендуется следующее правило для получения представления булевой функции с минимизируемыми значениями глубины формулы или схемы: если n - четное, то n1 = n2, иначе n1 - n2 = 1. Это правило используется в алгоритме разд. 6.

П р и м е р 1. На основе алгоритма 1 выполнить синтез формулы F (схемы S из ФЭ), реализующей линейную функцию f (3)(x1,x2,x3)=x1Åx2Åx3 в базисе G1 ={ g&(2), gÚ(2), gØ(1) } (соответствующих ФЭ). Заметим, что достаточно сформировать требуемые базисные формулы (соответствующие ФЭ) и связи между ними, обеспечивающие заданное функционирование.

Применив алгоритм 1, из табл. 1 получаем: в классе схем с ветвлением необходимо N=5p ФЭ, из которых 2p ФЭ g&, p ФЭ gÚ, 2p ФЭ gØ, причем номер ФЭ N=(p-1)+i, i = 1, 2,…,5, p - номер секции, i - номер ФЭ в секции; k - индекс вводимой переменной; в классе формул f(3)(x1, x2, x3)=x1Å Åx2Å x3 = сложностью LБ(f (3), G1 )=10 или в классе ДНФ - f(3)= x1`x2`x3Ú `x1x2`x3 Ú Ú`x1`x2x3 Ú x1x2x3 сложностью LБ(f (3), G1 ) = nm = 12 .

Обобщая результаты примера, формулируем вывод: номер ФЭ N= =(p – 1) + i, i = 1, 2,…,5, p - номер секции, i - номер ФЭ в секции, т. е. в схеме между всеми ФЭ (функциями) и их номерами установлена биекция (для автоматизации синтеза схем); сложность LБ(f (n), G1 ) = N=5pmax.

7. Использование ФУ в интеллектуальной системе синтеза интегральных схем. Результаты, изложенные в статье и ранее [21, 24], применяются в основном на этапе логического синтеза дискретных вычислительных и управляющих устройств, а также следующим за ним этапе технического синтеза. Технический этап синтеза устройств может использовать логические (интегральные схемы), оптические элементы и другие, физическая реализация которых может быть различной, но именно на функциональном уровне для всех них можно и полезно учитывать многие особенности последующей реализации булевых функций, начиная с их показателей сложности.

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

Для логической модели представления знаний основное ФУ (2.1) принимает форму

├ (7.1)

где X1ÈX2 = X, X1ÇX2 = Æ, êX1 ê= n1 ³ 1, êX2 ê= n2 ³ 1 и n = n1 + n2. Для ФУ типа 1 она уточняется

g(2), h(2), f(2), …, f(n-1) ├ f(n) (7.2)

и дополняется следующими правилами:

Если (fi(k), Gj , w), то (F, LБ(ik), LF(ik), DepF(ik), LS(ik), DepS(ik)),

где w – конструктивный способ представления функции fi(k) в базисе Gj, устанавливающими, как для правильного условия обеспечивается правильное (минимальное или близкое к нему по одному или нескольким показателям, с учетом приоритетности) заключение и, следовательно, истинность импликации – правильность вывода.

В логике предикатов представление знаний может использовать следующую форму: утверждение i (для сокращения ниже записаны все показатели, а не по одному): при представлении булевой функции fi формулой (схемой) в базисе Gi (соответствующий базис Gi для схемы) способом w(i) показатель сложности LБ(i), LF(i), DepF(i) (LS(i), DepS(i)) имеют оптимальное (или близкое к нему по перечисленным выше показателям качества) значение.

В соответствии с этими особенностями и общими правилами формирования языка определяем формальный логический язык [1-4, 25-27].

П р и м е р 2. Создать образ базы знаний для логической модели (7.2) на основе результатов статьи (разд.2, 3.2 и 4.2), применимый для разработки интеллектуальной системы синтеза интегральных схем.

Результаты разд.2, 3.2 и 4.2 и ранее опубликованные в [ 21, 24] основаны на разбиении множества булевых функций на классы, для которых уточняются методы их декомпозиции в определенных базисах и выводятся оценки для показателей качества (сложности по числу базисных подформул, глубине суперпозиционной формулы и др., которые часто являются минимальными) этой декомпозиции. Поэтому естественным для разрабатываемой базы знаний является: сохранение получаемой структуры; отображение результатов, представленных в разд.2, 3.2 и 4.2, точнее их номеров, в табл. 2 в качестве подготовительного этапа к формированию базы знаний.

Другие выводы из [21, 24] аналогичным образом включаются в табл. 2, используемую для формирования базы знаний. В первом и втором столбцах таблицы 2 содержатся классы функций и базисы, которые соответствующим образом кодируются для базы знаний и алгоритма 2. При этом кодируются также сами функции f(n) и получаемые результаты – функционалы качества.

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

В системе синтеза каждой булевой функции сопоставляется упорядоченный набор конечной длины z (вектор атрибутов), указывающий на состояния программы синтеза и выполнение операций. Этот набор z играет важную роль в приведенном ниже алгоритме синтеза формул (схем). При этом исходными данными являются булева функция, базис и определенные ограничения, а выходными - суперпозиция базисных функций (суперпозиционная формула F в заданном базисе) для одного типа реализации или схема из ФЭ – для другого типа. Результаты представляются в виде соответствующих таблиц: для формулы таблица состоит из списка базисных подформул - функций со связями; для схемы таблица включает список базисных ФЭ или ЛЭ, содержащий правила соединения, характеризуемые минимальными значениями показателей качества, если нет других требований.

Алгоритм 2 (основной).

Ш а г 1. Выбрать булеву функцию из системы функций fi , i = 1, 2, … , на основе заполнения пользователем вектора атрибутов или извлечение из базы знаний ее вектора атрибутов (общение пользователя с базой знаний).

Ш а г 2. Аналогично шагу 1 задать базис Gj пользователем из базы знаний или вывод базиса Gj из fi в базе знаний.

Ш а г 3. Для пары (fi, Gj) установить метод, способ, вариант w представления булевой функции.

Ш а г 4. Выполнить виртуальный синтез (получить формулу или схему): вычислить значения показателей сложности представления функции (на основе функционалов) и запомнить их, т. е. найти упорядоченную пару ((fi(k), Gj , w); (F, LБ(ik), LF(ik), DepF(ik), LS(ik), DepS(ik))), понимая (ik) как (i, k).

Ш а г 5. Учитывая приоритеты, сравнить текущие значения показателей качества воображаемой декомпозиции с лучшим результатом, выбранным на предыдущих итерациях; проверить условия относительно показателей сложности представления функции и принять решение о продолжении работы алгоритма, т. е. для оптимального представления переход - к шагу 6, иначе – к шагу 2 (за новым базисом или способом проведения конструктивных операций).

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

Ш а г 7. Конец.

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

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

Таблица 1

Номер

Номер

Индекс теку-

ФЭ

В х о

д ы

Выход -

ФЭ,

N

секции,

p

щей переменной, k

1

2

реализуемая функция

1

1

2

gØ1,1

x1

-

gØ1,1= gØ1

2

gØ1,2

x2

-

gØ1,2

3

g&1,3

gØ1,1

x2

g&1,3

4

g&1,4

x1

gØ1,2

g&1,4

5

gÚ1,5

g&1,3

g&1,4

gÚ1,5= f(2)

6

2

3

gØ2,1

f(k-1)

-

gØ2,1= gØ6

7

gØ2,2

xk

-

gØ2,2

8

g&2,3

gØ2,1

xk

g&2,3

9

g&2,4

f(k-1)

gØ2,2

g&2,4

10

gÚ2,5

g&2,3

g&2,4

gÚ2,5= f(3)= f(k)

К статье “Математические модели для

интеллектуализации синтеза дискретных логических управляющих и

вычислительных устройств ”

Таблица 2

f (n)

g(2)

w

LБ

LF

DepF

LS

DepS

&

&

Последо-вательная

(3.2)

(3.3)

(3.4)

(3.5)

(3.6)

Параллель-ная

(3.8)

(3.9)

(3.10)

(3.11)

(3.12)

Ú

&,Å

»

(4.7)

(4.8)

(4.9)

(4.10)

(4.11)

Å

&,Ú,Ø

»

(5.14)

(5.15)

(5.16)

(5.17)

(5.18)

…

…

…

…

…

…

…

…

К статье “Математические модели для

интеллектуализации синтеза дискретных логических управляющих и

вычислительных устройств ”

СПИСОК ЛИТЕРАТУРЫ

1. , , Поспелов знаний о времени и пространстве в интеллектуальных системах. М.: Наука. 1989.

2. , Поспелов интеллект //Прикладные системы. М.: Знание, 1985.

3. Поспелов и продукционные модели // Представление знаний в человеко-машинных и робототехнических системах. Т. А. М.: ВИНИТИ, 1984.

4. , , и др. Достоверный и правдоподобный вывод в интеллектуальных системах / Под ред. , . М.: Физматлит, 2004.

5. Глушков цифровых автоматов. М. Физматгиз.1962.

6. Тыугу программирование. М.: Наука, 1984.

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

8. , , и др. Интеллектуальные системы автоматизированного проектирования БИС и СБИС / Под ред. . М.: Радио и связь, 1988.

9. Системное проектирование сверхбольших интегральных схем. Кн. 1 и 2. М.: Мир, 1985.

10. , , Немировский методы оптимизации устройств и алгоритмов АСУ / Под ред. , . М.: Радио и связь, 1982.

11. , , и др. Быстродействующие матричные БИС и СБИС. Теория и проектирование / Под общей ред. и М.: Радио и связь, 1989.

12. , , и др. Перспективы развития вычислительной техники. Справ. пособие / Под ред. . Кн.2. Интеллектуализация ЭВМ. М.: Высш. шк., 1989.

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

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

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

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

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

18. Успенский о вычислимых функциях. М.: Изд-во МГУ, 1960.

19. Мальцев и рекурсивные функции. М.: Наука, 1965.

20. Теория рекурсивных функций и эффективная вычислимость / Пер. с англ. М.: Мир, 1972.

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

22. Чебурахин автоматизации и оптимизации аппаратной реализации булевых функций // Информационные технологии. 1999. № 2.

23. Чебурахин декомпозиции булевых функций: алгоритмы, показатели качества, приложения // Изв. РАН. ТиСУ. 2003. №5.

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

25. , Драгалин в математическую логику. М.: Изд-во МГУ, 1982.

26. Новиков математической логики. М.: Наука, 1973.

27. Вагин модели. Т. А. М.: ВИНИТИ, 1984.