Троичная система счисления - позиционная система счисления с целочисленным основанием, равным 3.

Существует в двух вариантах: несимметричная и симметричная.

В несимметричной троичной системе счисления чаще применяются цифры {0,1,2}, а в троичной симметричной системе счисления знаки {-,0,+}, {-1,0,+1}, {1,0,1}, {1,0,1}, {i,0,1}, {N,O,P}, {N,Z,P} и цифры {2,0,1}, {7,0,1}. Троичные цифры можно обозначать любыми тремя знаками {A,B,C}, но при этом дополнительно нужно указать старшинство знаков, например, C>B, B>A.

Цифры в троичной симметричной системе целесообразно обозначать их знаками, т.е. вместо 1, 0, -1 писать +, 0, -. Например, десятичные числа 13, 7, 6, -6 в такой троичной записи будут:

13 = +++
7 = +-+
б = +-0
-6 = -+0

Изменение знака числа в симметричном коде равносильно потритной инверсии, т.е. взаимозамене всех “+” на “-” и всех “-” на “+”.

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

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

Если общее количество состояний равно m, то количество триггеров равно m/b, а количество представимых ими чисел соответственно - b^(m/b). Как функция от b, это выражение достигает максимума при b равном числу e = 2,718281828…. При целых значениях b максимум достигается для b = 3. Таким образом, наиболее экономичной является троичная система счисления (используемая в троичных ЭВМ), следом за которой идут двоичная система счисления (традиционно используемая в большинстве распространённых ЭВМ) и четверичная система счисления.

Немного философии

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

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

Почему именно двоичная логика стала базой современных ЭВМ? Ответ представляется очевидным. Исторически математическая логика опиралась на идею "третьего не дано", сводя процесс логических умозаключений к бинарным решениям.

Эта догма классической логики обязана рождением принципу бивалентности логических суждений, введённому яростным стоиком Хризиппом и поддерживаемому авторитетом Аристотеля. "Фундаментом диалектики служит тезис, что всякое высказывание (то, что называют "аксиомой") или истинно, или ложно", - говорил Цицерон.

Простота бивалентности действительно неплохо описывает логические реалии жизни. Стоит вспомнить семафоры, пешеходные переходы и тумблеры "вкл-выкл". Бинарность неплохо управляет повседневностью.

Давайте взвесим на обычных рычажных весах два предмета А и В. Весы с лёгкостью позволят определить нам две противоположности: вес А > В и вес А
Логику повседневной жизни сложно впихнуть в чёрно-белую картину бивалентности - это осознавали многие мыслители. В результате на свет появились неклассические логики, отказавшиеся от закона исключённого третьего. Один из первых вариантов многозначной логики в двадцатых годах прошлого столетия разработал польский учёный Ян Лукасевич. В его трёхзначной логике кроме полярных "да" и "нет" появилось значение "возможно". Трёхзначные логические высказывания Лукасевича допускали отсутствие непротиворечивости и назывались модальными. Помните консилиум в сказке о Буратино? "Пациент скорее жив, чем мёртв". "Скорее жив" и есть модальное логическое высказывание.

Льюис Кэролл (Чарльз Лютвидж Доджсон)
В двоичной системе естественно представимы неотрицательные либо неположительные числа, а поскольку необходимы и те, и другие, то приходится прибегать к дополнительному или обратному коду или вводить особый бит знака числа (“прямой код”). По сравнению с троичным кодом, позволяющим ввести знак (+, 0, -) на уровне элемента-трита, благодаря чему радикально упрощаются все дальнейшие построения, двоичные конструкции в принципе неполноценны, за исключением, разве только двоично-троичной, представляющей триты парами битов. Дело в том, что числа (похоже, как и все в мире) тройственны по природе. Ведь положительное не есть неотрицательное (вопреки тому, как это встречается в англоязычной литературе) и отрицательное не есть неположительное, потому что имеется три фундаментальных класса чисел - положительные, отрицательные и нуль. Это трехзначная (не хрисиппо-булева) логика: положительное есть антиотрицательное, а отрицательное - антиположительное, комплементарно же положительному отрицательное или нуль и т.д. Это логика знаков числа, и хотя их два (плюс, минус), значений все-таки три: +, 0, -.

В русской историко-математической литературе «задача о гирях» известна под названием «задачи Баше-Менделеева», названной так в честь французского математика 17 в. Баше де Мезириака, который разместил эту задачу в своем «Сборнике приятных и занимательных задач» (1612 г.) и блестящего русского химика Дмитрия Ивановича Менделеева, который интересовался этой задачей будучи директором Главной Палаты мер и весов России.

