РОЗДІЛ ІІ ДОСЛІДЖЕННЯ ЗАСОБІВ ПЕРЕТВОРЕННЯ ЧИСЕЛ З ДОВІЛЬНОЇ ПОЗИЦІЙНОЇ СИСТЕМИ ЧИСЛЕННЯ В ДОВІЛЬНУ (МАШИННІ АЛГОРИТМИ)

Мета циклу лабораторних робіт – практичне використання методів перетворення даних з однієї позиційної системи числення в іншу; закріплення практичних навичок роботи з програмованими обчислювальними засобами індивідуального користування; закріплення теоретичних знань, одержаних при вивченні дисциплін: “Комп’ютерна схемотехніка”, “Основи дискретної математики”, “ЕОМ та мікропроцесорні системи”, “Основи програмування та алгоритмічні мови”, “Системи автоматизованого проектування”, “Мікроконтролери та ОМЕОМ”, “Синтез мікропрограмних автоматів”, тощо.

ОСНОВНІ ТЕОРЕТИЧНІ ПОЛОЖЕННЯ

Системи числення та методи перетворення даних з однієї системи числення в іншу

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

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

Розрізняють позиційні та непозиційні СЧ.

Типовим прикладом непозиційної СЧ є римська СЧ – система з дуже складним способом запису чисел і громіздких правил виконання арифметичних операцій (АО). Тому вона знаходить у наш час досить обмежене застосування.

Як інший приклад непозиційної СЧ можна назвати екзотичну поки систему залишкових класів. У цій системі задається деякий набір модулів у вигляді взаємо-простих цілих чисел p₁, p₂, …, p_k. Саме число A зображується набором залишків по кожному з модулів, тобто , де _i – найменший позитивний залишок від ділення числа A на модуль p_i.

Наприклад, зображення деяких чисел у системі залишкових класів для набору модулів p₁ = 2, p₂ = 3, p₃ = 5 представлено в табл. 1.1.

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

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

Таблиця 1.1 – Приклади зображення деяких десяткових чисел у системі залишкових класів

Десяткове число	Зображення десяткового числа (1, 2, 3)	Десяткове число	Зображення десяткового числа (1, 2, 3)
0	(0, 0, 0)	17	(1, 2, 2)
1	(1, 1, 1)	23	(1, 2, 3)
4	(0, 1, 4)	25	(1, 1, 0)
7	(1, 1, 2)	29	(1, 2, 4)

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

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

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

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

Кількість різноманітних цілих цифр 0, 1, ..., s-1 позиційної СЧ називають її основою s.

В загальному випадку в позиційній СЧ з основою s будь-яке число x може бути подано у вигляді полінома від основи

x_(s) = _r · s^r + _r-1 · s^r-1 +...+ _i · sⁱ +...+ ₁ · s¹ + ₀ · s⁰ + _-1 · s^-1 + _-2 · s^-2 +... .

ціла частина числа дробова частина

Тут коефіцієнти _i  {0,1, ..., s-1}. Це так званий розгорнутий вигляд числа.

На практиці прийнято користуватися еквівалентною, або більш простою скороченою формою представлення числа в вигляді послідовності відповідних цифр x_(s) = _r _r-1..._i...₁₀ , _-1_-2... _(s) .

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

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

В двійковій СЧ розряд носить спеціальну назву – біт. Вісім біт складають другу інформаційну одиницю – байт.

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

Найбільше розповсюдження в цифрових пристроях отримала двійкова СЧ, що використовує тільки дві цифри – 0 і 1.

Запис числа в ній представляється відповідною послідовністю двійкових цифр:

x₍₂₎ = _m _m-1 ... _i ... ₁ ₀ ,_-1 _-2 ... ₍₂₎ ,

де _i  {0, 1}.

Цей запис відповідає сумі ступенів числа 2, узятих із зазначеними в ній коефіцієнтами _i:

x₍₂₎ =_m·10^m + _m-1·10^m-1+...+ _i·10ⁱ +...+ ₁·10¹+ ₀·10⁰ + _-1·10^-1+ _-2·10^-2 +... ₍₂₎= = _m·2^m + _m-1·2^m-1 + ... + _i·2ⁱ + ... + ₁·2¹ + ₀·2⁰ + _-1·2^-1 + _-2·2^-2 + ... ₍₁₀₎ .

Приклад.

1011,101₍₂₎ = 1·10³ + 0·10² + 1·10¹ + 1·10⁰ + 1·10^-1 + 0·10^-2 + 1·10^-3 ₍₂₎ = = 1·2³ + 0·2² + 1·2¹ + 1·2⁰ + 1·2^-1 + 0·2^-2 + 1·2^-3 ₍₁₀₎ = = 8 + 0 + 1 + 1 + 0,5 + 0 + 0,125 ₍₁₀₎ = 11,625₍₁₀₎ .

Вісімкова система числення

У вісімковій системі вживається 8 цифр: 0, 1, ..., 7. Будь-яке число в ній у скороченому вигляді представляється наступною послідовністю цифр:

x₍₈₎ = _q _q-1 ... _i ... ₁ ₀ , _-1 _-2 ... ₍₈₎ ,

у якій _i можуть приймати будь-яке значення від 0 до 7, тобто

_i  {0,1,2,3,4,5,6,7}.

Цьому записові відповідає розгорнута форма у вигляді розкладання числа x по ступенях числа 8 з відповідними коефіцієнтами _i :

