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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Двійкова
система
Шістнадцяткова
система
Десяткова
система
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.

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

Зміст

Трійкова цифри[ред.ред. код]

У несиметричній трійковій системі числення частіше застосовуються цифри {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.

Фізичні реалізації[ред.ред. код]

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

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

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

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

Десяткове число 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, ваги розрядів рівні 3k.

Показникові системи числення[ред.ред. код]

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

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

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

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

Кожен добутокв такого запису називається (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 дробова частина відсутня, число - ціле,
при ak з трійкової множини a = {0,1,2} і b = 1 утворюється непозиційна трійков система числення з однаковими ваговими коефіцієнтами всіх розрядів рівними 1k = 1,
при ak з двійкової множини a = {0,1} і b = 3 в сумі будуть тільки цілі степені - 3k ,
при ak з трійкової множини a = {0,1,2} і b = 3 в сумі будуть цілі і подвоєні степені 3, система числення стає звичайною несиметричною трійковою системою числення, a k задовольняють нерівності  0\leqslant a_k\leqslant (b-1) <b , тобто  0\leqslant a_k\leqslant2 <3 ,
при ak з десяткової множини 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-х можливих[1]:
Число можливих 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. [2]
(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.
Ось одна з них [3]:
(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 знаків) найбільш економічна з позиційних показникових несиметричних систем числення.[4][5][6][7][8] А. Кушнеров[5] приписує цю теорему Джону фон Нейману.

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

Для перекладу ціле десяткове число ділять (цілочисельне ділення) на 3 доти, поки частка більше нуля. Остачі, записані зліва направо від останнього до першого є цілим несиметричним потрійним еквівалентом цілого десяткового числа. [9]
Приклад: десяткове ціле число 4810,10 переведемо в несиметричне трійкове ціле число:
число = 48 10,10 ділимо на 3, частка = 16, остача a0 = 0
частка = 16 10,10 ділимо на 3, частка = 5, остача a1 = 1
частка = 5 10,10 ділимо на 3, частка = 1, остача a2 = 2
частка = 1 10,10 ділимо на 3, частка = 0, остача a3 = 1
Частка не більше нуля, ділення закінчено.
Тепер, записавши всі остачі від останнього до першого зліва направо, отримаємо результат 4810,10 = (a3 a2 a1 a 0 ) 3,3 = 12103,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) для вирішення «завдання про гирі». [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 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, з яким пов'язано шість цінних властивостей:

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

Представлення від'ємних чисел[ред.ред. код]

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

10\bar1 = 9-1 = 8
\bar101 =-9+1 =-8

Округлення[ред.ред. код]

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

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

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

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

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

Див. також[ред.ред. код]

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

Примітки[ред.ред. код]

  1. http://314159.ru/kushnerov/kushnerov1.pdf Троичная цифровая техника. Ретроспектива и современность
  2. simon/teaching/CS1Q-students/systems/tutorials/tut3sol.pdf BCT: Binary Coded Ternary
  3. Тринари. Форум. Аппаратная часть. Сумматор. Блок 003
  4. С. В. Фомин]] {{{Заголовок}}}. (альтернативная ссылка)
  5. а б А. Кушнеров Троичная цифровая техника. Ретроспектива и современность.
  6. Экономичность систем счисления
  7. Удивительное свойство троичной системы счисления
  8. О. А. Акулов, Н. В. Медведев. Информатика и вычислительная техника. 4-е изд. — М.: Омега-Л, 2007. (Раздел I, Гл.3.3)
  9. Http://algolist.manual.ru/maths/teornum/count_sys.php Переклад з системи з більшою підставою - в систему з меншим
  10. «Троичный принцип» Николая Брусенцова.
  11. а б С. Б. Гашков {{{Заголовок}}}. В Google Chrome после нажатия на PDF(333Kb) нужно стронуть одну из боковых сторон рамки браузера.
  12. И. Я. Депман. История арифметики. Пособие для учителей. Издание второе, исправленное. Издательство «Просвещение», Москва, 1965. Глава I. Натуральное число. 7. Задача Баше — Менделеева, стр.36.
  13. Е. С. Давыдов, Наименьшие группы чисел для образования натуральных рядов, Спб., 1903, 36 стр.
  14. В. Ф. Гартц, Лучшая система для весовых гирь, Спб., 1910, 36 стр.
  15. Ф. А. Слудский, О свойствах степеней двух и трёх. «Математический сборник», ч. III, стр. 214.
  16. Юрий Ревич «Наследники Бэббиджа» // «Домашний компьютер», № 12, 1 декабря 2002 года.
  17. И. Я. Депман. «Меры и метрическая система», Учпедгиз, 1955.
  18. И. Я. Депман. «Возникновение системы мер и способов измерения величин», вып. 1, Учпедгиз, 1956.