3.3.2. Логічні методи прискорення операції множення
в двійковій системі числення
До логічних методiв прискорення операції множення належать: метод множення з пропусканням додавань у тих випадках, коли чергова цифра множнику є нуль; метод множення з перетворенням цифр множнику шляхом групування розрядiв i метод множення з послідовним перетворенням цифр множника.
В основi
двох останніх логічних методiв
лежить перехід до надлишкової двійкової
системи числення з алфавітом {1,
0,
},
який дозволяє зменшити кількість
одиниць у коді множника, але при цьому
в процесi
множення будуть виконуватись операції
додавання та віднімання.
Метод множення з пропусканням додавань є найпростішим з логічних методів прискорення множення. Схему керування взагалі простіше побудувати так, щоб за тактом зсуву щораз приділявся час на додавання, але додавання виконувалося б у залежності від цифри множника. Невелике ускладнення схеми керування, що дозволяє відводити час на додавання тільки тоді, коли воно дійсно необхідно, скорочує число тактів додавання в середньому вдвічі. Час множення за таким методом прискорення дорівнює:
.
Цей метод прискорення рівною мірою підходить для тих випадків, коли множення починається зі старших розрядів множника, і для випадків, коли множення починається з молодших розрядів.
Приклад 3.11. Помножити числа А = - 0, 10100 і В = 0, 10011, використовуючи метод множення з пропусканням додавань.
Розв'язання. Для даних чисел маємо: =1; = 0, 10100; =0; = 0, 10011. Визначаємо знак добутку: =1 0=1.
Усі дії, що виконуються в кожному циклі множення, наведені табл. 3.13.
Відповідь: С= - 0, 0101111100.
Таблиця 3.13 - Приклад множення за прискореним методом
Розглянемо тепер метод множення з перетворенням цифр множнику шляхом групування розрядiв.
Кількість циклів, що необхідні для реалізації операції множення, можна скоротити, якщо в кожному циклі аналізувати не один, а два або більше розрядів множнику, виконуючи після аналізу додавання або віднімання та зсув множнику на відповідну кількість розрядів (два або більше). Для організації прискореного множення множник розбивають на групи з двох розрядів і перетворюють його таким чином, щоб кожна група містила не більш одної значущої одиниці (додатної або від'ємної).
Правила перетворення множника з молодших розрядiв у разі групування по два розряди формулюються, враховуючи таке.
Комбінації 00, 01, 10 не перетворюються, а комбінація 11 замінюється комбінацією 1.0 , яка містить від'ємну одиницю в даній групі розрядів і додатну одиницю, що передається до наступної групи розрядів множника.
З урахуванням одиниці, що передається з попередньої групи розрядів, у даній групі розрядів після перетворення може зустрітися одна з таких комбінацій:
00 - якщо дана група розрядів містить цифри 00 і з попередньої групи одиниця не передається або якщо дана група розрядів містить цифри 11 і одиниця передається з попередньої групи розрядів;
01 - якщо дана група містить цифри 01 і з попередньої групи одиниця не передається, або якщо дана група розрядів містить 00 і передається одиниця з попередньої групи розрядів;
10 - якщо дана група містить 10 і нема одиниці з попередньої групи або якщо дана група містить 01 і є одиниця з попередньої групи розрядів;
0 - якщо дана група розрядів містить 11 і нема одиниці з попередньої групи або якщо дана група містить 10 і є одиниця з попередньої групи.
Із
сказаного випливають правила перетворенням
множнику, починаючи з молодших груп
розрядів, що наведені в табл. 3.14. Тут
- цифри даної групи розрядів;
- цифра, що передається з попередньої
групи;
- перетворені цифри даної групи;
- цифра, що передається в наступну групу.
Таблиця 3.14 - Правила перетворенням множнику, починаючи з
молодших груп розрядів
-
0 0
0
0 0
0
0 0
1
0 1
0
0 1
0
0 1
0
0 1
1
1 0
0
1 0
0
1 0
0
1 0
1
0
1
1 1
0
0
1
1 1
1
0 0
1
Застосовуючи ці правила необхідно враховувати, що старша значуща цифра перетвореного множника може знаходитися в розряді цілих, де неперетворений множник містить завжди нуль.
Приклад 3.12. Використовуючи групування розрядів, виконати перетворення множнику 001011111001100111, починаючи з молодших розрядів.
Розв'язання. Діючи за правилами, що наведені в табл. 3.14, одержимо
0 0 |
1 0 |
1 1 |
1 1 |
1 0 |
0 1 |
1 0 |
0 1 |
1 1 |
+1 |
+1 |
+1 |
+0 |
+0 |
+0 |
+0 |
+1 |
|
0 1 |
0
|
0 0 |
0 |
1 0 |
0 1 |
1 0 |
1 0 |
0 |
Замість 11 одиниць у вихідному представленні множника одержуємо 8 додатних і від'ємних одиниць у перетвореному.
Відповідь: 010 000 100110100 .
Коли одразу аналізуються два розряди перетвореного множнику, то в процесі множення виконуються такі дії.
Якщо група містить комбінацію 00, то це означає, що протягом двох найближчих циклів множення не потрібно буде виконувати ні додавань, ні віднімань; при наявності комбінації 01 потрібно буде виконати одне додавання в першому з двох найближчих циклів множення, а у разі комбінації 10 - у другому. Коли група містить комбінацію 0 , то буде потрібно виконати одне віднімання в першому з двох найближчих циклів множення.
У разі одночасного аналізу двох розрядів, починаючи зі старших, у правилах перетворення груп розрядів (табл. 3.15) враховується значення сусіднього розряду, що розташований праворуч від групи, яка аналізується. При цьому аналіз розрядів множника завжди починається з пустої групи, що дописується ліворуч від найстаршого розряду.
Приклад 3.13. Використовуючи групування розрядів, виконати перетворення множнику 001011111001100111, починаючи зі старших розрядів.
Розв'язання. Діючи за правилами, що наведені в табл. 3.15, одержимо
Замість 11 одиниць у вихідному представленні множника одержуємо 7 додатних і від'ємних одиниць у перетвореному.
Відповідь: 010 0000 010 0100 .
Той чи інший метод перетворення тим ефективніше, чим менше в перетвореному множнику середня кількість додатних і від'ємних одиниць, тобто чим менше в середньому потрібно додавань і віднімань. Важлива також максимальна кількість додавань і віднімань, що можуть виконуватись під час множення.
Таблиця 3.15 - Правила перетворення множнику,
починаючи зі старших груп розрядів
-
0 0
0
0 0
0 0
1
0 1
0 1
0
0 1
0 1
1
1 0
1 0
0
0
1 0
1
0
1 1
0
0
1 1
1
0 0
Для оцінки ефективності описаного вище методу групування розрядів відзначимо насамперед, що для будь-якої комбінації цифр протягом двох циклів множення може бути не більш одного додавання або віднімання. Таким чином, в гіршому випадку кількість додавань-віднімань дорівнює 0,5п.
Середня кількість додавань-віднімань дорівнює 0,375п. З урахуванням цього середній час множення складає:
- для першого і другого методів множення
;
- для третього і четвертого методів множення
.
Метод множення з послідовним перетворенням цифр множника передбачає послідовний аналіз цифр множника без розбиття на групи. При цьому використовується такі правила перетворення:
- якщо дана цифра неперетвореного множника не збігається із сусідньою праворуч цифрою, сусідня ліворуч цифра є 0 і попередня цифра перетвореного множника є 0, то даний розряд у перетвореному множнику є 1;
- якщо дана цифра неперетвореного множника не збігається із сусідньою праворуч цифрою, сусідня ліворуч цифра є 1 і попередня цифра перетвореного множника є 0, то даний розряд перетвореного множника повинний містити ;
- якщо дана цифра неперетвореного множника збігається із сусідньої праворуч цифрою або якщо попередня цифра перетвореного множника не є нулем, то даний розряд у перетвореному множнику є 0.
Застосовуючи ці правила необхідно враховувати, що старша значуща цифра перетвореного множника може знаходитися в розряді цілих; праворуч і ліворуч від значущих розрядів перетвореного множника завжди передбачаються нулі. Коли в приведеному правилі говориться про "попередні" цифри перетвореного множника, то стосовно до множення від молодших розрядів це відноситься до попередньої молодшої цифри перетвореного множника, а стосовно до множення від старших - до старшої попередньої цифри.
Описане послідовне перетворення розрядів множнику забезпечує під час множення в середньому 0,333п додавань-віднімань. Це найкращий результат, що може бути отриманий для логічних методів прискорення множення.
У здійсненні метод послідовних перетворень ненабагато складніше, ніж метод групування розрядів множника, ефективність же його вище.
При цьому виникають визначеної довжини послідовності чи нулів одиниць, що приводить до необхідності одночасного аналізу декількох розрядів множника і зрушенню на довільне число розрядів.