24

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ЛЬВІВСЬКИЙ ДЕРЖАВНИЙ ІНСТИТУТ НОВІТНІХ ТЕХНОЛОГІЙ ТА УПРАВЛІННЯ ІМ. В. ЧОРНОВОЛА

Арифметико-логічні основи

цифрової схемотехніки

Методичні вказівки

до практичних занять № 1 з дисципліни

“Комп’ютерна схемотехніка ”

Затверджено

на засіданні кафедри КСМ

Протокол № 1 від 29.08. 2008 р.

ЛЬВІВ 2008

Арифметико-логічні основи цифрової схемотехніки. Методичні вказів­ки до практичних занять № 1 з дисципліни "Комп’ютерна схемотехніка”.

Упорядники: Сергій Сергійович Івчук, ст. Викладач каф. Ксм

Арифметико-логічні основи цифрової схемотехніки

• системи числення;

• форми подання чисел;

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

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

П р и к л а д: Найбільш відома десяткова система числення, в якій для запису використовуються цифри 0, 1, 2, …, 9. Звідки число записується: 2, 4, 59, 555.

Подання запису чисел цифровими знаками існує велика кількість. Дові­льна система числення, яка призначена для практичного використання повинна забезпечувати:

• можливість подання довільного числа в діапазоні величин що розгля­даються;

• єдине подання (довільній комбінації символів повинна відповідати одна і тільки одна величина);

• високу швидкодію в процесі обробки цифрової інформації.

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

Самий простий спосіб запису числа в непозиційній системі числення мо­жемо записати наступним спо­со­бом

А_D = D₁ + D₂ + … + D_k = , (1)

де А_D – запис числа А в системі числення D; D_і – символ системи, який створює базу D = {D₁, D₂, …, D_k}.

П р и к л а д: Достатньо широко використовується римська система числення, де використовується сім символів (цифр) – I - 1, V - 5, X - 10, L - 50, C- 100, D - 500, M - 1000. Тому числа в даній системі записуються: II – 2, IV – 4, LIX – 59, DLV – 555.

В загальному випадку систему числення можливо сформувати за насту­пним принципом:

A_B = a₁B₁ + a₂B₂ + … + a_nB_n, (2)

де A_B – запис числа А в системі числення з основою B_і; a_n – цифра (літера) сис­теми числення з основою B_і; B_і – база або основа системи.

Якщо прийняти, що B_і = q^і, то з врахуванням попереднього запису в за­гальному випадку довільну позиційну систему числення з основою q можемо подана у вигляді полінома

А_(q) = а_nqⁿ + а_n-1q^n-1 + … + а₁q¹ + а₀q⁰ + а_-1q^-1 - а_-mq^-m, (3)

де А_(q) – число в позиційній системі числення з основою q; а – коефіцієнт; n – степінь та індекс.

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

Інакше говорячи – позиційна система числення повинна задовольняти умові рівності B_і = q^і B_і-1. Натуральна позиційна система числення має місце, коли q – ціле, додатне число. Звідки:

А_(q) = а_nqⁿ + а_n-1q^n-1 + … + а₁q¹ + а₀q⁰ + а_-1q^-1 - а_-mq^-m = (4)

де А_(q) – довільне число в позиційній системі числення з основою q; n +1, m – кількість цілих та дробових розрядів.

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

Позиційні системи числення можуть бути різними залежно від основи: десяткові – за основою десять; вісімкові – за основою вісім; шістнадцяткові – за основою шістнадцять; двійкові – за основою два, та інші.

П р и к л а д: Наприклад, запис числа в шістнадцятковій системі може виконуватися за допомогою наступних знаків (цифр та літер): 0, 1, …, 9, A, B, C, D, E, F (літери A, …, F можемо замінити довільними символами ).

На практиці використовують скорочене подання числа у вигляді послі­довності цифр (символів):

• для змішаного числа

A_q = ±a_na_n-1…a₁a₀a_-1…a_-m; (5)

