9 / 63 · Теория

Карты Карно и условия don’t-care

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

От таблицы истинности к стоимости реализации

Таблица истинности^{Таблица истинности перечисляет все возможные комбинации входов и выход для каждой из них. Изменения во времени проверяют отдельно по временным диаграммам. Подробнее} определяет функцию, а минимизация выбирает выражение для её реализации. Для трёх входов номер минтерма зададим двоичным ABC со старшим битом A.

F(A,B,C)=\Sigma m(1,3,4,5,7)

Например, минтерм 4 — ABC=100. В неперечисленных строках 0, 2, 6 выход равен 0. Вместо пяти отдельных произведений можно объединить члены, различающиеся ровно одним битом.

Карта Карно — таблица истинности в другом порядке

Расположим столбцы BC в порядке 00, 01, 11, 10. Это порядок кода Грея: соседние столбцы различаются одним битом. Крайний левый и крайний правый столбцы тоже соседние.

A / BC	00	01	11	10
0	0	1	1	0
1	1	1	1	0

Группы должны быть прямоугольными и содержать $1,2,4,8,\ldots$ ячеек. Включение нулевой ячейки изменяет функцию. Одну единицу разрешено включать в несколько групп.

Объединение четырёх ячеек двух столбцов C=1 показывает: выход равен 1 независимо от A и B. Остаётся член C.
При объединении BC=00 и 01 в строке A=1 меняется только C. Остаётся $A\overline B$ .
OR двух групп покрывает все единицы и не затрагивает ни одного нуля.

F=C+A\overline B

Сравните исходное определение и минимизированное выражение на восьми входах. Важно отдельно проверять сокращение записи и сохранение функции.

Следующая схема переводит две группы карты в выражение. В группе C меняются A и B, в паре ячеек — C, поэтому именно эти переменные удаляются из соответствующих членов.

Переменные, исчезающие в группе

m1,3,5,7: C=1 при изменении A и B
m4,5: При A=1, B=0 изменяется только C
Сумма двух групп: F = C + A · NOT B

Don’t-care — разрешение на оптимизацию и предположение о входах

Предположим, системный контракт исключает ABC=000. Пометив эту ячейку X, можно использовать её как 0 или 1. Объединение четырёх ячеек B=0 даёт более простое выражение:

F_{\mathrm{dc}}=C+\overline B

Новое выражение выдаёт 1 при ABC=000 и отличается от исходной полной таблицы. Поэтому утверждение об «эквивалентной схеме» должно включать условие, что вход не равен 000. Если 000 может появиться при инициализации или восстановлении после ошибки, оптимизация способна нарушить системные требования.

Минимизация выражения не равна минимизации кристалла

Меньшее число литералов не гарантирует оптимальные площадь, задержку и мощность в конкретной библиотеке стандартных ячеек. Влияют нагрузка, fan-out, доступные составные элементы, проводники и выбросы. Здесь устанавливаем функциональную эквивалентность и предположения о входах; физическую стоимость оцениваем по результатам синтеза и анализа временных ограничений.

Дополнительное чтение: MIT OpenCourseWare — Combinational Logic

Практикум · перекрывающиеся группы и условия don’t-care

От C и A·NOT B к более крупным группам

F = C + A · ¬B

Таблица истинности трёх входов · X — выход, не заданный контрактом
ABC	F
000	0
001	1
010	0
011	1
100	1
101	1
110	0
111	1

Выберите группу C. В четырёх ячейках меняются и A, и B, поэтому остаётся только C.
Выберите A·¬B. Она покрывает m4 и m5; m5 пересекается с группой C. Перекрытие допустимо, включение нулевой ячейки — нет.
Дважды нажмите m0: 0 → 1 → X. Теперь спецификация неполная, с d(0). Группа B=0 расширяется, и выражение становится $C+\overline B$ .
Нажмите m0 ещё раз, вернув 0. Исходное требование восстановлено, и расширенная группа должна исчезнуть.

Выбор группы не меняет значения. Полное выражение, покрывающее все единицы, сохраняется; рамка выделяет только рассматриваемый сейчас член. «Минимум» означает сначала минимум произведений, затем литералов; при нескольких решениях показывается одно.

Попробуйте сами

Вы заменили m0 на X и реализовали F=C+NOT B. Добавлено требование: при сбросе возможен ABC=000, и тогда F должна быть 0. Можно ли сохранить оптимизацию?

Прочитать объяснение

Нет. Новое требование снова задаёт m0=0. Оптимизированное выражение выдаёт 1 при 000 и нарушает его. Нужно вернуться к выражению, удовлетворяющему всем заданным строкам, например исходному C+A·NOT B.