Недвоичная логика

от автора

В начале Второй мировой войны перед военными силами США остро встала проблема нехватки баллистических таблиц стрельбы, жизненно необходимых для работы артиллерии. Типичная баллистическая таблица представляет собой набор числовых данных траекторий полета снаряда, предварительно расчитанных для определенных условий стрельбы, ствола, снаряда, погодных условий и температуры воздуха. Ручной расчет лишь одной траектории занимал несколько дней, и каждая таблица обходилась в огромные количества человеко-часов.

В то время этими расчетами занимались лишь несколько высококвалифицированных специалистов, и даже увеличение штата лаборатории в 1942 году помогло незначительно. В июне этого же года был заключен контракт с Школой электротехники Мура Пенсильванского университета, которая располагала диффереренциальным анализатором конструкции Вэнивара Буша — механическим вычислителем той эпохи. Работой руководил лейтенант, а позже капитан Герман Голдстайн, получивший степень доктора математики в Чикагском университете. Именно он с профессором Брайнердом в 1943 году представил идею «электронного дифференциального анализатора» авторства Джона Мокли.

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

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


Десятичные накопители ЭВМ ЭНИАК

Выбор десятичной системы был продиктован вопросами удобства её использования; создатели машины решили пренебречь достоинствами иных систем счисления. ЭНИАК мог складывать, вычитать, умножать, делить, извлекать квадратный корень и сравнивать любые десятичные числа из 10 цифр. В памяти 20 накопителей, являвшихся также и сумматорами, могло храниться до 20 таких чисел. При этом числа представлялись не десятью различными электрическими значениями, которые легко могли измениться, а отсутствием или наличием активных импульсов, и набор сигналов одного числа передавался совместно по нескольким различным проводам. Таким образом к каждому регистру подходило 11 линий (10 цифр и знак).

Каждый триггер машины имел два входа и два выхода и содержал два триода, соединенных таким образом, что в любой момент времени ток проходил лишь через один. Десять триггеров формировали десятичное кольцо, способное считать числовые сигналы и хранить числа. В свою очередь десять колец объединялись в базовую арифметический накопитель. Если одно из колец выходило за предел в 9 значений, старший сосед получал дополнительный импульс.

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

Очевидно, что ЭНИАК был в значительной степени аппаратно избыточен. Его сложность, вызванная использованием такой «человечной» десятичной формы представления чисел на основе двоичных триггеров, и нестабильность в работе вакуумных ламп несколько затрудняла его работу и заставляла персонал идти на различные ухищрения в его эксплуатации.

Последний апгрейд машины произошел в июле 1953 года (до этого ЭНИАК обзавелся, к примеру, механической системой развязки питания). Уже в 1951 году встал вопрос о недостаточности количества памяти, и в Burroughs Corporation предложили использовать перспективную технологию магнитных ячеек. Основной проблемой исполнителя стал язык. Для реализации в ЭНИАК памяти в 100 слов, каждое из которых представляло из себя 10 десятичных цифр и знак, потребовалось бы 9.100 бит хранилища. Вместо этого каждую цифру представили в виде 4 бит с введением преобразователей кода, но даже с учетом потерянных бит запрещенных состояний экономия была значительна — потребовалось всего 4.100 бит.

За ЭНИАКом последовала серия машин IBM, UNIVAC и других, но десятичные компьютеры постепенно были вытеснены двоичными. Причины этого просты: у распространенных сегодня элементарных логических элементов лишь два состояния, которые они могут принять, поэтому запись данных в двоичной форме заведомо проще и плотнее. Шестьдесят лет спустя отход от бинарной логики воспринимается как заведомо проигрышный шаг, но является ли двоичная логика математически лучшим выбором?

Удельная натуральнологарифмическая плотность записи информации описывается функцией

Эта функция достигает максимума в точке a = e. Это означает, что наибольшей плотностью записи информации обладает система исчисления с основанием, равным основанию натуральных логарифмов (е ≈ 2,718281828459045). Именно так было выбрано основание для фиксирования логарифмических таблиц. При этом из целочисленных систем счисления наибольшей плотностью записи информации обладает троичная, а не двоичная система исчисления.

Троичная система счисления существует в двух вариантах: симметричная, имеющая в наборе отрицательные цифры (−1, 0, 1) и несимметричном (0, 1, 2). Необходимо отметить, что троичная симметричная система счисления обладает тем свойством, что обеспечивает более простое представление отрицательных чисел в памяти компьютера. (Как известно, в двоичное число для этого нужно вводить дополнительный код, чтобы не усложнять архитектуру компьютера.)

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

Не все законы двоичной логики верны для троичной логики, для некоторых сформулированы троичные аналоги. Ряд исследователей апеллирует к тому, что трехзначная логика значительно более натуральна и свойственна человеческому мышлению, чем двоичная. Сегодня бинарная логика, согласно их заявлениям, не дает нам войти в трехзначную. Развитием троичной логики в разные периоды времени занимались польский философ и логик Ян Лукасевич, английский математик Льюис Кэролл и другие.

Несмотря на все достоинства троичной логики и троичной системы счисления, в истории человечества остались лишь две наиболее успешные попытки создать троичный компьютер. Первая из них — механическая — датируется XIX веком. Деревянный калькулятор Фаулера использовал симметричную троичную систему счисления, и Августом де Морганом было сделано наиболее точное на сегодня его описание, на основе которого машина была воссоздана.

Опасаясь кражи его идеи, Фаулер в одиночку выполнял детали из древесины. Чтобы скомпенсировать вызываемую ей низкую точность, изобретатель придал своей машине крупные габариты — 1,80 метра в длину, 90 см в глубину и 30 см в высоту. До этого Фаулер разработал методы работы с используемой в его машине системой счисления.

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

Множитель — это рама, которая может перемещаться перпендикулярно стержням множимого и произведения, и расположена между их плоскостями таким образом, что её край может быть совмещён скользящим движением с каждым стержнем множимого поочередно. Множитель состоит из набора стержней, при этом каждый из стержней имеет зубец с каждого края и зубец, которым множитель взаимодействует со стержнями множимого. Один набор зубцов расположен/размещён так, что опирается на раму, которая может вращаться вокруг оси. Каждый стержень может соприкасаться с рамой выше, ниже или в районе оси вращения. Зубцы, находящиеся на оси, не получают движения, остальные же придут в движение в ту или иную сторону в зависимости от того с какой стороны зубец касается рамы. Перпендикулярные зубцы с другого конца могут совершать движение вперёд–назад или оставаться неподвижными, в свою очередь они тем самым взаимодействуют со стержнями, которые составляют раму произведения, которая схожа с рамой множимого и имеет деталь, соединяющую её с множителем.

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

Результат умножения будет представлен не в простейшей форме: он должен содержать только +1 или −1, а полученный промежуточный ответ может содержать на любом стержне +2, −2, +3 или −3 и т.д. Для корректировки результата используется механизм переноса, который представляет собой простое устройство, которое, как и множитель, может совершать поперечное перемещение, и может быть помещен на любой паре соседних стержней. Аппарат переноса выдвигает левый из двух стержней на единицу и втягивает стержень находящийся справа на 3 единицы или наоборот. Даже без наличия обязательного навыка работы с механизмом переноса серьезная ошибка невозможна, так как за каждую операцию можно перенести нижнюю колонку только на 3 единицы, в то время как следующая колонка изменится в противоположном направлении на одну единицу.

Деление чисел осуществляется противоположным способом.

Второй наиболее успешный проект троичной вычислительной машины — это относительная современная серийная (50 экземпляров) ЭВМ «Сетунь», построенная в вычислительном центре МГУ в 1959 году. Её создателем является советский конструктор Николай Петрович Брусенцов, также в проекте принимали участие Е.А. Жоголев, В.В. Веригин, С.П. Маслов, А.М. Тишулина и др. Машина использовала симметричную троичную систему счисления.

Минимальной адресуемой единицей памяти «Сетуни» стал трайт, равный шести тритам и принимающий значения от -364 до 364. Работа с диапазоном отрицательных значений — особенность, отличающая трайт от двоичного байта, значения которого распространяются от 0 до 255. С помощью трайта можно закодировать все заглавные и строчные символы русского и латинского алфавитов, необходимые математические и служебные символы.

Машина была реализована не на ненадежных вакуумных лампах или дорогих в ту эпоху транзисторах, а на феррит-диодных элементах, собранных на гетинаксовой основе. Генератор тактовой частоты задавал такт работы ячеек в 200 кГц. Ячейки компоновались в функциональные блоки: сумматоры, дешифраторы троичного кода, регистры сдвига. С помощью тридцатиконтактного разъёма каждый блок стыковался с другими блоками «Сетуни», формируя базовые компоненты ЭВМ: арифметическое устройство и устройство управления

При проектировании Брусенцев позаимствовал принцип в работы в ЭВМ ЛЭМ-1, но в то время как в последнем используется пара сердечников под каждый бит — рабочий и компенсационный, в «Сетуни» работает и компенсационный сердечник, что задает троичный характер компьютера. В троичной ячейке Брусенцева один трит записывался в два двоичных разряда, четвёртое состояние двух двоичных разрядов не использовалось.

Первый опытный экземпляр машины «Сетунь» показывал при испытаниях 95% полезного времени (реальной работы вне тестирования, техобслуживания и устранения неисправностей), в то время как 60% считалось хорошим результатом. За счет несложных технологий «Сетунь» со всей периферией стоила 27,5 тысяч рублей (для сравнения: только процессорный блок рекордно дешевой PDP-8 стоил 20 тыс. долларов), и к машине проявляли интерес не только в соцстранах, но и на Западе. Чехословацкий завод «Зброевка Яна Швермы» был готов начать выпуск машины для покупателей за рубежом и обещал выгоду в полмиллиона долларов с каждой машины, но более высокое руководство требовало сначала развернуть массовый выпуск машины в СССР, хотя уже тогда было очевидно, что проект близится скорее к закрытию.

И проект действительно был закрыт. В 1967 году, когда было решено делать к 100-летию со дня рождения Ленина разнообразные производственные подарки, конструктора, некоторые из которых уже не могли принимать участие в проекте, взяли обязательство к этой дате сделать «Сетунь-70» — улучшенную версию оригинала. Это была несколько иная ЭВМ: она была стековой, но в отличие от «Эльбруса» с его стеком операндов и более позднего PDP-11 с его процедурным стеком, «Сетунь-70» имела два стека — команд и операндов. Как говорит сам Брусенцев, программы на «Сетунь-70» получались легко читаемыми и осваиваемыми, а вместо отладки использовалась контрольная сборка — проход написанного кода снизу вверх. Позднее «Сетунь-70» была эмулирована на двоичных машинах в форме диалоговой системы структурного программирования ДССП, но попыток тиражировать «Сетунь-70» разработчики, обладая горьким опытом «Сетуни», естественно, не предпринимали.

Не следует думать, что сегодня троичная логика была полностью забыта: она используется в телекоммуникациях, где важны скорости передачи информации. Отсылка за один такт одного трита увеличивает скорость передачи данных по одному разряду в 1,5 раза на один разряд, при увеличении количества разрядов скорость растет значительно, в то время как уменьшаются удельные аппаратные затраты.

IBM, Motorola, Hypres и Texas Instruments ведут различные исследования в области троичных компьютеров. Значительных аппаратных проблем в реализации трехзначной логики на сегодняшний день не существует; наоборот, предлагаются новые и новые перспективные элементы с тремя состояниями. В рамках кремниево-германиевых сплавов (SiGe) можно реализовать цифровые интегральные схемы, работающие с тремя и более уровнями сигнала.

В своей научной работе «Архитектура троичного оптического компьютера» Джин Йи, Хи Хуакан и Лу Янгтиан предлагают использовать для выражения информации два состояния поляризации света с ортогональными направлениями колебаний. Три исследователя предлагают использовать кольцо оптоволокна в качестве регистра, полупроводниковую память для троичной ячейки и жидкие кристаллы как модуляторы и сумматоры.

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

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

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

При подготовке публикации использовались материалы монографии «Электронные компьютеры в артиллерийских войсках», сайтов mortarti.com, trinary.ru, trinitas.ru, журнала Компьютерра и архивов МГУ.

ссылка на оригинал статьи http://habrahabr.ru/post/160595/


Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *