Логический синтез одноразрядного четверичного сумматора
Одноразрядный четверичный сумматор - это комбинационное устройство, имеющее 5 входов (2 разряда одного слагаемого, 2 разряда второго слагаемого и вход переноса) и 3 выхода. Принцип работы ОЧС представлен с помощью таблицы истинности (табл.4).
Разряды обоих слагаемых закодированы : 0 - 00; 1 - 11; 2 - 10; 3 - 01.
Если ОЧС синтезируется для схемы 1-го типа, то в таблице истинности необходимо выделить 16 безразличных наборов, так как со старших выходов ОЧУ не могут прийти коды “2” и “3”. Если ОЧС синтезируется для схемы 2-го типа, то безразличные наборы в таблице истинности отсутствуют.
Таблица истинности ОЧС. Таблица 4.
a1 | a2 | b1 | b2 | p | П | S1 | S2 | Пример операции в четверичной с/с |
0+0+0=00 | ||||||||
0+0+1=01 | ||||||||
х | х | х | 0+3+0=03 | |||||
х | х | х | 0+3+1=10 | |||||
х | х | х | 0+2+0=02 | |||||
х | х | х | 0+2+1=03 | |||||
0+1+0=01 | ||||||||
Окончание табл. 4 | ||||||||
a1 | a2 | b1 | b2 | p | П | S1 | S2 | Пример операции в четверичной с/с |
0+1+1=02 | ||||||||
3+0+0=03 | ||||||||
3+0+1=10 | ||||||||
х | х | х | 3+3+0=12 | |||||
х | х | х | 3+3+1=13 | |||||
х | х | х | 3+2+0=11 | |||||
х | х | х | 3+2+1=12 | |||||
3+1+0=10 | ||||||||
3+1+1=11 | ||||||||
2+0+0=02 | ||||||||
2+0+1=03 | ||||||||
х | х | х | 2+3+0=11 | |||||
х | х | х | 2+3+1=12 | |||||
х | х | х | 2+2+0=10 | |||||
х | х | х | 2+2+1=11 | |||||
2+1+0=03 | ||||||||
2+1+1=10 | ||||||||
1+0+0=01 | ||||||||
1+0+1=02 | ||||||||
х | х | х | 1+3+0=10 | |||||
х | х | х | 1+3+1=11 | |||||
х | х | х | 1+2+0=03 | |||||
х | х | х | 1+2+1=10 | |||||
1+1+0=02 | ||||||||
1+1+1=03 |
Определим множество единичных кубов:
L = {01001, 01110, 01111, 10111}
и множество безразличных кубов:
N ={00010, 00011, 00100, 00101,
01010, 01011, 01100, 01101,
10010, 10011, 10100, 10101,
11010, 11011, 11100, 11101}.
Сформируем множество С0 = L U N.
Первым этапом алгоритма Рота является нахождение множества простых импликант. Для реализации этого этапа будем использовать операцию умножения (*) над множествами С0, С1 и т.д., пока в результате операции будут образовываться новые кубы большей размерности. Первый шаг умножения (С0*С0) приведен в табл. 5. В результате этой операции сформируем новое множество кубов:
С1 = {0001x, 0010x, 0101x, 010x1, 0110x, 0111x, 011x0, 011x1, 01x01, 01x10, 01x11, 0x010, 0x011, 0x100, 0x101, 1001x, 1010x, 101x1, 10x11, 1101x, 1110x, 1x010, 1x011, 1x100, 1x101, x0010, x0011, x0100, x0101, x1010, x1011, x1100, x1101}.
Множество Z0 кубов, не участвовавших в образовании новых кубов, пустое.
В табл. 6 приведен следующий шаг поиска простых импликант с помощью операции С1*С1. В результате образовалось множество С2 кубов второй размерности:
С2 = {011xx, 01x1x, 01xx1, 0x01x, 0x10x, 1x01x, 1x10x, x001x, x010x, x101x, x110x, xx010, xx011, xx100, xx101}.
Множество Z1 кубов, не участвовавших в образовании новых кубов:
Z1 = {101х1, 10х11}.
В табл. 7 приведен следующий шаг поиска простых импликант – операция С2*С2. В результате образовалось множество С3 кубов третьей размерности:
С3 = {хх01х, хх10х}.
Множество Z2 кубов, не участвовавших в образовании новых кубов:
Z2 = {011хх, 01х1х, 01хх1}.
Поиск простых импликант (С0*С0). Таблица 5.
С0*С0 | ||||||||||||||||||||||||
----- | ||||||||||||||||||||||||
----- | ||||||||||||||||||||||||
0111x | ----- | |||||||||||||||||||||||
----- | ||||||||||||||||||||||||
----- | ||||||||||||||||||||||||
0001x | ----- | |||||||||||||||||||||||
----- | ||||||||||||||||||||||||
0010x | ----- | |||||||||||||||||||||||
01x10 | 0x010 | ----- | ||||||||||||||||||||||
010x1 | 01x11 | 0x011 | 0101x | ----- | ||||||||||||||||||||
011x0 | 0x100 | ----- | ||||||||||||||||||||||
01x01 | 011x1 | 0x101 | 0110x | ----- | ||||||||||||||||||||
x0010 | ----- | |||||||||||||||||||||||
10x11 | x0011 | 1001x | ----- | |||||||||||||||||||||
x0100 | ----- | |||||||||||||||||||||||
101x1 | x0101 | 1010x | ----- | |||||||||||||||||||||
x1010 | 1x010 | ----- | ||||||||||||||||||||||
x1011 | 1x011 | 1101x | ----- | |||||||||||||||||||||
x1100 | 1x100 | ----- | ||||||||||||||||||||||
x1101 | 1x101 | 1110x | ----- |
Поиск простых импликант (С1*С1). Таблица 6.
C1*C1 | 0001x | 0010x | 0101x | 010x1 | 0110x | 0111x | 011x0 | 011x1 | 01x01 | 01x10 | 01x11 | 0x010 | 0x011 | 0x100 | 0x101 | 1001x | 1010x | 101x1 | 10x11 | 1101x | 1110x | 1x010 | 1x011 | 1x100 | 1x101 | x0010 | x0011 | x0100 | x0101 | x1010 | x1011 | x1100 | |
0001x | ----- | ||||||||||||||||||||||||||||||||
0010x | ----- | ||||||||||||||||||||||||||||||||
0101x | 0x01x | ----- | |||||||||||||||||||||||||||||||
010x1 | ----- | ||||||||||||||||||||||||||||||||
0110x | 0x10x | ----- | |||||||||||||||||||||||||||||||
0111x | 01x1x | 011xx | ----- | ||||||||||||||||||||||||||||||
011x0 | ----- | ||||||||||||||||||||||||||||||||
011x1 | 01xx1 | 011xx | ----- | ||||||||||||||||||||||||||||||
01x01 | ----- | ||||||||||||||||||||||||||||||||
01x10 | ----- | ||||||||||||||||||||||||||||||||
01x11 | 01xx1 | 01x1x | ----- | ||||||||||||||||||||||||||||||
0x010 | ----- | ||||||||||||||||||||||||||||||||
0x011 | 0x01x | ----- | |||||||||||||||||||||||||||||||
0x100 | ----- | ||||||||||||||||||||||||||||||||
0x101 | 0x10x | ----- | |||||||||||||||||||||||||||||||
1001x | x001x | ----- | |||||||||||||||||||||||||||||||
1010x | x010x | ----- | |||||||||||||||||||||||||||||||
101x1 | ----- | ||||||||||||||||||||||||||||||||
10x11 | ----- | ||||||||||||||||||||||||||||||||
1101x | x101x | 1x01x | ----- | ||||||||||||||||||||||||||||||
1110x | x110x | 1x10x | ----- | ||||||||||||||||||||||||||||||
1x010 | xx010 | ----- | |||||||||||||||||||||||||||||||
1x011 | xx011 | 1x01x | ----- | ||||||||||||||||||||||||||||||
1x100 | xx100 | ----- | |||||||||||||||||||||||||||||||
1x101 | xx101 | 1x10x | ----- | ||||||||||||||||||||||||||||||
x0010 | ----- | ||||||||||||||||||||||||||||||||
x0011 | x001x | ----- | |||||||||||||||||||||||||||||||
x0100 | ----- | ||||||||||||||||||||||||||||||||
x0101 | x010x | ----- | |||||||||||||||||||||||||||||||
x1010 | xx010 | ----- | |||||||||||||||||||||||||||||||
x1011 | xx011 | x101x | ----- | ||||||||||||||||||||||||||||||
x1100 | xx100 | ----- | |||||||||||||||||||||||||||||||
x1101 | xx101 | x110x |
Поиск простых импликант (С2*С2). Таблица 7.
C2*C2 | 011xx | 01x1x | 01xx1 | 0x01x | 0x10x | 1x01x | 1x10x | x001x | x010x | x101x | x110x | xx010 | xx011 | xx100 | xx101 | |
011xx | ----- | |||||||||||||||
01x10 | ----- | |||||||||||||||
01xx1 | ----- | |||||||||||||||
0x01x | ----- | |||||||||||||||
0x10x | ----- | |||||||||||||||
1x01x | xx01x | ----- | ||||||||||||||
1x10x | xx10x | ----- | ||||||||||||||
x001x | ----- | |||||||||||||||
x010x | ----- | |||||||||||||||
x101x | xx01x | ----- | ||||||||||||||
x110x | xx10x | ----- | ||||||||||||||
xx010 | ----- | |||||||||||||||
xx011 | xx01x | ----- | ||||||||||||||
xx100 | ----- | |||||||||||||||
xx101 | xx10x | ----- |
Поиск простых импликант (С3*С3). Таблица 8.
C3*C3 | xx01x | xx10x | |
xx01x | ----- | ||
xx10x | ----- |
Результат С3*С3 приведен в табл. 8. Новых кубов (четвертой размерности) не образовалось. Получено множество Z3 = {хх01х, хх10х}.
На этом заканчивается этап поиска простых импликант, так как |С4|£1. Множество простых импликант
Z = Z0UZ1UZ2UZ3 = {101х1, 10х11, 011хх, 01х1х, 01хх1, хх01х, хх10х}.
Следующий этап – поиск L-экстремалей на множестве простых импликант. Для этого используется операция # (решетчатое вычитание). В табл. 9 из каждой простой импликанты поочередно вычитаются все остальные простые импликанты Z#(Z\z), результат операции (последняя строка таблицы) указывает на то, что L-экстремалями стали следующие простые импликанты:
E = 01xx1, xx01x, xx10x.
Необходимо проверить, нет ли среди них таких, которые стали L-экстремалями за счет безразличных кубов. Для этого в табл. 10 из кубов множества L вычитаются остатки простых импликант, полученные в табл. 9 (результат выполнения операции Z#(Z\z)). По результатам табл. 10 L-экстремалью, не связанной с безразличными наборами, стал куб 01хх1 (остаток от вычитания из него всех остальных простых импликант – 01001 – относится ко множеству единичных наборов L исходного задания функции). Этот куб обязательно должен войти в минимальное покрытие.
Поиск L-экстремалей. Таблица 9.
Z#(Z\z) | 101x1 | 10x11 | 011xx | 01x1x | 01xx1 | xx01x | xx10x | |||||||
101x1 | ----- | zz0zz | yyzz0 011xx | yy0z0 01x1x | yy0zz 01xx1 | 01yz0 xx01x | 01zz0 0x01x x110x xx100 | |||||||
10x11 | zzz0z | ----- | yyz00 011xx | yyzz0 01x1x | yyz0z 01xx1 | 01zz0 0x01x x101x xx010 | y1zy0 0yzy0 01zyy 0x10x x110x xx100 | |||||||
011xx | yyzzz | yyyzz | ----- | zz0zz 0101x | zz0zz 010x1 | z0yzz 1zyzz 10yzz 0x01x x101x xx010 | z0zzz 0010x | 1zzzz 1110x | 10zzz 1x100 | x0100 | ||||
01x1x | yyzyz | yyyzz | zzz0z 0110x | ----- | zzz0z | z0zzz 0001x | 1zzzz 1101x | 10zzz 1x010 x0010 | zyzyz 0010x | yzzyz 1110x | y0zyz 1x100 | 1yzyz x0100 | ||
01xx1 | yyzzz | yyzzz | zzzz0 | zzzz0 | ----- | zyzz0 0001x | yzzz0 1101x | y0zzy 1x010 | 1yzzy x0010 | zyzz0 0010x | yzzz0 1110x | y0zzy 1x100 | 1yzzy x0100 | |
xx01x | zzyyz | zzzzz | zzyyz | zzzzz | zzzyz | ----- | ----- | ----- | ----- | zzyyz 0010x | zzyyz 1110x | zzyyz 1x100 | zzyyz x0100 | |
xx10x | zzzzz | zzzzz | zzyzz | zzyyz 0001x | zzyyz 1101x | zzyyz 1x010 | zzyyz x0010 | ----- | ----- | ----- | ----- |
Проверка L-экстремалей. Таблица 10.
L ∩ Ê | |||||
0001x | |||||
1101x | |||||
1x010 | |||||
x0010 | |||||
0010x | |||||
1110x | |||||
1x100 | |||||
x0100 |
Далее необходимо проанализировать, какие из исходных единичных кубов (множество L) не покрыты найденной L-экстремалью. Этот анализ осуществляется с помощью табл. 11.
Поиск непокрытых исходных наборов. Таблица 11.
L # E | |||||
01xx1 | zzzzz | zzzzy | zzzzz | yyzzz |
Из табл. 11 видно, что L-экстремалью не покрыты два единичных куба (01110 и 10111 ). Чтобы их покрыть, воспользуемся множеством простых импликант, не являющихся L-экстремалями (табл.12).
Покрытие оставшихся кубов. Таблица 12.
L ∩ Ž | |||
101x1 | |||
10x11 | |||
011xx | |||
01x1x | |||
xx01x | |||
xx10x |
Из табл. 12 видно, что каждый из непокрытых единичных кубов может быть покрыт двумя равнозначными способами. Следовательно, существуют 4 тупиковые (минимальные) формы:
Функциональную схему ОЧС (рис. 7) построим по Fmin1 :
Дата добавления: 2022-02-05; просмотров: 278;