Цифровая логика: от вентилей до регистров

Логические элементы

Инвертор (НЕ) меняет 0 на 1 и обратно. Элементы И-НЕ и ИЛИ-НЕ универсальны: из одних двухвходовых И-НЕ можно собрать любую функцию. В КМОП-схемах каждый каскад по природе инвертирует, поэтому И-НЕ и ИЛИ-НЕ получаются одним каскадом, а И и ИЛИ — двумя. Важная тонкость: И-НЕ и ИЛИ-НЕ не ассоциативны — трёхвходовый И-НЕ нельзя получить, соединив два двухвходовых каскадом, как это делают с И. Исключающее ИЛИ нужно в сумматорах и при расчёте чётности и контрольных сумм, например CRC.

Таблица истинности и формула

Функцию задают таблицей истинности: для N входов в ней 2^N строк, по одной на каждую комбинацию. По таблице всегда можно записать формулу в виде суммы произведений (дизъюнктивной нормальной формы, СДНФ): для каждой строки, где выход равен 1, пишут произведение всех переменных — прямых, если в строке 1, и инверсных, если 0, — и объединяют эти произведения через ИЛИ. Двойственная форма — произведение сумм (СКНФ) — строится по строкам, где выход равен 0. Сумма произведений сразу превращается в схему: инверторы, вентили И на каждое произведение и вентиль ИЛИ на выходе.

Калькулятор строит таблицу по выражению или вектору значений, записывает СДНФ и СКНФ и находит минимальные формы:

Минимизация и карта Карно

Совершенная форма обычно избыточна: два произведения, которые отличаются значением одной переменной, сливаются в одно без неё — A · B + A · ¬B = A. Найти такие пары проще, если переставить строки таблицы так, чтобы соседние отличались ровно одним битом. Это и делает карта Карно: таблица истинности записывается двумерной таблицей, строки и столбцы нумеруются кодом Грея (00, 01, 11, 10), а крайние столбцы и строки считаются соседними — карту надо представлять свёрнутой в цилиндр (для 4 переменных — в тор).

Единицы обводят прямоугольными группами по 1, 2, 4, 8 клеток; каждая группа — одно произведение, из которого выпадают переменные, меняющиеся внутри группы. Чем больше группа, тем короче произведение. Комбинации входов, которые никогда не встречаются, помечают как безразличные (x) и включают в группы, если это их увеличивает.

Мультиплексор

Мультиплексор (MUX) выбирает один из входов по сигналу выбора: при S = 0 на выход идёт вход D0, при S = 1 — D1. Его формула — Y = ¬S · D0 + S · D1. Мультиплексор тоже универсален: на нём можно собрать инвертор, И и ИЛИ, а значит, и любую функцию.

Память: защёлка и триггер

Если выход мультиплексора завести обратно на его вход D0, получится элемент памяти — D-защёлка. Пока управляющий вход G равен 1, выход повторяет вход D (защёлка «прозрачна»); когда G становится 0, выход сохраняет последнее значение. Чтобы значение запомнилось надёжно, вход D должен быть стабильным некоторое время до спада G — это время установки (setup time) — и некоторое время после него — время удержания (hold time).

Две защёлки, включённые друг за другом и управляемые противофазными сигналами, образуют D-регистр, или D-триггер. Он записывает вход только в момент фронта тактового сигнала — нарастающего, перехода из 0 в 1 — и хранит значение до следующего фронта; между фронтами изменения входа на выход не проходят. На таких регистрах и строится синхронная логика: между регистрами стоит комбинационная схема, и такт должен быть длиннее её задержки с учётом времени установки.

Из регистров собирают остальные узлы: регистр из N триггеров с общим тактом хранит N-битное число, сдвиговый регистр — цепочка триггеров, где выход одного подан на вход следующего, — сдвигает данные на разряд за такт, счётчик — регистр с комбинационной схемой прибавления единицы на входе.