Допиливаем двоичный сумматор в игре «Жизнь» до конца

Продолжаем писать двоичный калькулятор, который складывает два двубитовых числа.

В первом посте мы написали саму игру «Жизнь» и модуль для отрисовки эволюции клеток на экране. Во втором посте познакомились с распространёнными фигурами из игры, научились генерировать «сигналы» и создали логические гейты NOT, AND, OR и XOR.

В этом посте мы используем созданные гейты, чтобы реализовать схему двоичного полусумматора, полного сумматора, а потом и калькулятора, который будет складывать два двубитовых числа.

Двоичный полусумматор

Полусумматор — это логическая схема, которая умеет складывать два бита. На вход схемы подаём два сигнала, на выходе получаем бит суммы и бит переноса:

Бит переноса отвечает за перенос суммы в следующий разряд. Так как мы работаем с двоичной логикой, то и система счисления при суммировании тоже двоичная. При сложении 1 и 1 один разряд не вмещает в себя всю сумму полностью, и единицу надо перенести в следующий разряд — для этого используется бит переноса.

А полусумматор он потому, что делает лишь половину настоящего сложения. Он действительно складывает два бита, но не может учесть перенос с предыдущего разряда, если он есть. Для полного сложения нам понадобится 2 таких полусумматора — к этому мы вернёмся позже.

(Гораздо более подробно о том, как работают двоичные сумматоры написал Петцольд в «Коде», советую прочесть.)

Схема полусумматора

Мы не будем придумывать схему заново, а подсмотрим её в Википедии. На схеме видно, что полусумматор состоит из гейтов XOR и AND.

XOR отвечает за бит суммы, а AND — за бит переноса. И действительно, если мы подаём на вход 1 и 1, XOR выдаст на выходе суммы 0, так как разряд переполнен, и требуется перенос. AND при таких входных значениях выдаст 1, что в результате и даст нам сумму 10.

В остальных случаях бит переноса (AND) будет выдавать 0, а сумма (XOR) — сумму двух входных значений.

Делим сигналы

У нас есть почти всё необходимое для переноса схемы. Гейты XOR и AND мы сделали в прошлый раз, но вот разделителя сигнала у нас сейчас не хватает.

Если мы посмотрим на схему ещё раз, то увидим, что сигнал от каждого входа делится на два. Каждый из этих разделённых сигналов отправляется на входы одного из гейтов. Чтобы это повторить, нам потребуется новый паттерн — разделитель (fanout).

Я не буду приводить псевдографику разделителя здесь, потому что она занимает много места, но оставлю ссылку на исходник. Сама же схема разделителя будет такой:

// gates/split.js

const signalGun = withSettings(gliderGunP60, { rotate: 270, reflect: true });
const split = withSettings(fanout, { phase: 11 });

export function divide(input = 0) {
	const signal = input ? { pattern: signalGun } : null;
	const splitter = { pattern: split, offset: { x: 28, y: 39 } };
	return composePatterns([signal, splitter]);
}

Разделитель будет дублировать входящий сигнал, поворачивая его на 90 градусов влево. Фазы глайдеров останутся теми же, что будет удобно при составлении схем в будущем:

Переносим схему в «Жизнь»

Прежде, чем пробовать составить полусумматор из элементов, которые у нас уже есть, стоит наметить примерную схему расположения всех элементов. У меня получилось нечто вот такое:

(Я почти уверен, что можно было расположить всё гораздо компактнее, но мне не хватило на это терпения — слишком уж муторно было подбирать расположение и фазы. Ссылки на более удачные решения я собрал в конце, ну а если у вас есть идеи — пул-реквесты на Гитхабе открыты 😃)

Рассмотрим внимательнее, что на схеме происходит. Сверху находится входной сигнал A, поток глайдеров которого делится разделителем на два потока. Под ним расположен сигнал B, поток которого так же делится разделителем на два.

Разделённые сигналы от каждого входа направлены влево и вправо. Сигналы справа поступают на вход схемы XOR, которую мы написали в прошлый раз. Выход этой схемы — это бит суммы. Если оба сигнала равны 1 или оба равны 0, то результат будет равен 0. В остальных случаях бит суммы будет равен 1.

Левые сигналы поступают на вход схемы AND. Её выход равен 1, только если оба сигнала равны 1 — это результат бита переноса.

Для того, чтобы составить такую схему, нам понадобятся:

• две пушки для входных сигналов;
• два разделителя, по одному на каждый вход;
• три отражателя, чтобы перенаправить некоторые сигналы на входы гейтам;
• гейты XOR и AND.

Создадим все нужные элементы:

// circuit/half-adder.js

// Пушки входных сигналов:
const gunA = withSettings(gliderGunP60, { rotate: 270, reflect: true });
const gunB = withSettings(gliderGunP60, { rotate: 270, reflect: true });

// Разделитель можно использовать одинаковый в обоих случаях:
const splitter = divide();

// Рефлекторы:
const redirectRight = withSettings(reflector, { phase: 4 });
const redirectA = withSettings(reflector, { phase: 1, reflect: true });
const redirectB = withSettings(reflector, { phase: 29, reflect: true });

