В повседневной жизни мы используем десятичную систему счисления. Почему именно её — это вопрос отдельный. В конце концов, существуют системы с основанием 12 (по фалангам пальцев без большого), 5 (пальцы на одной руке), 20, 60 и так далее. В компьютерах всё несколько проще — там (можно даже сказать, «Традиционно») используется двоичная система, как самая лёгкая для воплощения. Есть ток — нету тока. Есть отверстие в перфокарте — нет отверстия. Ноль или единица. Короче говоря, «да» или «нет» — третьего не дано. А что будет, если дать? Об этом и поговорим.
Собственно, существуют две возможности «дать» это самое третье: в виде «0, 1, 2» или в виде «-1, 0, 1». Первая система называется несимметричной, вторая — симметричной. Само по себе введение троичной системы счисления выгодно тем, что экономичность хранения данных для каждого разряда выше, чем для любой другой системы счисления. Связано это с тем, что, как говорится, «God counts by E», и наиболее экономичной является система с основанием, равным числу Эйлера (доказательство ищите на стр. 37), а тройка ближе к Е, чем двойка.
Но это ещё не всё — если несимметричная система является просто «расширением» двоичной, позволяя хранить в одной ячейке больше информации, то у симметричной системы выгод гораздо больше.
Одна из таких выгод — это появление значения «0», то есть «не определено». Как правило, 0 передаёт отсутствие значения, а 1 и -1 (иногда вместо цифр используются «+» и «-») — двоичное «да» и «нет». Чем это может быть выгодно? Вообще, зависит от того, как именно задана работа логики. Например, двоичный компьютер столкнувшись с парадоксальным запросом в духе «Второе утверждение истинно — первое утверждение ложно» впадёт в ступор. Троичный компьютер в ответ может просто выдать 0 — он не ответит, но избежит ответа. Или 1 — если работает на «логике парадокса». Ну, и помимо этого многие вопросы можно подвергнуть улучшению — например, не «наличие/отсутствие», а «недостаток/норма/избыток».
— Какой ужасный сон! Повсюду были нули и единицы. И мне показалось, что я увидел двойку!
— Бендер, это просто сон. Двоек не существует.
Выгода вторая — отрицательные значения. В двоичной системе, чтобы показать, что число имеет отрицательное значение, нужен дополнительный знак. В троичной системе если ведущий разряд числа отрицателен, то и число отрицательно. Смена знака с положительного на отрицательный и обратно достигается инвертированием всех его разрядов (что самое интересное, советский троичный компьютер «Сетунь» воспринимал «инвертирование» буквально — отрицательные числа печатались вверх ногами).
Из предыдущих двух пунктов выходит третий — увеличенная скорость вычислений при пониженном объёме занимаемой памяти. В двоичной системе нужно два разряда, чтобы показать знак числа, а вот в троичной системе нужен только один разряд (собственно, само число). Далее — сложение, самая часто выполняемая операция, которую сильно тормозят переносы из разряда в разряд — в случае двоичной системы они происходят в 50 % случаев, а в троичной (симметричной) системе — в 8 случаях из 27, т. е., примерно в 29,6% случаев. Большая скорость и меньшее количество элементов повышают быстродействие троичной машины примерно в 1,6 раза, и, соответственно, уменьшают энергопотребление.
Ну, или как-то так
Казалось бы, почему такое инженерное «wunderwaffe» не применяется повсеместно? На то есть несколько причин. Самая основная — их особенно-то никто и не разрабатывал. Самым известным примером троичного компьютера является советская «Сетунь» 50-х годов разработки. Уникальна она даже не потому, что является первой троичной ЭВМ (но не первой троичной вычислительной машиной), а потому, что сотрудники лаборатории ЭВМ МГУ собирали её буквально на коленке и из подручных материалов, потому что:
…мы должны были для МГУ получить машину М-2, которую сделали в лаборатории Брука. Но получилась неувязочка. На выборах академиков Сергей Львович Соболев — наш руководитель — проголосовал не за Брука, а за Лебедева. Брук обиделся и машину не дал.
Троичная счётная машина Фаулера — первый троичный калькулятор:
Помимо обычной «Сетуни» была также разработана «Сетунь-70» — принципиально новая машина со стеками команд и операндов (разработана, что характерно, к 100-летию со дня рождения Ленина). Ни оригинальная, ни 70-я «Сетуни» в большую серию не пошли — оригинал по не до конца понятным причинам весьма прозаично «задушили», а 70-я была единичным экземпляром. А помимо «Сетуни»… не было ничего. Американцы одно время экспериментировали с троичной логикой, и даже добились некоторого прогресса, но до строительства полноценных ЭВМ дело не дошло (максимум — эмулятор троичной логики «Ternac» для двоичной машины, который был написан на FORTRAN'е). В Канаде в 80-х был разработан чип ROM на основе несимметричной троичной логики (похожий чип можно и создать самостоятельно). В 90-х был разработан троичный язык программирования TriINTERCAL — опять же, на основе несимметричной троичной логики. Какие-то разработки ведутся до сих пор, хотя и не являются приоритетными. Другими словами, для их повсеместного применения просто нет ни опыта, ни материальной базы.
Из этого идёт вторая проблема — мы просто-напросто привыкли к двоичным компьютерам. Изначально они были гораздо более простым решением (сделать детектор «есть ток — нет тока» было гораздо легче, чем «ток ниже — ток номинальный — ток выше» — а ведь силу тока надо было точно контролировать…). Со временем их стало так много, и они стали так хорошо изучены, что нужды в каких-то более продвинутых системах пока (!) не возникает. Тем более, что все существующие на данный момент компьютерные программы заточены именно на бинарную логику. Если вводить троичные компьютеры в использование, то под них либо нужно писать свои собственные программы (что дорого и долго), либо делать их совместимыми с двоичными — а это не всегда возможно, и, возможно, даже сложнее.
Тем не менее, если кто-то всё-таки решится вложить время и деньги в разработку троичных машин и программ, то, потенциально, это приведёт к значительному росту мощностей компьютеров по всему миру, и, теоретически, может даже снизить необходимость в микропроцессорах с нанометровым техпроцессом. Плюс, не стоит забывать про такую весёлую вещь, как квантовые компьютеры. В квантовой физике мало что понимают даже те люди, которые полжизни ей занимаются. Например, квант может быть, как волной, так и частицей. Когда не ясно, в каком состоянии находится квант — это называется «Суперпозицией», отразить которую как раз может помочь дополнительное значение троичной логики. В общем, поле возможностей, открываемое троичными ЭВМ, бесконечно.
Непонятно только, когда и в какую сторону это поле начинать переходить.
Комментарии (98)
chernish2
00.00.0000 00:00+5Не совсем понятно, как может улучшить троичная система счисления работу над определенной предметной областью, например, финансовой информацией.
Vizmaros
00.00.0000 00:00+2В основе троичной логики лежит то, что фундаментальных значений три. И соответственно она будет удобна для ситуаций, где так же есть 3 фундаментальных ответа. В случае финансов они как раз имеются. "Нам должны", "Мы должны", "Никто не должен". При этом нужно учесть, что в этом случае можно явно выделить значения "Не должен" и "Должен 0 рублей".
Rsa97
00.00.0000 00:00+12Это вы какие-то примитивные финансы рассматриваете. В реальных у вас будет одновременно дебет и кредит по каждому счёту. Вполне нормальна ситуация, когда одновременно контрагент должен нам, а мы должны ему.
Vizmaros
00.00.0000 00:00+1Мне показалось что данный пример будет несколько нагляднее. Естественно что может быть 2 числа. ИМХО, в современном мире с высокоуровневыми языками троичная логика будет влиять скорее на производительность программ, нежели изменять их собственную логику. Как минимум, "Не определено" и "Null", в языках появились уже давно. С точки зрения большинства программистов, разницы в том, на уровне языка это значения или железа, никакой нет.
Rsa97
00.00.0000 00:00В большинстве языков 0, NULL и undefined — это разные понятия. И сколько вам тогда состояний понадобится?
Vizmaros
00.00.0000 00:00+1Не имеет значения, что они разные, поскольку undefined и NULL отдельные типы. Значение имеет то, что в троичной логике Boolean может быть в своём собственном значении Undefined, отдельном от системной. То есть можно явно разделить "Я не знаю о чём ты спрашиваешь" и "То, что ты спрашиваешь, неизвестно".
Tarakanator
00.00.0000 00:00+1Есть, четвертый вариант. То, что ты спрашиваешь не имеет смысла.
X>3 неизвестно правда ли это.
Это утверждение ложно. Это и не истина, и не ложь и не неизвестное состояние.Vizmaros
00.00.0000 00:00Сравнивать Boolean и Int? Если мы говорим не на JS, то получим не ещё одно состояние, а Undefined из моего предыдущего ответа. Или, что вероятнее, ошибку приведения типов.
А вариант с логическим парадоксом неприменим, поскольку на ЯП я такое написать не смогу
Tzimie
00.00.0000 00:00+9Непонятно какой толк в троичной логике. В Сетуне элементы были двоичными, трит хранился в двух битах, причем одна из четырех комбинаций не использовалась . По моему, это кастрированная двоичная машина, а не троичная
Alkash-kolyadun Автор
00.00.0000 00:00+4Из интервью с Николаем Брусенцовым, создателем "Сетуни": Юлий Израилевич Гутенмахер строил машину ЛЭМ-1 на феррит-диодных элементах. Мне пришла в голову мысль, что раз транзисторов нет, то можно попытаться делать ЭВМ на этих элементах. [...] они используют пару сердечников под каждый бит — рабочий и компенсационный. И мне пришла в голову идея: а что, если заставить компенсационный сердечник работать. Тогда каждая ячейка становится трехзначной. В результате получилось, что в «Сетуни» количество сердечников было в семь раз меньше, чем в ЛЭМ-1. При этом «Сетунь» имела почти вдвое большую разрядность.
iCerberus
00.00.0000 00:00+4Так было в первой Сетуни. Но уже в Сетуни-70 была реализована однопроводная передача трёхзначных сигналов, что по словам разработчика позволило почти в двое уменьшить число электрических соединений и в два с половиной раза снизить энергопотребление.
uszer
00.00.0000 00:00+1А какими красками заиграла передача информации по RS-485!
OldFashionedEngineer
00.00.0000 00:00При чем тут 485?
uszer
00.00.0000 00:00+1Троичная система исчисления прекрасно ложится на физический принцип передачи, используемый в RS-485.
saege5b
00.00.0000 00:00-3Незачёт. Незнание материала. Ответ не по теме. - так вроде преподаватели говорят студентам?
Стандартный транзистор может переключать либо положительное напряжение, либо отрицательное (очень условно). А как переключать "0" Вольт, это вообще сказочный вопрос.
Да, есть полупроводники которые могут, но они "не очень". Ещё появляются мэмс-реле. Они могут замечательно. Но что делать с "нулём" - это вопросов вопрос. 0 Вольт это может быть и разрыв соединения.
Собственно именно из-за сложности электрической/технической реализации это направление популярностью не пользуется. А эмулировать в двоичной системе - одни убытки.
iig
00.00.0000 00:00+1доказательство ищите на стр. 37
Какой-то неправильный пример. 30 десятичных знаков - это 10 3-значных десятичных чисел.Никак не 1000. 30 двоичных знаков - это 3 3-значных (2^10 = 1024) десятичных числа. 10 > 3. Десятичная система более емкая чем двоичная.
Есть кто-то, кто может прокомментировать, что именно доказано на странице 37? ;)
aborouhin
00.00.0000 00:00+1Под "знаком" там понимается любое из значений, которые может принимать разряд. Как в типографском наборе - чтобы набрать любое 3-хзначное десятичное число, нам надо 3 набора по 10 литер в каждом. Если же в каждом наборе будет только 2 литеры, как в двоичной системе, то такого количества хватит, чтобы набрать любое 15-значное число. Как-то так.
randomsimplenumber
00.00.0000 00:00+1Но это же немного не та задача. Литеру из набора можно использовать только 1 раз, поэтому они нужны с запасом. Символы системы счисления можно использовать без ограничений.
Так с помощью нехитрого математического трюка Штирлиц 50 лет водил за нос всё гестапо ;)
aborouhin
00.00.0000 00:00+3Ну достаточно очевидно, что сложность реализации в железе одного разряда прямо пропорциональна количеству значений, которые он может принимать - так что логика тут есть. Но вот насколько конкретно сложнее реализовать в железе троичные разряды, чем двоичные - в 1,5 раза или таки больше? (про десятеричные, очевидно, речь не идёт, вряд ли кто в своём уме реально проектировал десятеричное ежелезо). Увы, в посте техническая реализация троичных компьютеров обойдена стороной. Как, скажем, выглядел бы элементарный сумматор и т.п.... а это была бы самая интересная часть.
K0styan
00.00.0000 00:00+6И это, скорее всего, дало бы ответ на вопрос "почему забросили". Потому что есть у меня подозрение, что сложность там именно что непропорционально разрядности растёт, и с ростом степени интеграции на больших кристаллах это и выход годных снижало, и частоту повышать не давало.
iig
00.00.0000 00:00+4сложность реализации в железе одного разряда прямо пропорциональна количеству значений, которые он может принимать
Ну, наверное как-то связана, но прямую пропорциональность лучше бы доказать. Ячейка памяти, в которой наличие заряда чего-то кодирует, может хранить не только 0/1 (конденсатору всё равно что хранить). Да, схема записи/чтения/refresh усложняется, но эта схема одна на чип, а ячеек памяти может быть очень много.
вряд ли кто в своём уме реально проектировал десятеричное ежелезо
Декадно-шаговые искатели, декатроны.. Древние инженеры всякое проектировали ;)
Как, скажем, выглядел бы элементарный сумматор
Ужасно ;) Иногда сигналы в шине кодируют 0, 1 или 2, иногда -1,0,1. Кодировать отрицательные числа отдельным троичным разрядом - расточительно, использовать отдельный двоичный разряд для знака - странно, использовать несимметричное кодирование (-1 - отрицательные числа, 0,1 - положительные) - ещё страньше.
КМК троичный компьютер не должен быть калькой с двоичного, только троичным.
aborouhin
00.00.0000 00:00+1но прямую пропорциональность лучше бы доказать
Неточно выразился, имел в виду, что сложность безусловно увеличивается при увеличении основания системы счисления, но насколько именно она увеличивается при увеличении основания в N раз - большой вопрос.
Ndochp
00.00.0000 00:00Вроде было десятеричное. Ну точнее форма записи, где отводили 4 бита на одну десятичную цифру, а не представляли все число в двоичной форме.
Вика говорит, что в такой форме числа могли переваривать VAX, x86, Motorola 68000
Насколько хватает моего английского — в первых версиях это была железная поддержка, потом перешли на софтовую.
BCD
kuokk
00.00.0000 00:00+1похоже, здесь речь идет о "родной" двичной записи целых чисел и BCD коде (https://en.wikipedia.org/wiki/Binary-coded_decimal)
Dekmabot
00.00.0000 00:00+7Смутил вывод что "их особенно-то никто и не разрабатывал", имхо это всё же следствие. Нам преподавали что троичные компьютеры просто выходили сложнее и дороже. И охотно верю, что в те времена было проще сбегать-посмотреть заряжена ли ячейка, чем измерять на сколько и каким зарядом.
И отдельный вопрос - хранение заряда разного полюса в соседних ячейках на магнитной ленте. А ещё были перфокарты, где небыло "наполовину-дырок", так что двоичность вроде как оправдана.
rezdm
00.00.0000 00:00+5Где-то в глубинах подсознания: лет 25 назад я проходил мимо факта о том, что наиболее выгодной является система счисления на основе константы e (2.718281828...). Воплотить такое в практике невозможно из-за иррациональности константы. Из целочисленных систем троичная система ближе двоичной, и попытки воплотить были (см. заметку), но по историческим причинам всё пошло-поехало по двоичной системе.
iig
00.00.0000 00:00+2Все проходили мимо этого факта ;) И тут закралось подозрение, что это нифига не факт, а математическая спекуляция. Кто же будет спорить с самим Эйлером! ;) И выгодность совсем не та, которую все представляли.
С кодированием на основе числа е - интересная тема. Но, наверное, для дискретных вычислений она неприменима.
svischuk
00.00.0000 00:00+2iig
00.00.0000 00:00+2O5.. ;)
Чтобы записать 1000 чисел в десятичной системе, нужно 1000 * 3 = 3000 десятичных ячеек памяти. Или 1000 * 10 = 10 000 двоичных ячеек памяти (2^10=1024). Или 1000 * 7 = 7 000 (3^7 = 2187; 2187 > 1000) троичных ячеек.
Троичная ячейка памяти на феррите по конструкции получилась практически такая же как и двоичная, поэтому в Сетуни это прокатило. А там где феррит не используется - не прокатывает.
А вот этот трюк с числом e в виде решения все друг у друга переписывают не думая.
svischuk
00.00.0000 00:00+1Минимум оборудования измеряют в цифроразрядах, нам надо записать любое число в интервале [0, 999], в десятичной системе нам потребуется 3 разряда принимающих 10 значений, итого получается 3*10=30 цифроразрядов, в двоичной системе нам надо 10 разрядов по 2 цифре, итого 2*10=20 цифроразрядов.
Чтоб сравнить двоичную и троичную лучше взять интервал [0, 524 287] (2^19=524 288), итого в двоичной потребуется 2*19=38 цифроразрядов, а в троичной (3^12=531441) 3*12=36 цифроразрядов (и еще у нас остается небольшой диапазон, не охватываемый двоичной системой).
По ссылке выше, в конце есть рассчитанные значения, насколько они хуже идеального случая с числом Эйлера
Для проверки посчитаем соотношения 38/36=1,056 , 1,062/1,004=1,058, таким образом, с учетом неохваченного диапазона, они раны и все соответствует теории.
Ну а по поводу технологий- для двоичной системы уже сто лет ведут разработки лучшие умы, а для троичной пару раз разрабатывали "в гараже" по приколу.
randomsimplenumber
00.00.0000 00:00Осталось придумать разумное определение, что такое цифроразряд и как их сравнивать. Потому что мне продолжает казаться, что для записи любого числа от 000 до 999 необходимо и достаточно 3 десятичных разряда или 10 двоичных. Напрямую их сравнивать - все равно что груши с хомячками. Умножить на основание - получатся попугаи разных пород, тоже не пригодные для сравнения. Умножить на количество элементов в ячейке памяти? Это зависит от технологии.
svischuk
00.00.0000 00:00Допустим каждая ячейка памяти у нас представлена неполярным конденсатор, тогда для представления числа 524 287 в троичной системе нам надо будет 36 конденсаторов вместо 38 в двоичной.
randomsimplenumber
00.00.0000 00:00Ок. Но ячейка памяти устроена немного сложнее. Нужен ещё как минимум 1 транзистор. Если понадобится напряжение другой полярности - тогда наверное как минимум 2. Если хочется статическую память - в двоичной ячейке 6 транзисторов, в троичной, наверное, больше. Так что если умножать, то на площадь ячейки.
svischuk
00.00.0000 00:00Тогда можно представить что каждая ячейка представлена неким мультиплексором напряжения (сложность изготовления которого линейно растет в зависимости от количества входов). Мне кажется, что цифроразряды имеют право на существование, просто в реальном мире сложно найти реализацию памяти, с линейным ростом сложности от количества входов.
svischuk
00.00.0000 00:00Хотя даже не с линейной растущей сложностью, а сложностью которой можно пренебречь.
randomsimplenumber
00.00.0000 00:00Могу предложить, не вставая с дивана, логарифмическую сложность. Для 16ричной ячейки достаточно 4 конденсаторов и транзисторов. 16ричная система более выгодная получается? ;)
iCerberus
00.00.0000 00:00+1"Вопреки распространенному мнению, будто главное преимущество троичного кода перед двоичным состоит в его экономности, которая обусловлена тем , что 3 ближе чем 2 к основанию натурального логарифма e=2,718... , следует сказать, что эта экономия не превышает 5%, т.е. практически не имеет значения" (c) Н.П. Брусенцов.
Tarakanator
00.00.0000 00:00+2следует сказать, что эта экономия не превышает 5%
3^2/2^3=1.125
1.125>1.05
Tarakanator
00.00.0000 00:00Воплотить такое в практике невозможно из-за иррациональности константы
А точно невозможно? Да, я не могу придумать контрпримера, но не уподобляемся ли мы древнему Риму? Который тоже не знал более прогрессивной позиционной системы сличения? И вероятно они не догадывались что 10 и 1 можно записывать одним знаком.
Rsa97
00.00.0000 00:00В позиционной системе с иррациональным основанием понадобится бесконечное количество цифр для представления одного разряда. Так что, пока не придумаете какой-то другой принцип представления чисел, основание e для цифровой техники непригодно.
Его можно применить в аналоговой технике, где каждый разряд будет задаваться, например, напряжением от 0 до eВ. Но точность вычислений на такой технике будет крайне низкой.Tarakanator
00.00.0000 00:00В позиционной системе с иррациональным основанием понадобится бесконечное количество цифр для представления одного разряда.
Ну если подходить формально, то должно понадобиться число цифр, равное этому числу. Что странно, но это явно не бесконечное количество.
Вот к примеру если основание у нас корень из двух, то достаточно всего двух(а не бесконечности) цифр, для записи любого числа.
По сути это будет двоичная система с мусорными разрядами.
Зачем? да просто показать, что бесконечности цифр не нужно.Rsa97
00.00.0000 00:00Согласен, с бесконечным количеством цифр я неправ.
Однако, если взять для разрядов системы счисления по основанию e цифры 0 и 1, то не все числа можно будет представить. Если же добавить 2, то все числа представимы, но получим очень неудобный математический аппарат.
1e + 1e = 2e
1e + 2e = 10.0200112000010101102011010021021121202021...e
2e + 2e = 11.0200112000010101102011010021021121202021...eTarakanator
00.00.0000 00:00очень неудобный математический аппарат.
В общем виде-возможно.
но тут показали некоторое удобство фиеричной системы счисления.https://habr.com/ru/post/302178/
Возможно у еричной тоже есть преимущества, просто неочевидные.
А возможно нужно брать не с основанием e, а с каким-то другим близким(ближе, чем 3)
isqwonder
00.00.0000 00:00+1Не то, чтобы контр-пример с е-основанием, но с иррациональным, "фи" - "система счисления Бергмана": https://habr.com/ru/post/302178/
Натуральные здесь представимы конечным числом знаков.Rsa97
00.00.0000 00:00Система интересная, но не особо применимая на практике из-за неоднозначности записи чисел:
100Φ ≡ 11Φ ≡ 10.11Φ ≡ 10.1011Φ ≡…
и сложной операции сложения:
1Φ + 1Φ = 10.01Φ
ednersky
00.00.0000 00:00+15во времена, когда 8-битные CPU были большими, мы занимались разработкой векторного управления асинхронными и вентильными электродвигателями.
Так вот, формируя электронным способом трёхфазную синусоиду, постоянно сталкиваешься с делением на три и манипуляциями градусными мерами вроде 120 (1/3 от 360), 60 (1/3 от 180) градусов и так далее.
команд деления у CPU тогда не было, а считать нужно было быстро. Если компенсационную формулу CPU мог пересчитать в фоновом режиме за (сравнительно) большой интервал времени, то по прерыванию, ему нужно было сделать два деления и одно умножение на три.
в какой-то момент мы попробовали перевести измерительные счётчики в троичную систему. Да, инкремент такого счётчика был сравнительно дорогим, но зато вот эти самые деления стали страшно дешёвыми — сдвиг на разряд влево-право. В итоге двигатель крутился, причём исключительно на программном, а не аппаратном (ПЛИС) обеспечении.
эх, давно это было… романтика!
andy_p
00.00.0000 00:00+4На хабре много говорили про троичные компьютеры. Если нужны подробности, зайдите на сайт nedopc.org
Daddy_Cool
00.00.0000 00:00-1Военные всё давно знали. Невыдуманная история с моей военной кафедры. Преподаватель уж не помню по чему так и сказал: "Бит может находиться в трех состояниях - один, ноль и ничего". Я подумал, что это несколько отличается от того, что я читал в книжках, но может я плохо знаю аппаратную часть? И в скажем выключенном компьютере в ячейках памяти действительно ничего? В конце концов необязательно кодировать нулем и пятью вольтами.
Refridgerator
00.00.0000 00:00+2Если рассматривать аналоговый сигнал, то там действительно ноль значит "ничего". Или, другими словами, человек может быть не только жив или мёртв, но и отсутствовать в принципе.
В дискретном преобразовании Фурье основание тройки тоже предпочтительнее чем двойки — но уже не по соображениям скорости, а по соображениям удобства. В частности, в чётных размерах частота Найквиста не имеет фазы.
В системах автоматизации также часто используется логика открыто/закрыто/идёт открытие или закрытие (поскольку в реальном мире мгновенное изменение состояния невозможно).
Daddy_Cool
00.00.0000 00:00Ну да - ну там прозвучало именно "бит", так-то ясно, что физическая реализация может быть разной и со своими ограничениями.
"В частности, в чётных размерах частота Найквиста не имеет фазы".
А можно подробнее? Очень интересно!Refridgerator
00.00.0000 00:00Вкратце и упрощённо. Под FFT обычно понимают и ожидают получить разложение сигнала в виде синусоид, т.е.
Смысл этого в том, чтобы амплитуда синусоиды не зависела от времени измерения. Но по факту FFT даёт результат в виде
,
то есть пару чисел a и b для каждой частоты k, и уже из этих a и b можно получить искомые амплитуду и фазу.
Тут можно заметить, что при k=0 коэффициент a всегда равен нулю. Это значит, что синусоида с нулевой частотой (или постоянная смещения) описывается только одним числом. Например, если сигнал имеет вид [1,1,1,1,1,1,1,1] постоянная смещения равна 1, если сигнал имеет вид [-3,-1,-3,-1,-3,-1,-3,-1] то постоянная смещения равна -2.
Но возможен и другой случай когда наоборот, коэффициент b всегда равен нулю — когда
представимо в виде 
, n целое. Это случай максимально высокой частоты, т.е. сигнал вида [1,-1,1,-1,1,-1,1,-1], и в частотном домене уже не получится оперировать её фазой и сдвинуть например на 45°. Так вот, если размер FFT чётный, такие значения k попадают в разрядную сетку, а если нечётный, то нет. Эти нюансы не имеют значения, когда речь идёт об обычном спектральном анализе или свёртке через FFT, но имеют значение в более сложных алгоритмах, когда кепстры считаются и всякое такое.
edo1h
00.00.0000 00:00+2Изначально они были гораздо более простым решением (сделать детектор «есть ток — нет тока» было гораздо легче, чем «ток ниже — ток номинальный — ток выше» — а ведь силу тока надо было точно контролировать…). Со временем их стало так много, и они стали так хорошо изучены, что нужды в каких-то более продвинутых системах пока (!) не возникает.
…
Тем не менее, если кто-то всё-таки решится вложить время и деньги в разработку троичных машин и программ, то, потенциально, это приведёт к значительному росту мощностей компьютеров по всему мируа почему тогда останавливаться именно на троичных? в nand уже qlc массово используется (в одной ячейке хранятся 4 бита = 16 значений).
neowisard
00.00.0000 00:00+1Насколько я это понимаю , троичная логика неравно системе счисления ( хоть десятичной или 4ричной).
сделать что-то на троичной логике сложно но можно, четвиричная и дальше слишком сложны для мозга, помоему представить форму шара в 5 измерениях могут 1 из 10, аналогично и с логикой, очень тяжело формулировать все в новой логике, когда бинарная так комфортна. так как за машиной на такой логике должны быть и алгоритмы учитываются большую вариативность.
опять же , возможно люди сократят эти шаги 2ичная, 3ичная, 4ричная. .. и сразу начнут худо бедно описывать квантовую которая включает все эти варианты.
iCerberus
00.00.0000 00:00Главное достоинство троичного кода -- симметричность и естественное представление чисел со заком, упрощающие арифметические операции, а вовсе не в том, что 3 больше чем 2. Поэтому дальнейшее увеличение числа основания СС не имеет никакого смысла, т.к. кроме усложнения, ничего сверх того, что умеет троичная СС, "пятеричная" или "семиричная" уже не дадут.
gnomeby
00.00.0000 00:00Дополнительный код, использующийся в двоичной логике для отрицательных чисел, вполне себе красивое решение. Благодаря ему тоже не требуется отдельный вычитатель.
Если бы не это, то имело бы смысл цепляться за симметричность и естественные отрицательные числа, а так не принципиально.
VladimirFarshatov
00.00.0000 00:00Интересно, почему троичные компьютеры рассматриваются с точки зрения однополярного напряжения и токов? симметричные CMOS схемы с двуполярным питанием вполне могут работать на +- логике с нулевым значением (нет напряжения - выход в третьем состоянии). Собственно вся двоичная логика на CMOS с открытым коллектором разве не такова? Только там применяются "токи смещения", что кмк является наоборот усложнением для реализации двоичной логики, не?
randomsimplenumber
00.00.0000 00:00Сложное.. для начала вся булева логика идёт в лес ;) Чему равно 1 xor -1? 1-разрядный сумматор с переносом - как он будет выглядеть по сравнению с двоичным? А многоразрядный быстрый сумматор?
VladimirFarshatov
00.00.0000 00:00+2http://www.wikiznanie.ru/ru-wz/index.php/Троичный_сумматор тут есть вся математика троичного сумматора и даже вариации на базе двоичной логики. Но, как раз аппаратных решений на базе троичной логики -U,0,+U сходу не нашел. Я про этот путь написал.
Refridgerator
00.00.0000 00:00+2На хабре была серия статей о реализации троичной логики в железе. Можете там позадавать такие вопросы.
VladimirFarshatov
00.00.0000 00:00Спасибо, ознакомлюсь. Пока что нагуглил вот такое: http://314159.ru/kushnerov/kushnerov1.pdf оказывается работы в этом направлении активно ведутся, тут ссылки на 2005год.
ShutovKS
00.00.0000 00:00+1Познавательная статья, было интересно узнать что помимо 0,1,2 было ещё и -1,0,1
leveter
00.00.0000 00:00
Кол-во ячеек памяти необходимых для сохранения значения Я собственно чего подумал то... Вот наглядная табличка, где отображено кол-во ячеек памяти необходимых для хранения того или иного значения в памяти компьютера. И в случае троичной системы ячеек памяти надо значительно меньше. А следовательно и работа с арифметическими действиями будет протекать гораздо быстрее, так как значительно уменьшается время обращения к памяти.
Ну это я так... для наглядности. :)
K0styan
00.00.0000 00:00+1Осталось только сравнить сложность реализации ячейки на 2 состояния и на 3 - в транзисторах, p-n переходах, затворах или чём угодно ;-)
stt_s
00.00.0000 00:00'По фалангами пальцев без большого' - считать по костяшками называется, можно было не упоминать
amberovsky
00.00.0000 00:00+1Далее — сложение, самая часто выполняемая операция, которую сильно тормозят переносы из разряда в разряд — в случае двоичной системы они происходят в 50 % случаев, а в троичной (симметричной) системе — в 8 случаях из 27, т. е., примерно в 29,6% случаев. Большая скорость и меньшее количество элементов повышают быстродействие троичной машины примерно в 1,6 раза, и, соответственно, уменьшают энергопотребление.
ЕМНИП сложение выполняется за один такт, быстрее уже некуда
iig
00.00.0000 00:00+1ЕМНИП сложение выполняется за один такт, быстрее уже некуда
От конструкции сумматора зависит. Поразрядный сумматор с переносом - простой но медленный. Быстрый многоразрядный сумматор - сложный. Хотя, если его не из мелкой логики собирать - неважно ;) IMHO, это пересказ какого-то учебника из 70-х.
Tarakanator
00.00.0000 00:00Тут писали что двоичная логика несовершенна т.к. не даёт варианта значение не определено.
Я натыкался на рассуждение, что троичная тоже не совершенна.
Т.к. на каждый вопрос по сути даёшь 2 бита ответа:
1й бит: может ли утверждение быть истинным?
2й бит: может ли утверждение быть ложным?
к примеру
2>1 может быть истинным, но не может быть ложным, ответ 10
1>2 - не может быть истинным, может быть ложным, ответ 01
x>3 - может быть как истинным, так и ложным, ответ 11
Это утверждение ложно. - не может быть ни истинным, ни ложным, ответ 00
domix32
00.00.0000 00:00А ещё возникает вопрос насколько часто что-то будет находиться в нейтральных состояниях. А то оно может конечно и удобно, только окажется, что в 90% случаев бинарная логика будет превалировать, а нейтральный ненужон.
OldFashionedEngineer
00.00.0000 00:00Почему вы не упомянули одну важную особенность, что элементная база и принципы ее работы сильно отличались от того, что используется в современных двоичных компьютерах?
domix32
00.00.0000 00:00+1уменьшают энергопотребление.
Так для того чтобы иметь три уровня сигнала нужно диапазон расширять и всякие преобразования держать на более затратных уровнях. Так что сильно не факт, что энергопотребление уменьшится.
Помнится на хабр писались статьи, как чувак самостоятельно собирал троичный компьютер. Про него бы вспомнить
gnomeby
00.00.0000 00:00+2Интересуюсь темой троичных компов давно и сразу вижу ошибки от неглубокого анализа.
Например, двоичный компьютер столкнувшись с парадоксальным запросом в
духе «Второе утверждение истинно — первое утверждение ложно» впадёт в
ступор. Троичный компьютер в ответ может просто выдать 0 — он не
ответит, но избежит ответа. Или 1 — если работает на «логике парадокса».Это в случае, когда вы кодируете битами логические рассуждения, кодируйте байтами и будет вам 254 варианта между истина и ложно. На двоичной логике прекрасно эмулируется четверичная, восьмеричная и так далее. По сути триада: TRUE, FALSE, NULL в SQL и логические операции между ними это почти ваша троичная логика.
В двоичной системе, чтобы показать, что число имеет отрицательное
значение, нужен дополнительный знак. В троичной системе если ведущий
разряд числа отрицателен, то и число отрицательно.И что? Знак ничего не сжирает, при наличии знака, всех вариаций значений столько же - 256 для восьми бит.
Из предыдущих двух пунктов выходит третий — увеличенная скорость
вычислений при пониженном объёме занимаемой памяти. В двоичной системе
нужно два разряда, чтобы показать знак числа, а вот в троичной системе
нужен только один разряд (собственно, само число). Далее — сложение,
самая часто выполняемая операция, которую сильно тормозят переносы из
разряда в разряд — в случае двоичной системы они происходят в 50 %
случаев, а в троичной (симметричной) системе — в 8 случаях из 27, т. е.,
примерно в 29,6% случаев. Большая скорость и меньшее количество
элементов повышают быстродействие троичной машины примерно в 1,6 раза,
и, соответственно, уменьшают энергопотребление.Это если бы сложение делалось по тупому: ожидая перенос от предыдущей операции. Современное сложение делается по Carry-lookahead_adder или Carry-save_adder для умножений, и длинная регистра и вероятность переносов на скорость не влияют.
Тем не менее, если кто-то всё-таки решится вложить время и деньги в разработку троичных машин и программ, то, потенциально, это приведёт к значительному росту мощностей компьютеров по всему миру, и, теоретически, может даже снизить необходимость в микропроцессорах с нанометровым техпроцессом.
Нет не приведёт. Особенно из-за недостатков троичной системы, о которых в статье ни слова.
А первый и главный недостаток состоит в том, что чтобы чётко отличать уровни в троичных элементах друг от друга вам нужно повышать напряжение. А это уже повышенное тепловыделение.
Например, квант может быть, как волной, так и частицей. Когда не ясно, в
каком состоянии находится квант — это называется «Суперпозицией»,
отразить которую как раз может помочь дополнительное значение троичной
логики.Тут физики меня поправят, но думаю что последняя проблема квантовых компьютеров - это как нативно хранить неопределённое состояние.
Троичная логика для квантовых компьютеров хороша не тем, что можно нативно хранить состояние неопределённости. Проблема квантовых компьютеров - построение длинного стабильного регистра из кубитов. И вот как раз то, что в троичной логике нужно меньше кубитов для достижения того же объёма, и есть преимущество применения недвоичной логики. Но именно троичной здесь дело может и не ограничиться, вполне возможно использование и больших размерностей, если это дело приведёт к уменьшению количества оборудования.
iCerberus
00.00.0000 00:00А первый и главный недостаток состоит в том, что чтобы чётко отличать уровни в троичных элементах друг от друга вам нужно повышать напряжение. А это уже повышенное тепловыделение.
Предполагается, что воплощение в железе троичной логики подразумевает применение сигналов положительной и отрицательной полярности. Так что по крайней мере с различимостью сигналов проблем быть не должно.
gnomeby
00.00.0000 00:00Не подскажите радиодеталь толерантную к полярности, которую можно использовать для этого? Ну кроме реле.
iCerberus
00.00.0000 00:00Может вам сразу троичный компьютер построить? ;-)
gnomeby
00.00.0000 00:00Так в этом то и вопрос. Все пускающие слюни по троичной логике думают, что это радиодеталь сама собой появится.
iCerberus
00.00.0000 00:00+1Ну, сама собой она естественно не появится. Насколько я понимаю, основным препятствием для создания троичных логических элементов на современном технологическом уровне являются ограничения сложившейся технологии массового производства КМОП микросхем (слышал краем уха что технология "кремний на изоляторе" вроде как позволяет обойти имеющиеся ограничения, но она слишком дорогая). Тем не менее время от времени попадаются публикации (как например эта https://pandia.ru/text/80/614/58974.php ), свидетельствующие, что исследования в этом направлении пусть и не спеша, но ведутся. Так что была бы поставлена задача, а решение найдётся.
iig
00.00.0000 00:00Так что была бы поставлена задача, а решение найдётся.
Вот именно ;) Для какой-такой задачи необходима именно троичная система? Лёгкое целочисленное деление на 3, вот собственно и всё. Преимущества троичной системы для прочих математических операций не доказаны. Для хранения - никто не собирается городить новую элементарную базу для достижения теоретических 5% экономии.
iCerberus
00.00.0000 00:00+1Египетские пирамиды без компьютеров строились, так что при желании человечество может вообще без компьютеров прожить :-) Но это не значит, что не нужно стремиться к лучшему. Троичный компьютер позволяет делать всё то же, что и двоичный, только более простым и естественным образом, без "костылей". Чем перечислять все преимущества троичной арифметики, проще отправить вас читать Брусенцова. Очевидно, что если бы всё ограничивалось 5-ти процентной экономией, то не было бы такого количества работ, посвящённых троичной логике -- например, вот перечень использованной литературы в одной попавшейся мне публикации, посвящённой созданию троичного логического элемента:
[1] Hayes B. Third base // American Scientist. - 2001. - V. 89. № 6. - P. 490–494.
[2] Korotkov A.S., Morozov D.V., Pilipko M.M., Sinha A. Delta-Sigma ADC for Ternary Code System (Part I: Modulator Realization) // Proc. Int. Symp. Signals, Circuits and Systems. - July 2007. - V. 1 - P. 1–4.
[3] Д. Кнут. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. - М.: МИР, 1977.
[4] Брусенцов Н.П. Опыт разработки троичной вычислительной машины // Вестник МГУ. Сер. 1: математика, механика. - 1965. - №2. - С. 39–48.
[5] Брусенцов Н.П. Заметки о троичной цифровой технике // Сб. научных трудов Юбилейной Международной научно-технической конференции 50 лет модулярной арифметике, ноябрь 2005. - М., Зеленоград, 2006. - C. 618–641.
[6] Ji-Zhong Shen, Mao-Qun Yao, Xie-Xiong Chen, Hua-Hua Chen Ternary BiCMOS circuit structure and its design at switch level // Proc. 5th Int. Conf. ASIC. - Oct. 2003. - V. 1. - P. 581–585.
[7] Xunwei Wu; Penjun Wang; Yinshui Xia. Design of ternary Schmitt triggers based on its sequential characteristics // Proc. 32nd IEEE Int. Symp. Multiple-Valued Logic. - May 2002. - P. 156–160.
[8] Waho T., Chen K.J., Yamamoto M. Resonant-tunneling diode and HEMT logic circuits with multiple thresholds and multilevel output // IEEE J. Solid-State Circuits. - Feb. 1998. - V. 33. - № 2. - P. 268–274.
[9] Waho T.; Hattori K.; Takamatsu Y. Flash analog-to-digital converter using resonant-tunneling multiple-valued circuits // Proc. 31st IEEE Int. Symp. Multiple-Valued Logic. - May 2001. - P. 94–99.
[10] Nunez J., Quintana J.M., Avedillo M.J. Limits to a Correct Evaluation in RTD-based Ternary Inverters // ICECS’06. - Dec. 2006. - P. 403–406.
[11] Nunez J., Quintana J.M., Avedillo M.J. Correct DC Operation in RTD-based Ternary Inverters // 2nd IEEE Int. Conf. NEMS’07. - Jan. 2007. - P. 860–865.
[12] Uemura T., Baba T. A three-valued D-flip-flop and shift register using multiple-junction surface tunnel transistors // Proc. 31st IEEE Int. Symp. Multiple-Valued Logic. - May 2001. - P. 89–93.
[13] Dhande A.P., Ingole V.T. Design Of 3-Valued R-S & D Flip-Flops Based on Simple Ternary Gates // 2nd World Enformatika Conference, WEC'05. - Feb. 2005. - P. 62–65.
[14] Патент Германии DE 198 32 101 A1 Realisierung Ternärer Grundschaltungen in CMOS Technologie, J. Stackelberg. - 27.01.2000.
[15] Патент Японии № 2005036757 Ternary logic inverter circuit, N. Kazuto. - 08.02.2007.
[16] Toto F., Saletti R. CMOS dynamic ternary circuit with full logic swing & zero-static power consumption // Electronics Letters. - May 1998. - V. 34. - № 11. - P. 1083–1084.
[17] Mateo D.; Rubio A. Design and implementation of a 5×5 trits multiplier in a quasi-adiabatic ternary CMOS logic // IEEE J. Solid-State Circuits. - July 1998. - V. 33. - № 7. - P. 1111–1116.
[18] Herrfeld A, Hentschke S. Ternary Multiplication Circuits Using 4-Input Adder Cells and Carry Look-Ahead // Proc. 29th IEEE Int. Symp. Multiple-Valued Logic. - May 1999. P. 174–179.
[19] Gundersen H., Jensen R., Berg Y. A novel ternary switching element using CMOS recharge semi floating-gate devices // Proc. 35th Int. Symp. Multiple-Valued Logic. - May 2005. - P. 54–58.
[20] Gundersen H., Berg Y. A novel balanced ternary adder using recharged semi-floating gate devices // Proc. 36th Int. Symp. Multiple-Valued Logic. - May 2006. - P. 18–21.
[21] Berg Y., Jensen R., Lomsdalen J., Gundersen H., Aunet S. Fault Tolerant CMOS Logic Using Ternary Gates // Proc. 37th Int. Symp. Multiple-Valued Logic. - May 2007. - P. 38–38.
[22] Connell C.L., Balsara P.T. A novel single-rail variable encoded completion detection scheme for self-timed circuit design using ternary multiple valued logic // Proc. IEEE 2nd Dallas CAS Workshop Low Power/Low Voltage Mixed Signal Circuits Systems. - March 2001. - P. 7–10.
[23] C.N. Rozon, H.T.Mouftah. Realization of a three-valued logic built-in testing structure // IEEE J. Solid-State Circuits. - June 1990. - V. 25. - №. 3. - P. 814–820.
[24] Ji-Zhong Shen, Zhi-Gang Zhu, Mo Zhu. The general structure and design method of ternary monostable multivibrator // Proc. 5th Int. Conf. ASIC. - Oct. 2003. - V. 1. - P. 586–590.
[25] Патент Японии № 2005080257 CMOS driver circuit and CMOS inverter circuit, Japan Radio CO Ltd (F. Hideki). - 24.03.2005.
[26] Патент Японии № 2007208512 (WO 2007 088901) Three-valued logic function circuit, Japan Advanced Inst of Science and Tech (H. Yasushi, S. Masaaki). - 09.08.2007.
Как видите, в списке фигурирует не только Брусенцов ;-)
iig
00.00.0000 00:00Троичный компьютер позволяет делать всё то же, что и двоичный, только более простым и естественным образом, без "костылей".
Кроме деления на 3, какие ещё преимущества? ;) Зато есть фундаментальный недостаток - неудобно делить на 2. Все алгоритмы с делением на 2 начинают работать немного хуже ;)
Очевидно, что если бы всё ограничивалось 5-ти процентной экономией, то не было бы такого количества работ, посвящённых троичной логике
Неочевидно. Ради 5% экономии производители электроники уже вовсю клепали бы троичную память и троичные процессоры. А учёные занимаются разными вещами, кто за гранты, кто just for fun. Некоторые вещи могут пригодиться через пару сотен лет (как некоторые особенности простых чисел, спасибо Эйлеру), некоторые, возможно, никогда.
iCerberus
00.00.0000 00:00Ну да, других задач кроме как делить числа на 2 у компьютера нет ))
Кроме деления на 3, какие ещё преимущества?
Устойчивость к ошибкам округления, например.
iCerberus
00.00.0000 00:00Оттуда что при использовании СС с нечётным основанием математическое ожидание распределения ошибок округления равно нулю, т.е. такие системы не подвержены накоплению ошибок. Само округление производится простым отсечением лишних разрядов, т.к. значение отбрасываемой части всегда меньше половины младшего сохраняемого разряда.
iig
00.00.0000 00:00Логично. Это невредное свойство. Возможно, его даже можно использовать с пользой.
А теперь представьте, как выглядит умножение/деление в этой системе.
iig
00.00.0000 00:00А в чем полезность такого округления? В любом случае при округлении информация из младших разрядов теряется безвозвратно.
gnomeby
00.00.0000 00:00В современном наборе софта, когда уже всё написано никакой оригинальный железный подход не имеет значения. Тут я соглашусь.
iig
00.00.0000 00:00А вот тут я не соглашусь ;) Любой подход оправдан, если он достаточно хорош. Можно написать новый софт, разработать новую память и ALU, чтобы что? ;)
gnomeby
00.00.0000 00:00+1Чем перечислять все преимущества троичной арифметики, проще отправить вас читать Брусенцова.
Бруснецов жил во времена когда компы вручную паяли и Сетунь благодаря троичной логике был прост в производстве. А ещё память тогда была в дефиците, и нативность логики в железе была важна. Сейчас ситуация несколько другая.
Jury_78
Разве языкам высокого уровня не все равно какая система счисления используется? Компиляторы конечно уже специфично...
Demacr
Как бы и да и нет. Потому что на примере PostgreSQL можно использовать троичный boolean(а скорее это будет toolean) и в нём хранить одно из трёх значений: true, false или NULL. Так что теоретически всё равно, но для раскрытия производительности логику придётся переделывать.