Колледж туризма и гостиничного сервиса Санкт-Петербурга

Тема: « Алгоритм ділення двійкових чисел»

Цель:«Реалізація операції ділення»

1. Початкові дані

• Тип арифметичної операції — ділення двійкових чисел;

• початковий код подання операндів — прямий;

• розрядність — ділене X — 16 біт, дільник Y — 8 біт;

• код виконання мікрооперації у суматорі — доповняльний;

• структура операційного блока — із закріпленими мікроопераціями;

• тип керуючого блока — автомат з пам'яттю на JK-тригерах.

Елементна база, перелік обов'язкового графічного матеріалу та необхідні роз­рахунки.

2. Алгоритм ділення цілих чисел

Операція ділення цілих чисел Z=X/Y зводиться до послідовності віднімання дільника Y спочатку від діленого X, а потім від створюваних в процесі ділення залиш­ків Rj.

Залежно від способу віднімання дільника Y розрізняють два основні алгоритми ділення: без відновлення залишку R, та з відновленням залишку. Обидва способи реалізуються приблизно однаковими апаратними затратами, але для ділення без від­новлення залишку потрібно більше мікрооперацій додавання і віднімання. В універ­сальних комп'ютерах зазвичай використовують ділення без відновлення залишку.

У разі ділення цілих чисел часто ділене X подається в 2и-розрядному форматі, а дільник Y — у n-розрядному.

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

1. У регістри А, В і С послідовно записуються із вхідної шини n-розрядний ді­льник Y та 2n-розрядне ділене X. У лічильник циклів СТ заноситься число циклів n-1.

2. Ділене X та дільник Каналізуються на рівність нулю. Якщо ділене X = 0, то частці Z присвоюється нульове значення і ділення закінчується. Якщо діль­ник Y = 0, то ділення переривається.

3. Установлюється можливість ділення без переповнення розрядної сітки. Для цього значення діленого подвоюється зсувом вліво на один розряд. Із зсуну­того діленого віднімається дільник. Операція віднімання дільника заміню­ється на його додавання у доповняльному коді і визначається перший за­лишок R₀ за формулою

Якщо R₀<;0, то ділення можливе; якщо R₀>;0, виникає переповнення роз­рядної сітки і ділення припиняється.

4. Якщо ділення можливе, виконуються такі основні дії:

• частковий залишок в регістрі В і зміст регістра С зсуваються вліво на один розряд (тобто подвоюються);

• із зсунутого залишку віднімається дільник, якщо попередній залишок R_i-1³0, або додається, якщоR_i-1<0. Це визначається рекурентним спів­відношенням

де i = 1, 2,..., n-1.

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

Це означає, що поточна цифра частки є інверсією знака залишку;

• зміст лічильника циклів СТ зменшується на одиницю;

• п. 4 повторюється до обнуління лічильника циклів СТ.

Значення першого (старшого) розряду частки відводиться для записування зна­ка результату на підставі виразу r ₀ = А[п]Å В[п].

5. Залишок ділення розміщується у регістрі В на місці старших розрядів діле­ного, а частка — в регістрі С. Дільник, залишок і частка мають формат n-розрядного числа із знаком. Залишок має мати той же знак, що і ділене, нульові залишки і частки завжди додатні. Якщо знак останнього залишку від'ємний, то він коректується додаванням до нього модуля дільника, після цього залишку присвоюється знак діленого.

3. Принципіальна схема модуля операційного блока для мікропрограми ділення

Принципіальна схема модуля МОБ (рис.) містить:

• DD1 — восьмирозрядний регістр дільника RGA типу ИР35;

• DD2, DD3 — двоканальний восьмирозрядниймультиплексор MUX на двох мікросхемах типу КП16;

• DD4, DD5, DD32 — мікросхеми логічних елементів "виключальне ЧИ" типу ЛП5;

• DD6, DD9 — восьмирозрядні регістри діленого RGB і RGC типу ИР13;

• DD7, DD8 — восьмирозрядний суматор SM на двох мікросхемах типу ИМ6;

• DD10, DD11,DD26, DD27 — вісім JK-тригерів типу ТВ6;

• DD12-DD15 — чотири мікросхеми логічних елементів НЕ І типу ЛАЗ;

• DD16 — дешифратор типу ИДЗ;

• DD17, DD18, DD33 — мікросхеми інверторів типу ЛН1;

• DD19, DD29 — мікросхеми логічних елементів І типу ЛИ1;

• DD20-DD22 — мікросхеми логічних елементів НЕ І типу ЛА2;

• DD23, DD25 — мікросхеми логічних елементів НЕ І типу ЛА4;

• DD24 — мікросхема логічних елементів НЕ І типу ЛА1;

• DD28 —двійковий чотирирозрядний лічильник циклів типу ИЕ10;

• DD30, DD31, DD34 — мікросхеми логічних елементів ЧИ типу ЛЛ1.

4. Схема другого рівня керування операційним блоком

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

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

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

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

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

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

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

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

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

• на підставі одержаних логічних рівнянь визначається необхідний склад мік­росхем і будується схема другого рівня керування.

Відповідність між керуючими входами мікросхем операційного блока МОБ5 наведено в табл..

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

• J5-J8 — установлення тригерів T5-T8;

• К5-К8 - обнулення тригерів T5-T8;

• S1B, S0B — задання режимів універсального регістра RGB (00 — зберігання даних, 11 — записування даних, 01 і 10 відповідно — зсув вправо і вліво);

• S1C, S0C— задання режимів роботи регістра RGC;

• ОЕ —дозвіл передачі даних мультиплексору;

• ADR — адресує канал мультиплексування: ADR = 0, ОЕ = 0 — передають­ся дані із вхідної шини; ADR- 1, ОЕ = 0 — комутуються дані з виходів су­матора;

• LCT — завантаження лічильника числом циклів —константою 0111(2)=7₍₁₀₎;

• LA — завантаження регістра RGA;

• КА — сприйняття сигналу переповнення;

• CD — вхід віднімання лічильника.

На підставі даних табл. записується система логічних рівнянь, які є осно­вою для схемної реалізації другого ступеня керування ОБ:

5. Принципіальна схема автомата Мілі для операції ділення

На рис. виконано розмічення графу мікропрограми ділення для автомата Мілі. На основі закодованої і розміченої мікропрограми будується граф автомата Мілі для реалізації операції ділення (рис.).

Максимальна кількість станів автомата L = 14.

Стани кодуються логічними виразами таким чином:

На основі графу автомата Мілі для операції ділення будується пряма структур­на таблиця переходів і виходів (табл.).

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

• для функцій збудження:

• для вихідних сигналів:

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

В даному випадку пристрій АЛП реалізується на основі синхронного принципу керування, за якого:

• тривалість машинного такту Т_с для всіх мікрокоманд, поданих операторними вершинами мікропрограми ділення, постійна;

• усі мікрооперації поділяються на дві групи: короткі (приймання і пересилання операндів, зсуви, мультиплексування та ін.) і довгі (додавання або відніман­ня дільника від діленого);

• тривалість машинного такту Т_с обирається з умови виконання за один такт довгої мікрооперації;

• тривалість синхросигналу t_СС обирається з умови виконання коротких мікрооперацій;

• тривалість машинного такту пов'язана з тривалістю синхросигналу співвідношенням Т_с =(2...3) t_СС. Уся множина операторних вершин мікропрограми ділення (див. рис. 9. 23) по­слідовно розбивається на групи К₁, К₂,..., К₇ з певною кількістю операторів з однаковими ймовірностями звернення Р₁, Р₂,..., Р₇. Групи К4 і К5 виконуються в циклі n-1=7 раз.

 

 

Колледж туризма и гостиничного сервиса Санкт-Петербурга

 

ОТЧЕТ