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

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

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

На том же XOR построены коды, исправляющие ошибки. Бит чётности — XOR всех бит слова — замечает одиночную ошибку, но не показывает, где она. Код Хэмминга ставит несколько проверок чётности по перекрывающимся группам позиций: проверочный бит в позиции 1, 2, 4, 8, … охватывает все позиции, в двоичном номере которых есть этот разряд, и сработавшие проверки, прочитанные как двоичное число, дают номер ошибочного бита. Для 4 бит данных хватает 3 проверочных — код (7,4). Щёлкните по биту слова, чтобы внести ошибку и увидеть синдром; подробный разбор, SECDED и коды до (256,247) — в калькуляторе кода Хэмминга:

/* Hamming (7,4): D0 = bit 0 of data, code position 3
   (bits above D3 must be zero) */
#include <stdint.h>

static const uint32_t hamming_mask[3] = {
    0x0000000BUL,  /* p1: code position 1 */
    0x0000000DUL,  /* p2: code position 2 */
    0x0000000EUL,  /* p4: code position 4 */
};

/* Check bit p(2^i) in bit i. */
uint16_t hamming_check_bits(uint32_t data) {
    uint16_t check = 0;
    for (int i = 0; i < 3; i++)
        check |= (uint16_t)(__builtin_parityl(data & hamming_mask[i]) << i);
    return check;
}

/* Syndrome: the stored check bits XOR the recomputed ones; for a single error its
   low 3 bits are the code position of the bad bit. */

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

Функцию задают таблицей истинности: для 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-битное число, сдвиговый регистр — цепочка триггеров, где выход одного подан на вход следующего, — сдвигает данные на разряд за такт, счётчик — регистр с комбинационной схемой прибавления единицы на входе.