ПОНЯТТЯ ПРО СИСТЕМИ ЧИСЛЕННЯ

ЛАБОРАТОРНЕ ЗАНЯТТЯ №1

з курсу «Комп’ютерна схемотехніка»

Тема. Основи побудови комп’ютерних схем.
Мета. Ознайомитися з основними елементами систем числення, навчитися переходити від однієї системи числення до іншої, закріпити навички побудови таблиць істиності, ДДНФ та ДКНФ і їх перетворень, елементарних схем.

Теоретичні відомості
ПОНЯТТЯ ПРО СИСТЕМИ ЧИСЛЕННЯ
Система числення (або нумерація) – сукупність правил запису чисел за допомогою скінченої кількості знаків, а також правил виконання операцій над ними.
Людська практика виробила різні способи запису чисел. Однією з найстаріших систем нумерації була єгипетська ієрогліфічна нумерація (близько 5000 років тому).
За способом кодування системи числення поділяються на позиційні та непозиційні. Першою позиційною системою є шісдесяткова система давніх шумер (19-16 ст. до н.е.). За допомогою цієї системи можна було пронумерувати секунди у хвилинах, а хвилини у годинах. Крім поділу часу на години, шумери запропонували поділ кутів на градуси, мінути і секунди.
Прикладом непозиційної системи числення є римська система, в якій роль цифр відіграють літери латинського алфавіту:
І - одиниця С – сто L – п’ятдесят М – тисяча
V – п’ять Х - десять D – п’ятсот Наприклад, 324 = СССХХІV
В римській системі відсутнє поняття «0». Непозиційна система числення є незручною та складною для виконання арифметичних операцій та запису чисел.
В позиційній системі числення значення кожної цифри залежить від місця у послідовності цифр в записі числа.

Загальноприйнятою в сучасному світі є десяткова (decimal) позиційна система числення, яка з Індії через арабські країни прийшла в Європу. Цифри десяткової системи нумерації: 0, 1, 2, ..., 9. Основою цієї системи є число десять.
Основою системи числення називається число, що позначає, у скільки разів одиниця наступного розряду є більшою за попередню.
Запис числа є скороченою формою запису розкладу за степенями основи системи числення, наприклад:
123456=1*105+2*104+3*103+4*102+5*101+6*100
Тут, 10 є основою системи числення, а показник степеня – це номер позиції цифри в записі числа (нумерація ведеться зправа наліво, починаючи з нуля).
1 2 3 4 5 6
5 4 3 2 1 0
Позиційний принцип запису чисел ґрунтується на наступній теоремі.
Теорема. Будь-яке додатне дійсне число Х можна подати у вигляді розкладу:
X=anrn+ an-1rn-1+...+ a1r1+ a0r0+ a-1r-1+ a-2r-2+..., (1)
.
Якщо для позначення чисел множини В вибрати r різних знаків і коефіцієнти розкладу (1) записати в порядку спадання степенів r, відокремивши коефіцієнти у від’ємних степенях r комою, отримаємо запис числа Х в r-тій системі числення.
аnan-1...a1a0,a-1a-2... (2)
де ai – знак поставлений у відповідність числу ai з множини В.
В послідовності (2) позиції, на яких стоять коефіцієнти, нумеруються вліво від коми числами 0, 1, 2, ..., n, вправо – числами -1, -2, ... . Знак з приписаним йому значенням називається цифрою.
В послідовності (2) кожна цифра має певне значення, яке визначається за таким правилом: цифра, що стоїть в нульовому розряді, має своїм значенням число з множини В, яке цій цифрі поставлено у відповідність. Значення цифри, яка стоїть в розряді k буде в r раз більшим від того значення, яке б ця цифра мала в розряді k-1.
Основу системи числення вказують нижнім індексом.
Приклад.
11001,01(2)=25,75(10)
Як основу системи числення теоретично можна використати будь яке число, але на практиці використовують лише кілька – це двійкова, вісімкова, шістнадцяткова і десяткова.

