Главная страница
Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей
qrcode

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


Название4. минимизация булевых функций с помощью карт карно-вейча Двоичная система счисления
Анкорраздел 4.doc
Дата30.09.2017
Размер1.11 Mb.
Формат файлаdoc
Имя файлараздел 4.doc
ТипДокументы
#22555
КаталогОбразовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей
Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей

4. минимизация булевых функций с помощью карт

карно-вейча
4.1. Двоичная система счисления.

Числовой и графический способ задания булевых функций
Под системой счисления будем понимать способ записи чисел с помощью цифровых знаков. В настоящее время используются так называемые позиционные системы счисления, в которых изменения положения цифры в записи числа ведет к изменению самого числа, что не всегда выполняется в непозиционных системах счисления. Позиционной системой счисления (СС) называется такая, которая удовлетворяет следующему равенству:

где A(q) – запись числа в q-ичной СС;

q – основание СС (целое число, лежащее в диапазоне от 1 до N);

ак – значение к-го разряда в записи числа (к= -m…n, a=0, 1, …, q-1);

n – количество целых разрядов в записи числа;

m – количество дробных разрядов в записи числа, конкретные значения чисел n и m будем называть номером разряда или разрядом числа;

qP – будем называть весом разряда ( P = n, n-1, …, 1, 0, -1, -2, …, -m ).

Так, для десятичной (десятеричной) СС q = 10, aк = 0, 1, 2, …9, поэтому числа записываются следующим образом:

Например, в восьмеричной СС (q=8, ak= 0, 1, …, 7) возможна такая запись числа – 706,25(8). В СС с основанием больше 10-ти для записи чисел приходится вводить специальные символы, чтобы изображать цифры, имеющие значения больше 9. Так, например, в шестнадцатеричной СС (q=16) используются следующие символы: ак=0,1,2,3,4,5,6,7,8, 9, A, B, C, D, E, F. Число в 16-ричной СС может иметь следующий вид: 1A05F,ECD(16).

Двоичная СС оперирует двумя символами 0 и 1, т. е. в этой СС возможна такая запись числа 100101,0101(2). Так как булева алгебра тоже оперирует двумя значениями булевой переменной 0 и 1, то в некоторых случаях удобно сопоставлять булеву переменную с разрядом двоичного целого числа. Для перевода чисел из одной СС в другую разработано много алгоритмов. Приведем один из них:

  1. число, которое нужно перевести из одной СС в другую, делится нацело на основание новой СС (q) с записью остатка от деления (остаток не может быть больше или равен q);

  2. полученное частное снова делится нацело на q;

  3. пункт 2 выполняется до тех пор, пока полученное частное не окажется меньше основания новой СС;

  4. для получения записи числа в новой СС к последнему частному приписываются справа в обратном порядке все остатки от деления, полученные при выполнении пунктов 1, 2, 3. Например, десятичное число 167(10) в двоичную СС (рис. 4.1):



Рис. 4.1. Перевод числа в двоичную СС
Результат перевода: 167(10)=10101111(2).

При обратном переводе из двоичной СС в десятичную нужно в формулу 4.1 подставить необходимые значения и вычислить полученную сумму. Например, двоичное число 10010,101(2) в десятичной СС:

В табл. 4.1 представлены десятичные числа и их двоичные коды, причем над разрядами двоичных чисел записаны соответствующие им булевы переменные.


Таблица 4.1

Таблицы соответствия кодов

двоичных чисел и булевых переменных



Таблица для четырех переменных более общая и содержит в себе и табл. 4.1 (а) и табл. 4.1 (б). Если задана БФ от двух переменных, то набору х1х2=01 соответствует десятичное число 1, набору х1х2=11 – число 3, для трех переменных набору х1х2х3=100 – число 4, х1х2х3=110 – число 6, для четырех переменных набору х1х2х3х4=0101 – число 5, х1х2х3х4=1000 – число 8, х1х2х3х4=1110 – число 14 и т. д. Таким образом, БФ можно задавать перечислением наборов с указанием десятичных значений наборов булевых переменных, причем СДНФ задается как сумма (Σ) наборов, на которых БФ принимает единичное значение (конституент единицы), а СКНФ задается как произведение (Π) наборов, на которых БФ принимает нулевые значения (конституент нуля). Такой способ задания БФ называется числовым. Например, СДНФ БФ f1 из табл. 2.2 может быть задана так: f1=Σ(0,3,5,6,7). СКНФ функции f2 задается, как f2=П(0,1,3,6,7). Если БФ задана числовым способом, то чтобы узнать от какого числа переменных зависит функция, нужно перевести в двоичный код самое старшее число из указанных наборов. В отдельных случаях при задании БФ непосредственно в записи функции указываются все переменные, от которых зависит функция, например, f(х1х2х3)=Σ(0,2,3).

