Доповняльних кодів цілих чисел однакового формату

Розглянемо алгоритм ділення доповняльних кодів однакової довжини за наступними форматами аргументів і результату:

=(128 + А)_m128; =(128 + B)_m128;

=(128 + D)_m128; =(128 + C)_m128;

де А, В, D, С – відповідно знакові числові змінні діленого, дільника, частки та остачі.

Принцип визначення доповняльного коду частки при діленні допов-няльних кодів чисел однакового формату полягає в тому, що передусім обчислюють знак частки ND = (NAÅNB), який записується в усі розряди частки:

D = ND ND ND ND ND ND ND, тобто

D (ND=0) = 0 000 000 і D (ND=1) = 1 111 111.

DР	А	ВP →
5 4 3 2 1	7 6 5 4 3 2 1	7 6 5 4 3 2 1
X X X X X ND X X X X 0   ND = NA ÅNB ND X X X 0 0 = =0 ПП = NDÅ = 0 ND X X 0 0 0   = NA3П Å NB = 0 ND X 0 0 0 1   = =1 ND 0 0 0 1 1 = NA1ПÅNB = 1 0 0 0 1 1 D	1 1 1 0 0 0 0 NA 0 1 0 1 0 0 0 0 0 1 1 0 0 0 NA4П   1 1 0 1 1 0 0 0 0 0 0 1 0 0 NA3П 1 1 1 0 1 1 0 1 1 1 1 0 1 0 NA2П 0 0 0 0 1 0 1 1 1 1 1 1 1 1 NA1П NA1П =(NDÅNB)=NА 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 С	1 0 1 1 0 0 0 NB NB = NA = BP 1 1 0 1 1 0 0 NB ≠ NA4П ( )   = BP 1 1 1 0 1 1 0 NB≠NA3П ( ) = BP 1 1 1 1 0 1 1 NB=NA2П = NA1П = NB пробне віднімання   = А0 (А0 ≠ 0) відновлення залишку А1П = = С

Рисунок 3.38 – Приклад ділення (-МА)_DК на (-МВ)_DК

за алгоритмом «б» при С ≠ 0 (А1П < 0, А0 ≠ 0)

DР	←А	ВP
5 4 3 2 1	7 6 5 4 3 2 1	4 3 2 1
X X X X X ND X X X X 0   ND = NAÅNB=0 ND X X X 0 0   =NA4ПÅNB =0 ПП = NDÅ = 0 ND X X 0 0 0 = NA3П Å NB=0 ND X 0 0 0 1   = NA2П Å NB=1 ND 0 0 0 1 0 = NA1ПÅNB=0 0 0 0 1 0 D	1 1 1 0 0 1 1 NA 0 1 0 1 0 0 1 1 0 1 1 NA4П 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 NA3П 0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 NA2П 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 NA1П ≠ ≠(NDÅNB)=NА 1 0 1 1 1 1 0 1 0 0 0 С = А (7/4)	1 0 1 1 NB NB = NA =     NB ≠ NA4П ( )   =     NB≠NA3П ( )   =     NB=NA2П =     NB≠NA1П ( )   = С NC = (NBÅND) = NA=1

Рисунок 3.39 – Приклад ділення (-МА) _DК на (-МВ)_DК

за алгоритмом «a» при С≠ 0 (А1П > 0).

Зазначимо, що за таким способом утворення початкового стану доповняльного коду частки при скороченій довжині значущої частини частки завжди забезпечується формування коректного підсумкового сполучення цифр у незначущих позиціях частки, які у доповняльному коді повинні мати нульові значення за ND = 0 і одиничні стани за ND = 1.

Як було визначено при діленні модулів чисел однакового формату, у загальному випадку значущі цифри частки D являють собою частку від ділення знормованого діленого А^Н на знормований дільник В^Н, причому кількість значущих цифр цілої частини частки k пов’язана із кількістю незначущих цифр діленого А і дільника В співвідношенням:

k = (НВ +1) – НА,

де НВ, НА – кількість незначущих цифр у кодах дільника В і діленого А, які відкидаються у процесі формування знормованих станів дільника В і діленого А .

Слід зазначити також, що у випадку, коли НВ<НА, тобто за (НВ+1)–НА ≤ 0 і МА<МВ, модуль частки МD = 0. Тому, за (НВ+1) – НА≤ 0 операція ділення А на В повинна блокуватися з онулюванням коду частки.

Лічба кількості значущих позицій у коді частки k звичайно виконується за допомогою реверсивного лічильника тактів (СТТ), який попередньо онулюється (СТТ=0). Різниця [(НВ+1) – НА ] визначається подачею на вхід

прямої лічби «+1» лічильника (НВ +1) сигналів, а потім на вхід зворотної лічби «-1» НА імпульсів. Зазначимо, що у процесі лічби змінної k відбу-вається блокування операції ділення, якщо числовий вираз поточного стану лічильника набуває нульового значення, тобто за СТТ = [(НВ + 1- НА)] = 0.

Кількість імпульсів НВ і НА на входах лічильника тактів СТТ фор-мується у процесі нормалізації доповняльних кодів дільника В і діленого А , яка виконується логічним зсувом вліво кожного із операндів до появи одиничного стану ознаки нормалізації відповідного доповняльного коду:

ПНВ = NВ Å ВН (6); ПНА = NА Å АН (6), (3.195)

де ПНВ, ПНА - ознака знормованого стану доповняльного коду відповідно дільника В і діленого А ;

NА, NВ – знакові розряди відповідно дільника В і діленого А ;

, - поточний стан старших цифрових розрядів відповідно дільника і діленого.