ДВІЙКОВА СИСТЕМА ЧИСЛЕННЯ
Для подання чисел у пам’яті комп’ютера використовують двійкову систему числення (binary).
Для позначення чисел у цій системі існує лише дві цифри: «0» та «1», тобто два стійкі стани фізичних елементів (немає сигналу – «0», є сигнал – «1»; вимкнуто – «0», увімкнуто – «1» тощо).
Така система є легкою для моделювання і елементарною для виконання арифметичних операцій.
Наприклад, операції додавання й множення у двійковій системі числення:
+ 0 1
0 0 1
1 1 10
Додавання * 0 1
0 0 0
1 0 1
Множення

При додаванні 1+1 відбувається перенесення одиниці до старшого розряду, як для десяткових чисел.
Приклад.
+ 1 0 0 1 1 0
1 1 0 1 1
1 0 0 0 0 0 1
* 1 0 1 0 0 1
1 1
1 0 1 0 0 1
1 0 1 0 0 1
1 1 1 1 0 1 1

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

ВІСІМКОВА СИСТЕМА ЧИСЛЕННЯ
Двійковий
код Вісімковий
код
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7








Для комп’ютера двійкове представлення є дуже зручним та ефективним, але для програмістів і розробників апаратного чи програмного забезпечення такий запис є вкрай незручним.
Щоб скоротити довжелезні записі у двійковому коді було вирішено заміняти послідовність з трьох двійкових цифр на одну десяткову цифру. Оскільки перебір всіх комбінацій з трьох двійкових цифр надає 8 значень (23=8), тому такий код називають вісімковим (octal) і він використовує лише 8 цифр (від «0» до «7»).

ШІСНАДЦЯТКОВА СИСТЕМА ЧИСЛЕННЯ
Згодом, аналогічно було застосовано групування по чотири двійкових символи і позначення такої групи однією цифрою. Оскільки перебір всіх комбінацій з чотирьох двійкових цифр надає 16 значень (24=16), тому такий код називають шіснадцятковим (hexadecimal) і він використовує 10 десяткових цифр (від «0» до «9») та додаткові цифри, що позначаються першими літерами латинського алфавіту («A», «B», «C», «D», «F», «E»).

Двійковий
код Шіснадцятковий
код
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 A
1011 B
1100 C
1101 D
1110 E
1111 F







ПЕРЕХІД ВІД ОДНІЄЇ СИСТЕМИ ЧИСЛЕННЯ В ІНШУ
Під час налагодження програм та в деяких інших ситуаціях у програмуванні потрібно перетворення чисел з однієї системи числення в іншу. Тому розроблено правила переведення з різних систем числення.
Переведення з 2-ої у 8-у та 16-у системи
Якщо основа нової системи числення дорівнює деякому степеню двійкової системи числення (8=23, 16=24), то алгоритм переводу є дуже простим:
Потрібно згрупувати справа наліво двійкові цифри (від кінця числа) в кількості, що дорівнює показнику степеня і замінити цю групу цифр відповідною цифрою нової системи числення (якщо бракує цифр до групи, то зліва можна доповнити число нулями).
Наприклад:
110012= 0112 0012 =318
↓ ↓
38 18
110012= 00012 10012 =1916
↓ ↓
116 916


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

538= 58 38 =101 0112
↓ ↓
1012 0112
5316= 516 316 =0101 00112
↓ ↓
01012 00112


Переведення з 8-ої у 16-у та з 16-ої у 8-у
Тут застосовується проміжний етап переведення числа зі старої системи у двійкову систему числення, а потім з двійкової у нову систему числення.
418= 48 18 =1000012= 00102 00012 =2116
↓ ↓ ↓ ↓
1002 0012 216 116

А816= А16 816 =101010002= 0102 1012 0002 =2508
↓ ↓ ↓ ↓ ↓
10102 10002 28 58 08

