Порозрядні операції над даними

 

Вхідний контроль:

1 Які правила виконання арифметичних операцій у позиційних системах числення Ви знаєте?

 

Виконання операції додавання у кодах дещо відрізняється від звичайного:

– розряди знаковий і розряди числа є рівноправними і перенесення у знаковий розряд необхідно враховувати і додавати до знакових розрядів;

– при виконанні операції додавання в ОК перенесення із знакового розряду необхідно додавати до молодшого розряду числа (операція циклічного перенесення);

– при виконанні операції додавання в ДК перенесення із знакового розряду ігнорується і відкидається.

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

1 Для чисел з різними знаками

 

27 _D – 30 _D = 27 _D + (– 30 _D) = 11011 _В – 11110 _В

 

представимо двійкові числа у кодах

 

ОК ДК

+ 11011 _В 0.0011011 + 11011 _В 0.0011011

– 11110 _В 1.1100001 – 11110 _В 1.1100010

 

Виконаємо операцію додавання у кодах

 

ОК ДК

0.0011011 0.0011011

1.11000011.1100010

1.1111100 1.1111101

 

Результати отримано у відповідних кодах. Перетворимо їх на ПК і подамо у десятковій системі числення

1.1111100_ОК 1.0000011_ПК – 3 _D.

Результат при роботі з оберненним кодом правильний.

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

1.1111101_ДК – 1 = 1.1111100_ОК 1.0000011_ПК – 3 _D.

Результат також правильний.

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

2 Для двох інших чисел з різними знаками

– 27 _D + 30 _D = – 1011 _В + 11110 _В

представимо двійкові числа у кодах

 

ОК ДК

– 11011 _В 1.1100100 – 11011 _В 1.1100101

+ 11110 _В 0.0011110 + 11110 _В 0.0011110

Виконаємо операцію додавання у кодах

 

ОК ДК

1.1100100 1.1100101

0.00111100.0011110

1 0.0000010 1 0.0000011

0.0000011

При виконанні операції в ОК перенесення із знакового розряду було враховано в результаті, а при виконанні операції в ДК – відкинуто. Результат в обох випадках отримано у вигляді додатного числа 11 _В = 3 _D, що є правильним.

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

– при формуванні суми у тетраді отримано число, яке не є цифрою десяткової системи числення, наприклад,

 

+

0000 1001 _BCD

0000 0110 _BCD,

0000 1111 _BCD

 

у молодшій тетраді отримано двійкове число 1111 _В, яке неможливо подати у десятковій системі числення одним розрядом;

– при формуванні суми виникає перенесення до старшого розряду (старшої тетради), а значення результату в тетраді є невірне, наприклад,

 

0000 1001 _BCD

0000 1000 _BCD,

0001 0001 _BCD

 

у молодшій тетраді отримано двійкове число 0001 В, замість 0111 В, яке є правильним результатом.

В обох випадках корекція результату в тетраді буде виконуватися при використанні коду з надлишком 3 для обох складових, або при додаванні 6 _D (0110 _B) до результату. У першому випадку:

 

0000 1111 _BCD

0000 0110 _BCD.

0001 0101 _BCD

 

Контрольні питання:

1 Чому може з’явитися необхідність корекції результату при виконанні арифметичних операцій над числами, які подані у двійково-десятковій системі числення?

2 Який код використовується для корекції результату арифметичної операції над числами, які подані у двійково-десятковій системі числення?

3 Чим відрізняється виконання арифметичних операції над числами зі знаком над числами, які подані в оберненому і доповнювальному кодах?

 

Контрольні питання підвищеної складності:

1 Виконати операцію (+92 – 121) у доповнювальному коді. Отримати результат і перевести його у десяткову систему числення.

2 Виконати операцію (+92 – 121) в оберненному коді. Отримати результат і перевести його у десяткову систему числення.

3 Виконати операцію (+ 121 – 92) у доповнювальному коді. Отримати результат і перевести його у десяткову систему числення.

4 Виконати операцію (+ 121 – 92) в оберненному коді. Отримати результат і перевести його у десяткову систему числення.

