Троичная система счисления
Трои́чная систе́ма счисле́ния — позиционная система счисления с целочисленным основанием, равным 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}[источник не указан 3750 дней]. В распечатках ЭВМ «Сетунь» использовалось кодирование {1,0,1}[1]. Троичные цифры можно обозначать любыми тремя знаками {A,B,C}, но при этом дополнительно нужно указать старшинство знаков, например, A<B<C.
Физические реализацииПравить
В цифровой электронике, независимо от варианта троичной системы счисления, одному троичному разряду в троичной системе счисления соответствует один троичный триггер как минимум на трёх инверторах с логикой на входе или два двоичных триггера как минимум на четырёх инверторах с логикой на входе.
Представление чисел в троичных системах счисленияПравить
Несимметричная троичная система счисленияПравить
Примером представления чисел в несимметричной троичной системе счисления может служить запись в этой системе целых положительных чисел:
Десятичное число | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
Троичное число | 0 | 1 | 2 | 10 | 11 | 12 | 20 | 21 | 22 | 100 | 101 |
Если в десятичной системе счисления имеется 10 цифр и веса соседних разрядов различаются в 10 раз (разряд единиц, разряд десятков, разряд сотен), то в троичной системе используются только три цифры и веса соседних разрядов различаются в три раза (разряд единиц, разряд троек, разряд девяток, …). Цифра 1, написанная первой левее запятой, обозначает единицу; эта же цифра, написанная второй левее запятой, обозначает тройку и т. д.
Несимметричная троичная система счисления является частным случаем спаренных (комбинированных) показательных позиционных систем счисления, в которой ak — из троичного множества a={0,1,2}, b=3, веса разрядов равны 3k.
Показательные системы счисленияПравить
В показательных позиционных троичных системах счисления используются две системы:
- внутриразрядная система кодирования с основанием с, числа которой используются для записи цифр и
- приписная межразрядная система счисления с основанием b.
Целое число в показательной позиционной системе счисления представляется в виде суммы произведений значений в разрядах (цифр) — на k-е степени числа b:
- , где:
- k — число от 0 до n-1, номер числового разрядa,
- n — число разрядов,
- с — основание системы кодирования, с равно размерности множества a={0,1,…,c-1} из которого берутся цифры ak,
- ak — целые числа из множества a, называемые цифрами,
- b — число, основание межразрядной показательной весовой функции,
- bk — числа межразрядной функции, весовые коэффициенты разрядов.
Каждое произведение в такой записи называется (a, b)-ичным разрядом.
При c=b образуются (b, b)-ичные системы счисления с произведением — akbk и суммой — , которые при b=3 превращаются в обычную (3,3)-ичную (троичную) систему счисления. При записи первый индекс часто опускается, иногда, когда есть упоминание в тексте, опускается и второй индекс.
Весовой коэффициент разряда — bk — приписной и, в общем случае, может быть необязательно показательной функцией от номера разряда — k, и необязательно степенью числа 3. Множество значений ak более ограниченно и более связано с аппаратной частью — числом устойчивых состояний триггеров или числом состояний группы триггеров в одном разряде регистра. В общем случае, ak могут быть тоже необязательно из троичного множества a={0,1,2}, но, чтобы спаренной системе быть троичной и называться троичной, как минимум, одна из двух систем должна быть троичной. ak-е ближе к аппаратной части и по ak-м из множества a={0,1,2} или из множества a={-1,0,+1}, определяется система кодирования: несимметричная троичная или симметричная троичная.
Показательные троичные системы счисленияПравить
Целое число в показательной позиционной троичной системе записывают в виде последовательности его цифр (строки цифр), перечисляемых слева направо по убыванию старшинства разрядов:
В показательных системах счисления значениям разрядов приписываются весовые коэффициенты , в записи они опускаются, но подразумевается, что k-й разряд справа налево имеет весовой коэффициент равный .
Из комбинаторики известно, что количество записываемых кодов равно числу размещений с повторениями:
где a = 3 — 3-элементное множество a = {0, 1, 2}, из которого берутся цифры ak, n — число элементов (цифр) в числе x3,b.
Количество записываемых кодов не зависит от основания показательной функции — b, которое определяет диапазон представляемых числами x3,b величин.
Дробное число записывается и представляется в виде
где m — число разрядов дробной части числа справа от запятой;
- при m = 0 дробная часть отсутствует, число — целое,
- при ak из троичного множества a = {0, 1, 2} и b = 1 образуется непозиционная троичная система счисления с одинаковыми весовыми коэффициентами всех разрядов равными 1k = 1,
- при ak из двоичного множества a = {0, 1} и b = 3 в сумме будут только целые степени — 3k,
- при ak из троичного множества a = {0, 1, 2} и b = 3 в сумме будут целые и удвоенные степени 3, система счисления становится обычной несимметричной троичной системой счисления, ak удовлетворяют неравенству , то есть ,
- при ak из десятичного множества a = {0, 1, ..., 9} и b = 3 в сумме будут целые степени 3 умноженные на 1, 2, ..., 9.
В некоторых случаях этого может оказаться недостаточно, в таких случаях можно применить стро́енные (комтринированные), счетверённые и другие системы счисления.
Троичные системы счисления с дополнительным сомножителемПравить
В показательных позиционных троичных системах счисления в вес разряда можно ввести дополнительный сомножитель. Например, сомножитель (b/с):
В общем случае c≠3.
При ak из a={0,1,2}, b=3 и c=3 образуется обычная несимметричная троичная система счисления.
При a=2, b=3 и c=2 образуется (2,3,2)-ичная система счисления с дополнительным нецелочисленным весовым коэффициентом в произведении равным (3/c)=(3/2)=1,5.
При других значениях a, b и c образуются другие показательные позиционные системы счисления с дополнительным сомножителем (b/c), число которых бесконечно.
Возможны бесконечные множества и других составных систем счисления.
Кодирование троичных цифрПравить
Одна троичная цифра может кодироваться разными способами.
Трёхуровневые системы кодирования троичных цифрПравить
1. Трёхуровневое кодирование троичных цифр (3-Level LevelCoded Ternary, 3L LCT, «однопроводное»):
Число трёхуровневых систем кодирования троичных цифр равно числу перестановок:
- из них одна
1.1. Симметричная {-1,0,+1}
+U — (+1) ;
0 — (0) ;
-U — (-1) ,
1.2. Сдвинутая на +1 {0,1,2}
1.3. Сдвинутая на +2 {1,2,3}
Двухуровневые системы кодирования троичных цифрПравить
2. Двухбитные двоичнокодированые троичные цифры (2-Bit BinaryCodedTernary, 2B BCT representation, «двухпроводное») с использованием 3-х кодов из 4-х возможных[2]:
Число возможных 2B BCT систем кодирования троичных цифр равно числу сочетаний без повторения:
- умноженному на число перестановок в каждом наборе из 3-х цифр:
- то есть 4*6 = 24.
Вот некоторые из них:
2.1.[3]
(1,0) — 2 ;
(0,1) — 1 ;
(0,0) — 0.
2.2.
(1,1) — 2;
(0,1) — 1;
(0,0) — 0.
3. Двухбитные двоичнокодированые троичные цифры (2-Bit BinaryCodedTernary, 2B BCT representation, «двухпроводное») с использованием всех 4-х кодов из 4-х возможных (два из 4-х кодов кодируют одну и туже троичную цифру из 3-х).
3.1.
Вот одна из них[4]:
(0,0) — «0»
(1,1) — «0»
(0,1) — «-1»
(1,0) — «+1»
4. Трёхбитные двоичнокодированые троичные цифры (3-Bit BinaryCodedTernary, 3B BCT representation, «трёхпроводное») с использованием 3-х кодов из 8-ми возможных:
Число возможных 3B BCT систем кодирования троичных цифр равно числу сочетаний без повторения:
- умноженному на число перестановок в каждом наборе из 3-х цифр:
- то есть 54*6 = 324.
Вот некоторые из них:
3.1.
(1,0,0) — 2;
(0,1,0) — 1;
(0,0,1) — 0.
3.2.
(0,1,1) — 2;
(1,0,1) — 1;
(0,1,0) — 0.
3.3.
(1,1,1) — 2;
(0,1,1) — 1;
(0,0,1) — 0.
3.4.
(0,0,0) — 2;
(1,0,0) — 1;
(1,1,0) — 0.
3.5.
(1,0,0) — 2;
(1,1,0) — 1;
(1,1,1) — 0.
3.6.
(0,1,1) — 2;
(0,0,1) — 1;
(0,0,0) — 0.
3.7.
(1,0,1) — 2;
(0,1,0) — 1;
(0,0,0) — 0.
и др.
Сравнение с двоичной системой счисленияПравить
При поразрядном сравнении троичная система счисления оказывается более ёмкой, чем двоичная система счисления.
При девяти разрядах двоичный код имеет ёмкость чисел, а троичный код имеет ёмкость числа, то есть в раза больше.
При двадцати семи разрядах двоичный код имеет ёмкость чисел, а троичный код имеет ёмкость чисел, то есть в раз больше.
СвойстваПравить
Троичная позиционная показательная несимметричная система счисления по затратам числа знаков (в трёхразрядном десятичном числе 3*10=30 знаков) наиболее экономична из позиционных показательных несимметричных систем счисления.[5][6][7][8][9] А. Кушнеров[6] приписывает эту теорему Джону фон Нейману.
Перевод целых чисел из десятичной системы счисления в троичнуюПравить
Для перевода целое десятичное число делят нацело с остатком (целочисленное деление) на 3 до тех пор, пока частное больше нуля. Остатки, записанные слева направо от последнего к первому являются целым несимметричным троичным эквивалентом целого десятичного числа.[10][11]
Пример: десятичное целое число 4810,10 переведём в несимметричное троичное целое число:
число = 4810,10 делим на 3, частное = 16, остаток a0 = 0
частное = 1610,10 делим на 3, частное = 5, остаток a1 = 1
частное = 510,10 делим на 3, частное = 1, остаток a2 = 2
частное = 110,10 делим на 3, частное = 0, остаток a3 = 1
Частное не больше нуля, деление закончено.
Теперь, записав все остатки от последнего к первому слева направо, получим результат 4810,10 = (a3a2a1a0)3,3 = 12103,3.
Симметричная троичная система счисленияПравить
Позиционная целочисленная симметричная троичная система счисления была предложена итальянским математиком Фибоначчи (Леонардо Пизанский) (1170—1250) для решения «задачи о гирях».[12] Задачу о наилучшей системе гирь рассматривал Лука Пачоли (XV в.). Частный случай этой задачи был опубликован в книге французского математика Клода Баше де Мезириака «Сборник занимательных задач» в 1612 году (русский перевод книги К. Г. Баше «Игры и задачи, основанные на математике» вышел в Петербурге только в 1877 г.). В 1797 году в России был издан закон «Об учреждении повсеместно в Российской империи верных весов питейных и хлебных мер». Для взвешивания товаров допускались только гири следующих весов: в 1 и 2 пуда, в 1, 3, 9, 27 фунтов и в 1, 3, 9, 27 и 81 золотник. Как приложение к закону была издана таблица для взвешивания товаров от 1 фунта до 40 фунтов при помощи гирь в 1, 3, 9, 27 фунтов и для взвешивания товаров от 1 золотника до 96 золотников при помощи гирь в 1, 3, 9, 27 и 81 золотник[13]. Этой задачей занимался петербургский академик Леонард Эйлер, а позже интересовался Д. И. Менделеев.[14][15][16][17][18]
Симметричность при взвешивании на рычажных весах использовали с древнейших времён, добавляя гирю на чашу с товаром. Элементы троичной системы счисления были в системе счисления древних шумеров,[19] в системах мер, весов и денег, в которых были единицы равные 3. Но только в симметричной троичной системе счисления Фибоначчи объединены оба этих свойства.
Симметричная система позволяет изображать отрицательные числа, не используя отдельный знак минуса. Число 2 изображается цифрой 1 в разряде троек и цифрой (минус единица) в разряде единиц. Число −2 изображается цифрой (минус единица) в разряде троек и цифрой 1 в разряде единиц.
Возможны шесть соответствий цифр (знаков) троичной симметричной системы счисления и цифр (знаков) троичной несимметричной системы счисления:
1. | 2. | 3. | 4. | 5. | 6. | |
---|---|---|---|---|---|---|
1 | 2 | 1 | 0 | 0 | 2 | 1 |
0 | 1 | 0 | 2 | 1 | 0 | 2 |
1 | 0 | 2 | 1 | 2 | 1 | 0 |
В соответствии 2. сохраняются числовые значения 0 и 1.
Десятичная система | −9 | −8 | −7 | −6 | −5 | −4 | −3 | −2 | −1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Троичная несимметричная | −100 | −22 | −21 | −20 | −12 | −11 | −10 | −2 | −1 | 0 | 1 | 2 | 10 | 11 | 12 | 20 | 21 | 22 | 100 |
Троичная симметричная | 100 | 101 | 111 | 110 | 111 | 11 | 10 | 11 | 1 | 0 | 1 | 11 | 10 | 11 | 111 | 110 | 111 | 101 | 100 |
В троичной симметричной системе счисления знак 1 можно заменить знаком (не числом) i или 2 и, во втором случае, использовать для троичной симметричной системы счисления {-1,0,+1} знаки троичной несимметричной системы {2,0,1}.
СвойстваПравить
Благодаря тому что основание 3 нечётно, в троичной системе возможно симметричное относительно нуля расположение цифр: −1, 0, 1, с которым связано шесть ценных свойств:
- Естественность представления отрицательных чисел;
- Отсутствие проблемы округления: обнуление ненужных младших разрядов округляет — приближает число к ближайшему «грубому».
- Таблица умножения в этой системе, как отметил О. Л. Коши, примерно в четыре раза короче.[14](стр.34).
- Для изменения знака представляемого числа нужно изменить ненулевые цифры на симметричные.
- При суммировании большого количества чисел значение для переноса в следующий разряд растёт с увеличением количества слагаемых не линейно, а пропорционально квадратному корню числа слагаемых.
- По затратам количества знаков на представление чисел она равна троичной несимметричной системе.
Представление отрицательных чиселПравить
Наличие положительной и отрицательной цифр позволяет непосредственно представлять как положительные, так и отрицательные числа. При этом нет необходимости в специальном разряде знака и не надо вводить дополнительный (или обратный) код для выполнения арифметических операций с отрицательными числами. Все действия над числами, представленными в троичной симметричной системе счисления, выполняются, естественно, с учётом знаков чисел. Знак числа определяется знаком старшей значащей цифры числа: если она положительна, то и число положительно, если отрицательна, то и число отрицательно. Для изменения знака числа надо изменить знаки всех его цифр (то есть инвертировать его код инверсией Лукасевича). Например:
ОкруглениеПравить
Другим полезным следствием симметричного расположения значений цифр является отсутствие проблемы округления чисел: абсолютная величина части числа, представленной отбрасываемыми младшими цифрами, никогда не превосходит половины абсолютной величины части числа, соответствующей младшей значащей цифре младшего из сохраняемых разрядов. Следовательно, в результате отбрасывания младших цифр числа получается наилучшее при данном количестве оставшихся цифр приближение этого числа, и округление не требуется.
Перевод чисел из десятичной системы в троичнуюПравить
Перевод чисел из десятичной системы в троичную и соответствующий ему вопрос о гирях подробно изложены в книгах[20][21]. Там же рассказано о применении троичной системы гирь в русской практике.
Перевод в другие системы счисленияПравить
Всякое число, записанное в троичной системе счисления с цифрами 0, 1, −1, можно представить в виде суммы целых степеней числа 3, причём если в данном разряде троичного изображения числа стоит цифра 1, то соответствующая этому разряду степень числа 3 входит в сумму со знаком «+», если же цифра −1, то со знаком «-», а если цифра 0, то вовсе не входит. Это можно представить формулой
- , где
- — целая часть числа,
- — дробная часть числа,
причём коэффициенты K могут принимать значения { 1, 0, −1 }.
Для того чтобы число, представленное в троичной системе, перевести в десятичную систему, надо цифру каждого разряда данного числа умножить на соответствующую этому разряду степень числа 3 (в десятичном представлении) и полученные произведения сложить.
Практические примененияПравить
- Работая в палате мер и весов, Д. И. Менделеев, с учётом симметричной троичной системы счисления, разработал цифровой ряд значений весов разновеса для взвешивания на лабораторных весах, который используется по сей день.
- Симметричная троичная система использовалась в советской ЭВМ Сетунь.
Таблицы сложения в троичных системах счисленияПравить
В троичной несимметричной системе счисленияПравить
2 | 02 | 10 | 11 |
---|---|---|---|
1 | 01 | 02 | 10 |
0 | 00 | 01 | 02 |
+ | 0 | 1 | 2 |
В троичной симметричной системе счисленияПравить
1 | 00 | 01 | 11 |
---|---|---|---|
0 | 01 | 00 | 01 |
1 | 11 | 01 | 00 |
+ | 1 | 0 | 1 |
Девятеричная форма представления командПравить
Представление команд троичным кодом при программировании и при вводе в машину неудобно и неэкономно, поэтому вне машины применяется девятеричная форма представления команд. Девятеричные цифры сопоставляются парам троичных цифр:
При выводе из машины отрицательные девятеричные цифры обозначают буквами:
Девятеричная цифра | ||||
---|---|---|---|---|
Буква латинского алфавита | Z | Y | X | W |
Буква русского алфавита | Ц | У | Х | Ж |
См. такжеПравить
ПримечанияПравить
- ↑ Н. А. Криницкий, Г. А. Миронов, Г. Д. Фролов, под ред. М. Р. Шура-Бура. Глава 10. Программно-управляемая машина «Сетунь» // Программирование (рус.). — М., 1963.
- ↑ http://314159.ru/kushnerov/kushnerov1.pdf Архивная копия от 7 октября 2013 на Wayback Machine Троичная цифровая техника. Ретроспектива и современность
- ↑ BCT: Binary Coded Ternary (неопр.). Дата обращения: 30 сентября 2012. Архивировано 21 января 2022 года.
- ↑ Тринари. Форум. Аппаратная часть. Сумматор. Блок 003 (неопр.). Дата обращения: 29 сентября 2012. Архивировано из оригинала 30 марта 2022 года.
- ↑ С. В. Фомин. Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике). Архивная копия от 16 октября 2004 на Wayback Machine (альтернативная ссылка Архивная копия от 2 июня 2013 на Wayback Machine)
- ↑ 1 2 А. Кушнеров Троичная цифровая техника. Ретроспектива и современность. Архивная копия от 7 октября 2013 на Wayback Machine
- ↑ https://web.archive.org/web/20120111141145/http://misterkruger.narod.ru/math/base3rus.htm Удивительное свойство троичной системы счисления]
- ↑ Экономичность систем счисления с показательной весовой функцией (неопр.). Дата обращения: 22 января 2019. Архивировано 29 октября 2018 года.
- ↑ О. А. Акулов, Н. В. Медведев. Информатика и вычислительная техника. 4-е изд. — М.: Омега-Л, 2007. (Раздел I, Гл.3.3)
- ↑ Перевод десятичных целых чисел в троичные несимметричные целые числа (неопр.). Дата обращения: 22 января 2019. Архивировано 22 января 2019 года.
- ↑ http://algolist.manual.ru/maths/teornum/count_sys.php Архивная копия от 31 марта 2022 на Wayback Machine Перевод из системы с большим основанием — в систему с меньшим
- ↑ «Троичный принцип» Николая Брусенцова Архивная копия от 11 июня 2008 на Wayback Machine.
- ↑ Депман И. Я. Возникновение системы мер и способов измерения величин. Выпуск 1. (Москва: Государственное учебно-педагогическое издательство Министерства просвещения РСФСР (Учпедгиз), 1956. — Серия «Библиотека школьника»). Глава VIII. § Использование наиболее удобной системы гирь в России. Стр.118
- ↑ 1 2 С. Б. Гашков. § 11. Д. И. Менделеев и троичная система // Системы счисления и их применение. — М.: МЦНМО, 2004. — (Библиотека «Математическое просвещение»). Архивная копия от 12 января 2014 на Wayback Machine Архивированная копия (неопр.). Дата обращения: 18 октября 2009. Архивировано из оригинала 12 января 2014 года. В Google Chrome после нажатия на PDF(333Kb) нужно стронуть одну из боковых сторон рамки браузера.
- ↑ И. Я. Депман. История арифметики. Пособие для учителей. Издание второе, исправленное. Издательство «Просвещение», Москва, 1965. Глава I. Натуральное число. 7. Задача Баше — Менделеева, стр.36.
- ↑ Е. С. Давыдов, Наименьшие группы чисел для образования натуральных рядов, Спб., 1903, 36 стр.
- ↑ В. Ф. Гартц, Лучшая система для весовых гирь, Спб., 1910, 36 стр.
- ↑ Ф. А. Слудский, О свойствах степеней двух и трёх. «Математический сборник», ч. III, стр. 214.
- ↑ Юрий Ревич «Наследники Бэббиджа» // «Домашний компьютер», № 12, 1 декабря 2002 года.
- ↑ И. Я. Депман. «Меры и метрическая система», Учпедгиз, 1955.
- ↑ И. Я. Депман. «Возникновение системы мер и способов измерения величин», вып. 1, Учпедгиз, 1956.
ЛитератураПравить
- Брусенцов Н. П., С. П. Маслов, В. П. Розин, А. М. Тишулина «Малая цифровая вычислительная машина Сетунь», Издательство Московского университета, 1965.
- Фомин С. В. Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике).
В статье есть список источников, но не хватает сносок. |