Синтез и анализ логической схемы при кубическом задании булевой функции (стр. 2 из 4)
где ai= 0 или 1, объединение берется по всем таким ai.
Процесс выделения L-экстремали является циклическим, на каждом цикле очередная простая импликанта вычитается из предыдущей разности. Процессы вычитания и пересечения для полученных выше простых импликант отражены в табл. 8.
Выделение L-экстремалей Таблица 8
| Z11X1XX11 | Z2XX1X1X0 | Z300X0XX0 | Z40X00101 | Z5000010X | Z6X0X00X0 | Z7XX1111X | Z8X010XX0 | Z9101XX1X | Z101X1X11X | ||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Z1 | 1X1XX11 | - | 0ZZZZ0YXX1X1X0 | YZ0ZZ0Y00X0XX0 | YZYZZYZ0X00101 | YZYZZY0000010X | 0Z0ZZ0YX0X00X0 | 0ZZZZZZ0X1111X | 0ZZZZ0YX010XX0 | ZZZZZZ0101XX10 | ZZZZZZ01X1X110 |
| Z2 | XX1X1X0 | ZZZZ0ZY1X1XX11 | - | ZZ0Z0ZZ0000XX000X00X0 | ZZYZZZY0X00101 | ZZYZZZ1000010X | ZZ0ZYZZX0X00X0 | ZZZZZZ10X11111 | ZZZZ0ZZX0100X0 | ZZZZ0ZZ101X010 | ZZZZZZZÆ |
| Z3 | 00X0XX0 | Y1Z1ZZY1X1XX11 | 11Z1ZZZ1X1X1X0X11X1X0XX111X0 | - | Z1ZZZZY0X00101 | ZZZZZZ10000101 | 1ZZZZZZ10X00X0 | Z1ZYZZY0X11111 | 1ZZZZZZ10100X0 | YZZ1ZZZ101X010 | Æ |
| Z4 | 0X00101 | YZY10YZ1X1XX11 | YZY1Z1Y1X1X1X01ZY1Z1YX11X1X01ZYYZ1YXX111X0 | ZZZZ01Y0000XX0ZZ1ZY1Y00X00X0 | - | ZZZZZZZÆ | YZ1ZY1Y10X00X0 | ZZYYZYZ0X11111 | YZYZY1Y10100X0 | YZY1YYY101X010 | Æ |
| Z5 | 000010X | Y1Y10YZ1X1XX11 | Y1Y1Z1Z1X1X1X01YY1Z1ZX11X1X011YYZ1ZXX111X0 | ZZZZ01Z00000X00000X10ZZ1ZY1Z00X00X0 | Z1ZZZZZ0100101 | - | YZ1ZY1Z10X00X0 | Z1YYZYZ0X11111 | YZYZY0Z10100X0 | YZY1YYY101X010 | Æ |
| Z6 | X0X00X0 | Z1Z11ZY1X1XX11 | Z1Z1YZZ1X1X1X0ZYZ1YZZX11X1X0Z1ZYYZZXX111X0 | ZZZZZZZÆZZZZ1ZZ0000110ZZZZZZZÆ | ZYZZYZY0100101 | Æ | - | Z1ZYYZY0X11111 | ZZZZZZZÆ | ZZZ1ZZZ1011010 | Æ |
| Z7 | XX1111X | ZZZ00ZZ1X10X111X1X011 | ZZZ0Z0Z1X101X01X1X100ZZZ0Z0ZX1101X0X11X100 | ZZYYZZZ0000110 | ZZYYZYZ0100101 | Æ | ZZ0YY0Z10X00X0 | - | Æ | ZZZZYZZ1011010 | Æ |
| Z7 | ZZZZZ0ZXX111001 | ||||||||||
| Z8 | X010XX0 | Z1ZZZZY1X10X11Z1Z1ZZY1Z1Z011 | Z1ZZZZZ11 01X0Z1Z1ZZZ111X1001X11100ZYZZZZZX1101X0Z1ZYZZZXX11100 | ZZYZZZZ0000110 | ZYYZZZY0100101 | Æ | ZZ0ZZZZ10000X0 | Z1ZYZZY0X11111 | - | ZZZYZZZ1011010 | Æ |
| Z9 | 101XX1X | Z1ZZZZZ1110X11Z1ZZZZZ111X011 | ZYZZZ0Z11101X0ZYZZZYZ111X100Z1ZZZYZ1X111000YZZZ0ZX1101X00YZZZYZX11X10001ZZZYZXX11100 | YZYZZZZ0000110 | YYYZZYZ0100101 | Æ | ZZYZZ0Z10000X0 | Y1ZZZZZ0X11111 | Æ | - | Æ |
| Z10 | 1X1X11X | ZZZZ0ZZ1110011111X011 | ZZZZZ0Z1110100ZZZZZYZ111X100ZZZZZYZ1X111000ZZZZ0Z01101X0X1101000ZZZZY1X11X1000ZZZZYZXX11100 | 0000110 | 0100101 | Æ | 10000X0 | 0X11111 | Æ | ZZZZYZZ1011010 | - |
| ¹Æ | ¹Æ | ¹Æ | ¹Æ | Æ | ¹Æ | ¹Æ | Æ | ¹Æ | Æ |
Полученное минимальное покрытие:
1X1XX11
XX1X1X0
00X0XX0
0X00101
X0X00X0
XX1111X
101XX1X
Cтоимость полученного покрытия равна 36 ( стоимость исходного покрытия равна 53 ).
2. ПОСТРОЕНИЕ ФАКТОРИЗОВАННОГО ПОКРЫТИЯ
Покрытие, полученное на основе простых импликант и выделения из них L-экстремалей, принято называть минимальным. Однако практика показывает, что дополнительная минимизация возможна при помощи факторизации. Таким образом, минимальным следует считать факторизованное покрытие, а не множество L-экстремалей.
Факторизация покрытия основана на операции m-произведения, которая предназначена для выделения общей части двух кубов. Эта операция является поразрядной:
0 при ai= bi= 0, i = 1,n;aimbi= 1 при ai= bi= 1, i = 1,n;
m во всех остальных случаях.
Символ m указывает координату исходных кубов, которая различна в них, либо есть Х.
Куб, в котором хотя бы одна координата является m, называется m-кубом и обозначается через еm. Такой куб может участвовать в m-произведении, тогда при умножении на координату m должна получаться координата m.
Стоимость для m-куба определяется путем подсчета числа координат со значениями 0 и 1. Куб с наибольшей стоимостью считается максимальным. Если стоимость равна 0, то m-куб считается пустым, он равен Æ. Покрытие с учетом m-куба записывается в несколько измененном виде: под m-кубом фиксируются соответствующие ему кубы с сохранением тех координат, которые расположены под символами m.
Алгоритм факторизации покрытия является циклическим. Количество циклов равно числу уровней разложения покрытия ( числу m-кубов ). В разложенном по многим уровням покрытии выделяются на i-м цикле m-куб еmi, Mi ( множество кубов с прочерками, соответствующее еmi), Ci (множество кубов, которые будут рассматриваться на ( i+1)-м цикле).
Алгоритм факторизации можно сформулировать следующим образом:
1. Вычисляются m-произведения всех пар из Сi-1. В первом цикле С0 = Е. Во втором цикле дело надо иметь с С1, в третьем – с С2 и т.д.
2. Выбирается m-куб с наибольшей стоимостью еmi. Если несколько кубов имеют одинаковую стоимость, то выбирается первый.
3. Покрытие оформляется разложенным на две части: нижнюю часть Мi и верхнюю часть Сi. Ci содержит оставшиеся от Сi-1 кубы после удаления из него кубов Мi и добавленный куб еmi. Видимо,
Ci = ( Ci-1 – Mi ) È emi.
4. Если Сi состоит из одного куба или получаются пустые m-кубы, процесс факторизации следует закончить, в противном случае перейти к пункту 1.
Процесс факторизации по данному алгоритму удобно отражать в таблицах. Первый цикл представлен в табл. 9.
Первый цикл факторизации Таблица 9
| e11X1XX11 | e2XX1X1X0 | e300X0XX0 | e40X00101 | e5X0X00X0 | e6XX1111X | ||
| e1 | 1X1XX11 | - | |||||
| e2 | XX1X1X0 | mm1mmmm | - | ||||
| e3 | 00X0XX0 | Æ | mmmmmm0 | - | |||
| e4 | 0X00101 | mmmmmm1 | mmmm1mm | 0mm0mmm | - | ||
| e5 | X0X00X0 | Æ | mmmmmm1 | m0m0mm0 | mmm0mmm | - | |
| e6 | XX1111X | mm1mm1m | mm1m1mm | Æ | mmmm1mm | Æ | - |
| e7 | 101XX1X | 1m1mm1m | mm1mmmm | m0mmmmm | Æ | m0mmmmm | mm1mm1m |
Из этой таблицы видно, что еm1 = 1m1mm1m.. Покрытие после первого цикла выглядит следующим образом:
Так как С1 содержит больше одного куба, осуществляется переход ко второму циклу ( табл. 10 ).
Второй цикл факторизации Таблица 10
| е2XX1X1X0 | е300X0XX0 | е40X00101 | е5X0X00X0 | е6XX1111X | ||
| е2 | XX1X1X0 | - | ||||
| е3 | 00X0XX0 | mmmmmm0 | - | |||
| е4 | 0X00101 | mmmm1mm | 0mm0mmm | - | ||
| е5 | X0X00X0 | mmmmmm0 | m0m0mm0 | mmm0mmm | - | |
| е6 | XX1111X | mm1m1mm | Æ | mmmm1mm | Æ | - |
| еm1 | 1m1mm1m | mm1mmmm | Æ | Æ | Æ | mm1mm1m |
Очевидно, что еm2 = m0m0mm0.
Покрытие после второго цикла факторизации выглядит следующим образом:
Так как С2 содержит больше одного куба, осуществляется переход к третьему циклу ( табл. 11 ).
Третий цикл факторизации Таблица 11
| e2XX1X1X0 | e40X00101 | e6XX1111X | ||
| e2 | XX1X1X0 | - | ||
| e4 | 0X00101 | mmmm1mm | - | |
| e6 | XX1111X | mm1m1mm | mmmm1mm | - |
| em2 | m0m0mm0 | mmmmmm0 | mmm0mmm | Æ |
Из таблицы 11 видно, что еm3 = mm1m1mm.
Покрытие после третьего цикла выглядит так:
Так как С3 содержит больше одного куба переходим к четвертому циклу (табл. 12).
Таблица 12
Четвертый цикл факторизации
| e40X00101 | ||
| е4 | 0X00101 | - |
| еm3 | mm1m1mm | mmmm1mm |
Ясно, что еm4 = mmmm1mm.
Факторизованное покрытие выглядит следующим образом:
Чтобы определить стоимость факторизованного покрытия, нужен соответствующий алгоритм. Его сущность можно изложить следующим образом:
1. определить стоимость рассматриваемого куба покрытия;
2. если куб является маскирующим (m-куб), то добавить к стоимости 2;
3. если куб является обычным, то при Si > 1 добавить к стоимости 1, в противном случае ( Si = 1 ) добавлять 1 не нужно;
4. полученные стоимости кубов с добавлениями сложить.
В полученном выше факторизованном покрытии 11 кубов, его стоимость составляет 30. До факторизации стоимость покрытия составляла 36.
3. СОСТАВЛЕНИЕ ЛОГИЧЕСКОЙ СХЕМЫ НА ОСНОВЕ ДАННОГО БАЗИСА ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ
По любому кубическому покрытию можно построить логическую схему. По факторизованному покрытию схема строится следующим образом. Обычные кубы отражаются на схеме как элементы & с числом входов, равным стоимости куба. Прочеркнутые координаты на вход этих элементов не подаются. Они учитываются в маскирующих кубах в качестве общих сомножителей. Выходные сигналы обычных кубов, расположенных под рассматриваемым m-кубом, суммируются, затем логическая сумма этих кубов подается на вход маскирующего куба, который отображается на схеме как элемент &. Логическая схема в булевом базисе, построенная по факторизованному покрытию, показана на рис.1.
Стоимость кубов М1 и М2,а также куба ХХ-Х1Х-, входящего в М3, равна 1. Поэтому соответствующие им переменные подаются непосредственно на входы элементов ИЛИ (12, 11 и 10 соответственно). Умножение на координаты куба еm1 производится в элементе 15, на координаты куба еm2 – в элементе 14, на координаты куба еm3 – в элементе 13. Кубы еm3 и еm4 имеют общую пятую координату. Поэтому выходной сигнал элемента 13, соответствующего еm3, логически суммируется с выходным сигналом элемента 8, а затем логическая сумма поступает на вход элемента 16, где происходит умножение на координаты куба еm4.