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

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Ижевский Государственный Технический Университет им. М. Т. Калашникова Факультет «Информатика и вычислительная техника»

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

Курсовая работа по дисциплине «Схемотехника ЭВМ»

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

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

Выполнил: Студент гр. Б06−781−2з Чернышев М.С.

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

Гитлин В.Б.

Ижевск 2014 г.

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

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

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

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

Функция имеет шесть переменных, поэтому при её минимизации используем карту Карно на шесть переменных. Минимальное покрытие достигается в том случае, если значения функции на наборах 0, 1 000 100 000, 101 000 доопределить до нуля.

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

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

.

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

.

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

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

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

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

.

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

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

Общие части 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.

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

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

.

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

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

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

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

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

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

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

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

схема факторизация логический элемент

3. Построение схемы в универсальном базисе и в базисе, определяем заданием

Перевод в базис ИЛИ-НЕ.

Все элементы булева базиса заменяем элементами ИЛИ-НЕ. Переменные, поступающие на входы элементов И исходной схемы, инвертируем. Переменные, поступающие на входы элементов ИЛИ исходной схемы, оставляем без изменений. Так как последним элементом исходной схемы является элемент ИЛИ, то на выходе схемы устанавливаем инвертор.

4. Определение исходных данных для расчёта принципиальной схемы логического элемента

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

1. Тип схемы логического элемента и технические условия на элемент указываются в задании на курсовой проект.

В резисторно-транзисторных логических схемах (РТЛ) логические функции реализуются на резисторах R1, а транзистор выполняет функции инверсии и формирования сигнала. Будем рассматривать вариант логической схемы РТЛ, предназначенный для выполнения операции ИЛИ-НЕ в позитивной логике.

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

2. Коэффициент объединения по входу m определяется по функциональной схеме, построенной в универсальном базисе.

Для одноступенчатых элементов И-НЕ и ИЛИ-НЕ коэффициент m равен максимальному количеству входов одного элемента. Поэтому определяем коэффициент объединения по входу как m = 3.

3. Коэффициент разветвления по выходу n определяют исходя из предположения, что сигналы на входы логических элементов разработанной схемы поступают с выходов таких же логических элементов. Разрабатываемые логические элементы не имеют инверсии на входах. Для выполнения инверсии входных переменных необходимо дополнительно устанавливать инверторы.

К шине подключено три входа со стороны логических элементов. Поэтому определяем коэффициент разветвления по выходу как n = 3.

1. Гитлин В. Б. Методические указания по выполнению курсового проекта по дисциплине «Схемотехника»: учебное пособие. — Ижевск: Изд-во ИжГТУ, 2012.

2. Гитлин В. Б., Казаков В. С. «Введение в схемотехнику электронных вычислительных машин: учебное пособие» — Ижевск: Изд-во ИжГТУ, 2008 — 584 с.

.ur