Позиційні системи числення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

До числа таких систем належить сучасна Десяткова система числення (з основою b = 10), виникнення якої пов'язують із лічбою на пальцях. У середньовічній Європі вона з'явилася через італійських купців, які у свою чергу запозичили її у мусульман.

Класифікація позиційних систем числення[ред.ред. код]

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

Системи числення з рівною довжиною чисел належать до класу рівномірних кодів. Однакову довжину числа мають лише тоді, коли підмножини, які отримують в системах числення на кожному кроці розбиття вихідної множини, містять однакове число елементів.

Такі системи числення назвемо однорідними. Їх також ще називають природними, або степеневими. Як уже зазначалось, характерною ознакою таких систем є однаковість їх чисел за довжиною. Крім цього, другою не менш важливою особливістю цих систем є те, що вага розрядів в них змінюється згідно зі степеневим законом. До цих систем числення належать двійкова, десяткова, п'ятерична і безліч подібних інших. За їх основи беруть числа 2, 10, 5 і т. д.

Розроблення більш складних, ніж однорідні, позиційних систем числення почалося в основному в другій половині 20-го століття після того, як з'явилася цифрова обчислювальна техніка. Такі системи назвемо неоднорідними. Вони використовувались здебільшого при побудові спеціалізованих обчислювачів, систем зв'язку та керування, кодуючих та декодуючих пристроїв з метою підвищення їх ефективності.

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

Ваги цифр, які належать до одного розряду числа, у цьому випадку рівні між собою, однак вони на відміну від однорідних систем числення змінюються від розряду до розряду не за степеневим законом, як це має місце для однорідних систем числення, а за більш складним. Числа для неоднорідних систем числення з такими обмеженнями мають, як і для однорідних, рівну довжину. Прикладом таких систем числення є факторіальні, а в більш загальному випадку системи зі змішаною основою, чи поліадичні. На рис. 1.1 у вигляді блок-схеми наведена класифікація позиційних систем числення.

стандартно

рис. 1.1


Таким чином, позиційні системи числення розподіляються на два великих класи — однорідні (з рівною довжиною чисел і основою в вигляді натурального числа) і неоднорідні (з рівною та нерівною довжиною чисел і більш складною основою, ніж натуральні числа). Однорідні системи числення відповідно до числа, яке взяте за їх основу, у свою чергу, поділяються на двійкові, трійкові, десяткові й т.д. Неоднорідні поділяються на системи зі змішаною основою, або поліадичні, і структурні — з числовою або функціональною основою. Останні, у свою чергу, поділяться на комбінаторні і табличні.

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

Визначення[ред.ред. код]

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

x = \sum_{k=0}^n a_k b^k, де a_k і k — цілі, 0 \leq |a_k| < |b|

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

Симетричні позиційні системи числення[ред.ред. код]

Такі системи числення відрізняються тим, що використовують цифри не із множини натуральних чисел (0, \ldots, b-1), а із множини цілих чисел (-\frac{b-1}{2}, -\frac{b-3}{2}, \ldots, \frac{b-1}{2}). Щоб цифри були цілими, потрібно, щоб b було непарним. У симетричних системах числення не вимагається додаткових позначень для знака числа. Крім цього, обчислення у симетричних системах зручні тим, що немає особливих правил округлення, яке зводиться до простого відкидання зайвих розрядів, що різко зменшує систематичні помилки обчислень.

Найчастіше використовується симетрична трійкова система числення із цифрами \{-1, 0, 1\} або \{\bar{1},0,1\}. Вона застосовується у трійковій логіці і була технічно реалізована в обчислювальній машині «Сетунь».

Приклади[ред.ред. код]

Наприклад, число «тисяча п'ятсот вісімдесят сім» представляється у десятковій системі числення у вигляді:

 1587 = 1 \cdot 10^{3} + 5 \cdot 10^{2} + 8 \cdot 10^{1} + 7.

А число «одна друга»:

 0,5 = 0 \cdot 10^{0} + 5 \cdot 10^{-1}.

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

У системі із основою (-10) число «одинадцять» буде виглядати так:

 191 = 1 \cdot (-10)^{2} + 9 \cdot (-10)^{1} + 1 \cdot (-10)^{0} = 100 - 90 + 1.

