Троичные вычисления
Я готовлю курс лекций по архитектуре компьютеров для студентов нашего университета, и в качестве небольшой практической разминки я бы хотел предложить студентам построить примитивный программируемый вычислитель в троичной логике. Конкретно эта статья рассказывает про базовый модуль, который будет использоваться в постройке, а именно про троичный мультиплексор. В данном тексте я не пойду дальше простейшего сумматора (и его реализации в железе), текст и так получается достаточно насыщенным. В последующих статьях я буду потихоньку рассказывать, куда меня эта кривая заведёт, так как я в самом начале авантюры.
Я выбрал сбалансированную троичную систему, в которой один трит может представлять одно из трёх значений -1, 0 или 1. Весьма подробно о ней можно почитать тут.
На любые вопросы из разряда «зачем?!» я отвечаю заранее: «Because I can».
Стройматериал: троичный мультиплексор
Логический уровень
Базовым стройматериалом является троичный мультиплексор. Логически это штука о пяти выводах: на один из них (sel) подаётся троичный сигнал селектора, и в зависимости от него на выход мультиплексора (out) подаётся один из трёх входных сигналов inN, inO или inP.
На схемах его обычно рисуют как-то так:
Демультиплексор работает похожим образом: в зависимости от селектора один вход замыкается на один из трёх выходов. Та железка, что использую я, имеет двунаправленные ключи, так что она разом и мультиплексор, и демультиплексор (впрочем, возможности демультиплексирования я пока не использую).
Реализация в железе
Дизайн железки принадлежит Александру Шабаршину, я его честно целиком свистнул. Единственное, что я сделал, так это развёл железку под поверхностный монтаж, т.к. эти микросхемы существенно дешевле выводных, в китае можно их взять по 50 центов за штуку.
До того, как я наткнулся на этот дизайн (к слову, немало информации по троичным вычислениям и железкам для них есть на форуме Александра), я пытался городить огород из cd4016 и cd4007, что работало, но было крайне громоздко и неудобно. Использование ключей dg403 даёт настоящий троичный элемент без какой бы то ни было избыточности типа кодирования троичной системы в двухбитовой двоичной.
Для создания одного мультиплексора Александр использовал две микросхемы ключей dg403, у одной логика запитана между -5В и 0В, а у второй между 0В и 5В, что позволяет работать с троичным сигналом, представленным тремя уровнями напряжения -5, 0 и 5В.
Как это использовать? Функции одного аргумента
Давайте пропустим тривиальную тождественную функцию, которую можно получить, подав на соответствующие входы мультиплексора -1, 0, 1.
Для начала давайте прибавим ко входному сигналу А единицу (разумеется, в кольце -1,0,1):
А вот так мы можем единицу вычесть:
Вот так мы можем посчитать функцию одного аргумента max(A,0):
А вот так min(A,0):
Функции двух аргументов: полусумматор
A+B
Итак, одного мультиплексора нам хватает для того, чтобы посчитать функцию одного аргумента. Чтобы посчитать функцию двух аргументов, придётся использовать три или четыре мультиплексора. Например, если мы хотим посчитать сумму двух троичных сигналов A и B (по-прежнему в рамках кольца -1,0,1), то можно использовать такую схему:
Первый уровень мультиплексоров считает функции одного аргумента от сигнала А, а второй их использует в зависимости от уровня сигнала B.
Консенсус
Если мы хотим посчитать функцию консенсуса от двух троичных сигналов (она равна -1 если A=B=-1 и равна 1 если A=B=1, иначе она равняется нулю), то это можно сделать так:
Реализация в железе
Итак, мы только что создали полусумматор. В зависимости от двух входов А и B он выдаёт два выхода S и С, которые можно посчитать как A+B = S + 3*C.
Давайте его тестировать!
Вот эта табличка даёт все девять возможных состояний нашего полусумматора, каждая ячейка приводит соответствующие значения S и С. По ссылкам в ячейках соответствующие фотографии железа. Красный диод = -1, выключенный = 0, зелёный = 1.
| S,C | B | |||
| -1 | 0 | 1 | ||
| A | -1 | 1,-1 | -1,0 | 0,0 |
| 0 | -1,0 | 0,0 | 1,0 | |
| 1 | 0,0 | 1,0 | -1,1 | |
Функции трёх аргументов: полный сумматор
Полный же сумматор должен принимать на вход три аргумента, а не два, как полусумматор. Третьим аргументом является перенос из младшего разряда. Итак, из трёх входов A,B и Cin нам нужно посчитать два выхода S и Cout по закону A+B+Cin = S + 3*Cout.
Сумма трёх тритов
Для функции трёх аргументов идея ровно та же, что и для функции двух: мы применяем послойную подготовку данных для последующих вычислений. То есть, первый слой мультиплексоров принимает на вход только A, второй только B и последний мультиплексор только Cin.
Вот так может выглядеть схема вычисления S:
Обратите внимание, что когда Cin = 0, то это по факту должно повторять работу полусумматора. Логично, что полусумматор входит в схему полного сумматора (выделено зелёным).
Переполнение результата
Трит переполнения считается совершенно аналогично и совершенно так же схема включает в себя схему вычисления трита переполнения у полусумматора:
Реализация в железе
В этот раз тыкать проводочки на макетке мне было лень, поэтому быстренько развёл плату:
И сдул вековую пыль с запасов гетинакаса:
Вот все 27 возможных состояний полного сумматора, обратите внимание, что средняя таблица (которая для Cin=0) повторяет таблицу для полусумматора.
| Cin = -1 | B | |||
| -1 | 0 | 1 | ||
| A | -1 | 0,-1 | 1,-1 | -1,0 |
| 0 | 1,-1 | -1,0 | 0,0 | |
| 1 | -1,0 | 0,0 | 1,0 | |
| Cin = 0 | B | |||
| -1 | 0 | 1 | ||
| A | -1 | 1,-1 | -1,0 | 0,0 |
| 0 | -1,0 | 0,0 | 1,0 | |
| 1 | 0,0 | 1,0 | -1,1 | |
| Cin = 1 | B | |||
| -1 | 0 | 1 | ||
| A | -1 | -1,0 | 0,0 | 1,0 |
| 0 | 0,0 | 1,0 | -1,1 | |
| 1 | 1,0 | -1,1 | 0,1 | |
Чем хорош полный сумматор, так это тем, что такие платы можно собирать в бутерброд до достижения нужной разрядности.
Заключение
В данной статье я кратко рассказал, из чего и как можно строить базу для троичных вычислений. В следующих выпусках ждите счётчики, память, АЛУ и т.п. Stay tuned!
Автор: haqreu
