Синтез схемы, реализующей функцию, заданную кубическим комплексом в универсальном базисе логических элементов ИЛИ-НЕ. Нахождение минимального и построение факторизованного покрытий. Составление логической схемы и ее проверка контролирующим тестом.
Краткое сожержание материала:

Размещено на

19

Размещено на

Министерство образования Российской Федерации

Томский политехнический университет

Факультет автоматики и вычислительной техники

Кафедра вычислительной

техники

Курсовая работа

по дисциплине “Теория автоматов”

на тему: «Синтез и анализ логической схемы при кубическом задании булевой функции»

Томск 2009

СОДЕРЖАНИЕ

Введение

Нахождение минимального покрытия

Построение факторизованного покрытия

Составление логической схемы на основе данного базиса логических элементов

Нахождение по пи-алгоритму Рота единичного покрытия

Синтез контролирующего теста. Контроль схемы тестом

Заключение

Литература

ВВЕДЕНИЕ

Аппарат алгебры логики широко применяется в теории ЦВМ, в частности для решения задач анализа и синтеза схем. При решении задачи синтеза исходное логическое выражение, описывающее некоторую логическую функцию, преобразуется и упрощается так, чтобы каждый член полученного эквивалентного логического выражения мог быть представлен простой схемой. Таким образом, при синтезе вычислительных и управляющих схем составляется математическое описание задачи в виде формул алгебры логики. Затем производится минимизация исходной формулы и из числа эквивалентных логических схем выбирается та, которая допускает наиболее простую реализацию.

В данной курсовой работе стоит задача синтеза схемы, реализующей функцию, заданную кубическим комплексом к(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.

Для выполнения этих этапов используются операции *-произведения, #-вычитания кубов.

При выполнении операции *-произведения одного куба на другой получается новый куб, противоположные грани которого лежат в исходных кубах. Этот новый куб может стать простой импликантой исходного покрытия. Надо иметь в виду, что куб является простой импликантой исходного покрытия, если он не составляет грань никакого другого комплекса К или того куба, который получился при произведении в процессе нахождения простых импликант. Это означает, что простые импликанты при *-произведении не дают новых кубов, не входящих в предыдущие кубы.

При нахождении простых импликант выполняются все попарные произведения с учетом того, что произведение куба самого на себя приводит к кубу, участвующему в произведении; что произведение первого куба на второй равно произведению второго куба на первый.

Операция *-произведения двух кубов а=а₁а₂…а_i…a_n и b=b₁b₂…b_i…b_n определяется на основе табл. 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 Другие файлы: Исследование и логическое проектирование конечного частично определённого автомата Построение таблицы поведения автомата и соответствующего графа. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции "п... Исследование и логическое проектирование конечного частично определенного автомата Построение графа и таблицы поведения автомата. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции y. Определение бул... Разработка аппаратной реализации блочного шифра Требования к блочным шифрам. Основные операции, используемые в блочных шифрах. Синтез схемы логического устройства, реализующего операцию перестановки... Исследование возможностей основных соотношений булевой алгебры для решения практических задач Логический синтез устройства с использованием соотношений булевой алгебры. Составление таблицы истинности. Основные соотношения булевой алгебры. Логич... Синтез логической схемы цифрового устройства Выполнение синтеза логической схемы цифрового устройства по заданным условиям его работы в виде таблицы истинности. Получение минимизированных функций...