Трійкова система числення
Системи числення |
---|
![]() |
Індо-арабська система числення |
Східна Азія |
Алфавітні |
Давні |
Позиційні системи числення за основою |
Не стандартні позиційні системи числення[en] |
Список систем числення[en] |
Трійкова система числення — позиційна система числення з цілочисленною основою, рівною 3. За аналогією з a бітом, трійковою цифрою є трит (англ. trinary digit). Один трит містить біт інформації. Трійкова система числення використовується в трійковому комп'ютері.
Існує в двох варіантах: несиметрична і симетрична.
Зміст
- 1 Трійкова цифри
- 2 Фізичні реалізації
- 3 Представлення чисел в трійкових системах числення
- 4 Таблиці додавання в трійкових системах числення
- 5 Трійкова симетрична система числення
- 6 Дев’яткова форма представлення чисел
- 7 Див. також
- 8 Примітки
Трійкова цифри[ред. | ред. код]
У несиметричній трійковій системі числення частіше застосовуються цифри {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, ваги розрядів рівні 3k.
Показникові системи числення[ред. | ред. код]
У показникових позиційних трійкових системах числення використовуються дві системи:
- Внутрішньорозрядна система кодування з основою З, числа якої використовуються для запису цифр.
- Приписна міжрозрядна система числення з основою 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 і сумою - , які при 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}, визначається система кодування: несиметрична трійкова або симетрична трійкова.
Показникові трійкові системи числення[ред. | ред. код]
Ціле число в показниковій позиційній трійковій системі записують у вигляді послідовності його цифр (рядки цифр), що перераховуються зліва направо по спаданню старшинства розрядів:
У показникових системах числення значенню розрядів приписуються вагові коефіцієнти , в записі вони опускаються, але мається на увазі, що k-ий розряд справа наліво має ваговий коефіцієнт рівний .
З комбінаторики відомо, що кількість записуваних кодів дорівнює числу розміщень з повтореннями:
, де:
A = 3 - 3-х елементна множина a = {0,1,2} з якої беруться цифри a k , n - число елементів (цифр) в числі x 3, b .
Кількість записуваних кодів не залежить від основи показникової функції - b, яке визначає діапазон представляються числами x 3, b величин.
Дробове число записується і представляється у вигляді:
- , де 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 задовольняють нерівності , тобто ,
при 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/с):
У загальному випадку 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, «однопровідне»):
Число трирівневих систем кодування трійкових цифр дорівнює числу перестановок:
- з них одна
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-х можливих[2]:
Число можливих 2B BCT систем кодування трійкових цифр дорівнює числу сполук без повторення:
- помноженому на число перестановок в кожному наборі з 3-х чисел:
- тобто 4 * 6 = 24.
Ось деякі з них:
2.1. [3]
(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.
Ось одна з них [4]:
(0,0) - «0»
(1,1) - «0»
(0,1) - «-1»
(1,0) - «+1»
4. Трбохбітне двійкове кодування трійкових цифр (3-Bit BinaryCodedTernary, 3B BCT representation, «трипровідні») з використанням 3-х кодів з 8-ми можливих:
Число можливих 3B BCT систем кодування трійкових цифр дорівнює числу сполук без повторення:
- помноженому на число перестановок в кожному наборі з 3-х чисел:
- тобто 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.
та інш.
Порівняння з двійковою системою числення[ред. | ред. код]
При порозрядному порівнянні трійкова система числення виявляється більш ємною, ніж двійкова система числення.
При дев'яти розрядах двійковий код має ємність 29 = 512 чисел, а трійковий код має ємність 39 = 19683 числа, тобто в 39/29 = 38,4 рази більше.
При двадцяти семи розрядах двійковий код має ємність 227 = 134 217 728 чисел, а трійковий код має ємність 327 = 7 625 597 484 987 чисел, тобто в 327/227 = 56 815,13 разів більше.
При вісімдесяти одному розряді двійковий код має ємність 281 = 2 417 851 693 229 258 349 412 352 числа, а трійковий код — 381 ≈ 4,434·1038 чисел, тобто в 381/281 = 183 396 897 083 556,95 разів більше.
Властивості[ред. | ред. код]
Трійкова позиційна показникова несиметрична система числення за витратами числа знаків (в трирозрядному десятковому числі 3 * 10 = 30 знаків) найбільш економічна з позиційних показникових несиметричних систем числення.[5][6][7][8][9] А. Кушнеров[6] приписує цю теорему Джону фон Нейману.
Переклад цілих чисел з десяткової системи числення в трійкову[ред. | ред. код]
Для перекладу ціле десяткове число ділять (цілочисельне ділення) на 3 доти, поки частка більше нуля. Остачі, записані зліва направо від останнього до першого є цілим несиметричним потрійним еквівалентом цілого десяткового числа. [10]
Приклад: десяткове ціле число 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) для вирішення «завдання про гирі». [11] Задачу про найкращу систему гир розглядав Лука Пачолі (XV ст.). Окремий випадок цього завдання був опублікований в книзі французького математика Клода Баше де Мезіріака «Збірник цікавих завдань» у 1612 р. Російський переклад книги К. Г. Баше «Ігри та завдання, засновані на математиці» вийшов у Петербурзі в 1877 р. Пізніше цим завданням займався петербурзький академік Леонард Ейлер, цікавився Д.І.Менделєєв.[12][13][14][15][16]
Симетричність при зважуванні на важільних терезах використовували з найдавніших часів, додаючи гирю на чашку з товаром. Елементи трійкової системи числення були в системі числення стародавніх шумерів,[17] в системах мір, ваг і грошей, в яких були одиниці рівні 3. Але тільки в симетричній трійковій системі числення Фібоначчі об'єднані ці властивості.
Симетрична система дозволяє зображати від’ємні числа, не використовуючи окремий знак мінуса. Число 2 зображується цифрою 1 в розряді трійок і цифрою (мінус одиниця) в розряді одиниць. Число -2 зображується цифрою (мінус одиниця) в розряді трійок і цифрою 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, з яким пов'язано шість цінних властивостей:
- Природність представлення від’ємних чисел;
- Відсутність проблеми округлення (для округлення досить просто відкинути непотрібні цифри).
- Таблиця множення в цій системі, як зазначив О.Коші, приблизно в чотири рази коротша.[12] (стр.34).
- Для зміни знаку числа потрібно змінювати знаки у всіх його цифр.
- При додаванні великої кількості чисел значення для перенесення в наступний розряд зростає із збільшенням кількості доданків не лінійно, а пропорційно квадратному кореню числа доданків.
- За витратами числа знаків на представлення чисел вона рівна трійковій несиметричній системі.
Представлення від'ємних чисел[ред. | ред. код]
Наявність додатної та від’ємної цифр дозволяє безпосередньо представляти як додатні, так і від’ємні числа. При цьому немає необхідності в спеціальному розряді знака і не треба вводити додатковий ( або зворотний ) код для виконання арифметичних операцій з від’ємними числами. Всі дії над числами, представленими в трійковій системі числення з цифрами 0 , 1 , -1 , виконуються звичайно з урахуванням знаків чисел. Знак числа визначається знаком старшої значущої цифри числа: якщо вона додатна , то і число додатне, якщо від’ємна , то і число від’ємне. Для зміни знака числа треба змінити знаки всіх його цифр (тобто інвертувати його код інверсією Лукасевича ). Наприклад:
Округлення[ред. | ред. код]
Іншим корисним наслідком симетричного розташування значень цифр є відсутність проблеми округлення чисел: в результаті відкидання молодших цифр числа виходить найкраще, при даній кількості залишених цифр, наближення цього числа, і округлення не потрібно.
Переклад чисел з десяткової системи в трійкову[ред. | ред. код]
Переклад чисел з десяткової системи в трійкову і відповідне йому питання про гирі, детально викладені в книгах [18][19]. Там же розказано про застосування трійкової системи гир у російській практиці.
Переклад в інші системи числення[ред. | ред. код]
Будь-яке число , записане в трійковій системі числення з цифрами 0 , 1 , -1 , можна представити у вигляді суми цілих степенів числа 3 , причому якщо в даному розряді трійкового зображення числа стоїть цифра 1 , то відповідна цього розряду ступінь числа 3 входить в суму зі знаком «+» , якщо ж цифра -1 , то зі знаком «-» , а якщо цифра 0 , то зовсім не входить. Це можна представити формулою
- , де
- - ціла частина числа ,
- - дробова частина числа ,
причому коефіцієнти K можуть приймати значення { 1 , 0 , -1 } .
Для того щоб число , представлене в трійковій системі , перевести в десяткову систему , треба цифру кожного розряду даного числа помножити на відповідну цього розряду степінь числа 3 ( в десятковому поданні) і отримані добутки додати.
Практичні застосування[ред. | ред. код]
- Працюючи в Палаті мір і ваг, Д.І.Менделєєв , з урахуванням симетричної трійкової системи числення, розробив цифровий ряд значень ваг для зважування на лабораторних терезах, який використовується донині .
- Симетрична трійкова система використовувалася в радянській ЕОМ Сетунь .
Дев’яткова форма представлення чисел[ред. | ред. код]
Представлення чисел потрійним кодом при програмуванні і при введенні в машину незручно і неекономно, тому поза машини застосовується дев’яткова форма. Дев’яткові числа зіставляються парам трійкових чисел. При виведенні машиною від’ємні дев’яткові цифри позначають буквами.
Десяткова | |||||||||
---|---|---|---|---|---|---|---|---|---|
Трійкова | |||||||||
Дев’яткова | |||||||||
Латиниця | 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. Процитовано 20 January 2010.
- ↑ http://314159.ru/kushnerov/kushnerov1.pdf Троичная цифровая техника. Ретроспектива и современность
- ↑ simon/teaching/CS1Q-students/systems/tutorials/tut3sol.pdf BCT: Binary Coded Ternary
- ↑ Тринари. Форум. Аппаратная часть. Сумматор. Блок 003
- ↑ С. В. Фомин]]. {{{Заголовок}}}. (альтернативная ссылка)
- ↑ а б А. Кушнеров Троичная цифровая техника. Ретроспектива и современность.
- ↑ Экономичность систем счисления
- ↑ Удивительное свойство троичной системы счисления
- ↑ О. А. Акулов, Н. В. Медведев. Информатика и вычислительная техника. 4-е изд. — М.: Омега-Л, 2007. (Раздел I, Гл.3.3)
- ↑ Http://algolist.manual.ru/maths/teornum/count_sys.php Переклад з системи з більшою підставою - в систему з меншим
- ↑ «Троичный принцип» Николая Брусенцова.
- ↑ а б С. Б. Гашков. {{{Заголовок}}}. В Google Chrome после нажатия на PDF(333Kb) нужно стронуть одну из боковых сторон рамки браузера.
- ↑ И. Я. Депман. История арифметики. Пособие для учителей. Издание второе, исправленное. Издательство «Просвещение», Москва, 1965. Глава I. Натуральное число. 7. Задача Баше — Менделеева, стр.36.
- ↑ Е. С. Давыдов, Наименьшие группы чисел для образования натуральных рядов, Спб., 1903, 36 стр.
- ↑ В. Ф. Гартц, Лучшая система для весовых гирь, Спб., 1910, 36 стр.
- ↑ Ф. А. Слудский, О свойствах степеней двух и трёх. «Математический сборник», ч. III, стр. 214.
- ↑ Юрий Ревич «Наследники Бэббиджа» // «Домашний компьютер», № 12, 1 декабря 2002 года.
- ↑ И. Я. Депман. «Меры и метрическая система», Учпедгиз, 1955.
- ↑ И. Я. Депман. «Возникновение системы мер и способов измерения величин», вып. 1, Учпедгиз, 1956.