Двоичный множитель - Binary multiplier

Двоичный множитель является электронной схема используется в цифровой электронике , такие как компьютер , чтобы умножить два двоичных чисел .

Для реализации цифрового умножителя можно использовать различные компьютерные арифметические методы. Большинство методов включают вычисление набора частичных произведений, которые затем суммируются с помощью двоичных сумматоров . Этот процесс похож на длинное умножение , за исключением того, что в нем используется двоичная ( двоичная ) система счисления .

История

С 1947 по 1949 год Артур Алек Робинсон работал в English Electric Ltd учеником, а затем инженером-разработчиком. Очень важно, что в этот период он получил степень доктора философии в Манчестерском университете, где работал над дизайном аппаратного умножителя для первых компьютеров Mark 1. [3] Однако до конца 1970-х годов большинство миникомпьютеров не имело инструкции умножения, и поэтому программисты использовали «подпрограмму умножения», которая многократно сдвигает и накапливает частичные результаты, часто записываемые с использованием раскрутки цикла . У мэйнфреймов были инструкции умножения, но они выполняли те же сдвиги и сложения, что и «процедура умножения».

Ранние микропроцессоры также не имели инструкции умножения. Хотя инструкция умножения стала обычным явлением в 16-битном поколении, по крайней мере два 8-битных процессора имеют инструкцию умножения: Motorola 6809 , представленный в 1978 году, и семейство Intel MCS-51 , разработанное в 1980 году, а затем современный Atmel AVR. 8-битные микропроцессоры присутствуют в микроконтроллерах ATMega, ATTiny и ATXMega.

По мере того как стало доступно больше транзисторов на микросхему из-за более крупномасштабной интеграции, стало возможным разместить достаточное количество сумматоров на одной микросхеме, чтобы суммировать все частичные продукты сразу, вместо того, чтобы повторно использовать один сумматор для обработки каждого частичного продукта по одному.

Поскольку некоторые распространенные алгоритмы цифровой обработки сигналов тратят большую часть своего времени на умножение, разработчики цифровых сигнальных процессоров жертвуют значительной площадью кристалла, чтобы сделать умножение как можно более быстрым; Одноцикловое устройство умножения-накопления часто занимало большую часть площади чипа ранних DSP.

Двоичное длинное умножение

В школе метод умножения десятичных чисел основан на вычислении частичных произведений, их сдвиге влево и последующем сложении. Самая сложная часть - получить частичные произведения, поскольку для этого нужно умножить длинное число на одну цифру (от 0 до 9):

     123
   x 456
   =====
     738  (this is 123 x 6)
    615   (this is 123 x 5, shifted one position to the left)
 + 492    (this is 123 x 4, shifted two positions to the left)
   =====
   56088

Двоичный компьютер выполняет точно такое же умножение, как и десятичные числа, но с двоичными числами. В двоичном кодировании каждое длинное число умножается на одну цифру (0 или 1), и это намного проще, чем в десятичном, поскольку произведение на 0 или 1 равно 0 или тому же числу. Следовательно, умножение двух двоичных чисел сводится к вычислению частичных произведений (которые равны нулю или первому числу), их сдвигу влево и последующему сложению (конечно же, двоичному сложению):

       1011   (this is binary for decimal 11)
     x 1110   (this is binary for decimal 14)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is binary for decimal 154)

Это намного проще, чем в десятичной системе, поскольку здесь нет таблицы умножения, которую нужно запомнить: просто сдвигает и складывает.

Этот метод является математически правильным и имеет то преимущество, что небольшой ЦП может выполнять умножение, используя сдвиг и добавление функций своего арифметико-логического блока, а не специализированной схемы. Однако этот метод медленный, так как он включает в себя множество промежуточных добавлений. Эти дополнения требуют много времени. Могут быть разработаны более быстрые множители, чтобы делать меньшее количество добавлений; современный процессор может умножать два 64-битных числа на 6 сложений (вместо 64) и может выполнять несколько шагов параллельно.

Вторая проблема заключается в том, что метод базовой школы обрабатывает знак с отдельным правилом («+ с + дает +», «+ с - дает -» и т. Д.). Современные компьютеры встраивают знак числа в само число, обычно в виде дополнения до двух . Это вынуждает адаптировать процесс умножения для обработки дополнительных двух чисел, что немного усложняет процесс. Точно так же процессоры, которые используют дополнение единиц , знак и величину , IEEE-754 или другие двоичные представления, требуют определенных настроек процесса умножения.

Беззнаковые целые числа

Например, предположим, что мы хотим перемножить два беззнаковых восьмибитовых целых числа вместе: a [7: 0] и b [7: 0]. Мы можем произвести восемь частичных произведений, выполнив восемь однобитовых умножений, по одному на каждый бит в умноженном a :

 p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0]
 p1[7:0] = a[1] × b[7:0] = {8{a[1]}} & b[7:0]
 p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0]
 p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0]
 p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0] 
 p5[7:0] = a[5] × b[7:0] = {8{a[5]}} & b[7:0]
 p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0]
 p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0]

где {8 {a [0]}} означает повторение [0] (0-го бита) 8 раз ( нотация Verilog ).

Чтобы получить наш продукт, нам нужно сложить все восемь наших частичных продуктов, как показано здесь:

                                                p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0]
                                        + p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0
                                  + p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0     0
                            + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0     0     0
                      + p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0     0     0     0
                + p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0     0     0     0     0
          + p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0     0     0     0     0     0
    + p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0     0     0     0     0     0     0
