Смекни!
smekni.com

Виконання операцій множення і ділення у двійковій системі числення (стр. 1 из 9)

РЕФЕРАТ

на тему:”ВИКОНАННЯ ОПЕРАЦІЙ МНОЖЕННЯ І ДІЛЕННЯ В ДВІЙКОВІЙ СИСТЕМІ ЧИСЛЕННЯ ”


ВИКОНАННЯ ОПЕРАЦІЙ МНОЖЕННЯ І ДІЛЕННЯ В ДВІЙКОВІЙ СИСТЕМІ ЧИСЛЕННЯ

1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ОПЕРАЦІЮ МНОЖЕННЯ

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

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

(і = 0, 1, 2, .., k) і
А доти, поки не буде виконана умова 2k+l >В. Значення С визначають як суму тих часткових добутків
А, для яких
входить до представлення числа В. Хоча в цьому способі використовуються елементи двійкового множення, числа А и В представляються в системі числення з довільною основою р >2.

Приклад 3.1. Помножити числа А = 25 і В = 43.

Розв'язання. Складаються три стовпчики. В лівому стовпчику розташовуються степені двійки, де зірочками позначені ті числа, з яких складається число В = 43. У середньому стовпчику перше число дорівнює А, а кожне наступне є подвоєним попереднім числом. У правому стовпчику знаходяться часткові добутки, що відповідають поміченим числам лівого стовпчику. Результат множення утворюється додаванням чисел правого стовпчику.

Відповідь: С = 1075.

Найвідомішим є "шкільний" метод множення в стовпчик. Для двійкової системи числення він має два варіанти.

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

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

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

Найпростіше множення виконується у прямому коді. У разі представлення чисел з фіксованою комою воно реалізується у два етапи. На першому етапі визначається знак добутку шляхом додавання за модулем два цифр знакових розрядів співмножників (див. табл. 3.1). На другому етапі здійснюється множення модулів співмножників, потім, у разі потреби, округлення модуля добутку, після чого до модуля результату дописується його знак, що визначений на першому етапі. Множення цифр розрядів співмножників виконується згідно таблиці двійкового множення, що наведена у параграфі 2.1.

Таблиця 3.1 - Правила визначення знаку добутку

Обчислення вручну Обчислення в машині

3.2. МНОЖЕННЯ ЧИСЕЛ, ЩО ПРЕДСТАВЛЕНІ В ФОРМІ З ФІКСОВАНОЮ КОМОЮ

3.2.1. Прості методи множення

Нехай

- модуль множеного,
- модуль множника. Тоді, у разі представлення чисел у формi з фіксованою комою, модуль добутку
визначається за формулою:

. (3.1)

Звідси випливає, що процес множення полягає у нагромадженні часткових добутків

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

З урахуванням цього розглянемо прості методи множення.

Метод 1. Перетворимо формулу (3.1) до такого вигляду:

.

Звідси випливає, що множення зводиться до п-кратного виконання циклу:

,

де

,

для початкових значень

.

Це означає, що множення починається з молодших розрядiв множника

i множене зсувається вліво на один розряд
в кожному циклi. При цьому до суми часткових добутків
додається або зсунене множене, якщо
=1, або нуль, коли
=0. Після завершення п-го циклу утворюється остаточний результат множення. Тобто

.

Реалізація даного методу вимагає (рис. 3.1) 2п-розрядного зсувового регістру множеного РгА, п-розрядного зсувового регістру множнику РгВ, 2п схем І, що пропускають код із виходу регістра РгА на вхід 2п-розрядного нагромаджувального суматора НСМ коли

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

Оскільки зсув кодів у регістрах РгА і РгВ може виконуватись одночасно з додаванням у нагромаджувальному суматорі НСМ, то час множення п-розрядних кодів за даним методом дорівнює:

. (3.2)

Тут ураховано те, що в машинах завжди час додавання

більше, ніж час зсуву коду
.

Рис. 3.1. Структурна схема пристрою, що реалізує множення за методом 1

Приклад 3.2. Помножити числа А = - 0, 10100 і В = 0, 10011, використовуючи метод 1.

Розв'язання. Для даних чисел маємо:

=1;
= 0, 10100;
=0;
= 0, 10011. Визначаємо знак добутку:
=1
0=1.

Усі дії, що виконуються в кожному циклі множення, зручно подати у вигляді таблиці (табл. 3.2).

Відповідь: С= - 0, 0101111100.

Метод 2. Представимо (3.1) у вигляді:

.

Обчислення добутку за цією формулою зводиться до п-кратного виконання циклу:

;

для початкових значень

.

Звідси випливає, що множення починається зі старших розрядiв множника

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