Теперь создадим функцию, которая будет принимать два аргумента:

// circuit/half-adder.js

export function halfAdder(a = 0, b = 0) {
	// Создаём пушку, если есть соответствующий входной сигнал:
	const signalA = a ? { pattern: gunA, offset: { x: 328, y: 2 } } : null;
	const signalB = b ? { pattern: gunB, offset: { x: 329, y: 124 } } : null;

	// Делим каждый вход на два сигнала:
	const splitA = a ? { pattern: splitter, offset: { x: 328, y: 2 } } : null;
	const splitB = b ? { pattern: splitter, offset: { x: 329, y: 124 } } : null;

	// Берём XOR правых сигналов, чтобы получить бит суммы:
	const rerouteRight = { pattern: redirectRight, offset: { x: 496, y: 189 } };
	const sumBit = { pattern: xor(), offset: { x: 318, y: 201 } };

	// Берём AND левых сигналов, чтобы получить бит переноса:
	const divertA = a ? { pattern: redirectA, offset: { x: 54, y: 370 } } : null;
	const divertB = b ? { pattern: redirectB, offset: { x: 182, y: 365 } } : null;

	const carryBit = { pattern: and(), offset: { x: 83, y: 353 } };

	// Компонуем все элементы схемы в популяцию:
	return composePatterns([
		signalA,
		splitA,
		signalB,
		splitB,

		rerouteRight,
		divertA,
		divertB,

		sumBit,
		carryBit
	]);
}

Полный код схемы вы сможете найти на Гитхабе. Проверим, всё ли работает!

Я сделал отдельную страницу, на которой находится только эта схема — можно зайти повводить разные значения. (А ещё есть отдельная страница со всеми шагами создания. Ну так, на всякий случай 😃)

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

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

Проще всего провести аналогию со сложением столбиком:

  1 0 1  Число A
  0 1 1  Число B
_______
1 0 0 0  Сумма
0 1 1 1  Выходной перенос разряда
1 1 1 0  Входной перенос разряда

Сложение начинается с младшего, нулевого разряда (справа). У него по определению входного переноса нет, потому что до него мы не производили сложение.

Выходной перенос нулевого разряда станет входным переносом первого. По правилам сложения, в первом разряде нам надо уже не только сложить числа A и B, но ещё и прибавить к ним перенос с нулевого разряда. Именно эту задачу и решает полный сумматор — он позволяет учитывать результат сложения младших разрядов.

Благодаря входному переносу мы можем соединять сумматоры «паровозиком», где выходной перенос каждого становится входным переносом последующего. Обратите внимание, что младший разряд здесь также находится справа — это позволяет продолжить аналогию со сложением столбиком:

Схема сумматора

Полный сумматор состоит из двух полусумматоров и гейта OR. Первый полусумматор считает сумму и перенос входных сигналов, а второй — учитывает перенос предыдущего разряда:

Таблица входов и выходов для полного сумматора будет отражать «сложение столбиком» одного разряда:

В принципе, это уже можно переносить в игру, но есть одна проблема. На схеме некоторые сигналы проходят «над» другими — пересекаются без соединения. Мы можем настроить потоки глайдеров так, чтобы они «проходили сквозь» друг друга, не уничтожаясь, но для этого потребуется менять их фазы, а это сложно.

Для изменения фаз, нам понадобится добавить другой вид отражателей, расставить их так, чтобы они вовремя меняли фазы, а потом меняли их обратно… Вместо этого я решил перестроить схему сумматора так, чтобы у сигналов не было пересечений.

Присмотревшись можно увидеть, что схема работает так же, но в ней не пересекаются сигналы, и она занимает больше места. Пересечения позволяют скомпоновать элементы компактнее, что важно для, например, настоящих электронных схем. Но в этом случае мне показалось, что можно пожертвовать пространственной эффективностью в угоду лени, штоуш 😅

Переносим сумматор

Попробуем собрать схему из существующих элементов. Сумматор — это функция от 3 входных значений: двух битов и переноса. Для сложения битов мы используем полусумматор, который создали ранее. Для учёта переноса составим полусумматор из отдельных элементов — это будет удобнее:

// circuit/full-adder.js

export function fullAdder(a = 0, b = 0, carry = 0) {
	const inputSum = { pattern: halfSum(a, b), offset: { x: -4, y: 118 } };
	const carry0 = carry ? { pattern: gunCarry0, offset: { x: 801, y: 600 } } : null;

	// Делим каждый перенос на два сигнала:
	const splitCarry0 = { pattern: divide(), offset: { x: 801, y: 600 } };
	const splitCarry1 = { pattern: divide(), offset: { x: 464, y: 555 } };

	// Используем XOR суммы 1-го бита и переноса 0-го бита,
	// чтобы получить финальную сумму:
	const sumOut = { pattern: xor(), offset: { x: 596, y: 738 } };
	const collector1 = { pattern: collector, offset: { x: 753, y: 997 } };

	// Перенаправляем сигналы для удобства:
	const divertLeft = { pattern: redirectLeft, offset: { x: 385, y: 728 } };
	const divertBack = { pattern: redirectBack, offset: { x: 1027, y: 845 } };
	const divertForward = { pattern: redirectForward, offset: { x: 838, y: 1029 } };

	// Получаем AND суммы 1-го бита и переноса,
	// зачем OR получившегося значения и переноса,
	// чтобы получить финальный перенос:
	const sumAndCarry = { pattern: and(), offset: { x: 778, y: 1101 } };
	const carryOut = { pattern: or(), offset: { x: 892, y: 1312 } };

	// Превращаем всё это в популяцию:
	return composePatterns([
		carry0,
		inputSum,

		splitCarry0,
		splitCarry1,

		sumOut,
		collector1,

		divertLeft,
		divertBack,
		divertForward,

		sumAndCarry,
		carryOut
	]);
}

Полный код схемы с настроенными фазами каждого элемента вы сможете найти на Гитхабе.

Если мы теперь запустим схему, передав ей все единицы, то получим на выходе сумму 1 и перенос 1:

Я также сделал и отдельную страницу, на которой находится только схема полного сумматора — добро пожаловать 😃

Складываем два числа

Один сумматор складывает один разряд. Чтобы сложить два двубитовых значения, нам нужно два сумматора. Но так как младший разряд по умолчанию не будет содержать входного переноса, нам достаточно использовать один сумматор и один полусумматор.

Полусумматор будет считать сумму и перенос младшего (нулевого) разряда, а полный — сумму и перенос старшего (первого) разряда.

Мы переиспользуем схемы, которые уже создали, поэтому код будет коротким:

// circuit/two-bits-adder.js

const halfSum0 = (a, b) => jumpToPhase(halfAdder(a, b, { collectCarry: false }), 27);

export function adder(a = '00', b = '00') {
	const [a0, a1] = toBits(a);
	const [b0, b1] = toBits(b);

	const bit0 = { pattern: halfSum0(a0, b0), offset: { x: 514, y: 16 } };
	const bit1 = { pattern: fullAdder(a1, b1) };
	return composePatterns([bit0, bit1]);
}

Функция toBits будет дробить строку на отдельные значения «битов». Из неё мы возвращаем числа в обратном порядке, чтобы младший разряд стоял в массиве первым:

// utils.js

export function toBits(str) {
	return str.split('').map(Number).reverse();
}

Ну и наконец — проверим, как будет работать сложение! Попробуем сложить «11» и «11», чтобы получить «110»:

Отлично, сложение работает верно! Поиграться с различными значениями можно на странице приложения. Я также добавил настройку скорости эволюции, чтобы можно было ускорять распространение сигналов по схеме. По умолчанию значение считается довольно медленно, если не хочется ждать вечность, можно ускорить процесс.

Что стоит учесть

Вы могли заметить, что архитектура схемы не самая эффективная и красивая 😅
Как я говорил ранее, можно расположить элементы гораздо компактнее, если научиться скрещивать потоки глайдеров без их уничтожения. Да и логические гейты работают не совсем так, как настоящие электронные устройства.

Также схема не учитывает задержки сигналов, и правильный ответ даёт спустя какое-то время, когда все сигналы дойдут до конца. До этого момента на выходах может появляться шум. Понятно, что в настоящих схемах такого допускать нельзя, но я посчитал, что в демо на это можно не обращать внимания.

Кроме этого, из моих схем трудно совместить трёх или четырёх-битовый калькулятор. А вот, например, Николас Карлини (Nicholas Carlini) написал аж целый счётчик с дисплеем. Он визуализировал весь процесс в Golly — мейнстримовом приложении для работы с игрой «Жизнь». В Golly удобно управлять масштабом мира, чтобы рассмотреть детали.

Его схемы гораздо более эффективные, точные и совместимые друг с другом. Они больше похожи на настоящие штуки, на которых работают компьютеры. А в третьем посте он предлагает ещё более крутое решение, где вместо глайдеров использует легковесные корабли (lightweight space ships). Короче, очень рекомендую прочесть его.

Также для разработки именно схем можно использовать другой клеточный автомат, который называется Wireworld. Его правила идеально подходят для моделирования логических и электрических схем (в отличие от игры жизнь, лол). О других подобных клеточных автоматах есть отличный ролик на канале Onigiri — тоже рекомендую.

Ссылки и ресурсы

• Исходники
• «Калькулятор» двух бит
• Создание схемы по шагам

Другие посты из серии

• Первая часть: пишем основы игры «Жизнь»
• Вторая часть: реализуем логические гейты

Фигуры, схемы и теория

• Разделитель
• Полусумматор
• Полный сумматор
• Full Adder on theorycircuit.com
• Binary Half and Full Adder
• Код. Тайный язык информатики. Чарльз Петцольд

Другие правила, автоматы, реализации

• Digital Logic Gates on Conway’s Game of Life - Part 1
• Клеточные автоматы | Сделал игру жизнь в 3D
• Wireworld
• Список автоматов, похожих на «Жизнь»