-------------------------------------------------------------------------------------------
P[15] P[14] P[13] P[12] P[11] P[10]  P[9]  P[8]  P[7]  P[6]  P[5]  P[4]  P[3]  P[2]  P[1]  P[0]

Другими словами, P [15: 0] получается суммированием p 0, p 1 << 1, p 2 << 2 и так далее, чтобы получить окончательный 16-битный продукт без знака.

Целые числа со знаком

Если б был подписан целое число вместо знака числа, то частичные продукты должны были бы иметь было знаковое расширение до ширины продукта перед суммированием. Если бы a было целым числом со знаком, то частичное произведение p7 нужно было бы вычесть из окончательной суммы, а не прибавлять к ней.

Вышеупомянутый множитель массива может быть изменен для поддержки чисел со знаком дополнения до двух, путем инвертирования нескольких терминов продукта и вставки единицы слева от первого члена частичного продукта:

                                                    1  ~p0[7]  p0[6]  p0[5]  p0[4]  p0[3]  p0[2]  p0[1]  p0[0]
                                                ~p1[7] +p1[6] +p1[5] +p1[4] +p1[3] +p1[2] +p1[1] +p1[0]   0
                                         ~p2[7] +p2[6] +p2[5] +p2[4] +p2[3] +p2[2] +p2[1] +p2[0]   0      0
                                  ~p3[7] +p3[6] +p3[5] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0]   0      0      0
                           ~p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4[2] +p4[1] +p4[0]   0      0      0      0
                    ~p5[7] +p5[6] +p5[5] +p5[4] +p5[3] +p5[2] +p5[1] +p5[0]   0      0      0      0      0
             ~p6[7] +p6[6] +p6[5] +p6[4] +p6[3] +p6[2] +p6[1] +p6[0]   0      0      0      0      0      0
   1  +p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0]   0      0      0      0      0      0      0
 ------------------------------------------------------------------------------------------------------------
P[15]  P[14]  P[13]  P[12]  P[11]  P[10]   P[9]   P[8]   P[7]   P[6]   P[5]   P[4]   P[3]   P[2]   P[1]  P[0]

Где ~ p представляет собой дополнение (противоположное значение) к p.

В приведенном выше битовом массиве есть много упрощений, которые не показаны и не очевидны. Последовательности из одного дополненного бита, за которым следуют неполные биты, реализуют трюк с дополнением до двух, чтобы избежать расширения знака. Последовательность p7 (неполный бит, за которым следуют все дополняемые биты) объясняется тем, что мы вычитаем этот член, поэтому все они были инвертированы с самого начала (и 1 была добавлена ​​в наименее значимую позицию). Для обоих типов последовательностей последний бит инвертируется, и неявный -1 должен быть добавлен непосредственно под MSB. Когда +1 от отрицания дополнения до двух для p7 в позиции бита 0 (LSB) и все -1 в битовых столбцах с 7 по 14 (где расположен каждый из MSB) складываются вместе, их можно упростить до единственной единицы. это «волшебно» плывет влево. Объяснение и доказательство того, почему переворачивание MSB спасает нас от расширения знака, можно найти в книге по компьютерной арифметике.

Числа с плавающей запятой

Двоичное число с плавающей запятой содержит знаковый бит, значащие биты (известные как мантисса) и биты экспоненты (для простоты мы не рассматриваем базовое поле и поле комбинации). Знаковые биты каждого операнда подвергаются операции XOR, чтобы получить знак ответа. Затем два показателя степени складываются, чтобы получить показатель степени результата. Наконец, умножение значения каждого операнда вернет значение результата. Однако, если результат двоичного умножения больше, чем общее количество бит для определенной точности (например, 32, 64, 128), требуется округление, и показатель степени изменяется соответствующим образом.

Аппаратная реализация

Процесс умножения можно разделить на 3 этапа:

  • создание частичного продукта
  • уменьшение частичного продукта
  • вычисление конечного продукта

В более старых архитектурах умножителей для суммирования каждого частичного продукта использовались сдвигатель и аккумулятор, часто один частичный продукт за цикл, при этом скорость соответствовала площади кристалла. Современные архитектуры умножителей используют (модифицированный) алгоритм Боу-Вули , деревья Уоллеса или множители Дадда для сложения частичных произведений за один цикл. Производительность реализации дерева Уоллеса иногда повышается за счет модифицированного кодирования Бута одного из двух множимых, что уменьшает количество частичных произведений, которые необходимо суммировать.

Для скорости множители сдвига и сложения требуют быстрого сумматора (что-то более быстрое, чем перенос с помощью пульсации).

Умножитель «одного цикла» (или «быстрый умножитель») - это чистая комбинационная логика .

В быстром умножителе процесс уменьшения частичного произведения обычно вносит наибольший вклад в задержку, мощность и площадь умножителя. Что касается скорости, этапы «уменьшения частичного продукта» обычно реализуются как сумматор с сохранением переноса, состоящий из компрессоров, а этап «вычисление конечного продукта» реализуется как быстрый сумматор (что-то более быстрое, чем перенос с прерыванием).

Многие быстрые умножители используют полные сумматоры в качестве компрессоров («компрессоров 3: 2»), реализованных в статической КМОП-матрице . Для достижения лучшей производительности на той же площади или такой же производительности на меньшей площади в умножителях могут использоваться компрессоры более высокого порядка, такие как компрессоры 7: 3; реализовать компрессоры в более быстрой логике (такой как логика затвора передачи, логика проходного транзистора, логика домино ); подключить компрессоры по разной схеме; или какая-то комбинация.

Примеры схем

2-битный на 2-битный двоичный умножитель

Смотрите также

использованная литература

внешние ссылки