Синтез и анализ логической схемы при кубическом задании булевой функции (стр. 1 из 4)
Министерство образования Российской Федерации
Томский политехнический университет
Факультет автоматики и вычислительной техники
Кафедра вычислительной
техники
Курсовая работа
по дисциплине “Теория автоматов”
на тему: «Синтез и анализ логической схемы при кубическом задании булевой функции»
Томск 2009
СОДЕРЖАНИЕ
Введение
1. Нахождение минимального покрытия
2. Построение факторизованного покрытия
3. Составление логической схемы на основе данного базиса логических элементов
4. Нахождение по пи-алгоритму Рота единичного покрытия
5. Синтез контролирующего теста. Контроль схемы тестом
Заключение
Литература
ВВЕДЕНИЕ
Аппарат алгебры логики широко применяется в теории ЦВМ, в частности для решения задач анализа и синтеза схем. При решении задачи синтеза исходное логическое выражение, описывающее некоторую логическую функцию, преобразуется и упрощается так, чтобы каждый член полученного эквивалентного логического выражения мог быть представлен простой схемой. Таким образом, при синтезе вычислительных и управляющих схем составляется математическое описание задачи в виде формул алгебры логики. Затем производится минимизация исходной формулы и из числа эквивалентных логических схем выбирается та, которая допускает наиболее простую реализацию.
В данной курсовой работе стоит задача синтеза схемы, реализующей функцию, заданную кубическим комплексом к(f). В табл. 1 приведено исходное покрытие из 8 кубов. Логическую схему следует построить в универсальном базисе элементов ИЛИ-НЕ, который характеризуется коэффициентом объединения по входу к(вх)=4 и коэффициентом разветвления по выходу к(р)=2. Стоимость покрытия равна 48.
Таблица 1
| Обозначение куба | Покрытие | Размерность куба |
| a | 1011X10 | 6 |
| b | 1X1XX11 | 4 |
| c | 1011X11 | 6 |
| d | XX1X1X0 | 3 |
| e | 0X11111 | 6 |
| f | 00X0XX0 | 4 |
| g | 0X00101 | 6 |
| h | 10X00X0 | 5 |
Порядок выполнения работы можно определить следующим образом:
1). Нахождение минимального покрытия;
2). Построение факторизованного покрытия;
3). Составление логической схемы на основе данного базиса логических элементов;
4). Нахождение по пи-алгоритму Рота единичного покрытия;
5). Построение контролирующего теста;
6). Проверка логической схемы контролирующим тестом.
1.НАХОЖДЕНИЕ МИНИМАЛЬНОГО ПОКРЫТИЯ
В первую очередь необходимо найти минимальное в смысле Кванта покрытие. Минимальное покрытие булевой функции ищется в два этапа:
1).получение минимального множества Z простых импликант;
2).выделение L-экстремалей на множестве Z.
Для выполнения этих этапов используются операции *-произведения, #-вычитания кубов.
При выполнении операции *-произведения одного куба на другой получается новый куб, противоположные грани которого лежат в исходных кубах. Этот новый куб может стать простой импликантой исходного покрытия. Надо иметь в виду, что куб является простой импликантой исходного покрытия, если он не составляет грань никакого другого комплекса К или того куба, который получился при произведении в процессе нахождения простых импликант. Это означает, что простые импликанты при *-произведении не дают новых кубов, не входящих в предыдущие кубы.
При нахождении простых импликант выполняются все попарные произведения с учетом того, что произведение куба самого на себя приводит к кубу, участвующему в произведении; что произведение первого куба на второй равно произведению второго куба на первый.
Операция *-произведения двух кубов а=а1а2…аi…an и b=b1b2…bi…bn определяется на основе табл. 2.
Таблица 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,
È ( a1a2…ai-1aiai+1…an),