Эмуляция троичной системы. Вариант концепции

    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. Сдвиг («<<» и «>>»).
    В скобках приведены обозначения операций, принятые в языке программирования Си (кроме п. 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. Пост выражает точку зрения автора и ни в коем случае не претендует на эффективность реализации или звание истины.
    Поделиться публикацией
    Комментарии 24
      +6
      В двоичной логике есть шесть основных операций, которые не могут быть выражены друг через друга:

      XOR вполне себе выражается через AND, OR и NOT.
        +7
        Функциональная полнота, если мне память не изменяет, причем можно даже через пары И-НЕ или ИЛИ-НЕ (КНФ и ДНФ).
          +4
          Память вам немного изменила. КНФ и ДНФ — это представления в базисе (И, ИЛИ, НЕ).
          Но вы правы, базис И-НЕ тоже существует.

          Вообще, в двоичном базисе может быть от 1 до 4х функций, причем все варианты осуществимы.
            0
            от 1? это xor в смысле в базисе?
              +4
              Нет, с xor не получится, она линейная. Но есть функции, с которыми получится:
              ru.wikipedia.org/wiki/Штрих_Шеффера
              ru.wikipedia.org/wiki/Стрелка_Пирса
                +1
                Во, точно, я стрелку пирса забыл :)

                а вот на штрихе первый раз слышу, чтоб собралась полная система. пойду погуглю.
                туплю. это ж фактически инверс стрелки. логично, ага :) ИЛИ-НЕ и И-НЕ.
                старая добрая 155я серия… любимая ЛА3…
          0
          Спасибо. Прошляпил.
          0
          Если в двоичной системе 1 байт = 8 бит, то в троичной наверное правильней было бы 9 трит? Все таки 3^3 = 9.
            +7
            Таки 3^3 = 27
              +3
              Если в двоичной системе 1 байт = 8 бит, то в троичной наверное правильней было бы 9 трит? Все таки 3^3 = 9.
              Конкретное количество битов в байте 1.) не имеет никакого отношения к разрядности системы 2.) ничем не определено даже для двоичной системы. Байт — это от «binary term» и конкретного размера по определению не имеет.
                0
                Конкретное количество битов в байте 1.) не имеет никакого отношения к разрядности системы
                Я тут фигню сказал какую-то, байт — он и так только в двоичной системе, конечно. Имелось ввиду по аналогии трайты и т.п.
                0
                Один трайт был принят равным восьми тритам для возможности сравнения с байтом из восьми бит. безусловно, договоренность может быть любой.
                0
                Было бы здорово, если б кто-то привел конкретные или даже реальные (если есть) примеры использования троичной логики и насколько оно себя в этих случаях оправдывает.
                  +2
                  Так вроде же были Советские ЭВМ на троичной логике, если не ошибаюсь.
                  UPD: Троичный компьютер
                    +1
                    Были. Я имею в виду современные реализации.
                      0
                      Читайте внимательнее. Там есть ссылки на современные работы.
                        +1
                        Пока я писал комментарий, вы изменили свой )
                        UPD: спасибо
                    +1
                    квантовые компьютеры в общем случае можно привести к троичной логике
                      0
                      Квантовый комп — это недетерминированная машина Тьюринга, зачем ее приводить к детерминированной? Это лишено смысла.
                    +3
                    Почему во втором разделе была явно введена симметричная система (-1, 0, 1), а в разделе про троичную арифметику автор вдруг снова возвращается к обычной (0, 1, 2) со всеми проблемами представления отрицательных чисел?
                      0
                      Для удобства восприятия троичного представления через двоичное. Не явно знак присутствует и в т.н. «несбалансированной» троичной системе, если ее представление осуществляется через двоичную (избыточность двух бит для представления одного трита). Возможно, не самый оптимальный метод. Очень прошу: если есть идеи — поделитесь. Буду только благодарен.
                      +2
                      1. Отрицание («NOT», !);
                      2. Повторение («REP», ~);

                      В скобках приведены обозначения операций, принятые в языке программирования Си (кроме п. 2, т. к. в Си нет операции повторения — прим. автора).

                      Зато в языке C есть унарный оператор ~. Это как раз и есть побитовое отрицание. Его следует написать напротив NOT. А! — это логическое отрицание.
                        0
                        Большое спасибо. Исправил.
                        0
                        Насколько я помню, единственным полезным свойством троичных вычислений является симмтерия относительно нуля, которая означает, что при округлении у нас не возникает систематической ошибки, как при использовании чётных систем счисления.

                        Речь про вековечную проблему «куда округлять 0.5 до целых?». В нечётной системе счисления всё просто — там эквивалента 0.5 просто нет.

                        В условиях плавающей запятой с ограниченной мантисой это значительно повышает точность вычислений.

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

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

                        Самое читаемое