Як бачимо, якщо основа однієї системи числення дорівнює дея¬кому степеню іншої, то алгоритми переведення є легкими. Переведення є дещо складніше, коли потрібно переводити у десяткову систему числення чи навпаки з десяткової.

Переведення з 2-ої, 8-ої чи 16-ої системи у 10-у
Щоб знайти десятковий запис числа за заданим r-им записом потрібно записати розклад (1) з теореми і в ньому основу r і коефіцієнти аі записати у десятковій системі та виконати обчислення.
Приклад:
З шістнадцяткової в десяткову:
92С816 = 9*163+2*162+12*161+8*160 = 36864+512+192+8 =3757610
З вісімкової в десяткову:
7358 = 7*82+3*81+5*80 =448+24+5= 47710
З двійкової в десяткову:
1100,1012 = 1*23+1*22+0*21+0*20+1*2-1+0*2-2+1*2-3 =12,62510
Переведення з 10-ої системи у 2-у, 8-у чи 16-у
Для переведення цілої частини:
Послідовно десяткове число ділити на основу нової системи числення, виділяючи остачі. Остачі записують у зворотному порядку і це буде числом в новій системі числення;
Для переведення дробової частини:
Послідовно дробову частину числа множити на основу нової системи числення, виділяючи цілі частини, які й будуть утворювати запис дробової частини числа в новій системі числення.
Наприклад:
Для цілої частини: Для дробової частини:
0,25
2
0 50
1 0


ОСОБЛИВОСТІ КОДУВАННЯ ВІД’ЄМНИХ ЦІЛИХ ЧИСЕЛ
Тепер розглянемо, як у комп’ютері подано знакові цілі числа. Проблема зі знаком вирішується досить просто, оскільки знак має чітко визначену позицію в числі – він передує самому числу. А тому було вирішено виділити для його збереження крайній лівий біт байта і домовитися, що якщо цей розряд містить значення «0», число є додатним, якщо ж «1» – від’ємним. Всі інші біти байта відводяться під саме число. Наприклад, якщо двійкова послідовність є десятковим числом «5», то послідовність є числом « 5» в межах одного байта.
Цілі числа в оперативній пам’яті подаються в додатковому коді. Додатковий код додатного цілого числа співпадає з двійковим записом числа, доповненим спереду нулями до k розрядів, де k – довжина коду. Додатковий код від’ємного цілого числа шукається так: відкидається знак «-», двійковий запис числа доповнюється нулями до k розрядів, кожен нуль замінюється на одиницю, а одиниця нулем і до останнього розряду додається одиниця.
Наприклад, візьмемо десяткове число -10(10)=-1010(2)=00001010(2). Кожен нуль замінимо на одиницю, а одиницю нулем – 11110101, а потім додамо 1: . Це і буде додатковий код числа .
БУЛЕВА АЛГЕБРА
Аналіз комбінаційних пристроїв і цифрових логічних схем найпростіше проводи¬ти з допомогою булевої математики, яка оперує тільки двома поняттями: істина (логічна 1) і неістина (логічний 0). В результаті функції, які відображають інформа¬цію приймають в кожний момент часу тільки значення 0 і 1. Таблиця, в якій кожному набору вхідних сигналів ставиться у відповідність вихідний сигнал, називається таб¬лицею істинності.
Змінні, розглянуті в алгебрі логіки, можуть приймати тільки два значення – 0 або 1. В алгебрі логіки визначені: відношення еквівалентності (позначається знаком =) і операції: додавання (дизюнкція), яка позначається знаком (+), множення (кон¬юнкція), яка позначається знаком & або крапкою, і заперечення (або інверсії), яка позначається рискою зверху або апострофом.
Алгебра логіки визначається схемою аксіом, а саме:




