44741

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

Курсовая

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

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

Русский

2014-12-02

896.5 KB

250 чел.

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

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

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


СОДЕРЖАНИЕ

                С.

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

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


 

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

41721. ДИОДНЫЕ ОГРАНИЧИТЕЛИ И ФИКСАТОРЫ УРОВНЯ 340.36 KB
  В зависимости от схемы включения и режима работы нелинейного элемента ограничителя различают 3 вида ограничения: по максимуму ограничение сверху –рис.5 Диод ограничителя включается между входом и выходом схемы последовательно с нагрузкой. Если напряжение входного сигнала Uвх меньше напряжения смещения Е диод работает на обратной ветви характеристики где его внутреннее сопротивление велико и разделяет вход схемы от выхода. Форма напряжений на входе и выходе схемы иллюстрируется на рис.
41722. Подготовка и проведение измерений с помощью электронного мультиметра 200.19 KB
  Испытание однофазного трансформатора при работе под нагрузкой Методическое указание Самара Самарский государственный технический университет 2008 Печатается по решению Редакционно-издательского совета СамГТУ УДК621. 313 Испытание однофазного трансформатора при работе под нагрузкой: метод. Содержат практические рекомендации по экспериментальным методам определения основных характеристик однофазного трансформатора по обработке опытных данных и оформлению отчетов а также контрольные вопросы. Этот процесс...
41723. Создание и редактирование таблиц, построение диаграмм 601.37 KB
  Рассмотрим некоторые особенности ввода текста в ячейки рабочего листа. Текст "Наименование", который вводится в ячейку А1, целиком в этой ячейке не помещается и занимает еще и ячейку В1 (рис. 2.3). Поскольку в ячейку В1 не было введено никакой информации, текст виден полностью. При вводе в ячейку В1 текста "Стоимость", текст в А1 будет виден частично, в пределах границ столбца А.Среднее количество проданного товара каждого наименования за текущий год. Общее количество проданных товаров за каждый месяц. Минимальное и максимальное количество товаров за полугодие количество максимальных продаж. Вклад в продажи сахара в общее количество проданного товара за...
41724. Частотные характеристики типовых звеньев систем автоматического управления 1.47 MB
  Построение частных характеристик типовых звеньев средствами математического пакета MATLAB и изучение зависимости этих характеристик от параметров входящих в состав передаточной функции.Построить следующие частотные характеристики: ЛАЧХ; ФЧХ; АФЧХ. Увеличив значение T в 10 раз определить как изменятся частотные характеристики. Задание 1 Используя пакет MTLB получим частотные характеристики.
41726. Исследование электрической цепи с последовательным и параллельным соединениями приёмников электрической энергии 349.01 KB
  Проверка на опыте особенностей последовательного и параллельного соединения резисторовэ,и при этом образуется неразветвленная цепь или участок цепи. Для последовательного соединения характерно то что во всех этих резисторах возникает одинаковый ток а падения напряжения на них пропорциональны сопротивлениям: Каждое сопротивление может быть найдено по формулам: Падение напряжения на всем участке цепи равно сумме падений напряжений на каждом резисторе: Эквивалентное сопротивление участка цепи равно сумме сопротивлений каждого резистора: Если же к концам участка вместо трех резисторов подключить эквивалентный...
41727. Органолептическая оценка качества сырья и приготовление полуфабрикатов из мяса и домашней птицы 101.48 KB
  Организация рабочего места используемые технологическое оборудование посуда инвентарь из мясного цеха Органолептическая оценка мяса. Признаки свежести мяса. Полуфабрикаты из мяса приготовление котлетной массы.
41728. Решение оптимизационных задач с помощью надстройки Excel «Поиск решения» 21.87 MB
  Ниже перечислены основные правила которыми следует руководствоваться чтобы создать качественную модель на основе электронных таблиц: необходимо четко обозначить все переменные; следует четко обозначить входы модели переменные решения и параметры; надо указать критерии эффективности и выходные переменные; не следует жестко привязывать значения параметров к формулам параметры должны храниться в отдельных ячейках рабочего листа для удобства документирования и анализа; если это возможно надо отделять переменные представляющие...