Adder (Computing)

О гадюках, см. Adder.

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

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

Прежде чем приступить к суммированию, следует ознакомиться с логическими элементами NOT, OR, XOR и AND. Описания этих вентелей есть для механической, жидкостной, животной и логики существ. Для сложения также требуются слагаемые, которые необходимо хранить в некоторой памяти.

Инкрементирование

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

1-битное инкрементирование

Простейшее инкрементирование — это приращение на 1 бит, то есть сложение двух однобитовых двоичных значений. Есть две опции: 0+1=1 и 1+1=10, но поскольку у нас есть только один бит, мы отказываемся от старшего бита, поэтому 1+1=0. Эта таблица значений представляет собой ту же таблицу, что и для операция NOT. Обратите внимание, что наша таблица значений декремента также идентична: NOT — это одновременно и приращение на 1 бит, и уменьшение на 1 бит.

2-битное инкрементирование

Понятно, что инкрементирование 1-го бита не очень полезно. Однако мы можем легко сгенерировать перенос из нашего приращения на 1 бит, учитывая значение нашего 1-го бита. Когда мы увеличиваем наш первый бит, он генерирует перенос, влияющий на наш второй бит тогда и только тогда, когда наш первый бит равен 1 (истина), поэтому, выполняя операцию XOR нашего второго (более значимого) бита с нашим первым битом, мы генерируем правильное значение для второго бита. Важно отметить, что это XOR должно выполняться с исходным значением первого бита, а не с увеличенным (NOT) значением!

2-битное декрементирование

При двух битах декрементирование немного отличается от инкрементирования, но ненамного. Разница лишь в том, что мы будем генерировать перенос только в том случае, если наш первый бит равен 0. Таким образом, наша вторая цифра становится равной [2]XOR(NOT[1]), а не [2]XOR[1].

Инкрементирование и декрементирование 3 и более бит

Когда мы достигаем 3 или более битов, нам нужно добавить дополнительный уровень сложности. Представьте, что произойдет, если мы инкрементируем 1101: если мы просто [4]XOR[3] (XOR нашего 4-го бита с нашим 3-м битом), мы ошибочно получим значение как 0110, а не 1110. Нам нужно заставить наши переносы правильно распространяться по системе. Специальный инкрементатор может встроить эту функциональность в свои биты, увеличивая следующий более высокий бит каждый раз, когда он меняется с 1 на 0, но не тогда, когда он меняется с 0 на 1. Этот процесс можно описать логически, реализуя новый бит переноса, и действуя справа, использовать следующий алгоритм (это не какой-то конкретный язык, это просто псевдокод:)

установить [перенос] равным [1] — если наш первый бит равен 1, начинается перенос

[1] становится равным NOT[1] — наш первый бит инвертирует свое значение
установить n равным 2 — перейти к следующей позиции бита
пока n<=количество_бит — пока мы еще не разобрались со всеми битами
  [n] становится равным [n]XOR[перенос] — увеличиваем следующий бит, если у нас есть перенос
  [перенос] становится равным NOT[n] AND [перенос] — если наше значение для n-го бита сменилось, распространяем перенос; в противном случае завершить перенос
  n становится равным n+1 — переход к следующей битовой позиции
конец

Декрементация, опять же, работает аналогично — с той лишь разницей, что мы распространяем перенос тогда и только тогда, когда значение в определенной битовой позиции изменилось с 0 на 1.

установить [перенос] равным NOT[1] — если наш первый бит равен 0, начните перенос

[1] становится равным NOT[1] — наш первый бит инвертирует свое значение
установить n равным 2 — перейти к следующей позиции бита
пока n<=количество_бит — пока мы еще не разобрались со всеми битами
  [n] становится равным [n]XOR[перенос] — уменьшаем следующий бит, если у нас есть перенос
  [перенос] становится равным [n] И [перенос] — если наше значение для n-го бита сменилось, распространяем перенос; в противном случае завершить перенос
  n становится равным n+1 — переход к следующей битовой позиции
конец

Пример системы инкрементирования, основанной на логике существ, со встроенным в память инкрементированием, см. в здесь.

Счетчик

Обычно системы инкрементирования разрабатываются не только с учетом ввода, но и вывода. Такая система увеличивает каждый раз, когда она получает определенный входной сигнал, и выдает результат, когда достигает определенного внутреннего счетчика этого входного сигнала. Выходные цепи представляют собой простые вопросы двоичного счета. Например, счетчик, который выводит результат после достижения 11, то есть выдаёт на выход 1, когда первый бит равен 1 И второй бит равен 1 И третий бит равен 0 И четвертый бит равен 1. Обычно выход предназначен для сброса счетчика путем записи 0 для всех битов счетчика.

Пример системы инкрементирования, использующей животную логику, см. в User:Bidok#Counter. Полностью жидкостная реализация доступна на странице User:Hussell/ClockToggle.

Сложение и инкрементирование

Простой, но медленный сумматор можно спроектировать, многократно увеличивая одно слагаемое и уменьшая второе слагаемое, пока второе не достигнет нуля. Такая система требует какого-нибудь повторителя для управления процессом — каждый раз, когда повторитель срабатывает, и второе слагаемое не равно нулю (NOT первый бит AND NOT второй бит AND NOT n-й бит), первое увеличивается, а второе уменьшается. Когда второе слагаемое достигает нуля, первое слагаемое представляет собой сумму двух начальных слагаемых.

Сложение

Описывая инкрементирование, мы почти описали полное сложение. Однако основой сложения является операция XOR, а не операция NOT.

1-битное сложение

В простейшем сумматоре мы рассматриваем два слагаемых. Благодаря этому у нас теперь есть четыре возможности: 0+0=0, 1+0=1, 0+1=0 и 1+1=10=0. Это та же самая таблица значений, которую мы получаем с помощью операции XOR. Следовательно, сложение двух однобитовых значений представляет собой операцию XOR для этих двух значений.