Сущность «задачи Баше-Менделеева» состоит в следующем: при какой системе гирь, имея их по одной, можно взвесить всевозможные грузы Q от 0 до максимального груза Qmax, чтобы значение максимального груза Qmax было бы наибольшим среди всех возможных вариаций? Известно два варианта решения этой задачи: (1) когда гири позволено класть на свободную чашу весов; (2) когда гири позволяется класть на обе чаши весов. В первом случае «оптимальная система гирь» сводится к двоичной системе гирь: 1, 2, 4, 8, 16, ..., а появляющийся при этом «оптимальный» алгоритм или способ измерения рождает двоичную систему счисления, лежащую в основе современных компьютеров. Во втором случае наилучшей является троичная система гирь: 1, 3, 9, 27, 81,…

Хронология

Преимущества троичных ЭВМ

Троичные ЭВМ (компьютеры) обладают рядом преимуществ по сравнению с двоичными ЭВМ (компьютерами).

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

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

Наверняка на хабре уже немало постов на эту тему. Тем не менее, я попытаюсь рассказать свою точку зрения на всё это…

Однажды я прочитал в интернете про троичную систему счисления и заинтересовался. Меня мучил вопрос, а нельзя использовать в основе компьютера симметричную троичную систему счисления (СС), и даже вдруг это увеличит производительность компьютера? Мне казалось, что это возможно, и я жаждал это проверить.

Информация:
Троичная система счисления - позиционная система счисления с целочисленным основанием, равным 3. Существует в двух вариантах: несимметричная и симметричная.
В несимметричной троичной системе счисления чаще применяются цифры {0,1,2}, а в симметричной троичной системе счисления знаки {−,0,+}, {−1,0,+1}.
У некоторых людей эта логика вызывает затруднения. Они говорят, например, приведите пример подобной логики в жизни.
Человек, немного подумавший над этой логикой поймет, что она более жизненна чем двоичная. Обычный пример троичной логики в жизни связан с постоянным током: ток движется в одну сторону, в другую сторону, его нет.

Оказалось, что симметричная троичная система счисления использовалась давным-давно для решения «задачи о гирях», использовалась в компьютере Сетунь , построенном в 50-е годы в МГУ. С 2008 года в университете « California Polytechnic State University of San Luis Obispo» функционирует цифровая компьютерная система TCA2 , основанная на троичной системе счисления.

В чем же плюсы троичной СС над двоичной? Рассмотрим эти плюсы:

Меньше разрядов

(Написано разжевано, чтобы каждый смог понять суть этого пункта)
Возьмем число 10 в десятичной СС и переведем его в двоичную СС, получим 1010, переведем в троичную симметричную СС, получим +0+, ну а если в троичную несимметричную СС, то получим 101. Из этого мы видим, что в некоторых числах в троичной симметричной и несимметричной СС-ах меньше разрядов, чем в двоичной СС.
Возьмем число 5 в десятичной СС и переведем его в двоичную СС, получим 101, переведем в троичную симметричную СС, то получим +--, ну а если в троичную несимметричную СС, то получим 12. Из этого мы видим, что в некоторых числах в троичной несимметричной СС меньше разрядов, чем в двоичной и троичной симметричной СС-ах.

Емкость

Троичная СС вмещает больший диапазон чисел, т.к. 3^n>2^n (где n-натуральное число). Например, если n=9, то 3^9=19683>2^9=512.
3.

Экономичность системы счисления

Экономичность системы счисления - запас чисел, который можно записать в данной системе с помощью определенного количества знаков. Чем больше запас тем экономичнее система. По затратам числа знаков (в трёхразрядном десятичном числе 3*10=30 знаков) наиболее экономична из позиционных показательных несимметричных систем счисления. Обозначим p основание системы счисления, n количество требуемых знаков. Тогда получим n/p разрядов требуемых для записи этого набора знаков в заданной системе счисления, а количество чисел которое при этом можно записать будет равно pn/p.

Мы рассмотрели троичную арифметику, теперь затронем логику:

В чем же проблемы двоичной логики?
1.Мощности компьютера, основанного на двоичной логике, не всегда хватает. Приведем пример. Одна из наиболее сложных систем защиты – криптосистема RSA. Вскрытие шифра RSA с длиной ключа 1024 бита (такая длина часто используется в информационных системах) займет в лучшем случае - при проведении распределенных вычислений на тысячах мощных ПК - не менее пятнадцати лет, а к тому времени данная система шифровки перестанет быть востребованной.
Докажем математически какая система счисления будет наилучшей для максимальной мощности и емкости памяти. Для этого рассмотрим функцию f(p)=p^(n/p), в которой p – основание системы счисления, а n – количество требуемых знаков. Тогда получим n/p разрядов требуемых для записи этого набора знаков в заданной системе счисления, а количество чисел, которое при этом можно записать, будет равно pn/p

