Факторизация покрытия и выбор функциональной схемы ячейки минимальной стоимости. Построение схемы в универсальном базисе. Тип схемы элемента. Перевод в базис ИЛИ-НЕ. Определение исходных данных для расчёта принципиальной схемы логического элемента.
Краткое сожержание материала:

Размещено на

Размещено на

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

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования

Ижевский Государственный Технический Университет

им. М. Т. Калашникова

Факультет «Информатика и вычислительная техника»

Кафедра «Вычислительная техника»

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

по дисциплине «Схемотехника ЭВМ»

на тему «Минимизация и факторизация булевой функции»

вариант № 21-11.

Выполнил: Студент гр. Б06-781-2з

Чернышев М.С.

Проверил: Профессор д.т.н.

Гитлин В.Б.

Ижевск 2014г.



1. Минимизация исходного состояния

Пусть частично определённая логическая (переключательная) функция задана кубическими комплексами

,

на котором функция принимает значение, равное единице (F = 1), и

на котором функция может принимать как единичное, так и нулевое значение (F = d). Говорят, что функция F на множестве N не определена.

	000	010	110	100	101	111	011	001
000	d0			d0	d0			d0
010	1	1	1	1	1	1	1	1
110	1	1	1	1	1	1	1	1
100
101
111					1		1	1
011	1		1	1
001

Функция имеет шесть переменных, поэтому при её минимизации используем карту Карно на шесть переменных. Минимальное покрытие достигается в том случае, если значения функции на наборах 000000, 001000 100000, 101000 доопределить до нуля.

Схема, реализующая это покрытие



Стоимость схемы:

Оценим выигрыш в стоимости, полученный за счёт минимизации. Стоимость схемы до минимизации можно определить непосредственно по исходному покрытию L:

.

Выигрыш по стоимости составит

.

Минимальное покрытие, имеет вид:

2. Факторизация покрытия и выбор функциональной схемы ячейки минимальной стоимости

Еще раз подчеркнём. Факторизация не обязательно снижает стоимость схемы. Ее основная задача - уменьшение коэффициента объединения по входу логических элементов путём перехода от двух уровневых схем к многоуровневым. При этом изменяется стоимость схемы, изменяется количество используемых в схеме логических элементов, увеличивается число ступеней, повышается время прохождения сигнала от входа до выхода и снижается быстродействие. Необходимость и глубина выполнения факторизации определяются разработчиком.

В рассматриваемом примере используем второй метод факторизации. Запишем минимальное покрытие, поученное после минимизации в виде ДНФ:

.

Обозначим термы функции как X1, X2, X3, X4, X5, X6 и заменим переменные их порядковыми номерами:

Составим таблицу пересечений термов. Выпишем общие части термов и найдём экономию, получаемую после их вынесения

	X1	X2	X3	X4	X5
	-
	5	-
	5	5	-
	5		3,4,5	-
	5		5	5	-
	-				-



Общие части Z1, Z4, и Z5 дают экономию на 3 входа. Вынесем Z5. После вынесения вверх конъюнкции Z5 выражение для функции F можно записать как:

.

Эта функция может быть реализована при помощи схемы



Исходное множество X1,X2,X3,X4,X5,X6 разбивается на два подмножества: X31 , X41 и X1, X2, X5, X6, Z5. Дальнейшее вынесение вверх возможно только по отдельности в каждом из множеств.

Проведём вынесение вверх для множества X1 , X2 , X5 , X6 , Z5.

Составим таблицу пересечений термов. Выпишем общие части термов и найдём экономию, получаемую после их вынесения

	X1	X2	X5	X6
	-
	5	-
	5		-
	-		-	-
	5	5	5	3,4

Вынесем Z9,как дающее максимальную экономию, на данном этапе. После вынесения вверх конъюнкции Z9 выражение для функции F можно записать как:

.



Исходное множество X1, X2, X5, X6, Z5 разбивается на два подмножества: X21 , X51 и X1, X6, Z5, Z9.

Проведём вынесение вверх для множества X1 , X6 , Z5, Z9.

Составим таблицу пересечений термов. Выпишем общие части термов и найдём экономию, получаемую после их вынесения

	X1	X6	Z5
	-
	-	-
	5	3,4	-
	5	-	5

Вынесем Z13 на данном этапе. После вынесения вверх конъюнкции Z13 выражение для функции F можно записать как:

Исходное множество X1 , X6 , Z5, Z9 разбивается на два подмножества: X61 , Z51 и X1, Z9, Z13.

Проведём вынесение вверх для множества X1, Z9, Z13.



Вынесем Z14 на данном этапе. После вынесения вверх конъюнкции Z13 выражение для функции F можно записать как:

Из схемы следует, что факторизация уменьшила максимальное значение коэффициента объединения по входу...