5 Перевести число +8,73 у двійкову систему числення і подати у вигляді з плаваючою точкою (у вигляді мантиси і порядку). Мантису подати у вигляді округленого восьмирозрядного (з урахуванням знака) двійкового числа у прямому, зворотному та доповнювальному кодах.

6 Перевести число –5,63 у двійкову систему числення і подати у вигляді з плаваючою точкою (у вигляді мантиси і порядку). Мантису подати у вигляді округленого восьмирозрядного (з урахуванням знака) двійкового числа у прямому, зворотному та доповнювальному кодах.

7 Виконати операцію додавання чисел, отриманих у попередніх пунктах в оберненному коді.

8 Виконати операцію додавання (+ 8.73 –5,63) у доповнювальному коді.

9 Представити число 95 у двійково-десятковій системі числення.

10 Пояснити, чому при виконанні арифметичних операцій над числами, поданими у двійково-десятковій системі числення, необхідно використовувати код з залишком 3?

11 Як перевести десяткові числа 95 і 55 у двійково-десяткову систему числення? Виконати над отриманими числами операцію додавання. Скоригувати результат.

 

ЦИФРОВІ АВТОМАТИ

 

Вхідний контроль:

1 Які логічні операції виконуються в обчислювальній техніці?

2 Які властивості логічних елементів Ви знаєте?

3 Яка різниця між комбінаційними і послідовнісними схемами?

4 Які логічні функції Ви знаєте?

5 Які способи мінімізації логічних функцій Ви знаєте?

 

Перетворення інформації в обчислювальній техніці відбувається за допомогою електронних цифрових пристроїв (ЦП) – логічних схем,які будуються з логічних елементів і забезпечують виконання арифметичних і логічних операцій над сукупністю цифрових вхідних сигналів Х_i, перетворюючи їх у сукупність вихідних сигналів Y_j. Розподіляють два класи таких пристроїв: комбінаційні схеми (КС) і послідовнісні схеми – цифрові автомати (ЦА).

В комбінаційних схемах результат перетворення – сукупність цифрових вихідних сигналів у будь-який момент часу t_n залежить лише від сукупності (комбінації) цифрових сигналів Х_i,які надходять на її входи у даний момент часу і не залежать від стану схеми, який передував надходженню сигналів Х_i. В таких схемахвідсутні елементи пам’яті, тому сигнали, які діють у такий схемі, не зберігаються. Такі ЦП ще називають цифровими автоматами без пам’яті (примітивними автоматами). До КС відносяться досить прості елементи, вузли та блоки мікропроцесорних систем: шифратори, дешифратори, мультиплексори, демультиплексори, комбінаційні суматори, перетворювачі кодів, схеми контролю тощо.

До послідовністних схем відносяться ЦП, в яких результат перетворення Y_j залежить не лише від комбінації цифрових сигналів Х_i, які надходять на її входи у даний момент часу t_n, а й від послідовності попередніх цифрових станів входів і виходів схеми – внутрішніх станів Z_f. Для запам’ятовування попередніх станів така схема повинна мати елементи пам’яті. Подібні схеми називають цифровими автоматами. Можна стверджувати, що кількість внутрішніх станів і кількість елементарних запам’ятовувальних пристроїв в цифрових автоматах зв’язані між собою такою залежністю Z = 2 ^k, де k – кількість запам’ятовувальних елементів.

Загальна теорія ЦА поділяється на абстрактну і структурну. Абстрактна теорія досліджує поведінку автомата відносно зовнішнього середовища, на рівні алгоритмів його роботи, не вирішуючи задач його побудови. Абстрактна теорія ЦА показує принципові відміни КС від ЦА для можливості подання дискретних процесів і обмеження, які є при цьому. Важливий висновок, який отримано у цих дослідженнях, полягає в тому, що в ЦА можливо реалізувати нескінченні регулярні події, на відміну від КС, де є можливість реалізувати лише скінченні події. Регулярними подіями вважаються такі події, які у скінченному алфавіті X = { x₁, x₂,…, x_n } можливо отримати з елементарних слів алфавіту X при здійсненні над ними операцій диз’юнкції, перемноження та ітерації. Нерегулярні події реалізувати у ЦА неможливо, тому що це вимагає нескінченного обсягу пам’яті. На практиці звичайно розглядаються ЦА, які мають обмежений обсяг пам’яті і називаються скінченними ЦА.

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

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

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

 

