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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовой проект

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

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

Содержание

Введение

1. Исходные данные

2. Построение карт Карно

3. Переход от булевых выражений к функциональным схемам

4. Минимизация заданной функции

5. Факторизация покрытий

6. Схемная реализация факторизированного покрытия

7. Перевод схемы в универсальный базис

8. Описание работы схемы

Заключение

Список использованных источников

Введение

Цель работы: преобразовать данную булеву функцию, минимизировать ее произвести факторизацию, оценить экономию, а также выполнить схемную реализацию факторизованного покрытия.

При переходе от кубической записи булевой функции к функциональной схеме переменные одного куба объединяются знаком конъюнкции, т.е. являются входами одной схемы И, все кубы объединяются друг с другом знаком дизъюнкции, т.е. выходы схем И являются входами одной схемы ИЛИ. Около входа схемы И ставится переменная без инверсии, если на соответствующем месте в кубе стоит 1; с инверсией, если на соответствующем месте в кубе стоит нуль; вход остается пустым, если на соответствующей месте стоит X.

1. Исходные данные

Вариант №12

Тип множества	12
L	011X0 0011X 101X1 00X0X 111XX 0X010 01011

Рисунок 1

2. Построение карт Карно

Для проведения минимизации составим карты Карно для пяти переменных по следующей схеме

Рисунок 2 - Карта Карно пяти переменных

Данный набор содержит в себе кубы различно размерности: одномерной, двухмерной и нулевой.

Одномерный куб E12. На этом кубе переменная x1 может принимать значения 0 и I. Для каждого значения x1 функция F(x1) также может принимать значения либо 0, либо 1.

. Двумерный куб ^* На этом кубе переменные я ж^ могут принимать одно из значений 0 ила I; всего возможно четыре комбинации,- что отпечено на рис.3 кружками. На первой позиции каждой комбинации отмечено значение х₍, на второй -позиции - зс^, Для каждой из комбинаций я,: одно аз значений; 0 или I.

3.

Двумерный куб E₂². На этом кубе переменные x₁ и x₂ могут принимать одно из значений: 0 или 1. Для каждой из комбинаций x₁x₂ функция F(x₁x₂) может принимать одно из значений: 0 или 1.

В исходных данных задана функция F(x₁, x₂, x_3, х₄, х₅), которая равна 1 на следующих наборах

Дизъюнктивная нормальная форма такой функции

.

Построим для данной функции карты Карно

Рисунок 3 - Карта Карно для исходных данных

Построение карт Карно по данным функциям производилось следующим образом, на примере набора 011X0. Так как вторая и пятая координата куба равны 0, а вторая и третья равны 1, то единицы проставляем во всех клетках, где вторая и пятая координата куба равны 0, а вторая и третья равны 1. Четвертая позиция может быть как равна 0 так и 1, что проставляем единицы в клетках, где четвертая позиция равна 0, либо 1. Аналогично заполняются клетки для оставшихся кубов

3. Переход от булевых выражений к функциональным схемам

При переходе от кубической записи булевой функции к функциональной схеме переменные одного куба объединяются знаком конъюнкции, т.е. являются входами одной схемы И, все кубы объединяются друг с другом знаком дизъюнкции, т.е. выходы схем И являются входами одной схемы ИЛИ. Около входа схемы И ставится переменная без инверсии, если на соответствующем месте в кубе стоит 1; с инверсией, если на соответствующем месте в кубе стоит нуль; вход остается пустым, если на соответствующей месте стоит X.

Строим функциональную схему для исходных данных.

Найдем стоимость схемы по следующей формуле:

, (1)

Где n - общее число координат,

r - размерность куба

К - число кубов, на которых функция равна 1



Рисунок 4 - функциональная схема

4. Минимизация заданной функции

Используются следующие принципы минимизации:

1. Построить максимальные кубы на клетках, где функций 1 (простые импликанты).

2. Найти клетки, которые покрываются только одним кубом (обособленные клетки или вершины куба).

3. Включить в минимальное покрытие все кубы, которые покрывают обособленные клетки.

4. Удалить из рассмотрения покрытые клетки. Выбросить из рассмотрения кубы, которые покрывали что-то из выбранных клеток, если клетки, покрываемые отбрасываемыми кубами, имеют другое покрытие в виде другого куба равной или большей размерности по сравнению с отбрасываемым кубом.

5. Продолжить процесс поиска.

Таким образом, следуя данному принципу минимизации отброшенными из рассмотрения кубами будут: 00Х0Х, 00ХХ0. 111ХХ.

Кубами вошедшими в минимальное покрытие станут:

1X1X1, 001XX, X11X0, 0101X, 0000X, 0X010

Окончательное минимальное покрытие будет выглядеть следующим образом:

Функциональная схема после минимизации

Рассчитаем стоимость:

Рассчитаем экономию:

Стоимость схемы до минимизации

W(C(F))=34

Стоимость после минимизации

W(C(F))_min=25



Рисунок 5 - Функциональная схема после минимизации функции

Выигрыш в стоимости составляет

ДW=34-25=9

5. Факторизация покрытий

В основе первого алгоритма факторизации (м-алгоритм) лежит м-произведение, которое обозначается a_м b, слагается из результатов покоординатных произведений

и выполняется в соответствии с таблицей 1:

Таблица 1.

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

1. Берем полученное минимизированное покрытие C₀(F):

2. Определяют м-произведения всех кубов из C₀(F). Это удобнее проделать при помощи следующей таблицы (Табл. 2). По вертикали в первой слева колонке размещены кубы покрытия C₀(F), по горизонтали в первой сверху строчке размещены те же кубы, без последнего. На месте пересечения кубов самих с собой ставят прочерки.

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

Таблица 2 - м-произведения всех кубов из C₀(F)

	1X1X1	001XX	X11X0	0101X	0000X
1X1X1	-	-	-	-	-
001XX	µ µ1 µ µ	-	-	-	-
X11X0	µ µ1 µ µ	µ µ1 µ µ	-	-	-
0101X	µ µ µ µ µ	0 µ µ µ µ	µ1 µ µ µ	-	-
0000X	µ µ µ µ µ	00 µ µ µ	µ µ µ µ µ	0 µ0 µ µ	-
0X010	µ µ µ µ µ	0 µ µ µ µ	µ µ µ µ0	0 µ01 µ	0 µ0 µ µ

3. Выбираем маскирующий куб C_м, имеющий максимальную стоимость. Стоимость куба определяется по формуле:

,

где r_м - общее число координат куба, не равных м.

Кубом, имеющим максимальную стоимость, будет куб

.

4. В таблице отмечаем кубы, отмаскированные выбранным маскирующим кубом. Ими будут кубы 0X010, 0101X.

5. Покрытие C₀(F) разбиваем на три части. Вверху располагают кубы, кубы, которые не покрываются маскирующим кубом. Затем записывается маскирующий куб. Под ним помещаются отмаскированные кубы с прочерками на тех координатах, которые не равны м в маскирующем кубе.

6. Отмаскированные кубы исключаем из рассмотрения. После исключения отмаскированных кубов алгоритм повторяется.

7. Вновь строится таблица (таблица 3)

Таблица 3 - м-произведения всех кубов из C₁(F)

	1X1X1	001XX	X11X0	0000X
1X1X1	-	-	-	-
001XX	µ µ1 µ µ	-	-	-
X11X0	µ µ1 µ µ	µ µ1 µ µ	-	-
0000X	µ µ µ µ µ	00 µ µ µ	µ µ µ µ µ	-
0 µ01 µ	µ µ µ µ µ	0 µ µ µ µ	µ µ µ µ µ	0 µ0 µ µ

8. Выбирается маскирующий куб максимальной стоимости.

Выберем один из кубов, им будет куб

9. Отмечаются кубы, отмаскированные C_м3. В данном случае таковыми будут 0000Х, 0 µ01 µ.

10. Покрытие C₂(F) разбивается вновь на три части.

.

11. Снова строим таблицу

Таблица 4 - м-произведения всех кубов из C₂(F)

	1X1X1	001XX	X11X0
1X1X1	-	-	-
001XX	µ µ1 µ µ	-	-
X11X0	µ µ1 µ µ	µ µ1 µ µ	-
0 µ0 µ µ	µ µ µ µ µ	0 µ µ µ µ	µ µ µ µ µ

Выбираем маскирующие кубы с максимальной стоимостью.

Отмечаем кубы, отмаскированные C_м5. В данном случае таковыми будут 001ХХ, Х11Х0, 1Х1Х1. И строим покрытие.

12. Так остались еще неотмаскированные кубы, снова строим таблицу.

Таблица 5 - м-произведения всех кубов из C₃(F)

	0 µ0 µ µ
0 µ0 µ µ	-
µ µ 1 µ µ	µ µ µ µ µ

