Двоичный умножитель — это электронная схема , используемая в цифровой электронике , например, в компьютере , для умножения двух двоичных чисел .
Для реализации цифрового умножителя можно использовать различные методы компьютерной арифметики . Большинство методов включают вычисление набора частичных произведений, которые затем суммируются с помощью двоичных сумматоров . Этот процесс похож на длинное умножение , за исключением того, что он использует двоичную ( двоичную ) систему счисления .
Между 1947 и 1949 годами Артур Алек Робинсон работал в English Electric , будучи учеником-стажером, а затем инженером-разработчиком. В этот период он учился на докторскую степень в Манчестерском университете, где работал над проектированием аппаратного умножителя для раннего компьютера Mark 1. Однако до конца 1970-х годов большинство мини-компьютеров не имели инструкции умножения, поэтому программисты использовали «процедуру умножения» [1] [2] [3] , которая многократно сдвигает и накапливает частичные результаты, часто написанные с использованием разматывания цикла . У мэйнфреймовых компьютеров были инструкции умножения, но они делали те же виды сдвигов и сложений, что и «процедура умножения».
Ранние микропроцессоры также не имели инструкции умножения. Хотя инструкция умножения стала обычной с 16-битным поколением, [4] по крайней мере два 8-битных процессора имеют инструкцию умножения: Motorola 6809 , представленный в 1978 году, [5] и семейство Intel MCS-51 , разработанное в 1980 году, а позднее современные 8-битные микропроцессоры Atmel AVR, присутствующие в микроконтроллерах ATMega, ATTiny и ATXMega.
Поскольку благодаря более масштабной интеграции стало доступно больше транзисторов на кристалле , стало возможным разместить достаточное количество сумматоров на одном кристалле, чтобы суммировать все частичные произведения одновременно, вместо того чтобы повторно использовать один сумматор для обработки каждого частичного произведения по одному за раз.
Поскольку некоторые распространенные алгоритмы цифровой обработки сигналов большую часть времени тратят на умножение, разработчики цифровых сигнальных процессоров жертвуют значительной площадью кристалла, чтобы сделать умножение максимально быстрым; однотактный блок умножения-накопления часто занимал большую часть площади кристалла ранних ЦСП.
Метод, которому учат в школе для умножения десятичных чисел, основан на вычислении частичных произведений, сдвиге их влево и последующем сложении. Самое сложное — получить частичные произведения, так как это подразумевает умножение длинного числа на одну цифру (от 0 до 9):
123 × 456 ===== 738 (это 123 × 6) 615 (это 123 × 5, смещено на одну позицию влево) + 492 (это 123 × 4, сдвинуто на две позиции влево) ===== 56088
Двоичный компьютер выполняет точно такое же умножение, как и десятичные числа, но с двоичными числами. В двоичном кодировании каждое длинное число умножается на одну цифру (либо 0, либо 1), и это намного проще, чем в десятичном, так как произведение на 0 или 1 равно просто 0 или тому же числу. Таким образом, умножение двух двоичных чисел сводится к вычислению частичных произведений (которые равны 0 или первому числу), сдвигу их влево и последующему сложению (конечно, двоичное сложение):
1011 (это двоичное число для десятичного 11) × 1110 (это двоичное десятичное число 14) ====== 0000 (это 1011 × 0) 1011 (это 1011 × 1, сдвинутое на одну позицию влево) 1011 (это 1011 × 1, сдвинутое на две позиции влево) + 1011 (это 1011 × 1, сдвинутое на три позиции влево) ========= 10011010 (это двоичное число для десятичного 154)
Это намного проще, чем в десятичной системе, поскольку не нужно запоминать таблицу умножения: только сдвиги и сложения.
Этот метод математически корректен и имеет то преимущество, что небольшой ЦП может выполнять умножение, используя функции сдвига и сложения своего арифметико-логического устройства, а не специализированную схему. Однако этот метод медленный, поскольку он включает в себя множество промежуточных сложений. Эти сложения отнимают много времени. Более быстрые умножители могут быть спроектированы для того, чтобы делать меньше сложений; современный процессор может умножать два 64-битных числа с 6 сложениями (а не 64) и может выполнять несколько шагов параллельно. [ необходима цитата ]
Вторая проблема заключается в том, что базовый школьный метод обрабатывает знак с помощью отдельного правила («+ с + дает +», «+ с − дает −» и т. д.). Современные компьютеры встраивают знак числа в само число, обычно в представление в виде дополнения до двух . Это заставляет адаптировать процесс умножения для обработки чисел в виде дополнения до двух, и это немного усложняет процесс. Аналогично, процессоры, использующие дополнение до единиц , знак и величину , IEEE-754 или другие двоичные представления, требуют определенных настроек процесса умножения.
Например, предположим, что мы хотим умножить два беззнаковых 8-битных целых числа: a [7:0] и b [7:0]. Мы можем получить восемь частичных произведений, выполнив восемь 1-битных умножений, по одному для каждого бита в множимом 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]}} означает повторение a[0] (нулевого бита a) 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 + р2[7] р2[6] р2[5] р2[4] р2[3] р2[2] р2[1] р2[0] 0 0 + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0 + стр4[7] стр4[6] стр4[5] стр4[4] стр4[3] стр4[2] стр4[1] стр4[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 + с6[7] с6[6] с6[5] с6[4] с6[3] с6[2] с6[1] с6[0] 0 0 0 0 0 0 + стр7[7] стр7[6] стр7[5] стр7[4] стр7[3] стр7[2] стр7[1] стр7[0] 0 0 0 0 0 0 0-------------------------------------------------- ---------------------------------------------П[15] П[14] П[13] П[12] П[11] П[10] П[9] П[8] П[7] П[6] П[5] П[4] П[3] П[2] П[1] П[0]
Другими словами, P [15:0] получается путем суммирования p 0, p 1 << 1, p 2 << 2 и т. д., чтобы получить наш конечный беззнаковый 16-битный продукт.
Если бы b было целым числом со знаком , а не целым числом без знака , то частичные произведения должны были бы быть расширены по знаку до ширины произведения перед суммированием. Если бы 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 стр7[7] ~стр7[6] ~стр7[5] ~стр7[4] ~стр7[3] ~стр7[2] ~стр7[1] ~стр7[0] 0 0 0 0 0 0 0-------------------------------------------------- -------------------------------------------------- ----------- П[15] П[14] П[13] П[12] П[11] П[10] П[9] П[8] П[7] П[6] П[5] П[4] П[3] П[2] П[1] П[0]
Где ~p представляет собой дополнение (противоположное значение) p.
В битовом массиве выше есть много упрощений, которые не показаны и не очевидны. Последовательности из одного дополненного бита, за которым следуют недополненные биты, реализуют трюк с дополнением до двух, чтобы избежать расширения знака. Последовательность p7 (недополненный бит, за которым следуют все дополненные биты) возникает потому, что мы вычитаем этот член, поэтому все они были инвертированы для начала (и 1 была добавлена в наименее значимую позицию). Для обоих типов последовательностей последний бит инвертируется, и неявный −1 должен быть добавлен непосредственно под MSB. Когда +1 из отрицания дополнения до двух для p7 в битовой позиции 0 (LSB) и все −1 в битовых столбцах с 7 по 14 (где расположен каждый из MSB) складываются вместе, их можно упростить до единственной 1, которая «волшебным образом» выплывает влево. Объяснение и доказательство того, почему переворачивание старшего бита избавляет нас от необходимости расширения знака, см. в книге по компьютерной арифметике. [6]
Двоичное число с плавающей точкой содержит знаковый бит, значимые биты (известные как мантиссы) и биты экспоненты (для простоты мы не рассматриваем поле базы и комбинации). Знаковые биты каждого операнда подвергаются операции XOR для получения знака ответа. Затем две экспоненты складываются для получения экспоненты результата. Наконец, умножение мантиссы каждого операнда вернет мантиссу результата. Однако, если результат двоичного умножения превышает общее количество бит для определенной точности (например, 32, 64, 128), требуется округление, и экспонента изменяется соответствующим образом.
Процесс умножения можно разделить на 3 этапа: [7] [8]
Более старые архитектуры умножителей использовали сдвигатель и аккумулятор для суммирования каждого частичного продукта, часто одного частичного продукта за цикл, жертвуя скоростью ради площади кристалла. Современные архитектуры умножителей используют (модифицированный) алгоритм Бо–Вули, [9] [10] [11] [12] деревья Уоллеса или умножители Дадда для сложения частичных продуктов вместе за один цикл. Производительность реализации дерева Уоллеса иногда улучшается с помощью модифицированного кодирования Бута одного из двух множимых, что уменьшает количество частичных продуктов, которые необходимо суммировать.
Для повышения скорости умножители сдвига и сложения требуют быстрого сумматора (что-то более быстрое, чем последовательный перенос). [13]
«Однотактный» умножитель (или «быстрый умножитель») представляет собой чистую комбинационную логику .
В быстром умножителе процесс сокращения частичного продукта обычно вносит наибольший вклад в задержку, мощность и площадь умножителя. [7] Для скорости этапы «сокращения частичного продукта» обычно реализуются как сумматор с сохранением переноса, состоящий из компрессоров, а этап «вычисления конечного продукта» реализуется как быстрый сумматор (что-то более быстрое, чем непрерывный перенос).
Многие быстрые умножители используют полные сумматоры в качестве компрессоров («компрессоры 3:2»), реализованных в статическом КМОП . Чтобы достичь лучшей производительности в той же области или той же производительности в меньшей области, конструкции умножителей могут использовать компрессоры более высокого порядка, такие как компрессоры 7:3; [8] [7] реализовывать компрессоры в более быстрой логике (такой как логика вентиля передачи, логика проходного транзистора, логика домино ); [13] подключать компрессоры по другой схеме; или в какой-либо комбинации.
