Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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


1. Історія

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


2. Визначення

Позиційна система числення визначається цілим числом b> 1, званим підставою системи числення. Система числення з основою b також називається b-річної (зокрема, двійковій, трійкової, десяткової і т. п.).

Ціле число x в b-річної системі числення представляється у вигляді кінцевої лінійної комбінації степенів числа b: [1]

x = \ sum_ {k = 0} ^ {n-1} a_k b ^ k , Де \ A_k - Це цілі числа, звані цифрами, що задовольняють нерівності 0 \ leq a_k \ le b-1.

Кожна ступінь \ B ^ k в такого запису називається розрядом (позицією), старшинство розрядів і відповідних їм цифр визначається значенням показника ступеня \ K . Зазвичай для ненульового числа \ X вимагають, щоб старша цифра \ A_ {n-1} в b-ричном поданні \ X була також ненульовий.


Якщо не виникає різночитань (наприклад, коли всі цифри видаються як унікальних письмових знаків), число \ X записують у вигляді послідовності його b-ковий цифр, що перераховуються за зменьшенням старшинства розрядів зліва направо: [1]

x = a_ {n-1} a_ {n-2} \ dots a_0.

Побудова такого запису числа називають позиційним кодуванням числа, а сам запис - позиційним кодом числа.

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

103 = 1 \ cdot 10 ^ {2} + 0 \ cdot 10 ^ {1} + 3 \ cdot 10 ^ {0}.

Щоб уникнути плутанини при одночасній роботі з декількома системами числення підставу вказується в якості нижнього індексу:

x = (a_ {n-1} a_ {n-2} \ dots a_0) _b.

За допомогою n позицій в b-річної системі числення можна записати цілі числа від 0 до b n - 1 , Тобто, всього b n різних чисел.


3. Приклади


4. Запис чисел

Для запису чисел в системах числення з основою до 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 і т. д., іноді x = 10.

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

123 10 - Це число 123 в десятковій системі числення;
173 8 - Те ж число в вісімковій системі;
1111011 2 - Те ж число, але в двійковій системі.

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

  • в асемблері і записи спільного роду, не прив'язаних до конкретної мови, буквою h (від h exadecimal) наприкінці числа (синтаксис Intel);
  • в Паскалі знаком "$" на початку числа;
  • в C і багатьох інших мовах комбінацією 0x або 0X (від he x adecimal) на початку.

У деяких діалектах мови Сі за аналогією з "0x" використовується префікс "0b" для позначення двійкових чисел. (Позначення "0b" не входить в стандарт ANSI C.)

У російських рахунках для запису чисел в десятковій показовою позиційній системі числення застосовується унарнодесятічная система запису (подання) десяткових цифр з одного надлишкової унарнодесятічной цифрою "1111111111" = 10 жовтня на кожен розряд.


4.1. Економічність

В цифрову техніку система числення з основою b реалізується регістрами, що складаються з наборів тригерів, кожен з яких може приймати b різних станів, що кодують цифри числа. При цьому особливе значення набуває економічність системи числення - можливість подання якомога більшого діапазону чисел з використанням якомога меншої загальної кількості станів. [1] Якщо загальна кількість станів одно m, то кількість тригерів приблизно дорівнює \ Tfrac {m} {b} , А кількість представимо ними чисел відповідно - b ^ {\ frac {m} {b}} . Як функція від b, цей вислів сягає максимуму при b рівному числу e = 2,718281828 .... При цілих значеннях b максимум досягається для b = 3. Таким чином, найбільш економічної є троичная система числення (використовувана в трійкових ЕОМ), слідом за якою йдуть двійкова система числення (традиційно використовується в більшості поширених ЕОМ) і четверичной система числення.

Економічність системи числення - важлива обставина з точки зору її використання в обчислювальній машині. Тому, хоча застосування в обчислювальній машині трійкової системи замість двійковій тягне деякі конструктивні труднощі (при цьому потрібно користуватися елементами, кожен з яких може перебувати не в двох, а в трьох стійких станах), ця система вже була використана [2] в деяких реально існуючих обчислювальних пристроях. [1]

Еквівалентна опис економічності системи числення можна отримати, використовуючи поняття інформаційної ентропії. За умови равновероятности появи кожної з цифр у записі числа інформаційна ентропія записи n-розрядного числа в системі числення з основою b приймає значення n \ tfrac {\ ln b} {b} (З точністю до постійного коефіцієнта). Тому щільність запису (тобто, кількість інформації на один розряд) чисел в системі числення з основою b дорівнює \ Tfrac {\ ln b} {b} , Яка також приймає максимальне значення при b = e, а для цілих значень b - при b = 3.


