44741

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

Курсовая

Информатика, кибернетика и программирование

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

Русский

2014-12-02

896.5 KB

252 чел.

Пояснительная записка к курсовому проекту

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

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


СОДЕРЖАНИЕ

                С.

Введение………………………………………………………………

3

1.

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

3

2.

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

3

3.

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

5

4.

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

7

5.

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

9

6.

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

13

7.

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

14

8.

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

18

ЗАКЛЮЧЕНИЕ………………………………………………………….

20

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………………

21

Введение

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

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


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

Вариант № 12

Тип множества

12

L

011X0

0011X

101X1

00X0X

111XX

0X010

01011

Схема №12


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

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

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

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

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

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

3.

Двумерный куб E22.  На этом кубе переменные   x1 и x2 могут принимать одно из значений: 0 или 1. Для каждой из комбинаций x1x2 функция F(x1x2) может принимать одно из значений: 0 или 1.

В исходных данных задана функция F(x1, x2, x3, х4, х5), которая равна 1  на следующих наборах   

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

.

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

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

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

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

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

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

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

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

,                            (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

W(C(F))=34

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

W(C(F))min=25

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

ΔW=34-25=9

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

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

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

Таблица 1.

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

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

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

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

Таблица 2 -  μ-произведения всех кубов из C0(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. Покрытие C0(F) разбиваем на три части. Вверху располагают кубы, кубы, которые не покрываются маскирующим кубом. Затем записывается маскирующий куб. Под ним помещаются отмаскированные кубы с прочерками на тех координатах, которые не равны μ  в маскирующем кубе.

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

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

Таблица 3  -  μ-произведения всех кубов из C1(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. Покрытие    C2(F) разбивается вновь на три части.

 .

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

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

1X1X1

001XX

X11X0

1X1X1

-

-

-

001XX

µ µ1 µ µ

-

-

X11X0

µ µ1 µ µ

µ µ1 µ µ

-

0 µ0 µ µ

µ µ µ µ µ

0 µ µ µ µ

µ µ µ µ µ

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

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

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

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

0 µ0 µ µ

0 µ0 µ µ

-

µ µ 1 µ µ

µ µ µ µ µ

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

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

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

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

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

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

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

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

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

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

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

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

ИЛИ-НЕ (б)

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

Рисунок 8 – Реализация операции И (а) при помощи элемента

ИЛИ-НЕ (б)

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

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

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

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

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

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

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

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

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

Wб=23.

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

ΔW=25-23=2

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

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

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

ΔW=34-23=11

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

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

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


 

А также другие работы, которые могут Вас заинтересовать

13743. История отечества. Тест. Вариант 11 121 KB
  Вариант №11 Часть 1 А1. Какое событие древнейшая русская летопись Повесть временных лет относит к 945 г. 1 восстание древлян 3 призвание варягов в Новгород 2 крещение князя Владимира 4 поход князя Олег
13744. История отечества. Тест. Вариант 12 123.5 KB
  Вариант №12 Часть 1 А1.Установление монголотатарского ига на Руси произошло в 1 XI в. 2 XII в. 3 XIII в. 4 XIV в. А2. Соседями восточных славян в период Древней Руси являлись ...
13745. История отечества. Тест. Вариант 13 128.5 KB
  Вариант №13 Часть 1 А1. Какое из названных событий произошло в XV в. 1 основание славяногреколатинской академии 2 церковнообрядовая реформа патриарха Никона 3 издание печатной книги Апостол ...
13746. История отечества. Тест. Вариант 14 120.5 KB
  Вариант №14 Часть 1 А1. В XIII в. произошло событие 1 сражение на реке Калке 3 Грюнвальдская битва 2 взятие Казани 4 Куликовская битва А2. Избранию царя из династии Романовых предшествовало с
13747. История отечества. Тест. Вариант 15 119.5 KB
  Вариант №15 Часть 1 А1. Земли Поволжья и волжский торговый путь в состав Русского государства вошли в 1 XIII в. 2 XIV в. 3 XVI в. 4 XVIII в. А2. Имена Григория Отрепьева и Марины Мнишек связанны с событи...
13748. Тести до ЗНО. Географія 4.98 MB
  Тести підготовлені групою вчителів які проходили курсову підготовку з 13 червня по 30 червня 2006р Час виконання 120 хвилин Інструкція Екзаменаційний тест складається з 50 тестових завдань різних рівнів. Правила виконання містяться на початку кожно...
13749. ГЕОГРАФІЯ Типові завдання 350.5 KB
  ГЕОГРАФІЯ Типові завдання Час виконання 120 хвилин Інструкція Екзаменаційний тест складається з 50 тестових завдань різних типів. Правила виконання містяться на початку кожного типу завдань. Відповідайте тільки після того як Ви уважно прочи...
13750. Искусство и власть 34 KB
  1. Искусство и власть. В развитии человеческой культуры постоянно прослеживается любопытная закономерность того как искусство часто использовалось для укрепления власти светской и религиозной. Благодаря произведениям искусства власть укрепляла свой...
13751. Искусство вокруг нас. Виды искусства 642 KB
  Вопрос 1. Искусство вокруг нас. Виды искусства. Искусство часть духовной культуры человечества специфический род духовно практического освоения мира. К искусству относят разновидности человеческой деятельности объединяемые художественно образными формами в