13. Алгоритм заканчивается, когда не останется неотмаскированных кубов, либо маскирующий куб максимальной стоимости будет состоять только из одних м (нулевая стоимость).

Таким образом, окончательное факторизованное покрытие будет выглядеть следующим образом.



6. Схемная реализация факторизированного покрытия

булевый транзистор карта карно

Отобразим полученное факторизованное покрытие в виде схемы

Рисунок 6 - Схемная реализация факторизованного покрытия

7. Перевод схемы в универсальный базис

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

1. Универсальный базис ИЛИ-НЕ.

Обозначение базисного элемента ИЛИ-НЕ показано на рисунке 6.



Рисунок 6 - Элемент базиса ИЛИ-НЕ

Операция инверсии реализуется при помощи элемента ИЛИ-НЕ с одним входом (рисунок 7).

Рисунок 7 - Реализация операции НЕ (а) при помощи элемента ИЛИ-НЕ (б)

Операцию И получают с использованием теоремы де Моргана: , т. е. путем подачи инвертированных значений переменных на входы элемента ИЛИ-НЕ (рисунок 8)

Рисунок 8 - Реализация операции И (а) при помощи элемента ИЛИ-НЕ (б)

Для выполнения операции ИЛИ используют два элемента, поскольку (рисунок 9)

Рисунок 9 - Реализация схемы в универсальном базисе ИЛИ-НЕ

Правила перехода из булева базиса И, ИЛИ, НЕ в универсальный базис ИЛИ-НЕ.

1. При переходе в базис ИЛИ-НЕ все логические элементы заменяют на элементы ИЛИ-НЕ.

2. Независимые входы элементов И инвертируют, независимые элементов входы ИЛИ оставляют неизменными.

3. На выходе схемы устанавливают инвертор, если выход снимался с элемента ИЛИ.

В результате перевода получается следующая схема:

Рисунок 10 - Схема в универсальном базисе ИЛИ-НЕ

Поскольку двойное инвертирование эквивалентно отсутствию операции, то схему можно упростить

Если посчитать стоимость схемы, то она будет составлять: W_б=23.

Если сравнить с ценой схемы минимизированного покрытия, то после проведения факторизации и перевода схемы в универсальный базис, то экономия в цене составит:

ДW=25-23=2

Коэффициент объединения по входу m=3

Коэффициент объединения по выходу: n=2

А если сравнивать максимальную экономию от первоначальную функции, то она составит:

ДW=34-23=11

Рисунок 11 - упрощенная схема в универсальном базисе ИЛИ-НЕ

8. Описание работы схемы

Рисунок 12

При подаче напряжения на один из входов(X₁..X_M) транзисторы открываются и на выходе(N) получается 0. Когда на вход ничего не подается, транзистор закрыт - на выходе высокий уровень напряжения.

Таким образом, при подаче «1» хотя бы на один вход на выходе элемента присутствует «0». Только при наличии «0» одновременно на всех входах на выходе элемента получаем «1».

Параллельное соединение транзисторов с нагрузкой в цепи коллектора позволяют выполнять операцию ИЛИ-НЕ. В данной схеме транзисторы являются инверторами. Они состоят из транзисторов VT1..VT2 c установленным в цепи коллектора резистором R_к.

C - форсирующий конденсатор, нужен для сокращения времени работы транзистора

Когда на базу транзистора идет высокий уровень - конденсатор заряжается

В процессе заряда конденсатора С ток через него снижается. После того как С полностью зарядится, ток в базу транзистора пойдет только через R1.

После окончания процесса перезаряда на конденсаторе С присутствует напряжение. В момент поступления на вход отрицательного перепада потенциал левой обкладки конденсатора снижается.

Отрицательный потенциал правой обкладки, будучи приложенным к базе, форсированно закрывает транзистор. Ток рассасывания заряда из базы транзистора возрастает за счет тока перезаряда конденсатора С.

- E_см - источник смещения. Из-за больших номиналов резисторов использование источника смещения обязательно.

минимизация покрытие карта карно

Заключение

В данном курсовом проекте была проведена минимизация и факторизация заданной булевой функции. После проведенных действий экономия в цене схемы составила 11. В результате схемной реализации факторизованной булевой функции была получена ее схема в универсальном базисе, которая в дальнейшем была переведена в базис ИЛИ-НЕ.

Список использованных источников

1. Гитлин В.Б. Методические указания по выполнению курсового проекта по курсу «Схемотехника ЭВМ», 2011.

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

Размещено на Allbest.ru