Анонический метод синтеза комбинационных схем.

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

Согласно каноническому методу синтез КС включает в себя ряд этапов.

1. Подлежащая реализации булева функция (или её отрицание) представляется в виде СДНФ.

2. С использованием методов минимизации определяется минимальная ДНФ (МДНФ) или минимальная КНФ (МКНФ). Из полученных двух минимальных форм выбирается более простая.

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

4. По представлению функции в заданном базисе строят комбинационную схему.

Необходимо отметить, что подлежащая реализации булева функция F(x₁,x₂,...,x_m) может быть задана не на всех возможных наборах аргументов x₁, x₂, ..., x_m. На тех наборах, где функция неопределенна, её доопределяют так, чтобы в результате минимизации получить более простую МДНФ или МКНФ. При этом упростится и сама КС. Кроме того, довольно часто с целью получения ещё более простого представления функции, МДНФ, полученная в п.2, представляется в так называемой скобочной форме, т.е. выносятся за скобки общие части импликант МДНФ (используется факторный алгоритм).

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

Как известно из курса машинной арифметики, полный одноразрядный сумматор - это устройство, которое осуществляет сложение по mod2 соответствующих разрядов (X1, X2) двоичных чисел с учётом переноса (Р_m) в данный разряд из соседнего младшего разряда суммы. Сумматор вырабатывает цифру результата (S) в данном разряде и перенос (Р_с) в соседний старший разряд суммы. Таблица истинности такого сумматора (т.е. представление булевой функции, которую он реализует, в виде СДНФ) представлена ниже.

X1
X2
Таблица истинности полного одноразрядного двоичного сумматора. Pm
S
Pc

Необходимо получить булевы функции S=F₁(X₁,X₂,Р_m) и Р_с=F₂(X₁,X₂,Р_m). Карты Карно для этих функций приведены ниже (рис.2).

S = X1X2Pm + X1X2Pm + X1X2Pm + X1X2Pm Pc = X1X2 + X1Pm + X2Pm

Как следует из приведённых карт, МДНФ соответствующих функций имеет вид:

Полученная система булевых функций представлена в базисе И, ИЛИ, НЕ. Соответствующая ей КС приведена на рисунке 4.

Полученную комбинационную схему можно упростить, вынеся за скобки общие части в выражениях для S и Р_c, однако существенного результата это не даст (желательно самостоятельно в этом убедиться).

Значительно упростить схему можно, если воспользоваться другим базисом, например логическим элементом "ИСКЛЮЧАЮЩЕЕ ИЛИ". В этом случае выражение для S можно записать S = (X₁+X₂+ Р_m)mod2= X₁Å X₂Å Р_m. Тогда схема для S будет иметь вид (рис.3). Однако это кажущееся упрощение, т.к. логический элемент "ИСКЛЮЧАЮЩЕЕ ИЛИ" является более сложным, чем элементы И, ИЛИ и НЕ.

Иногда для синтеза КС с несколькими выходами может использоваться следующий приём. Будем считать, что при

синтезе схемы сумматора функция S является функцией четырёх переменных: S=f(X₁,X₂,Р_m,Р_с). Таблица истинности для этого случая принимает вид изображенный в таблице 2.

X1

X2

Pm

Pc

S

X

X

X

X

X

X

X

X

Таблица 2. Таблица истинности сумматора

Неопределённые значения для S соответствуют наборам, которые никогда не могут быть в реальной схеме. Карта Карно для функции S=f(X₁,X₂,P_m,P_c) представлена на рис.5.

В результате минимизации, получается :

Сравнивая выражения (2) и (3), отмечаем, что функция S=f(X₁,X₂,P_m,P_c) проще, чем функция S=f₁(X₁,X₂,P_m). Схему, соответствующую (3), предлагается построить самостоятельно.

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