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

Трійкова система числення — позиційна система числення з цілочисленною основою, рівною 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 тритів, аналогічно двоїчному байту.

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

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

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

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

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

• 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-х можливих

Число можливих 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.

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

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

• (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.

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

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

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

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

При вісімдесяти одному розряді двійковий код має ємність 2⁸¹ = 2 417 851 693 229 258 349 412 352 числа, а трійковий код — 3⁸¹ ≈ 4,434·10³⁸ чисел, тобто в 3⁸¹/2⁸¹ = 183 396 897 083 556,95 разів більше.

Властивості

Трійкова позиційна показникова несиметрична система числення за витратами числа знаків (в трирозрядному десятковому числі 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 .

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

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

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

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
+	0	1	2

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

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

+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
+	-1	0	+1

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

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

Симетричність при зважуванні на важільних терезах використовували з найдавніших часів, додаючи гирю на чашку з товаром. Елементи трійкової системи числення були в системі числення стародавніх шумерів, в системах мір, ваг і грошей, в яких були одиниці рівні 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	0	1	2	3	4	5	6	7	8	9
Трійкова несиметрична	−10	−2	−1	0	1	2	10	11	12	20	21	22	100
Трійкова симетрична	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, з яким пов'язано шість цінних властивостей:

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

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

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

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

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

Округлення

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

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

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

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

Будь-яке число , записане в трійковій системі числення з цифрами 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

Див. також

• Позиційні системи числення
• Тризначна логіка