Двоичный умножитель — это электронная схема, используемая в цифровой электронике , например в компьютере , для умножения двух двоичных чисел .
Для реализации цифрового умножителя можно использовать различные методы компьютерной арифметики . Большинство методов включают в себя вычисление набора частичных произведений, которые затем суммируются с помощью двоичных сумматоров . Этот процесс аналогичен длинному умножению , за исключением того , что здесь используется двоичная система счисления .
Между 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.
Поскольку благодаря более масштабной интеграции стало доступно больше транзисторов на кристалл , стало возможным разместить достаточное количество сумматоров на одном кристалле, чтобы суммировать все частичные продукты одновременно, вместо того, чтобы повторно использовать один сумматор для обработки каждого частичного продукта по одному.
Поскольку некоторые распространенные алгоритмы цифровой обработки сигналов тратят большую часть времени на умножение, разработчики цифровых процессоров сигналов жертвуют значительной площадью кристалла, чтобы сделать умножение как можно быстрее; однотактный блок умножения-накопления часто занимал большую часть площади кристалла ранних DSP.
Метод умножения десятичных чисел, которому обучают в школе, основан на вычислении частичных произведений, их сдвиге влево и последующем сложении. Самая сложная часть — получить частичные произведения, поскольку для этого нужно умножить длинное число на одну цифру (от 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] (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 + 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] П[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 +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] П[2] П[1] П[0]
Где ~p представляет собой дополнение (противоположное значение) p.
В приведенном выше битовом массиве есть много упрощений, которые не показаны и не очевидны. Последовательности одного дополненного бита, за которым следуют недополненные биты, реализуют трюк с дополнением до двух, чтобы избежать расширения знака. Последовательность p7 (недополненный бит, за которым следуют все дополненные биты) обусловлена тем, что мы вычитаем этот член, поэтому все они изначально были инвертированы (и в наименее значащую позицию была добавлена 1). Для обоих типов последовательностей последний бит инвертируется, и непосредственно под старшим битом следует добавить неявное значение -1. Когда +1 из отрицания дополнения до двух для p7 в битовой позиции 0 (LSB) и все -1 в битовых столбцах с 7 по 14 (где расположены каждый из старших битов) складываются вместе, их можно упростить до одной 1. это «волшебным образом» уплывает влево. Объяснение и доказательство того, почему переворачивание старшего разряда позволяет нам сэкономить расширение знака, можно найти в книге по компьютерной арифметике. [6]
Двоичное число с плавающей запятой содержит бит знака, значащие биты (известные как мантисса) и биты экспоненты (для простоты мы не рассматриваем базовое и комбинационное поле). Знаковые биты каждого операнда подвергаются операции XOR для получения знака ответа. Затем два показателя складываются, чтобы получить показатель результата. Наконец, умножение мантиссы каждого операнда вернет мантиссу результата. Однако если результат двоичного умножения превышает общее количество битов определенной точности (например, 32, 64, 128), требуется округление и соответствующим образом изменяется показатель степени.
Процесс умножения можно разделить на 3 этапа: [7] [8]
В старых архитектурах умножителей для суммирования каждого частичного произведения, часто одного частичного произведения за цикл, использовались сдвигатель и аккумулятор, в расчете на скорость и площадь кристалла. Современные архитектуры умножителей используют (модифицированный) алгоритм Боуга-Вули, [9] [10] [11] [12] деревья Уоллеса или множители Дадды для сложения частичных произведений за один цикл. Производительность реализации дерева Уоллеса иногда улучшается за счет модифицированного кодирования Бута одного из двух множимых, что уменьшает количество частичных произведений, которые необходимо суммировать.
Для повышения скорости множители сдвига и сложения требуют быстрого сумматора (что-то более быстрое, чем пульсирующий перенос). [13]
Умножитель «один цикл» (или «быстрый умножитель») представляет собой чистую комбинационную логику .
В быстром умножителе процесс сокращения частичного продукта обычно вносит наибольший вклад в задержку, мощность и площадь умножителя. [7] Для повышения скорости этапы «уменьшения частичного произведения» обычно реализуются как сумматор с сохранением переноса, состоящий из компрессоров, а этап «вычисления конечного продукта» реализуется как быстрый сумматор (что-то более быстрое, чем пульсирующий перенос).
Многие быстрые умножители используют полные сумматоры в качестве компрессоров («компрессоры 3:2»), реализованные в статической КМОП . Чтобы добиться лучшей производительности в той же области или той же производительности в меньшей области, в конструкциях умножителей могут использоваться компрессоры более высокого порядка, например компрессоры 7:3; [8] [7] реализуют компрессоры с использованием более быстрой логики (например, логика передающего вентиля, логика проходного транзистора, логика домино ); [13] подключить компрессоры по другой схеме; или некоторая комбинация.
