Множення чисел на ДСОК при негативному множнику

Доказ. Нехай А=[A]_об і В<0, тоді ; відповідно до подання у ФРК, фіксовано перед старшим розрядом |B|+[B]_об=q-q^-n=2-2^-n; звідси [В]_об=2+В-2^-n; тож,+ 2^-n-1, добуток дорівнює: А×В =A_об×+[A]_об× (-2^-n)+; є два виправлення: перше [A]_об×(-2^-n) порівняне мале (тому часто ігнорується) і друге +.

Алгоритм. Множення на ДСОК (при В<0) виконується в наступній послідовності (наведена в таблиці 13.2):

- у суматор записуються 11.111...1 (машинний нуль оберненого коду);

- у регістр В записується множник у оберненому коді (без знака);

- у суматор додається множене у оберненому коді А_об;

- ведеться аналіз розрядів РгВ (починаючи з молодшого), і якщо там «1» («0»), то до вмісту суматора додається (нічого не додається) обернений код множеного;

- після циклу додавання і аналізу робиться зсув вправо вмісту суматора і РгВ на один розряд (можна з переносом молодших розрядів суматора в старші розряди РгВ);

- після аналізу і зсуву старшого розряду множника до результату додають виправлення [] - інверсію А_об, включаючи і знак;

- якщо знак результату негативний, то він у оберненому коді і необхідне перетворення у прямий код;

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

Приклад. Метод 2, множення чисел на ДСОК. А=-0/110101; В=-0/101000; А×В=+2120. Рішення: Запишемо машинне зображення чисел.

А^м_об = 11/001010; В^м_об = 11/010111; = 00/110101.

Послідовність виконання операції множення наведена в таблиці 13.2.

З урахуванням розрядів РгВ будемо мати 100100001000111. Переповнення «1» із знакового розряду Sg₁ додається до молодшого розряду числа. Тоді, одержимо відповідь: С_пр=00100001001000=2120₍₁₀₎.

Існує ряд методів множення заснованих на роздільному під-сумковуванні груп часткових доданків з наступним об’єднанням сум з урахуванням переносів. Роздільна обробка проміжних сум і переносів вимагає так званого "дерева суматорів" (використано в IBM-360).

Таблиця 13.2 - Множення на ДСОК при негативному множнику

Існують також прискорені методи множення, засновані на використанні матриць проміжних результатів. Розглянемо схему множення:

A = a₅, a₄, а₃, а₂, a₁

*B = b₅, b₄, b₃, b₂, b₁

a₅b₁ а₄b₁ а₃b₁ а₂b₁ а₁b₁

+.........................................

а₅b₅ а₄b₅ а₃b₅ а₂b₅ а₁b₅

С₁₀ С₉.......................С₂ С₁

Цю схему можна представити також у вигляді матриці таблиці 13.3. Кожний елемент цієї матриці дорівнює "0" або "1".

Таблиця 13.3 Матричне множення чисел

Добуток двох чисел можна одержати, якщо підсумувати елементи матриці в діагональному порядку. Cкладати доводиться тільки 0 або 1, тому операцію додавання можна виконувати за допомогою напівсуматорів і суматорів на один двійковий розряд.

Рисунок 13.1 - Структурна схема пристрою множення для реалізації матричного алгоритму

Рисунок 13.2 - Схема множного пристрою за алгоритмом Дадда

Найбільше поширення одержали алгоритми Дадда, Уоллеса (матричний) і алгоритм збереження переносів [1-21]. На рис. 13.1 представлена структурна схема матричного пристрою множення для реалізації матричного алгоритму.

Алгоритми відрізняються друг від друга групуванням часткових добут-ків, кількістю етапів перетворень. Для матричного алгоритму - чотири етапи перетворення, для алгоритму Дадда – три етапи. Однак, матричні методи множення, незважаючи на більший об’єм устаткування, дають великий виграш часу, а використання ВІС значно знижує обмеження на устаткування.

Розглянуті методи множення знайшли широке застосування в практиці бінарної арифметики.

14 ДІЛЕННЯ БІНАРНИХ ЧИСЕЛ

14.1 Методи ділення бінарних чисел

Найбільше поширення одержали наступні методи виконання операції ділення чисел:

1. На кожному кроці з діленого віднімається дільник (починаючи зі старших розрядів) стільки разів, скільки це можливо до одержання залишку менше дільника. У частці записується цифра, рівна числу цілих частин дільника N. L - залишок. A: B= N×B+L

2. Інший метод ділення полягає в множенні діленого на обернену величину З=А:В=А×В^-1=А×1/В.

Тут виникає проблема знаходження обернених величин шляхом розкладання в біноминальний ряд Ньютона, використовуючи модель розкладання бінома ступеня m:

де C^k_m - біномінальні коефіцієнти число різних сполучень із m різних змінних по k у кожному сполученні:

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

Перший розглянутий метод відносять до “шкільних” алгоритмів ділення з відновленням залишку. Розглянемо приклад розподілу в бінарній арифметиці.

14.1.1 Алгоритм ділення з відновленням залишку

Формально алгоритм описується в такий спосіб. Нехай А - ділене, В - дільник, С - частка: A=0,α₁α_2...α_n; B=0,b₁b₂...b_m, C=0,c₁c₂...c_r.

На кожному кроці визначається залишок А_i=A_i-1-B×2^-i, проводиться аналіз: якщо залишок А_i>0, то в старший розряд частки записується C_i=l, робиться лівий зсув і перехід до визначення наступного залишку. Якщо A_i<0, то С_i=0 і відновлюється залишок A_i=A_i-1+B×2^-i, а на наступному кроці після зсуву визначається новий залишок і т.д.

Даний алгоритм ділення з відновленням залишку реалізується на двійкових суматорах оберненого (ДСОК) або доповняльного (ДСДК) кодів. Структурна схема наведена на рис. 14.1.

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

Рисунок 14.1 - Структурна схема ЦА операції ділення

14.2 Ділення чисел з фіксованою комою з відновленням залишку

Ділення виконується за алгоритмом із відновленням залишку на суматорі доповняльного коду (ДСДК) у наступній послідовності:

- визначається знак частки по формулі Sg_С=Sg_АÅSg_В;

- проводиться подання діленого і дільника в машинних кодах, коли ділене завжди, незалежно від його знака, береться в прямому коді з позитивним знаком, а дільник завжди, незалежно від його знака, береться у доповняльному коді з негативним знаком;

- усунення дробової частини в дільнику, шляхом переносу коми вправо на n розрядів (за аналогією з десятковою системою числення). Щоб дріб не змінився, у діленому також переносять вправо кому на n розрядів;

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

1) якщо знак проміжного залишку 00 (позитивний), то в регістр частки РгС записується 1, починаючи зі старшого розряду. Залишок зсувається на один розряд вліво (просто знакову крапку перенести вправо на один розряд), зноситься наступний розряд діленого (що не брав участь до цього в ділені). Після цього, проміжний залишок підготовлений до наступного додатка діленого у доповняльному коді;

2) якщо знак проміжного залишку 11 (негативний), то в регістр частки РгС записується 0, починаючи зі старшого розряду. Залишок відновлюється шляхом додатка до нього дільника в прямому коді з позитивним знаком. Відновлений залишок зсувається вліво на один розряд (крапку, що відокремлює знак, перенести вправо на один розряд), зноситься наступний розряд діленого (що не брав участь до цього в ділені). Після цього, проміжний залишок підготовлений до наступного додатка дільника у доповняльному коді;

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

- результат ділення представлений у регістрі частки С в прямому коді.

Знак результату привласнюється відповідно до пункту 1.

