Синтез схем в монофункциональном базисе.

При синтезе схем в базисе p-И-НЕ, где p – число входов элемента, используется следующий алгоритм.

Исходная функция представляется в дизъюнктивной нормальной форме, т.е. в виде К1Ú К2 Ú… ÚКr, затем над ней проводится операция двойного отрицания, одно из которых опускается до конъюнкций, т.е.

функция будет представлена через функции базиса. 

Если r£p и число букв в каждой из конъюнкций не больше p, то задача решена. Схема будет состоять из двух уровней. На первом из них реализуются конъюнкции, на втором происходит их объединение. Задача усложняется, если на каком-то уровне у элемента не хватает для реализации входов. В этом случае задача состоит в том, чтобы разбить исходную запись функции на фрагменты и реализовать каждый из них отдельно, объединяя затем, используя правило де Моргана.

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

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

Пример. Реализуем в базисе 3 -И-НЕ функцию f=<01101000>

Запишем её в СДНФ: f =`a×`b ×c Ú`a ×b ×`c Ú a ×`b×`c

Функция не минимизируется, полученная нормальная форма является и минимальной.

Схема будет иметь вид как на рис. 3.9.

Если возникает необходимость реализовать эту функцию в базисе 2-И-НЕ, то формулу преобразуем так:

f =`a×`b×cÚ`a×b×`cÚa×`b×`c= `a×(`b×cÚ×b×`c)Úa×(`b×`c) =
=`a / (`b × c Ú b`c) / (a / (`b ×`c )).

(`bc Ú b`c ) = (`b / c) / (b /`c ), ` b`c =`b /`c .

Здесь символом / обозначена функция элемента базиса.

Инверсия реализуется на одном элементе базиса, если у него на оба входа подать одну и ту же переменную, т.е. (x/x)=`x.

При реализации на элементе p-ИЛИ-НЕ используют представление функции в конъюнктивной нормальной форме.
Всё остальное то же, что и при реализации в базисе p-И-НЕ.

Пример. Реализуем ту же функцию в базисе 3-ИЛИ-НЕ.

f=(aÚbÚc) × (aÚ`bÚ`c) × (`aÚbÚ`c) × (`aÚ`bÚc) × (`aÚ`bÚ`c)=
= (aÚbÚc) × (`bÚ`c)× (`a Ú`c) × (`aÚ`b).

Решение имеет вид как на рис.3.10.

 

Упражнения

 

Функциональная полнота

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

а) f = (a®`bc) Å`ca ;

б) f = (ab®cd)v(aÅb)`d ;

в) f = a b`c v`a b`c v`a`bc va`b`c ;

г) f = a b`c v`a b c v a`bc vabc ;

д) f = (aÅb)cv (avbv`c) ® abc;

е) f = (cÅb)v ac(`b®d)vd&(⌐(c®a));

ж) f = ((a®b) Åac)&(cÅb). `

Синтез схем

1. Построить схему для заданной пары функций методом факторизации в классическом базисе {2И, 2ИЛИ, НЕ} (в скобках – число элементов в схеме).

а) {f1 =`a`b`c v `a b c v ac, f2= `a`b`c v a` b c } (не более 7 эл-тов);

б) {f1 =`a`c v `b`с v d (b v c),
 f2 = a b`d v a`d v c`d v a`b d } (не более 8 эл-тов);

в) {f1= a`b v`a b с v a`b c),
 f2 = `a v a`b v c`d v a`b d } (не более 4 эл-тов);

г) {f1= a`b v`a b с v a`b c,
 f2 = a ®(a`b) v a`b c } (не более 4 эл-тов);

д) {f1= a`b v`b c v a`b c,
 f2 = a `b v `a b c v a b`c } (не более 5 эл-тов);

е) {f1 = a`b v`a b c v `a b`c, f2= a b c } (не более 5 эл-тов);

ж) {f1 = Ø(a`b v`a b c v `a b`c),
f2 = a v `a b v `b c } (не более 5 эл-тов).

 

2. Построить схему для заданной функции методом декомпозиции в классическом базисе {2И, 2ИЛИ, НЕ}, используя разложение К. Шеннона

а) {f = (01101001000111101010010100011110)};

б) {f = (00111101110000100101000110101110)};

в) {f = (00101101000111101010010100011110)};

г) {f = (10011101011000100101000110101110)};

д) {f = (00011101111000100101000110101110)};

е) {f = (11011101001000100101000110101110)};

ж) {f = (11010010001011010101101010100101)};

з) {f = 10100101000111101010010100011110) }).

 

3. Построить схему для заданной функции методом декомпозиции в монофункциональном базисе {3И-НЕ}

a) {f: T1 = (001, 010, 100)};

b) {f: T1 = (001, 010, 100, 111)};

c) {f: T1 = (000, 011, 100, 110)};

d) {f: T1 = (000, 011, 100)};

e) {f: T1 = (010, 100, 101)};

f) {f: T1 = (000, 110, 101)};

g) {f: T1 = (000, 011, 101)}.  

 

4. Построить методом факторизации в классическом базисе {2И, 2ИЛИ, НЕ} плоскую схему с внешним доступом для заданной пары функций

а) {f1 = a b c v `a` b c, f2= `a b`c v `a b c } (не более 6 эл-тов);

б) {f1 =`a v`b a, f2= (`a ®b)`c v c } (не более 6 эл-тов);

в) {f1 = (b ® a)`d v d, f2= (a ®b)`c v c} (не более 6 эл-тов);

г) {f1= a b`c v a`b`c v a b c, f2= a`b`c v a`c v b`c} (не более 7 эл-тов);

д) {f1 = b`c v a`b v a c, f2= b`c v a`b } (не более 5 эл-тов);

е) {f1 = `a`b v a c, f2= Ø (b a v `b) } (не более 7 эл-тов).

 

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: