44741

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

Курсовая

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

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

Русский

2014-12-02

896.5 KB

253 чел.

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

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

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


СОДЕРЖАНИЕ

                С.

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

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


 

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

40148. ИНФОРМАЦИЯ В ДИСКРЕТНЫХ СООБЩЕНИЯХ 412.5 KB
  Когда говорят об информации то имеют в виду как объективные сведения о событиях в материальном мире так и получателя этих сведений то есть субъекта. Определить количество информации и передать его с наименьшими потерями по каналам связи не интересуясь смыслом информации это предмет теории информации которую иногда называют математической теорией связи. Качественная сторона информации например её ценность полезность важность исследуется в семантической теории информации.
40149. ИНФОРМАЦИЯ В НЕПРЕРЫВНЫХ СООБЩЕНИЯХ 1.23 MB
  Представляет интерес определить собственное количество информации заключённое в непрерывном сообщении с тех же позиций что и для дискретного сообщения то есть с использованием понятия энтропии. Замену непрерывной функции времени можно осуществить последовательностью дискретов на основании теоремы Котельникова согласно которой если отсчёты непрерывного сообщения взять через интервал t=1 2Fc где Fc максимальная частота спектра реализации xt то непрерывная функция xt на интервале времени наблюдения [0T] эквивалентна...
40150. ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА СВЯЗИ 1.03 MB
  Рассматривая появление символа алфавита как реализацию случайной величины можно найти энтропию сообщения на входе канала связи 3. Пусть в канале связи отсутствуют помехи. Пусть в канале связи действуют помехи рис.
40151. ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ ИНФОРМАЦИИ 87.5 KB
  Кодирование линии связи заключается в преобразовании закодированного сообщения при котором обеспечивается возможность надежной синхронизации и минимум искажений при трансляции сообщения через линию связи среду передачи информации при этом число исходных комбинаций равно числу закодированных. В теоретическом плане эта возможность основывается на наличии избыточности сообщения. Под избыточностью сообщения понимают разность между максимально возможной и реальной энтропией . Максимально возможная энтропия определяется для случая когда...
40152. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ. КЛАССИФИКАЦИЯ КОДОВ 146 KB
  По длине кодов и взаимному расположению в них символов различают равномерные и неравномерные коды. Неравномерные коды отличаются тем что кодовые комбинации у них отличаются друг от друга не только взаимным расположением символов но и их количеством при минимизации средней длины кодовой последовательности. Очевидно что средняя длина неравномерного кода будет минимизироваться тогда когда с более вероятными сообщениями источника будут сопоставляться более короткие комбинации канальных символов. Тем самым создается возможность обнаружения и...
40153. МОДУЛЯЦИЯ СИГНАЛОВ 143.5 KB
  В современных цифровых системах связи радиолокации радионавигации и радиотелеуправления также применяются различные виды импульсной модуляции.2 Радиосигналы с амплитудной модуляцией При АМ амплитуда несущего колебания меняется в такт передаваемому сообщению st Тогда общее выражение для АМ сигнала будет иметь вид: где амплитуда в отсутствии модуляции; угловая круговая частота; начальная фаза; безразмерный коэффициент пропорциональности; модулирующий сигнал. Рассмотрим простейший вид амплитудной модуляции ...
40154. РАДИОПЕРЕДАЮЩИЕ И РАДИОПРИЕМНЫЕ УСТРОЙСТВА 44.5 KB
  Назначение классификация и основные параметры Радиопередающие устройства радиопередатчики предназначены для формирования колебаний несущей частоты; модуляции их по закону передаваемого сообщения и излучения полученного радиосигнала в пространство или передачи его по физическим линиям связи. Нестабильность частоты несущих колебаний. Абсолютной нестабильностью частоты называется отклонение частоты f излучаемого радиопередатчиком сигнала от номинального значения частоты fном. Относительной нестабильностью частоты называется отношение...
40155. Основы радиоэлектроники и связи 78 KB
  В ней рассматриваются способы математического представления сообщений сигналов и помех методы формирования и преобразования сигналов в электрических цепях вопросы анализа помехоустойчивости и оптимального приема сообщений основы теории информации и кодирования. Знания полученные в результате изучения дисциплины являются базой для глубокого усвоения материала по существующим и перспективным методам передачи информации сравнительному анализу этих методов и выявлению наиболее рациональных способов повышения эффективности радиоэлектронных...
40156. ОБЩИЕ СВЕДЕНИЯ О РАДИОТЕХНИЧЕСКИХ СИГНАЛАХ И ПОМЕХАХ 1.75 MB
  Импульсный сигнал это сигнал конечной энергии существенно отличный от нуля в течение ограниченного интервала времени соизмеримого со временем завершения переходного процесса в системе для воздействия на которую этот сигнал предназначен. Конкретный вид случайного процесса который наблюдается во время опыта например на осциллографе называется реализацией этого случайного процесса. Примером такого процесса является процесс характеризующий состояние системы массового обслуживания когда система скачком в произвольные моменты времени t...