Синтез комбинационной схемы: пример по таблице

Синтез комбинационной схемы - это переход от описания нужного поведения к соединению логических элементов, которое это поведение реализует. В отличие от простого чтения готовой формулы, здесь сначала нужно решить, какими должны быть выходы для каждого набора входов, а затем выбрать удобную реализацию. Разберём весь путь на двухвходовом мультиплексоре: он передаёт на выход один из двух сигналов по команде третьего. В интерактиве можно перебрать все восемь наборов и сверить результат с таблицей ниже.
От условия к модели
Комбинационная схема после завершения переходных процессов выдаёт результат, определяемый текущими входами. Она не хранит предыдущий набор как состояние. Реальные элементы имеют задержку, поэтому непосредственно во время переключения выход может ещё не соответствовать новому набору. Это отличие абстрактной функции от физической схемы важно при проверке устройства.
Пусть и - данные, - управляющий вход, а - выход. Задание таково: при передавать , при передавать . Все переменные принимают только 0 или 1. Значения данных могут совпадать: тогда переключение выбора не должно менять установившийся выход.
Золотая точка в ролике связывает выбранный вход с результатом. Это иллюстрация логического выбора, а не измерение скорости сигнала. В реальном устройстве задержку надо брать из характеристик конкретных элементов.
Таблица истинности из технического задания
Для трёх входов существует наборов. Перечислим их в порядке : сначала все варианты при , затем при . Для первой половины копируем , для второй - .
| Почему | ||||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | выбран |
| 0 | 0 | 1 | 0 | выбран |
| 0 | 1 | 0 | 1 | выбран |
| 0 | 1 | 1 | 1 | выбран |
| 1 | 0 | 0 | 0 | выбран |
| 1 | 0 | 1 | 1 | выбран |
| 1 | 1 | 0 | 0 | выбран |
| 1 | 1 | 1 | 1 | выбран |
Полная таблица - главный договор между условием и схемой: она фиксирует результат даже для комбинаций, которые легко забыть при словесном описании. В учебных материалах MIT по синтезу логики этот переход тоже начинается с функционального задания и таблицы истинности.
Перед заполнением таблицы полезно определить полярность каждого сигнала: означает ли единица разрешение действия или, наоборот, запрет. Не менее важно уточнить, какие входные комбинации возможны на практике и какое значение требуется в каждой из них. Например, слова «выбрать первый вход» ещё не сообщают, при каком уровне управляющего сигнала это происходит. В нашем условии этот выбор явно привязан к нулю.
Если в задании указано несколько выходов, их удобно разместить отдельными столбцами. Для каждого вывода строят свою функцию, а позже ищут общие промежуточные выражения: совместное использование элемента иногда уменьшает общую схему.
Записываем СДНФ по единичным строкам
В таблице четыре единицы: , , и . Для каждой строки составим конъюнкцию всех трёх переменных: при нуле переменная входит с отрицанием, при единице - без него. Затем объединим строки операцией ИЛИ:
Первое слагаемое истинно только на наборе , второе - только на и так далее. Поэтому сумма четырёх слагаемых точно воспроизводит единичные строки, а на остальных равна нулю. Эта запись называется совершенной дизъюнктивной нормальной формой, или СДНФ. Подробно её построение разобрано в статье про СДНФ.
Обратите внимание на порядок действий: сначала отрицание отдельной переменной, затем И внутри слагаемого и только после этого ИЛИ между слагаемыми. Каждая строка таблицы соответствует одному минтерму. Если единичных строк нет, выход просто равен константе 0; если единицы стоят во всех строках, его можно заменить константой 1. Это помогает не усложнять схему, когда функция вырождается.
СДНФ даёт систематический способ получить верную формулу, но не обещает самой экономной схемы. В ней повторяются переменные и их отрицания; прежде чем выбирать микросхемы, полезно проверить, какие условия можно объединить.
Минимизация: две группы вместо четырёх строк
Сгруппируем первую пару слагаемых и вторую. В первой паре меняется только , во второй - только :
Равенства и убирают лишние переменные. Смысл результата прозрачен: первая ветвь разрешена, когда , вторая - когда . Это та же функция, с которой мы начали, но теперь она выражена через стандартные логические операции.

На карте Карно столбцы идут в порядке : соседние столбцы отличаются одним битом. Две единицы в верхней строке объединяются в ; две в нижней - в . Клетка может входить в несколько групп, а крайние столбцы карты тоже соседние. Группы содержат клеток, и их выбирают так, чтобы покрыть все единицы, не захватывая обязательные нули. Принцип карты и её связь с таблицей объяснены в материалах MIT.
Выбираем базис и строим соединения
В базисе И, ИЛИ, НЕ для нужны один инвертор, два двухвходовых элемента И и один двухвходовый ИЛИ. Подайте на инвертор; соедините и с первым И, а и - со вторым. Выходы двух элементов И подайте на ИЛИ. Всего в такой реализации четыре логических элемента; число входов и доступность инверсного сигнала в других условиях могут изменить оценку.
Можно использовать только двухвходовые И-НЕ, то есть NAND. Сначала получим . Затем вычислим и . Последний элемент даст . По закону де Моргана он инвертирует произведение отрицаний двух ветвей и тем самым выполняет нужное ИЛИ. Здесь тоже четыре элемента NAND. От формулы к проводам помогает перейти отдельный разбор построения схемы по выражению.
Четыре элемента - результат именно выбранного разложения и указанного базиса, а не универсальная цена любого устройства выбора. В библиотеке может быть готовый мультиплексор; при ограничениях по задержке, нагрузке или питанию выгодной окажется другая реализация. Сравнивать варианты следует по заданному критерию, а не только по длине формулы.
Как проверить синтез и учесть реальные ограничения
Сначала проверим крайние положения выбора подстановкой. При формула даёт , поскольку вторая ветвь равна нулю; при остаётся . Это охватывает все восемь наборов. Дополнительно можно пройти по таблице и сравнить значения обеих записей и выход схемы; интерактив выделяет выбранную строку. В задачах на другие функции удобна независимая проверка каждого набора, а не только нескольких примеров.
Эквивалентность двух функций можно проверить ещё одним способом: построить для них общий столбец сравнения и убедиться, что на каждом наборе результаты одинаковы. Принцип такого сравнения разобран в материале про эквивалентность и таблицу истинности. Для трёх входов полный перебор занимает восемь строк; при большом числе входов применяют автоматизированную проверку, поскольку число наборов растёт как . Проверять только наборы с единичным выходом недостаточно: ошибочная схема может выдать единицу и там, где требуется ноль.
Неопределённые значения, обозначаемые , допустимо использовать при упрощении только тогда, когда задание действительно допускает любой выход на соответствующем наборе. Они не означают автоматически «сигнал равен нулю» и не заменяют забытые строки. Если аппаратно такой набор всё же возможен, надо удостовериться, что любое получившееся значение безопасно для последующих узлов.
Наконец, логическая эквивалентность относится к установившимся значениям. При изменении входов задержки разных путей могут вызвать короткий ложный импульс. Например, при идеальный выход постоянен, но переключение в схеме из двух ветвей способно на мгновение погасить обе. Метод и пример такого риска описаны в курсе Computation Structures. Если импульсы критичны, анализируют задержки и применяют подходящее схемное или временное решение.
Для сравнения с другой функцией трёх входов полезна мажоритарная функция: она выдаёт единицу по числу единиц на входах, тогда как мультиплексор выбирает значение одного входа управляющим сигналом. Оба задания можно синтезировать одним и тем же маршрутом через таблицу.
Частые ошибки
- Меняют порядок переменных при переходе от таблицы к формуле. Записывайте порядок рядом с каждым набором.
- Группируют на карте Карно клетки с разницей в двух битах или захватывают обязательный ноль. Проверяйте соседство и размер каждой группы.
- Принимают неопределённую строку за единицу без основания в условии. Отмечайте её только при явно допустимом произвольном результате.
- Считают совпадение формул доказательством отсутствия импульсов. Установившаяся функция и временное поведение требуют отдельных проверок.
FAQ
Чем синтез отличается от анализа схемы?
При анализе известны элементы и соединения, а требуется найти функцию. При синтезе известна требуемая функция или словесное условие, а соединения предстоит выбрать и затем проверить анализом.
Всегда ли нужна карта Карно?
Нет. Небольшую функцию можно сократить алгебраически, как в примере; для более крупных используют алгоритмы и средства автоматического синтеза. Карта удобна, когда все клетки ещё легко обозреть.
Является ли комбинационной схема с задержками?
Да. Задержки сами по себе не создают логической памяти: после стабилизации входов её выход определяется текущим набором. Для конкретного устройства при этом необходимо соблюдать временные ограничения.
Коротко
Синтез начинают с входов, выходов и полной таблицы истинности. Затем получают функцию, упрощают её, выбирают доступный базис и проверяют каждую строку. В примере мультиплексора четыре единичных набора сводятся к ; физическая проверка дополнительно учитывает задержки и возможные переходные импульсы.
Читайте также

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

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

Дешифратор и шифратор: таблицы и примеры
Дешифратор и шифратор в цифровых схемах: таблицы истинности 2 на 4 и 4 на 2, логические формулы, примеры выбора линии, приоритет входов и активные уровни сигналов.

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

КМОП-инвертор: схема, работа и задержка
Как работает КМОП-инвертор на p-МОП и n-МОП транзисторах: таблица истинности, передаточная характеристика, задержка и энергия переключения на примере RC-модели.

Логические элементы И, ИЛИ, НЕ: таблица истинности
Как работают логические элементы И, ИЛИ и НЕ: таблицы истинности, обозначения, примеры расчёта схем и типичные ошибки при работе с двоичными сигналами.