Синтез логічних схем

Правила функціонування логічних схем (ЛС) можуть задаватися у різний спосіб:

- словесне описування;

- за допомогою таблиць істинності;

- за допомогою часових діаграм;

- аналітичний – за допомогою логічних (булевих) виразів;

- у вигляді координатних діаграм.

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

Слід зазначити, що для спрощення розв’язання задачі синтезу загальна ЛС поділяється на декілька схем, кожна з яких має один вихід (із сукупності вихідних сигналів Y_j) і стільки входів, скільки входить у сукупність вхідних сигналів Х_i, необхідних для формування Y_j. Для більшого спрощення дозволяється подальше роздрібнення схеми таким чином, щоб зменшити кількість вхідних сигналів Х. Після закінчення синтезу схем усі ці дрібні схеми об’єднують в одну загальну схему ЦП. Розв’язання задачі синтезу виконується за декілька етапів.

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

На другому етапі відбувається подання описування роботи ЛС в аналітичному виді – у досконалій диз’юнктивній нормальній формі (ДДНФ), або у вигляді досконалої кон’юнктивної нормальної форми (ДКНФ). Вибір форми подання можливо обумовити співвідношенням кількості нулів та одиниць у вихідному сигналі (логічній функції) та їх розташуванням за номерами рядків таблиці істинності або технічним завданням на проведення синтезу схеми.

На третьому етапі відбувається мінімізація схеми ЦП. Найбільш просто і наочно рекомендується проводити мінімізацію за допомогою координатних діаграм (карти Карно або діаграми Вейча). Різниця між цими способами полягає лише у поданні системи координат на діаграмі. На рис. 3.1, а показано вид карти Карно, а на рис. 3.1, б – вид діаграми Вейча.

 

Рисунок 3.1 – Координатні діаграми

 

Кількість можливих комбінацій значень вхідних сигналів (логічних змінних) Х, а також кількість можливих стійких станів (логічних функцій) дорівнює K = 2 ^N, де N – кількість вхідних сигналів. Слід зазначити, що деякі стійкі стани можуть бути відсутніми, тобто вихідний сигнал Y (логічна функція) індиферентний до комбінації вхідних сигналів Х_i у цей час. Це можливо трактувати, як відсутність деяких комбінацій вхідних сигналів Х_i у повному наборі можливих. Так, наприклад, дешифратор для керування цифровим індикатором, який відображує десять десяткових цифр 0...9, має чотири входи для подання кодів двійкових чисел від 0000 до 1001, а кількість стійких станів для такої схеми дорівнює K = 2⁴ = 16. Таким чином, шість комбінацій сигналів (16 _D –10 _D = 6 _D) не можуть бути сформовані на виходах такого пристрою. Значення сигналу карти Карно (рис. 3.1, а) і діаграми Вейча (рис. 3.1, б) для трьох вхідних змінних х ₀, х ₁, х ₂, при однаковому розміщенні вхідних змінних на сторонах прямокутників, які є осями координат (загалом, вибір системи координат може бути довільним, обов’язковим є тільки зсув координат на одну клітинку відповідно одна до одної на тих напрямках, на яких необхідно розміщувати дві змінні). У клітинках на рис. 3.1, а показано набори вхідних сигналів, а на рис. 3.1, б номери рядків таблиці істинності, які відповідають один одному.

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

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

На четвертому етапі за отриманими МДНФ або МКНФ можливо побудувати принципову схему ЦП у базисі ТА-АБО-НІ. Якщо принципову схему необхідно мати в іншому базисі, то виконуємо необхідне перетворення і будуємо схему у відповідному базисі ТА-НІ (АБО-НІ). За необхідності на цьому етапі можливо зробити розрахунок часу затримки сигналу й інших параметрів схеми.

Як приклад зробимо синтез схеми дешифратора для керування одним із елементів семисегментного індикатора, який відображує десяткові цифри 0...9.

