Собираем свой компьютер. Арифметико-логическое устройство
На основе курса Nand2Tetris и книги The Elements of Computing Systems
Запись чисел в компьютере
Самые базовые операции, которые компьютер может выполнять - арифметические. Собственно, эти операции и выполняет ALU - arithmetical logical unit. В этом посте будет разобрано, как его реализовать, основываясь на гейтах из прошлого поста. Здесь пока не будет умножения и деления, только сложение и вычитание.
Начать стоит с напоминания - компьютеры (по крайней мере распространенные их реализации) не работают с “обычными” числами, они работают с двоичными числами. Двоичные числа - это числа, записанные в двоичной системе счисления. Двоичная система счисления - позиционная система счисления с основанием 2. Основание системы счисления - натуральное число, показывающее, сколько различных символов используется для записи чисел в данной системе счисления. Примеры:
- Двоичная: {0, 1}
- Десятичная: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- Шестнадцатеричная: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
В компьютерах обычно числа представляются “словами” - последовательностью цифр заданной длины. Например, если длина слова 4, то двоичное число 11 (3 в десятичной системе) будет записано не как 11, а как 0011. Соответственно, при такой записи числа не могут быть больше \(2^{word\_len}-1\).
Сложение
Сложение двоичных чисел происходит так же, как и десятичных. Складываем соответствующие разряды числа и перенос (carry, в школе это называли “в уме”). Если результат сложения не влезает в заданное слово, то старшие разряды просто отбрасываются (это называется переполнением). Таким образом на каждом разряде нам нужно сложить три числа: первое слагаемое (x), второе слагаемое (у) и перенос. Пример без переполнения:
Пример c переполнением:
Запись отрицательных чисел
Прямой код
Старший разряд используется для индикации отрицательного числа. То есть если 0011 = 3, то 1011 = -3. При таком подходе получается два ноля: +0 (0000) и -0 (1000)
Обратный код
Опять, старший разряд используется для индикации отрицательного числа, но все биты “перевернуты” относительно положительного числа. То есть если 0011 = 3, то при обратном коде -3 = 1100. И при этой записи тоже есть +0 и -0.
Дополнительный код
Его мы и будем использовать. Если мы хотим представить отрицательное число \(-x\), то мы его будем записывать в форме \(2^n-x\), где n - длина слова. Таким образом, если мы хотим записать -3, то вместо этого мы запишем \(2^4 - 3 = 16 - 3 = 13 = 1101\).
И опять, получается, что старший разряд бита мы отдаем под индикацию отрицательного числа. И тогда доступный нам диапазон чисел - это \([-2^{n-1} : 2^{n-1} - 1]\)
Сравнительная таблица
| Слово (n = 3) | Unsigned | Прямой код | Обратный код | Дополнительный код |
|---|---|---|---|---|
| 000 | 0 | 0 | 0 | 0 |
| 001 | 1 | 1 | 1 | 1 |
| 010 | 2 | 2 | 2 | 2 |
| 011 | 3 | 3 | 3 | 3 |
| 100 | 4 | -0 | -3 | -4 |
| 101 | 5 | -1 | -2 | -3 |
| 110 | 6 | -2 | -1 | -2 |
| 111 | 7 | -3 | -0 | -1 |
Вычитание отрицательных чисел
При записи дополнительным кодом отрицательных чисел мы автоматом получаем их вычитание. Посмотрим пару примеров, для облегчения возьмем длину слов n = 3, поскольку для них можно использовать таблицу выше.
Проверим на примере 3 - 1. Мы можем переписать его как 3 + (-1). Запишем в битовом виде: 011 + 111 = 1010. Отбросим лишний бит: 010. Смотрим по таблице: 010 -> 2. Что является корректным.
Проверим на примере 3 - 4: 011 + 100 = 111 -> -1. Верно.
Проверим на примере -1 - 2: 111 + 110 = 1101 -> 101 -> -3. Тоже верно
Как сделать число отрицательным
Вспомним, как именно мы представляем отрицательное число: если у нас есть положительное число \(x\), то отрицательное число \(-x\) будет иметь запись \(2^n-x\). Мы можем добавить и вычесть к этой записи единицу: \(1 + (2^n -1) - x\). \(2^n - 1\) при представлении в битовом слове будет полностью забито единицами. То есть если длина слова 4, то \(2^4 - 1 = 16 - 1 = 15 = 1111_{base\ two}\). Из такого слова легко вычесть любое другое: если у соответствующего разряда в вычитаемом стоит единица, то результирующий разряд просто зануляем, иначе ничего не делаем. После этого к получившемуся числу нужно просто добавить единицу.
Чипы
Теперь все описанное выше нужно реализовать в рамках логических гейтов и двоичной арифметики. Для этого нам понадобится 4 новых чипа:
- Half adder - на вход получает два бита для суммы, на выходе тоже два - результат в этом же разряде и индикация переполнения разряда
- Full adder - то же самое, что half adder, только на вход три бита
- Adder - складывает числа для слов заданной длины
- ALU - собственно, первый шаг к компьютеру. На вход получает два числа: x, y. Кроме этого несколько управляющих флагов, которые будут задавать функцию, применяемую к этим словам.
Я буду описывать чипы для длины слова N = 4, но они без проблем расширяются до 8 / 16 / 32 / …
Half adder
Все просто: на вход поступает 2 бита, на выход тоже. Один из битов это сумма битов на входе, другой сигнализирует, нужен ли перенос при сложении.
CHIP HalfAdder {
IN a, b; // 1-bit inputs
OUT sum, // Right bit of a + b
carry; // Left bit of a + b
PARTS:
Xor(a = a, b = b, out = sum);
And(a = a, b = b, out = carry);
}
Full adder
То же, что и Half Adder, только складывает 3 бита
CHIP FullAdder {
IN a, b, c; // 1-bit inputs
OUT sum, // Right bit of a + b + c
carry; // Left bit of a + b + c
PARTS:
HalfAdder(a = a, b = b, sum = smallSum, carry = smallCarry);
HalfAdder(a = smallSum, b = c, sum = sum, carry = bigCarry);
Or(a = smallCarry, b = bigCarry, out = carry);
}
Adder
Уже умеет складывать числа. На вход подается 2 числа в двоичном представлении, на выходе их сумма.
CHIP Add4 {
IN a[4], b[4];
OUT out[4];
PARTS:
HalfAdder(a = a[0], b = b[0], sum = out[0], carry = carry0);
FullAdder(a = a[1], b = b[1], c = carry0, sum = out[1], carry = carry1);
FullAdder(a = a[2], b = b[2], c = carry1, sum = out[2], carry = carry2);
FullAdder(a = a[3], b = b[3], c = carry2, sum = out[3], carry = discardCarry);
}
ALU
Арифметико-логическое устройство принимает в себя два числа: Х и Y, и несколько управляющих флагов:
- ZX - нужно ли занулить Х ввод
- ZY - нужно ли занулить Y ввод
- NX - нужно ли инвертировать биты X ввода
- NY - нужно ли инвертировать биты Y ввода
- F - если 1, то в OUT будет лежать результат X + Y, иначе там будет X & Y
- NO - нужно ли инвертировать биты OUT вывода.
Вывод имеет следующий вид:
- OUT - результат, посчитанный в соответствии с флагом F и прочими флагами, влияющими на ввод
- ZR - 1 если OUT == 0, иначе 0
- NG - 1 если OUT < 0, иначе 0
На схеме выделил несколько областей, чтобы легче было разобрать, что именно происходит (изображение кликабельно):
Сначала мы зануляем ввод, если это нужно, в соответствии с флагами ZX и ZY (1). Затем мы, опять же, в соответствии с флагами NX и NY при необходимости инвертируем ввод(2). Поскольку у нас нет чипов, которые позволили бы ветвить сигнал, мы посчитаем сразу обе функции, которые от нас могут попросить: и SUM и AND (3). Ненужный нам результат мы занулим и из двух оставим только один (4). Осталось немного: инвертировать вывод, если нужно (5) и вывести результат(6). При выводе результата мы в out выводим, собственно, результат вычислений, в NG мы выводим старший бит результата, поскольку если число негативное, то там будет 1 (согласно описанию записи через дополнительный код). Также в чипе Or4Way мы применяем Or ко всем битам OUT, чтобы понять, есть ли там хоть одна 1. Если мы на выходе получим 0, то, значит, и сам OUT - это 0. Поскольку флаг ZR стоит в 1, если результат 0, то, прежде чем вывести это значение в ZR, мы его тоже инвертируем.
// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0 // 4-bit constant
// if (nx == 1) set x = !x // bitwise not
// if (zy == 1) set y = 0 // 4-bit constant
// if (ny == 1) set y = !y // bitwise not
// if (f == 1) set out = x + y // integer 2's complement addition
// if (f == 0) set out = x & y // bitwise and
// if (no == 1) set out = !out // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1
CHIP ALU {
IN
x[4], y[4], // 4-bit inputs
zx, // zero the x input?
nx, // negate the x input?
zy, // zero the y input?
ny, // negate the y input?
f, // compute out = x + y (if 1) or x & y (if 0)
no; // negate the out output?
OUT
out[4], // 4-bit output
zr, // 1 if (out == 0), 0 otherwise
ng; // 1 if (out < 0), 0 otherwise
PARTS:
Not4(
in[0] = zx,
in[1] = zx,
in[2] = zx,
in[3] = zx,
out = notZx);
Not4(
in[0] = zy,
in[1] = zy,
in[2] = zy,
in[3] = zy,
out = notZy);
And4(a = notZx, b = x, out = xZeroPreset);
And4(a = notZy, b = y, out = yZeroPreset);
Xor4(
a = xZeroPreset,
b[0] = nx,
b[1] = nx,
b[2] = nx,
b[3] = nx,
out = xNegatePreset);
Xor4(
a = yZeroPreset,
b[0] = ny,
b[1] = ny,
b[2] = ny,
b[3] = ny,
out = yNegatePreset);
Add4(a = xNegatePreset, b = yNegatePreset, out = sumResult);
And4(a = xNegatePreset, b = yNegatePreset, out = andResult);
Not4(
in[0] = f,
in[1] = f,
in[2] = f,
in[3] = f,
out = notF);
And4(
a[0] = f,
a[1] = f,
a[2] = f,
a[3] = f,
b = sumResult,
out = sumZeroPostprocess);
And4(a = notF, b = andResult, out = andZeroPostProcess);
Or4(a = sumZeroPostprocess, b = andZeroPostProcess, out = funcResult);
Xor4(a = funcResult,
b[0] = no,
b[1] = no,
b[2] = no,
b[3] = no,
out = out,
out = outSecond,
out[3] = ng);
Or4Way(in = outSecond, out = isOutNotZero);
Not(in = isOutNotZero, out = zr);
}