Булева алгебра, эквивалентные преобразования и стоимость реализации

Эквивалентные выражения совпадают на всех входах

Упрощая комбинационную схему, стремятся не только сократить запись. Нужно сохранить функцию и учитывать число логических уровней, fan-in, fan-out и реальные библиотечные ячейки. Сначала интерпретируйте $+$ и произведение в булевой алгебре^{iБулева алгебра оперирует значениями 0 и 1 и операциями AND, OR, NOT. Знак сложения здесь обычно означает OR, поэтому правила отличаются от сложения целых чисел.} как OR и AND.

Второе равенство проверяется разбором случаев: при $A=1$ обе стороны равны 1, при $A=0$ обе равны $B$. После применения заученного тождества вы должны уметь объяснить его смысл.

Чтение структур NAND и NOR через законы де Моргана

Например, $Y=AB+AC$ эквивалентно $A(B+C)$. Первое выражение можно нарисовать как два AND и один OR, второе — как один OR и один AND. Но при разном времени прихода входов или нагрузке меньшее число элементов не всегда означает более быструю схему.

Полезна и теорема консенсуса:

Если $BC=1$, то при $A=0$ уже равно 1 слагаемое $\overline A C$, а при $A=1$ — $AB$. Поэтому $BC$ избыточно для установившейся функции. Однако удаление этого члена может изменить свойства схемы во время переходов и появление опасных состязаний. Разберём это в лекции о задержках.

Каждый столбец ниже — одна комбинация ABC, а не шаг времени. Проверьте совпадение двух выходов во всех столбцах. Число элементов и пути могут различаться, но функция для устойчивых входов 0/1 одинакова.

Критерий проверки эквивалентности

Обозначьте исходный и преобразованный выходы y_ref и y_opt и для небольшого пространства входов сравните все комбинации. Успех одного-двух примеров не доказывает эквивалентность.

assign y_ref = (a & b) | (a & c);
assign y_opt = a & (b | c);
assign mismatch = y_ref ^ y_opt;

На всех восьми комбинациях 0/1 сигнал mismatch должен оставаться 0. Симуляция с четырьмя состояниями, включая X/Z, и проверка эквивалентности последовательностных схем требуют дополнительных условий. Явно указывать границы доказанного — базовый навык проектного ревью.