Двоичный множитель
| Часть серии о | |||||||
| Арифметико-логические схемы | |||||||
|---|---|---|---|---|---|---|---|
| Быстрая навигация | |||||||
|
Теория |
|||||||
|
Компоненты
|
|||||||
|
Категории |
|||||||
|
См. также |
|||||||
Двоичный умножитель — это электронная схема , используемая в цифровой электронике , например в компьютере , для умножения двух двоичных чисел .
различные методы компьютерной арифметики Для реализации цифрового умножителя можно использовать . Большинство методов включают в себя вычисление набора частичных произведений, которые затем суммируются с помощью двоичных сумматоров . Этот процесс аналогичен длинному умножению , за исключением того, что здесь используется двоичная ( двоичная ) система счисления .
История [ править ]
Между 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 (this is 123 × 6)
615 (this is 123 × 5, shifted one position to the left)
+ 492 (this is 123 × 4, shifted two positions to the left)
=====
56088
Двоичный компьютер выполняет точно такое же умножение, как и десятичные числа, но с двоичными числами. В двоичном кодировании каждое длинное число умножается на одну цифру (0 или 1), и это намного проще, чем в десятичном, поскольку произведение на 0 или 1 равно 0 или тому же числу. Следовательно, умножение двух двоичных чисел сводится к вычислению частичных произведений (которыми являются 0 или первое число), их сдвигу влево, а затем их сложению (двоичное сложение, конечно):
1011 (this is binary for decimal 11)
× 1110 (this is binary for decimal 14)
======
0000 (this is 1011 × 0)
1011 (this is 1011 × 1, shifted one position to the left)
1011 (this is 1011 × 1, shifted two positions to the left)
+ 1011 (this is 1011 × 1, shifted three positions to the left)
=========
10011010 (this is binary for decimal 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] P[2] P[1] P[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] P[2] P[1] P[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] подключить компрессоры по другой схеме; или некоторая комбинация.
Примеры схем [ править ]
См. также [ править ]
- Алгоритм умножения Бута
- Слитое умножение-сложение
- Множитель Дадда
- Дерево Уоллеса
- Алгоритм БКМ для комплексных логарифмов и экспонент
- Умножение Кочанского для модульного умножения
- Логический сдвиг влево
Ссылки [ править ]
- ^ Вернее, Элизабет Д.; Колберн, Дональд Р.; Мур, Чарльз Х. (1996) [1993]. «Эволюция Форта» . В Бергине, Томас Дж.; Гибсон, Ричард Г. (ред.). История языков программирования---II . Ассоциация вычислительной техники. стр. 625–670. дои : 10.1145/234286.1057832 . ISBN 0201895021 .
- ^ Дэвис, AC; Фунг, Ю.Т. (1977). «Сопряжение аппаратного умножителя с микропроцессором общего назначения» . Микропроцессоры . 1 (7): 425–432. дои : 10.1016/0308-5953(77)90004-6 .
- ^ Рафикуззаман, М. (2005). «§2.5.1 Двоичная арифметика: умножение беззнаковых двоичных чисел» . Основы цифровой логики и проектирования микрокомпьютеров . Уайли . п. 46. ИСБН 978-0-47173349-2 .
- ^ Rafiquzzaman 2005 , §7.3.3 Сложение, вычитание, умножение и деление знаковых и беззнаковых чисел с. 251
- ^ Кант, Кришна (2007). «§2.11.2 16-битные микропроцессоры» . Микропроцессоры и микроконтроллеры: архитектура, программирование и системное проектирование 8085, 8086, 8051, 8096 . Обучение PHI. п. 57. ИСБН 9788120331914 .
- ^ Пархами, Бехруз (2000). Компьютерная арифметика: алгоритмы и конструкции аппаратного обеспечения . Издательство Оксфордского университета . ISBN 0-19-512583-5 .
- ↑ Перейти обратно: Перейти обратно: а б с Рухоламини, Махнуш; Кавехи, Омид; Мирбаха, Амир-паша; Джасби, Сомайе Джафарали; Нави, Кейван. «Новая конструкция компрессоров 7:2» (PDF) .
- ↑ Перейти обратно: Перейти обратно: а б Леонг, Юхао; Ло, ХиХиунг; Дриберг, Майкл; Саюти, Абу Бакар; Себастьян, Патрик. «Сравнительный обзор производительности компрессора 8-3 на FPGA» .
- ^ Боуг, Чарльз Ричмонд; Вули, Брюс А. (декабрь 1973 г.). «Алгоритм умножения параллельных массивов с дополнением до двух». Транзакции IEEE на компьютерах . С-22 (12): 1045–1047. дои : 10.1109/TC.1973.223648 . S2CID 7473784 .
- ^ Хатамян, Мехди; Кэш, Гленн (1986). «Параллельный конвейерный умножитель с частотой 70 МГц, 8 × 8 бит в КМОП 2,5 мкм» . Журнал IEEE твердотельных схем . 21 (4): 505–513. Бибкод : 1986IJSSC..21..505H . дои : 10.1109/jssc.1986.1052564 .
- ^ Гебали, Файез (2003). «Множитель Боуга – Вули» (PDF) . Университет Виктории , CENG 465 Lab 2. Архивировано (PDF) из оригинала 14 апреля 2018 г. Проверено 14 апреля 2018 г.
- ^ Рейндерс, Неле; Деэн, Вим (2015). Проектирование энергоэффективных цифровых схем сверхнизкого напряжения . Аналоговые схемы и обработка сигналов. Спрингер. дои : 10.1007/978-3-319-16136-5 . ISBN 978-3-319-16135-8 . ISSN 1872-082X . LCCN 2015935431 .
- ↑ Перейти обратно: Перейти обратно: а б Пэн Чанг. «Реконфигурируемый цифровой умножитель и конструкция компрессорных ячеек 4:2» . 2008.
- Хеннесси, Джон Л.; Паттерсон, Дэвид А. (1990). «Раздел А.2, раздел А.9». Компьютерная архитектура: количественный подход . Морган Кауфманн. С. А–3..А–6, А–39..А–49. ISBN 978-0-12383872-8 .