Рефераты. Основы цифровой техники






совпадает с числом различных наборов переменных – 2n.

СДНФ логической функции – это дизъюнкция минтермов, соответствующих

наборам входных переменных, для которых функция равна единице.

СКНФ логической функции – это конъюнкция макстермов, соответствующих

входным наборам, для которых функция равна нулю.

2. Алгоритм перехода от таблицы истинности

логической функции к ее записи в виде СДНФ

1. Выбрать в таблице такие наборы входных переменных, на которых

функция обращается в единицу;

2. Записать минтермы для выбранных наборов входных переменных. При

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

входной переменной в наборе – единичное, то она записывается в

прямой форме, если же значение переменной – нулевое, то – в

инверсной форме;

3. Полученные минтермы объединить между собой знаками дизъюнкции.

Пример 1. Получить СДНФ логической функции y = x1 ~ x2.

Решение. Из таблицы истинности (рис.1.) следует, что функция у=1 на

двух наборах входных переменных: (0 0) и (1 1). Для выбранных наборов

записываем минтермы в соответствии с п.2 приведенного выше алгоритма:

[pic], [pic].

Соединив минтермы знаком дизъюнкции, получим СДНФ функции:

[pic]

1.3 Алгоритм перехода от таблицы истинности

логической функции к ее записи в виде СКНФ

1. Выбрать в таблице истинности такие наборы входных переменных, на которых

функция принимает нулевые значения;

2. Записать макстермы для выбранных наборов. При этом следует

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

наборе нулевое, то она записывается в прямой форме, если значение

переменной единичное, то – в инверсной форме;

3. Полученные макстермы соединить знаками конъюнкции.

Пример 2. Получить СКНФ логической функции y = x1 ~ x2.

Решение. Из таблицы истинности (рис.1.), следует, что функция y=x1~x2=0

на двух наборах входных переменных (0 1) и (1 0). Для указанных наборов

записываем макстермы

[pic] и [pic].

Соединив их знаком конъюнкции, получим СКНФ функции:

[pic]

Нетрудно убедиться, что СДНФ и СКНФ функции эквивалентны.

1.4 Минимизация логических функций

Работа любого КЦУ с одним выходом может быть описана логическим

выражением или системой m логических выражений, если у КЦУ m выходов.

Другими словами, всякому КЦУ с одним выходом или каждому из m выходов

многовыходного КЦУ взаимно однозначно соответствует логическое выражение, в

котором буквы соответствуют входным переменным, а знаки операций – ЛЭ,

выполняющим эти операции. Подобные логические выражения именуют уравнениями

связи «вход-выход» КЦУ. В этих условиях упрощение схемы КЦУ сводится к

минимизации логических выражений, соответствующих этим устройствам.

СДНФ и СКНФ используются для первоначального представления логических

функций, но эти формы, как правило, неэкономичны для построения схем КЦУ.

Прежде чем строить схему, реализующую логическую функцию, ее необходимо

минимизировать, т.е. найти такую эквивалентную форму представления, при

которой выражение для функции будет состоять из наименьшего числа

переменных (букв).

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

используя постулаты и законы булевой алгебры.

Основными понятиями, которые вводятся на этапе минимизации логических

функций, являются понятия смежных минтермов и импликант, а основной

операцией упрощения является операция склеивания смежных минтермов.

Смежными принято называть минтермы, отличающиеся формой вхождения в них

лишь одной переменной (в один минтерм переменная входит в прямой форме, а в

другой – в инверсной). Например, смежными являются минтермы [pic] и [pic]

(различаются формой вхождения только переменной х1).

Два смежных минтерма СДНФ могут быть объединены по разнящемуся

аргументу, в результате чего происходит их замена одной конъюнкцией с

числом переменных на единицу меньшим, чем в исходных минтермах.

Например, [pic]

Операция объединения смежных минтермов по разнящейся переменной

именуется склеиванием.

Конъюнкция, получаемая в результате склеивания двух смежных минтермов,

называется импликантой. Импликанты с одинаковым числом переменных (рангом),

в свою очередь могут оказаться смежными, что позволяет производить их

склеивание между собой.

Процесс многоступенчатого склеивания приводит к получению импликант,

которые не имеют себе смежных. Такие импликанты называют простыми.

