Анатомия сумматора
Как заставить провода сложить два числа? Здесь на помощь приходят уже знакомые нам логические вентили.
Чтобы сложить два бита, нужно получить два результата: саму сумму и бит переноса — ту самую «единицу в уме», когда мы складываем 1 + 1. Для вычисления суммы идеально подходит вентиль XOR: он выдаёт 1, только если на входах разные значения, и 0, если на обеих входах единицы. А чтобы поймать бит переноса, параллельно ставим вентиль AND — он сработает только тогда, когда мы складываем две единицы одновременно.
Такая связка из XOR и AND называется полусумматором. Правда, он умеет складывать только два бита, и у него нет входа для переноса. А как сами числа представляются в двоичной системе — напоминает статья «Двоичная математика для начинающих».
Полусумматор: XOR и AND
Полусумматор (Half Adder) складывает два бита A и B и выдаёт два бита: Sum (сумму) и Carry (перенос). Формулы у него простейшие:
Sum = A XOR B
Carry = A AND BПроверим по таблице истинности:
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Обрати внимание на последнюю строку: 1 + 1 даёт сумму 0 и перенос 1 — это двоичная «10», то есть десятичная двойка. Ровно как при сложении в столбик.
Но у полусумматора есть ограничение: он не понимает, что с младшего разряда могла прийти «единица в уме». Здесь нужен полный сумматор.
Полный сумматор: третий вход
Полный сумматор (Full Adder) решает эту проблему: у него три входа — A, B и CarryIn (перенос с младшего разряда) — и два выхода: Sum и CarryOut. Полная таблица истинности — 8 строк, все комбинации трёх входов:
| A | B | CarryIn | Sum | CarryOut |
|---|---|---|---|---|
| 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 |
Закономерность видна сразу: Sum — это сумма трёх битов по модулю два, а CarryOut равен 1, когда единиц на входах не меньше двух.
Формулы сумматора
Сумма считается через двойной XOR, а перенос — через «голосование большинства»:
Sum = (A XOR B) XOR CarryIn
CarryOut = (A AND B) OR (A AND CarryIn) OR (B AND CarryIn)Первый XOR складывает A и B, а второй добавляет к результату перенос CarryIn.
А перенос — это «голосование большинства»: CarryOut = 1, когда хотя бы два из трёх входов равны 1. Три попарных AND проверяют каждую пару, а OR собирает победу — выигрывает большинство.
Цепочка переноса: 113 + 29
Один сумматор складывает один разряд. Чтобы сложить 8-битные числа, соединяем восемь полных сумматоров в цепочку: CarryOut каждого подаётся на CarryIn следующего. Такая конструкция называется каскадом, или ripple carry, — перенос перетекает по разрядам, как волна.
Проверим на числах из статьи о двоичной математике: 113 (01110001) + 29 (00011101).
FA0: 1 + 1 + 0 = 0, перенос 1
FA1: 0 + 0 + 1 = 1, перенос 0
FA2: 0 + 1 + 0 = 1, перенос 0
FA3: 1 + 0 + 0 = 1, перенос 0
FA4: 1 + 1 + 0 = 0, перенос 1
FA5: 1 + 0 + 1 = 0, перенос 1
FA6: 1 + 0 + 1 = 0, перенос 1
FA7: 0 + 0 + 1 = 1, перенос 0
Итог: 10001110 = 142Смотри, как перенос бежит по цепочке: из нулевого разряда в первый, потом из четвёртого в пятый, из пятого в шестой, из шестого в седьмой. При этом все сумматоры работают одновременно: схема не «выполняет код по шагам» — сигналы просто распространяются по проводам, и за время прохода волны переноса вся цепочка выдаёт готовый ответ: 142.
В игре: от полусумматора к ADDER8
В игре этот путь повторяется трижды. На уровне 1.6 ты собираешь полусумматор из XOR и AND и получаешь за награду чип HalfAdder. На уровне 1.7 — полный сумматор уже из трёх вентилей: XOR, AND и OR, — а в награду — чип FullAdder.
А на уровне 1.8 ты соберёшь 8-битный сумматор ADDER8: восемь полных сумматоров в цепочке плюс два расщепителя шины (Splitter) и сборщик (Maker), чтобы развести 8-битные входы по разрядам и собрать результат в шину. За прохождение получишь фирменный чип ADDER8. Про шины рассказывает статья «Информационные шины».
Частые ошибки
1. Подавать перенос в неправильную сторону. CarryOut младшего сумматора должен идти в CarryIn старшего, а не наоборот.
2. Забывать третий вход. Полный сумматор без подключённого CarryIn превращается в два независимых полусумматора.
3. Думать, что сумматоры работают по очереди. Вся цепочка вычисляет параллельно, просто перенос «дозревает» по мере распространения сигналов.
Резюме
1. Полусумматор складывает два бита: Sum = A XOR B, Carry = A AND B.
2. Полный сумматор принимает и перенос: входы A, B, CarryIn, выходы Sum и CarryOut.
3. Sum = (A XOR B) XOR CarryIn, а CarryOut — «голосование большинства» из трёх AND и одного OR.
4. Каскад сумматоров складывает числа любой длины: перенос каждого разряда уходит на вход следующего.
5. Цепочка из восьми сумматоров считает 113 + 29 = 142 = 10001110 за один проход волны переноса.
6. В игре: уровень 1.6 — полусумматор, 1.7 — полный сумматор, 1.8 — ADDER8 из восьми FullAdder.
На уровне 1.7 тебе предстоит собрать полный сумматор из вентилей XOR, AND и OR — ровно по формулам этой статьи. А на уровне 1.8 ты соединишь такие сумматоры в цепочку и соберёшь целый 8-битный ADDER8, увидев каскад переносов в деле.