Прискорення операції множення. Аналіз двох розрядів множника одночасно.

Розбиття множника на групи довжиною k розрядів означає перехід до нової системи числення з основою 2^k. Якщо при цьому вдається скоротити кількість елементарних дій, виконуваних при множенні (додавання і зсуву), то скорочується час множення. Зупинимося більш докладно на прикладі множення на два розряди одночасно (k = 2).

Можливі чотири випадки поєднання розрядів множника: 00, 01, 10, 11. Множення на кожну з пар розрядів множника повинно виконуватися за один такт автоматного часу, тобто в кожному такті множення повинно виконуватися не більш одного додавання. Розглянемо множення на ці пари на прикладі алгоритму А.

У разі пари 00 необхідно виконати тільки зсув часткової суми на два розряди - ^.

Для пари 01 виконується додавання множимого в суматор з подальшим зсувом суми на два розряди - ^,

За наявності пари 10 можливі такі варіанти дій:

a) ^, тобто в цьому випадку відбуваються два складання, що суперечить вимозі;

б) ^, в цьому випадку потрібен додатковий регістр для зберігання подвоєного Мн;

в) ^, що відповідає додаванню до часткової сумі зрушеного на один розряд вліво множимо;

г) ^, тобто часткова сума зсувається на один розряд вправо до і після додавання до неї множимо.

При множенні на пару 11 (до часткової сумі необхідно додати утроенное множене) її можна представити у вигляді: 11 = (2 ² - 1)

М _Н ∙ 11 = М _Н ∙ (2² ‒1) = М _Н ∙ 2² ‒ М_Н, тобто в поточному такті до часткової суми додається множене, взяте зі знаком мінус. Додавання М _Н ∙ 2² реалізується шляхом збільшення на одиницю наступної старшої пари розрядів.

У наведеній нижче таблиці 2.1 представлені правила перетворення множника для системи (0, ,1).

Таблиця 2.1 - правила перетворення множника

Аналізована пара розрядів Мт	Перенесення з попередньої пари	Перетворена пара	Перенесення в старшу пару
		0
		0

Приклад: Мн = 0101
Мт = 11000111
Мт ^п = 0101001001

Множення будемо здійснювати згідно з алгоритмом А [1] – зсувом суми часткових добутків.
[- Мн] _дод = 1.1011
2 Мн = 0.1010
0.0000
+ 1.1011 = -Mн
1.1011
1. 11 11 10 ∙ 2^-2
+ 0.1010 = 2Mн
0.1000 11
0. 00 10 0011 ∙ 2^-2
0. 00 00 100011 ∙ 2^-2 ( ∙ 2^-4 так как )
+ 1.1011 = -Mн
1.1011 100011
1. 11 10 11100011 ∙ 2^-2
0.0101 = Mн
0.0011 11100011

Час множення на два розряди одночасно.

Поява будь-який з розглянутих пар множників рівноймовірно. Отже, час множення на два розряди множника може бути виражене таким співвідношенням: _, де n - кількість розрядів множника.
Практичні завдання

9. Перевести вісімкове число А₈ = 326 в трійкову систему числення.

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

Не нашли, что искали? Воспользуйтесь поиском: