Розробка управляючого і операційног вузлів ЕОМ
1. Завдання.
Розробити управляючий і операційний вузли ЕОМ з наступними
параметрами:
1. Система числення:
1.2 десяткова
2. Спосіб представлення інформації:
2.1 з фіксованою комою
3. Загальна кількість розрядів:
3.2 24
4. Набір операцій:
основна:
4.2 ділення
додаткова:
4.7 логічне множення
5. Основний тип використовуваних логічних елементів:
5.4 КМОН
6. Загальна функціональна схема проектованого пристрою подана на рис.
1.
рис. № 1
|СОП – сигнал операції |
|СПО – сигнал початку |
|операції |
|СС – синхронізуючий сигнал |
|СЗО – сигнал закінчення |
|операції |
|ОР – ознака операції |
2. Огляд і аналіз літературних джерел
2.1 Поняття про комбінаційну схему і
цифровий автомат. (Каган ст. 62-65)
Пристрій, який перетворює дискретну інформацію, в загальному випадку
має n входів для вхідних сигналів і k виходів, з яких знімаються вихідні
сигнали.
Кожний з вхідних сигналів являє собою деякий символ (букву) вхідного
алфавіту. В свою чергу, вихідні сигнали являють собою символи (букви)
вихідного алфавіту. В якості букв цих алфавітів звичайно використовуються
двійкові і, рідше, десяткові цифри.
Перетворення інформації в ЕОМ виконується електронними пристроями
(логічними схемами) двох класів: комбінаційними схемами і цифровими
автоматами.
В комбінаційних схемах (КС) сукупність вихідних сигналів (вихідне
слово Y) в дискретний момент часу ti однозначно визначається вхідними
сигналами (вхідним словом X), які поступили на входи в той самий дискретний
момент часу.
Закон функціонування КС визначений, якщо є задана відповідність між
словами її вхідного і вихідного алфавітів, наприклад, в вигляді таблиці.
Другий, більш складний клас перетворювачів дискретної інформації
складають цифрові автомати. Цифровий автомат навідміну від комбінаційної
схеми має деяке скінченне число різних внутрішніх станів.
Під дією вхідного слова цифровий автомат переходить з одного стану в
інший і видає вихідне слово. Вихідне слово на виході цифрового автомату
в дискретний момент часу визначаєтся вхідним словом, яке поступило в цей
момент часу на вхід автомату, і внутрішнім станом автомату, яке є
результатом дії на автомат вхідних слів в попередні дискретні моменти часу.
Комбінація вхідного слова і біжучого стану автомата в даному такті
визначає не тільки вихідне слово, але й стан, в який автомат перейде до
початку наступного такту.
Цифровий автомат містить пам’ять, що додається з запам’ятовуючих
елементів (ЗЕ) - тригерів, елементів затримки та інших, що фіксують стан, в
якому він знаходився. Комбінаційна схема не містить ЗЕ. Тому її називають
автоматом без пам’яті або примітивним автоматом.
Структурна схема цифрового автомату містить ЗЕ1 - ЗЕk та комбінаційні
схеми КС1 і КС2.
Мал. № 1 Комбінаційна схема (а) і цифровий автомат (б).
Стан ЗЕ, що визначає стан автомату, передається в формі сигналів qi по
ланцюгах прямого зв’язку на входи КС2 і по ланцюгах зворотнього звязку на
входи КС1. На входи комбінаційних схем поступають також сигнали x1,...,xn з
входу автомату.
Вихідне слово виробляється в КС2, причому вхідними змінними для неї
служать букви вхідного слова і стани ЗЕ - стани автомату. Вихідні сигнали
КС1 переводять автомат в нові стани, при цьому вхідними змінними для цієї
схеми служать букви вхідного слова і стани ЗЕ. Одночасність появи нових
значень вхідних сигналів на всіх входах пристрою досягається за допомогою
тактових сигналів (синхросигналів), що забезпечують передачу інформації з
ЗЕ на входи комбінаційної схеми одночасно з сигналами, що поступають на її
входи з інших пристроїв.
В ряді випадків при аналізі автомата його заміняють автоматом з одним
еквівалентним входом і з одним еквівалентним виходом і рахують, що
еквівалентні вхідний сигнал x(t) і вихідний сигнал y(t) приймають значення
з відповідним чином перетворених алфавітів P і S вхідних і вихідних
сигналів.
Для задання цифрового автомата повинно бути вказано:
1) вхідний алфавіт [pic]
2) вихідний алфавіт [pic]
3) алфавіт стану [pic]
4) початковий стан автомату [pic]
5) функція переходу [pic]
6) функція виходів [pic] - однозначно визначає залежність відповідно
стану автомата [pic] в момент дискретного часу [pic] і вихідного сигналу
y(t), від стану автомата Q(t) і вхідного сигналу x(t) в момент дискретного
часу t.
Використовуючи функції переходів і виходів, поведінку автомата можна
описати рівняннями
[pic] (1)
[pic] (2)
де t=0,1,2 ...; Q(0)=Q0.
Рівнянням (1) і (2) відповідає автомат, вихідний сигнал якого залежить
від стану автомата і від сигналу на його вході. Такий автомат називається
автоматом Мілі.
В пристроях ЕОМ широко використовуються так звані автомати Мура,
в яких вихідний сигнал y(t) в момент дискретного часу t залежить виключно
від стану автомата Q(t) в цей момент часу і незалежить від вхідного сигналу
x(t).
Функціонування автомата Мура описується рівняннями
[pic] (3)
[pic] (4)
де t=0,1,2 ... ; Q(0)=Q0.
Функції переходів і виходів можуть задаватись різними способами,
наприклад в вигляді таблиці або з допомогою графів. При заданні в виді
графа стан автомата зображається вершинами, а переходи з стану в стан -
дугами. На дугах вказується значення вхідних сигналів, які викликають
відповідні переходи. Вихідні сигнали автомата Мура вказуються біля вершин
графа.
В випадку автомата Мілі вихідні сигнали, що виробляються перед переходом,
вказуються на відповідних дугах.
В теорії автоматів вводиться поняття повної системи переходів і повної
системи виходів автомата. Якщо для двох любих станів Qi і Qj автомата є
вхідний сигнал, який переводить автомат з стану Qi в Qj, то такий автомат
називається автоматом з повною системою переходів. Автомат Мура має повну
систему виходів, якщо вихідні сигнали різні для всіх його станів.
При побудові вузлів ЕОМ, які являються цифровими автоматами, в якості
запам’ятовуючих елементів (елементів пам’яті) використовуються елементарні
автомати. Елементарними автоматами є автомати Мура з двома станами,
що володіють повними системами переходів і виходів.
2.2 Декомпозиція обчислювального пристрою
на операційний і керуючий блоки.
(Каган ст. 166-168)
Операційний блок складається з регістрів, суматорів і інших вузлів,
які виконують прийом з зовнішнього середовища і зберігають коди слів, їх
перетворення і видачу в зовнішнє середовище результату перетворення, а
також видачу в керуючий блок і зовнішнє середовище, які повідомляють
сигнали, які належать множині [pic], про знаки і особливі випадки знаків
операндів, їх окремих розрядів, особливих випадків значень проміжкових і
кінцевих результатів операції.
Процес функціонування під час пристрою обробки цифрової інформації
додається з послідовності тактових інтервалів, в яких операційний блок
виробляє певні елементарні операції перетворення слів. Операційний блок
виконує деякий набір елементарних перетворень інформації, наприклад, таких,
як передача слова з одного регістра в інший, використання оберненого коду,
зсув і т.д.. Виконання цих елементарних операцій ініціюється поступленням в
операційний блок відповідних керуючих сигналів з деякої множини сигналів
[pic].
Елементарна функціональна операція (або деяка їхня комбінація), яка
виконується за один тактовий інтервал і приводиться в дію одним керуючим
сигналом [pic], називається мікрооперацією.
В деякі такти можуть поступати декілька керуючих сигналів, викликаючи
паралельне під час виконання відповідних мікрооперацій. Така сукупність
мікрооперацій називається мікрокомандою. Частково, мікрокоманда може
додаватися з одної мікрооперації.
Керуючий блок (або керуючий автомат) виробляє розподілену під час
послідовності керуючих сигналів [pic] породжуючих в операційному блоці
потрібну послідовність мікрооперацій.
Послідовність керуючих сигналів визначається керуючим командним кодом,
який поступає в керуючий блок ззовні, і сигналами [pic], залежним від
операндів і проміжкових результатів перетворень.
Операційний блок задається його структурою, тобто складом вузлів і
зв’язками між ними, і виконуваним операційним блоком набором мікрооперацій.
Послідовність мікрокоманд, що забезпечує виконання даної операції,
називається мікропрограмою даної операції.
Функціонування обчислювального пристрою може бути описано сукупністю
реалізуючих в ньому мікропрограм. В деяких випадках це зручно, хоча це і не
єдиний можливий спосіб описування цифрових пристроїв.
2.3 Кодування десяткових чисел
(Каган ст. 50-51)
Таблиця 1.1 Двійково-десяткові коди
|Десятк|Код |Код з |Код 2|Десятк|Код |Код з |Код 2|
|ові |8421 |надлишком |з 5 |ові |8421 |надлишком |з 5 |
|цифри | |3 | |цифри | |3 | |
|0 |0000 |0011 |11 |5 |0101 |1000 |01 |
| | | |000 | | | |010 |
|1 |0001 |0100 |00 |6 |0110 |1001 |01 |
| | | |011 | | | |100 |
|2 |0010 |0101 |00 |7 |0111 |1010 |10 |
| | | |101 | | | |001 |
|3 |0011 |0110 |00 |8 |1000 |1011 |10 |
| | | |110 | | | |010 |
|4 |0100 |0111 |01 |9 |1001 |1100 |10 |
| | | |001 | | | |100 |
Код 8421. Найбільше поширення в обчислювальній техніці знайшов код
8421, в якому кожна цифра десяткового числа замінюється відповідним
чотирьохрозрядним двійковим числом. Цей код зручний для виконання машиною
(а не вручну) перетворення з десяткової системи в двійкову і навпаки. Цей
код аддитивний, тобто сума представлення двох цифр є кодом їх суми.
Але використання цього коду пов’язане з труднощами пошуку переносу в
наступний десятковий розряд і важкістю переходу до зворотнього і
доповнюючого коду для десяткових чисел, що полегшує виконання алгебраїчної
дії.
Це пояснюється тим, що код 8421 не є самодоповнюючим, тобто інверсія його
двійкових цифр не дає коду доповнення десяткової цифри до 9.
Код з надлишком 3 зручний при виконанні арифметичних операцій над
десятковими цифрами, так як він є самодоповнюючим. Крім того, легко
визначається перенос, так як сума двох доданків, кожне з яких береться з
надлишком 3, вийде з надлишком 6, що виключає лишні кодові комбінації.
Для отримання правильного коду суми з отриманого результату відкидається 3.
В деяких випадках для використання суттєво, що код 0 містить 1 і тому
легко відрізнити наявність коду 0 від попадання коду цифри. Код з надлишком
3 не дуже зручний для перетворення чисел з одної системи числення в іншу.
Код 2 з 5. Десяткові цифри зображаються п’ятьма розрядами, з яких
містять дві 1. Ця надмірність використовується для контролю правильної
передачі цифри. В виразі кожної цифри присутні дві 1. Будь-яка помилка в
одному розряді перетворює 0 в 1 або 1 в 0, в результаті вийде більше або
менше двох 1, що вкаже на помилку. При одночасній появі двох помилок
можливі випадки,
коли їх не вдається знайти (якщо 0 в одному розряді перетворюється в 1, а в
другому розряді 1 в 0).
2.4 Управляючий автомат
(Каган стр.241 - 243)
Будь-який цифровий пристрій складається з двох частин – операційного
та управляючого блоків. Операційний блок характеризується сукупністю
визначених в ньому мікрооперацій, кожна з яких являє собою деякий
виконуваний в даному операційному блоці елементарний акт передачі або
перетворення інформації,
що ініціалізується поступленням управляючого функціонального сигналу на
деяку управляючу шину.
Будь-яка команда, операція або процедура, що виконується в
операційному блоці, описується деякою мікропрограмою і реалізується за
декілька тактів,
в кожному з яких виконується одна або декілька мікрооперацій. Для
реалізації команди, операції або процедури (мікропрограми) необхідно на
відповідні управляючі шини операційного блоку подати певним чином
розподілену в часі послідовність управляючих функціональних сигналів.
Частина цифрового вичислювального пристрою, що призначена для
генерації послідовностей управляючих функціональних сигналів, називаються
управляючим блоком або управляючим пристроєм. Послідовність, що генерується
управляючим блоком, задається кодом операції, що поступають на входи блоку,
сигналами з операційного блоку, що несуть інформацію про особливості
операндів і проміжкові та кінцеві результати операцій, а також з
синхросигналами, що задають границі тактів.
Формально управляючий блок можна розглядати, як скінченний автомат, що
визначається:
а) множиною двійкових вихідних сигналів V = {v1,…,vm}, що відповідають
множині мікрооперацій операційного блоку. При vi = 1 розпочинається i-та
операція;
б) множиною вхідних сигналів U = {u1,…un}, що відповідає блоку
двійковому коду операцій і двійковому значенню освідомлюючих сигналів;
в) множиною мікропрограм;
г) по множинах вхідних і вихідних сигналів і мікропрограм визначається
множина внутрішніх станів блоку Q = {Q0,…Qr}, потужність якого в процесі
проектування старається мінімізувати. Управляючий автомат може бути
заданий, як автомат Мура
Q(t + 1)=A[Q(t), u1(t),…,un(t)];
v1(t) = B1[Q(t)];
……………………………..
vm(t) = Bm[Q(t)];
або автомат Мілі
Q(t + 1)=A[Q(t), u1(t),…,un(t)];
v1(t) = B1[Q(t),u1(t),…,un(t)];
……………………………...
vm(t) = Bm[Q(t),u1(t),..,un(t)],
де функції переходів і виходів A, B визначаються заданою
мікропрограмою.
2.5 Керуючі автомати з “твердою” логікою
Керуючі автомати з “твердою” логікою являють собою логічні схеми,
які виробляють розподілені по часу керуючі функціональні сигнали. На
відміну від керуючих пристроїв з збереженою у пам’яті логікою в цих
автоматах можна змінити логіку роботи тільки шляхом перероблення схем
автомата.
В склад схеми входять регістр кода операції, який є частиною регістра
команд, лічильник тактів, дешифратор тактів і дешифратор кода операції,
а також логічні схеми утворення керуючих функціональних сигналів.
На лічильник тактів поступають сигнали від блока синхросигналів,
і лічильник з кожним сигналом міняє свій стан. Стан лічильника
представляють номера тактів, які міняються від 1 до n. Дешифратор тактів
формує на j-му виході одиничний сигнал при i-му стані лічильника тактів,
тобто під час i-го такта.
Дешифратор кода операції виробляє одиничний сигнал на j-му виході,
якщо виконується j-та команда.
Логічні схеми утворення керуючих функціональних сигналів для кожної
команди збуджують формувачі функціональних сигналів для виконання потрібних
в даному такті мікрооперацій.
Недоліком розглянутих схем є одинакове число тактів для всіх команд.
Це потребує вирівнювання числа тактів виконання команд по найбільш “довгій”
команді, що призведе до затрати часу.
Автомат Мілі, побудований на мікропрограмі, має число станів, як
правило, менше, ніж число станів еквівалентного йому автомата Мура. З цієї
точки зору використання автомата Мілі є кращим. Але використання автомата
Мілі в якості керуючого автомата не завжди можливо. Це пояснюється тим,
що керуючий автомат працює в контурі з операційним блоком. В автомата Мілі
перехід в новий стан здійснюється одночасно з формуванням вихідного
сигнала. Тому, якщо операційний блок виробляє освідомлюючі сигнали зразу ж
при виникненні керуючих сигналів, а керуючий автомат є автоматом Мілі,
можлива наступна недопустима ситуація: автомат Мілі ще не змінив стан, а на
його входи прийшли нові значення освідомлюючих сигналів, які потребують
виконання іншого переходу.
Для виключення можливих збоїв в роботі керуючих автоматів ставляться
спеціальні схеми затримки або,що є таким самим, один з двох автоматів
(керуючий або операційний) виконують в вигляді автомата Мура, який видає
вихідний сигнал після зміни стану (перехода).
2.6 Системи логічних елементів (Каган стр. 73)
Основні параметри систем логічних елементів:
Питома напруга і сигнали. Системи елементів характеризуються кількістю
напруги, що використовуються, і її номінального значення.
Для логічних елементів вказується полярність і рівень вхідного та
вихідного сигналу.
Коефіцієнт з’єднання по входу. Визначає максимально можливе число
входів логічних елементів. Збільшення числа входів пов’язане з ускладення
схеми елементів і призводить до погіршення інших параметрів.
Коефіцієнт розгалуження по виходу. Показує, на скільки логічних входів
може бути одночасно навантажений вихід даного логічного елементу.
Завадостійкість. Завадою називають небажану електричну дію (пульсація
напруги живлення, дія паразитних ємностей) на логічний елемент, яка може
призвести до спотворення даних. Завадостійкість – це здатність елемента
правильно функціонувати при наявності завад; визначається максимально
допустимою напругою завади, при якому не настає збій у його роботі.
Швидкодія. Характеризується середнім часом затримки розповсюдження
сигналу: [pic], де tз1 і tз2 – затримка вихідного сигналу відносно фронту
і спаду вхідного.
2.7 Двійково-десятковий перетворювач
(Чу стр. 75 - 80)
Алгоритм двійково-десяткового перетворювача базується на способі
ручного перетворення. Він перетворює 10-бітні цілі двійкові числа в
десяткові, причому кожен десятковий розряд кодується десятковим числом.
Використовуються такі регістри:
A(4 – 1) регістр розряду 100
B(4 – 1) регістр розряду 101
C(4 – 1) регістр розряду 102
D(0 – 3) лічильник
Q(1 – 12) регістр вихідного числа
T(0 – 2) регістр управління
K(0 – 4) = T декодер
Оператор cor:
X ( cor X(4 – 1),
IF (X = 5, 6, 7, 8, 9) THEN (X ( X add 3).
Перетворення відбувається в касрегістрі C – B – A.
На першому кроці касрегістр встановлюється в 0. Потім вміст
касрегістру C – B – A – Q зсуваєтсья на один біт вліво, і тоді в регістр A
попадає старший біт числа, що перетворюється. На кроці 3 перевіряєтсья чи
потрібна корекція вмісту регістрів A, B, C, тобто чи не містить хоча б один
з них числа,
що більше, ніж 4. Описані мікрооперації зсуву вліво і умовної корекції
повторюються до тих пір, поки останній біт регістру Q не попаде в регістр
A.
A ( 0, B ( 0, C ( 0, D ( 0, FINI ( OFF, T ( 0
C – B – A – Q ( Shl C – B – A – Q, T ( 1
D ( countdn D, T ( 2
IF (D = 0) THEN (T ( 4) ELSE (T ( 3),
A ( cor A, B ( cor B, C ( cor C, T ( 0
FINI ( ON
Перетворення з десяткової системи у двійкову є складнішим. Тому ми не
будемо його використовувати.
2.8 Структура і мікропрограми АЛП
для ділення чисел з фіксованою крапкою.
(Каган ст. 211, 213-219)
Ділення в ЕОМ звичайно зводиться до виконання послідовності віднімання
дільника спочатку з діленого, а потім з утворюючихся в процесі ділення
часткових залишків і зсуву часткових залишків.
Реалізувати ділення можна двома основними способами.
1. Ділення з нерухомим діленим і зсуваючим вправо дільником.
Цей спосіб ділення заснований на прямому копіюванні дій при ручному
діленні. Структура АЛП для ділення має вигляд, який зображений на
малюнку 6-8, а.
мал. 6-8 а) (Каган стр. 214)
Початкове ділене X заноситься в PгX, а дільник Y – в старші розряди
Pг1Y. Дільник зсувається вправо шляхом косої передачі з Pг1Y в Pг2Y і
прямої передачі з Pг2Y в Pг1Y. Віднімання дільника виконується
підсумувуванням додаткового коду дільника. Цифри частки залишків, які
визначають по знаку часткових залишків, фіксується в регістрі Pг1Z шляхом
послідовного занесення їх в молодший розряд Pг1Z і зсуву вмісту Pг1Z з
допомогою косої передачі в Pг2Z і прямої з Pг2Z в Pг1Z.
Недоліком такого АЛП є подвійна довжина суматора і його регістрів.
2. Ділення з нерухомим дільником і зсувом вліво діленого.
Цей спосіб дозволяє будувати АЛП з суматором одиночної довжини
(малюнок 6-8, б).
малюнок 6-8, б (Каган стр. 214)
Тут нерухомий дільник Y зберігається в PгY, а ділене X, зсуваючись
вліво відносно Y, знаходиться в двох регістрах: старші розряди X – в Pг1X,
а молодші – в Pг2X. Ділення починається з зсуву вліво діленого X шляхом
косої передачі його в PгCm і Pг3X і відповідних прямих передач в Pг1X. Далі
на вхід суматора подається зсунуте вліво ділене, утворюється частковий
залишок шляхом підсумовуванням додаткового коду дільника, і наступна цифра
частки заноситься в звільнений при зсуві X розряд Pг2X.
Арифметично-логічний пристрій розглянутого типу широко застосовується
для ділення.
Алгоритм ділення з нерухомим дільником з відновленням залишку.
1. Берутся модулі від діленого і дільника.
2. Початкове значення часткового залишку покладається рівним старшим
розрядам діленого.
3. Частковий залишок подвоюється шляхом зсуву на один розряд вліво.
При цьому в звільнений при зсуві молодший розряд часткового залишку
заноситься наступна цифра діленого.
4. З зсунутого часткового залишку віднімається дільник і аналізується
знак результату віднімання.
5. Наступна цифра модуля частки рівна 1, якщо результат віднімання
додатній, і 0, якщо від’ємний. В останньому випадку значення остачі
відновлюється до того, яке було до віднімання.
6. Пункти 3, 4 і 5 послідовно виконуються для одержання всіх цифр
модуля частки.
7. Знак частки плюс, якщо знаки діленого і дільника однакові, в іншому
випадку – мінус.
Розглянемо тепер більш детально ділення в АЛП з нерухомим дільником.
Структурна схема АЛП дана на малюнку 6-9.
малюнок 6-9 (Каган стр. 215)
Схема містить: суматор Cm; вхідний регістр Pг1 для збереження
дільника; вхідний регістр суматора PгA, в який поступає прямий або
зворотній код дільника; вихідний регістр суматора PгCm, в якому утворюється
частковий залишок; регістри діленого PгB (старші розряди) і Pг2 (молодші
розряди); допоміжний регістр Pг2’ для зсуву діленого, тригери знаків
діленого і дільника ТгЗн1 і ТгЗн2; лічильник циклів СчЦ для підрахунку
числа одержаних цифр частки. Одержані в процесі ділення цифри частки
заносяться в звільнені розряди Pг2’.
Мікропрограма ділення для випадку додатніх чисел приведена на
малюнку 6-10. Пояснемо процедуру відновлення остачі.
малюнок 6-10 (Каган стр. 217)
Якщо віднімання дає від’ємний результат (См[0] = 1), то попередній
частковий залишок, який зберігається в PгB, передається в PгCm, для чого
попередньо обнулюється PгA. В PгCm прийом здійснюється з зсувом вліво на
1 розряд. Це забезпечує відновлення попереднього часткового залишку і
зміщення його відносно дільника перед наступним відніманням.
Мікропрограма, яку ми розглядаємо, призначена для обробки додатніх
чисел. А також її можна легко перетворити для обробки чисел з любими
знаками,
які представленні в прямому коді. Для цього треба внести такі зміни:
після прийому операндів в PгB, Pг2 і Pг1 значення знакових розрядів X і Y
передаються в тригер знака – відповідно ТгЗн1 і ТгЗн2. Потім в PгB [0] і
Pг1 [0] заноситься 0, тобто виконується перехід до модулів X і Y. Розряд
знаку частки встановлюється в 0 при ТгЗн1 = ТгЗн2 і в 1 в протилежному
випадку.
Розглянутий метод ділення носить назву ділення з відновленням залишку.
Недоліком цього методу є необхідність введення спеціального такту для
відновлення залишку.
Звичайно в ЕОМ для ділення використовується другий метод – ділення без
відновлення залишку.
Алгоритм ділення з нерухомим дільником без відновлення залишку.
Пункти 1-3 співпадають з алгоритмом ділення з відновленням залишку.
4. З зсунутого часткового залишку віднімається дільник, якщо залишок
додатній, і до зсунутого часткового залишку додається дільник, якщо залишок
від’ємний.
5. Наступна цифра модуля частки рівна 1, якщо результат віднімання
додатній, і 0, якщо від’ємний.
Пункти 6, 7 співпадають з попереднім алгоритмом.
Можна показати, що часткові залишки після виконання додавання при
діленні без відновлення залишку одержуються такі самі, як і залишки після
зсуву відновленного залишку при діленні з відновленням залишку.
Дійсно, оскільки зсув часткового залишку на один розряд вліво є
еквівалентом множення його на два, одержимо: 2*a – b = 2*(a – b) + b, (6-
5),
де a – частковий залишок; b – дільник.
Аналогічно
2na = {…{[(a – b)*2 + b] + b}*2 + … + b}. (6-6)
Ділення без відновлення залишку завжди потребує для одержання одної
цифри частки тільки додавання або віднімання з зсуву часткового залишку.
Мікропрограма ділення цілих додатніх чисел без відновлення залишку у
своїй початковій частині співпадає з мікропрограмою ділення без відновлення
залишку. Різниця з’являєтья після формування знаку частки. На малюнку 6-11
приведена частина мікропраграми ділення без відновлення залишку після
мікрокоманди фіксації знаку частки.
малюнок 6-11 (Каган стр. 219)
Блок-схема показує, що поки невизначені всі цифри частки (СчЦ <> 0),
в залежності від знаку часткового залишку або підсумовується Y (при См [0]
= 1), або віднімається Y (при См [0] = 0). В одержаному новому частковому
залишку аналізується знак і в ньому визначається цифра частки. Після
завершення всіх циклів ділення (СчЦ = 0) видається реультат. При цьому якщо
залишок від’ємний, то він відновлюється шляхом підсумуванням Y.
Ділення чисел, що представленні в залежності від знаку прямим
доповнюючим кодом, можна зробити не переходячи до модулів. При цьому
алгоритм ділення є подібним до розглянутих.
Відмінності заключаються в наступному (для випадку ділення без
відновлення залишку):
1. Так як ділене і дільник можуть мати різні знаки, то дія з частковим
залишком (додавання або віднімання Y) залежать від знаку залишку і дільника
і визначаються таблицею 6-4.
|Знак залишку |Знак дільника|Дія |
|+ |+ |Віднімання Y |
|+ |- |Додавання Y |
|- |+ |Додавання Y |
|- |- |Віднімання Y |
таблиця 6-4 (Каган стр. 219)
Якщо знак залишку співпадає з знаком дільника, то zi = 1, інакше zi =
0.
2. Якщо X > 0 і Y < 0, то частку необхідно збільшити на одиницю.
Якщо X < 0 і Y > 0, то частку необхідно збільшити на одиницю у випадку
залишку від ділення, яке не дорівнює нулю.
Якщо X < 0 і Y < 0, то частку необхідно збільшити на одиницю у випадку
залишку від ділення, яка рівна нулю.
Ділення правильних дробів виконується так, як і ділення цілих.
Різниця заключається тільки у тому, що ділене має, як правило, таку ж
довжину, як дільник. Але можна допустити, що ділене має ще n молодших
розрядів, які рівні нулю. Тоді стає ясно, що алгоритм ділення дробів нічим
не відрізняється від алгоритму ділення цілих.
2.8.1 Арифметичний пристрій з фіксованою крапкою (Чу стр. 130-135)
Арифетичний пристрій виконує арифметичні команди, що зберігаютьсяв
пам’яті обчислювальної машини. У тому випадку, якщо цей пристрій додає і
віднімає додаткові коди паралельно, тобто ми виконуємо арифметичні дії над
всіма розрядами одночасно, то це є паралельний арифметичний пристрій.
В такому пристрої є схема паралельного суматора або паралельного
віднімання.
Двійкові числа, що представляються знаковим бітом і двійковим модулем
числа, в якому, між цілою і дробною частиною розміщені завжди на одному
місці, називаються двійковими числами з фіксованою крапкою. Є два способи
представлення таких чисел: модуль – ціле число, або модуль – простий дріб.
Якщо кома розміщена між знаковим бітом і старшим бітом числа, то будь-яке
число в такому форматі є дробовим. Якщо ж кома розміщена справа від
молодшого біта значущої частини, то число є цілим.
| | |
|1 Число |S |
|22 | |
малюнок 4.1 (Чу стр. 131)
Представимо число у вигляді цілого. Це представлення має вид “знак +
модуль”. Нуль в знаковому біті означає, що число додатнє, а одиниця – що
воно від’ємне. Для числа, модуль якого дорівнює нулю, в знаковому біті
завжди формуєтсья одиниця.
Будемо використовувати регістри AC – накопичуючий регістр,
MQ – регістр частки, SR – запам’ятовуючий регістр, SC – лічильник зсувів.
Використовується схема паралельного суматора і регістр DVOV. AS, MQ, SR,
складаються з двох частин: в одній зберігається знак, а в другій – модуль
числа. Отже, ми використовуємо субрегістри для знаку AS(S), MQ(S), SR(S)
і субрегістри модуля AS(M), MQ(M), SR(M). Субрегістром називається частина
регістру, сукупність бітів якої мають особливий зміст. Об’єднання декількох
субрегістрів або регістрів при виконанні спеціальної операції в один
регістр називається касрегістром.
Регістр DVOV сигналізує про стан переносу при діленні.
Ми не будемо його використовувати.
Структура:
AC(M) = AC(1 – 23),
SR(M) = SR(1 – 23),
MQ(M) = MQ(1- 23).
AC(S, R, Q, 1- 23),
SR(S, 1 - 23),
MQ(1 – 23),
SC(0 – 5),
C.
Паралельний суматор:
ADD(R, Q, 1 – 23) = ADSR(R, Q, 1 – 23) EXOR ADAC(R, Q, 1 – 23)
EXOR C(R, Q, 1 – 23),
C(R, Q, 1 – 22) = ADSR(Q, 1 – 23)*ADAC(Q, 1 – 23) + ADAC(Q, 1 – 23)
*C(Q, 1 – 23) + C(Q, 1 – 23) * ADSR(Q, 1 – 23), C(23) = 0.
Опис виводів Z:
Z(R, Q, 1 – 23) = 0 – 0 – AC(M) add2 0 – 0 – SR(M) – 0.
Опис оператора add2:
W(R, Q, 1 – 23) = X(R, Q, 1 – 23) add2 Y(R, Q, 1 – 24)
C(23) = Y(24),
C(R, Q, 1 – 22) = X(Q, 1 – 23)*Y(Q, 1 – 23) + Y(Q, 1 – 23)*C(Q, 1 – 23) +
C(Q, 1 – 23)*X(Q, 1 – 23)
W(R, Q, 1 – 23) = X(R, Q, 1 – 23) EXOR Y(R, Q, 1 – 23) EXOR
C(R, Q, 1 – 23).
Тут в регістрі АС є біт АС(Q), який міститься між знаковим бітом і старшим
бітом значущої частини регістру. В цьому біті міститься перенос з старшого
біту значущої частини, який утворюється при додаванні або віднімані. Розряд
АС(R) містить перенос з біту АС(Q).
В нашій схемі звичайно використовуються однобітні повні суматори,
що мають по три входи і два виходи. На схемі 4.3 i-ий біт першого
доданку – ADAC(i), j – біт другого доданку ADSR(i), i – ий біт переносу –
C(i),
(i – 1) – й біт переносу C(i – 1) і i – ий біт суми – ADD(i), де i – номер
розряду паралельного суматора.
малюнок 4.3 та 4.4 (Чу стр. 134)
На малюнку 4.4 входи ADAC(R, Q, 1 – 23) і ADSR(1 - 23) з’єднані з виходами
регістрів АС(R, Q, 1 –23) і SR(1 – 23) відповідно. На входи ADSR(R, Q)
сигнали з регістру SR звичайно не поступають. Замість цього при
необхідності на цих шинах формуються константи 0 або 1. Вхід С(23) на
якому повинен бути 0 є входом переносу для крайнього правого біту суматора.
Входи
ADD(R, Q, 1 – 23) являють біти суми, а виходи С(R, Q, 1 – 23) – переноси
для всіх 26 однобітних повних суматорів. Схема паралельного суматора
зображена на малюнку 4.5.
малюнок 4.5 (Чу стр. 134)
В алгоритмі ділення виконується перевірка однієї з спеціальних вихідних шин
паралельного суматора. Частина цих шин зв’язана з входами субрегістру
АС(M),
а друга – з входами субрегістру SR(M). Це і є виводи Z.
Оператор add2 виконує додавання значущих частин двох 26 – бітних двійкових
чисел; у цьому випадку вхідний перенос С(23) = 0. Його зручно
використовувати також при додаванні додаткового коду від’ємника з
зменшуваного (вілнімання); в такому випадку вхідний перенос С(23) = 1.
Таким чином, вхідний пернос розглядається як додатковий вхід паралельного
суматора; потрібна модифікація додавання описується оператором add2.
2.8.1.1 Ділення (Чу стр. 144 – 148)
При діленні чисел, представлених у форматі з фіксованою комою ділене
знаходиться в касрегістрі, який додається з регістрів АС і MQ, а дільник –
в регістрі SR; частка поміщається в регістр MQ, а залишок – в регістр AC.
Дільник після виконання операції залишається в регістрі SR; ділене в
касрегістрі губиться. Алгоритм ділення побудований на основі використання
методу порівняння. Його зручно розділити на дві частини: ініціалізація
(малюнок 4.11) і відповідно ділення (малюнок 4.12)
малюнок 4.11 (Чу стр. 144)
малюнок 4.12 (Чу стр. 145)
При ініціалізації перевіряється чи не буде переповнення, і визначається
знак частки. Переповнення при діленні визначається шляхом віднімання
діленого з дільника (субрегістри AC(M) і SR(M)). При відніманні до дільника
додають ділене з субрегістру AC(M) в оберненому коді. Якщо перевірка
показує, що значення на шині суми Z(Q) = 0 то з цього слідує, що ділене з
AC(M) більше або дорівнює дільнику з SR(M). При переповненні в регістр DVOV
засилається одиниця, і процес ділення завершується. Якщо ж перевірка
показує, що Z(Q) = 1, то процес ініціалізації продовжується і визначається
знак частки. Знак частки записується як нуль, якщо знакові біти AC(S) і
SR(S) співпадають; в іншому випадку в M(Q) засилається одиниця. Потім
проводиться запуск процесу ділення.
При діленні значення часткового залишку в субрегістрі AC(M) зберігається в
оберненому коді. Процес починається з засилки в регістр лічильника зсувів
SC константи 2310. Далі вміст касрегістру AC(M) – MQ(M) зсувається вліво на
один біт; одночасно біт MQ(1) інвертується і переміщується в біт AC(23) для
того, щоб частковий залишок в субрегістрі AC(M) залишався в оберненому
коді. Дільник з субрегістру SR(M) порівнюється з частковим залишком AC(M).
Якщо порівняння показує, що Z(Q) = 0, то це означає, що частковий залишок з
AC(M) більше дільника з SR(M) або дорівнює йому. В цьому випадку в біт
MQ(23) засилається одиниця і одночасно дільник з SR(M) додається до
часткового залишку з AC(M). Якщо ж Z(Q) = 1, то це означає, що дільник з
SR(M) більше часткового залишку AC(M); у цьому випадку пересилка і
додавання не відбуваються. Далі вміст лічильника зсувів SC зменшується на
одиницю і перевіряється на нуль. Якщо вміст SC <> 0, то алгоритм
продовжується до вичерпання SC. Далі частковий залишок в AC(M)
перетворюється в вихідне представлення шляхом інвертування всіх бітів. На
цьому процес ділення завершується.
Процедурний опис ділення:
Ділене = + 00001111 = + 1510,
Дільник = - 0011 = - 310,
Частка = - 0101 = - 510,
Залишок = + 0000 = 0.
AC(R, Q, M) ( 0 – 0 – AC(M)’;
IF (Z(Q) = 1) THEN (DVOV ( 1, GOTO C2);
IF (SR(S) = AC(S)) THEN (MQ(S) ( 0) ELSE (MQ(S) ( 1);
SC ( 35;
AC(M) – MQ(M) ( AC(2 – 35) – MQ(1)’ – MQ(2 – 35) – 0;
IF (Z(Q) = 0) THEN (MQ(35) ( 1, AC(R, Q, M) ( 0 – 0 – AC(M) add2
0 – 0 SR(M) – 0;
SC ( countdn SC;
IF (SC <> 0) THEN (GOTO C1);
AC(M) ( AC(M)’
END
2.8.1.2 Мікропрограми арифметичного пристрою
(Чу стр. 177)
Розглянемо тепер відповідність між управляючими сигналами і
мікроопераціями. Процес встановлення такої відповідності розпадається на
три етапи. На першому етапі вибираються управляючі сигнали для
ініціалізації роботи пристрою і запуску генераторів синхро- і управляючих
сигналів. Ця група сигналів генерується незалежно від мікропрограми. На
другому етапі проходить прив’язка мікрооперацій команд до одної або
декількох мікрокоманд, а на третьому встановлюється зв’язок між кожною
мікрооперацією, що зустрічається в мікропрограмі і управляючим сигналом для
неї. По результатам виконання двох цих результатів будується мікропрограма.
Мікропрограма ділення також додається з чотирьох мікрокоманд: D1, D2, D3,
D4. Мікрокоманда D1 пересилає адрес операнду з регістру K в адресний
регістр AD і витягує операнд з основної пам’яті.D2 – ініціалізаація; D3 -
ділення; D4 – завершення.
F ( CM(H),
AD ( K,
SR ( M(AD),
H ( countup H.
F ( CM(H),
AC(R, Q, M) ( 0 – 0 AC(M)’,
IF Z(Q) <> 1) THEN (DVOV ( 1, BR(1) ( 1)
ELSE (BR(2) ( 1),
IF (BR(2) = 1) THEN (MQ(S) ( SR(S) EXOR AC(S), SC ( 35),
IF(BR(1) = 1) THEN (H ( F(ADS))
ELSE (H ( countup H),
IF (BR(1) = 1) THEN (DO DSET),
BR ( 0.
F ( CM(H),
SC ( countdn SC,
AC(M) – MQ(M) ( AC(2 – 35) MQ(1)’ – MQ(2 – 35) – 0,
IF (Z(Q) <> 1) THEN (MQ(35) ( 1,
AC(R, Q, M) ( 0 – 0 – AC(M) add2 0 – 0 SR(M) – 0),
IF (SC = 0) THEN (H ( countup H).
F ( CM(H),
AC(M) ( AC(M)’,
H ( F(ADS),
DO SET.
2.8.2 Послідовний арифметичний пристрій
(Чу стр. 223 –228)
Арифметичний пристрій здатний виконувати додавання, віднімання, множення і
ділення. Ці арифметичні операції можуть виконуватись паралельно, послідовно
або змішаним способом. Парлельний арифметичний пристій складує всі цифри
двох чисел одночасно, в той час, як послідовний арифметичний пристрій може
виконувати додаваннядвох чисел цифра за цифрою при допомозі простого
суматора. Паралельний арифметичний пристрій виконує операції скорше, тоді
як послідовний арифметичний пристрій дешевше.
Тут описуєтсья послідовні двійково-десяткові арифметичні пристрої.
Послідовний двійково- арифметичний пристрій може виконувати додавання
одного або декількох бітів одночасно. Для його реалізації потрібно
однобітові
(або багатобітові) пристрої додавання-віднімання. Подібним чином пристрій
десяткової арифметики може додавати одну або декілька десяткових цифр
одночасно, і для його реалізації потрібно однорозрядні або багаторозрядні
десяткові суматори. Двійково- арифметичний пристрій використовує
однобітовий суматор-віднімач, а десятковий арифметичний пристрій
використовує однорозрядний десятковий суматор-віднімач.
2.8.2.1 Представлення чисел
В розглянутому арифметичному пристрою число має довжину 24 біта. Від’ємні
числа зображаються в доповнюючому коді. Формат числа показаний на малюнку
6.1. Двійкова кома розміщена між знаковим і старшим бітами; таким чином,
число має дробову частину і зображено в двійковій формі.
|X0 |X1 |X2 |… |X22 |X23 |
Додатнє число зображається в вигляді знака і модуля:
[pic], де X – число, знак плю зображуєтсья нулем,
а xi – числові біти. Найбільш можливе число рівне 0, 11…1, або 20 – 2-23.
Від’ємне число зображається в додатковому коді
[pic] (6.2)
Знак мінус зображується одиницею. Так як число в додатковому коді дорівнює
сумі одиниць молодшого біта числа і числа в оберненому коді,
формулу (6.2) можна переписати в наступному вигляді:
[pic] (6.3)
і [pic], де [pic] - інверсія xi. Найменш можливе від’ємне число рівне
1, 00…0, або –1.
2.8.2.2 Повний суматор-віднімач
Повний однобітовий сумотор має вигляд логічної схеми з трьома входами і
двома виходами. Нехай X, Y, і Wi, представляють собою доданок і вхід
переносу відповідно, а виходи Z і W0 – суму і результуючий перенос.
Однобітовий суматор можна визначити за допомогою наступного опису виводів:
Z = X EXOR Y EXOR Wi, (6.4)
W0 = X*Y + Y*Wi + Wi*X.
Однобітовий віднімач має вигляд логічної схеми с трьома входами і двома
виходами. Нехай X, Y, Wi, Z і W0 – входи і виходи схеми. Однобітовий
віднімач можна визначити при допомозі наступного опису вивиодів:
Z = X EXOR Y EXOR Wi (6.5)
W0 = X’*Y + Y*Wi + W*X’.
Як видно з привдених вище виразів, вихідний сигнал Z однаковий для обох
оисів, хоча Wi в виразі (6.4) означає перенос, а в виразі (6.5) – позика.
Вихід W0 в двох випадках одинаковий, зи винятком лише того, що X в виразі
(6.5) інвертується.
Описаний вище повний суматор і віднімач можна об’єднати в одну схему. Нехай
однобітовий регістр N вказує на додавання, якщо його вміст рівний 1, і на
віднімання, якщо його вміст рівний 0. Однобітовий суматор можна визначити
при допомозі наступного опису виводів:
Z = X EXOR Y EXOR Wi, (6.6)
W0 = (N COIN X)*Y + (N COIN X)*Wi + Y*Wi.
Якщо вміст регістру N дорівнює 1, то вираз (6.6) спіпадає з вираом (6.4);
якщо цей вміст дорівнює 0, то з виразом (6.5). Однобітовий суматор-
віднімач, описаний виразом (6.6), буде використаний для побудови двійкового
послідовного арифметичного пристрою.
2.8.2.3 Структура
Регістр А є накопичуючим регістром, регістр Q – регістр множника-частки,
регістр R – регістр операнда, який використовується також в якості
буферного регістра пам’яті. Арифметичні операції виконуються в цих трьох
регістрах, які сумісно використовуються з суматором-віднімачем.
малюнок 6.2 Чу стр. 226
| | |Регістр А |Регістр Q |
|Операці|Регістр|спочатк|вкінці |спочатк|вкінці |
|я |R |у | |у | |
|Ділення|Дільник|Ділене |Залишок|Нулі |Частка |
R(0 – 23),
A(0 – 23),
Q(0 – 23),
BC(4 – 0),
WC(4 – 0),
E,
C,
AV,
DV,
N,
SUM,
DIF,
DSTEST,
OV,
SA,
SR,
AQE(0 – 48) = A – Q – E,
AQ(0 – 47) = A – Q.
Z = R(23) EXOR A(23) EXOR C,
W = (N COIN A(23))*R(23) + (N COIN A(23))*C + R(23)*C,
AVTEST = N*SA’*SR’*C + N*SA*SR*C’ + N’*SA’*SR*C’ + N’*SA*SR’*C,
DVSTOP = N’*A(0)’*R(0)’*SA*E’ + N’*A(0)*R(0)*SA’ + N*A(0)’*R(0)*
SA*E’ + N*A(0)*R(0)’*SA’.
2.8.3 Ділення двійкових чисел
Ділення двійкових чисел виконується по алгоритму ділення без відновлення
залишку, розробленим Берксом, Голдстайном і фон Нейманом.
Нехай X і Y – ділене і дільник відповідно. Частковий залишок віднімається з
допомогою рівняння [pic]. При цьому, якщо знак залишку ri-1 (а не ri) і
дільники однакові, біт частки qi равен 1 і частичний залишок утворюється
відніманням діленого Y з 2ri – 1. Якщо знаки різні, біт частки qi дорінює
0,
і частковий залишок одержується додаванням дільника Y з 2ri – 1. Частка Q
утворюється з бітів qi з відповідністю з наступним правилом:
[pic], де (-1 + 2-n) – член корекція, який додається до бітів частки. (Це
поянює, чому qi називається бітом псевдочастки).
Початковий залишок дорівнює діленому X. Перевірка знаків залишку ri – 1 і
дільника Y, формування біта залишку qi і частки Q, утворення нового
залишку,
а також збільшеня і перевірка індекса i входять в склад циклу. Після виходу
з циклу к частному Q добавляєтсья коректуючий член і утворюється правильна
частка.
2.8.3.1 Умова припинення ділення
Якщо дільник малий порівняно з діленим, частка може показатися дуже
великим і не поміститися в регістрі Q. В випадку виникнення такої ситуації,
називається переповненням при діленні, частка буде неправильне, і ділення
необхідно зупинити.
Раніше було прийнято, що ділене і дільник – дробові числа. Бажано, щоб і
частка була дробовим числом, звідки слідує, що ділене повинно бути меншим
дільника. Це і є критерій, який дозволяє сформувати умови припинення
ділення.
Є чотири випадки, при яких виникає необхідність зупинки ділення.
2.8.3.2 Блок-схема алгоритма
Блок-схема послідовності перевірки переповнення зображена на
малюнку 6.11.
малюнок 6.11 Чу стр. 243
Як видно з цієї блок-схеми, алгоритм знаходиться в циклі очікування,
неперервно провіряючи стан регістра DSTEST. Коли вміст регістра DSTEST стає
рівним 1, починається виконання основної частини алгоритма. Регістри BC, C
і E скидуються в 0, регістр N встановлюється в 1 (при додаванні) або
скидується в 0 (при відніманні). Потім починається цикл послідовного
додавання (або віднімання). Під час циклу додавання (або віднімання) біт
переноса (або позики) запам’ятовується в регістрі C, але біт суми (різниці)
ігнорується, так як він не використовується, за винятком випадку переносу з
самого лівого біта, який запам’ятовується в регістрі SA. Вміст регістра SA
використовуєтсья оператором DVSTOP. Крім цього, під час додавання
(віднімання) в регістрі E запам’ятовується результат логічної операції OR
над бітом суми (або різниці) і E; тому якщо вміст регістра Е; тому якщо
вміст регістра E дорівнює 0, то це означає, що модуль суми (різниці)
дорівнює 0. Цикл виконуєтсья 24 рази. Після виходу з циклу перевіряється
DVSTOP. Якщо виникло переповнення, регістр DV встановлюється
в 1. На цьому виконання алгоритму закінчується, і регістр DSTEST
встановлються в 0, щоб забезпечити повернення до алгоритму ділення.
Після повернення з перевірки регістра DV починається послідовність ділення.
Якщо вміст цього регістру дорівнює 1, виконання ділення припиняється.
В протилежному випадку починається цикл ділення. В цьому циклі виконується
шість мікрооперацій, а саме встановлення біта Q(23) в 1 або 0, зсув вмісту
касрегістра AQ вліво, звернення до послідовності SUM – DIF, скидання
регістра OV в 0, а також збільшення лічильника WC і його перевірка. Якщо
вміст регістра WC не дорівнює 23, цикл повторюється. Вихід з циклу
здійснюється при WC, рівним 23. Тоді вміст регістру Q зсувається вліво на 1
біт, а частка коректується. Корекція додається в інвертуванні біта Q(0) і
встановленні біта Q(23) в 1. На цьому виконання послідовності ділення
закінчується.
2.8.4 Алгоритм десяткового ділення
Десяткове ділення засновано на використанні алгоритма ділення з
відновленням залишку. Початкове ділення знаходиться в масиві регістрів R,
а 16-розрядне ділене – в касрегістрі AQ. Після виконання операції ділення
частка розміщується в масиві регістрів Q, а залишок – в масиві регістрів A;
ділене губиться. Переповнення індикується вмістом регістру DV.
На малюнку 6.20 і 6.21 приведені блок-схеми алгоритма ділення десяткових
чисел.
малюнок 6.20 Чу стр. 265
малюнок 6.21 Чу стр. 266
Додовання і віднімання, які використовуються цим алгоритмом, виконуються
підпослідовністю SUM – DIF, а перевірка переповнення – з допомогою
підпослідовності DSTEST. З малюнку 6.20 видно, що ділення починається з
скидання регістру WC в 0 і звернення до підпослідовності DSTEST з цілью
перевірки можливості переповнення при діленні. Підпослідовніст DSTEST,
зображена в виді блок-схеми на малюнку 6.21, в свою чергу починається з
звернення до підпослідовності SUM – DIF; останні здійснює віднімання
дільника, який знаходиться в масиві регістрів R, з старшої частини
діленого, який знаходиться в масиві регістрів A. Різниця залишається в
масиві регістрів A.
Потім виконується перевірка, яка дозволяє встановити, чи не містить регістр
OV позики. Якщо регістр OV містить 0, значить місце переповнення при
діленні немає, і ділене відновлюється шляхом звернення до підпослідовності
SUM – DIF, здійснюється додавання дільника з масива регістрів R і різниці
масива регістрів A. В цей момент виконання підпослідовності DSTEST
закінчується скидуванням регістра DSTEST в 0.
Після повернення з підпослідовності DSTEST до підпослідовності ділення
виконується перевірка регістра DV на рівність 1. Випадок рівності DV
одиниці вказує на переповнення при діленні, що викликає припинення операції
ділення. Якщо ж в індикаторі переповнення DV міститься нуль, ділення
продовжується. Так як успішний вихід перевірки умови переповнення при
діленні означає, що вміст масива регістрів A менше дільника, який
знаходиться в масиві регістрів R, ділене в масиві регістрів A множиться на
10 шляхом зсуву на одну десяткову цифру вліво.
Як видно з малюнка 6.20, в алгоритмі є два цикла – внутрішній і зовнішній.
Внутрішній цикл починаєтсья з встановлення лічильника DVC в 0. Потім
починається внутрішній цикл додавання-віднімання. В внутрішньому циклі
виконується звертання до підпослідовності SUM –DIF, яка здійснює додавання
або віднімання, а також перевірки виникнення позики при відніманні.Якщо
позики немає, лічильник DVC збільшується на 1, і керування передається до
початку внутрішнього циклу. Цикл віднімання повторюється до тих пір, поки
не виникне позика, на чому виконання циклу закінчується. Наявність позики
означає, що вміст лічильника DVC є цифра частки; значення вмісту DVC
пересилається в субрегістр Q(,8). Лічильник WC збільшується на 1, після
чого його нове значення порівнюється з константою 8. Якщо вміст WC дорівнює
8, касрегістр A зсувається вліво на одну десяткову цифру, і управління
передається до початку зовнішнього циклу. Зовнішній цикл повторяється до
тих пір, поки лічильник WC на стане рівним 8. В цей момент визначаються
знаки частки і залишку, які поміщаються в регістри SA і SQ відповідно. На
цьому виконання операції ділення закінчується.
2.9 КМОН
З багатьох серій цифрових мікросхем на польових транисторах найбільше
використання одержали серії мікросхем КМОП.
Скорочено КМОП – це початкові букви чотирьох слів з повного визначення:
комплементарні польові транзистори з структурою металл – окисел –
напівпровідник. Слово комплементарний переводиться як взаємно доповнюючий.
Так називаються пару транзисторів, які подібні по абсолютним значенням
параметрів, але з напівпровідниковими структурами, взаємно відображені як
би в вигляді негатива і позитива. В біполярній схемотехніці – це
транзистори n-p-n і p-n-p, в польовій p-канальні і n-канальні. Тут p –
перша буква від слова positive,
n – negative.
Цікаво, що на перших етапах розвитку біполярних цифрових мікросхем
пророкували широке розповсюдження комплементарних біполярних логічних
елементів на n-p-n і p-n-p транзисторах. Для прикладу, якщо в ТТЛ вдалось
би замінити вихідний каскад на двохтактний комплементарний, принципово
збільшилась би економічність елемента. Але біполярна комплементарна
транзисторна логіка не прижилась через труднощі виготовлення на кристалі
великої кількості компактних по площині і високоякісних по параметрах
інтегральних p-n-p транзисторів.
Нагадаємо, що в аналоговій схемотехніці, де p-n-p транзистори просто
необхідні як для спрощення схемотехніки, так і для покращення властивостів
підсилювачів, проблема створення добрих p-n-p транзисторів для технологів
все ж таки існує. Тому реально біполярні мікросхеми ТТЛмають на виході так
називаємі квазікомплементарний каскад. На кристалі роблять тільки n-p-n
транзистори. Ця компромісна схема елемента ТТЛ вийшла оптимальною і
перспектвною на багато десятеліть.
Перші спроби випускати серії простих польових елементів, подібний по схемі
з РТЛ, до успіху не привели. Логічні елементи виходили малошвидкодіючі,
оскільки внутрішній опір канала у польового транзистора на порядок більше,
чим опір між колектором і емітером насиченого біполярного транзистора.
Однополярні мікросхеми МОП не відрізнялись успіхом ні перешкодостійкістю,
ні малою потребуючою силою. Добрі результати дало використання двополярного
інвертора, який побудований на комплементарній польовій парі.
Тепер можна конкретно вибрати необхідні елементи КМОН для реалізації даної
схеми, хоча при проектуванні постійно перевірялася можливість втілення схем
за допомогою стандартних мікросхем серій КМОН.
2.10 Мікросхеми
Отже:
- як D-тригери беремо мікросхему К176ТМ2
Ця мікросхема містить два D-тригера і є корисна тим, що має інверсні
виходи, а також має входи скидання (Reset).
Довжина тактового імпульсу не повинна бути меншою 100 нс.
Час встановлення виходів – не менше 25 нс.
Логічні мікросхеми також легко підібрати.
К561ЛА7 К561ЛА8 К561ЛА9 К561ЛИ2
Хоча мікросхеми серії К561 і підтримують напругу живлення до 15 Вольт (чим
більша напруга, тим більша швидкодія) але ми змушені використовувати
мікросхеми старішої серії К176, максимальна напруга живлення яких – 9
Вольт. Тому напруга живлення всього автомата не повинна перевищувати 9
Вольт,
а в ідеальному випадку бути рівною цьому значенню.
3. Розробка графу
Будується на основі автомату Мура, що використовує алгоритм двійкового
ділення (паралельний пристрій). Хоча за умовою я повинна розробити пристрій
для ділення десяткових чисел, але, враховуючи, що блок-схема десяткового
ділення складніша у два рази (Каган) та маючи КМОН, яка є повільною, я буду
використовувати двійковий алгоритм (Чу, 23) та шифратори і дешифратори.
Модифікований алгоритм приведе до такого графа:
CM – дозвіл
___
CM – логічна операція множення
X0: SR(M) <= AC(M)
X1: SR(S) = AC(S)
X2: SC = 23
Стани в автоматі Мура відповідають таким мікрокомандам:
Z0: SM ( 1
Z1: AC(M) ( – AC(M)’
Z2: MQ(S) ( 0
Z3: MQ(S) ( 1
Z4: SC ( 0
Z5: AC(M) – MQ(M) ( AC(1 – 22) – MQ(23)’ – MQ(1 – 22)
Z6: MQ(22) ( 1
AC(M) ( AC(M) add SR(M)
Z7: SC ( countup SC
Z8: AC(M) ( AC(M)’
В цифровому автоматі Мура в якості запам’ятовуючих елементів
використовується двохтактні тригери, що дає можливість уникнути ефекту
гонок. Виберемо D – тригери.
Кількість станів цифрового автомату забезпечать чотири двохтактні
D – тригери. Для кодування станів виберемо код “8421”, який є найкращий для
машинної обробки.
4. Розробка управляючого блоку.
|Таблиця кодування станів ЦА Мура |
| |E |F |G |H | |E |F |G |H |
|S0 |0 |0 |0 |0 |S5 |0 |1 |0 |1 |
|S1 |0 |0 |0 |1 |S6 |0 |1 |1 |0 |
|S2 |0 |0 |1 |0 |S7 |0 |1 |1 |1 |
|S3 |0 |0 |1 |1 |S8 |1 |0 |0 |0 |
|S4 |0 |1 |0 |0 | | | | | |
де (i Zi = Si (кодуємо кодом 8421)
Визначимо умови станів для управляючого автомату
[pic]
[pic]
[pic]
Ready – сигнал готовності до початкувиконання операції
Sync – синхронізуючий сигнал
При використанні D – тригера ми отримаємо наступний управляючий автомат:
5. Розробка операційного блоку
5.1 Основна дія
Тепер, коли ми маємо готовий управляючий автомат, можна приступати до
проектування операційного автомата. Для виконання ділення нам необхідно
мати вісім чотирьохрозрядні суматори і одинадцять чотирьохрозрядних
регістри, не враховуючи супроводжуючих логічних схем.
Всі необхідні елементи легко можна знайти в (3) сторінки 193 – 290.
В якості базового суматора можна вибрати К561ИМ1. Єдиною позитивною рисою
цієї мікросхеми є те, що її характеристики детально розписані
в (3) ст. 267.
Недоліки:
– страшенно мала швидкість (хоча, можливо, і не погана, як на елемент
КМОН), час спрацювання – 550 нс. Тобто при послідовному під`єднанні
чотирьох суматорів, як у нашому випадку, швидкість спрацювання становитиме
4.4 мкс.
– відсутність синхронізуючого входу. Цей недолік змушує нас вводити ще
чотири чотирьохрозрядні регістри для збереження сум часткових добутків.
У ролі робочих регістрів буде виступати мікросхема К561ИР9.
Це є послідовно-паралельний регістр.
P/S = 0 – ввімкнено послідовний режим. При приході на C додатнього імпульсу
вміст регістра буде зміщено вліво і в D0 буде записано біт з JK–входу.
P/S = 1 – при приході додатнього імпульсу на синхронізуючий вхід з входів
D0 – D3 буде принято чотири біти.
R – при приході на цей вхід додатнього імпульсу регістр безпосередньо
(асинхронно) буде скинутий в нулі.
T/C – перемикає виходи. Якщо T/C=1 то на виходах пряме число (Q0 – Q3),
інакше на виходах будуть інвертовані рівні.
Час встановлення регістра при живленні 10 Вольт приблизно становить
200 нс.
5.2 Додаткова операція
Додаткова операція.
Основні алгоритми виконання
порозрядних логічних операцій.
Всі способи виконання порозрядних логічних операцій можна розбити
на дві групи:
– послідовні;
– паралельні.
Для простоти обробки чисел візьмемо під знаковий розряд 23.
Послідовний спосіб добре описаний в (2), стор. 145. Він полягає у тому,
що аргументи записуються в регістри і потім послідовно, біт за бітом,
перебираються і відповідний результат записується у регістри результату.
Коротко такий алгоритм представляється так:
1. Записати аргументи в регістри RGA та RGB.
2. Якщо ми пройшли всі розряди, то кінець.
3. Виконуємо задану логічну операцію над нульовими розрядами RGA та RGB і
записуємо результат в старший розряд RGC.
4. Зсуваємо RGA, RGB та RGC на один розряд вправо.
5. Переходимо на 2.
Після n ітерацій в регістрі RGC матимемо результуюче значення,
де n – розрядність задачі.
Такий метод потребує мінімальної кількості логічних схем, однак є дуже
повільним. Саме через недостатню швидкість виконання ми змушені відмовитися
від цього методу, бо елементи КМОН самі по собі не відрізняються великою
швидкістю.
Якщо взяти частоту шини 0.25 мегагерц, як того вимагала основна задача, то
для опрацювання 24 розрядів необхідно буде 96 мікросекунди – гігантський
інтервал часу простоювання системи вцілому. Тому у нашому випадку
доцільніше використовувати другий метод, тобто метод паралельної обробки.
Хоча він і потребуватиме в 24 разів більше логічних схем, однак можна
зекономити на регістрах аргументів, приймаючи їх безпосередньо з шини. Для
результату все ж доведеться використати регістр, щоб забезпечити роботу в
режимі автомату із внутрішньою пам`яттю.
К561ЛА7
6. Зауваження до схеми автомату
виконання основної операції
Оскільки вибраний лічильник не може рахувати у зворотньому напрямку, на
початку роботи у нього записується не 23, а 0. Тепер при виконанні ітерацій
множення умовою виходу рівність лічильника 23.
Обов'язковим є заземлення всіх входів мікросхем що не використовуються
( див.(3) стор. 195). Ця умова спричинена специфікою КМОН - елементів і при
невиконанні її мікросхеми можуть вийти з ладу.
До кожної мікросхеми необхідно підвести живлення і землю живлення:
– для мікросхем К561ИР9, К561ИМ1, К176ИЕ19 живлення (+9 Вольт)
і землю подавати на 16 і 8 ножки відповідно;
– для інших мікросхем живлення і землю подавати на 14 і 7 ножки відповідно.
6.1 Часові характеристики схеми
Швидкість системи визначається швидкістю спрацювання найповільніших її
вузлів. Наша схемі є паралельним пристроєм.Це означає, що операції
виконуються за один машинний такт. Тут можна виділити такі частини:
занесення даних, ініціалізація, 23 такти за лічильником, завершення
ділення. Враховуючи, що час спрацювання одного суматора становить не менше
550 нс. отримаємо, що лише для виконання додавання необхідно 4.4 мкс.
Додавши ще час занесеня в регістр (200 нс.) а також час перемикання
тригерів станів плюс супроводжуючої логіки, матимемо, що тривалість
високого рівня синхронізуючого імпульсу повинна бути не менше 6 мкс. Час
нульового рівня синхросигналу повинен бути достатнім
для спрацювання логічних схем умов, тобто приблизно не менше 2 мкс.
Таким чином очевидно, що період синхросигналу не повинен бути меншим, ніж
4 мкс, і наш автомат працюватиме на частотах не більше 0.16 мегагерц.
Для комп`ютера це звичайно ж замало, однак для якоїсь простої системи із
обмеженими запасами енергії повинно бути достатньо.
Бажана форма сигналу
Елементи КМОН дуже чутливі до крутизни фронтів синхронізуючих імпульсів.
Якщо час активізуючого фронту перевищить якесь певне критичне значення (для
кожної серії воно своє) пристрій не спрацює належним чином (3).
Висновок
Ми розробили автомат для ділення десяткових чисел. Всередині ми працювали з
двійковими числами, перетворюючи їх на вході та виході у десяткові.
Недоліком цього автомату є мала швидкодія, так як елементною базою для нас
служили КМОН – технології. На сьогоднішній час розроблені спеціальні
мікропроцесори, які виконують задану дію. Затрати на них є значно меншими.
На початок і кінець автомату я поставила перетворювач з двійково-
десяткового у двійковий та з двійкового у двійково-десятковий. Мікросхеми
К155ПР6 та К155ПР7 належать до логіки ТТЛ, тому їм передували перетворювачі
рівнів від КМОН до ТТЛ К176ПУ1 та К176ПУ2. На виходах стоїть мікросхема
К156ПУ6. Я використала мікросхеми ТТЛ тому, що в КМОН логіці таких
мікросхем немає, а працювати з десятковими або двійково-десятковими числами
є важко.
Список літератури
1. Методичні вказівки до курсового проекту з курсу “Схемотехніка ЕОМ”
для студентів спеціальності 6.08.04 “Комп’ютерні науки”.
Львів ДУ”ЛП”, 1995.
2. Каган Б. М. Электронные вычислительные машины и системы.
Москва: Энергоатомиздат, 1985.
3. Шило В.Л. Популярные цифровые микросхемы: Справочник.
Москва: Радио и связь, 1987.
4. ЕСКД. Правила выполнения электрических схем.
Москва: Издательство стандартов, 1976.
5. Обозначения условные графические в схемах. Двоичные логические
элементы ГОСТ 2.743 – 72
Москва: Государственный комитет стандартов совета министров СССР.
6. Я. Чу Организация ЭВМ и микропрограммирование.
Москва. Мир, 1975.
Зміст
1. Завдання 2
2. Огляд і аналіз літературних джерел 3
2.1 Поняття про комбінаційну схему та цифровий автомат 3
2.2 Декомпозиція обчислювального пристрою на операційний
і керуючий блоки
6
2.3 Кодування десяткових чисел 7
2.4 Управляючий автомат 8
2.5 Керуючі автомати з “твердою” логікою 9
2.6 Система логічних елементів 10
2.7 Двійково десятковий перетворювач 11
2.8 Структура і мікропрограми АЛП для ділення чисел
з фіксованою крапкою
13
2.8.1 Арифметичний пристрій з фіксованою крапкою 20
2.8.1.1 Ділення 23
2.8.1.2 Мікропрограми арифметичного пристрою 26
2.8.2 Послідовний арифметичний пристрій 27
2.8.2.1 Представлення чисел 28
2.8.2.2 Повний суматор – віднімач 29
2.8.2.3 Структура 30
2.8.3 Ділення двійкових чисел 32
2.8.3.1 Умова припинення ділення 33
2.8.3.2 Блок-схема алгоритму 34
2.8.4 Алгоритм десяткового ділення 36
2.9 КМОН 39
2.10 Мікросхеми 40
3. Розробка графа 41
4. Розробка управляючого блоку 43
5. Розробка операційного блоку 45
5.1 Основна дія 45
5.2 Додаткова операція 46
6. Зауваження до схеми автомату виконання основної операції 48
6.1 Часові характеристики схеми 49
Висновки 50
Список літератури 51
-----------------------
q1
q1
x1
y1
ЗЕ1
q2
y1
x2
y2
qk
y2
ЗЕ2
KC
KC1
KC2
qk
x1
x1
x2
ym
ym
xn
xn
xn
ЗЕk
а)
б)
A ( 0
B ( 0
C ( 0
D ( 10
FINI ( OFF
A ( cor A
B ( cor B
C ( cor C
C – B – A – Q ( shl C – B – A – Q
D ( countdn D
D = 0
FINI ( ON
Знаковий біт
C(i)
ADAC(R, Q, 1 – 35)
ADAC(i)
ADSR(R, Q, 1 – 35)
C(35)
ADSR(i)
Паралельний
суматор
[pic]
ADD(R, Q, 1 – 35)
C(R, Q, 1 – 34)
C(i-1)
ADD(i)
C
w
FAS
R(0–23)
z
SR
N
SA
Q(0-23)
A(0-23)
E
SUM
OV
BC(4-0)
AV
DIF
WC(4-0)
DV
DSTEST
Вхід DDIV
Вихід
УА
Управляючий автомат
ОА
Операційний автомат
СОП
m
СПО
СС
СЗО
ОР
Вхідні дані, n розрядів
z
x
Результати обчислень
Q0
Q1
Q2
Q3
16
8
1
15
14
13
9
10
11
12
7
5
6
2
4
3
14
7
2 мкс
6 мікросекунд
. . .
. . . |