Очевидно, что от табличного способа задания БФ можно всегда перейти к числовому и наоборот. Если БФ задана числовым способом, то чтобы восстановить таблицу истинности нужно в столбце значений в клетках, соответствующих указанным наборам записать единицы (СДНФ) или нули (СКНФ).

Например, для БФ f1=Σ(0,2,4,6,7,8,10,12,14,15) и f2=Π(1,3,4,5,8,9,13,14) таблицей истинности является табл. 4.2:

Таблица 4.2

Таблицы истинности для БФ, заданных числовым способом

Х1

Х2

Х3

Х4

f1

f2

0

0

0

0

1

1

0

0

0

1

0

0

0

0

1

0

1

1

0

0

1

1

0

0

0

1

0

0

1

0

0

1

0

1

0

0

0

1

1

0

1

1

0

1

1

1

1

1

1

0

0

0

1

0

1

0

0

1

0

0

1

0

1

0

1

1

1

0

1

1

0

1

1

1

0

0

1

1

1

1

0

1

0

0

1

1

1

0

1

0

1

1

1

1

1

1


Кроме табличного и числового способа существует графический, или кубический, способ задания БФ. При этом функция от n переменных задается на n-мерном пространстве (n-мерном кубе), каждая вершина которого сопоставляется с одним из наборов булевых аргументов, причем значение БФ записывается в вершине соответствующего куба. Например, пусть БФ задана числовым способом f1=Σ(0,1,3). Графическое изображение этой БФ представлено на рис. 4.2.


Рис 4.2. Графическое задание БФ от двух переменных

Вершины, соответствующие единичному значению функции, отмечены закрашенными кружками, нулевому значению функции – незакрашенными. Вершины в узлах кубов располагаются в таком порядке, что две соседние вершины отличаются знаком инверсии одного аргумента. На рис. 4.3 представлено графическое изображение БФ от трех переменных f=Σ(0,2,3,4,5,7).


Рис. 4.3. Графическое представление БФ от трех переменных
4.2. Минимизация булевых функций с помощью

карт Карно-Вейча
Во второй главе уже рассматривался алгебраический способ минимизации БФ. Для построения экономичной, с точки зрения аппаратных затрат, схемы, реализующей булеву функцию, необходимо провести некоторые преобразования исходной формулы. В теории дискретных устройств разработаны различные методы минимизации. Как правило, исходной формой при проведении минимизации является СДНФ или СКНФ. Если БФ задана не совершенной формой, то к ней можно перейти с помощью преобразований.

МинимальнойДНФ (МДНФ) называют такую запись функции, которая содержит меньшее число переменных по сравнению со всеми другими ДНФ, эквивалентными исходной функции. Все методы минимизации основаны на применении законов склеивания и поглощения. Конъюнкция, получаемая в результате склеивания двух соседних конституент, называются импликантой


Различные импликанты с одинаковым числом переменных, в свою очередь, могут оказаться соседними, что позволяет склеивать их между собой. Процесс многоступенчатого склеивания приводит к получению импликант, которые уже не склеиваются с другими. Такие импликанты называют простыми. Импликанта, полученная в результате склеивания некоторого множества конституент, покрывает (поглощает) эти конституенты. Так, импликанта х2х4 покрывает четыре конституенты единицы:
.
Дизъюнкцию всех простых импликант называют сокращеннойДНФ (СокрДНФ). Любая БФ имеет только одну СокрДНФ. Сокращенная ДНФ часто является избыточной, т. к. одна и та же конституента может покрываться несколькими ипликантами. После исключения из СокрДНФ лишних импликант образуется тупиковая ДНФ (ТДНФ). При удалении из ТДНФ любой импликанты получается ДНФ, не эквивалентная исходной.

БФ может иметь несколько ТДНФ. Задача состоит в выборе ТНДФ с минимальным числом переменных. ТДНФ, содержащая наименьшее число переменных по сравнению с другими ТДНФ, называется минимальной ДНФ (МДНФ). Разработаны формализованные методы получения ТДНФ. Они описываются строгими алгоритмами и реализованы на ЭВМ. Среди этих методов существуют такие, которые пригодны для минимизации БФ от любого числа аргументов, но есть и методы, которые удобно использовать для БФ от небольшого числа аргументов. Для БФ от 2, 3, 4 и иногда от 5 и 6 переменных чаще используются методы минимизации с помощью карт, предложенных Карно и Вейчем.