Процесс минимизации логических функций значительно упрощают карты

Карно. Карты Карно представляют собой прямоугольную таблицу (матрицу),

разбитую горизонтальными и вертикальными линиями на клетки (ячейки). Общее

число ячеек совпадает с числом минтермов и равно 2n, где n – число

переменных упрощаемой функции. Таким образом, каждая ячейка карты

соответствует определенному минтерму, размещение которых осуществляется

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

Соседними считаются ячейки, имеющие общие стороны, а также расположенные на

краях одних и тех же строк или столбцов карты.

Такой порядок размещения минтермов обеспечивается принятым способом

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

Все переменные разбиваются на две группы. Наборам переменных одной группы

ставят в соответствие столбцы, наборам другой группы – строки карты. Для

определенности крайний левый столбец и верхнюю строку карты обозначают

наборами с нулевыми значениями всех переменных (это условие не является

обязательным).

Для функции двух переменных карта Карно представляет собой таблицу,

разделенную на четыре ячейки, по одной на каждый входной набор (рис. 2, а).

Строки карты связаны с переменной [pic], столбцы – с переменной [pic].

Расположенная слева вверху ячейка соответствует входному набору (0 0) или

минтерму ([pic]), расположенная ниже ее ячейка соответствует входному

набору (1 0) или минтерму ([pic]) и т.д.

В случае функции трех переменных карта Карно (рис. 2, б) содержит

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

ячейки.

Поскольку для функции четырех переменных существует 16 входных наборов,

карта Карно разделена на 16 ячеек (рис. 2, в).

Наряду с изложенным применяют и другой способ маркировки размещения

минтермов: столбцы и строки карты Карно, соответствующие переменным в

прямой форме, охватывают скобками и возле них проставляют символы

переменных.

Аналогично поступают для переменных, представленных в инверсной форме.

Пример маркировки строк и столбцов карты Карно для функции трех и четырех

переменных приведен на рис. 3.

| | |[pic] |x2 |

| | | | |

|[pi| | | | | |

|c] | | | | | |

|х1 | | | | | |

| | | | | |

| | |[pic]|x3 |[pic]|

а)

| |[pic] |х3 | |

| | | | |

| | | | | | | |[pi|

|[pi| | | | | | |c] |

|c] | | | | | | | |

| | | | | | | | |

| | | |* | | | |х2 |

| | | | | | | | |

|х1 | | | | | | | |

| | | | | | | |[pi|

| | | | | | | |c] |

| | | | | |

| |[pic]|x4 |[pic]| |

б)

Рис. 3. Альтернативный способ маркировки строк и столбцов карты Карно для

функции трех (а) и четырех (б) переменных

Минтермы, соответствующие определенным ячейкам карты, образуются из

наборов групп переменных (рис. 2) или наборов переменных (рис. 3),

обозначающих строку и столбец, на пересечении которых расположена

рассматриваемая ячейка. Например, ячейке, выделенной на рис. 3,б

соответствует минтерм [pic].

1.5 Алгоритм минимизации логических функций, заданных

в СДНФ при помощи карт Карно

1. Обозначить ячейки карты, соответствующие минтермам упрощаемой

функции. Обозначение состоит в простановке (записи) единиц в

соответствующие ячейки карты. Остальные ячейки остаются не заполненными.

Для обозначения ячеек карты используют либо аналитическое выражение

упрощаемой функции, либо ее таблицу истинности.

2. 2К соседних обозначенных ячеек, расположенных по столбцу или по

строке, либо образующих прямоугольник или квадрат, объединить в контур

(блок).

При образовании блоков необходимо придерживаться следующих правил:

2.1. Одни и те же ячейки могут входить в несколько блоков;

2.2. Блоки должны покрывать все обозначенные ячейки;

2.3. Следует стремиться к тому, чтобы количество блоков было

минимальным, а сами блоки покрывали по возможности большее число ячеек.

3. Для каждого блока записать логическое выражение в виде конъюнкции

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

ячеек. Если блок покрывает 2, 4 или более ячеек, то конъюнкции представляют

собой импликанты склеиваемых минтермов. Ранг полученных таким образом

импликант меньше ранга минтермов, объединенных в контур, на К единиц.

4. Логические выражения для блоков объединить значками дизъюнкции.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.