Русская Википедия:Троичная система счисления

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Системы счисления Трои́чная систе́ма счисле́ния — позиционная система счисления с целочисленным основанием, равным 3.

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

Один троичный разряд называется трит (сокращение от trinary digit).

Троичные цифры

В несимметричной троичной системе счисления чаще применяются цифры {0,1,2}, а в троичной симметричной системе счисления знаки {−,0,+}, {−1,0,+1}, {Шаблон:Overline,0,1}, {1,0,1}, {i,0,1}, {N,O,P}, {N,Z,P} и цифры {2,0,1}, {7,0,1}Шаблон:Нет АИ. В распечатках ЭВМ «Сетунь» использовалось кодирование {Шаблон:Перевёрнутая единица,0,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, написанная первой левее запятой, обозначает единицу; эта же цифра, написанная второй левее запятой, обозначает тройку и т. д.

Несимметричная троичная система счисления является частным случаем спаренных (комбинированных) показательных позиционных систем счисления, в которой a_k — из троичного множества a={0,1,2}, b=3, веса разрядов равны 3^k.

Показательные системы счисления

В показательных позиционных троичных системах счисления используются две системы:

1. внутриразрядная система кодирования с основанием с, числа которой используются для записи цифр и
2. приписная межразрядная система счисления с основанием b.

Целое число в показательной позиционной системе счисления представляется в виде суммы произведений значений в разрядах (цифр) — <math>\ a_k</math> на k-е степени числа b:

<math>x_{a,b} = \sum_{k=0}^{n-1} a_k b^k</math>, где:

• k — число от 0 до n-1, номер числового разрядa,
• n — число разрядов,
• с — основание системы кодирования, с равно размерности множества a={0,1,…,c-1} из которого берутся цифры a_k,
• a_k — целые числа из множества a, называемые цифрами,
• b — число, основание межразрядной показательной весовой функции,
• b^k — числа межразрядной функции, весовые коэффициенты разрядов.

Каждое произведение <math>\ a_k b^k</math> в такой записи называется (a, b)-ичным разрядом.

При c=b образуются (b, b)-ичные системы счисления с произведением — a_kb^k и суммой — <math>\sum_{k=0}^{n-1} a_k b^k</math>, которые при b=3 превращаются в обычную (3,3)-ичную (троичную) систему счисления. При записи первый индекс часто опускается, иногда, когда есть упоминание в тексте, опускается и второй индекс.

Весовой коэффициент разряда — b^k — приписной и, в общем случае, может быть необязательно показательной функцией от номера разряда — k, и необязательно степенью числа 3. Множество значений a_k более ограниченно и более связано с аппаратной частью — числом устойчивых состояний триггеров или числом состояний группы триггеров в одном разряде регистра. В общем случае, a_k могут быть тоже необязательно из троичного множества a={0,1,2}, но, чтобы спаренной системе быть троичной и называться троичной, как минимум, одна из двух систем должна быть троичной. a_k-е ближе к аппаратной части и по a_k-м из множества a={0,1,2} или из множества a={-1,0,+1}, определяется система кодирования: несимметричная троичная или симметричная троичная.

Показательные троичные системы счисления

Целое число <math>x</math> в показательной позиционной троичной системе записывают в виде последовательности его цифр (строки цифр), перечисляемых слева направо по убыванию старшинства разрядов:

<math>x_{a,b} = (a_{n-1} a_{n-2} \dots a_0)_{a,b}.</math>

В показательных системах счисления значениям разрядов приписываются весовые коэффициенты <math>b^k</math>, в записи они опускаются, но подразумевается, что k-й разряд справа налево имеет весовой коэффициент равный <math>b^k</math>.

Из комбинаторики известно, что количество записываемых кодов равно числу размещений с повторениями:

<math>\bar{A}(a,n) = \bar{A}_a^n = a^n = 3^n,</math>

где a = 3 — 3-элементное множество a = {0, 1, 2}, из которого берутся цифры a_k, n — число элементов (цифр) в числе x_3,b.

Количество записываемых кодов не зависит от основания показательной функции — b, которое определяет диапазон представляемых числами x_3,b величин.

Дробное число записывается и представляется в виде

<math>x_{a,b} = (a_{n-1} a_{n-2}\dots a_{1} a_{0},a_{-1} a_{-2}\dots a_{-(m-1)} a_{-m})_{a,b} =\sum_{k=-m}^{n-1} a_k b^k,</math>

где m — число разрядов дробной части числа справа от запятой;

• при m = 0 дробная часть отсутствует, число — целое,
• при a_k из троичного множества a = {0, 1, 2} и b = 1 образуется непозиционная троичная система счисления с одинаковыми весовыми коэффициентами всех разрядов равными 1^k = 1,
• при a_k из двоичного множества a = {0, 1} и b = 3 в сумме будут только целые степени — 3^k,
• при a_k из троичного множества a = {0, 1, 2} и b = 3 в сумме будут целые и удвоенные степени 3, система счисления становится обычной несимметричной троичной системой счисления, a_k удовлетворяют неравенству <math>0 \leqslant a_k \leqslant (b - 1) < b</math>, то есть <math>0 \leqslant a_k \leqslant 2 < 3</math>,
• при a_k из десятичного множества a = {0, 1, ..., 9} и b = 3 в сумме будут целые степени 3 умноженные на 1, 2, ..., 9.

В некоторых случаях этого может оказаться недостаточно, в таких случаях можно применить стро́енные (комтринированные), счетверённые и другие системы счисления.

Троичные системы счисления с дополнительным сомножителем

В показательных позиционных троичных системах счисления в вес разряда можно ввести дополнительный сомножитель. Например, сомножитель (b/с):

<math>x_{a,b,c} = (a_{n-1} a_{n-2}\dots a_{1}a_{0},a_{-1}a_{-2}\dots a_{-(m-1)}a_{-m})_{a,b,c} = \sum_{k=-m}^{n-1} a_k b^k (b/c)</math>

В общем случае c≠3.
При a_k из 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, «однопроводное»):
Число трёхуровневых систем кодирования троичных цифр равно числу перестановок:

<math>P_3=A_3^3=\frac {3!}{(3-3)!}=\frac {3!}{0!}=3!= 6,</math> из них одна

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-х возможных:
Число возможных 2B BCT систем кодирования троичных цифр равно числу сочетаний без повторения:

<math>{n\choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!} = {4\choose 3} = \frac{4!}{3!\left(4-3\right)!} = 4,</math> умноженному на число перестановок в каждом наборе из 3-х цифр:

<math>P_3=A_3^3=\frac {3!}{(3-3)!}=\frac {3!}{0!}=3!= 6,</math> то есть 4*6 = 24.

Вот некоторые из них:
2.1.
(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.
Вот одна из них:
(0,0) — «0»
(1,1) — «0»
(0,1) — «-1»
(1,0) — «+1»
4. Трёхбитные двоичнокодированые троичные цифры (3-Bit BinaryCodedTernary, 3B BCT representation, «трёхпроводное») с использованием 3-х кодов из 8-ми возможных:
Число возможных 3B BCT систем кодирования троичных цифр равно числу сочетаний без повторения:

<math>{n\choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!} = {8\choose 3} = \frac{8!}{3!\left(8-3\right)!} = 54,</math> умноженному на число перестановок в каждом наборе из 3-х цифр:

<math>P_3=A_3^3=\frac {3!}{(3-3)!}=\frac {3!}{0!}=3!= 6,</math> то есть 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.
и др.

Сравнение с двоичной системой счисления

При поразрядном сравнении троичная система счисления оказывается более ёмкой, чем двоичная система счисления.
При девяти разрядах двоичный код имеет ёмкость <math>2^9=512</math> чисел, а троичный код имеет ёмкость <math>3^9=19 683</math> числа, то есть в <math>3^9/2^9=38,4</math> раза больше.
При двадцати семи разрядах двоичный код имеет ёмкость <math>2^{27}=134 217 728</math> чисел, а троичный код имеет ёмкость <math>3^{27}=7 625 597 484 987</math> чисел, то есть в <math>3^{27}/2^{27}=56 815,13</math> раз больше.

Свойства

Троичная позиционная показательная несимметричная система счисления по затратам числа знаков (в трёхразрядном десятичном числе 3*10=30 знаков) наиболее экономична из позиционных показательных несимметричных систем счисления. А. Кушнеров приписывает эту теорему Джону фон Нейману.

Перевод целых чисел из десятичной системы счисления в троичную

Для перевода целое десятичное число делят нацело с остатком (целочисленное деление) на 3 до тех пор, пока частное больше нуля. Остатки, записанные слева направо от последнего к первому являются целым несимметричным троичным эквивалентом целого десятичного числа.
Пример: десятичное целое число 48_10,10 переведём в несимметричное троичное целое число:
число = 48_10,10 делим на 3, частное = 16, остаток a₀ = 0
частное = 16_10,10 делим на 3, частное = 5, остаток a₁ = 1
частное = 5_10,10 делим на 3, частное = 1, остаток a₂ = 2
частное = 1_10,10 делим на 3, частное = 0, остаток a₃ = 1
Частное не больше нуля, деление закончено.
Теперь, записав все остатки от последнего к первому слева направо, получим результат 48_10,10 = (a₃a₂a₁a₀)_3,3 = 1210_3,3.

Симметричная троичная система счисления

Позиционная целочисленная симметричная троичная система счисления была предложена итальянским математиком Фибоначчи (Леонардо Пизанский) (1170—1250) для решения «задачи о гирях». Задачу о наилучшей системе гирь рассматривал Лука Пачоли (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 золотник. Этой задачей занимался петербургский академик Леонард Эйлер, а позже интересовался Д. И. Менделеев.

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

Симметричная система позволяет изображать отрицательные числа, не используя отдельный знак минуса. Число 2 изображается цифрой 1 в разряде троек и цифрой <math>\bar 1</math> (минус единица) в разряде единиц. Число −2 изображается цифрой <math>\bar 1</math> (минус единица) в разряде троек и цифрой 1 в разряде единиц.
Возможны шесть соответствий цифр (знаков) троичной симметричной системы счисления и цифр (знаков) троичной несимметричной системы счисления:

	1.	2.	3.	4.	5.	6.
1	2	1	0	0	2	1
0	1	0	2	1	0	2
Шаблон:Overline	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

В троичной симметричной системе счисления знак Шаблон:Overline можно заменить знаком (не числом) i или 2 и, во втором случае, использовать для троичной симметричной системы счисления {-1,0,+1} знаки троичной несимметричной системы {2,0,1}.

Свойства

Благодаря тому что основание 3 нечётно, в троичной системе возможно симметричное относительно нуля расположение цифр: −1, 0, 1, с которым связано шесть ценных свойств:

• Естественность представления отрицательных чисел;
• Отсутствие проблемы округления: обнуление ненужных младших разрядов округляет — приближает число к ближайшему «грубому».
• Таблица умножения в этой системе, как отметил О. Л. Коши, примерно в четыре раза короче.(стр.34).
• Для изменения знака представляемого числа нужно изменить ненулевые цифры на симметричные.
• При суммировании большого количества чисел значение для переноса в следующий разряд растёт с увеличением количества слагаемых не линейно, а пропорционально квадратному корню числа слагаемых.
• По затратам количества знаков на представление чисел она равна троичной несимметричной системе.

Представление отрицательных чисел

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

<math>10\bar1 = 9-1 = 8</math>

<math>\bar101 =-9+1 =-8</math>

Округление

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

Перевод чисел из десятичной системы в троичную

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

Перевод в другие системы счисления

Всякое число, записанное в троичной системе счисления с цифрами 0, 1, −1, можно представить в виде суммы целых степеней числа 3, причём если в данном разряде троичного изображения числа стоит цифра 1, то соответствующая этому разряду степень числа 3 входит в сумму со знаком «+», если же цифра −1, то со знаком «-», а если цифра 0, то вовсе не входит. Это можно представить формулой

<math> \cdots + K_3\cdot3^3 + K_2\cdot3^2+ K_1\cdot3^1+ K_0\cdot3^0+ K_{-1}\cdot3^{-1}+ K_{-2}\cdot3^{-2}+ K_{-3}\cdot3^{-3} + \cdots</math>, где

<math> \cdots + K_3\cdot3^3 + K_2\cdot3^2+ K_1\cdot3^1+ K_0\cdot3^0</math> — целая часть числа,

<math> \cdots + K_{-1}\cdot3^{-1}+ K_{-2}\cdot3^{-2}+ K_{-3}\cdot3^{-3} + \cdots</math> — дробная часть числа,

причём коэффициенты K могут принимать значения { 1, 0, −1 }.

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

Практические применения

• Работая в палате мер и весов, Д. И. Менделеев, с учётом симметричной троичной системы счисления, разработал цифровой ряд значений весов разновеса для взвешивания на лабораторных весах, который используется по сей день.
• Следствием из задачи Фибоначчи о гирях является то, что применение троичности в номиналах денежных систем (3 коп., 15 коп., 3 руб.) упрощает набор и суммы и сдачи и уменьшает количество денежных знаков в обороте (количество монет и вес монет для монет или количество листов и вес листов для банкнот).
• Симметричная троичная система использовалась в советской ЭВМ Сетунь.

Таблицы сложения в троичных системах счисления

В троичной несимметричной системе счисления

2	02	10	11
1	01	02	10
0	00	01	02
+	0	1	2

В троичной симметричной системе счисления

1	00	01	1Шаблон:Overline
0	0Шаблон:Overline	00	01
Шаблон:Overline	Шаблон:Overline1	0Шаблон:Overline	00
+	Шаблон:Overline	0	1

Девятеричная форма представления команд

Представление команд троичным кодом при программировании и при вводе в машину неудобно и неэкономно, поэтому вне машины применяется девятеричная форма представления команд. Девятеричные цифры <math>\bar4, \bar3, \bar2, \bar1, 0, 1, 2, 3, 4</math> сопоставляются парам троичных цифр:

<math>\bar1\bar1 = \bar4;\quad\bar10 = \bar3;\quad\bar11 = \bar2;\quad0\bar1 = \bar1;\quad00 = 0;</math>

<math>11 = 4;\quad10 = 3;\quad1\bar1 = 2;\quad01 = 1.</math>

При выводе из машины отрицательные девятеричные цифры обозначают буквами:

Девятеричная цифра	<math>\bar1</math>	<math>\bar2</math>	<math>\bar3</math>	<math>\bar4</math>
Буква латинского алфавита	Z	Y	X	W
Буква русского алфавита	Ц	У	Х	Ж

См. также

• Троичный код
• Троичная логика
• Сетунь (компьютер)
• Троичный триггер
• Троичный компьютер
• Троичный разряд
• Трайт
• Единицы количества информации
• Троичное кодирование

Литература

• Брусенцов Н. П., С. П. Маслов, В. П. Розин, А. М. Тишулина «Малая цифровая вычислительная машина Сетунь», Издательство Московского университета, 1965.
• Шаблон:Книга