Xreferat.com » Рефераты по коммуникации и связи » Виконання операцій множення і ділення у двійковій системі числення

Виконання операцій множення і ділення у двійковій системі числення

РЕФЕРАТ


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

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


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


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

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

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

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

Виконання операцій множення і ділення у двійковій системі числення

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

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

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


Виконання операцій множення і ділення у двійковій системі числення


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


Виконання операцій множення і ділення у двійковій системі числення


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

Найпростіше множення виконується у прямому коді. У разі представлення чисел з фіксованою комою воно реалізується у два етапи. На першому етапі визначається знак добутку шляхом додавання за модулем два цифр знакових розрядів співмножників (див. табл. 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. Після завершення п-го циклу утворюється остаточний результат множення Виконання операцій множення і ділення у двійковій системі числення.


Таблиця 3.2 - Приклад множення за методом 1

Виконання операцій множення і ділення у двійковій системі числення


Для реалізації даного методу множення потрібні (рис.3.2) 2п-розрядний регістр множеного РгА з колами для зсуву вправо, п-розрядний регістр множника РгВ з колами для зсуву вліво, 2п схем І і 2п-розрядний нагромаджувальний суматор НСМ. Тут чергова цифра множника, що керує додаванням часткових добутків, береться зі старшого розряду регістра множника.

Час множення за даним методом дорівнює:

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


Виконання операцій множення і ділення у двійковій системі числення


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


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

Розв'язання. Для даних чисел маємо: Виконання операцій множення і ділення у двійковій системі числення=1; Виконання операцій множення і ділення у двійковій системі числення = 0, 10100; Виконання операцій множення і ділення у двійковій системі числення=1; Виконання операцій множення і ділення у двійковій системі числення = 0, 10011. Визначаємо знак добутку: Виконання операцій множення і ділення у двійковій системі числення=1Виконання операцій множення і ділення у двійковій системі числення1=0. Усі дії, що виконуються під час множення, наведені у табл. 3.3.

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

Метод 3. Перетворимо (3.1) за схемою Горнера для обчислення поліномів:

Виконання операцій множення і ділення у двійковій системі числення=

=Виконання операцій множення і ділення у двійковій системі числення.

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

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

Таблиця 3.3 - Приклад множення за методом 2

Виконання операцій множення і ділення у двійковій системі числення


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

Для реалізації даного методу множення потрібні (рис.3.3) п-розрядний регістр множеного РгА, п-розрядний регістр множника РгВ з колами для зсуву вліво, п схем І і (2п+1)-розрядний нагромаджувальний суматор НСМ з колами для зсуву вправо. Тут множене завжди додається до п старших розрядів суми часткових добутків. Один додатковий розряд ліворуч у НСМ необхідний для запам'ятовування цифри переповнення, що може виникнути в процесі додавання; під час наступного зсуву ця цифра піде в старший з основних розрядів нагромаджувального суматора, так що в остаточному результаті переповнення не буде.


Виконання операцій множення і ділення у двійковій системі числення


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


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

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

Приклад 3.4. Помножити числа А = 0, 11100 і В = 0, 10011, використовуючи метод 3.

Розв'язання. Для даних чисел маємо: Виконання операцій множення і ділення у двійковій системі числення=0; Виконання операцій множення і ділення у двійковій системі числення = 0, 11100; Виконання операцій множення і ділення у двійковій системі числення=0; Виконання операцій множення і ділення у двійковій системі числення = 0, 10011. Визначаємо знак добутку: Виконання операцій множення і ділення у двійковій системі числення=0Виконання операцій множення і ділення у двійковій системі числення0=0. Послідовність дій, що виконуються для одержання модулю добутку, показано в табл. 3.4.

Таблиця 3.4 - Приклад множення за методом 3

Виконання операцій множення і ділення у двійковій системі числення


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


Особливість даного методу множення полягає в тому, що в кожному циклі визначається одна вірогідна цифра добутку (починаючи з наймолодшого розряду), яка не змінюється в інших циклах множення. Врахування цього дозволяє зменшити кількість розрядів нагромаджувального суматора вдвічі, обчислюючи 2п-розрядний добуток. При цьому для зберігання вірогідних цифр використовуються розряди регістра множника, що звільняються в процесі множення. Структурна схема такого пристрою для множення наведена на рис. 3.4. Тут вихід молодшого розряду нагромаджувального суматора НСМ з'єднаний з входом старшого розряду

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: