Комбинационные схемы: полусумматор

Урок строит из вентилей первую полезную схему — сумматор, складывающий двоичные числа.

Полусумматор — комбинационная схема, складывающая два одноразрядных двоичных числа и выдающая сумму и перенос.

Как процессор складывает числа? С помощью сумматоров — схем из вентилей. Полусумматор — первый шаг к арифметико-логическому устройству.

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

Складывая два бита $a$ и $b$, получаем два выхода: сумму $S$ (младший бит) и перенос $C$ (старший бит). По таблице истинности видно, что

$$ S = a \oplus b \;(\text{XOR}), \qquad C = a \cdot b \;(\text{AND}). $$

Например, $1 + 1 = 10_2$: сумма $S = 0$, перенос $C = 1$.

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

Полусумматор не учитывает перенос из младшего разряда. Полный сумматор имеет три входа ($a$, $b$, входной перенос $C_{in}$) и складывает их, выдавая сумму и выходной перенос. Соединяя полные сумматоры в цепочку, складывают многоразрядные числа — так устроены процессоры.

Сумматор в Python

def half_adder(a, b):
    s = a ^ b      # сумма (XOR)
    c = a & b      # перенос (AND)
    return s, c

def full_adder(a, b, cin):
    s1, c1 = half_adder(a, b)
    s, c2 = half_adder(s1, cin)
    return s, c1 | c2

print("Полусумматор:")
for a in (0,1):
    for b in (0,1):
        s, c = half_adder(a, b)
        print(f"  {a}+{b} -> сумма={s}, перенос={c}")

# Сложение 3-битных чисел 011 (3) и 101 (5)
A, B = [1,1,0], [1,0,1]   # младший бит первым
res, carry = [], 0
for i in range(3):
    s, carry = full_adder(A[i], B[i], carry)
    res.append(s)
res.append(carry)
print("3 + 5 =", int(''.join(str(b) for b in reversed(res)), 2))

Вывод:

Полусумматор:
  0+0 -> сумма=0, перенос=0
  0+1 -> сумма=1, перенос=0
  1+0 -> сумма=1, перенос=0
  1+1 -> сумма=0, перенос=1
3 + 5 = 8

Как работает под капотом

Сумматор — наглядный пример того, как из простой логики рождается арифметика. XOR даёт «сумму без переноса» (ведь $1+1$ в одном разряде даёт 0 с переносом), а AND ловит момент переноса. Полный сумматор склеивает два полусумматора и объединяет переносы через OR. Соединяя $n$ полных сумматоров в «гирлянду» (ripple-carry), процессор складывает $n$-битные числа: перенос «бежит» от младшего разряда к старшему, как при сложении столбиком. Именно поэтому в коде мы перебираем биты от младшего к старшему, передавая carry дальше. Реальные процессоры используют ускоренные схемы переноса, но идея та же — вся арифметика сводится к комбинациям XOR, AND и OR.

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

• Используют полусумматор для многоразрядного сложения, забывая про входной перенос.
• Путают порядок бит: в коде удобно хранить младший бит первым.
• Берут OR вместо XOR для суммы — тогда $1+1$ даст неверный результат.

Итог

• Полусумматор: $S = a \oplus b$, $C = a \cdot b$.
• Полный сумматор учитывает входной перенос.
• Цепочка сумматоров складывает многоразрядные числа.
• Так процессоры выполняют арифметику.