3.2. МНОГОСТУПЕНЧАТЫЕ РЕАЛИЗАЦИИ

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

Реализация этой функции двухступенчатой схемой при значительном числе нереальна, так как потребовалось бы вентилей И на . входов каждый и один вентиль ИЛИ на входов. Это следует из того, что среди наборов значений переменных всегда половина нечетных, и каноническая форма функции содержит минтермов. К тому же она не минимизируется, так как не содержит ни одной пары склеивающихся минтермов (на карте Карно отмеченные ячейки располагаются в шахматном порядке). В то же время данная функция реализуется многоступенчатой схемой, состоящей из двухвходовых вентилей исключающее ИЛИ, которые выполняют операцию сумма по модулю 2, причем для функции переменных таких вентилей требуется . Соответствующая схема при показана на рис. 3.3,а. Реализация в булевом базисе требует замены вентилей исключающее ИЛИ соответствующими булевыми эквивалентами — дизъюнктивными (рис. ) или конъюнктивными (рис. 3.3,в). В результате функция реализуется двухвходовыми вентилями И и ИЛИ совместно с вентилями НЕ, причем всего требуется логических вентилей и инверторов.

Рис. 3.3.

Рис. 3.4.

Рис. 3.5.

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

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

Любые ограничения на коэффициенты разветвления и нагружения можно удовлетворить заменой вентилей снедопустимо большим числом входов и выходов так называемыми древовидными схемами (рис. 3.5). Одна из таких схем уже использовалась выше для реализации функции проверки на четность. Вентиль на входов реализуется древовидной схемой, состоящей из () двухвходовых вентилей, причем число ступеней равно , т. е. наименьшему целому числу, большему или равному (рис. ). Аналогично вентиль с выходами реализуется древовидной схемой, которая содержит также ступеней, а каждый вентиль имеет один вход и два выхода (рис. ).