Числа «один» і «два» у симетричній системі \{\bar{1},0,1\} з базою  \phi=(1+\sqrt{5})/2 виглядають так:

 10,\bar{1} = 1 \cdot \phi^{1} + \bar{1} \cdot \phi^{-1} \approx 1,618 - 0,618.
 100,\bar{1} = 1 \cdot \phi^{2} + \bar{1} \cdot \phi^{-1} \approx 2,618 - 0,618.


Також поширені системи числення з основами:

Запис[ред.ред. код]

Для запису чисел системи числення з основою до 36 включно у якості цифр використовуються арабскі цифри (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) а потім букви латинського алфавіту (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z). При цьому, a = 10, b = 11 і т.д.

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

453_{10} — це число 453 у десятковій системі числення;
111000101_2 — те ж число, але у двійковій системі;
705_8 — те ж число, але у вісімковій системі.

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

  • у мові асемблера і записах загального роду, не прив'язаних до конкретної мови, буквою h (від hexadecimal) у кінці числа (синтаксис Intel) — 75h (453_{10});
  • у Паскалі знаком «$» на початку числа;
  • у Ci і багатьох інших мовах комбінацією 0x або 0X (від hexadecimal) на початку.

Властивості[ред.ред. код]

Позиційна система числення має такі властивості:

  1. Основа системи числення у ній самій завжди записується як 10. Наприклад, у двійковій системі 10_2 означає число 2_{10}.
  2. Для запису числа x у системі числення з основою b потрібно [log_b(x)] + 1 цифр, де [\cdot]ціла частина числа.
  3. Порівняння чисел. Порівняємо два числа 516 і 561. Для цього зліва направо порівнюємо цифри, які стоять на однакових позиціях: 5 = 5 — результат порівняння не визначений; 1 < 6 — перше число менше незалежно від цифр, що залишились.
  4. Додавання чисел. Додамо 516 і 221. Для цього справа наліво додаємо цифри, що стоять на однакових позиціях:
    • 6 + 1 = 7
    • 1 + 2 = 3
    • 5 + 2 = 7
    • загалом — 737.

Таким самим чином можна додавати числа довільної довжини.

Перехід до іншої основи[ред.ред. код]

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

Якщо число у системі числення з основою b дорівнює

a_1\;a_2\;a_3 \ldots a_n,

то для переведення його до десяткової системи обчислюють наступну суму:

\sum_{i=1}^n a_i\cdot b^{n-i}

або, більш наглядно:

a_1\cdot b^{n-1} + a_2 \cdot b^{n-2} + \ldots + a_{n-1} \cdot b^1 + a_n \cdot b^0,

або, нарешті, у вигляді схеми Горнера:

((\ldots(a_1 \cdot b + a_2) \cdot b + a_3) \ldots ) \cdot b + a_n.

Приклад[ред.ред. код]

101100_2=
= 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 0 · 1 =
= 1 · 32 + 0 · 16 + 1 · 8 + 1 · 4 + 0 · 2 + 0 · 1 =
= 32 + 8 + 4 + 0 = 4410

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

Для переведення потрібно ділити число із залишком на основу системи числення допоки частка не стане меншою за основу.

Приклад[ред.ред. код]

44_{10} переведемо до двійкової системи
44 ділимо на 2; частка 22, залишок 0
22 ділимо на 2; частка 11, залишок 0
11 ділимо на 2; частка  5, залишок 1
 5 ділимо на 2; частка  2, залишок 1
 2 ділимо на 2; частка  1, залишок 0

Частка менша двох, ділення закінчено. Тепер записуємо останню частку від ділення і усі залишки, починаючи з останнього, зліва направо, отримаємо число 101100_2.

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

Для цього типу операцій існує спрощений алгоритм.

Для вісімкової — розбиваємо числа на триплети, перетворюючи триплети згідно з таблицею

000 0  100 4
001 1  101 5
010 2  110 6
011 3  111 7

Для шістнадцяткової — розбиваємо на квартети, перетворюючи згідно з таблицею

0000 0  0100 4  1000 8  1100 C 
0001 1  0101 5  1001 9  1101 D
0010 2  0110 6  1010 A  1110 E
0011 3  0111 7  1011 B  1111 F

Приклад 1[ред.ред. код]

Перетворимо 1011002

у вісімкову — 101 100 → 548
у шістнадцяткову — 0010 1100 → 2C16

Приклад 2[ред.ред. код]

Перетворимо до двійкової системи

768 → 111 110
3E16 → 0011 1110

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