44741

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

Курсовая

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

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

Русский

2014-12-02

896.5 KB

257 чел.

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

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

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


СОДЕРЖАНИЕ

                С.

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

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 с.


 

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

53422. Важливість упровадження в навчальний процес інтерактивних технологій як одного із засобів особистісно-зорієнтованого навчання 43 KB
  Сучасна школа стоїть перед прикрим фактом: в умовах традиційних форм та методів навчання школярі пасивно отримуючи інформацію не вміють здобувати її самостійно і застосовувати те що знають. Особистіснозорієнтоване навчання у цьому плані є досить перспективним оскільки воно виходить із самоцінності особистості її духовності та суверенності. Визначальним для особистіснозорієнтованого навчання має бути соціокультурний діалог у системі âпедагог дитинаâ на основі її розуміння прийняття і визнання.
53423. Зимова подорож до святого Миколая. Виготовлення листівки бажань 41.5 KB
  Зимова подорож до святого Миколая. Мета: розширити знання учнів про святого Миколая; вчити учнів правильно виразно читати поетичні твори; збагачувати словниковий запас учнів; виготовити листівку бажань; сприяти вихованню міцної внутрішньої опори людини що знаходить свій прояв у доброті чуйності лагідності. Сьогодні на уроці ми завітаємо у гості до святого Миколая. Я знаю що день святого Миколая улюблене свято українських дітей.
53424. Інтегроване заняття з використанням наочного моделювання 31 KB
  На основі знайомої казки Колосок за допомогою схемсимволів вчити дітей сприймати зміст казки. Хіба зможемо прожити ми без них Діти вам подобаються казки Що вам подобається в казках Так всі люблять казки кони ведуть нас у світ пригод вчать розпізнавати добро зло. 1 коробка Діти підійдіть до коробки з літерою А в коробці захована схема з гудзиків за казкою Колосок З якої казки герої Який був півник Якими були мишенята Як звали Півника мишенят Чому вчить ця казочка Хто не працює той не їсть Потрібно...
53425. Формування ключових компетентностей молодшого школяра шляхом впровадження інтегрованих уроків 299 KB
  Предметних компетентностей: ознайомити дітей з усіма варіантами числа 7; вчити учнів складати розвязувати читати вирази на додавання в межах 7; вивчити назви днів тижня; розвивати мислення память; розширити знання про фрукти їх користь для людей; збагатити словниковий запас поняттями екзотика екзотичні фрукти; виховувати бережливе ставлення до природи зокрема садупрагнення до здорового харчування. Обладнання: мультимедійний проектор компютер аудіозаписи мікрофон демонстраційний матеріалкартки із...
53426. Закріплення вивчених букв. Робота з дитячою книгою. Українська народна казка «Курочка Ряба». Виготовлення курочки з солоного тіста 209 KB
  Мета Формувати у дітей поняття про казку як художній твір,Розвивати навички слухання та інтонування почутого, мовлення, уяву, фантазію, логічне раціональне мислення, використовуючи методи інтерактивного навчання; закріплювати вміння читати слова, речення та тексти з вивченими буквами, вдосконалювати навички звукового аналізу слів;
53427. Таблицы сложения и вычитания числа 9. Периметр четырехугольника. Изготовление кораблика способом оригами 180.5 KB
  Трудовое обучение: продолжать знакомить учеников с оригами как видом искусства; учить изготавливать кораблик способом складывания и перегибания бумаги; развивать внимание усидчивость умение работать по технологической карте; воспитывать усидчивость старательность. Как называется эта геометрическая фигура четырехугольник Работа по таблице четырехугольники.
53428. Весна прийшла. Вірш Л.Українки «Вишеньки». Виготовлення сувеніру для мами 76.5 KB
  Мета: вчити учнів виготовляти сувеніри і розвивати вміння самостійно добирати розмір колір матеріал працювати з поролоном і картоном; формувати емоційно-позитивне ставлення до художнього образу вишні; поглибити кявлення про народні звичаї та повіря; розвивати звязне мовлення творчість мислення естетичний смак; виховувати любов до мами почуття вдячності і шанобливе ставлення повагу гордість за рідну матусю бажання...
53429. Життя в добрі 3.65 MB
  Так би і померла та людина, аби тою дорогою не проїздив самарянин. Треба відмітити, що євреї не любили самарян. Вони не розмовляли з самарянами і навіть не пускали їх у свій храм для поклоніння Богу. Але коли самарянин побачив пораненого єврея, то не став згадувати про це.
53430. Математична подорож на Південний берег Криму 722 KB
  На тему: Математична подорож на Південний берег Криму. Математичнаподорож на Південний берег Криму. Ознайомити учнів з географічним положенням рослинним та тваринним світом Південного берега Криму розширювати та збагачувати знання дітей про природу виховувати любов до природи та бережливе ставлення до її багатств. Обладнання: фізична карта України гербарій рослин Південного берега Криму мультимедійні засоби навчання малюнки підручники: 1 Богданович М.