Системи числення

В КОМП’ЮТЕРАХ І КОП’ЮТЕРНИХ СИСТЕМАХ

Розділ 1. СИСТЕМИ ЧИСЛЕННЯ, ЯКІ ВИКОРИСТОВУЮТЬСЯ

Програмування для комп’ютерів і комп’ютерних систем (ККС) та їх конструктивні особливості тісно пов’язані з поняттям системи числення, оскільки ЕОМ оперує з інформацією, яка подається в цифровому вигляді.

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

У будь-якій системі числення число представляють сукупністю символів (розрядів), що називають цифрами. Кожній цифрі в записі числа зіставляється деяка кількість, що виражається цією цифрою і називається кількісним еквівалентом цифри.

Якщо, наприклад, число записано у вигляді послідовності символів

,

де – і -ва цифра заданого числа А, якій однозначно відповідає певний кількісний еквівалент , то кількісний еквівалент числа А є деякою функцією числових еквівалентів всіх його розрядів, тобто

.

Розрізняють непозиційні і позиційні системи числення.

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

I – 1, V – 5, X – 10, L – 50, C – 100, D – 500, M – 1000 і т.д.

Для запису проміжних чисел користуються правилом: кожне менше значення символу, поставлене справа від більшого, додається до більшого, а поставлене зліва від більшого, віднімається від останнього. Значення однакових символів додаються. Наприклад: ІХ – 9, ХІ – ХІІ – 12, ХХХ – 30, MCMXCVIII – 1998, ММVІ – 2006.

Однак непозиційні системи числення майже не знаходять застосування в комп’ютерах і комп’ютерних системах (ККС) у зв’язку з наступними недоліками:

1) відсутність нуля;

2) необхідність утримувати нескінчену кількість символів;

3) складність алгоритмів представлення чисел і виконання арифметичних операцій.

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

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

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

Позиційні системи числення в свою чергу поділяються на однорідн і і неоднорідні.

Однорідні позиційні системи. Переважне поширення в ККС одержали позиційні однорідні системи числення. Однорідність системи числення означає, що у всіх розрядах числа, записаного в такій системі, використовують цифри з тої самої множини. Наприклад, у звичайній десятковій системі числення у всіх розрядах числа використовуються цифри з множини {0,1,...,9}, у двійковій системі – цифри з множини {0,1} і т.д. У позиційній однорідній системі з безпосереднім поданням цифр число А записують у вигляді

. (1.1)

Кількісний еквівалент числа, поданого таким записом, визначається як

. (1.2)

Тут - цифра -го розряду числа А, що приймає значення з множини {0,1,..., р -1}, a р – називається основою системи числення і дорівнює кількості цифр, які використовуються у даній системі числення. Величину прийнято називати вагою -го розряду. В -розрядному числі (1.1), де , ціла частина числа представлена розрядами ліворуч від коми, а дробова частина – т розрядами праворуч від коми. У даному випадку вага -го розряду в p раз більше ваги -1-го розряду . Таку систему числення називають також системою з природним порядком ваг або природною системою, або натуральним кодом. Наприклад, послідовність ваг для десяткової природної системи числення виглядає як , для двійкової природної системи – і т.д. Для систем з природним порядком ваг обов'язковим є сталість відношення ваг сусідніх розрядів і існування розряду з номером нуль, вага якого дорівнює одиниці.

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

Існують також системи числення зі штучним порядком ваг, для яких сталість відношення ваг сусідніх розрядів не є обов'язковим. Відомі, наприклад, системи зі штучним порядком ваг, у яких ціле додатне число А виражається як

,

де може приймати одне зі значень, що належать множині , тобто, . При р=2, j=3 ваги розрядів у такій системі утворюють ряд ,... або 1, 2, 4, 7, 14, 28,.... Такі системи числення знаходять застосування в комп'ютерних засобах, що мають поліпшені технічні характеристики по надійності, власному енергоспоживанню та ін., а також для кодування цифр інших систем числення з високими основами.

Системи з природним порядком ваг розрізняють також за виглядом основи р. Відомі, наприклад, системи з натуральними, від’ємними, дробовими, комплексними основами. Найбільше застосування в ККС одержали системи числення з натуральними основами.

Деякі числа, представлені в однорідних системах числення з різними основами, наведено в табл. 1.1.

Таблиця 1.1

