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

Двійкова система	Шістнадцяткова система	Десяткова система
00000	00	00
00001	01	01
00010	02	02
00011	03	03
00100	04	04
00101	05	05
00110	06	06
00111	07	07
01000	08	08
01001	09	09
01010	0A	10
01011	0B	11
01100	0C	12
01101	0D	13
01110	0E	14
01111	0F	15
10000	10	16
10001	11	17
10010	12	18
10011	13	19
10100	14	20
10101	15	21
10110	16	22
10111	17	23
11000	18	24
11001	19	25
11010	1A	26
11011	1B	27
11100	1C	28
11101	1D	29
11110	1E	30
11111	1F	31

Трійкова система числення — позиційна система числення з цілочисленною основою, рівною 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\leqslant2 <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. <иr/>При інших значеннях a, b і c утворюються інші показові позиційні системи числення з додатковим співмножником (b/c), число яких нескінченне.
Можливі нескінченні множини та інших складових систем числення.

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

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

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

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

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

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 систем кодування трійкових цифр дорівнює числу сполук без повторення:

${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.

Ось деякі з них:
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 систем кодування трійкових цифр дорівнює числу сполук без повторення:

${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.

Ось деякі з них:
3.1.
(1,0,0) - 2;
(0,1,0) - 1;
(0,0,1) - 0.
3.2.
(0,1,1) - 2;
(1,0,1) - 1;
(1,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.
та інш.

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

При порозрядному порівнянні трійкова система числення виявляється більш ємною, ніж двійкова система числення.
При дев'яти розрядах двійковий код має ємність $2^9 = 512$ чисел, а трійчковий код має ємність $3^9 = 19683$ числа, тобто в $3^9/2^9 = 38,4$ рази більше.
При двадцяти семи розрядах двійковий код має ємність $2^{27} = 134217728$ чисел, а трійковий код має ємність $3^{27} = 7 625 597 484 987$ чисел , тобто в $3^{27}/2^{27} = 56 815,13$ разів більше.
При вісімдесяти одному розряді двійковий код має ємність $2^{81} = 2 417 851 693 229 258 349 412 352$ числа, а трійковий код має ємність $3^{81} = 4,434 e +38$ чисел, тобто в $3^{81}/2^{81} = 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\bar1 = 9-1 = 8$

$\bar101 =-9+1 =-8$

Округлення

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

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

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

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

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

$\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$ , де

$\cdots + K_3\cdot3 ^ 3 + K_2\cdot3 ^ 2 + K_1\cdot3 ^ 1 + K_0\cdot3 ^ 0$ - ціла частина числа ,

$\cdots + K_ { -1 }\cdot3 ^ { -1 } + K_ { -2 }\cdot3 ^ { -2 } + K_ { -3 }\cdot3 ^ { -3 } +\cdots$ - дробова частина числа ,

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

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

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

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

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

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

$\bar1\bar1 =\bar4 ;\quad\bar10 =\bar3 ;\quad\bar11 =\bar2 ;\quad0\bar1 =\bar1 ;\quad00 = 0 ;$

$11 = 4 ;\quad10 = 3 ;\quad1\bar1 = 2 ;\quad01 = 1 .$

При виведенні з машини від’ємні дев’яткові цифри позначають буквами:

Дев’яткова цифра	$\bar1$	$\bar2$	$\bar3$	$\bar4$  | -	Літера латининиці	Z	Y	X	W
Літера кирилиці	Ц	У	Х	Ж

Див. також

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