1 Таблиця істинності, що завдає алгоритм роботи цього дешифратора, – табл. 3.1.

 

Таблиця 3.1 – Таблиця істинності дешифратора

№ набору вхідних змінних	х 3	х 2	х 1	х 0	Y
					~
					~
					~
					~
					~
					~

 

2 За даними цієї таблиці запишемо вираз у вигляді досконалої диз’юнктивної нормальної форми (ДДНФ) або у вигляді досконалої кон’юнктивної нормальної форми (ДКНФ). Досконалість логічних функцій передбачає включення у вираз, який отримується, всіх логічних функцій, які використовуються для формування логічної функції. Будь-який з цих двох способів однозначно описує алгоритм роботи ЛС.

Для подання у вигляді ДДНФ вибираємо рядки таблиці, на яких значення вихідної функції Y дорівнює L 1 (логічній одиниці) і записуємо у вигляді кон’юнкції (логічного добутку) набори вхідних змінних кожного рядка, які об’єднуємо у вигляді диз’юнкції (логічної суми). Математичний вираз, що описує функцію на одному рядку, називається термом. Вхідні змінні повинні входити у кон’юнкцію таким чином, щоб значення логічного добутку дорівнювало L 1, для чого вхідні змінні, які мають значення L 0 (логічного нуля) необхідно інвертувати. Так, для нульового набору (рядок таблиці з номером 0) кон’юнкція вхідних змінних матиме вигляд:

 

 

Рядки таблиці, на яких логічна функція не визначена, не беруться до уваги. Тоді логічна функція у вигляді ДДНФ буде записана як

 

Y _ДДНФ

.

 

Для подавання логічної функції у вигляді ДКНФ вибираємо рядки, на яких значення вихідної функції Y дорівнює логічному нулю L 0, і записуємо логічну функцію у вигляді кон’юнкції (логічного добутку) диз’юнкцій вхідних логічних змінних кожного рядка. Для опису вихідної логічної функції Y у вигляді L 1 логічні зміні кожного рядка, які входять у вираз ДКНФ, необхідно проінвертувати. ДКНФ логічної функції має вигляд:

Y _ДКНФ

.

 

За виразами ДДНФ і ДКНФ можливо оцінити їхню складність у вигляді коефіцієнта зв’язку К _зв, який визначає кількість елементарних логічних функцій, які необхідно виконати для отримання результатів:

 

К _{зв ДДНФ} = 4_НІ + 4_ТА + 1_АБО = 9.

К _звДКНФ = 4_НІ + 6_АБО + 1_ТА = 11.

 

Таким чином видно, що для реалізації функції у ДДНФ необхідно 9, а для реалізації у ДКНФ – 11 логічних елементів.

3 Мінімізацію досконалих логічних функцій виконуємо за допомогою діаграми Вейча, яка для логічної функції з чотирма вхідними змінними матиме вигляд квадрата 4 × 4 клітинки. Діаграма Вейча для логічної функції, яка описана табл. 3.1, наведена на рис. 3.2.

Для мінімізації логічної функції за одиницями або за нулями на діаграмі Вейча необхідно визначити мінімальну кількість найбільших груп (контурів), що складаються з одиниць або нулів, у вигляді квадратів або прямокутників (об’єднувати можливо лише сусідні клітинки). Сусідніми вважаємо клітинки, що мають спільні сторони, при цьому клітинки, розташовані по горизонтальних та вертикальних сторонах квадрата, є сусідніми. Взагалі, ознакою сусідства можливо вважати відміну двійкового коду номера клітинки лише в одному розряді. Таким чином, аналізуючи номери клітинок у верхньому і нижньому рядках, а також у правому і лівому, можливо зробити висновок, що відповідні клітинки у цих рядках також є сусідніми і діаграму Вейча можна згорнути у циліндр по горизонталі і вертикалі. Кількість клітинок у групі повинна дорівнювати цілому ступеню двійки, тобто 1, 2, 4, 8, 16. На рис. 3.2 у вигляді кіл і овалів показано контури, які об’єднують одиниці і нулі поданої логічної функції. Контури об’єднань можуть будь-яку кількість разів перетинатися, але не можуть повністю суміщатися. Якщо функція має невизначені стани (символ – ~), то функції цієї клітинки можливо надати значення 0 або 1 таким чином, щоб отримати контур, до якого буде входити більша кількість клітинок з однаковими значеннями 0 або 1.

 

 

