139
правок
Изменения
Нет описания правки
[[Файл:Матричный_умножитель_2.PNG|420px|thumb|right]]
Умножение в бинарной системе счисления происходит точно так же как в десятичной.
Для формирования произведения требуется вычислить n (где n - количество разрядов в числах) частичных произведенияпроизведений. Примечательно то, что в бинарной арифметике следует умножать только числа 1 и 0. Это означает, что нужно либо суммировать множимое прибавлять множитель к сумме остальных частичных произведений, либо нетприбавляется ноль. Таким образом, для формирования частичного произведения можно воспользоваться логическими элементами “2И”.
==== Вычисление частичных произведений ====
Для формирования частичного произведения, кроме операции умножения на один разряд, требуется осуществлять его сдвиг влево на число разрядов, соответствующее весу разряда множителя. Сдвиг можно осуществить простым соединением соответствующих разрядов частичных произведений к необходимым разрядам двоичного сумматора.<br>
==== Суммирование частичных произведений ====
На этом этапе происходит сложение всех частичных произведений m. Это происходит так:
вначале мы суммируем <tex>m_0</tex> и <tex>m_1</tex>, саму сумму занесем в <tex>u_1</tex>, а переносы в <tex>v_1</tex>(в <tex>u_1</tex> и <tex>v_1</tex> будет не более n+1 битов в каждом), затем суммируем числа <tex>u_1</tex>, <tex>v_1</tex>, <tex>m_2</tex> и получаем <tex>u_2</tex>, <tex>v_2</tex>. Так суммируется <tex>u_{i-1}</tex>, <tex>v_{i-1}</tex>, <tex>m_i</tex> для всех <tex>i = 2, 3, … , n – -1</tex> . В итоге получаем два числа <tex>u_{n-1}</tex> и <tex>v_{i-1}</tex>, которые складываем с помощью [[двоичный каскадный сумматор|двоичного каскадного сумматора]].
==== Схема ====
[[Файл:Mul_2.jpg|right|Схема матричного умножителя]]
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на рисунке-схеме. Формирование частичных произведений в этой схеме осуществляют микросхемы D1, D3, D5, D7. В этих микросхемах содержится сразу четыре логических элемента “2И”.
==== Работа схемы ====
Сумматор, выполненный на микросхеме D6, суммирует первое и второе частные произведения. При этом младший разряд первого частного произведения не нуждается в суммировании. Поэтому он подаётся на выход умножителя непосредственно (разряд M0). <br>Второе частное произведение должно быть сдвинуто на один разряд. Это осуществляется тем, что младший разряд выходного числа сумматора D6 соединяется со вторым разрядом произведения (M1). Но тогда первое частное произведение необходимо сдвинуть на один разряд по отношению ко второму частному произведению! Это выполняется тем, что младший разряд группы входов A соединяется с первым разрядом частного произведения, первый разряд группы входов A соединяется со вторым разрядом частного произведения, и т.д. Однако старший разряд группы входов A не с чем соединять! Вспомним, что если добавить к числу слева ноль, то значение числа не изменится, поэтому мы можем этот разряд соединить с общим проводом схемы. <br>
Точно таким же образом осуществляется суммирование третьего и четвёртого частного произведения. Это суммирование выполняют микросхемы D4 и D2 соответственно. Отличие заключается только в том, что здесь не нужно задумываться о старшем разряде предыдущей суммы, ведь предыдущая микросхема сумматора формирует сигнал переноса.
==== "Матричный умножитель" ====
Частичные произведения вычисляются за ''n'' шагов. Сложение с вычислением переносов включает ''n - 1'' шаг. Последнее сложение можно выполнить за ''O(log n)''. <br>
В итоге суммарное время работы: <br>
Конкретно по нашей схеме: <br>
Скорость работы схемы, приведенной на рисунке-схеме определяется максимальным временем распространения сигнала. Это цепь D7, D6, D4, D2. Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится. <br>
