2. Построение специализированных схем Два варианта быстрых схем

1). Аппаратное умножение

P_i+1 = P_i + A2b_i+1

См. Угрюмов «Элементы и узлы ЦЭВМ»

Если не хотим задержку для регистра, за каждой операцией умножения закрепляем сумматор.

A

b₀

B

b₁

И

И

b₂

И

b₃

И

 - задержка на каждом сумматоре

(2n-1) - время на умножение двух n-разрядных чисел

в результате умножение происходит примерно в два раза медленнее, чем обычное сложение ( )

Для построения быстрого устройства умножения используется методика закрепления – за каждой операцией закрепляется свое устройство

2). Табличный способ

Аргумент	Функция
00…000
00…001
00…010
………

Аргумент линейно возрастает

Значение аргумента совпадает с номером строки – хорошая таблица

Аргумент – адрес

Значение функции – то значение, которое хранится по адресу

ЗУ

аргумент

функция

(значение)

(адрес)

Такая организация каких-либо операций – это основа таблично-алгоритмических методов Память (зу) не является памятью автомата

ЗУ, которое в течение работы не меняет своего значения – это КС (комбинационная схема); если память меняет свое значение, то это память автомата.

Рассмотрим таблицу, в которой приводится объем памяти ЗУ для хранения результатов операции умножения двух чисел;

n – разрядность множимого и множителя

2n – разрядность произведения

№	n	V1	V2	V3
1	8	64Kб  16р	256 б  16р	16 б  8р
2	16	4Гб  32р	64 Кб  32р	256 б  16р
3	32	234Гб  64р	4 Гб  64р	64 Кб  32р

1 – перемножаются 8-ми разрядные числа

2 – перемножаются 16-ти разрядные числа

3 – перемножаются 32-х разрядные числа

V₁ – обычное умножение; имеется 2ⁿ множимых 2ⁿ множителей, в итоге количество результатов 2ⁿ 2ⁿn

Например, умножаются два 16-ти разрядных числа

2¹⁶*2¹⁶ – количество результатов операции умножения

16 – разрядность результата

2¹⁶*2¹⁶*16 бит  32р = 2³⁰*2²  32р = 4 Гб  32р будет занимать таблица результатов

Попытаемся уменьшить объем таблицы

V₂ рассмотрим вычисление меньшего объема

(A – B)² = A² + B² – 2·A·B квадрат разности

т.е. произведение двух чисел можно представить в виде

Умножение при наличии таблицы квадратов можно осуществить примерно за 6 тактов

Например, умножаются два 8-ми разрядных числа

2⁸ – возможное количество результатов операции умножения

2⁸*16р = 256  16р будет занимать таблица результатов

V₃ рассмотрим вычисление меньшего объема