Трійкова система числення

Трійкова система числення — позиційна система числення з цілочисленною основою, рівною 3. За аналогією з a бітом, трійковою цифрою є трит (англ. trinary digit). Один трит містить $\log _{2}3\approx 1.58496$ біт інформації. Трійкова система числення використовується в трійковому комп'ютері.

Існує в двох варіантах: несиметрична і симетрична.

Трійкові цифри

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

Фізичні реалізації

У цифровій електроніці, незалежно від варіанту трійкової системи числення, одному трійковому розряду в трійковій системі числення відповідає один трійковий тригер як мінімум на трьох інверторах з логікою на вході або два двійкових тригера як мінімум на чотирьох інверторах з логікою на вході.

Трайт

Деякі трійкові комп'ютери, такі як «Сетунь», використовують трайт який дорівнює 6 тритів, аналогічно двійковому байту.^[1]

Представлення чисел в трійкових системах числення

Несиметрична трійкова система числення

Прикладом подання чисел у несиметричній трійковій системі числення може служити запис в цій системі цілих додатних чисел:

Десяткове число	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.

Показникові системи числення

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

Внутрішньорозрядна система кодування з основою З, числа якої використовуються для запису цифр.
Приписна міжрозрядна система числення з основою b.

Ціле число в показниковій позиційній системі числення представляється у вигляді суми добутків значень в розрядах (цифр):

K — число від 0 до n-1, номер числового розряду,
N — число розрядів,
З — основа системи кодування, 3 дорівнює розмірностімножини a = {0,1, …, c-1} з якого беруться цифри a_k,
A_k — цілі числа з множини a, назваються цифрами,
B — число, основа міжрозрядної показниковою вагової функції,
B^k — числа міжрозрядної функції, вагові коефіцієнти розрядів.

Кожен добутокв такого запису називається (a, b)-им розрядом.

При c = b утворюються (b, b)-ві системи числення з добутком — a_k b^k і сумою — $\sum _{k=0}^{n-1}a_{k}b^{k}$ , які при 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}, визначається система кодування: несиметрична трійкова або симетрична трійкова.

Показникові трійкові системи числення

Ціле число в показниковій позиційній трійковій системі записують у вигляді послідовності його цифр (рядки цифр), що перераховуються зліва направо по спаданню старшинства розрядів:

X_{a,b}=(a_{n-1}a_{n-2}\dots a_{0})_{a,b}.

У показникових системах числення значенню розрядів приписуються вагові коефіцієнти $b^{k}$ , в записі вони опускаються, але мається на увазі, що k-ий розряд справа наліво має ваговий коефіцієнт рівний $b^{k}$ .

З комбінаторики відомо, що кількість записуваних кодів дорівнює числу розміщень з повтореннями:

${\bar {A}}(a,n)={\bar {A}}_{a}^{n}=a^{n}=3^{n}$ , де A = 3 - 3-х елементна множина a = {0,1,2} з якої беруться цифри a_k, n - число елементів (цифр) в числі x_{3, b}.

Кількість записуваних кодів не залежить від основи показникової функції - b, яке визначає діапазон представляються числами x _{3, b} величин.

Дробове число записується і представляється у вигляді:

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}

, де 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 задовольняють нерівності $0\leqslant a_{k}\leqslant (b-1)<b$ , тобто $0\leqslant a_{k}\leqslant 2<3$ ;
при a_k з десяткової множини a = {0,1,2,3,4,5,6,7,8,9} і b = 3 в сумі будуть цілі степені 3 помножені на 1, 2, 3, 4, 5, 6, 7, 8 і 9.

У деяких випадках цього може виявитися недостатньо, в таких випадках можна застосувати зтроєні (комтринування), зчетверені та інші системи числення.

Трійкова системи числення з додатковим співмножником

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

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)

У загальному випадку 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), число яких нескінченне. Можливі нескінченні множини та інших складових систем числення.

Кодування трійкових цифр

Одна трійкова цифра може кодуватися різними способами.

Трирівневі системи кодування

Трирівневе кодування трійчастих цифр (3-Level Coded Ternary, 3LCT, «однопровідне»)

Число трирівневих систем кодування трійкових цифр дорівнює числу перестановок:

P_{3}=A_{3}^{3}={\frac {3!}{(3-3)!}}={\frac {3!}{0!}}=3!=6,

з них одна

симетрична {-1, 0, +1} (+U - (+1); 0 - (0); -U - (-1)),
зсунута на +1 {0, 1, 2}
зсунута на +2 {1, 2, 3}

Дворівневі системи кодування

Двобітне двійкове кодування

Також називається «двопровідне»^{[джерело?]}, англ. 2-Bit BinaryCodedTernary, 2B BCT representation.