Карты Карно-Вейча для БФ от n переменных представляют собой таблицы, содержащие 2n клеток, каждая из которых соответствует одному единственному набору аргументов БФ. Карты Карно отличаются от карт Вейча только разметкой, т. е. тем как идентифицируется каждая клетка карты.

Разметка карты Вейча для БФ от двух аргументов (рис. 4.4, а) осуществляется булевыми переменными, отмечающими столбцы и строки карты.


Рис. 4.4. Карты от двух переменных:

а – Вейча; б – Карно
Так, переменная x1 покрывает обе клетки левого столбца, а переменная (ее не принято показывать на карте, чтобы не загромождать ее) покрывает обе клетки правого столбца. Переменная покрывает две клетки верхней строки таблицы, а переменная покрывает две клетки нижней строки таблицы. Таким образом, каждая клетка карты имеет имя, составленное из набора переменных, покрывающих эту клетку. На карте Вейча (рис. 4.4, а) показаны имена каждой клетки, а в скобках приведены номера двоичных кодов, соответствующих наборам аргументов, покрывающих эту клетку.

Отличие карт Карно в том, что на карте Карно (рис. 4.4, б) переменная, отмечающая строку или столбец карты, обозначается 0, если она принимает инверсное значение , или 1, если переменная принимает прямое значение .

Если рассмотреть любые две соседние клетки карт, то очевидно, что конъюнкции, записанные в них, являются соседними и к ним возможно применение операции склеивания. На картах операция склеивания проводится геометрически – склеиваемые клетки карты обводятся контуром.


Рис. 4.5. Функции Z1 и Z2, нанесенные на карты:

а – Вейча; б – Карно
Нанесение БФ на карту заключается в расстановке значений БФ в соответствующие клетки карты. Если БФ задана ДНФ, то в соответствующие клетки карты заносятся 1, а если КНФ, то 0. Пусть заданы две БФ Z1=(0,1,2) и Z2=(0,1,3). Результат нанесения на карту Вейча (Z1) и карту Карно (Z2) представлен на рис. 4.5.

Минимизация с помощью карт Карно-Вейча осуществляется в соответствие со следующим алгоритмом:

  1. соседние клетки карты, отмеченные 1 для СДНФ или 0 для СКНФ, покрываются контурами, имеющими форму квадрата или прямоугольника;

  2. контур может покрывать 2k клеток, где k=0, 1, 2…n (n –количество переменных, от которых зависит БФ);

  3. все клетки, отмеченные 1 для СДНФ или 0 для СКНФ, должны быть покрыты контурами;

  4. одна и та же клетка карты может быть покрыта несколькими контурами;

  5. количество контуров должно быть минимально, а их размер максимальным;

  6. каждому контуру присваивается свое имя;

  7. БФ записывается как логическая сумма (СДНФ) или логическое произведение (СКНФ) имен контуров.

Имена контуров для ДНФ составляются по следующему алгоритму:

  1. все переменные для данного контура просматриваются поочередно;

  2. если для всех клеток контура переменная принимает прямое значение, то в имени контура на ее месте записывается 1;

  3. если для всех клеток контура переменная принимает инверсное значение, то в имени контура на ее месте записывается 0;

  4. если для одних клеток контура переменная принимает прямое значение , а для других инверсное , то переменная является независимой, и в имени контура на ее месте записывается крест Х;

  5. конъюнкция, соответствующая имени контура, записывается как произведение переменных, причем, если в имени контура на месте переменной стоит 1, то переменная записывается в прямом виде, а если на месте переменной стоит 0, то в конъюнкции на ее месте записывается инверсное значение переменной. Переменная, отмеченная как Х, из записи конъюнкции исключается.

Для КНФ алгоритм получения имен контуров следующий:

  1. все переменные для данного контура просматриваются поочередно;

  2. если для всех клеток контура переменная принимает прямое значение, то в имени контура на ее месте записывается 1;

  3. если для всех клеток контура переменная принимает инверсное значение, то в имени контура на ее месте записывается 0;

  4. если для одних клеток контура переменная принимает прямое значение, а для других инверсное, то переменная является независимой и в имени контура на ее месте записывается крест Х.

  5. дизъюнкция, соответствующая имени контура, записывается как сумма переменных, причем, если в имени контура на месте переменной стоит 1, то переменная записывается в инверсном виде, а если на месте переменной стоит 0, то на ее месте записывается прямое значение переменной. Переменная, отмеченная как Х, из записи дизъюнкции исключается.

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

Рис. 4.6. Покрытие контурами функций:

а – Z1; б – Z2
Функции Z1 и Z2 после минимизации имеют вид:

