15 / 63 · Теория

От таблицы истинности к MUX и разложению Шеннона

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

Вывод правила выбора

Чтобы при sel=0 выдавать a, а при sel=1 — b, умножьте каждый вход на условие выбора и объедините через OR.

y=\overline s a+s b

Подстановка $s=0$ оставляет только a, $s=1$ — только b. Если a и b одинаковы, изменение sel не влияет на выход. Поэтому для обнаружения ошибки выбора обязательно нужны разные данные.

Синий путь соответствует выбранному входу. Задайте разные a и b и меняйте sel. При одинаковых данных даже неверно подключённый селектор трудно распознать по выходу.

Тракт данных, изменяемый сигналом выбора

y = sel ? b : a

MUX — общий способ разложения логической функции

Обозначим через $F_0,F_1$ функции, полученные из произвольной булевой F фиксацией s в 0 и 1.

F=\overline s F_0+sF_1

Это разложение Шеннона. Любую функцию можно разделить на две части как s ? F1 : F0. Например, для $F=a\oplus b$ при селекторе a получаем $F_0=b$ , $F_1=\overline b$ , поэтому XOR строится из MUX^{Мультиплексор — комбинационная схема, соединяющая один из нескольких входов с выходом по сигналу выбора. Соответствие битов выбора и номеров входов должно быть задано явно.} и инверсии^{Инверсия — операция NOT, меняющая 0 на 1 и 1 на 0. Черта над формулой означает применение NOT ко всему выражению под ней. Подробнее}.

Выбор 4-to-1 и приоритет

Выбор одного из четырёх входов двумя битами можно построить в два уровня MUX 2-to-1. А if (req0) ... else if (req1) ... отдаёт приоритет более раннему запросу при нескольких единицах. Адресный выбор и приоритетный выбор — разные задачи.

SystemVerilog
assign y = sel[1] ? (sel[0] ? d3 : d2)
                 : (sel[0] ? d1 : d0);

В идеальном сбалансированном дереве для $2^m$ входов путь содержит m уровней. Физическая задержка зависит также от прихода входов, нагрузки и проводников. Разложение функций создаёт варианты реализации, но не доказывает оптимальность задержки.

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

Представьте $F=a b+\overline a c$ как MUX с селектором a. Каковы два входа данных?

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

При $a=0$ получается $F_0=c$ , при $a=1$ — $F_1=b$ , поэтому assign f = a ? b : c;. Сначала вычисляйте кофакторы, чтобы не перепутать входы для выбора 0 и 1.