З використанням 3-х кодів з 4-х можливих^[2]

Число можливих 2B BCT систем кодування трійкових цифр дорівнює числу сполук без повторення:

{N \choose k}=C_{n}^{k}={\frac {n!}{K!\left(nk\right)!}}={4 \choose 3}={\frac {4!}{3!\left(4-3\right)!}}=4,

помноженому на число перестановок в кожному наборі з 3-х чисел:

P_{3}=A_{3}^{3}={\frac {3!}{(3-3)!}}={\frac {3!}{0!}}=3!=6,

тобто 4 * 6 = 24.

Ось деякі з них:

Перший варіант: ^[3]

(1,0) - 2;
(0,1) - 1;
(0,0) - 0.

Другий варіант:

(1,1) - 2;
(0,1) - 1;
(0,0) - 0.

З використанням всіх 4-х кодів з 4-х можливих (два з 4-х кодів кодують одну і ту ж саму трійкову цифру)

Ось одна з них^{[джерело?]}:

(0,0) - «0»
(1,1) - «0»
(0,1) - «-1»
(1,0) - «+1»

Трьохбітне двійкове кодування

Також відоме як «трипровідне»^{[джерело?]}, англ. 3-Bit BinaryCodedTernary, 3B BCT representation. Використовуються три коди з 8-ми можливих.

Число можливих 3B BCT систем кодування трійкових цифр дорівнює числу сполук без повторення:

{N \choose k}=C_{n}^{k}={\frac {n!}{K!\left(nk\right)!}}={8 \choose 3}={\frac {8!}{3!\left(8-3\right)!}}=54,

помноженому на число перестановок в кожному наборі з 3-х чисел:

P_{3}=A_{3}^{3}={\frac {3!}{(3-3)!}}={\frac {3!}{0!}}=3!=6,

тобто 54 * 6 = 324.

Ось деякі з них:

Перший варіант:

(1,0,0) - 2;
(0,1,0) - 1;
(0,0,1) - 0.

Другий варіант:

(0,1,1) - 2;
(1,0,1) - 1;
(1,1,0) - 0.

Третій варіант:

(1,1,1) - 2;
(0,1,1) - 1;
(0,0,1) - 0.

Четвертий варіант:

(0,0,0) - 2;
(1,0,0) - 1;
(1,1,0) - 0.

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

При порозрядному порівнянні трійкова система числення виявляється більш ємною, ніж двійкова система числення.

При дев'яти розрядах двійковий код має ємність $29 = 512$ чисел, а трійковий код має ємність $39 = 19683$ числа, тобто в $39 /2 9 = 38,4$ рази більше.

При двадцяти семи розрядах двійковий код має ємність $227 = 134 217 728$ чисел, а трійковий код має ємність $327 = 7 625 597 484 987$ чисел, тобто в $327 /2 27 = 56 815,13$ разів більше.

При вісімдесяти одному розряді двійковий код має ємність $281 = 2 417 851 693 229 258 349 412 352$ числа, а трійковий код — $381 \approx 4,434\cdot10 38$ чисел, тобто в $381 /2 81 = 183 396 897 083 556,95$ разів більше.

Властивості

Трійкова позиційна показникова несиметрична система числення за витратами числа знаків (в трирозрядному десятковому числі 3 * 10 = 30 знаків) найбільш економічна з позиційних показникових несиметричних систем числення.^[4]^[5]^[6]^[7]^[8] А. Кушнеров^[5] приписує цю теорему Джону фон Нейману.

Переклад цілих чисел з десяткової системи числення в трійкову

Для перекладу ціле десяткове число ділять (цілочисельне ділення) на 3 доти, поки частка більше нуля. Остачі, записані зліва направо від останнього до першого є цілим несиметричним потрійним еквівалентом цілого десяткового числа. ^[9]
Приклад: десяткове ціле число 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.

Таблиці додавання в трійкових системах числення

У трійковій несиметричній системі числення

З результатом в десятковій системі числення:

+	0	1	2
2	2	3	4
1	1	2	3
0	0	1	2

З результатом у трійковій несиметричній системі числення:

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

У трійковій симетричній системі числення

З результатом в десятковій системі числення:

+	-1	0	+1
+1	0	+1	+2
0	-1	0	+1
-1	-2	-1	0

З результатом у трійковій симетричній системі числення:

+	-1	0	+1
+1	00	01	1i
0	0i	00	01
-1	I1	0i	00

Трійкова симетрична система числення