F(p)=p^(n/p)
Для того, чтобы определить максимальное значение функции, найдем ее производную:
ln f = ln p^(n/p)
ln f =n/p* ln p
...(Я не буду приводить здесь всю математику)
n*p^(n/p-2) никогда не будет равно 0 => (1 - ln⁡ p)=0, ln p = 1, p = e
e = 2,71, а ближайшее целое число к нему – это три.
Значит, в этом плане лучшая система с целочисленным основанием - троичная.

Самое вкусненькое - рассмотрим троичные логические операции:

1.Отрицание

2.Конъюнкция - логическое И

3.Дизъюнкция - логическое ИЛИ

4.Операция Выбора . Эта операция существует только для троичной логики. Таблица истинности каждой из этих трёх операций содержит везде „-“, кроме единственного значения, которое ею можно выбрать.

5.Модификация . Полное название этих одноместных операций: увеличение на единицу по модулю три (INC) и уменьшение на единицу по модулю три (DEC). Увеличение на единицу по модулю три – это циклическое прибавление единицы.

Здесь видны и прежде знакомые вам логические операции из двоичной логики, но добавились и новые…

Квантовые компьютеры

Квантовый компьютер - вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе классической механики.
Благодаря огромной скорости разложения на простые множители, квантовый компьютер позволит расшифровывать сообщения, зашифрованные при помощи популярного асимметричного криптографического алгоритма RSA. До сих пор этот алгоритм считается сравнительно надёжным, так как эффективный способ разложения чисел на простые множители для классического компьютера в настоящее время неизвестен. Для того, например, чтобы получить доступ к кредитной карте, нужно разложить на два простых множителя число длиной в сотни цифр. Даже для самых быстрых современных компьютеров выполнение этой задачи заняло бы больше времени, чем возраст Вселенной, в сотни раз. Благодаря алгоритму Шора эта задача становится вполне осуществимой, если квантовый компьютер будет построен.
Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 кубит. Это устройство работает на кубитах - квантовых аналогах битов.
Но можно построить компьютеры не на битах, а на кутритах - аналогах трита в квантовом компьютере.
Кутрит (квантовый трит) - квантовая ячейка, имеющая три возможных состояния.
Подлинное новаторство метода Ланьона в том, что, используя в универсальных квантовых вентилях кутриты вместо кубитов, исследователи могут существенно снизить количество необходимых вентилей.
Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, если будет основан на троичном представлении.
Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.

Итог:
В конечном итоге видно, что троичная симметричная система лучше двоичной системы в некоторых показателях, но не сильно выигрывает. Но с пришествием квантовых компьютеров троичные вычисления получили новую жизнь. Универсальные квантовые логические вентили - краеугольный камень новорожденных квантовых вычислительных систем - требует сотни вентилей для завершения одной полезной операции. Квантовый компьютер канадской компании D-Wave, анонсированный в прошлом году, состоит всего из 16 квантовых битов - кубитов - минимум, необходимый для управляемого вентиля «NOT». Использование в квантовом компьютере кутритов нужно было бы намного меньше вентилей для завершения одной операции. Я думаю, если бы началось производство и тестирование таких компьютеров, то результаты были бы лучше, чем у обычных компьютеров, вскоре началось бы массовое их производство, и про двоичные компьютеры все бы забыли…

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

Его научный руководитель академик С.Л. Соболев загорелся идеей создания малой ЭВМ, пригодной по стоимости, размерам, надежности для институтских лабораторий. Он организовал семинар, в котором участвовали М.Р. Шура-Бура, К.А. Семендяев, Е.А. Жоголев и, конечно, сам Сергей Львович. Анализировали недостатки существующих машин, прикидывали систему команд и структуру (теперь это называют архитектурой), рассматривали варианты технической реализации, склоняясь к магнитным элементам, поскольку транзисторов еще не было, лампы исключались, а сердечники и диоды можно было достать и все сделать самим. На одном из семинаров (23 апреля 1956 г.) с участием С.Л. Соболева были сформулированы основные технические требования к созданию малой ЭВМ. Руководителем и вначале единственным исполнителем разработки нового компьютера был назначен Н.П. Брусенцов. Заметим, что речь шла о машине с двоичной системой счисления на магнитных элементах.

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

Первый экземпляр «Сетуни» (а машина была названа так по имени речки, протекавшей возле университета) был готов к концу 1958 г. Сделали ее, можно сказать, своими руками сотрудники возглавляемой Н. П. Брусенцовым лаборатории: Е. А. Жоголев, С. П. Маслов, В. В. Веригин, В. С. Березин, Б. Я. Фельдман, Н. С. Карцева, А. М. Тишулина, В. П. Рогозин. На десятый день комплексной наладки машина заработала. Такого в практике наладчиков разрабатываемых в те годы ЭВМ еще не было.

