1. Пролог
Недавно я прочитал замечательную статью [1]. В ней автор рассказывает о том, что не всегда вычислительные машины были двоичными. На заре компьютерной эры существовали машины, которые использовали десятичную и троичную систему счисления.
Десятичная система удобна человеку, но ее достаточно сложно реализовать на существующей элементной базе. Кроме того, десятичная система подвержена ошибкам в результате искажения сигнала при передаче. Троичную систему реализовать не на много сложнее двоичной ([2]), но она способна дать как минимум три преимущества.
Во-первых, представление отрицательных чисел становится естественным. Так как минимальная единица информации в троичной системе (будем называть ее трит) способна принимать три возможных значения, появляется возможность по-разному представлять ноль и положительное число.
Во-вторых, трайт (совокупность из восьми трит) способен принимать значения в диапазоне ±3 280, включая ноль, что приблизительно в тринадцать раз больше числа возможных значений байта в диапазоне только положительных чисел (байт принципиально не может принимать отрицательные значения без введения специальных условностей).
В-третьих, трит способен принимать значение «не определено», что ближе к модели человеческого , чем совокупность двоичных значений «истина» и «ложь».
Цель статьи — предложить метод реализации базовых логических операций с троичными значениями, используя двоичную вычислительную систему.
2. Троично-двоичное преобразование
Первое, что нам необходимо сделать — найти метод представления троичных чисел в двоичной вычислительной системе. Как уже было сказано, трит способен принимать три логических значения: «ложь», «не определено» и «истина». Три возможных значения могут быть представлены двумя битами, но в отличие от двоичной системы здесь биты неравноправны.
Пусть первый бит определяет логические значения «истина» и «ложь». Второй бит (полутрит) — управляющий. От его значения зависит определенность значения трита. Если полутрит установлен — значение трита определено, если сброшен — не определено.
Таким образом, для представления трайта необходимо два байта. Наиболее простой реализацией представляется «собрать» управляющие полутриты в один байт, а все «значащие» полутриты в другой.
Итоговое значение трита определяется по следующему алгоритму: анализируется значение полутрита из управляющего байта. Если оно ложно, значением трита становится «не определено», иначе значением трита становится значение значащего полутрита.
Пример:
Пусть трит в трайте может принимать одно из следующих значений:
1 — «истина»
-1 — «ложь»
0 — «не определено»
Значащий байт 0010 1100
Управляющий байт 1100 1010
Трайт -1-100 10-10
В двоичной системе трайт может быть представлен следующим образом:
01011000 11100100
Таким образом, двоичные аналоги троичных значений будут иметь:
1t = 10b ~ «истина»
0t = 00b ~ «не определено»
0t = 10b ~ «не определено»
-1t = 01b ~ «ложь»
Примечание: Как видно значение «не определено» может быть представлено двумя способами. Это связано с избыточностью возможных значений двух бит для представления одного трита.
3. Операции троичной логики
В двоичной логике есть шесть основных операций, которые не могут быть выражены друг через друга:
1. Отрицание («NOT», !);
2. Повторение («REP», ~);
3. Конъюнкция («AND», &);
4. Дизъюнкция («OR», |);
5. Исключающая дизъюнкция («XOR», ^);
6. Сдвиг («<<» и «>>»).
В скобках приведены обозначения операций, принятые в языке программирования Си (кроме п. 2, т. к. в Си нет операции повторения — прим. автора).
Во второй части было сказано, что анализ значения трита начинается с анализа значения полутрита. Если его значение «не определено», анализировать второй полутрит не имеет смысла — значением всего трита становится «не определено». Если значение трита определено, логические операции применяются к тритам аналогично битам.
Пример:
-1011 -1-1-10 & 000-1 11-10
Представим трайты в двоичной системе:
-1011 -1-1-10 = 01001111 01010100
000-1 11-10 = 00000001 11110100
Разделим трайты на управляющий и значащий байты (ЗБ — значащий байт, УБ — управляющий байт):
01001111 01010100 = 0011 0000 (ЗБ) 0011 1110 (УБ)
00000001 11110100 = 0000 1100 (ЗБ) 0001 1110 (УБ)
Произведем операцию, как с двоичными байтами:
0000 0000 (ЗБ) 0001 1110 (УБ) = 00000001 01010100 = 000-1 -1-1-10
Сдвиг осуществляется аналогично, только следует принять во внимание, что операция сдвига осуществляется над тритом, который в двоичной системе обозначается двумя битами. Другими словами:
-1011 -1-1-10 >> 2 = 01001111 01010100 >> 4 = 00000100 11110101 = 00-10 11-1-1
4. Троичная арифметика
Законы троичной арифметики аналогичны законам математики для троичной системы счисления. Для удобства представления чисел стоит принять, что
0t = 00b
1t = 01b
2t = 10b
Таким образом, алгебра логики сильно отличается от вычислительной алгебры. Для обозначения знака числа будет применяться полутрит со значением «11» таким же образом, как это происходит в двоичном представлении отрицательного числа.
Примечание: В начале статьи я намерено допустил неточность. Теперь очевидно, что значение одного трайта лежит в диапазоне ±1 143, что тем не менее больше диапазона ±128 почти в 9 раз.
4. Заключение
В статье я постарался кратко и по возможности доступно представить свое видение реализации троичных вычислений на двоичных системах. Конечно, без аппаратной поддержки троичная логика и арифметика могут стать скорее интересной забавой, чем найти серьезное применение.
Системы с сильно отличающейся от Intel архитектурой существуют и сейчас. Возможно когда-нибудь с целью снижения затрат и увеличения производительности гиганты мировой цифровой индустрии обратятся к разработкам 50-х годов: идея автоматического вычислителя родилась за много веков до появления порвого компьютера.
P.S. Пост выражает точку зрения автора и ни в коем случае не претендует на эффективность реализации или звание истины.
Автор: norn