Позиційна цілочисленна симетрична трійкова система числення була запропонована італійським математиком Фібоначчі (Леонардо Пізанський) (1170-1250) для вирішення «завдання про гирі». ^[10] Задачу про найкращу систему гир розглядав Лука Пачолі (XV ст.). Окремий випадок цього завдання був опублікований в книзі французького математика Клода Баше де Мезіріака «Збірник цікавих завдань» у 1612 р. Російський переклад книги К. Г. Баше «Ігри та завдання, засновані на математиці» вийшов у Петербурзі в 1877 р. Пізніше цим завданням займався петербурзький академік Леонард Ейлер, цікавився Д.І.Менделєєв.^[11]^[12]^[13]^[14]^[15]

Симетричність при зважуванні на важільних терезах використовували з найдавніших часів, додаючи гирю на чашку з товаром. Елементи трійкової системи числення були в системі числення стародавніх шумерів,^[16] в системах мір, ваг і грошей, в яких були одиниці рівні 3. Але тільки в симетричній трійковій системі числення Фібоначчі об'єднані ці властивості.

Симетрична система дозволяє зображати від’ємні числа, не використовуючи окремий знак мінуса. Число 2 зображується цифрою 1 в розряді трійок і цифрою ${\bar {1}}$ (мінус одиниця) в розряді одиниць. Число -2 зображується цифрою ${\bar {1}}$ (мінус одиниця) в розряді трійок і цифрою 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.

Десяткова система	-3	-2	-1	1	2	3	4	5	6	7	8	9
Трійкова несиметрична	−10	−2	−1	1	2	10	11	12	20	21	22	100
Трійкова симетрична	10	11	1	1	11	10	11	111	110	111	101	100

У трійковій симетричній системі числення знак 1 можна замінити знаком (не числом) i або 2і, в другому випадку, використовувати для трійкової симетричної системи числення {-1,0,+1} знаки трійкової несиметричною системи {2,0,1}.

Властивості

Завдяки тому що основа 3 непарна, у трійковій системі можливо симетричне відносно нуля розташування цифр: -1, 0, 1, з яким пов'язано шість цінних властивостей:

Природність представлення від’ємних чисел;
Відсутність проблеми округлення (для округлення досить просто відкинути непотрібні цифри).
Таблиця множення в цій системі, як зазначив О.Коші, приблизно в чотири рази коротша.^[11] (стр.34).
Для зміни знаку числа потрібно змінювати знаки у всіх його цифр.
При додаванні великої кількості чисел значення для перенесення в наступний розряд зростає із збільшенням кількості доданків не лінійно, а пропорційно квадратному кореню числа доданків.
За витратами числа знаків на представлення чисел вона рівна трійковій несиметричній системі.

Представлення від'ємних чисел

Наявність додатної та від’ємної цифр дозволяє безпосередньо представляти як додатні, так і від’ємні числа. При цьому немає необхідності в спеціальному розряді знака і не треба вводити додатковий ( або зворотний ) код для виконання арифметичних операцій з від’ємними числами. Всі дії над числами, представленими в трійковій системі числення з цифрами 0 , 1 , -1 , виконуються звичайно з урахуванням знаків чисел. Знак числа визначається знаком старшої значущої цифри числа: якщо вона додатна , то і число додатне, якщо від’ємна , то і число від’ємне. Для зміни знака числа треба змінити знаки всіх його цифр (тобто інвертувати його код інверсією Лукасевича ). Наприклад:

10{\bar {1}}=9-1=8

{\bar {1}}01=-9+1=-8

Округлення

Іншим корисним наслідком симетричного розташування значень цифр є відсутність проблеми округлення чисел: в результаті відкидання молодших цифр числа виходить найкраще, при даній кількості залишених цифр, наближення цього числа, і округлення не потрібно.

Переклад чисел з десяткової системи в трійкову

Переклад чисел з десяткової системи в трійкову і відповідне йому питання про гирі, детально викладені в книгах ^[17]^[18]. Там же розказано про застосування трійкової системи гир у російській практиці.

Переклад в інші системи числення

Будь-яке число , записане в трійковій системі числення з цифрами 0 , 1 , -1 , можна представити у вигляді суми цілих степенів числа 3 , причому якщо в даному розряді трійкового зображення числа стоїть цифра 1 , то відповідна цього розряду ступінь числа 3 входить в суму зі знаком «+» , якщо ж цифра -1 , то зі знаком «-» , а якщо цифра 0 , то зовсім не входить. Це можна представити формулою

\cdots +K_{3}\cdot 3^{3}+K_{2}\cdot 3^{2}+K_{1}\cdot 3^{1}+K_{0}\cdot 3^{0}+K_{-1}\cdot 3^{-1}+K_{-2}\cdot 3^{-2}+K_{-3}\cdot 3^{-3}+\cdots

, де

\cdots +K_{3}\cdot 3^{3}+K_{2}\cdot 3^{2}+K_{1}\cdot 3^{1}+K_{0}\cdot 3^{0}

