Сумматоры: от полусумматора к каскаду
Урок строит арифметику с нуля: от сложения двух бит до сложения целых чисел через каскад сумматоров.
Полный сумматор — схема, складывающая три бита (два слагаемых и входной перенос) и дающая бит суммы и бит переноса. Из цепочки полных сумматоров строится сложение многоразрядных чисел.
Зачем разбирать сложение по битам
Сложение — самая частая операция процессора (адреса, счётчики, циклы — всё это сложение). Понять, как из логических вентилей рождается арифметика, — значит увидеть мост между булевой логикой и числами. И этот мост на удивление прост: всё начинается с одного XOR.
Полусумматор: складываем два бита
Сложим биты a и b. Возможны суммы 0, 1, 2. «2» не влезает в один бит, поэтому нужен перенос. Бит суммы = a XOR b (1, если ровно один из них 1). Перенос = a AND b (1, только если оба 1).
ПОЛУСУММАТОР a b | carry sum -----+---------- 0 0 | 0 0 0 1 | 0 1 1 0 | 0 1 1 1 | 1 0 <- 1+1 = 10 (два): sum=0, перенос=1 sum = a XOR b carry = a AND b
Полный сумматор: добавляем входной перенос
При сложении многоразрядных чисел в каждый разряд приходит перенос из предыдущего. Значит надо складывать три бита: a, b и cin. Полный сумматор собирается из двух полусумматоров. Проверим обе схемы кодом:
def half_adder(a, b):
return (a & b), (a ^ b) # (carry, sum)
def full_adder(a, b, cin):
c1, s1 = half_adder(a, b)
c2, s = half_adder(s1, cin)
cout = c1 | c2
return cout, s
print("a b cin | cout sum")
for a in (0,1):
for b in (0,1):
for cin in (0,1):
cout, s = full_adder(a, b, cin)
print(f"{a} {b} {cin} | {cout} {s}")Вывод:
a b cin | cout sum 0 0 0 | 0 0 0 0 1 | 0 1 0 1 0 | 0 1 0 1 1 | 1 0 1 0 0 | 0 1 1 0 1 | 1 0 1 1 0 | 1 0 1 1 1 | 1 1
Как работает под капотом: каскад (ripple-carry)
Чтобы сложить 4-битные числа, ставим 4 полных сумматора в ряд. Перенос «течёт» (ripple) из младшего разряда в старший, как при сложении в столбик. Соберём 4-битный сумматор:
def full_adder(a, b, cin):
s = a ^ b ^ cin
cout = (a & b) | (cin & (a ^ b))
return cout, s
def adder4(A, B):
# A, B - списки из 4 бит, младший разряд первым
carry = 0
result = []
for i in range(4):
carry, s = full_adder(A[i], B[i], carry)
result.append(s)
return result, carry
# 5 = 0101 -> [1,0,1,0]; 6 = 0110 -> [0,1,1,0]
A = [1,0,1,0]
B = [0,1,1,0]
res, cout = adder4(A, B)
value = sum(bit << i for i, bit in enumerate(res)) + (cout << 4)
print("5 + 6 =", value, "(биты, младший первым:", res, "перенос:", cout, ")")Вывод:
5 + 6 = 11 (биты, младший первым: [1, 1, 0, 1] перенос: 0 )
Цена каскада
У ripple-carry есть слабость: старший разряд должен дождаться переноса от всех младших. Для 64-битного числа это 64 задержки подряд — медленно. Поэтому в реальных процессорах применяют сумматоры с ускоренным переносом (carry-lookahead), которые вычисляют переносы заранее параллельно. Но идея сложения остаётся той же.
Глубже в тему
Почему сложение бит начинается именно с XOR — стоит прочувствовать, а не просто запомнить. XOR выдаёт единицу, когда входы различны, то есть ровно тогда, когда в сумме «один плюс ноль» получается один. А единственный случай, когда биты дают перенос, — это «один плюс один», и его ловит AND. Получается, что таблица истинности сложения двух бит идеально раскладывается на два знакомых вентиля без какой-либо подгонки. В этом и красота: арифметика не «прикручена» к логике искусственно, она в ней уже содержится. Тот же мост ведёт и обратно — умножение строится из сдвигов и сложений, вычитание из сложения с дополнительным кодом, а значит, вся целочисленная арифметика вырастает из этой одной клеточки.
Полный сумматор можно описать двумя способами, и оба полезны. Через два полусумматора видно происхождение схемы: сначала складываем a и b, потом к результату прибавляем входной перенос. Через прямые формулы sum = a XOR b XOR cin и cout = (a AND b) OR (cin AND (a XOR b)) видно суть: бит суммы — это чётность тройки бит, а перенос — мажоритарная функция, то есть «перенос есть, если хотя бы двое из трёх входов единичны». Заметьте, что перенос — это «голосование большинством»: ровно эта функция всплывёт ещё много где в цифровой технике.
Слабость каскада ripple-carry стоит оценить количественно, потому что именно она десятилетиями двигала проектирование сумматоров. Старший разряд физически не может выдать правильный бит, пока к нему не «дотечёт» перенос через все младшие разряды по очереди. Для 64-битного числа это до 64 последовательных задержек вентилей — и эта цепочка обычно и есть тот самый критический путь, что ограничивает тактовую частоту (мы вернёмся к нему в разделе про тактирование). Поэтому в реальных процессорах ставят сумматоры с предвычислением переноса (carry-lookahead) и их родственников: они заранее, параллельно вычисляют, в каких разрядах перенос точно возникнет (когда оба бита единичны) и через какие он «протолкнётся» (когда биты различны). Это снижает задержку с линейной до логарифмической ценой большей площади — снова тот же компромисс «скорость против размера».
Наконец, важно понимать, что один и тот же сумматор обслуживает и сложение, и вычитание, и сравнение. Вычитание реализуется как сложение с дополнительным кодом, а сравнение двух чисел — это вычитание с проверкой флагов результата. Именно поэтому сумматор — не просто «калькулятор плюса», а вычислительное ядро, вокруг которого в следующем уроке вырастет всё АЛУ. И тот же блок считает адреса в памяти, индексы массивов и значение счётчика команд — в процессоре сложение происходит буквально на каждом шагу.
Частые ошибки
- Забывать про входной перенос. Полусумматор складывает только 2 бита; для каскада нужен полный сумматор (3 бита).
- Путать sum и carry. sum = XOR (бит результата), carry = AND/мажоритарность (перенос в старший разряд).
- Игнорировать задержку переноса. Наивный ripple-carry линейно медленный по числу разрядов.
Итог
- Полусумматор: sum = a XOR b, carry = a AND b.
- Полный сумматор складывает три бита (a, b, cin) и собирается из двух полусумматоров.
- Каскад полных сумматоров складывает многоразрядные числа; перенос «течёт» по разрядам.