Трійкова система числення
Системи числення |
---|
Індо-арабська система числення |
Східна Азія |
Алфавітні |
Давні |
Позиційні системи числення за основою |
Не стандартні позиційні системи числення[en] |
Список систем числення[en] |
Трійкова система числення — позиційна система числення з цілочисленною основою, рівною 3. За аналогією з a бітом, трійковою цифрою є трит (англ. trinary digit). Один трит містить біт інформації. Трійкова система числення використовується в трійковому комп'ютері.
Існує в двох варіантах: несиметрична і симетрична.
У несиметричній трійковій системі числення частіше застосовуються цифри {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.
При інших значеннях a, b і c утворюються інші показові позиційні системи числення з додатковим співмножником (b/c), число яких нескінченне. Можливі нескінченні множини та інших складових систем числення.
Одна трійкова цифра може кодуватися різними способами.
Число трирівневих систем кодування трійкових цифр дорівнює числу перестановок:
- з них одна
- симетрична {-1, 0, +1} (+U - (+1); 0 - (0); -U - (-1)),
- зсунута на +1 {0, 1, 2}
- зсунута на +2 {1, 2, 3}
Також називається «двопровідне»[джерело?], англ. 2-Bit BinaryCodedTernary, 2B BCT representation.
Число можливих 2B BCT систем кодування трійкових цифр дорівнює числу сполук без повторення:
- помноженому на число перестановок в кожному наборі з 3-х чисел:
- тобто 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 систем кодування трійкових цифр дорівнює числу сполук без повторення:
помноженому на число перестановок в кожному наборі з 3-х чисел:
- тобто 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/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 знаків) найбільш економічна з позиційних показникових несиметричних систем числення.[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 в розряді трійок і цифрою (мінус одиниця) в розряді одиниць. Число -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, з яким пов'язано шість цінних властивостей:
- Природність представлення від’ємних чисел;
- Відсутність проблеми округлення (для округлення досить просто відкинути непотрібні цифри).
- Таблиця множення в цій системі, як зазначив О.Коші, приблизно в чотири рази коротша.[11] (стр.34).
- Для зміни знаку числа потрібно змінювати знаки у всіх його цифр.
- При додаванні великої кількості чисел значення для перенесення в наступний розряд зростає із збільшенням кількості доданків не лінійно, а пропорційно квадратному кореню числа доданків.
- За витратами числа знаків на представлення чисел вона рівна трійковій несиметричній системі.
Наявність додатної та від’ємної цифр дозволяє безпосередньо представляти як додатні, так і від’ємні числа. При цьому немає необхідності в спеціальному розряді знака і не треба вводити додатковий ( або зворотний ) код для виконання арифметичних операцій з від’ємними числами. Всі дії над числами, представленими в трійковій системі числення з цифрами 0 , 1 , -1 , виконуються звичайно з урахуванням знаків чисел. Знак числа визначається знаком старшої значущої цифри числа: якщо вона додатна , то і число додатне, якщо від’ємна , то і число від’ємне. Для зміни знака числа треба змінити знаки всіх його цифр (тобто інвертувати його код інверсією Лукасевича ). Наприклад:
Іншим корисним наслідком симетричного розташування значень цифр є відсутність проблеми округлення чисел: в результаті відкидання молодших цифр числа виходить найкраще, при даній кількості залишених цифр, наближення цього числа, і округлення не потрібно.
Переклад чисел з десяткової системи в трійкову і відповідне йому питання про гирі, детально викладені в книгах [17][18]. Там же розказано про застосування трійкової системи гир у російській практиці.
Будь-яке число , записане в трійковій системі числення з цифрами 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. Архів оригіналу за 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.
- ↑ О. А. Акулов, Н. В. Медведев. Информатика и вычислительная техника. 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.