Постановлением Совмина СССР серийное производство «Сетуни» было поручено Казанскому заводу математических машин. Конструкторскую документацию на машину разработали в СКБ Института кибернетики АН Украины. Первый образец машины демонстрировался на ВДНХ в Москве. Второй пришлось сдавать на заводе, поскольку заводские начальники пытались доказать, что машина, принятая Межведомственной комиссией и успешно работающая на ВДНХ, не годится для производства. «Пришлось собственными руками привести заводской (второй) образец в соответствие с нашей документацией, - вспоминает Брусенцов, - и на испытаниях он показал 98% полезного времени при единственном отказе (пробился диод на телетайпе), а также солидный запас по климатике и вариациям напряжения сети». Желания наладить крупносерийное производство у руководства завода не было. Причины: «Сетунь» была слишком дешевой машиной, а значит, невыгодной для завода, и тот факт, что она надежно и продуктивно работала во всех климатических зонах от Калининграда до Магадана и от Одессы до Якутска, причем без какого-либо обслуживания и по существу без запасных частей, в расчет не принимался. Успешность испытаний вынудили 30 ноября 1961 г. директора завода был подписать акт, положивший конец его стараниям похоронить неугодную машину.

Выпускали всего по 15-20 машин в год, а вскоре и от этого отказались. Всего казанский завод выпустил 50 ЭВМ «Сетунь», 30 из них работали в высших учебных заведениях СССР.

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

В 1961-1968 гг. Брусенцов вместе с Жоголевым разработал архитектуру новой машины, названной затем «Сетунь-70». Было намечено к 1970 г. разработать действующий образец. В апреле 1970 г. образец уже действовал. Работал он на тестах, которые пришлось писать Н. П. Брусенцову, потому что Жоголев увлекся другой работой. Машину все же «оседлали», помог программист Рамиль Альварес Хосе, а еще через год, «слегка» модернизировав «Сетунь-70», сделали ее машиной структурированного программирования.

Это была машина, в которой неизвестные в то время (1966-1968 гг.) RISC - идеи соединились с преимуществами трехзначной логики, троичного кода и структурированного программирования Э. Дейкстры. Для нее создали диалоговую систему структурированного программирования, а в ней множество высокоэффективных, надежных и компактных продуктов - таких, как кросс-системы программирования микрокомпьютеров, системы разработки технических средств на базе однокристальных микропроцессоров, системы обработки текстов, управления роботами-манипуляторами, медицинский мониторинг и многое другое.

Машина была задумана так, что обеспечивалась эффективная возможность ее программного развития. Троичность в ней играла ключевую роль. Команд в традиционном понимании не было - они виртуально складывались из слогов. Длина и адресность команд варьируются по необходимости, начиная с нульадресной. На самом деле программист не думает о командах, а пишет в постфиксной форме (ПОЛИЗ) выражения, задающие вычисления над стеком операндов. Для процессора эти алгебраические выражения являются готовой программой, но алгебра дополнена операциями тестирования, управления, ввода-вывода. Пользователь может пополнять набор слогов своими операциями и вводить (определять) постфиксные процедуры, использование которых практически не снижает быстродействия, но обеспечивает идеальные условия для структурированного программирования. Результат - трудоемкость программ уменьшилась в 5-10 раз при небывалой надежности, понятности, модифицируемости и т. п., а также компактности и скорости.

К сожалению, лаборатория Н. П. Брусенцова после создания машины «Сетунь-70» была выселена из помещения ВЦ МГУ на чердак студенческого общежития. Вероятно, причина была в том, что на фоне двоичных ЭВМ выглядела она со своей троичностью белой вороной. Первое детище Николая Петровича - машина «Сетунь» (экспериментальный образец, проработавший безотказно 17 лет) была варварски уничтожена - ее разрезали на куски и выбросили на свалку. «Сетунь-70» сотрудники лаборатории забрали с собой на чердак и там на ее основе создали «Наставник» - замечательную систему обучения с помощью компьютера.

В человеческом обществе неприятие нового в порядке вещей, и Н. П. Брусенцов еще легко отделался. А вот Уильям Оккам, проповедовавший трехзначную логику в ХIII веке, с большим трудом избежал костра…Тем не менее Н. П. Брусенцов уверен, что полноценная информатика не может ограничиться общепринятой сегодня по техническим причинам двоичной системой - основа должна быть троичной.

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

Н. П. Брусенцов говорил, что «..налицо убедительные доказательства верности открытого пути. С какой легкостью была сделана «Сетунь», как просто ее осваивали и продуктивно применяли во всех областях и как программисты плевались, когда пришлось им переходить на двоичные машины. Наивысшее достижение сегодня -- RISC-архитектура - машины с сокращенным набором команд (обычно их 150), но где им до «Сетуни», у которой 24 команды обеспечивали полную универсальность и несвойственные RISC эффективность и удобство программирования!