• для цілого числа

A_q = ±a_na_n-1…a₁a₀; (6)

• для правильного дробу

A_q = ±0,a_-1…a_-m. (7)

П р и к л а д: Наведемо приклад подання чисел за допомогою відповід­ного полінома:

• двійкова система числення q = 2, а_і   0, 1:

А₂ = 1011,101 = 12³ + 02² + 12¹ + 12⁰ + 12^-1 + 02^-2 + 12^-3 = 11 = 11,625₁₀;

• вісімкова система q = 8, а_і   0, 1, 2, …, 7:

А₈ = 154,25605 = 18² + 58¹ + 48⁰ + 28^-1 + 58^-2 + 68^-3 + 08^-4 + 58^-5 = 108,34₁₀;

• десяткова система q = 10, а_і   0, 1, 2, …, 9:

А₁₀ = 163,46 = 110² + 610¹ + 310⁰ + 410^-1 + 610^-2;

• шіснадцяткова система q = 16, а_і   0, 1, 2, …, 9, А, В, …, F:

А₁₆ = 6C₁₆ = 616¹ + C16⁰ = 108₁₀.

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

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

П р и к л а д: 96₁₀ = 140₈ = 10120₃ = 1100000₂. В даному випадку одне і теж число, подане в різних базисах, має різну довжину розрядної сітки.

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

В сучасних комп’ютерних системах використовують, крім розглянутих вище, ряд спеціальних позиційних двійкових систем:

• систему з використанням символів 0, -1 або 1, -1; для зручності символ -1 позначають ; таку систему називають системою числення (1, );

• системи числення з від’ємною основою q < -1 і символами 0, 1, … (q - 1); систему з основою q = -2 і символами 0, 1 називають мінус-двійковою;

• надлишкову систему з основою q і кількістю символів більше q, нап­риклад при q = 2 використовують символи (1, 0, ), таку систему числення на­зивають симетричною знакорозрядною.

1.4. Правильний вибір системи числення – важливе практичне питання, ос­кільки від правильного його рішення залежить технічні характеристики ЕОМ і програмного забезпечення, як швидкодія, об’єм пам’яті, складність алгоритм­мів. Тому при виборі системи числення необхідно враховувати наступне:

• основа системи числення визначає кількість стійких станів, які пови­нен мати функціональний елемент, що використовується для відображення роз­рядів числа;

• довжина числа суттєво залежить від основи системи числення;

• система числення повинна забезпечити прості алгоритми виконання арифметичних та логічних операцій.

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

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

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

(8)

В загальному випадку задачу переводу числа з однієї системи числення з основою q₁ в систему числення з основою q₂ можемо визначити як визначення коефіцієнтів b_j нового ряду, що відображає число з основою q₂. Основна склад­ність постає у виборі максимальної степені, яка ще міститься в числі А_q1. Всі дії повинні виконуватися за правилами q₁-арифметики, тобто за правилами вихід­ної системи числення.

Після знаходження максимальної степені основи перевіряють "вход­же­ння" в задане число всіх степенем нової основи, менших максимального. Кожне з відмічених степеней може "входити" в ряд не більше q₂ – 1 раз, оскільки для довільного коефіцієнта ряду накладається обмеження:

0  а_і  q₁ – 1 0  b_j  q₂ – 1 (9)

П р и к л а д: Перевести число А = 96₁₀ в систему числення з основою три (q₂ = 3).

96 = 03⁵ + 13⁴ + 03³ + 13² +23¹ + 03⁰ = 10120₃ звідки А₃ = 10120

Для реалізації автоматизованих алгоритмів переходу від однієї системи до іншої застосовують наступні методи.

Переведення цілих чисел відбувається діленням числа на основу q₂ нової системи числення. Ціле число А_q1 в системі з основою q₂ записується у вигляді

А_q2 = (10)

Переписавши даний вираз за схемою Горнера, отримаємо

