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

Часть серии по
арифметико-логические схемы
Быстрая навигация
Составные части

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

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

История

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

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

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

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

Основы

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

     123 x 456 ===== 738 (это 123 x 6) 615 (это 123 x 5, сдвинуто на одну позицию влево) + 492 (это 123 x 4, сдвинуто на две позиции влево) === == 56088

Двоичные числа

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

       1011 (это 11 в двоичном формате) x 1110 (это 14 в двоичном формате) ====== 0000 (это 1011 x 0) 1011 (это 1011 x 1, сдвинутое на одну позицию влево) 1011 (это 1011 x 1, сдвинуто на две позиции влево) + 1011 (это 1011 x 1, сдвинуто на три позиции влево) ========= 10011010 (это 154 в двоичном формате)

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

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

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

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

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

 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]] "

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

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

Если б был подписанный целое вместо беззнаковый целое число, то перед суммированием частичные продукты должны быть расширены знаком до ширины продукта. Если а было целое число со знаком, затем частичный продукт 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 спасает нас от расширения знака, можно найти в книге по компьютерной арифметике.[6]

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

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

Реализации

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

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

В более старых архитектурах умножителей для суммирования каждого частичного продукта использовались сдвигатель и аккумулятор, часто по одному частичному продукту за цикл, с обменом скорости на площадь кристалла. Современные архитектуры умножителей используют (изменено) Алгоритм Боуга – Вули,[9][10][11][12] Деревья Уоллеса, или же Множители Дадды для добавления частичных продуктов в один цикл. Производительность Дерево Уоллеса реализация иногда улучшается модифицированный Кодирование будки одно из двух множимых, которое уменьшает количество частичных произведений, которые необходимо суммировать.

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

Множитель "одного цикла" (или "быстрый множитель") является чистым комбинационная логика.

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

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

Примеры схем

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

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

Рекомендации

  1. ^ "Эволюция форта" Элизабет Д. Рэзер и др.[1][2]
  2. ^ «Подключение аппаратного умножителя к микропроцессору общего назначения»
  3. ^ М. Рафикзаман (2005). Основы цифровой логики и проектирования микрокомпьютеров. Джон Уайли и сыновья. п. 251. ISBN  978-0-47173349-2.
  4. ^ Кришна Кант (2007). Микропроцессоры и микроконтроллеры: архитектура, программирование и системное проектирование 8085, 8086, 8051, 8096. PHI Learning Pvt. ООО п. 57. ISBN  9788120331914.
  5. ^ Кришна Кант (2010). Микропроцессорное оборудование для сельского хозяйства. PHI Learning Pvt. ООО п. 139. ISBN  9788120340862.
  6. ^ Пархами, Бехруз, Компьютерная арифметика: алгоритмы и конструкции оборудования, Oxford University Press, Нью-Йорк, 2000 (ISBN  0-19-512583-5, 490 + xx стр.)
  7. ^ а б c Махнуш Рухоламини; Омид Кавехи; Амир-паша Мирбаха; Сомай Джафарали Джасби; и Кейван Нави.«Новый дизайн компрессоров формата 7: 2».
  8. ^ а б Юхао Леонг, ХайХиунг Ло, Майкл Дриберг, Абу Бакар Саюти и Патрик Себастьян.«Сравнительный обзор производительности компрессора 8-3 на ПЛИС».
  9. ^ Боуг, Чарльз Ричмонд; Вули, Брюс А. (декабрь 1973 г.). «Алгоритм параллельного умножения массива с дополнением до двух». Транзакции IEEE на компьютерах. С-22 (12): 1045–1047. Дои:10.1109 / T-C.1973.223648. S2CID  7473784.
  10. ^ Хатамян, Мехди; Кэш, Гленн (1986). «Параллельный конвейерный умножитель 8 бит × 8 бит с полосой пропускания 70 МГц в КМОП-матрице 2,5 мкм». Журнал IEEE по твердотельным схемам. 21 (4): 505–513. Дои:10.1109 / jssc.1986.1052564.
  11. ^ Гебали, Файез (2003). "Множитель Боу-Вули" (PDF). Университет Виктории, CENG 465 Лаборатория 2. В архиве (PDF) из оригинала на 2018-04-14. Получено 2018-04-14.
  12. ^ Рейндерс, Неле; Дехайн, Вим (2015). Сверхнизковольтная конструкция энергоэффективных цифровых схем. Аналоговые схемы и серия обработки сигналов. Аналоговые схемы и обработка сигналов (ACSP) (1-е изд.). Чам, Швейцария: Springer International Publishing AG, Швейцария. Дои:10.1007/978-3-319-16136-5. ISBN  978-3-319-16135-8. ISSN  1872-082X. LCCN  2015935431.
  13. ^ а б Пэн Чанг.«Реконфигурируемый цифровой умножитель и конструкция компрессорных ячеек 4: 2».2008.

внешняя ссылка