Карты для БФ трех аргументов имеют по восемь клеток (23). Они имеют вид, показанный на рис. 4.7. Внутри каждой клетки показаны наборы переменных, покрывающих эту клетку, и десятичные коды, соответствующие числовому эквиваленту набора аргументов.

Особенностью этих карт является то, что их можно сворачивать, как цилиндр, по широкой стороне (4 и более клеток). Это основано на том, что, левый и правый столбцы карты отмечены соседними конъюнкциями (рис. 4.8, а).


Рис. 4.7. Карты для трех переменных:

а – Вейча; б – Карно
Рассмотрим пример двух функций Y1=(0,2,6,7) и Y2=(0,2,3,6,7). Первая задана СДНФ и нанесена на карту Карно, а вторая СКНФ и нанесена на карту Вейча (рис. 4.8).


Рис. 4.8. Минимизация БФ:

а – Y1; б – Y2
БФ Y1 покрывается двумя контурами по две клетки в каждом, Y2 двумя контурами из четырех и двух клеток. Если записать эти БФ в СДНФ и СКНФ соответственно, то получатся следующие формулы:


После минимизации формулы этих БФ преобразуются:

Карты для БФ от четырех аргументов содержат 24=16 клеток. Карта Вейча изображена на рис. 4.9, а, карта Карно на рис. 4.9, б. Имена клеток карт нанесены в виде десятичных чисел, соответствующих наборам переменных.

Рис. 4.9. Карты для четырех переменных:

а – Вейча; б – Карно
Карты от четырех переменных можно сворачивать как по вертикали, так и по горизонтали. Причем, это можно делать одновременно, поэтому четыре угловые клетки карт образуют один контур из четырех клеток. Минимизируем булевы функции S1=(0,2,4,5,6,7,8,9,10) с помощью карты Карно и S2=(0,1,3,4,5,7,8,9,10,12,13) с помощью карты Вейча. После минимизации булевы функции будут иметь вид (рис. 4.10):


Рис. 4.10. Минимизация БФ:

а – S1 ; б – S2
На рис. 4.11 приведена карта Карно для пяти переменных.

Рис. 4.11. Разметка карты Карно для БФ от пяти аргументов
Сложность применения карт Карно и Вейча от пяти переменных заключается в том, что соседними являются столбцы, расположенные не только рядом, но и на расстоянии друг от друга. На рис. 4.11, например, это столбцы, отмеченные переменными х2х3х4 – 001 и 101, 011 и 111. Для карт от шести переменных появляются такие же соседние строки. Поэтому карты Карно и Вейча чаще применяются для минимизации БФ от 2, 3, и 4 переменных. А булевы функции от пяти и более переменных минимизируются другими способами.

На рис 4.12, рис 4.13 приведены примеры БФ, нанесенных на карты Вейча и Карно, и показан результат их минимизации:


  1. БФ Р1=(1,3,4,5,8,9,10,14,15) (L=15, C=20)





  1. БФ Р2=(1,2,8,10,13,14,15) (L=16, C=21)




3) БФ Р3=(1,3,6,7,10,11,12,14,15) (L=10, C=14)

4) БФ Р4=(0,3,5,6,9,13,14) (L=17, C=22)



  1. БФ Р5=(2,3,7,10,11,13) (L=9, C=12)





  1. БФ Р6=(0,1,4,5,6,10,12,13,14,15) (L=9, C=13)





  1. БФ Р7=(0,2,3,6,7) (L=3, C=4)





  1. БФ Р8=(0,2,4,5,6,7) (L=2, C=2)




  1. БФ F1=(2,8,9,13,15) (L=10, C=13)





  1. БФ F2=(0,2,3,4,5,6,7,10,11,12,14,15) (L=7, C=10)





  1. БФ F3=(1,5,6,8,9,10,14,15) (L=15, C=20)




  1. БФ F4=(0,6,7,8,10,12,13) (L=12, C=16)





  1. БФ F5=(0,5,6,7,9,10,11,14) (L=16, C=21)




  1. БФ F6=(0,1,3,4,5,7,8,12,13,15) (L=6, C=9)





  1. БФ F7=(1,2,4,5,6,7) (L=5, C=8)





  1. БФ F8=(2,3,4,5,6,7) (L=2, C=2)






Рис. 4.12. Примеры минимизации булевых функций с помощью карт Вейча:

  1. Р1; б – Р2; в – Р3; г – Р4; д – Р5; е – Р6; ж – Р7; з – Р8



Рис. 4.13. Примеры минимизации булевых функций с помощью карт Карно

  1. F1; б – F2; в – F3; г – F4; д – F5; е – F6; ж – F7; з – F8







перейти в каталог файлов

Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей

Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей