Изменения
Нет описания правки
[[Файл:Матричный_умножитель_2.PNG|420px|thumb|right]]
Умножение в бинарной системе счисления происходит точно так же, как в десятичной.
Для формирования произведения требуется вычислить <tex>n</tex> (где <tex>n</tex> — количество разрядов в числах) частичных произведений. Примечательно то, что в бинарной арифметике следует умножать только числа <tex>1</tex> и <tex>0</tex>. Это означает, что нужно прибавлять к сумме остальных частичных произведений либо множитель, либо ноль. Таким образом, для формирования частичного произведения можно воспользоваться логическими элементами “2И”“И”.
==== Вычисление частичных произведений ====
==== Схема ====
[[Файл:Mul_2.jpgjpg?|right|Схема матричного умножителя]]
Далее будем рассматривать умножение пяти разрядного и четырех разрядного чисел. Соответственно нам понадобится три пяти разрядных сумматора.
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на схеме. Формирование частичных произведений в этой схеме осуществляется посредством логических элементов “2И”“И”.
Помимо этого, рассматриваемая схема содержит шесть дополнительных двухвходовых элементов "исключающее ИЛИ" и два дополнительных входа <tex> u1, u2 </tex>. При этом в рабочем режиме на входы <tex> c, u1, u2, p1, p2, p3 </tex> подаются сигналы логического "0".
Это нужно для работы теста проверяющего неисправности. Но рассматривать мы это не будемотносится к этой теме.
===== Работа схемы =====
Схема работает по достаточно простому принципу.
В начале первый разряд первого и первый разряд второго числа поступают на элемент "2ИИ" и результат сразу записывается в первый разряд произведения.
Дальше второй разряд первого числа снова поступает вместе с первым разрядом второго числа на элемент 2И И и результат уже суммируется с произведение первого разряда первого числа и второго разряда второго числа и все это записывается во второй разряд произведения.
И дальше все продолжается по циклу.
То есть все произведения разрядов первого числа на <tex> n - 1 </tex> разряд второго числа суммируются с произведением предыдущего разряда первого числа на <tex> n </tex> разряд второго числа. И далее эта сумма так же суммируется, если только мы уже не получили нужный нам разряд произведения.
===== Проводники =====
Как мы можем видеть, <tex>y1 - y5</tex> - это — разряды первого числа, <tex>x1 - x4</tex> - это — разряды второго числа. <tex>y1 - y5</tex> проводники идут ко всем элементам 2И"И", а <tex>x1 - x4</tex> идут каждый только к одному из пяти разрядных сумматоров <tex>SM</tex>. А на выходе мы имеем <tex>z1 - z9</tex> - это — разряды конечного числа.
==== "Матричный умножитель" ====
Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “2И”“И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
==Схемная сложность==
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.