Рисунок 3.2 – Діаграма Вейча з контурами для одиниць і нулів

 

Таким чином, об’єднавши 1 і невизначені стани, отримали два контури, до яких входять клітинки з номерами 0, 2, 8, 10 і 2, 6, 10, 14. Мінімальною формою логічної функції для кожного з контурів будуть координати контурів на діаграмі з відсутніми координатами, на яких функція Y змінює своє значення. Так, координата х ₁ у контурі з номерами клітинок 0, 2, 8, 10 змінює своє значення; у стовпчику з клітинками 0, 8 вона має значення 0, а у стовпчику з номерами клітинок 2, 10 – 1. Таким чином, координата х ₁буде відсутня при записуванні мінімальної ДНФ (МДНФ).

Запишемо мінімальні логічні функції, які отримуємо після мінімізації

 

Y _МДНФ ,

 

Y _МКНФ .

 

Оцінимо К _зв для мінімізованих функцій:

 

для МДНФ К _зв = 2НІ + 2ТА + 1АБО = 5,

 

для МКНФ К _зв = 1НІ + 1АБО + 1ТА = 3.

 

4 За одним із отриманих у попередньому пункті виразах МДНФ або МКНФ можемо побудувати схему логічного пристрою у базисі ТА-АБО-НІ. Критерієм вибору є менше значення К _зв або завдання на розробку пристрою.

Логічні схеми будують, як правило, на елементах одного типу в базисах ТА-НІ, АБО-НІ. Це робиться для того, щоб запобігти розкиду параметрів часових затримок у схемі.

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

 

 

Простіше перетворювати вираз МДНФ до базису ТА-НІ, а вираз МКНФ до базису АБО-НІ, взагалі можливі будь-які перетворення, але при перетворенні МДНФ до базису АБО-НІ і навпаки МКНФ до базису ТА-НІ, схеми будуть більші на один логічний елемент.

Виконаємо перетворення МДНФ у базис ТА-НІ

 

Y _МДНФ ,

 

і перетворення МКНФ у базис АБО-НІ

 

Y_МКНФ .

За цими виразами будується схема дешифратора. На рис. 3.3 схема подана у базисі ТА-НІ, а на рис. 3.4 – у базисі АБО-НІ.

 

 

Рисунок 3.3 – Схема дешифратора у базисі ТА-НІ

 

 

Рисунок 3.4 – Схема дешифратора у базисі АБО-НІ

 

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

 

T _затр = t _зм× N _мc,

де T _затр – час затримки сигналів схемою;

t _зм – час затримки сигналів однією мікросхемою (визначається

технологією виготовлення мікросхеми);

N _мc – максимальна кількість мікросхем від входу схеми до її виходу.

Для розроблених схем

 

T _затр = t _зм× N _мc = 20∙10^-6 × 3 = 60∙10^-6 с,

 

де t _зм = 20∙10^-6 секунди – часова затримка однієї мікросхеми, вважаючи,

що мікросхема виготовлена за технологією ТТЛ;

N _мc = 3 – кількість мікросхем, через які проходять сигнали х ₂ і х ₀ на рис. 3.3, а також сигнал х ₁ на рис. 3.4.

 

Контрольні питання:

1 Синтезувати схему цифрового пристрою, алгоритм роботи якого задано не повністю визначеною логічною функцією, що подана у вигляді таблиці істиності:

 

№ набору	Х 3	Х 2	Х 1	Х 0	Y

 

Визначити складність логічної функції.

 

Контрольні питання підвищеної складності:

1 Виконати мінімізацію логічної функції, що подана у вигляді:

 

Y

 

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

– у базисі ТА–НІ;

– у базисі АБО–НІ.

2 Визначити складність логічної функції до і після мінімізації для кожного з базисів.