Двоичный множитель является электронной схема используется в цифровой электронике , такие как компьютер , чтобы умножить два двоичных чисел .
Для реализации цифрового умножителя можно использовать различные компьютерные арифметические методы. Большинство методов включают вычисление набора частичных произведений, которые затем суммируются с помощью двоичных сумматоров . Этот процесс похож на долгое умножение , за исключением того, что в нем используется двоичная ( двоичная ) система счисления .
История
С 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 х 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»), реализованных в статической КМОП-матрице . Для достижения лучшей производительности на той же площади или такой же производительности на меньшей площади в умножителях могут использоваться компрессоры более высокого порядка, такие как компрессоры 7: 3; [8] [7] реализуют компрессоры в более быстрой логике (например, логика затвора передачи, логика проходного транзистора, логика домино ); [13] подключите компрессоры по разной схеме; или какая-то комбинация.
Примеры схем
Смотрите также
- Алгоритм умножения Бута
- Слитное умножение – сложение
- Дерево Уоллеса
- Алгоритм BKM для комплексных логарифмов и экспонент
- Умножение Кочанского для модульного умножения
- Логический сдвиг влево
Рекомендации
- ^ "Эволюция Форта" Элизабет Д. Ратер и др. [1] [2]
- ^ "Взаимодействие аппаратного умножителя с микропроцессором общего назначения"
- ^ М. Rafiquzzaman (2005). Основы цифровой логики и проектирования микрокомпьютеров . Джон Вили и сыновья . п. 251. ISBN. 978-0-47173349-2.
- ^ Кришна Кант (2007). Микропроцессоры и микроконтроллеры: архитектура, программирование и системное проектирование 8085, 8086, 8051, 8096 . PHI Learning Pvt. ООО п. 57. ISBN 9788120331914.
- ^ Кришна Кант (2010). Agri Instrumentation на базе микропроцессоров . PHI Learning Pvt. ООО п. 139. ISBN 9788120340862.
- ^ Пархами, Бехруз, Компьютерная арифметика: алгоритмы и конструкции оборудования, Oxford University Press , Нью-Йорк, 2000 ( ISBN 0-19-512583-5 , 490 + xx стр.)
- ^ a b c Мануш Рухоламини; Омид Кавехи; Амир-паша Мирбаха; Сомай Джафарали Джасби; и Кейван Нави. «Новый дизайн компрессоров формата 7: 2» .
- ^ а б Юхао Леонг, Хай Хьюнг Ло, Майкл Дриберг, Абу Бакар Саюти и Патрик Себастьян. «Сравнительный обзор производительности компрессора 8-3 на ПЛИС» .
- ^ Боуг, Чарльз Ричмонд; Вули, Брюс А. (декабрь 1973 г.). «Алгоритм умножения параллельных массивов с дополнением до двух». Транзакции IEEE на компьютерах . С-22 (12): 1045–1047. DOI : 10.1109 / TC.1973.223648 . S2CID 7473784 .
- ^ Хатамян, Мехди; Кэш, Гленн (1986). «Параллельный конвейерный умножитель 8 бит × 8 бит с полосой пропускания 70 МГц в КМОП-матрице 2,5 мкм» . Журнал IEEE по твердотельным схемам . 21 (4): 505–513. DOI : 10,1109 / jssc.1986.1052564 .
- ^ Гебали, Файез (2003). "Множитель Боу-Вули" (PDF) . Университет Виктории , CENG 465 Lab 2. Архивировано (PDF) из оригинала 2018-04-14 . Проверено 14 апреля 2018 .
- ^ Рейндерс, Неле; Дехайн, Вим (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 .
- ^ а б Пэн Чанг. «Реконфигурируемый цифровой умножитель и конструкция компрессорных ячеек 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.
Внешние ссылки
- Конструкции умножителей, предназначенные для ПЛИС
- Схема двоичного умножителя с использованием полусумматоров и цифровых вентилей.