Приклад. Розділити число А= -100111(-39) на В= -11(-3), представлених у (ФФЗ) . Розрядність суматора і регістрів дорівнює 6.

Рішення: Операція робиться на ДСДК (модифікований код) за алгоритмом із відновленням залишку.

1. Визначаємо знак частки: Sg_С=Sg_АÅSg_В =1Å1=0. Знак позитивний.

2. Записуємо машинні зображення чисел: А^м_пр=00/100111; В^м_пр=11/11; В^м_доп=11/01;

3. Виконуємо послідовність дій над числами за методом алгоритму з відновленням залишку (таблиця 14.1).

Примітка: ДСДК не використовує перенос П_Sg1 при переповненні суматора старшого розряду знака (див. рис. 8.1).

Відповідь: С_пр=11/01101 (-13).

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

Таблиця 14.1 - Приклад ділення чисел А на В з відновленням залишку

Відповідь: С_пр=11/01101 (-13).

15 ДІЛЕННЯ ЧИСЕЛ З ФІКСОВАНОЮ КОМОЮ БЕЗ ВІДНОВЛЕННЯ ЗАЛИШКУ

Аналізуючи попередній алгоритм, бачимо, що у випадку, коли C_i - чергова цифра частки дорівнює "0", то проводиться відновлення залишку по формулі A_i-1 = A_i + В×2^-i (на і-му кроці алгоритм ділення A_i = A_i-1 - В×2^-i, де A_i-1 - попередній залишок, A_i - поточний залишок). Відновлений залишок приймається за A’_i і процес ділення триває, тобто:

А_i+1=А’_i - B×2^-(i+1) =(A_i+В×2^-i)-B×2^-(i+1)

Перетворюючи цей вираз, одержимо:

A_і+1=A_i+B×2^{-(i+ 1)} . (15.1)

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

15.1 Алгоритм ділення без відновлення залишку

Метод ділення бінарних чисел без відновлення проміжних залишків виконується в послідовності:

- визначити знак частки за формулою: Sg_С=Sg_АÅSg_В;

- представити числа (операнди) у доповняльному коді в машинному зображенні, ділене (завжди), незалежно від його знака, береться в прямому коді з позитивним знаком, а дільник (завжди), незалежно від його знака, береться в доповняльному коді з негативним знаком;

- привласнити суматору значення См:=А^м_доп ; РгВ:=B^м_дoп; РгС:=0;

- усунути дробову частину в дільнику, переносячи кому вправо на n розрядів (за аналогією з десятковою системою числення) і, щоб дріб не змінився, у діленому також перенести вправо кому на n розрядів;

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

1) якщо знак проміжного залишку 00 (позитивний), то в регістр частки РгС записується 1, починаючи зі старшого розряду. Залишок зсувається на один розряд вліво (знакову крапку перенести вправо на один розряд), зноситься наступний розряд діленого, що не брав участі до цього в діленні. Після цього, проміжний залишок підготовлений до наступного додатка діленого у доповняльному коді;

2) якщо знак проміжного залишку 11 (негативний), то в регістр частки РгС записується 0, починаючи зі старшого розряду. Залишок зсувається на один розряд вліво (знакову крапку перенести вправо на один розряд), зноситься наступний розряд діленого, що не брав участі до цього в діленні. Після цього, проміжний залишок підготовлений до наступного додавання до нього дільника в прямому коді зі знаком 00;

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

- знак результату привласнюється відповідно до пункту 1. Результат ділення представлений у регістрі частки в прямому коді.

Приклад 1. Розділити на ДСДК числа (ФФЗ): А=16,25₍₁₀₎; В=-3,25₍₁₀₎

Рішення: виконуємо ділення методом без відновлення залишку.

- визначаємо знак частки С: Sg₀С=0 Å 1=1. У старші розряди регістра частки С заносимо значення негативного знака 11/;

- встановлюємо регістри РгА, РгВ і См у нульовий стан, очистивши їх від попередньої інформації;

