Изменения

== Определение Принцип работы ====== Умножение в бинарной системе ====[[Файл:mult_bin.png|300px|right|thumb|''Умножение в столбик'']] Умножение в бинарной системе счисления происходит точно так же, как в десятичной {{---}} по схеме ''умножения столбиком''. Если множимое {{---}} <tex>k</tex> разрядное, а множитель {{---}} <tex>n</tex> разрядный, то для формирования произведения требуется вычислить <tex>n</tex> частичных произведений и сложить их между собой. ===== Вычисление частичных произведений =====В бинарной системе для вычисления частичного произведения можно воспользоваться логическими элементами <tex>\&</tex> {{---}} конъюнкторами.Каждое частичное произведение <tex>(m_i)</tex> {{---}} это результат выполнения <tex>k</tex> логических операции <tex>\&</tex> ( между текущим <tex>i</tex>, где <tex>i=1..n</tex>, разрядом множителя и всеми <tex>k</tex> разрядами множимого) и сдвига результата логической операции влево на число разрядов, соответствующее весу текущего разряда множителя. Матричный умножитель вычисляет частичные произведения по формуле:  <tex>m_i = 2^{i - 1} (a \& b_i), (i=1..n)</tex>

Матричный умножитель {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая умножение двух чисел c помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]]===== Суммирование частичных произведений =====На этом этапе происходит сложение всех частичных произведений <tex> m </tex>.

[[Файл:Mul_2Mult_3.jpg‎png|700px|right|thumb|Схема матричного умножителя]]Далее будем рассматривать умножение четырехразрядных чисел. Соответственно нам понадобится три четырёхразрядных сумматора. <br>Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, для двух четырёх {{---}} разрядных чисел приведена на рисунке-схеме. Формирование частичных произведений в этой схеме осуществляют микросхемы D1, D3, D5, D7. В этих микросхемах содержится сразу четыре осуществляется посредством логических элемента “2И”элементов <tex>\&</tex>.==== Работа схемы ====Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.Сумматор, выполненный на микросхеме D6, суммирует первое Разрядность результата {{---}} <tex>l</tex> определяется разрядностью множителя {{---}} <tex>n</tex> и второе частные произведениямножимого {{---}} <tex>k</tex>:  <tex> l=n+k </tex>. При этом младший разряд первого частного произведения не нуждается в суммировании  Все конъюнкторы работают параллельно. Поэтому он подаётся на выход умножителя непосредственно (разряд M0). Второе частное произведение должно быть сдвинуто на один разряд. Это осуществляется тем, что младший разряд выходного числа Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора D6 соединяется со вторым разрядом произведения (M1). Но тогда первое частное произведение необходимо сдвинуть на один разряд по отношению ко второму частному произведению! Это выполняется тем, что младший разряд группы входов A соединяется В приведенной схеме использованы четырех разрядные сумматоры с первым разрядом частного произведения, первый разряд группы входов A соединяется со вторым разрядом частного произведения, и т.д. Однако старший разряд группы входов A не с чем соединять! Вспомним, что если добавить к числу слева ноль, то значение числа не изменится, поэтому мы можем этот разряд соединить с общим проводом схемыпоследовательным переносом. Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <tex> p8 <br/tex>.Точно таким же образом осуществляется суммирование третьего и четвёртого частного произведения. Это суммирование выполняют микросхемы D4 и D2 соответственно. Отличие заключается только в том, что здесь не нужно задумываться о старшем разряде предыдущей суммы, ведь предыдущая микросхема сумматора формирует сигнал переноса.==== "'''Матричный умножитель" ''' ====Если внимательно посмотреть на схему '''матричного умножителя''' (англ. ''binary multiplier''), то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A </tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “2И”<tex>\&</tex>. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей. 

Частичные произведения вычисляются за ''<tex>n'' </tex> шагов. Сложение с вычислением переносов включает ''<tex>n - 1'' </tex> шаг. Последнее сложение можно выполнить за ''<tex>O(\log n)''. <br/tex>.  В итоге суммарное время работы:  <brtex>''O(n) + O(n) + O(\log n) = O(n)'' <br/tex>Конкретно по нашей схеме: <br>Скорость работы схемы, приведенной на рисунке-схеме определяется максимальным временем распространения сигнала. Это цепь D7, D6, D4, D2. Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится. <br> Особенно заметен выигрыш в быстродействии при построении многоразрядных умножителей, однако ничего не бывает бесплатно. В обмен на быстродействие придётся заплатить увеличением разрядности сумматоров, а значит сложностью схемы. Если сумматоры частных произведений останутся той же разрядности, что и ранее, то разрядность сумматоров пар частичных произведений должна быть увеличена на единицу. Разрядность сумматоров четвёрок частичных произведений будет на два разряда больше разрядности сумматоров частичных произведений и т.д. <br> Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает ''<tex>O(\log n)''</tex>. == См. также ==*[[Дерево Уоллеса]]*[[Двоичный каскадный сумматор]] == Источники информации ==* [http://bookfi.net/book/556972 Е. Угрюмов "Цифровая схемотехника" 2001г.]  * [http://bookfi.net/book/532753 Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.]  * [http://bookfi.net/book/637011 М.И. Богданович "Цифровые интегральные микросхемы" 1996г.]  * [http://library.espec.ws/section6/article46.html Схема умножителя]