x₍₈₎ = _q·10^q + _q-1·10^q-1+...+ _i·10ⁱ +...+ ₁·10¹+ ₀·10⁰ + _-1·10^-1+ _-2·10^-2 +... ₍₈₎ = = _q·8^q + _q-1·8^q-1 +...+ _i·8ⁱ +...+ ₁·8¹ + ₀·8⁰ + _-1·8^-1 + _-2·8^-2 +... ₍₁₀₎ .

Приклад.

207,4₍₈₎ = 2·10² + 0·10¹ + 7·10⁰ + 4·10^-1₍₈₎ = 2·8² + 0·8¹ + 7·8⁰ + 4·8^-1₍₁₀₎ = = 128 + 0 + 7 + 0,5₍₁₀₎ = 135,5₍₁₀₎ .

Шістнадцяткова система числення

У шістнадцятковій СЧ для зображення чисел вживаються 16 цифр (у десятковому еквіваленті – від 0 до 15), при цьому для позначення останніх шістьох цифр використовуються заголовні літери латинського алфавіту, тобто: 0, 1, 2, ..., 9, A, B, C, D, E, F.

Запис довільного числа в 16-ій СЧ зображується у вигляді наступної послідовності цифр

x₍₁₆₎ = _t _t-1 ... _i ... ₁ ₀ , _-1 _-2 ... ₍₁₆₎ ,

де _i може приймати будь-які з 16 значень від 0 до F, тобто

_i  {0, 1, 2, …, 9, A, B, C, D, E, F}.

Цей запис відповідає розкладанню числа x по ступенях основи 16 із зазначеними коефіцієнтами _i :

x₍₁₆₎ = _t·10^t + _t-1·10^t-1 + ... + _i·10ⁱ + ... + ₁·10¹ + ₀·10⁰ + _-1·10^-1 + _-2·10^-2 + ... ₍₁₆₎ = = _t·16^t + _t-1·16^t-1 + ... + _i·16ⁱ + ... + ₁·16¹ + ₀·16⁰ + _-1·16^-1 + _-2·16^-2 + ... ₍₁₀₎ .

Приклад.

A2,8₍₁₆₎ = A·10¹ + 2·10⁰ + 8·10^-1₍₁₆₎ = 10·16¹ + 2·16⁰ + 8·16^-1₍₁₀₎ = = 10·16 + 2 + 0,5₍₁₀₎ = 162,5₍₁₀₎ .

Таблиця відповідності чисел у різних системах числення

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

Звернемо увагу на позиції таблиці, які відзначені гуртками. Аналізуючи їх, можна зробити висновок: основа СЧ, яка записана в цій же системі числення, завжди виглядає однаково – як 10. Таким чином, можна записати 2₍₁₀₎ = 10₍₂₎, 3₍₁₀₎ = 10₍₃₎, 5₍₁₀₎ = 10₍₅₎, 8₍₁₀₎ = 10₍₈₎, 16₍₁₀₎ = 10₍₁₆₎ і так далі.

Використання систем числення в цифрових пристроях

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

Таблиця 1.2 – Таблиця відповідності чисел

10	2	3	5	8	16		10	2	3	5	8	16
0	0	0	0	0	0		17	10001	122	32	21	11
1	1	1	1	1	1		18	10010	200	33	22	12
2	10	2	2	2	2		19	10011	201	34	23	13
3	11	10	3	3	3		½	0,1	0,(1)	0,(2)	0,4	0,8
4	100	11	4	4	4		¼	0,01	0,(02)	0,(1)	0,2	0,4
5	101	12	10	5	5		⅛	0,001	0,(01)	0,(03)	0,1	0,2
6	110	20	11	6	6		1/16	0,0001	0,(0012)	0,(0124)	0,04	0,1
7	111	21	12	7	7		1/32	0,00001	0,(00021121)	0,(00342312)	0,02	0,08
8	1000	22	13	10	8		⅜	0,011	0,(10)	0,(14)	0,3	0,6
9	1001	100	14	11	9		⅝	0,101	0,(12)	0,(30)	0,5	0,A
10	1010	101	20	12	A		⅞	0,111	0,(21)	0,(41)	0,7	0,E
11	1011	102	21	13	B		⅓	0,(01)	0,1	0,(13)	0,(25)	0,(5)
12	1100	110	22	14	C		⅔	0,(10)	0,2	0,(31)	0,(52)	0,(A)
13	1101	111	23	15	D		0,2	0,(0011)	0,(0121)	0,1	0,(1463)	0,(3)
14	1110	112	24	16	E		0,3	0,0(1001)	0,02(2002)	0,1(2)	0,2(3146)	0,4(C)
15	1111	120	30	17	F		3⅛	11,001	10,(01)	3,(03)	3,1	3,2
16	10000	121	31	20	10		4½	100,1	11,(1)	4,(2)	4,4	4,8

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

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

Початкові дані та результати обчислювань для зручності користувачів звичайно подаються в десятковій СЧ.

Із цього випливає необхідність перетворення даних з однієї СЧ в другу. Звичайно такі перетворення виконуються автоматично пристроями комп’ютера. Однак, при програмуванні завдання чи втручанні оператора в процес розв`язування виникає необхідність ручного переведення окремого числа чи невеликої групи даних із однієї СЧ в другу з метою аналізу результатів обробки. Крім того, подання даних в різноманітних СЧ та їх перетворення з однієї СЧ в другу цілком необхідно при розробки (програмуванні) простих мікропроцесорних пристроїв, а також логічному проектуванні мікропрограмних пристроїв (цифрових автоматів) з ”жорсткою” або мікропрограмною логікою управління.