Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Часть серии по
арифметико-логические схемы
Быстрая навигация
Составные части

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

Для реализации цифрового умножителя можно использовать различные компьютерные арифметические методы. Большинство методов включают вычисление набора частичных произведений и последующее суммирование частичных произведений. Этот процесс похож на метод учит школьник младших классов для проведения длинных умножений на базе-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 году, а затем современные 8-разрядные микропроцессоры Atmel AVR, присутствующие в микроконтроллерах ATMega, ATTiny и ATXMega.

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

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

Основы [ править ]

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

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

Двоичные числа [ править ]

Двоичный компьютер выполняет точно такое же умножение, как и десятичные числа, но с двоичными числами. В двоичной кодировке каждое длинное число умножается на одну цифру (0 или 1), и это намного проще, чем в десятичном, поскольку произведение на 0 или 1 равно 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 или другие двоичные представления, требуют определенных настроек в процессе умножения.

Беззнаковые числа [ править ]

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

Числа с плавающей запятой [ править ]

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

Реализации [ править ]

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

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

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

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

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

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

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

Примеры схем [ править ]

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

См. Также [ править ]

  • Алгоритм умножения Бута
  • Слитное умножение – сложение
  • Дерево Уоллеса
  • Алгоритм BKM для комплексных логарифмов и экспонент
  • Умножение Кочанского для модульного умножения
  • Логический сдвиг влево

Ссылки [ править ]

  1. ^ "Эволюция Форта" Элизабет Д. Рэзер и др. [1] [2]
  2. ^ «Подключение аппаратного умножителя к микропроцессору общего назначения»
  3. ^ М. Rafiquzzaman (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. ^ Parhami, Behrooz, Компьютерная арифметика: Алгоритмы и аппаратный Designs, Oxford University Press , НьюЙорк, 2000 ( ISBN 0-19-512583-5 , 490 + ая стр.) 
  7. ^ a b c Мануш Рухоламини; Омид Кавехи; Амир-паша Мирбаха; Сомай Джафарали Джасби; и Кейван Нави. «Новый дизайн компрессоров формата 7: 2» .
  8. ^ а б Юхао Леонг, ХайХиунг Ло, Майкл Дриберг, Абу Бакар Саюти и Патрик Себастьян. «Сравнительный обзор производительности компрессора 8-3 на ПЛИС» .
  9. ^ Baugh, Чарльз Ричмонд; Вули, Брюс А. (декабрь 1973 г.). «Алгоритм параллельного умножения массива с дополнением до двух». Транзакции IEEE на компьютерах . С-22 (12): 1045–1047. DOI : 10.1109 / TC.1973.223648 . S2CID 7473784 . 
  10. ^ Хатамян, Мехди; Кэш, Гленн (1986). «Параллельный конвейерный умножитель 8 бит × 8 бит с полосой пропускания 70 МГц в КМОП-матрице 2,5 мкм» . Журнал IEEE по твердотельным схемам . 21 (4): 505–513. DOI : 10,1109 / jssc.1986.1052564 .
  11. ^ Gebali, Fayez (2003). "Множитель Боу-Вули" (PDF) . Университет Виктории , CENG 465 Lab 2. Архивировано (PDF) из оригинала 2018-04-14 . Проверено 14 апреля 2018 .
  12. ^ Рейндерс, Неле; Дехайн, Вим (2015). Сверхнизковольтная конструкция энергоэффективных цифровых схем . Аналоговые схемы и серия обработки сигналов . Аналоговые схемы и обработка сигналов (ACSP) (1-е изд.). Чам, Швейцария: Springer International Publishing AG, Швейцария . DOI : 10.1007 / 978-3-319-16136-5 . ISBN 978-3-319-16135-8. ISSN  1872-082X . LCCN  2015935431 .
  13. ^ а б Пэн Чанг. «Реконфигурируемый цифровой умножитель и конструкция компрессорных ячеек 4: 2» . 2008 г.
  • Хеннесси, Джон Л .; Паттерсон, Дэвид А. (1990). «Раздел A.2, раздел A.9». Компьютерная архитектура: количественный подход . Издательство Morgan Kaufmann Publishers, Inc., стр. A – 3..A-6, A-39..A-49. ISBN 978-0-12383872-8.

Внешние ссылки [ править ]

  • Конструкции умножителей, предназначенные для ПЛИС
  • Схема двоичного умножителя с использованием полусумматоров и цифровых вентилей.