Синтез и анализ логической схемы при кубическом задании булевой функции (стр. 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=b1 b2 …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,

È ( a1 a2 …ai -1 ai ai +1 …an ),


Copyright © MirZnanii.com 2015-2018. All rigths reserved.