5. Властивості

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

  • Основа системи числення в ній самій завжди записується як 10; наприклад, у двійковій системі числення 10 означає число 2. Дане твердження не застосовується до унарний системі числення, в якій використовується тільки одна цифра.
  • Для запису числа x у b-річної системі числення потрібно \ Lfloor \ log_b x \ rfloor + 1 цифр, де \ Lfloor \ cdot \ rfloor означає взяття цілої частини числа.
  • Природний порядок на натуральних числах відповідає лексикографічному порядку на їх уявленнях в позиційній системі числення. Тому порівнювати їх подання можна поразрядно, починаючи зі старшого розряду, до тих пір, поки цифра в одному числі не буде більше відповідної цифри в іншому. Наприклад, для порівняння чисел 321 і 312 у десятковій системі числення потрібно порівнювати цифри в однакових розрядах зліва направо:
    • 3 = 3 - результат порівняння чисел поки не визначено;
    • 2> 1 - перше число більше (незалежно від решти цифр).
  • Арифметичні операції над числами. Позиційна система числення дозволяє без зусиль виконувати додавання, віднімання, множення, ділення й ділення із залишком чисел, знаючи тільки таблицю складання однозначних чисел, а для трьох останніх операцій ще й таблицю множення у відповідній системі. (Див., наприклад, поділ стовпчиком).

6. Перехід до іншого підставі

6.1. Переклад в десяткову систему числення

Якщо число в 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 2 5 + 0 2 4 + 1 2 3 + 1 2 2 + 0 2 1 + 0 2 0 =
= 1 32 + 0 16 + 1 8 + 1 4 + 0 2 + 0 1 =
= 32 + 8 + 4 + 0 = 44 10

6.2. Переклад з десяткової системи числення

Ціла частина
  1. Послідовно ділити цілу частину десяткового числа на основу, поки десяткове число не стане дорівнює нулю.
  2. Отримані при розподілі залишки є цифрами потрібного числа. Число у новій системі записують, починаючи з останнього залишку.
Дрібна частина
  1. Дробову частину десяткового числа множимо на підставу системи, в яку потрібно перевести. Відокремлюємо цілу частину. Продовжуємо множити дробову частину на основу нової системи, поки вона не стане рівною 0.
  2. Число у новій системі складають цілі частини результатів множення в порядку, відповідному їх отримання.
Приклад

44 10 переведемо в двійкову систему:

 44 ділимо на 2. приватне 22, залишок 0 22 ділимо на 2. приватне 11, залишок 0 11 ділимо на 2. приватне 5, залишок 1 Травня ділимо на 2. приватне 2, залишок 1 лютого ділимо на 2. приватне 1, залишок 0 1 ділимо на 2. приватне 0, залишок 1 

Приватне дорівнює нулю, розподіл закінчено. Тепер записавши всі залишки знизу вгору отримаємо число 101100 2


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

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

Для вісімковій - розбиваємо перекладається число на кількість цифр, рівне ступеню 2 (2 зводиться в ту ступінь, яка потрібна, щоб отримати підставу системи, в яку потрібно перевести (2 = 8), в даному випадку 3, тобто тріад). Перетворимо тріади за таблицею тріад:

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

Для шістнадцятковій - розбиваємо перекладається число на кількість цифр, рівне ступеню 2 (2 зводиться в ту ступінь, яка потрібна, щоб отримати підставу системи, в яку потрібно перевести (2 4 = 16), в даному випадку 4, тобто зошити). Перетворимо тетради за таблицею тетрад:

 0000 0 0100 квітень 1000 серпень 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 

Приклад:

 перетворимо 101100 2 вісімкова - 101 100 → 54 8 шістнадцяткова - 0010 1100 → 2C 16 

6.4. Переклад з вісімковій і шістнадцятковій систем в двійкову

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

Для вісімковій - перетворимо за таблицею в триплети

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

Для шістнадцятковій - перетворимо за таблицею в квартети

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

Приклад:

 перетворимо 54 8 → 101100 2C 16 → 0010 1100 

6.5. Переклад з двійкової системи в 8 - і 16-річний

Переклад дробової частини з двійкової системи числення в системи числення з основами 8 і 16 здійснюється точно також, як і для цілих частин числа, за тим лише виключенням, що розбивка на октави і тетради йде вправо від десяткової коми, відсутні розряди доповнюються нулями справа. Наприклад, розглянуте вище число 1100,011 2 буде виглядати як 14,3 8 або C, 6 16.

6.6. Переклад з довільної системи числення в десяткову

Розглянемо приклад перекладу двійкового числа 1100,011 2 в десяткове. Ціла частина цього числа дорівнює 12 (див. вище), а от переклад дробової частини розглянемо детальніше:

0,011 = 0 \ cdot 2 ^ {-1} + 1 \ cdot 2 ^ {-2} + 1 \ cdot 2 ^ {-3} = 0 + 0,25 + 0,125 = 0,375.

Отже, число 1100,011 2 = 12,375 10.

Точно також здійснюється переклад з будь-якої системи числення, тільки замість "2" ставиться основа системи.

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


6.7. Переклад з десяткової системи в довільну

Для переведення дробової частини числа в інші системи числення потрібно звернути цілу частину в нуль і почати множення числа, що вийшло на підставу тієї системи, в яку потрібно перевести. Якщо в результаті множення будуть знову з'являтися цілі частини, їх потрібно повторно звертати в нуль, попередньо запам'ятавши (записавши) значення вийшла цілої частини. Операція закінчується, коли дробова частина повністю звернеться в нуль. Нижче наводиться приклад перекладу числа 103,625 10 в двійкову систему числення.

Переводимо цілу частину за правилами, описаним вище, отримуємо 103 10 = 1100111 2.

 0,625 множимо на 2. Дрібна частина 0,250. Ціла частина 1. 0,250 множимо на 2. Дрібна частина 0,500. Ціла частина 0. 0,500 множимо на 2. Дрібна частина 0,000. Ціла частина 1. 

Отже, зверху вниз отримуємо число 101 2. Тому 103,625 10 = 1100111,101 2

Точно також здійснюється переклад в системи числення з будь-якою основою.

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


7. Варіації і узагальнення

7.1. Запис раціональних чисел

Раціональне число x в b-річної системі числення представляється у вигляді лінійної комбінації (взагалі кажучи, нескінченної) ступенів числа b:

x = (a_ {n-1} a_ {n-2} \ ldots a_1 a_0, c_1 c_2 \ ldots) _b = \ sum_ {k = 0} ^ {n-1} a_k b ^ k + \ sum_ {k = 1} ^ {\ infty} c_k b ^ {-k}

де a k - Цифри цілої частини (до коми), c k - Цифри дробової частини (після коми), n - число розрядів цілої частини.

Кінцевою записом в b-річної системі числення володіють тільки раціональні числа, представимо у вигляді \ Frac {q} {b ^ m} , Де m і q - цілі числа:

\ Frac {q} {b ^ m} = (a_ {n-1} a_ {n-2} \ ldots a_1 a_0, c_1 c_2 \ ldots c_ {-m}) _b = \ sum_ {k = 0} ^ { n-1} a_k b ^ k + \ sum_ {k = 1} ^ {m} c_k b ^ {-k},

де (A_ {n-1} a_ {n-2} \ ldots a_1 a_0) _b і (C_1 c_2 \ ldots c_ {-m}) _b представляють b-ковий записи відповідно приватного та залишку від ділення q на b m .

Раціональні числа, не представимо у вигляді \ Frac {q} {b ^ m} , Записуються у вигляді періодичних дробів.


7.2. Симетричні системи числення

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

Найчастіше використовується симетрична троичная система числення з цифрами (-1,0,1). Вона застосовується в трійкової логіці і була технічно реалізована в обчислювальній машині "Сетунь".


7.3. Негативні підстави

Існують позиційні системи з негативними підставами, звані нега-позиційними :

  • -2 - Нега-двійкова система числення
  • -3 - Нега-троичная система числення
  • -10 - Нега-десяткова система числення

7.4. Нецілочисельне підстави

Іноді також розглядають позиційні системи числення з нецілочисельне підставами: раціональними, ірраціональними, трансцендентними.

Прикладами таких систем числення є:


7.5. Комплексні підстави

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

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

Приклади

Далі будемо записувати позиційну систему числення в наступному вигляді \ Langle \ rho, A \ rangle , Де ρ - Заснування системи числення, а A - безліч цифр. Зокрема, безліч A може мати вигляд:

  • B_R = \ {0, 1, 2, \ dots, R-1 \},
  • D_R = \ {-r_1,-r_1 +1, \ dots, -1,0,1, \ dots, r_2-1, r_2 \}, де \ R_1, \; r_2 \ geq 0 і \ R = r_1 + r_2 +1 . При \ R_1 = 0 безліч \ D_R перетворюється на безліч \ B_R .

Прикладами систем числення з комплексними підставами є (далі j - уявна одиниця):

  • \ Langle \ rho = j \ sqrt {R}, B_R \ rangle. [6]
    • Приклад: \ Langle \ rho = \ pm j \ sqrt {2}, \ {0,1 \} \ rangle;
  • \ Langle \ rho = \ sqrt {2} e ^ {\ pm j \ pi / 2}, B_2 \ rangle. [5]
    • Приклад: \ Langle \ rho =- 1 \ pm j, \ {0,1 \} \ rangle;
  • \ Langle \ rho = 2e ^ {j \ pi / 3}, \ {0,1, e ^ {2j \ pi / 3}, e ^ {-2j \ pi / 3} \} \ rangle; [7]
  • \ Langle \ rho = \ sqrt {R}, B_R \ rangle, де \ Varphi = \ pm \ arccos {(- \ beta / 2 \ sqrt {R})} , \ Beta <\ min \ {R, 2 \ sqrt {R} \} - Ціле позитивне число, яке може приймати кілька значень при даному R; [8]
  • \ Langle \ rho =- R, A_R ^ 2 \ rangle, де безліч A_R ^ 2 складається з комплексних чисел виду r_m = \ alpha_m ^ 1 + j \ alpha_m ^ 2 , А числа \ Alpha_m \ in B_R. Наприклад: \ Langle -2, \ {0,1, j, 1 + j \} \ rangle; [7]
  • \ Langle \ rho = \ rho_2 ^ {}, \ {0,1 \} \ rangle, де \ Rho_2 = \ begin {cases} (-2) ^ {1 / 2} & \ mbox {if} \ m \ \ mbox {even}, \ \ j (-2) ^ {(m-1) / 2m} & \ mbox {if} \ m \ \ mbox {odd}. \ end {cases} . [9]


Двійкові комплексні системи числення

Нижче перераховані підстави двійкових позиційних систем числення та представлення чисел 2, -2 і -1 в них:

  • ρ = 2 : 2 = (10) ρ (Система числення з натуральним підставою);
  • ρ = - 2 : 2 = (110) ρ , - 2 = (10) ρ , - 1 = 11 ρ (Нега-позиційна система числення);
  • ρ = - ρ 2 : 2 = (10 100) ρ , - 2 = (100) ρ , - 1 = 101 ρ (Система числення з комплексним підставою);
  • \ Rho = j \ sqrt {2} : 2 = (10 100) ρ , - 2 = (100) ρ , - 1 = (101) ρ (Система числення з комплексним підставою);
  • ρ = - 1 + j : 2 = (1100) ρ , - 2 = (11100) ρ , - 1 = (11 101) ρ (Система числення з комплексним підставою);
  • \ Rho = \ frac {-1 + j \ sqrt {2}} 2 : 2 = (1010) ρ , - 2 = (110) ρ , - 1 = (111) ρ (Система числення з комплексним підставою).

7.6. Непоказовими системи числення

Показові системи числення є окремим випадком позиційних систем числення з показовою залежністю. Замість показовою залежності можуть бути інші залежності. Наприклад, гіпероператорная позиційна система числення hiper4 (a, b) {\ Operatorname {hyper4} (a, b) = \ operatorname {hyper} (a, 4, b) = a ^ {(4)} b = a \ uparrow \ uparrow b = \ atop {\}} \! \ ! \! \! \! \! \! {{\ underbrace {a ^ {a ^ {\ cdot ^ {\ cdot ^ {a }}}}}} \ atop {b \ mbox {copies of} a}} \! \! \! \! \! \! \! {= a \ to b \ to 2 \ atop {\}} дозволяє записувати великі діапазони чисел тим же числом знаків.


Примітки

  1. 1 2 3 4 С. В. Фомін Системи числення - plm.mccme.ru/ann/a40.htm - М .: Наука, 1987. - 48 с. - ( Популярні лекції з математики). (альтернативна посилання - www.math.ru/lib/files/plm/v40.djvu)
  2. Див Трійчастий комп'ютер.
  3. С. Б. Гашко Системи числення та їх застосування - www.mccme.ru / mmmf-lectures / books / books / books.php # book-29 - 2004. - 52 с. - ( Бібліотека "Математичне освіта"). - ISBN 5-94057-146-8.
  4. А. В. Нікітін Система Бергмана - andrejnikitin.narod.ru/matematika2.htm.
  5. 1 2 Хмільник С. І. Спеціалізована ЦВМ для операцій з комплексними числами - lib.izdatelstwo.com/Papers2/s4.zip / / Питання радіоелектроніки. - 1964. - В. 2. - Т. XII.
  6. 1 2 Knuth DE (1960). "An Imaginary Number System". Communication of the ACM 3 (4): 245-247. DOI : 10.1145/367177.367233 - dx.doi.org/10.1145/367177.367233.
  7. 1 2 Хмільник С. І. Кодування комплексних чисел і векторів - www.lulu.com/content/94846 - Mathematics in Computers. - Ізраїль, 2004. - ISBN 978-0-557-74692-7.
  8. Хмільник С. І. Позиційне кодування комплексних чисел - lib.izdatelstwo.com/Papers2/s5.zip / / Питання радіоелектроніки. - 1966. - В. 9. - Т. XII.
  9. Khmelnik SI Method AND System For Processing Complex Numbers - - Patent USA, US2003154226 (A1). - 2001.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Нега-позиційна система числення
Система числення
Десяткова система числення
Унарна система числення
Фібоначчійовий система числення
Кирилична система числення
Десяткова система числення
Шістнадцяткова система числення
© Усі права захищені
написати до нас
Рейтинг@Mail.ru