Курсовая работа: Синтез и анализ логической схемы при кубическом задании булевой функции
Таблица 2
|
ai * bi | ai | |||
| 0 | 1 | X | ||
|
bi | 0 | 0 | Y | 0 |
| 1 | Y | 1 | 1 | |
| X | 0 | 1 | X | |
Если значение Y получается только в одной координате, то произведение кубов a и b дает так называемый вновь образованный куб, в котором величина Y заменяется на X. Если же имеется более одной координаты Y, то звездчатое произведение дает 0.
Процесс нахождения множества простых импликант является циклическим. В каждом цикле вначале удаляются те кубы исходного покрытия, которые являются гранями других кубов этого покрытия. Далее удаляются кубы исходного покрытия, являющиеся гранями кубов покрытия. Должны быть удалены полученные при *-произведении кубы, являющиеся гранями кубов покрытия. И наконец, удаляются полученные кубы с размерностью, на единицу меньшей номера цикла. Оставшиеся в таблице кубы передаются на следующий цикл *-произведения. Циклы выполняются до тех пор, пока перестанут появляться вновь образованные кубы. Процесс нахождения множества простых импликант для 35-го варианта приведен в табл. 3,4,5,6. Куб «с» не используется при нахождении данного множества, т.к. он входит в куб «b».
1 цикл нахождения множества простых импликант Таблица 3
| 1011X10 | 1X1XX11 | XX1X1X0 | 0X11111 | 00X0XX0 | 0X00101 | |
| 1011X10 | - | |||||
| 1X1XX11 | 1011X1X | - | ||||
| XX1X1X0 | 1011110 | 1X1X11X | - | |||
| 0X11111 | Æ | XX11111 | 0X1111X | - | ||
| 00X0XX0 | Æ | Æ | 00101X0 | Æ | - | |
| 0X00101 | Æ | Æ | Æ | Æ | 000010X | - |
| 10X00X0 | 101X010 | 101001X | 1010XX0 | Æ | X0X00X0 | Æ |
2 цикл нахождения множества простых импликант Таблица 4
| 1Х1ХX11 | XX1X1X0 | 00X0XX0 | 0X00101 | 1011X1X | 101X010 | 1X1X11X | XX11111 | 101001X | 0X1111X | 1010XX0 | 000010X | |
| 1X1XX11 | - | |||||||||||
| XX1X1X0 | - | |||||||||||
| 00X0XX0 | - | |||||||||||
| 0X00101 | - | |||||||||||
| 1011X1X | 1011X11 | 101111X | Æ | Æ | - | |||||||
| 101X010 | 101X01X | 101XX10 | Y010010 | Æ | 1011010 | - | ||||||
| 1X1X11X | 1X1X111 | 1X1X110 | Y010110 | Æ | 101111X | 101XY10 | - | |||||
| XX11111 | 1X11111 | XX1111X | Æ | Æ | 1011111 | Æ | 1X11111 | - | ||||
| 101001X | 1010011 | 1010Y10 | Y010010 | Æ | 101X01X | 1010010 | 1010Y1X | Æ | - | |||
| 0X1111X | XX11111 | 0X11110 | 001Y110 | Æ | X01111X | Æ | YX1111X | 0X11111 | Æ | - | ||
| 1010XX0 | 1010X1X | 10101X0 | X010XX0 | Æ | 101XX10 | 1010010 | 1010110 | Æ | 1010010 | Æ | - | |
| 000010X | Æ | 00Y0100 | 0000100 | 0000101 | Æ | Æ | Æ | Æ | Æ | Æ | Æ | - |
| X0X00X0 | 101001X | X010XX0 | 00X00X0 | 0000Y01 | 101Y010 | 1010010 | 1010Y10 | Æ | 1010010 | Æ | 10100X0 | 0000Y00 |
3 цикл нахождения множества простых импликант Таблица 5
| 1X1XX11 | XX1X1X0 | 00X0XX0 | 0X00101 | 1011X1X | 1X1X11X | 000010X | X0X00X0 | 101X01X | 1010X1X | 101XX10 | XX1111X | |
| 1X1XX11 | - | |||||||||||
| XX1X1X0 | - | |||||||||||
| 00X0XX0 | - | |||||||||||
| 0X00101 | - | |||||||||||
| 1011X1X | - | |||||||||||
| 1X1X11X | - | |||||||||||
| 000010X | - | |||||||||||
| X0X00X0 | - | |||||||||||
| 101X01X | 101X011 | 101XX10 | X010010 | Æ | 101101X | 101XX1X | Æ | 1010010 | - | |||
| 1010X1X | 1010X11 | 1010110 | X010X10 | Æ | 101XX1X | 101011X | Æ | 1010010 | 101001X | - | ||
| 101XX10 | 101XX1X | 101X110 | X010X10 | Æ | 1011X10 | 101X110 | Æ | 1010010 | 101X010 | 1010X10 | - | |
| XX1111X | 1011111 | XX11110 | 001X110 | Æ | 101111X | 1X1111X | Æ | Æ | 1011X1X | 101X11X | 1011110 | - |
| X010XX0 | 1010X1X | X0101X0 | 0010XX0 | Æ | 101XX10 | 1010110 | 00X0100 | X0100X0 | 1010010 | 1010X10 | 1010X10 | X01X110 |
4 цикл нахождения множества простых импликант Таблица 6
| 1X1XX11 | XX1X1X0 | 00X0XX0 | 0X00101 | 000010X | X0X00X0 | XX1111X | X010XX0 | 101XX1X | |
| 1X1XX11 | - | ||||||||
| XX1X1X0 | - | ||||||||
| 00X0XX0 | - | ||||||||
| 0X00101 | - | ||||||||
| 000010X | - | ||||||||
| X0X00X0 | - | ||||||||
| XX1111X | - | ||||||||
| X010XX0 | - | ||||||||
| 101XX1X | 101XX11 | 101X110 | X010X10 | Æ | Æ | 1010010 | 101111X | 1010X10 | - |
| 1X1X11X | 1X1X111 | 1X1X110 | X010110 | Æ | Æ | 1010X10 | 1X1111X | 1010110 | 101X11X |
В таблицах 3, 4, 5 и 6 опущены те *-произведения, которые были рассмотрены раньше. Множество простых импликант Z выглядит следующим образом:
Z={ 1X1XX11, XX1X1X0, 00X0XX0, 0X00101, 000010X, X0X00X0, XX1111X, X010XX0, 101XX1X,1X1X11X }.
Стоимость данного покрытия составляет 53, что на 5 больше стоимости исходного покрытия.
После нахождения множества Z в нем необходимо выделить такое подмножество, которое покрывало бы все вершины из комплекса L и имело бы минимальную стоимость по Квайну. В основе лежит понятие L-экстремали, то есть куба Zi , содержащего в себе одну или несколько вершин из комплекса L (L=C), которой нет ни в одной другой простой импликанте из множества Z.
Куб Zi является L-экстремалью, если для него выполняется следующее соотношение:
[ Zi # ( Z - Zi )] ÇL¹Æ,
где # - знак операции вычитания кубов.
Операция вычитания, например, из куба а куба b служит для удаления их общей части, т.е. их пересечения, из куба а. Эта операция определяется следующим образом:
Координатное вычитание кубов ( ai # bi ) Таблица 7
| ai # bi | ai | |||
| 0 | 1 | X | ||
|
bi | 0 | Z | Y | 1 |
| 1 | Y | Z | 0 | |
| X | Z | Z | Z | |
Операция вычитания из куба а куба b определяется следующим образом:
a, при наличии Y,
a # b = Æ, если ai # bi = Z,
È ( a1 a2 …ai -1 ai ai +1 …an ),
где ai = 0 или 1, объединение берется по всем таким ai .
Процесс выделения L-экстремали является циклическим, на каждом цикле очередная простая импликанта вычитается из предыдущей разности. Процессы вычитания и пересечения для полученных выше простых импликант отражены в табл. 8.
Выделение L-экстремалей Таблица 8
|
Z1 1X1XX11 |
Z2 XX1X1X0 |
Z3 00X0XX0 |
К-во Просмотров: 458
Бесплатно скачать Курсовая работа: Синтез и анализ логической схемы при кубическом задании булевой функции
|