Троичный компьютер в браузере

    000. Предыстория


    В 1959 году Н. П. Брусенцов разработал для МГУ уникальную вычислительную машину «Сетунь». Она была основана на троичной системе счисления и хотя элементная база была частично двоичной, что приводило к перерасходу деталей, машина зарекомендовала себя как экономичная и надёжная. Сегодня троичную машину можно увидеть разве что в музее, двоичный код победил.

    Но, как я говорил ранее, всегда найдутся люди, готовые сохранять технологии прошлого в виде эмуляторов.

    00+. Теоретические основы


    В этой статье рассматривается троичная симметричная система счисления. Цифры в ней положительные и отрицательные, то есть -1/0/1 или более общепринятое -/0/+. Из этого свойства вытекает нативная поддержка нашим будущим компьютером отрицательных чисел.

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



    Существует формула y = ln(x)/x, физический смысл которой я понимаю как «соотношение объема хранимой информации к сложности ее хранения», где сложность возрастает по оси X.

    Главным же недостатком считается отсутствие базового элемента, который способен находиться в трех состояниях и при этом эффективно работать в режимах, пригодных для построения процессоров. Но для эмулятора это не проблема. Более того, схемы составных троичных элементов известны. Если прикинуть, сколько транзисторов в современных процессорах реально отвечают за систему команд, а сколько за оптимизации, то получится, что реализация самого троичного процессора не такая уж проблема.

    0+-. Предпосылки


    О работе Н. П. Брусенцова я узнал сравнительно недавно. Изучив некоторые материалы по Сетуни я понял, что нет необходимости проделывать весь путь заново и можно использовать знания наших дней. Насколько я знаю, троичная виртуальная машина была так же разработана в МГУ. Но материалов по ней мало, а исходников вообще нет.

    Как раз в этот момент Н. Вирт опубликовал первые наработки проекта Оберон 2013.



    Собственная система команд RISC-подобного процессора, простой язык и простой компилятор для него натолкнули меня на мысль о том, что неплохо бы соединить концепции двух умных людей в одну.

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

    Проект был доведен до стадии альфы и заморожен. И вот в 2015 году в процессе изучения языка Dart возникла идея реализовать порт эмулятора для браузера.
    Нетипичный для веба проект, много странных целей, что может быть интереснее?

    0+0. Цели и средства


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

    Так же, ради интереса, можно использовать собственные типы данных, которые будут характерны для троичных машин, а сам процессор реализовать в виде отдельных модулей, примерно соответствующих реальным блокам процессора — регистры, АЛУ и т.д. Плюсом будет использование множества фич Dart, ведь проект нужен для самообучения.

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

    0++. Математика


    Для начала реализуем логику и математику. Сразу интересно.

    Основной логический тип троичной системы — trilean (по аналогии с boolean). Русского аналога слову я не нашел. Для типа trilean существует три значения, true/null/false. Для этих значений существуют основные логические законы. Их сформулировал Ян Лукасевич в 20-х годах прошлого века. Из двух законов, отрицания и импликации выводятся все основные логические операции.
    Описав в Dart тип Tril, используем возможности перегрузки операторов.
    Немного тестирования, и тип готов. Используем фабричный конструктор, чтобы не плодить множество копий объектов типа Tril, своеобразная оптимизация.

    С целыми числами тоже не все так просто. Минимальной единицей информации является трит (по аналогии с битом). В проекте Сетунь использовался шеститритный трайт (по аналогии с байтом). В своем проекте я использовал девятитритный трайт, чтобы быть ближе к восьмибитному байту по размеру. И хотя на первый взгляд, девять больше восьми, этот факт окупается мощностью получившегося типа данных — 19683 значений. От -9841 до 9841 включительно. Без обратных дополнений, без необходимости отличать арифметический сдвиг от логического.

    В альтернативной вселенной у людей в 80-х не было проблем с умещением нужных символов в 256 значений одного байта. Опишем этот тип данных tryte на языке Dart, реализуем для него базовые арифметические операции.

    Дополнительно введем тип int27, как можно догадаться, в нем 27 тритов, это будет размером машинного слова в нашей системе. Конечно, 27 тритов умещают больше значений, чем 32 бита. Значения от -3 812 798 742 493 до 3 812 798 742 493. Тут можно сказать, что 64 бита уместят больше значений, чем 27 тритов, но при этом понадобится вдвое больше триггеров для такого регистра.

    Для самых требовательных можно ввести тип int81, который зарулит в минуса даже 128-битные числа. Кстати, можно заметить, что количество тритов увеличивается по степеням тройки.
    Реализуем тип int27 аналогично tryte.

    Дополнительным типом нашей математической подсистемы будет тип Trits, это аналог типа SET в Обероне. Типу SET посвящена отдельная статья Н. Вирта, где он называет тип SET недооцененным. Мы же оценим его по достоинству.

    Если кратко, то тип Trits (SET) представляет собой множество тритов. Он свободно конвертируем в целое число, но к типу Trits применимы все базовые операции над множествами, сложение, умножение и так далее. Поддержка данного типа упростит реализацию обработки некоторых инструкций в процессоре. А еще он поможет преобразовать троичное число в строку.

    Кроме троичной записи чисел символами -/0/+ существует также девятеричная форма записи троичных чисел, в ней символами являются ZXYW01234. Реализуем конвертеры для такой записи чисел.

    В качестве развлечения, не связанного с основной задачей — реализуем конвертер в троичную симметричную систему счисления с иррациональным основанием.
    Основанием выберем квадрат золотого сечения. Подобная система счисления называется фибоначчиевой. У нее есть интересное свойство — запись числа симметрична относительно ее нулевого разряда.



    Пример всех конвертеров в одной картинке.
    Проведем несколько тестов. Математическая подсистема готова.

    +--. Железо


    Для начала опишем память. Это довольно просто, память это просто массив трайтов. Мы дополним ее только одной функцией в виде дополнительного класса — возможность читать целые слова данных.

    Дополнительно, для памяти опишем MMU, устройство для управления доступом к различным областям памяти. Наше MMU простое, оно позволит подключиться к некоторым ячейкам памяти как к пинам ввода/вывода, а так же позволит использовать отрицательные адреса для доступа к этим пинам из исполняемых программ.

    Для процессора я использовал асинхронные возможности языка Dart. Каждый цикл процессора планируется на будущее и исполняется асинхронно. При этом я все же схитрил и ускорил исполнение, увеличив тактовую частоту в 100 раз. Получился своеобразный разгон. Итак, основная активность процессора происходит в методе next().

    Пришло время разработать систему команд процессора. Как я уже говорил, я основывался на материалах проекта Оберон 2013. Н. Вирт разработал простую систему команд для реализации своего RISC-процессора на ПЛИС. Я модернизировал эту систему команд для троичного кода. Двух- или трех-операндная арифметика, условные переходы, прямая и косвенная адресация памяти.

    В процессоре будет 27 регистров общего назначения, дополнительный регистр PC будет обозначать адрес расположения следующей команды в памяти, регистр IR будет содержать текущую команду. Также присутствует дополнительный трит NZ, который будет содержать дополнительный результат выполнения операций над регистрами. Некоторые регистры общего назначения заберет себе система Оберон для размещения адресов возврата, вершины стека и т.д.

    Как известно, процессоры RISC обычно используют отдельные команды для загрузки и выгрузки данных в оперативную память, а все операции проводят над регистрами и данными в них.

    Итак алгоритм действий процессора такой — из памяти читается слово по адресу PC, значение записывается в IR и отправляется дешифратору команд, который отправляет сигналы тем или иным блокам на выполнение действий. Такие действия могут поменять значение регистра, при этом в регистр NZ записывается информация о том, является ли значение нулем или оно больше нуля. Вот так, одним тритом отвечают на два вопроса. В последствии этот трит может быть использован при исполнении инструкции условного перехода. В результате выполнения команды меняется состояние памяти в местах, которые исполняемый код считает переменными, меняется адрес перехода процессора на следующем шаге, итерация завершается. Завершение работы процессора происходит при переходе на -1 ячейку памяти, так как в ней записана команда с форматом — (-13).

    Всю систему команд нет смысла расписывать. С ней можно ознакомиться в документе github.com/kpmy/tri/blob/master/doc/trinary-0.pdf.

    Общение с внешним миром происходит с помощью записи в ячейку памяти с предустановленным адресом значения, которое обработает хост-исполнитель. Например, можно таким образом реализовать примитивную отладочную консоль.
    Так как у нас веб-приложение, выведем эту консоль в аутентичном черном окошке с белыми буквами. Для этого воспользуемся готовым компонентом и возможностями стандартной библиотеки Dart по управлению веб-содержимым.

    +-0. Первые шаги


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

    Итак, для прошивки в память готового кода опишем класс-загрузчик, котовый будет загружать код с сервера и записывать его в память. Код в формате JSON, странно, но факт, ведь любой бинарный формат записи был бы не совсем совместим с троичным кодом.

    По канонам системы Оберон, загрузчик выполняет модификацию адресов перехода, простая математика вносит в код поправку на смещение кода загружаемого модуля относительно нулевой позиции, которую задает компилятор при компиляции.

    Отдельным модулем идет bootstrap, это несколько команд, которые установят в памяти константы машины (размер памяти, адрес таблицы модулей и др.) и переведет процессор на адрес первой исполняемой команды. Bootstrap был подготовлен вручную.

    Модуль Core создан по образу и подобию ядра системы Оберон, модулю Kernel, так как это ядро, в нем много прямых операций с памятью, реализация аллокатора динамических структур (глючит иногда) реализация перехватчика исключений и т.д,
    Как раз в модуле Core реализуем самую примитивную консоль. Для вывода строк и чисел будем записывать значения символов в ячейку памяти, как было описано выше. Платформозависимый модуль SYSTEM является виртуальным, его вызовы компилятор переводит непосредственно в машкод.

    Невыразительный скриншот.
    Проверить работоспособность получившейся виртуальной машины можно вот здесь. Конечно, комплексная отладка и процессора и компилятора одновременно привела к некоторым багам (которые я еще не нашел), но как proof of concept результат работы мне показался достаточным.

    +-+. Итоги


    В итоге мы получили вполне работоспособный, расширяемый во все стороны аналог процессора Н. Вирта из проекта Оберон 2013 с модификацией для троичной системы счисления и троичного кода и несколько модулей для работы в получившейся системе.

    В оригинальном интерпретаторе я предпринял попытку развить успех и реализовать общение с внешним миром по аналогу порта rs232, с файловой системой на основе протокола 9p. И вот с чем я столкнулся. И та и другая технология, хоть и декларируются кроссплатформенными, при вводе в понятие платформы тритов и трайтов стремительно теряют свою кроссплатформенность. Основа в виде байтов и битов делает портирование таких технологий нетривиальной задачей.

    Конечно, здесь можно возразить, что значимость и распространенность троичных систем равна нулю, но тут как в анекдоте про Вовочку, троичность есть, а слов про кроссплатформенность для нее нет. Возможно это является некоторым тормозом в распространении троичных систем. Ведь все и так работает.

    Лично я увидел только одно оправданное применение троичных машин — это организация защищенных от вторжений каналов связи. Ведь даже при наличии прямого доступа к каналу хакеру потребуется как минимум аппаратный дешифратор сигналов, который еще надо разработать. Таким образом, борьба брони и снаряда может дать жизнь промышленному применению описанных технологий.

    +0-. Ссылки


    Ну и пожалуй, несколько ссылок для тех, кто заинтересуется.

    +00. P.S


    Н.П. Брусенцов скончался 4 декабря 2014 года. Надеюсь, дело его жизни не будет забыто.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 96

      +7
      Брусенцов Николай Петрович… эх, когда то люди таки будут научатся писать эту фамилию, и оценят его огромный вклад в вычислительную технику…
      Я просто оставлю это здесь:
      ternarycomp.cs.msu.ru/
        –21
        Triple Level Cell (TLC) — новая технология памяти в SSD, одна ячейка хранит 3 бита информации или 8 уровней заряда.

        en.wikipedia.org/wiki/Multi-level_cell
          +14
          3 бита — это не три состояния.
            +2
            Зато 8 уровней заряда — это восемь состояний.
              +8
              Зато 2 трита это 9 состояний.
                –1
                Если 3 бита, то это не 8 уровней заряда, а комбинация из ячеек с двумя уровнями.
                  +3
                  нет, одна ячейка с 8 уровнями хранит 3 бита
                    0
                    Вы чего, люди?
                    Если 3 бита, то это не 8 уровней заряда, а комбинация из ячеек с двумя уровнями
                    1) Там именно восемь уровней заряда в одной ячейке — написано ясно и в комменте, и в статье по ссылке.
                    2) С чего это вдруг «если хранит три бита информации, то сделано из ячеек с двумя уровнями»? Одна шестнадцатиричная цифра на бумаге хранит четыре бита информации, например.

                    Пользуясь случаем, напомню, что сложная цифровая техника на самом деле и так имеет не два, а три состояния: https://ru.wikipedia.org/wiki/Высокоимпедансное_состояние

                    По теме этой восьмиуровневой ячейки — интересно, как удается надежно различать эти уровни. Двоичная арифметика тем и ценна, что есть всего два состояния, которые трудно спутать. К сожалению, в топике об этом ни слова (только график, который не имеет к этому отношения).
                      0
                      По теме этой восьмиуровневой ячейки — интересно, как удается надежно различать эти уровни.
                      Если бы удавалось различить надёжно — было бы интересно. А так… сотни, в лучшем случае тысячи, циклов перезаписи TLC-памяти откуда берутся, как вы думаете?

                      P.S. Хотя вот как раз трёхуровневая ячейка будет близка скорее к SLC, чем к MLC по надёжности…
                        0
                        Высокоимпедансное состояние совместно с нулем и единицой, это не совсем одно и тоже, что троичная система счисления и ячейка для трех байт. Высокоимпедансное состояние не несет себе информационной ценности (равноправной нулю и единице) и появилось в результате столкновения математической абстракции с физикой несовершенного мира. Но как прецедент, тоже интересно, да.
                    –4
                    Я не понимаю людей заминусовавших мой комментарий. Наверное, они невероятно горды за своей впечатляющую компетентностью и решили вершить справедливость здесь и сейчас.

                    Я всего лишь привел ближайший пример современной актуальной технологии, в которой используется нечетное число (а именно три) в качестве базового, атомарного элемента.
                      +9
                      Там ничего нечетного нет. Три — это число бит, которых достаточно для хранения того же количества информации. Это лишь сравнение с тем, чего физически там нет.

                      Но в целом аналогия действительно уместна по той причине, что хранится больше двух состояний в одном элементе. А ваш комментарий выглядит так, словно вы ячейку TLC выдаете за трит. Вероятно, потому и минусуют.
                  +2
                  Собираюсь сделать троичные светодиодные часы, где трит будет отображён двумя светодиодами +- (оба горящих и оба потушенных — это ноль), на часы 4 трита, на минуты тоже 4 трита, после 40 минут будет показывать, сколько осталось до следующего часа со знаком минус (4 трита позволяют показать от -40 до +40).
                    +2
                    Интересно, на каком уровне вы будете использовать троичное представление? Только для отображения значений? Или будете реализовывать схему троичного вычислителя в железе?
                    Кстати, похожая идея реализована в часах «Синхрон». Но мне показалось, что мозгу тяжело воспринимать и пересчитывать значения с приемлимой быстротой.
                      +1
                      В первой версии только для отображения значений, причём значащие нули можно показывать +-, чтобы было видно разрядность чисел в темноте. А потом можно будет реализовать эмулятор троичного компьютера, где часы это будет адрес, а минуты — машинный код по этому адресу. Каждый светодиод будет так же кнопкой, можно будет быстро выставлять нужные значения, как времени, так и значения адреса и машинный код при программировании этого компьютера. Купил уже корпус и кнопки со встроенными светодиодами (вот такие белые: www.aliexpress.com/snapshot/6417781181.html), осталось разработать схему, собрать её, и написать прошивку для микроконтроллера.

                      Вот пример троичных часов на JavaScript (с секундами, в железных часах секунд не будет): ibnteo.klava.org/idea/tclock2.html
                      Когда минуты минусовые, то на час больше показывает, к примеру 13:50 = 14:-10, читать следует «без 10 минут 14 часов», то же самое с секундами.

                      Считать просто, каждый разряд это +- 27 9 3 1, нужно просто сложить числа, с учётом знака.
                      Например +-0+ это +27-9+0+1=19
                    –14
                    Какое практическое применение этого? И еще:

                    Из этого свойства вытекает нативная поддержка нашим будущим компьютером отрицательных чисел.

                    Автор, а вы знаете как отрицательные числа в двоичной системе представлены?
                      +2
                      Насколько я знаю, отрицательное число в двоичной системе получается вот так. И как следует из названия, это именно представление об отрицательном числе, а не реальное отрицательное число.

                      А что значит «практическое применение»?
                        –1
                        А что такое «реальное отрицательное число»? В чем собственно преимущество здесь перед двоичной системой? В двоичной системе есть знаковый бит или это не «нативно»?

                        Практическое применение — это означает что применяемо на приктике и хотя бы выдерживает критику и конкуренцию с аналогами.
                          +2
                          Ноль это «0» и «0». Один это «1» и "+". До этого момента в двоичной системе все хорошо. Минус один это "-" и что?

                            0
                            Это "-" и 1, если в прямом коде. Но на практике используется дополнительный код для упрощения вычислений. То есть "-" и дополнение до двух.
                              +5
                              "-" это не цифра двоичного кода, это интерпретируемый как минус старший бит многобитного числа.
                                +1
                                Ну вас же вроде не смущает, что "+" — тоже не цифра двоичного кода. И если говорить в этих понятиях, то в троичном коде (-, 0, +) тоже особо много не представишь. Либо -0, 0 и +0, либо придется интерпретировать набор тритов как различные числа.
                                  0
                                  В троичном коде принято писать цифру 1 символом +, так как есть цифра -1, которую удобно обозначать через -. Стало быть, + это 1, как раз цифра двоичного кода.
                                  В любом случае, -0 это -3, а +0 это 3 в троичном коде.
                                    0
                                    У троичной системы есть плюсы, конечно же. Но из статьи и комментариев их осознать затруднительно, если не знать о них заранее. Затруднительно даже понять существование самого принципа симметричной записи цифр, который разительно отличается от привычной записи в любой системе счисления.

                                    Когда я писал про -0, 0 и +0, я подразумевал под знаком именно знак, а не разряд какой-либо системы счисления.
                                      0
                                      Если честно, экскурс в троичную СИ вышел чисто ознакомительным, другого я не планировал, все же статья про мой проект и память о Сетуни.

                                      Статья про троичную СИ скорее должна быть написана математиком. Если вообще получится все уместить в одну статью.

                                      А про +0/-0 вы не поясните подробнее?
                                        0
                                        Мое замечание о том, что в качестве знака числа используется один из битов в двоичной системе счисления, вы парировали тем, что это не знак, а старший бит, интерпретируемый как знак. То есть интерпретацию одной сущности как другой, вы считаете неподходящим явлением в обсуждаемой ситуации. Полагаю, в вашем понимании, это делает используемое представление не нативным, неудобным или же неугодным по любой другой причине.

                                        Раз есть условие, что цифру нельзя считать знаком, то вполне логично и обратное. Цифра остается цифрой, а знак остается знаком. При симметричной записи в троичной системе счисления мы оперируем тремя сущностями: "+", "-", «0». А так как цифрой является только одна из них, и это ноль, то и записать число, отличное от нуля, на первый взгляд, затруднительно. Наиболее отличающимися будут значения -0 и +0, то есть числа, стремящиеся к нулю слева и справа соответственно.

                                        Такое ограничение можно обойти, допустив, что число определяется количеством нулей, в него входящим. То есть +000 — это 3, а -00 — это -2.

                                        Но не принимайте мои слова всерьез. Сей диалог — лишь повод найти пищу для размышлений, попутно исчерпав тему. Доводы строятся на догадках и допущениях с небольшими вкраплениями иронии. Ведь даже в пределах этого комментария я намеренно использовал в качестве представления состояний трита наиболее удобные для того, чтобы мои слова не выглядели чистой ересью.
                                          +1
                                          То есть интерпретацию одной сущности как другой, вы считаете неподходящим явлением в обсуждаемой ситуации. Полагаю, в вашем понимании, это делает используемое представление не нативным, неудобным или же неугодным по любой другой причине.
                                          Не знаю, почему kpmy это опустил, но с симметричной троичной системой тритовый сдвиг и целочисленное умножение/деление на 3 — одно и то же для любых чисел. А с двоичной системой с таким способом записи числа двоичный сдвиг отрицательных чисел официально не определён. И в соседних темах с рекламой PVS-Studio вы теперь видите небезосновательную ругань статического анализатора на такие вещи.
                              –1
                              Так, давайте сначала, вы написали:

                              Из этого свойства вытекает нативная поддержка нашим будущим компьютером отрицательных чисел.

                              «отрицательных чисел», в множественном числе сказали вы, мне кажется один из нас не понимает о чем говорит.
                                +1
                                Отрицательные числа представляются нативно так как в троичной симметричной системе, на которой основан компутер есть цифра -1. Искаропки. Этого достаточно, чтобы представить -1, -2, -3 и т.д. таким же образом, как в двоичной системе представлены числа 1, 2, 3 и т.д.
                                  –1
                                  Еще раз в чем тут «нативность»? Для двоичной системы все отрицательные числа будут со знаковым битом, все положительные — без оного, а единственное число 0 которое посредине примет в жертву младшую цифру в разрядности -127 (к примеру для байта) — где здесь пресловутая «нативность»? Следуя вашей логике двоичная система так же нативная — так как в ней отрицательные числа с 1 преставляем, а положительные с 0.
                                    +2
                                    Костыли-костылики.

                                    В троичной системе минус просто есть. Один трит точно отвечает на вопрос о знаке числа. А в двоичной для обозначения минуса нужен дополнительный бит. А это уже интерпретация информации. Которая зависит от наблюдателя.

                                    Просто смиритесь с тем, что это логика такая неумолимая, у вас всего два варианта минимального количества информации, а у меня три. Применительно к арифметике эти три варианта обозначают знак числа. А вам нужен еще один дополнительный вопрос для его описания. Если вы подберете слову «нативность» русскоязычный аналог, он и будет ответом на ваш вопрос. Мой вариант — отрицательное число получается «само собой».
                                      –1
                                      Вы что-то не понимаете, в троичной системе одним тритом вы можете представить всего три числа -1,0 и 1. Для -2 и дальше вам уже понадобиться два и больше разрядов итд. Так в чем тут «нативность»?
                                        0
                                        Ваша претензия, по существу, относится к изобретателям разрядов в системах счисления. И даже в этом случае, ваш старший бит в отрицательном числе на самом деле является старшим разрядом положительного числа, который вы ИНТЕРПРЕТИРУЕТЕ как знак минус. Да, и впрямь, интерпретация старших битов это нативное свойство двоичных машин. Только при чем тут отрицательные числа?
                                          +1
                                          Как в троичной системе хранят числа из многих разрядов? Будет ли при этом знак содержаться только в одном из разрядов, то есть будет ли один из разрядов интерпретироваться отлично от остальных? Если ответ «да», то в чем принципиальное отличие от двоичного кода?
                                            0
                                            В троичной симметричной системе число -5 равно -9+3+1, то есть -++. Математически очевидный способ хранения отрицательных чисел. Нет никакого «хранения знака».
                                              0
                                              Спасибо, начинаю понимать. Но как в такой ситуации определить знак числа? Если я понял верно, то для этого может потребоваться пройтись по всем разрядам. В двоичной системе для этого достаточно пощупать первый разряд.

                                              Пригодилась бы табличка перевода в троичную чисел от -100 до 100. Посмотрел в википедии, там всё обозначают по-другому.
                                                0
                                                Знак числа определяется знаком старшего разряда. Сумма младших разрядов в любом случае его не превысит по модулю.
                                                  0
                                                  А если старший разряд равен 0?
                                                    0
                                                    Старшего значащего разряда. Для проверки на ноль тоже нужно пройтись по всем разрядам, но это не вызывает проблем.
                                                  +1
                                                  Для примера
                                                  gist.github.com/kpmy/22338f6359056b07413e

                                                  ...
                                                   -9 [000000000000000000000000-00] Z0 -9
                                                   -8 [000000000000000000000000-0+] Z1 -8
                                                   -7 [000000000000000000000000-+-] Z2 -7
                                                   -6 [000000000000000000000000-+0] Z3 -6
                                                   -5 [000000000000000000000000-++] Z4 -5
                                                   -4 [0000000000000000000000000--] 0W -4
                                                   -3 [0000000000000000000000000-0] 0X -3
                                                   -2 [0000000000000000000000000-+] 0Y -2
                                                   -1 [00000000000000000000000000-] 0Z -1
                                                   0 [000000000000000000000000000] 0 0
                                                   1 [00000000000000000000000000+] 01 1
                                                   2 [0000000000000000000000000+-] 02 2
                                                   3 [0000000000000000000000000+0] 03 3
                                                   4 [0000000000000000000000000++] 04 4
                                                   5 [000000000000000000000000+--] 1W 5
                                                   6 [000000000000000000000000+-0] 1X 6
                                                   7 [000000000000000000000000+-+] 1Y 7
                                                   8 [000000000000000000000000+0-] 1Z 8
                                                   9 [000000000000000000000000+00] 10 9
                                                  ...
                                                  
                                                    0
                                                +1
                                                Ага, а вы почему-то число 010, записанное в троичной системе счисления, интерпретируете как минус единицу, когда 010==03, и вовсе не −13, которое вы записываете как «−» непонятно почему.

                                                110==13, а вовсе не 03.
                                                210==23, а вовсе не 13, которое вы записываете как «+».

                                                Скажу даже больше. Знак числа вообще никоим образом не записывается системой счисления.

                                                −610==−1102.

                                                То, чем вы здесь занимаетесь, называется кодированием информации, а именно — чисел ∈ ℤ.
                                                Здесь вам показалось удобным кодировать с использованием троичной системы счисления так, что при кодировании числа −110 в вашем коде оно записывается как 03, или «−». И всё.

                                                Это никоим образом не отличается от того, что вы имели в виду, когда писали капсом «ИНТЕРПРЕТИРУЯ». Точка.

                                                Это вообще относится только к целым числам. Захочется вам записать десятичную дробь, вообще любое рациональное число, или записать иррациональное число с бесконечной точностью (а не все иррациональные числа выразимы через радикалы), или вовсе кватернион — вам безусловно потребуется вообще иной способ кодирования чисел. И сможете ли вы (или кто иной) извлечь пользу из троичного бита — отдельный вопрос.

                                                Disclaimer: я не являюсь ярым адептом двоичной логики и не пытаюсь сравнивать двоичную и троичную систему счисления в применении к вычислительным машинам, но не надо так обращаться с математикой.
                                                  +2
                                                  Знак числа вообще никоим образом не записывается системой счисления.

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

                                                  И да, именно в симметричных позиционных системах счисления знак числа не надо записывать отдельным символом, потому что строение такой системы счисления позволяет исключить использование знака «-» вообще.

                                                  Хочу заметить, что позиционные симметричные системы счисления ещё не самые взрывающие мозг, и они довольно удобны в использовании. Если прогуляться хотя бы до википедии (я уж не говорю про учебники), то можно найти много примеров куда более экзотических.
                                                    +1
                                                    О! Спасибо.

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

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

                                                    Просто следовало бы заранее сказать, что впредь под «троичная система счисления» будет пониматься «троичная симметричная система счисления».
                                    +3
                                    В целом, я не понимаю вашего вопроса про практическое применение троичного кода. Оно такое же, как и у двоичного кода. То есть, машинное представление всего подряд.
                                    У троичных систем те же цели и задачи, что и у двоичных. Просто двоичные победили.
                                    Но есть нюансы. К примеру, в системе команд процессора Вирта в одном слове выделяются разные блоки битов, отвечающие за адресацию регистров. 4 бита могут адресовать 16 регистров, а 4 трита — 81 регистр. Без ухищрений и увеличения размера слова. То есть, троичная электроника, при наличии в этой вселенной условного троичного транзистора повышает плотность хранения информации на элемент хранения.
                                      0
                                      «троичного транзистора повышает плотность хранения информации на элемент хранения»

                                      В математической модели (т.е. на бумаге) — да, в реальной жизни — нет (физика и химия не дают это сделать)
                                        +1
                                        Вы реалист, это похвально.
                                        +1
                                        А можно предположить условный транзистор, хранящий 4 состояния, и назвать его квадритом. 4 квадрита будут адресовать 256 регистров. Квадрит, как и трит, можно эмулировать на обычных битах. Только эмуляция квадрита будет более эффективной.

                                        Но можно пойти еще дальше. В SSD применяется технология TLC (упомянута во втором комменте к посту). Там ячейка может хранить 8 состояний. 4 октитов (как легко вводятся эти названия, оказывается) хватит для адресации 4096 регистров. И элементная база существует. Но нет теоретической базы, которая давала преимущество перед привычными битами.

                                        Вы говорите о плотности хранения информации на элемент хранения. Но не забывайте про то, что количество информации на элементе не интересно. Куда важнее ее количество на единице объема.
                                          +3
                                          График в начале статьи, в моем представлении, показывает, что система из 4-х состояний не даст большей эффективности хранения, чем двоичная система, так как сложность хранения будет выше.
                                            –6
                                            График в начале статьи с таким же успехом может показывать отношение длины члена Х в дециметрах на велечину индеферентности Y. И да, он вообще не связан с предствленой в статье формулой y = ln(x)/x
                                              +3
                                              Аргументы еще принимаются? Или вы уже перешли к оскорблениям?
                                                +2
                                                Конечно, непонятно, почему Maur утверждает, мол, что
                                                И да, он вообще не связан с предствленой в статье формулой y = ln(x)/x
                                                Картинка в посте — вполне себе график f(x)=ln(x)/x, другое дело, что можно было бы его исполнить и получше:

                                                kpmy, если хотите, можете использовать мою каринку в вашей блогозаписи (если необходимо большее разрешение, напишите в личку).

                                                Однако к первому пункту комментария хабрачеловека Maur:
                                                График в начале статьи с таким же успехом может показывать отношение длины члена Х в дециметрах на велечину индеферентности Y.
                                                я не могу предьявить никаких претензий, и в целом с ним согласен.

                                                kpmy, скажите пожалуйста, где можно увидеть доказательство следующего вашего тезиса?
                                                Существует формула y = ln(x)/x, физический смысл которой я понимаю как «соотношение объема хранимой информации к сложности ее хранения», где сложность возрастает по оси X.
                                                Вообще, я слабо понял этот тезис, если не сказать, что не понял вообще. Что означает слово «соотношение»? Каким образом зависимость не очень понятно чего от не очень понятно чего в вашем, kpmy:
                                                в моем представлении
                                                представлении оказывается близка к функции f(x)=ln(x)/x?
                                                  0
                                                  Сейчас расскажу, а вы поправьте, если что не так.

                                                  Есть понятие экономичность. С математической точки зрения это некое отношение логарифма к аргументу логарифма. Прикольно, но суть непонятна.

                                                  Вот я так понимаю, что чем больше базовых состояний, тем сложнее их хранить. Пусть сложность хранения линейно возрастает с количеством значений. То есть по X одновременно и количество уровней и сложность их хранения.

                                                  А логарифм это такой показатель степени числа, которое может содержать разряд x-ичной системы.
                                                  Для меня непонятным остается, почему натуральный логарифм, а не другой.

                                                  То есть, рабоче-крестьянский смысл в том, что два состояния хранить просто, но и емкость маловата, три состояния хранить сложнее, но емкость больше, у четырех емкость больше, но хранить настолько сложно, что выгода теряется, по экономичности даже хуже чем хранить два состояния.
                                                    +1
                                                    Для 4 и 2 величина log(x)/x совершенно одинакова.
                                                    Какой логарифм брать — натуральный или по любому другому основанию, не важно — они отличаются в константу раз.
                                                    Но само по себе понятие «экономичности» выглядит странно. Потому что его основное положение — «количество ресурсов для хранения одной цифры пропорционально основанию системы счисления». Честно говоря, я не вижу в реальной жизни ситуации, где это бы выполнялось. Разве что в доске вроде абака, где значение цифры представлено положением камешка, лежащего в одной из N лунок. Уже в счётах для представления цифры хватило бы N-1 костяшки. А в электронике технические детали полностью скрывают эту стройную картину — всё зависит от конкретной реализации.
                                                      0
                                                      Ну смотрите, чтобы сохранить число
                                                      443 426 488 243 038 000 000 000 000 000 000 000 000
                                                      нужно спаять 81 троичный триггер.
                                                      А чтобы сохранить число
                                                      340 282 366 920 938 000 000 000 000 000 000 000 000
                                                      которое, кстати, меньше предыдущего, нужно спаять 128 двоичных триггеров.
                                                      Больше в 1,6 раз. Учитывая, что к каждому триггеру надо подвести провод, по которому данные пойдут в сумматор с таким же количеством разрядов, можете представить, как растут расходы на провода.
                                                        +2
                                                        А десятичных триггеров (если под «триггером» вы понимаете объект, в котором хранится одна цифра) понадобится всего 39. В 2.07 раза меньше, чем троичных. А 1000-ричных — ещё втрое меньше. Здесь надо считать расходы на реализацию конкретного триггера. И как она зависит от числа значений — кто его знает…
                                                        +2
                                                        Важно, потому что теория информации выделяет e и натуральный логарифм среди всех прочих.

                                                        Как отмечает создатель уникального троичного компьютера Н.П. Брусенцов, главное
                                                        преимущество троичного представления чисел перед принятым в современных компьютерах двоичным состоит не в иллюзорной экономичности троичного кода[1]. В данном случае речь идет об утверждении высказанном и доказанном в свое время одним из основателей информатики Джоном фон Нейманом(John von Neumann).
                                                        Это теорема о представлении некоторого числа n минимальным набором символов в
                                                        определенной системе счисления. Её основанием является число e — основание натуральных логарифмов. С математической точки зрения доказательство сводится к поиску экстремума функции ( f(x) = x^(n/x) )
                                                        На рис. 1 приведен график этой функции для n= 8.
                                                        image

                                                        На практике это утверждение воспринимается как интересный факт и используется для оценки «идеальности» системы счисления. Если рассматривать представление чисел только в этом аспекте, то действительно3 находится ближе к е чем2. Это, тем не менее, не является тем решаюшим критерием, по которому использование троичной сбалансированной (уравновешанной, симметричной) системы счисления более удобно в реальных условиях. Для того чтобы понять в чем удобство упомянутого представления нужно сравнить его с традиционным двоичным. Далее приводятся основные характеристики, определяющие практическую ценность троичного кода и трехзначной логики.
                                                        • имеет место естественное представление чисел со знаком, т.е. не нужно пользоваться
                                                        искусственными приемами типа прямого, обратного или дополнительного кода
                                                        • знак числа определяется знаком старшей ненулевой цифры и не нужно использовать
                                                        специальный знаковый бит, как в двоичной системе
                                                        • просто производится сравнение чисел по величине, при этом не нужно обращать
                                                        внимание на знак числа
                                                        • в соответствии с этим команда ветвления по знаку в троичной машине занимает в два
                                                        раза меньше времени, чем в двоичной
                                                        • усечение длины числа равносильно правильному округлению; способы округления,
                                                        используемые в двоичных машинах, не обеспечивают этого
                                                        • троичный сумматор осуществляет вычитание при инвертировании одного из слагаемых,
                                                        откуда следует, что троичный счетчик автоматически является реверсивным
                                                        • в трехвходовом троичном сумматоре перенос в следующий разряд возникает в8
                                                        ситуациях из27, а в двоичном сумматоре- в4 из8. В четырехвходовом сумматоре
                                                        перенос также происходит только в соседний разряд.
                                                        • таблицы умножения и деления почти так же просты, как и в двоичной системе,
                                                        умножение на-1 инвертирует множимое
                                                        • трехуровневый сигнал более устойчив к воздействию помех в линиях передачи. Это
                                                        означает что специальные методы избыточного кодирования троичной информации
                                                        проще, нежели двоичной (вот с этим, кстати, не согласен — два уровня определить намного проще, чем один. мб что-то другое имелось ввиду)
                                                          0
                                                          А можете, пожалуйста, пояснить, каким образом получается функция f(x)=x^(n/x)? Это функция чего от чего?
                                                          Это теорема о представлении некоторого числа n минимальным набором символов в
                                                          определенной системе счисления.
                                                          Я подумал, что это могло бы быть функцией количества символов, необходимых для представления числа n в системе числения с базисом x от x, так как из цитаты понятно, что именно эту функцию и хотят минимизировать (процесс минимизирования приведён на картинке), но при быстрой проверке в уме, положив n=4, x=10, я получаю f(x)=4^(4/10)=2^(4/5), что примерно равно 1.7411, что даже после округления (!) даёт 2, а вовсе не 1, хотя именно единица — количество символов, необходимых для представления числа n=4 в системе с базисом x=10 (десятичной).

                                                          Что-то не сходится. Не поясните?
                                                            +1
                                                            Похоже, что это максимальное число, которое можно показать на арифмометре, у которого на всех кольцах в сумме n цифр (т.е. число разрядов, умноженное на основание системы счисления равно n). Тогда x — заданное основание.
                                                            Например, при n=60 получаем:
                                                            f(2)=2^30 = 1073741824
                                                            f(3)=3^20 = 3486784401
                                                            f(4)=4^15 = 1073741824
                                                            f(5)=5^12 = 244140625
                                                            f(e)=e^(60/e) = 3855499742
                                              0
                                              Это называется экономичность.
                                      0
                                      Глядя на то, как вы нумеруете главы, не совсем понятно, как же в троичной системе «естественным» образом получаются отрицательные числа. Не могли бы вы пояснить?
                                        0
                                        0 — 1 = -1; «0» — "-" = "-";
                                        -1 — -1 = -2, но -2 запрещено, поэтому имеем -3 в старшем разряде, "-" — "-" = -+; и так далее.
                                        Применительно к электронике "+" и "-" это два полюса двуполюсного ИП. Естественный минус 1.
                                          0
                                          «0» — "-" = "-"; — это разве не «0 минус (-1) = -1»? Как-то странно.
                                            +1
                                            Да, простите, я с минусами запутался.
                                            Папа решает, а Вася сдает.
                                          +4
                                          В симметричной системе счисления в каждом разряде присутствует знак, знак старшего не нулевого разряда по сути является знаком всего числа. При этом складывать и вычитать числа можешь поразрядно, не учитывая знак числа. Удобно округлять, просто отбрасывая или обнуляя младшие разряды. Удобно производить операции с числами разной разрядности.

                                          Инвертировать знак всего числа можно операцией инвертирования знака всех разрядов, был 0+- (0+3-1=+2), сделали 0-+ (0-3+1=-2).

                                          1 (0+); 2 (+-); 3 (+0); 4 (++)
                                          -1 (0-); -2 (-+); -3 (-0); -4 (--)
                                            0
                                            Спасибо, так гораздо понятнее!
                                          +1
                                          MLT-3. Только ради 100BASE-TX троичные роутеры, конечно, никто делать не станет. Но в качестве аппарата для взаимодействия двоичных и троичных систем, наверное, представляет интерес.
                                            0
                                            MLT-3 используется для согласования цифрового сигнала, переносящего биты, и линии связи: делается shaping спектра мощности, за счёт чего уменьшается его ширина, что позволяет втиснуть в витую пару третьей категории сигнал со скоростью переключения 125 миллионов импульсов в секунду.
                                            То есть это просто сигналы и ничего более — биты остались битами.
                                            Пример shaping spectrum по MLT-3
                                            yadi.sk/i/6UvrEnLgfejSj
                                              0
                                              Я в курсе, для чего это сделано. Не мешайте фантазировать :)

                                              Есть линия, которая позволяет передавать троичные символы. И есть код, который определяет способ передачи двоичной последовательности с их помощью, позволяющий получить определённую форму спектра.

                                              Исходный комментарий и для меня сейчас не очень хорошо выглядит. Разумеется, сам по себе MLT-3 создан только для передачи двоичных данных. Интерес может представлять PHY в целом, как отправная точка для реализации троичного канала связи.

                                              Вот решит кто-то перенести эксперименты из браузера на FPGA и разработать протокол взаимодействия между троичными устройствами. А там уже 100 Mbps PHY есть. Правда, существует ли реализация PHY, которая позволит такое издевательство над собой (передачу произвольных троичных символов) — это тоже большой вопрос :(

                                              А ещё в этот раз я даже не говорю о взаимодействии двоичных и троичных систем. Это, похоже, задача совсем другого рода. Некий чёрный ящик с информацией о представлении форматов одних и тех же данных в двоичном и троичном мире.
                                                0
                                                Кстати, как (чем) график построен?
                                                  0
                                                  На Qt Plotter, который есть в книжках Бланшета. А по факту — усреднялся (300 реализаций) квадрат модуля спектра, полученного с помощью БПФ, то есть прямое моделирование прямоугольных импульсов в дискретном виде (плюс использовалось окно Блэкмана для снижения уровня боковых).
                                                  До аналитики функции корреляции MLT-3 я не дошёл :).
                                              –1
                                              У вас опечатка, вот тут:
                                              Она была основана на троичной системе счисления и хотя элементная база была частично двоичной, что приволило к перерасходу деталей, машина зарекоменловала себя как экономичная и надёжная.


                                              А статья хорошая, да и тема очень интересная.
                                                0
                                                Спасибо.
                                                +1
                                                Эх, были времена, когда я много интересовался троичной логикой :)
                                                Но, конечно, это все на бумаге красиво.
                                                Потому что даже через функцию Вебба в двоичной логике все операции выражаются гораздо проще, чем в троичной.
                                                  0
                                                  Не могли бы пояснить для народа чем проще? Очень интересно
                                                    +1
                                                    В двоичной логике инверсия выражается такой формулой:

                                                    Not(x) = Webb(x, x)

                                                    А в троичной такой:

                                                    Inc(x) = Webb(x, x)
                                                    Dec(x) = Inc(Inc(x))
                                                    Not(x) = Webb(Webb(Dec(x), Inc(x)), Inc(Webb(Dec(x), x)))

                                                    Оцените количество операций самостоятельно :)
                                                    P.S. Искал этот коммент на хабрахабре, но в итоге нашел его на geektimes.
                                                      0
                                                      С другой стороны, вентили для выполнения таких операций строятся на основе таблиц истинности, а они известны наперёд.
                                                • UFO just landed and posted this here
                                                    +1
                                                    Если говорить о железной реализации — для троичной симметричной системы могут быть реализованы элементы с двуполярным питанием, которое будет выражать -/0/+. Говорят, что это хорошо. Сам я не особо железячник, на эту тему могу рассуждать только поверхностно.
                                                    Сам я пробовал симулировать схему (схемы) троичных вентилей на двуполярных источниках питания. Могу только сказать, что оно работает.
                                                      0
                                                      Ваш вопрос про цвета я не понял.
                                                      0
                                                      Троичный код идеален для электрической среды. Для передачи данных к примеру rs485, PCM (ИКМ), но в настоящее время средой передачи данных, все больше, является ВОЛС. Оптика разве может быть троичной?
                                                        0
                                                        Оптика разве может быть троичной?

                                                        Если учитывать поляризацию, то сколь угодно N-ричной…
                                                        Без поляризации — нет.
                                                          0
                                                          A если учитывать разные длины волн?
                                                            0
                                                            Так скорость же будет разной.
                                                              0
                                                              Замечательно. Ещё один способ разделить разные значения сигнала.
                                                                +1
                                                                А ловить-то цифры как будем? Хотелось бы чтоб они в каком порядке ушли, в том и пришли.
                                                              0
                                                              Ну да. Когда я только знакомился с оптикой, закладывался многомодовый кабель как раз с расчетом на такую перспективу.
                                                              Но в итоге основная масса используют одномод. Аргументируя тем что сам кабель еще и выступает в качестве фильтра.

                                                              А если ближе к теме, то на практике мы все же редко встречаемся с отрицательными числами. И как правило любая физическая величина может быть отображена положительными числами. Все зависит от системы измерений.
                                                              Хотя признаю, что мое мышление именно на это ориентировано и трудно себя перебороть на использование троичной системы.
                                                          0
                                                          Насколько я знаю, «Сетуней» было сделано несколько, и один из них до сих пор используется в «продакшене», скажем так. Где — не скажу, не для энторнетов это :)
                                                            0
                                                            Не иначе в НИИЧАВО «Алдан» проапгрейдили?
                                                              –1
                                                              Как мы помним, «Алдан» «вместо того, чтобы считать в двоичной системе, непонятным мне образом переходил на древнюю шестидесятиричную» :)
                                                                0
                                                                Вот и проапгрейдили. С двоичной на троичную.
                                                            0
                                                            Интересная статья, интересные комменты.
                                                            А почему победила двоичная электроника? :) Наверняка, много причин, как «железных» так и «бумажных».
                                                            И я думаю, одна из них, что отрицательные числа в большинстве задач и не нужны. То есть их нативная поддержка теряет привлекательность.
                                                              +1
                                                              Ну, сложный вопрос. Думаю, многим свойственно так рассуждать, положительных чисел достаточно, двоичного кода достаточно, скопировать западные образцы достаточно, 640 килобайт достаточно. Вон, свежая статья на гиктаймсе про юникод, им вот тоже достаточно, одного байта для всех английских символов достаточно, остальные пусть строят костыли. Не стану гадать, не знаю более конкретных причин отказа, может не осилили взять на себя ношу изобретения, когда надо сопровождать свои решения десятилетиями, проще взять уже готовое. На западе с двоичным computer science справляются, теория и практика развивается, а на востоке со своим троичным не срослось. Остается только эмуляторы писать.
                                                              –3
                                                              Потому что двоичную логику можно реализовать «нативно» — вкл-выкл, есть напряжение-нет, транзистор закрыт-открыт, магнитный заряд есть-нет. Троичную логику афайк можно только эмулировать. А на эмуляции все преимущества и теряются. Нельзя «полуоткрыть» транзистор.

                                                            Only users with full accounts can post comments. Log in, please.