Истинный RISC может быть только троичным.

Информация, которой оперирует компьютер, так или иначе раскладывается на единицы и нули - графика, музыка, тексты, алгоритмы программ. Все просто и понятно: «включено» - «выключено», «есть сигнал» - «нет сигнала». Либо «истина», либо «ложь» - двоичная логика. А между тем еще в 1961-м, в год первого полета человека в космос, в Советском Союзе наладили производство необычных вычислительных машин, оперировавших не двоичной, а троичной логикой.

В принципе, у троичной системы счисления было не меньше шансов, чем у двоичной. Кто знает, по какому пути развития пошел бы технический прогресс, если бы «трайты» одержали победу над «байтами». Как выглядели бы современные смартфоны или GPS-навигаторы, как отразилось бы значение «может быть» на их быстродействии? Сложно сказать. Мы проанализируем этот вопрос, а вам предоставим возможность сделать выводы самостоятельно.

Машина Фоулера

Справедливости ради сразу следует заметить: первую вычислительную машину с троичной системой счисления задолго до советских конструкторов построил английский изобретатель-самоучка Томас Фоулер в далеком 1840 году. Его машина была механической и полностью деревянной.

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

Затем он пошел дальше, решив полностью автоматизировать расчеты по таблицам, и построил счетную машину. Английская патентная система того времени была несовершенна, предыдущее изобретение Фоулера (термосифон для систем парового отопления) было скопировано с минимальными изменениями и запатентовано множеством недобросовестных «изобретателей», поэтому, опасаясь, что его идею снова могут украсть, он решил изготовить машину в единственном экземпляре и - из дерева. Так как дерево - материал ненадежный, для обеспечения достаточной точности вычислений Фоулеру пришлось сделать машину весьма громоздкой, около 2 м в длину. Впрочем, как писал сам изобретатель в сопроводительной записке, отправляя машину в Лондонский королевский колледж, «если бы ее можно было изготовить из металла, она бы оказалась не больше пишущей машинки».

Машина Фоулера была проста, эффективна и использовала новаторский подход: вместо десятичной системы счисления оперировала «триадами», то есть степенями тройки. К сожалению, замечательное изобретение так и осталось незамеченным, оригинал машины не сохранился до наших времен, и о ее устройстве известно только из сочинения Фоулера-младшего, написавшего биографию отца.

Первые советские опыты

О практическом использовании троичной системы счисления забыли более чем на сто лет. Следующими, кто вернулся к этой идее, были инженеры с кафедры вычислительной математики механико-математического факультета МГУ.

Все началось в 1954 году: кафедре должны были передать электронно-вычислительную машину М-2, но не сложилось. А машину-то ждали, готовились ее устанавливать и налаживать, с нею связывались определенные ожидания и планы. И кто-то предложил: давайте построим свою.

Взяли - и построили, благо в то время в МГУ существовали некоторые теоретические наработки. Руководителем группы, осуществлявшей проектирование и изготовление машины, был назначен Николай Петрович Брусенцов. Задача была такая: сделать машину предельно простой и недорогой (потому что никакого специального финансирования у проекта не было). Поначалу собирались делать двоичную ЭВМ, но позже - как раз из соображений экономичности и простоты архитектуры - пришли к решению, что она будет троичной, использующей «естественный» троичный симметричный код, простейший из симметричных кодов.

К концу 1958 года был закончен первый экземпляр машины, которой дали имя «Сетунь» - по названию московской речки. «Сетунь» была относительно невелика для вычислительных машин того поколения и занимала площадь 25−30 м2. Благодаря своей изящной архитектуре она была способна выполнять 2000−4500 операций в секунду, обладала оперативной памятью в 162 девятитритных ячейки и запоминающим устройством на магнитном барабане емкостью 36−72 страницы по 54 ячейки каждая. Машинных команд было всего 27 (причем три так и остались невостребованными), благодаря чему программный код получался весьма экономным; программирование непосредственно в машинных кодах было настолько простым, что для «Сетуни» даже не разрабатывали свой ассемблер. Данные вводили в машину с перфоленты, результаты выводились на телетайп (причем, что любопытно, отрицательные цифры печатались как обычные, но перевернутые кверху ногами). При эксплуатации машина показывала 95−98% полезного времени (расходуемого на решение задач, а не на поиск неисправностей и устранение неполадок), а в те времена очень хорошим результатом считалось, если машина могла дать хотя бы 60%.

