Abnormal programming
Entertaining tasks
Algorithms
Mathematics
Programming microcontrollers
16 March 2017

Считаем до трёх

Троичные вычисления


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



Я выбрал сбалансированную троичную систему, в которой один трит может представлять одно из трёх значений -1, 0 или 1. Весьма подробно о ней можно почитать тут.

На любые вопросы из разряда «зачем?!» я отвечаю заранее: «Because I can».



Стройматериал: троичный мультиплексор


Логический уровень


Базовым стройматериалом является троичный мультиплексор. Логически это штука о пяти выводах: на один из них (sel) подаётся троичный сигнал селектора, и в зависимости от него на выход мультиплексора (out) подаётся один из трёх входных сигналов inN, inO или inP.

На схемах его обычно рисуют как-то так:



Демультиплексор работает похожим образом: в зависимости от селектора один вход замыкается на один из трёх выходов. Та железка, что использую я, имеет двунаправленные ключи, так что она разом и мультиплексор, и демультиплексор (впрочем, возможности демультиплексирования я пока не использую).

Реализация в железе


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



До того, как я наткнулся на этот дизайн (к слову, немало информации по троичным вычислениям и железкам для них есть на форуме Александра), я пытался городить огород из cd4016 и cd4007, что работало, но было крайне громоздко и неудобно. Использование ключей dg403 даёт настоящий троичный элемент без какой бы то ни было избыточности типа кодирования троичной системы в двухбитовой двоичной.

Кстати, в отличие от многих теоретиков, Александр пошёл гораздо дальше, он разработал и заказал собственные микросхемы, работающие на троичной логике:



Для создания одного мультиплексора TRIMUX Александр использовал две микросхемы ключей dg403, у одной логика запитана между -5В и 0В, а у второй между 0В и 5В, что позволяет работать с троичным сигналом, представленным тремя уровнями напряжения -5, 0 и 5В. Но это оставляет половину ног свободной, поэтому в две микросхемы dg403 как раз умещаются два троичных мультиплексора.





Как это использовать? Функции одного аргумента


Давайте пропустим тривиальную тождественную функцию, которую можно получить, подав на соответствующие входы мультиплексора -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.

Давайте его тестировать! Красный диод = -1, выключенный = 0, зелёный = 1. Таким образом, эта фотография нам говорит, что S=-1, C=1, то есть, 1+1 = -1 + 3*1:



Вот эта табличка даёт все девять возможных состояний нашего полусумматора, каждая ячейка приводит соответствующие значения S и С. По ссылкам в ячейках соответствующие фотографии железа.
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

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

Вот так выглядит бутерброд для двух разрядов:


Вот так он решает пример -4 + 2 (левая плата — младший разряд):


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

Заключение


В данной статье я кратко рассказал, из чего и как можно строить базу для троичных вычислений. В следующих выпусках ждите счётчики, память, АЛУ и т.п. Stay tuned!

+81
27.3k 145
Support the author
Comments 64
Top of the day