„10”	„2”	„4”	„8”	„16”	„3”	„10”	„2”	„4”	„8”	„16”	„3”
				A						1A
				B						1B
				C						1C
				D						1D
				E						1E
				F						1F

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

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

, (1.3)

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

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

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

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

Наприклад, час 2 роки, 25 діб, 14 годин, 35 хвилин; 48 секунд, виражений в одиницях молодшого розряду, визначається за формулою (1.3) наступним чином:

сек.

В пакеті Mathcad обчислення мають вигляд:

Спеціально для застосування в ЕОМ була розроблена неоднорідна двійково-п’ятіркова система числення, в якій в непарних розрядах основа , а в парних розрядах основа (Крім випадку нульового розряду, коли ). Оскільки добуток двох сусідніх (парного і непарного) розрядів дорівнює 10, то двома двійково-п’ятірковими розрядами можна кодувати одну десяткову цифру (табл. 1.2).

Приклад 1.1. Записати числа 398 і 798 в двійково-п’ятірковій системі числення.

Розв’язання. Користуючись табл. 1.2 запишемо . Тут ; основи системи: , , , , , , ; цифри розрядів: , , , , , . Для обчислення кількісного еквіваленту числа підставимо одержані значення в формулу (1.2)

.

В пакеті Mathcad обчислення мають вигляд:

Аналогічно, для десяткового числа 6798 двійково-п’ятіркове число запишеться . Його складові: ; , , , , , , , ; , , , , , , , . Кількісний еквівалент числа

В пакеті Mathcad обчислення мають вигляд:

Розглянута вище класифікація систем числення показана на рис.1.

Рис. 1.

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

1. Однозначність - кожному числу повинне відповідати єдине його подання в заданій системі і навпаки.

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

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

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

Симетричними називають системи числення з непарними натуральними основами і цифрами . Такі системи дають можливість подати будь-яке ціле число, як додатне, так і від’ємне, у скінченому вигляді. Якщо основа системи є парною, то побудувати симетричну канонічну систему неможливо. Прикладом симетричної канонічної системи є трійкова система з цифрами .

Якщо канонічна система має тільки цифриабо тільки цифри , то вона називається зміщеною системою. У таких системах можна представити в скінченому вигляді або тільки додатні, або тільки від’ємні цілі числа. До зазначених систем відносяться, наприклад, десяткова система з цифрами {0,1,...,9} і двійкова система з цифрами {0,1}.

Приклад 2. Утворити всі можливі числа для системи числення зміщеного типу з основою 2 і штучним порядком ваг 4,1,9,3,2.

Таблиця 1.3

Числа з вагами розрядів 4 1 9 3 2
0 00000 1 01000 2 00001 3 00010 01001 4 10000	5 11000 6 10001 7 10010 8 11010 9 00100 10011	10 01100 11011 11 00101 12 00110 01101 13 10100 14 11100 00111	15 10101 16 11101 17 11110 18 10111 19 11111

Легко встановити, що таких чисел буде 20 – від 0 до 19 (табл. 1.3).

З табл.1.3 випливає, що деякі числа (3,4,5,6,7,9 та ін.) у такій системі можуть бути представлені неоднозначно. Отже, ця система не може бути віднесена до канонічних.

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

З практичної точки зору дуже важливим є питання про діапазон чисел, які можуть бути подані у деякій канонічній системі числення. Для визначення діапазонів подання чисел у різних канонічних системах числення необхідно у формулу (1.1) для знаходження кількісного еквівалента підставити замість цифр їх можливі мінімальні і максимальні значення для різних систем. Тоді одержимо:

а) для зміщених систем з додатними цифрами:

,

;

б) для зміщених систем з від’ємними цифрами:

,

;

в) для симетричних систем з цифрами , де :

,

;

г) для кососиметрична систем з цифрами , де ,

,

.

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

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

Надлишкові системи з натуральною основою р=2r і цифрами або основою р=2r+1 і цифрами називають квазіканонічними. Прикладом таких систем можуть бути десяткова система з цифрами {-5,-4,...,-1,0,1,...,5,6} і трійкова система з цифрами {-2,-1,0,1,2}. Загальна кількість цифр у квазіканонічних системах дорівнює р+2.

Системи з натуральною основою р=2r і цифрами або з основою р=2r+1 і цифрами називають модифікованими квазіканонічними надлишковими системами числення. У таких системах кількість різних цифр дорівнює р+ 1. До модифікованих квазіканонічних систем відносяться трійкова система з цифрами {-1, 0,1,2} і двійкова з цифрами {-1,0,1}.