На межведомственных испытаниях 1960 года машину признали пригодной для массового использования в КБ, лабораториях и вузах, последовало распоряжение о серийном выпуске «Сетуни» на Казанском заводе математических машин. С 1961 по 1965 год было построено 50 экземпляров, которые работали по всей стране. Затем производство свернули. Почему перестали выпускать «Сетунь», если она успешно использовалась всюду от Калининграда до Якутска? Одна из возможных причин в том, что компьютер оказался слишком дешевым в производстве и потому невыгодным для завода. Другая причина- косность бюрократических структур, противодействие ощущалось на каждом из этапов.

Впоследствии Николай Брусенцов и Евгений Жоголев разработали более современную версию машины, использовавшую те же принципы троичности, - «Сетунь-70″, но она так и не пошла в серийное производство, единственный опытный образец работал в МГУ до 1987 года.

Трехзначная логика

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

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

Логике, оперирующей тремя значениями, естественным образом соответствует троичная система счисления - троичная симметричная, если говорить точнее, простейшая из симметричных систем. К этой системе впервые обратился Фибоначчи для решения своей «задачи о гирях».

В троичной симметричной системе используются цифры: –1, 0 и 1 (или, как их еще обозначают, –, 0 и +). Преимущества ее как симметричной системы состоят в том, что, во-первых, не нужно как-то особо отмечать знак числа - число отрицательно, если его ведущий разряд отрицателен, и наоборот, а инвертирование (смена знака) числа производится путем инвертирования всех его разрядов; во-вторых, округление здесь не требует каких-то специальных правил и производится простым обнулением младших разрядов.

Кроме того, из всех позиционных систем счисления троичная наиболее экономична - в ней можно записать большее количество чисел, нежели в любой другой системе, при равном количестве используемых знаков: так, например, в десятичной системе, чтобы представить числа от 0 до 999, потребуется 30 знаков (три разряда, десять возможных значений для каждого), в двоичной системе теми же тридцатью знаками можно закодировать числа в диапазоне от 0 до 32767, а в троичной - от 0 до 59048. Самой экономичной была бы система счисления с основанием, равным числу Эйлера (e = 2,718…), и 3 - наиболее близкое к нему целое.