2-битное сложение

Для сложения нам нужно реализовать значение переноса с добавлением второго бита. Наш первый бит — это [1]XOR[1'] — то есть XOR первого бита обоих слагаемых (штрих обозначает второе слагаемое). Однако нам также необходимо сгенерировать значение переноса из этого сложения, которое равно [1]AND[1']. Чтобы получить значение второго бита, мы сначала складываем оба вторых бита, затем XOR результата к нашему переносу из первого бита — таким образом, второй бит становится равным ([2]XOR[b])XOR[перенос] или XOR нашего переноса с XOR второго бита нашего первого слагаемого и второго бита нашего второго слагаемого.

Этот алгоритм обобщается на значения любой битовой длины. Мы работаем справа налево. После определения значения нашего 2-го бита нам нужно обновить наше значение переноса, которое становится равным 1, если любые два (или более) значения, обработанные XOR, включая перенос, были равны 1. То есть после завершения значения для нашего второй бит, мы устанавливаем наш перенос равным (([2]OR[2'])AND([carry]))OR([2]AND[2']).

Рассмотрим следующее красивое изображение 9-битного сумматора, основанного на логике животных, с примечаниями, обозначающими значение каждой цифры:

• 

  Больше информации в User:LordOOTFD#Adders

6-битный механический сумматор продемонстрирован в http://mkv25.net/dfma/movie-1561-addingmachine. 8-битная гибридная система продемонстрирована в http://mkv25.net/dfma/movie-1084-numberabbeydemonstration.

n-битное вычитание

Вычитание, опять же, удивительно похоже на сложение. Здесь, однако, мы должны учитывать, что вычитание не является коммутативным, поэтому придётся учитывать, что одно значение вычитается из другого. Мы будем считать наше второе значение, представленное n' битовыми позициями, вычитаемым, а первое значение, из которого вычитается, уменьшаемым.

Опять же, основой вычитания является операция XOR. Рассмотрим четыре возможности для бита: 0-0=0, 1-0=1, 0-1=-1=1, 1-1=0. Разница в том, как мы работаем с переносом. Для нашего первого, крайнего правого бита мы начинаем с установки переноса на 0 (ложь). После этого мы генерируем перенос либо в том случае, если и наш перенос, и вычитаемое равны 1, либо если наше уменьшаемое равно нулю, а либо наш перенос, либо вычитаемое равно 1. Другими словами, перенос для первого бита равен ([carry]AND[1'])OR(NOT[1]AND([carry]OR[1'])). Это работает для вычитаний любой длины.

Сложение с переносом

Из предыдущих примеров было ясно, что наши значения находятся под угрозой переполнения. Например, добавление 1 к 1111 дает 0. Традиционные (не-дварфийские) компьютеры обычно имеют функцию сложения и сложения с переносом. Их комбинация позволяет добавлять значения, превышающие длину бита.

Сложение с переносом начинается с простого сложения наименьшего фрагмента двух слагаемых. Например, для слагаемых 000001 и 001111, мы могли бы начать с трех младших цифр каждого из них, 001 и 111, и сложить их, в результате чего получится 000. Однако для следующего сложения мы сохраним перенос, сгенерированный последний (третий) бит сложения, а не отбрасывать его в начале следующего переноса. Теперь мы добавляем следующие три цифры каждого значения (000 и 001), но включая перенос из нашего предыдущего сложения. Эти последовательные сложения дают нам правильное значение (010000) без достаточной длины бит для сложения в противном случае.

Система, способная как просто складывать, так и складывать с переносом, считается полным сумматором. Полные сумматоры, даже 1-битные полные сумматоры, могут складывать значения любой битовой длины. Пример использования жидкостной логики см. в User:Kyace/Adder.

Ускоренный перенос

Хотя простой сумматор и способен выполнять надежное сложение, он может работать очень медленно. Рассмотрим 8-битный сумматор: значение 8-го бита зависит от переноса, полученного из 7-го бита, который, в свою очередь, зависит от переноса, полученного из 6-го бита, и так далее. Все сложение должно выполняться последовательно, а не добавлять биты параллельно. Из-за того, как перенос колеблется в значении, такие системы называются "каскадными сумматорами". Когда в цепях используются вода или живые существа, операция сложения 8-битных чисел может занимать день или больше. Однако этот процесс можно значительно улучшить за счет увеличения сложности, внедрив систему прогнозирования.

Системы предсказания разбивают значения на последовательности битов, основываясь на том факте, что если оба слагаемого в n-ом бите равны 0 ((NOT[n])AND(NOT[n'])), любой перенос закончится на этом бите, и если бит в слагаемых равен 1 ([n]AND[n']), он будет генерировать перенос. Основываясь на этом, можно параллельно обрабатывать добавление бит различной длины, основываясь на знании того, что переносы не будут распространяться дальше бита, завершающего перенос. Это может значительно сократить время, необходимое для сложения двух чисел.

Дварфисйский компьютер от Jong'а использует предсказание для более быстрого сложения и способен складывать с переносом. Проект можно дополнительно сжать до очень компактного и универсального полного сумматора: User:Larix/Adder. Пример использования логики существ см. в разделе Vasiln/Goblin_Logic_2.

Умножение и деление

Хотя подобные логические инструменты выходят за рамки этой статьи, их можно использовать для умножения или деления двух значений. В простейшей (но самой медленной) реализации любой из них может быть представлен последовательным сложением или вычитанием, объединяющим сумматор со счетчиком. Это также можно сделать с помощью египетского умножения и деления.

• User:BaronW демонстрирует действие именно такого впечатляющего механического калькулятора.