Устройство умножения двоичных чисел

Q(q_(0,) q_1,…〖,q〗_(n+m-1)). Каждый разряд произведения является логической функцией аргументов〖 а〗_(0,) а_(1,)…,а_(n-1 )и b_(0,) b_(1,) 〖…,b〗_(m-1) , значение которого можно найти из таблиц умножение либо путём выполнения умножения для заданных значений аргументов. Однако прямой логический синтез схемы умножителя, основанный на представлении функции выражениями в булевой алгебре , ввиду громоздкости неэффективности. Исключения составляют простейшие случаи перемножения одноразрядных или двухразрядных двоичных чисел. Поэтому на практике используют метод синтеза , основанный на разложении операции умножения на последовательность простейших арифметических действий с одноразрядными числами .

Пологая , что в двоичном представлении значение числа А и В определяются выражениями :

А=∑_(j=0)^(n-1)▒a_(i ) 2^i, (2.1)

B=∑_(j=0)^(m-1)▒a_(i ) 2^i, (2.2)

произведение Q=A×B можно записать в форме двоичной суммы:

Q=∑_(j=0)^(n-1)▒2^i ∑_(j=0)^(n-1)▒〖a_(i ) b_j 〗 2^((i+j)), (2.3)

Группируя члены одинаковыми весовыми коэффициентами 2^((i+j))=2^к , преобразуем (2.3) к виду:

Q=∑_(k=0)^(m+n-2)▒2^k ∑_(j+i=k)^(n-1)▒〖(a_(i ) b_j 〗). (2.4)

Из полученной формулы (2.4) видно, что для вычисления значения k-го разряда произведения необходимо выполнять совокупность произведений одноразрядных чисел 〖(a〗_(i ) b_j) ,для которых сумма индексов j+i=k. Затем надо последовательно складывать эти произведения . При добавлении к сумме новых слагаемых возможно появление

...