Неканонічна двійкова система. У ККС при виконанні деяких операцій (наприклад, ділення і добування кореня) знаходить застосування неканонічна двійкова система числення з цифрами {-1,1}. У цій системі вага кожного розряду дорівнює цілому степені числа 2, а діапазон представлення чисел при природному порядку ваг знаходиться між максимальним числом

і мінімальним числом

,

(тут означає –1). Відсутність цифри 0 у цій системі призводить до неможливості представлення тут парних чисел і нуля (точніше - неможливості представлення скінченим числом цифр).

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

де р – основа системи числення, символами якої кодуються числа; Р – основа вихідної системи числення.

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

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

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

Прикладом системи числення з природними ваговими коефіцієнтами розрядів може бути двійково-десяткова система з ваговими коефіцієнтами 8–4–2–1. У ній кожна цифра кодується двійковою тетрадою. Наприклад десяткове число 2796 в цій двійково-десятковій системі набуде вигляду:

0010 0111 1001 0110.

Прикладом системи числення з штучними ваговими коефіцієнтами розрядів може бути двійково-десяткова система з ваговими коефіцієнтами 2–4–2–1. Десяткове число 2796 в цій двійково-десятковій системі набуде наступного вигляду:

0010 1101 1111 1100.

В табл. 1.4 наведено десяткові цифри, подані в деяких двійково-десяткових кодах.