Запис логічних виразів, зазвичай, здійснюють у конюнктивній або дизюнктивній нормальних формах. У дизюнктивній формі логічні вирази записуються як логічна сума логічних добутків, у конюнктивній формі – як логічний добуток логіч¬них сум. Порядок дій такий же, як і у звичайних алгебраїчних виразів. Логічні вирази зв’язують значення логічної функції зі значеннями логічних змінних.
При перетвореннях логічних виразів використовуються логічні тотожності:



.
Будь-який логічний вираз, складений з n змінних xn, хn-1, ..., х1 за допомогою скінченого числа операцій алгебри логіки, можна розглядати як деяку функцію n змінних. Таку функцію називають логічною. Відповідно до аксіом алгебри логіки, функція може приймати, залежно від значення змінних, значення 0 або 1. Функція n логічних змінних може бути визначена для 2n значень змінних, відповідним всім можливим значенням n-розрядних двійкових чисел.
Якщо булева функція подана таблицею істинності, то вона може бути подана в аналітичній формі за допомогою операцій конюнкції, дизюнкції та інверсії за допомогою наступних правил:
Кожній одиниці в таблиці істинності ставиться у відповідність конюнкція рангу n, де n – кількість аргументів функції. Рангом конюнкції називається число аргументів, які входять в конюнкцію, причому аргумент входить без інверсії, якщо він у відповідному наборі приймає значення 1 та з інверсією, якщо приймає значення 0. Всі отримані конюнкції обєднуються знаками дизюнкції.
Такий аналітичний вираз називають досконалою дизюктивною нормальною формою (ДДНФ). Досконалою, тому що всі конюнкції мають ранг п, нормальною тому що інверсії застосовуються тільки до окремих аргументів.
Якщо в таблиці істинності нулів набагато менше ніж одиниць, то використовують аналітичний запис у вигляді досконалої конюктивної нормальної форми (ДКНФ). Вона будується наступним чином: кожному нулю в таблиці істинності ставиться у відповідність дизюнкція рангу n, де n кількість аргументів функції. Рангом дизюнкції називається число аргументів, які входять в дизюнкцію, при чому аргумент входить без інверсії, якщо він у відповідному наборі приймає значення 0 та з інверсією, якщо приймає значення 1. Всі отримані дизюнкції обєднуються знаками конюнкції.
Під контактом розуміють фізичне тіло, яке може перебувати рівно у двох станах – включено і виключено. Послідовне з’єднання відповідає кон’юнкції, а паралельне кон’юнкції.







Завдання
1. Дано два десяткових числа: 321,25 і 120. Треба перевести їх у двійкову, вісімкову і шістнадцяткову системи числення і виконати додавання. Отриманий результат перевести в десяткову систему і порівняти з правильним.
2. Дано два числа, записаних у двійковій формі: 1011,01 і 111,11. Необхідно:
а) виконати віднімання і результат перевести в десяткову систему числення;
б) перевести дані числа в десяткову систему числення і виконати віднімання;
в) порівняти результати отримані на кроках а) і б).
3. Дано два числа, записаних у десятковій системі числення: -30 і 50. Необхідно подати дані числа у додатковому коді та виконати додавання. Отриманий результат перевести у десяткову систему числення і порівняти з правильним результатом.
4. Побудувати контактну схему, робота якої описується формулою. Спростити формулу і побудувати спрощену схему. Побудувати для заданої формули таблицю істиності, а по ній спроектувати схему за допомогою логічних елементів «І», «АБО», «НЕ».
.
Контрольні запитання
1. Що таке система числення?
2. Які типи систем числення ви знаєте?
3. Що таке основа позиційної системи числення?
4. Яка система числення використовується для подання чисел у пам’яті комп’ютера? Чому?
5. З яких міркувань використовують 8-у та 16-у системи числення?
6. Яким чином можна перевести число з 8-ої системи числення у 16-у?
7. За якими правилами переводяться числа з десяткової системи числення?
8. За якими правилами переводяться числа в десяткову систему числення?