Значущі k цифр числової частини частки D визначаються діленням знормованого доповняльного коду діленого АН на знормований код діль-ника ВН за будь-яким комп‘ютерним алгоритмом ділення доповняльних кодів. Сукупність операцій при нормуванні остачі операції ділення вико-нуються за правилами, які були визначені для операції ділення цілочислових модулів чисел однакового формату.

Приклади ділення цілочислових доповняльних кодів однакового формату А на В за алгоритмами «б» і «а» подано на рис.3.40 – 3.41.

D	А	В	CTТ	CTC
7 6 5 4 3 2 1	7 6 5 4 3 2 1	7 6 5 4 3 2 1
X XXX XXX 1 1 1 1 1 1 1 ND = NAÅNB=1 1 1 1 1 1 1 0   = NA2ÅNB=0   1 1 1 1 1 0 1 =NA1ÅNB=1 + 1   1 1 1 1 1 1 0 D	0 0 0 1 1 0 1 NA HA=2 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 NA2   1 1 0 1 1 0 0 1 1 1 1 0 0 0 NA1   0 0 1 0 1 0 0 0 0 0 1 1 0 0 HA (СТС) 0 0 0 0 0 1 1	1 1 1 1 0 1 1 NB HB=3 1 0 1 1 0 0 0 BH2DK NB ≠ NA = A2DK BH2DK 1 1 0 1 1 0 0 BH1DK NB ≠ NA2 = A1DK   NA1≠(NDÅNB)=0, NB= NA1   = C ∙2HA   = C	HB+1- -HA = =3+1-2 = 2(d2d1)	HВ=2

Рисунок 3.40 – Приклад ділення A на В за алгоритмом «б»

Вправи та запитання до розділу 3

1. Виконайте обчислення коефіцієнтів полінома частки:

МА = МВ*MD = MB(d₄·2³ + d₃·2² + d₂·2¹ + d₁·2⁰) =

= d₄ (MB·2³)+ d₃ (MB·2²)+ d₂ (MB·2¹)+ d₁ (MB·2⁰),

де МА=100 011– модуль діленого подвійного (шестирозрядного) формату;

МВ = 111 – модуль дільника одинарного (трирозрядного) формату;

d₄ – ознака переповнення гранично-припустимого формату модуля частки, обмеженого трирозрядним рядком цифр;

d₃ d₂ d₁ – послідовність цифр цілої частини гранично–припустимого трирозрядного формату частки.

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

Запропонуйте простий алгоритм і схему арифметичного пристрою для реалізації операції ділення МА(6/1) на МВ(3/1).

2. Згідно завдання 1 для визначення коефіцієнтів d₃і d₂ полінома-частки потрібно обчислити знак залишків діленого А3 і А2:

А3 = МА - d₄ (MB·2³) -(MB·2²);

А2 = МА – d_П (MB·2³) - d₃ (MB·2²) - (MB·2¹).

D	А	В	CT	CTC
7 6 5 4 3 2 1	7 6 5 4 3 2 1	7 6 5 4 3 2 1
X XXX XXX ND 1 1 1 1 1 1 1 ND = NAÅNB 1 1 1 1 1 1 0   =NA2ПÅNB=0 1 1 1 1 1 0 1 =NA1ПÅNB=1 + 1   1 1 1 1 1 1 0 D	1 1 1 0 0 1 1 NA HA=2 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 NA2П 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 NA1П   1 0 1 1 0 0 0 1 1 0 1 0 0 0 (HB=3) 1 1 1 1 1 0 1	0 0 0 0 1 0 1 NB HB=3 0 1 0 1 0 0 0 BHDK NB ≠ NA = A2ПDK   = A2ПDK BHDK NB ≠ NA2П = A1ПDK   NA1П ≠NBÅND=1 NB= NA1П   = C ∙2HB   = C	(HB+1)- -HA = =(3+1)--2 = 2 (d2d1)	HВ=3

Рисунок 3.41 – Приклад ділення A на В за алгоритмом «a»

Як побудувати рекурентні функції, за якими залишок діленоно А2 був би пов'язаний з попереднім залишком А3 за d₃ = 0 (А3<0) і d₃ = 1 (А3≥0)? Який вигляд мають такі залежності за алгоритмоми «а» і «б» з відновленням і без відновлення залишку?

3. Знайдіть сукупність операцій, за допомогою яких можна знайти остачу МС(3/1) від ділення МА(6/1) на МВ(3/1):

МА = МВ * MD + MC = MB(d₄·2³ + d₃·2² + d₂·2¹ + d₁·2⁰) + MC,

де МА = 100110, МВ = 110; МС – модуль цілочислової остачі від ділення МА на МВ.

За допомогою яких операцій можна обчислити остачу МС(3/1) з використанням останнього залишку А1 за d₁= 0 і d₁= 1?

4. Обчисліть частку МD і остачу МС від ділення МА на МВ однакового формату:

МА(6/1) = МВ(6/1) * МD(6/1) + МС(6/1),

де МА(6/1) = 010001, МВ(6/1) = 000011.

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

5. Покажіть, як виконується ділення (±МА) на (±МВ) , якщо МА=100011 і МВ = 111, тобто остача МС=0.

Запропонуйте загальний алгоритм визначення остачі = 0.

6. Найдіть частку та остачу від ділення (±МА) на (±МВ) , якщо МА=100011 і МВ=110.

Запропонуйте загальний алгоритм визначення остачі ≠ 0.

7. Розробіть приклад ділення (±МА) на (±МВ) , якщо МА=010010 і МВ = 000011.

Запропонуйте загальний алгоритм визначення припустимої кількості значущих цифр частки.

8. Які випадки блокування процедури ділення (±МА) на (±МВ) повинні фіксуватися за довільних величин операндів МА і МВ?

Наведіть приклади, за якими процедура ділення повинна перериватися.