- переводимо десяткові числа в бінарні, прямі і доповняльні коди (п.15.1):

А_пр=0010000,01 (+16,25); В_пр=1111,01 (-3,25); В^м_доп=110,11; В_пр.від.=0011,01. Для вирахування використаємо В^м_доп=110,11. Для дільника в прямому коді зі знаком «+» беремо В^м_пр=0011,01. (Щоб провести ділення з операндами А і В, як з цілими числами, перенесемо зап`яту на два розряди вліво в А і В).

Для порівняння кількості кроків при виконанні операції ділення проведіть самостійно операцію ділення на ДСДК вказаних чисел А= +16,25₍₁₀₎ і В= -3,25₍₁₀₎ за алгоритмом без відновлення залишку.

15.2 Ділення чисел з рухомою комою

При діленні чисел представлених у ФРК, ділення виконують над мантиссою m_С=m_А/m_В, а порядки віднімаються:

Р_С=Р_А-Р_B (15.2)

При цьому можливі два випадки:

- мантиса |m_А|≥ |m_B|;

- мантиса |m_А|<|m_B|.

Розподіл мантис виробляється в такому ж порядку, як і у форматі з фіксованою комою. При цьому, використаються методи з відновленням і без відновлення залишку. Результату привласнюється порядок Р_С.

Примітка. В алгоритмах ділення застосовується правило: на першому кроці підготовки операндів А і В до ділення робиться так, щоб ½А½ завжди було менше ½В½ (тимчасово змінюючи вимогу нормалізації операнда А і, відповідно, корегуючи значення порядка Р на +1) для того, щоб при першому кроці операції ділення не було переповнення молодшого знакового розряду Sg₂: порівняйте дії над нормалізованими двійковими операндами, наданими у ФРК: А=+0,101^.2⁺¹ і В=+0,101^.2⁺¹:

а) ділене А^м_пр=00,101001; дільник В^м_пр= 00,101001; частка С^м_пр=01,000000- отримали ненормоване число і переповнення знакового розряду (тоді, згідно вимог g і δ, треба робити зсув на першому же кроці алгоритму ділення, що затримує процес у часі);

б) ділене А^м_пр=00,0101010; дільник В^м_пр=00,101001; частка С^м_пр= 00,100001-отримали нормоване число С автоматично без переповнення знакового розряду Sg₂, бо вибрано½А½<½В, (ф-ла 15.2).

6 БІНАРНО – КОДОВАНІ ДЕСЯТКОВІ СИСТЕМИ ЧИСЛЕННЯ

16.1 Загальні вимоги до БКДС

Візьмемо будь-яке десяткове число, наприклад, 689 і представимо кожний його розряд у бінарній (двійковій) системі числення. Тоді, 689=0110.1000.1001. Якщо кожний десятковий розряд представляти бінарною тетрадою (чотири молодших розряди цілих двійкових чисел), то будь-яке десяткове число буде представлене в бінарно-кодованій десятковій системі числення (БКДС). Узагальнюючи приклад для будь-якої системи числення, можна сказати, що будь-яке число А, представлене цифрами з основою В ¹ 2^k, може бути записане в бінарно-кодованій системі числення (БКС) як:

А_БКС = ±Σ_і(Σ_ℓd_ℓq_ℓ)×В^р-1,

де d – бінарні розряди; q – вага кожного бінарного розряду. Вираз в дужках представляє ℓ-й розряд числа А, вага якого В, у свою чергу залежить від місця розташування в числі В^р-1.

На практиці в інформаційних системах найбільш широке поши-рення одержали БКДС (основні їх типи представлені в таблиці 16.1).

Взагалі, можна знайти багато варіантів і способів кодування десяткових чисел. Однак, для того щоб у БКДС можна було виконувати арифметичні операції, ефективно проводити кодування - декодування, необхідно, щоб вони відповідали ряду основних вимог: