Тема 3.2. Синтез комбинационных устройств. Основные методы минимизации логических функций

3.2.1. Синтез комбинационных устройств

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

Синтез комбинационного устройства подразделяется на 4 этапа:

1) составление таблицы истинности синтезируемого КУ согласно его определению, назначению и описанию принципов работы;

2) составление математических формул для логических функций, описывающих работу синтезируемого КУ согласно таблице истинности;

3) анализ полученных функций с целью построения различных вариантов ее математического выражения (на основании законов алгебры логики) и нахождение наилучших из них в соответствии с тем или иным критерием;

4) составление функциональной (логической) схемы КУ из элементов НЕ, И, ИЛИ.

Рассмотрим синтез КУ на примере синтеза полусумматора, имеющего 2 входа (слагаемые x₁ и x₂) и 2 выхода (цифры суммы S и переноса P).

1-й этап. Составим таблицу истинности КУ (таблица 3.3).

Таблица 3.3. Таблица истинности комбинационного устройства

1-я цифра – слагаемое x1	0	0	1	1
2-я цифра – слагаемое x2	0	1	0	1
Цифра переноса P	0	0	0	1
Цифра суммы S	0	1	1	0

2-й этап

Методика перехода от таблицы истинности к аналитическому выражению подробно изложена в [9]. Приведем только конечную форму и правила записи аналитического выражения функции на основании таблицы истинности.

Аналитическое выражение функции записывается в одной из двух форм:

а) совершенной дизъюнктивной нормальной форме (СДНФ)

(3.1)

где x_i (x₁, x₂...x_n) – двоичные переменные (входные аргументы),

j–номер набора аргументов в таблице истинности,

[x_i]_j – индекс, определяющий, что значения переменной x_i берутся из таблицы истинности для j-набора;

б) совершенной конъюнктивной нормальной форме (СКНФ)

(3.2)

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

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

Напомним правила получения аналитической записи логической функции для некоторого КУ [9].

Правило 1

Для того чтобы получить аналитическое выражение функции, заданной таблично, в СДНФ, необходимо составить сумму (V) конституент единицы для всех наборов входных двоичных переменных, для которых реализация функции f_j = 1, причем символ любой переменной в некоторой конституенте берется со знаком отрицания, если конкретное значение переменной [x_i]_j в рассматриваемом наборе равно 0.

Применив это правило для функций P и S полусумматора, на основании таблицы 3.3 получим:

;(3.3а)

.

Правило 2

Для того чтобы получить аналитическое выражение функции, заданной таблично, в СКНФ, необходимо составить произведение (конъюнкцию) конституент нуля для всех наборов входных двоичных переменных, для которых реализация функции f_j = 0, причем символ любой переменной в некоторой конституенте берется со знаком отрицания, если ее конкретное значение [x_i]_j в рассматриваемом наборе равно 1.

Применив это правило для функций P и S полусумматора, на основании таблицы 3.3, получим:

(3.3 б)

Формы представления функций СДНФ и СКНФ являются каноническими. К ним можно перейти не только от табличной, но и от произвольной аналитической записи функции.

В общем случае переход от произвольной формы к СДНФ или СКНФ производится в 3 шага:

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

2. С помощью распределительных законов производится переход к одной из нормальных форм:

– для перехода к СДНФ – применяется закон 1-го рода;

– для перехода к КНФ – закон 2-го рода.

3. Производится преобразование членов ДНФ или КНФ в соответствующие конституенты при помощи правила развертывания.

Пример 3.1

Преобразовать функцию , заданную в некоторой произвольной форме, в СДНФ и СКНФ.

Решение:

1-шаг – применяя к исходной функции правило инверсии, снимаем общие и групповые отрицания

2-шаг – применяя распределительные законы, приводим функцию к ДНФ и КНФ.

а)

б)

3-шаг – применяя правила развертывания, преобразуем функцию в СДНФ и СКНФ

а)

б)

3–й этап

Анализ и оптимизация (минимизация) логических функций являются важнейшими в синтезе КУ. Поэтому эти вопросы будут рассмотрены отдельно (см. подраздел 3.2.2.).

4-й этап

Построение схемы основано на прямом замещении элементарных произведений, сумм и отрицаний соответственно конъюнкторами (&), дизъюнкторами (1) и инверторами (1).

На рисунках 3.2 и 3.3 приведены функциональные схемы полусумматора, реализующие функции P и S, представленные в СДНФ и СКНФ соответственно.

Рисунок 3.2.

Рисунок 3.3.