Сумматор и триггеры

Урок о том, как из нескольких вентилей собирается арифметика и память — то есть две главные способности любого компьютера.

Сумматор — логическая схема, складывающая двоичные числа; триггер — схема, способная устойчиво хранить один бит, то есть простейшая ячейка памяти.

До сих пор вентили только вычисляли значение функции «здесь и сейчас». Но компьютер должен уметь две вещи: считать и запоминать. Удивительно, но и то и другое получается из тех же самых И, ИЛИ, НЕ, XOR. Сложение собирается из сумматора, а память — из триггера. Сложение двоичных чисел и работа разрядов — постоянная тема экзаменационных задач, поэтому разберём всё на реальных битах.

Зачем это нужно

Когда процессор складывает два числа, он не делает ничего «магического» — внутри работает цепочка сумматоров, по одному на каждый разряд. А когда программа хранит переменную, каждый её бит сидит в отдельном триггере. Понять эти две схемы — значит увидеть, как из голой логики рождается настоящий компьютер: арифметико-логическое устройство и регистры.

Сложение в столбик, но в двоичной системе

Вспомним сложение битов. Есть всего четыре случая:

$$ 0+0=0, \quad 0+1=1, \quad 1+0=1, \quad 1+1=10_2 $$

Последний случай ключевой: $1+1$ в двоичной системе даёт $10_2$ — то есть 0 в текущем разряде и 1 переноса в старший разряд (как $9+1=10$ в десятичной). Значит, для сложения двух битов нам нужно вычислить две величины: бит результата (sum) и бит переноса (carry). Сравните таблицу сложения с таблицами вентилей из первого урока:

Присмотритесь: столбец «Сумма» — это в точности таблица XOR, а столбец «Перенос» — таблица И! Отсюда формулы:

$$ S = A \oplus B, \qquad C = A \land B $$

Полусумматор

Схема из одного XOR и одного И, реализующая эти две формулы, называется полусумматором (half adder). Он складывает два бита и выдаёт сумму и перенос:

A ---+---[ XOR ]--- S  (сумма)
     |              
B ---+---[ AND ]--- C  (перенос)

Почему «полу»? Потому что он не умеет принимать перенос из предыдущего разряда. А при сложении многоразрядных чисел перенос обязательно приходит справа. Поэтому нужен старший брат.

Полный сумматор

Полный сумматор (full adder) складывает уже три бита: два слагаемых $A$, $B$ и входной перенос $C_{in}$ из младшего разряда. Он выдаёт сумму $S$ и исходящий перенос $C_{out}$. Формулы:

$$ S = A \oplus B \oplus C_{in} $$

$$ C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B)) $$

Идея простая: сумма равна 1, если среди трёх входных битов нечётное число единиц (за это отвечает двойной XOR), а перенос возникает, если единиц хотя бы две. Полный сумматор собирается из двух полусумматоров и одного вентиля ИЛИ. Его таблица истинности:

Проверим обе формулы программой и заодно сложим как пример числа $A=3$ и $B=1$ поразрядно через полный сумматор:

def full_adder(a, b, cin):
    s = a ^ b ^ cin                       # сумма по модулю 2
    cout = (a and b) or (cin and (a ^ b)) # перенос
    return s, int(bool(cout))

print("A B Cin | S Cout")
for a in (0, 1):
    for b in (0, 1):
        for cin in (0, 1):
            s, cout = full_adder(a, b, cin)
            print(a, b, cin, "  |", s, cout)

# Сложим 3 (011) и 1 (001) по разрядам, справа налево
A, B = [0, 1, 1], [0, 0, 1]   # старший -> младший
carry, result = 0, []
for i in range(2, -1, -1):
    s, carry = full_adder(A[i], B[i], carry)
    result.insert(0, s)
print("3 + 1 =", "".join(map(str, result)), "(двоичное) =", int("".join(map(str, result)), 2))

Вывод:

A B Cin | S Cout
0 0 0   | 0 0
0 0 1   | 1 0
0 1 0   | 1 0
0 1 1   | 0 1
1 0 0   | 1 0
1 0 1   | 0 1
1 1 0   | 0 1
1 1 1   | 1 1
3 + 1 = 100 (двоичное) = 4

Цепочка из нескольких полных сумматоров, где $C_{out}$ каждого заводится в $C_{in}$ следующего, складывает уже многоразрядные числа. Так устроен многоразрядный сумматор внутри процессора.

Триггер: как логика начинает помнить

Сумматор всё считает заново при каждом наборе входов — он ничего не хранит. Память появляется из неожиданного приёма: обратной связи. Если выход вентиля завести обратно на его же вход, схема может «зациклиться» в устойчивом состоянии и удерживать его — то есть запомнить бит.

Простейший RS-триггер собирается из двух вентилей NOR (или NAND), у которых выходы перекрёстно заведены на входы друг друга. У него два управляющих входа: S (set — установить в 1) и R (reset — сбросить в 0). Поведение:

Самое важное — строка $S=0, R=0$: триггер ничего не меняет и держит ранее записанный бит. Это и есть хранение информации. Один триггер хранит 1 бит; восемь триггеров — байт; миллиарды триггеров складываются в регистры и кэш процессора.

Как это работает

За счёт перекрёстной обратной связи выход каждого NOR-вентиля «подпитывает» вход другого, и схема залипает в одном из двух устойчивых состояний: $Q=1$ или $Q=0$. Чтобы переключить его, нужно коротко подать сигнал на S или R. Пока оба входа в нуле, состояние держится сколько угодно — пока есть питание. Поэтому триггеры называют энергозависимой памятью: выключили ток — информация пропала (так теряется содержимое оперативной памяти при выключении). На триггерах строят регистры процессора и быстрый кэш; именно их скорость делает регистры самой быстрой памятью в компьютере.

Частые ошибки

• Забывают про перенос. $1+1=10_2$, а не 1. Сумма даёт 0 в разряде и 1 переноса — иначе сложение многоразрядных чисел развалится.
• Путают полусумматор и полный сумматор. Полусумматор складывает 2 бита, полный — 3 (учитывает входной перенос). Для многоразрядного сложения годится только полный.
• Считают, что сумма — это ИЛИ. Бит суммы даёт XOR, а не OR: при $1+1$ ИЛИ выдало бы 1, а правильная сумма в разряде — 0.
• Думают, что триггер хранит данные без питания. RS-триггер — энергозависимая память: при отключении тока состояние теряется.

Итоги

• Сложение битов раскладывается на сумму $S = A \oplus B$ (XOR) и перенос $C = A \land B$ (И) — это полусумматор.
• Полный сумматор складывает три бита (учитывает входной перенос): $S = A \oplus B \oplus C_{in}$, и собирается из двух полусумматоров и ИЛИ.
• Цепочка полных сумматоров складывает многоразрядные числа, передавая перенос из разряда в разряд.
• RS-триггер на перекрёстных NOR хранит 1 бит за счёт обратной связи; это энергозависимая память — основа регистров.