Если в привычных нам двоичных компьютерах информация измеряется в битах и байтах, то компьютеры на троичной системе счисления оперируют новыми единицами: тритами и трайтами. Трит - это один троичный разряд; подобно тому, как бит может принимать значения 0 и 1 («ложь» и"истина»), трит может быть (+), (0) или (–) (то есть «истина», «неизвестно» или «ложь»).

Один трайт традиционно (так было на «Сетуни») равен шести тритам и может принимать 729 различных значений (байт - только 256). Впрочем, возможно, в будущем трайты станут 9- или 27-разрядными, что естественнее, так как это степени тройки.

Настоящее и будущее троичных компьютеров

После «Сетуни» было несколько экспериментальных проектов, осуществлявшихся энтузиастами (таких, например, как американские Ternac и TCA2), однако это были либо весьма несовершенные машины, далекие от двоичных аналогов, либо и вовсе программные эмуляции на двоичном «железе».

Основная причина состоит в том, что использование в компьютерах троичных элементов пока не дает никаких существенных преимуществ перед двоичными: выпуск последних налажен массово, они проще и дешевле по себестоимости. Даже будь сейчас построен троичный компьютер, недорогой и по своим характеристикам сравнимый с двоичными, он должен быть полностью совместим с ними. Уже разработчики «Сетуни-70» столкнулись с необходимостью обеспечить совместимость: чтобы обмениваться информацией с другими университетскими машинами, пришлось добавить возможность читать с перфолент двоичные данные и при выводе также конвертировать данные в двоичный формат.

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

Одно из таких исследовательских направлений - поиск альтернативных способов увеличения производительности процессоров. Каждые 24 месяца число транзисторов в кристалле процессора увеличивается примерно вдвое - эта тенденция известна как «закон Мура», и вечно продолжаться она не может: масштабы элементов и связей можно измерить в нанометрах, и очень скоро разработчики столкнутся с целым рядом технических сложностей. Кроме того, есть и экономические соображения - чем меньше, тем дороже разработки и производство. И с какого-то момента окажется дешевле поискать альтернативные способы делать процессоры мощнее, нежели продолжать гонку за нанометрами, - обратиться к технологиям, от которых раньше отказывались как от нерентабельных. Переход от однородных кремниевых структур к гетеропереходным проводникам, состоящим из слоев различных сред и способным генерировать несколько уровней сигнала вместо привычных «есть» и «нет», - это возможность повысить интенсивность обработки информации без увеличения количества элементов (и дальнейшего уменьшения их размеров). При этом от двухзначной логики придется перейти к многозначным - трехзначной, четырехзначной и т. д.

Другое направление, также нацеленное на увеличение производительности, - разработки в области асинхронных процессоров. Известно, что обеспечение синхронности процессов в современных компьютерах изрядно усложняет архитектуру и расходует процессорные ресурсы - до половины всех транзисторов в чипе работает на обеспечение этой самой синхронности. Компания Theseus Logic предлагает использовать «расширенную двоичную» (фактически - троичную) логику, где помимо обычных значений «истина» и «ложь» есть отдельный сигнал «NULL», который используется для самосинхронизации процессов. В этом же направлении работают еще несколько исследовательских групп.

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

Ненормальное программирование ,

Программирование ,

Совершенный код

• Перевод

"Возможно, самая красивая система счисления - это сбалансированная троичная" - Дональд Е. Кнут, Искусство программирования, Издание 2.

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

Такая конструкция сегодня настолько распространена, что трудно себе представить, как компьютеры могут работать иначе. Но, в Советской России 50-х годов они работали иначе. Если вы вдруг не слышали про такое, загуглите "Сетунь " - сбалансированный трехкомпонентный компьютер, разработанный в 1958 году небольшой группой во главе с Брусенцовым, в МГУ.

Перед тем, как говорить о Брусенцове и Сетуни, давайте я немного объясню вам троичную сбалансированную систему счисления.

Сбалансированная троичность

Тернарная или троичная - это система счисления, в которой есть три вероятных значения: 0 , 1 и 2 . В её сбалансированной версии существуют три вероятности -1 , 0 и +1 , часто упрощённые до - , 0 и + соответственно.

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

Эмм, давайте я просто приведу пример. Давайте запишем 114:

+++-0 = (1 * 3^4) + (1 * 3^3) + (1 * 3^2) + (-1 * 3^1) + 0 = 81 + 27 + 9 + -3 = 114

И в бинарной (двоичной):

1110010 = (1 * 2^6) + (1 * 2^5) + (1 * 2^4) + 0 + 0 + (1 * 2^1) + 0 = 64 + 32 + 16 + 2 = 114

И, для уверенности, те же правила, применённые при десятичной системе счисления:

114 = (1 * 10^2) + (1 * 10^1) + (4 * 10^0) = 100 + 10 + 4 = 114

Что если мы хотим представить -114 ? В двоичной и десятичной системах нам понадобится использовать новый символ: знак (sign). В основной памяти двоичного компьютера это осуществляется либо через хранение ведущего бита, указание знака или значительное уменьшение количества чисел, которые мы можем представить 1 . Именно по этой причине мы говорим о signed и unsigned в языках программирования.

Но в симметричной троичной системе, как мы узнаем позже, чтобы представить обратную величину числа (инвертированное число), нам просто нужно поменять все "+" на "-" и наоборот. Нам не нужна какая-то дополнительная информация, чтобы указать знак!

Вот смотрите:

---+0 = (-1 * 3^4) + (-1 * 3^3) + (-1 * 3^2) + (1 * 3^1) + 0 = -81 + -27 + -9 + 3 = -114

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

Рождение Сетуни

В конце 50-х годов в мире компьютеров был захватывающий период: Натаниэль Рочестер и его команда в IBM недавно разработали первый серийно выпускаемый компьютер с хранящейся в памяти программой, так называемый «современный» компьютер IBM 701 . Джон Бэкус со своей командой изобрели FORTRAN , первый язык программирования высокого уровня, который обрёл широкое применение. И, пожалуй, самое главное - начали развиваться первые целиком транзисторные компьютеры, такие как TX-0 и Philco Transac S-2000 . Было задано направление для разработки двоичных компьютеров, которые позже стали доминировать.

Но это было в Северной Америке.

В то же время в России группа математиков и инженеров под руководством Брусенцова и его коллеги Сергея Соболева разрабатывает другие компьютерные системы 2 . Брусенцов и его коллеги исследуют множество западных компьютеров и технологических достижений, и осмысливают применение транзисторов для представления двоичных данных. Но давайте вспомним, что это СССР - транзисторы не так легко доступны за железным занавесом. А электронные лампы трубки одинаково отстойны как в России, так и на Западе!

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

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

Троичная логика была реализована через объединение двух таких ферритовых элементов и подключения их таким образом, что они моделировали три устойчивых состояния. Этот подход был успешным, но количество необходимых элементов не сокращалось, поскольку в действительности два ферритовых сердечника могут потенциально представлять собой два двоичных бита, что в итоге даёт больший объём информации (2 ^ 2), чем один троичный "трит" (3 ^ 1), Печально, но хотя бы потребляемая мощность была снижена!

Сетунь оперирует числами до 18 тритов, то есть один трит может моделировать любое число между -387 420 489 и 387 420 489 . Двоичному компьютеру требуется как минимум 29 битов для достижения такой мощности.

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

В большей степени из-за неспособности завода-изготовителя оправдать массовое производство того, что они расценивали как дешёвую область науки и "плод университетской фантазии". Думаю, можно с уверенностью предположить, что Россия тогда просто была не готова понять потенциальную важность вычислительных машин. В конце концов, машины Сетунь были заменены двоичными аналогами, которые справлялись с вычислениями с той же эффективностью, но стоимость эксплуатации была выше чем в два раза!

Что же особенного в тернарной системе?

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

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

Давайте я приведу простой пример. Перевод в код числа 0.2 выглядит следующим образом:

0.+--+ = 0 + (1 * (3^-1)) + (-1 * (3^-2)) + (-1 * (3^-3)) + (1 * (3^-4)) = 0.33 + -0.11 + -0.03 + 0.01 = 0.2

И для записи 0.8 нужно начать с + в старшем разряде, а затем просто инвертировать дробную часть (например, 1 + -0,2):

+.-++- = 1 + (-1 * (3^-1)) + (1 * (3^-2)) + (1 * (3^-3)) + (-1 * (3^-4)) = 1 + -0.33 + 0.11 + 0.03 + -0.01 = 0.8

Выше видно, что выделение целой части тритов справа от поразрядной точки эквивалентно округлению: 0,2 становится нулём, а 0,8 становится единицей. Круто!

Программирование с тритами и трайтами!

Ок, возвращаемся к Сетуни в последний раз. В конце 60-х Брусенцов разработал более современную машину "Сетунь-70", которая воплотила тернарность более чётко. Было введено понятие "трайт", который состоял из 6 тритов (примерно 9,5 битов). Компьютер Сетунь-70 был стековым , и поэтому вместо машинных инструкций, которые намеренно назвали регистрами для ввода и вывода, все операции выполнялись в двух стеках - одном для операндов (вход) и одном для возвращаемых значений (выход). Для того, чтобы приспособить этот дизайн, машинные инструкции были написаны в обратной бесскобочной нотации (обратной польской нотации или постфиксной записи).

В конце 70-х годов, Брусенцов и несколько его учеников разработали язык программирования для Сетунь-70, который назвали Диалоговая система структурированного программирования (ДССП). Проводя своё исследование 4 , я заметил, что это стек-ориентированный язык (что, правда, совсем не удивительно), аналогичный Forth и использует обратную польскую нотацию. Это позволяет писать программы на языке относительно высокого уровня, но продолжать чувствовать себя "низкоуровнево". Настолько, что у его авторов было следующее сообщение:

ДССП не был изобретен. Он был открыт. Поэтому у языка нет версий, только расширения.

Рассмотрим программу на ДССП, которая складывает группу цифр:

1 2 3 4 DEEP 1- DO +

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

1 Добавить 1 в стек. 2 Добавить 2 в стек. 3 Добавить 3 в стек. 4 Добавить 4 в стек. DEEP Добавить "глубину стека" (4) в стек. 1- [-1 4 4 3 2 1] Добавить -1 в стек. DO Начать цикл, удалить два элемента из стека. Для управления циклом первый элемент применяется ко второму пока не получится 0. + Применить оператор "+" до завершения цикла, каждый раз удаляя верхний элемент из стека операндов, применяя + и добавляя вывод в стек возвратов.

По окончанию исполнения, стек операндов будет пустым, а в стеке возвратов будет .

О ДССП подробней написано на сайте Ивана Тихонова (авторы Сидоров С.А. и Шумаков М.Н.).

Будущее

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

А именно, японские исследователи в конце 90 -х годов описали возможность использовать переход Джозефсона для реализации троичной логики. Этого можно было достичь за счет циркуляции сверхпроводящих токов - положительного (по часовой), отрицательного (против часовой стрелки), или нулевого. Они обнаружили, что это даёт ячейкам памяти "высокоскоростную способность вычислений, низкое энергопотребление и очень простую конструкцию с меньшим количеством элементов, благодаря тернарной операции".

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

1. Это зависит от того, как конкретная машина представляет числа. Дополнительный код - это представление чисел в десятичной системе счисления, которое даёт возможность представить от -((2^n) / 2) до ((2^n) / 2) - 1 в n битах.

2) Хотя компьютер Сетунь был первым электронным устройством, использовавшим для работы тернарную систему, стоит отметить, что идея использования такой системы в вычислительных устройствах впервые была популяризована более 100 лет назад. В 1840 году Томас Фаулер построил вычислительную машину целиком из дерева, и она работала с данными, используя тернарную систему.

Более точное описание можно найти на сайте российского компьютерного музея .

Справочный материал для ДССП на английском языке не слишком доступен, поэтому я предупреждаю, что мои знания ограничены и могут содержать догадки трайты

1. тернарный компьютер
Добавить метки