А_q2 = (…((b_kq₂ + b_k-1)q₂ +…+ b₁)q₀ + b₀. (11)

Права частина виразу (11) ділиться на величину основи q₂. В результаті визначаємо перший залишок b₀ та цілу частину (…((b_kq₂ + b_k-1)q₂ +…+ b₁). Роз­діливши цілу частину на q₂, знайдемо наступний залишок b₁. Повторюючи про­цес ділення k + 1 раз, отримуємо останнє ціле часткове b_k, яке, за умовою, мен­ше основи системи q₂ і є старшою цифрою числа, поданого в системі числення з основою q₂.

П р и к л а д: Перевести десяткове число А=98 в двійкову систему числення (q₂=2).

98	2
98	49	2					А2 = 1100010
b0 = 0	48	24	2
	b1 =1	24	12	2
		b2 = 0	12	6	2
			b3 = 0	6	3	2
				b4 = 0	2	1 = b6
					b5 = 1

П р и к л а д: Перевести двійкове число А₂ = 11001001 в десяткову систему числення (q₂= 10). Основа q₂ подається у двійковій системі числення q₂ = 10 = 1010₂

11001001	1010
-
1010	1010		1010		A10 = b2b1b0 = 105
	-
001100	1010		b2 = 1
-
1010	b1 = 0000
b1=0101

Переведення правильного дробу множенням на основу q₂ нової системи числення проходить наступним чином. Нехай вихідне число, записане в старій системі числення з основою q₁, має вигляд

А_q1 = (12)

Тоді в новій системі з основою q₂ число буде зображено як 0, b_-1...b_-S або

А_q2 = (13)

Переписавши даний вираз за схемою Горнера, отримаємо

А_q2 = . (14)

Якщо праву частину виразу (14) перемножимо на q₂, тоді отримаємо но­вий неправильний дріб, в цілій частині буде число b_-1. Якщо перемножимо дріб, що залишився на величину основи q₂, отримаємо дріб, в цілій частині якого бу­де b_-2, і т.д. Повторюючи процес множення S раз, знайдемо всі S цифр числа в новій системі числення. При цьому всі дії мають виконуватися за правилами q₁-арифметики, тому в цілій частині дробів що отримуємо, появляються еквівале­н­ти цифр нової системи числення, записані у вихідній системі числення.

П р и к л а д: Перетворимо десятковий дріб А = 0,625 в двійкову систему числення (q₂ = 2).

0,		625
	
		2
b-1 =1,		250	А2 = 0,1010
	
		2
b-2 =0,		500
	
		2
b-3 =1,		000
	
		2
b-4 =0,		000

П р и к л а д: Перетворити двійковий дріб А₂ = 0,1101 в десяткову сис­тему числення (q₂ = 10 = 1010₂).

0,			1101
		
			1010
b-1 = 8	1000,		0010	А10 = 0,8125
		
			1010
b-2 = 1	0001		0100
		
			1010
b-3 = 2	0010		1000
		
			1010
b-4 = 5	0101		0000

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

Для перетворення неправильних дробів із одної системи числення в ін­шу необхідно проводити перетворення цілої та дробової частини окремо за пра­вилами описаними вище.

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

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

2. Економічність системи числення. Система з більшою основою q забе­зпечує подання числа з меншою кількістю розрядів. Але при цьому ус­кладню­ється реалізація фізичного елемента з більшою кількістю станів. Ефек­ти­в­ність системи числення з основою q_і оцінюється кількістю цифрових розря­дів D_і, не­обхідних для зображення певного числа з довжиною n_і, тобто D_і = q_іn_і. При цьому враховується, що зменшення значення D_і призводить до зменшення еле­ктричних схем для реалізації подання чисел в цифрових системах. Так для по­дання довільного десяткового числа довжиною n₁₀ = 6 використовують D₁₀ = q₁₀n₁₀ = 106 = 60 цифророзрядів. У двійковій системі для подання того ж числа (з врахуванням співвідношення n₂ = 3 n₂) необхідно мати D₂ = q₂3n₂ = 236 = 36 цифрових розрядів. Найбільш економічною є система з основою q = 2, 73 …  3.Двійкова система економічно поступається трійковій на 5,8 %, проте має надійніші фізичні елементи. Крім того для запам’ятовування цифр тріскової системи 0, 1, 2 використовуються два двійкових фізичних елементи. Тобто най­ефективнішою є двійкова система числення.

3. Трудомісткість та швидкодія виконання арифметичних операцій. Чим менша основа q, тим менше цифр бере участь в обчисленні даних і тим вища швидкодія цифрових систем.

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

Двійково-десяткову систему числення застосовують для вирішення еко­номічних задач, які характеризуються великим об’ємом вхідних і вихідних да­них і відносно малим об’ємом розрахунків.

Двійково-десяткова система має такі переваги:

• не потрібно переводити дані з однієї системи в іншу;

• зручність контролю результатів зображенням їх на екрані дисплея;

• зручність автоматичного контролю через наявність надлишкових кодів в зображення цифр: 1010, 1011,…, 1111.

Завдання для освоєння матеріалу

1. Подати довільне число у вигляді полінома.

Приклад: Зобразити десяткове число 528,23₁₀ у вигляді полінома:

528,23₁₀ = 510² + 210¹ +810⁰ + 210^-1 + 310^-2.

Приклад: Зобразити двійкове число 10011,01₂ у вигляді полінома:

10011,01₂ = 12⁴ + 02³ + 02² + 12¹ + 12⁰ + 02^-1 + 12^-2.

Приклад: Зобразити шістнадцяткове число АС3Е₁₆ у вигляді полінома:

АС,3Е₁₆ = А16¹ + С16⁰ + 316^-1 + Е16^-2.

2. Перевести довільне ціле число з однієї системи числення в іншу.

Приклад: Подати у двійковій системі числення десяткове число 108₁₀:

108	2
108	54	2
0	54	27	2				10810 = 11011002
	0	26	13	2
		1	12	6	2
			1	6	3	2
				0	2	1
					1

Задане вище число можна перевести у двійкове при допомозі проміжної (вісімкової) системи числення у двійкову:

108	8		10810 = 1548
8	13	8
28	8	1
24	5
4

В наступному кроці вісімкове число за допомогою тріад перетворюємо у двійкове:

1	5	4	1548 = 11011002
001	101	100

Приклад: Перевести двійкове число 1101100₂ у десяткове:

1101100₂ = 12⁶ + 12⁵ + 02⁴ + 12³ + 12² + 02¹ + 02⁰ = 64 + 32 + 8 + 4 = 108₁₀.

Приклад: Перевести вісімкове число 154₈ у десяткове:

154₈ = 18² + 58¹ + 48⁰ = 64 + 40 + 4 = 108.

3. Перевести довільне дробове число з однієї системи в іншу.

Приклад: Перевести десяткове число 0,34 у двійкове:

0,34  2 = 0,68 переносимо 0

0, 68  2 = 1,36 переносимо 1

0,36  2 = 0,72 переносимо 0

0,72  2 = 1,44 переносимо 1

0,44  2 = 0,88 переносимо 0

0,88  2 = 1,76 переносимо 1

0,76  2 = 1,52 переносимо 1

процес перетворення припиняємо з врахуванням заданої розрядної сітки або заданої точності подання числа, отримаємо 0,34₁₀ = 0,0101011₂.

Приклад: Перевести десяткове число 0,34₁₀ у вісімкове:

0,34  8 = 2,72 переносимо 2

0,72  8 = 5,76 переносимо 5

0,76  8 = 6,08 переносимо 6

0,08  8 = 0,64 переносимо 0

0,64  8 = 5,12 переносимо 5

перетворення припиняємо і отримуємо число 0,34₁₀ = 0,25605₈.

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

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

Приклад: Перетворення десяткового числа 108,34₁₀ у двійкове:

108,34₁₀ = 1101100,0101011₂.