Синтез комбинационных схем

Синтез комбинационных схем можно проиллюстрировать решением простой задачи.

Задача 1

Приёмная комиссия в составе трех членов комиссии и одного председателя решает судьбу абитуриента большинством голосов. В случае равного распределения голосов большинство определяется той группой, в которой оказался председатель приемной комиссии. Построить автомат, обеспечивающий определение большинства голосов.

Решение

Пусть f - функция большинства голосов. f = 1, если большинство членов комиссии проголосовало за приём абитуриента, и f = 0 в противном случае.

Обозначим через x4 голос председателя комиссии. x4 = 1, если председатель комиссии проголосовал за приём абитуриента. x3, x2, x1 - голоса членов приёмной комиссии.

С учётом вышеуказанных допущений условие задачи можно однозначно представить в виде таблицы истинности.

Заполнение таблицы осуществляем с учётом того, что функция f является полностью определённой, т.е. она определена на всех возможных наборах переменных x1 - x4. Для n входных переменных существует N = 2n наборов переменных. В нашем примере N = 24 = 16 наборов.

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

x4 x3 x2 x1 f0 0 0 0 00 0 0 1 00 0 1 0 00 0 1 1 0 0 1 0 0 00 1 0 1 0 0 1 1 0 00 1 1 1 11 0 0 0 01 0 0 1 1 1 0 1 0 11 0 1 1 11 1 0 0 11 1 0 1 11 1 1 0 11 1 1 1 1

Примечание

Здесь и далее под набором будем понимать конъюнкцию всех входных переменных. Существует множество научных определений для набора(конституента,терм,импликанта,минтерм и т.д.),но они только вносят путаницу.

Все наборы, на которых функция принимает значение 1, будем называть единичными, или рабочими. Наборы, на которых функция принимает значение 0, будем называть нулевыми, или запрещенными.

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

Таким образом,

f = x4'x3x2x1 + x4x3'x2'x1 + x4x3'x2x1' + x4x3'x2x1 + x4x3x2'x1' + x4x3x2'x1 + + x4x3x2x1' + x4x3x2x1

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

Очевидно, применяя основные законы булевой алгебры, мы могли бы аналитически уменьшить сложность полученного выражения. Но это наихудший способ минимизации булевых функций. Покажем это на предыдущем примере. Представим полученную функцию в виде логической суммы цифровых рабочих наборов:

f = 0111+1001+1010+1011+1100+1101+1110+1111 = = (0111+1111)+(1001+1011)+(1010+1011)+(1100+1101)+(1110+1111) = = -111+10-1+101-+110-+111- = -111+10-1+(101-+111-)+(110-+111-) = = -111+10-1+1-1-+11- = x3x2x1+ x4x3'x1+ x4x2+ x4x3.

Как мы потом увидим, результат минимизации должен быть компактнее. Но при аналитической минимизации придётся ввести неочевидную группировку: (1101+1111).

f = 0111+1001+1010+1011+1100+1101+1110+1111 = =(0111+1111)+(1001+1011)+(1010+1011)+(1100+1101)+(1110+1111) + (1101+1111).= = -111+10-1+101-+110-+111-+11-1 = -111+(10-1+11-1)+(101-+111-)+(110-+111-) = = -111+1-1+1-1-+11- = x3x2x1+ x4x1+ x4x2+ x4x3 = x3x2x1+ x4 (x1+ x2+ x3).

После длинных и неочевидных группировок удалось, наконец, получить правильное решение. При числе аргументов более 4-х аналитический метод минимизации не рационален.