Неважко підмітити, що код 2–4–2–1 є самодоповнюючийся, що дає можливість найбільш раціонально будувати лічильники і різні арифметичні схеми. Код називається самодоповнюючимся, якщо двійкові коди будь-яких двох десяткових чисел, які доповнюють один одного до 9 (тобто якщо їх десяткова сума дорівнює 9 (), доповнюють один одного до (тобто їх сума .

Таблиця 1.4

Десяткова цифра	Код 8421	Код 2421	Код 8421+3	Десяткова цифра	Код 8421	Код 2421	Код 8421+3

Ще одним самодоповнюючимся кодом є “код з надвишком три” – “8421”+3. Він одержується із природного коду 8421 додаванням до нього числа . У результаті такого додавання одержується система з непостійними ваговими коефіцієнтами розрядів. Наприклад, цифра кодується як , тобто у третьому двійковому розряді 1 має вагу одиниця. Тоді, як при кодуванні цифри старша двійкова цифра повинна мати вагу 8, але при кодуванні цифри вона має вагу 5. Відмітимо, що всі наведені коди є системами однорідними, оскільки в кожному двійковому розряді можуть бути дві цифри: 0 або 1.

Слід також відмітити, що двійково-десяткові коди володіють певною надлишковістю, оскільки для кодування десяткових цифр використовуються тільки 10 комбінацій із 16, що можна використовувати для виявлення деяких помилок.

Найбільш широке застосування в обчислювальній техніці одержали двійково-десяткові системи числення, у яких десяткові цифри записуються у вигляді двійкової тетради. Таке представлення десяткових цифр називають також безнадлишковим, оскільки для нього необхідно мінімальна кількість двійкових розрядів. Обмежене застосування знаходять і надлишкові представлення десяткових цифр за допомогою п'яти, шести і семи двійкових розрядів. У принципі, можна побудувати ККС, що працює при будь-якому двійково-десятковому кодуванні. Однак емпіричним шляхом установлено, що для створення десяткових обчислювальних засобів найбільш доцільно використовувати двійково-десяткові коди (ДДК), що володіють властивостями зваженості, упорядкованості, парності, доповнюваності й однозначності (так званими властивостями Рутисхаузера). Зупинимося більш детально на цих властивостях.

Зваженість. ДДК називається зваженим, якщо кожному з h розрядів двійкового подання десяткової цифри А поставлені у відповідність ваги , причому . Властивість зваженості спрощує виконання логічних і арифметичних операцій.

ДДК, які одержуються один із одного простою перестановкою ваг , утворять кодову групу. Для позначення конкретних ДДК і кодових груп часто використовують послідовність їхніх ваг, записаних у порядку їхнього убування, наприклад, “8,4,2,1”, “4,4,2,1” і т.п.

Упорядкованість. ДДК називають упорядкованим, якщо для двійкових подань десяткових цифр: виконується одна з умов:

,

,

Наявність упорядкованості ДДК необхідно для реалізації логічних операцій.

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

Доповнюваність. Сутність властивості доповнюваності ДДК полягає в наступному. Якщо сума двох десяткових цифр дорівнює 9, то перехід від двійкового подання однієї цифри до двійкового подання іншої цифри повинно здійснюватися шляхом інверсії двійкових розрядів (тобто, шляхом заміни нулів одиницями й одиниць нулями). Ця властивість є необхідною для спрощення алгебраїчних операцій (операцій з урахуванням знаків операндів) за правилами десяткової арифметики.

Однозначність. ДДК має властивість однозначності, якщо між десятковою цифрою і комбінацією двійкових цифр установлена взаємно однозначна відповідність. Ця властивість спрощує і полегшує як процедуру представлення в ДДК десяткових чисел (тобто, кодування), так і процедуру розпізнавання десяткових чисел у ДДК (тобто, декодування).

Особливістю зважених ДДК, що має тільки додатні ваги, крім ДДК групи “8,4,2,1”, є відсутність однозначного представлення десяткових цифр. Це означає, що деякі десяткові цифри можуть бути записані декількома комбінаціями двійкових цифр. Наприклад, у ДДК “4,4,2,1” цифру 4 можна представити як 1000 і як 0100, цифру 5 – як 1001 і як 0101, цифру 6-як 1010 і як 0110, цифру 7 – як 1011 і як 0111. Причиною цього є неоднозначність розв’язання рівняння

відносно змінних . Однозначність подання десяткових цифр, яка полягає в тому, що кожній такій цифрі відповідає тільки одна з 16 двійкових тетрад, забезпечується в ДДК групи “8,4,2,1”. Крім того, однозначність представлення десяткових цифр може бути забезпечена в ДДК із від’ємними вагами. У табл.1.5 наведено всі кодові групи однозначних ДДК. На лістингу 1 наведено програму реалізовану в пакеті Mathcad, за допомогою якої легко одержати відповідні коди і перевірити сказане.

Таблиця 1.5

Кодові групи однозначних ДДК
“8,4,2,1”	“8,4,2,-1”	“8,4,-2,1”	“8,-4,2,1”	“8,-4,-2,1”	“8,-4,2,-1”	“8,4,-3,2”
“8,4,3,-2”	“8,-4,3,2”	“8,4,-3,-2”	“8,-4,3,-2”	“8,5,-4,2”	“8,-5,4,2”	“8,5,-4,-2”
“8,6,-4,1”	“8,-6,4,1”	“8,6,-4,-1”	“8,-6,4,3”	“8,7,-4,-2”	“7,6,-5,3”	“7,-6,5,3”
			“-7,6,5,3”

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

Властивістю доповнюваності володіють усі зважені ДДК із позитивними вагами, у яких сума ваг дорівнює 9. Існують чотири кодових групи зважених ДДК, що володіють також і властивостями єдиності і доповнюваності, а саме: "5,2,1,1", "4,3,1,1", "4,2,2,1","3,3,2,1". Три з перерахованих ДДК наведено на Лістингу 2.

Серед зважених ДДК із від’ємними вагами, властивостями єдиності і доповнюваності володіють ДДК 19 кодових груп, перерахованих у табл. 1.6. Упорядкованість властива лише ДДК, що не має від’ємних ваг. Одночасно властивостями єдиності, впорядкованості, доповнюваності і зваженості володіють ДДК кодових груп “5,2,1,1”, “4,3,1,1”, “3,3,2,1”, “4,2,2,1”. Усіма п’ятьма властивостями володіють ДДК кодової групи “4,2,2,1” (табл.1.7), які називають також кодами Эмері.

Таблиця 1.6

Кодові групи ДДК із від’ємними вагами, що володіють властивостями єдиності, доповнюваності і зваженості
“8,4,3,-6”	“8,4,2,-5”	“8,3,2,-4”	“7,5,3,-6”	“7,5,1,-4”	“7,3,1,-2”	“6,5,2,-4”
“6,5,1,-3”	“6,4,2,-3”	“6,4,1,-2”	“6,3,2,-2”	“6,3,1,-1”	“6,2,2,-1”	“5,4,3,-3”
“5,3,2,-1”	“4,4,3,-2”	“4,4,2,-1”	“8,6,-1,-4”	“8,4,-2,-1”

Дата добавления: 2014-01-05