- ціла частина числа ,

\cdots +K_{-1}\cdot 3^{-1}+K_{-2}\cdot 3^{-2}+K_{-3}\cdot 3^{-3}+\cdots

- дробова частина числа ,

причому коефіцієнти K можуть приймати значення { 1 , 0 , -1 } .

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

Практичні застосування

Працюючи в Палаті мір і ваг, Д.І.Менделєєв , з урахуванням симетричної трійкової системи числення, розробив цифровий ряд значень ваг для зважування на лабораторних терезах, який використовується донині .
Симетрична трійкова система використовувалася в радянській ЕОМ Сетунь .

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

Представлення чисел потрійним кодом при програмуванні і при введенні в машину незручно і неекономно, тому поза машини застосовується дев’яткова форма. Дев’яткові числа ${\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4$ зіставляються парам трійкових чисел. При виведенні машиною від’ємні дев’яткові цифри позначають буквами.

Десяткова	$-4$	$-3$	$-2$	$-1$	$0$	$1$	$2$	$3$	$4$
Трійкова	${\bar {1}}{\bar {1}}$	${\bar {1}}0$	${\bar {1}}1$	$0{\bar {1}}$	$00$	$01$	$1{\bar {1}}$	$10$	$11$
Дев’яткова	${\bar {4}}$	${\bar {3}}$	${\bar {2}}$	${\bar {1}}$	$0$	$1$	$2$	$3$	$4$
Латиниця	W	X	Y	Z	0	1	2	3	4
Кирилиця	Ж	Х	У	Ц	0	1	2	3	4

Див. також

Примітки

↑ Бруснєцов, М. П.; Маслов, С. П.; Ramil Alvarez, J.; Zhogolev, E.A. Development of ternary computers at Moscow State University. Архів оригіналу за 5 травня 2010. Процитовано 20 січня 2010.
↑ Троичная цифровая техника. Ретроспектива и современность (PDF). Архів оригіналу (PDF) за 7 жовтня 2013. Процитовано 19 січня 2014.
↑ Simon Gay. BCT: Binary Coded Ternary (PDF) (англ.). Архів (PDF) оригіналу за 21 січня 2022. Процитовано 29 липня 2019.
↑ С. В. Фомин]]. Системы счисления. — М. : Наука, 1987. — 48 с. — (Популярные лекции по математике). (альтернативная ссылка [Архівовано 2 червня 2013 у Wayback Machine.])
↑ ^а ^б А. Кушнеров Троичная цифровая техника. Ретроспектива и современность. [Архівовано 7 жовтня 2013 у Wayback Machine.]
↑ Экономичность систем счисления^{[недоступне посилання з липня 2019]}
↑ Удивительное свойство троичной системы счисления. Архів оригіналу за 11 січня 2012. Процитовано 19 січня 2014. [Архівовано 2012-01-11 у Wayback Machine.]
↑ О. А. Акулов, Н. В. Медведев. Информатика и вычислительная техника. 4-е изд. — М.: Омега-Л, 2007. (Раздел I, Гл.3.3)
↑ Http://algolist.manual.ru/maths/teornum/count_sys.php [Архівовано 31 березня 2022 у Wayback Machine.] Переклад з системи з більшою підставою - в систему з меншим
↑ «Троичный принцип» Николая Брусенцова [Архівовано 11 червня 2008 у Wayback Machine.].
↑ ^а ^б С. Б. Гашков. § 11. Д. И. Менделеев и троичная система // Системы счисления и их применение : [арх. 12 січня 2014]. — М. : МЦНМО, 2004. — (Библиотека «Математическое просвещение»). В Google Chrome после нажатия на PDF(333Kb) нужно стронуть одну из боковых сторон рамки браузера.
↑ И. Я. Депман. История арифметики. Пособие для учителей. Издание второе, исправленное. Издательство «Просвещение», Москва, 1965. Глава I. Натуральное число. 7. Задача Баше — Менделеева, стр.36.
↑ Е. С. Давыдов, Наименьшие группы чисел для образования натуральных рядов, Спб., 1903, 36 стр.
↑ В. Ф. Гартц, Лучшая система для весовых гирь, Спб., 1910, 36 стр.
↑ Ф. А. Слудский, О свойствах степеней двух и трёх. «Математический сборник», ч. III, стр. 214.
↑ Юрий Ревич «Наследники Бэббиджа» // «Домашний компьютер», № 12, 1 декабря 2002 года.
↑ И. Я. Депман. «Меры и метрическая система», Учпедгиз, 1955.
↑ И. Я. Депман. «Возникновение системы мер и способов измерения величин», вып. 1, Учпедгиз, 1956.