Un multiplicador binario es un circuito electrónico que se utiliza en electrónica digital , como una computadora , para multiplicar dos números binarios .
Se puede utilizar una variedad de técnicas aritméticas por computadora para implementar un multiplicador digital. La mayoría de las técnicas implican calcular el conjunto de productos parciales, que luego se suman mediante sumadores binarios . Este proceso es similar a la multiplicación larga , excepto que utiliza un sistema numérico de base 2 ( binario ) .
Historia
Entre 1947 y 1949 Arthur Alec Robinson trabajó para English Electric Ltd, como estudiante aprendiz y luego como ingeniero de desarrollo. Durante este período, estudió un doctorado en la Universidad de Manchester, donde trabajó en el diseño del multiplicador de hardware para la primera computadora Mark 1. [3] Sin embargo, hasta finales de la década de 1970, la mayoría de las miniordenadores no tenían una instrucción de multiplicación, por lo que los programadores usaban una "rutina de multiplicación" [1] [2] que cambia repetidamente y acumula resultados parciales, a menudo escritos mediante desenrollado de bucle . Las computadoras mainframe tenían instrucciones de multiplicación, pero hacían el mismo tipo de cambios y adiciones como una "rutina de multiplicación".
Los primeros microprocesadores tampoco tenían instrucción de multiplicación. Aunque la instrucción de multiplicación se hizo común con la generación de 16 bits, [3] al menos dos procesadores de 8 bits tienen una instrucción de multiplicación: el Motorola 6809 , introducido en 1978, [4] [5] y la familia Intel MCS-51 , desarrollada en 1980, y más tarde los modernos microprocesadores Atmel AVR de 8 bits presentes en los microcontroladores ATMega, ATTiny y ATXMega.
A medida que se dispuso de más transistores por chip debido a la integración a mayor escala, fue posible colocar suficientes sumadores en un solo chip para sumar todos los productos parciales a la vez, en lugar de reutilizar un solo sumador para manejar cada producto parcial de uno en uno.
Debido a que algunos algoritmos comunes de procesamiento de señales digitales dedican la mayor parte de su tiempo a multiplicar, los diseñadores de procesadores de señales digitales sacrifican un área de chip considerable para que la multiplicación sea lo más rápida posible; una unidad de multiplicación-acumulación de ciclo único a menudo consumía la mayor parte del área de chip de los primeros DSP.
Multiplicación larga binaria
El método que se enseña en la escuela para multiplicar números decimales se basa en calcular productos parciales, desplazarlos hacia la izquierda y luego sumarlos. La parte más difícil es obtener los productos parciales, ya que eso implica multiplicar un número largo por un dígito (de 0 a 9):
123 x 456 ===== 738 (esto es 123 x 6) 615 (esto es 123 x 5, desplazado una posición a la izquierda) + 492 (esto es 123 x 4, desplazado dos posiciones a la izquierda) ===== 56088
Una computadora binaria hace exactamente la misma multiplicación que los números decimales, pero con números binarios. En la codificación binaria, cada número largo se multiplica por un dígito (0 o 1), y eso es mucho más fácil que en decimal, ya que el producto por 0 o 1 es solo 0 o el mismo número. Por lo tanto, la multiplicación de dos números binarios se reduce a calcular productos parciales (que son 0 o el primer número), desplazarlos a la izquierda y luego sumarlos (una adición binaria, por supuesto):
1011 (esto es binario para el decimal 11) x 1110 (esto es binario para el decimal 14) ====== 0000 (esto es 1011 x 0) 1011 (esto es 1011 x 1, desplazado una posición a la izquierda) 1011 (esto es 1011 x 1, desplazado dos posiciones a la izquierda) + 1011 (esto es 1011 x 1, desplazado tres posiciones a la izquierda) ========= 10011010 (esto es binario para el decimal 154)
Esto es mucho más simple que en el sistema decimal, ya que no hay una tabla de multiplicar para recordar: solo cambia y suma.
Este método es matemáticamente correcto y tiene la ventaja de que una pequeña CPU puede realizar la multiplicación usando el cambio y agregar características de su unidad aritmética lógica en lugar de un circuito especializado. Sin embargo, el método es lento, ya que implica muchas adiciones intermedias. Estas adiciones requieren mucho tiempo. Se pueden diseñar multiplicadores más rápidos para hacer menos adiciones; un procesador moderno puede multiplicar dos números de 64 bits con 6 adiciones (en lugar de 64) y puede realizar varios pasos en paralelo. [ cita requerida ]
El segundo problema es que el método escolar básico maneja el signo con una regla separada ("+ con + produce +", "+ con - produce -", etc.). Las computadoras modernas incrustan el signo del número en el número mismo, generalmente en la representación del complemento a dos . Eso obliga a que el proceso de multiplicación se adapte para manejar números en complemento a dos, y eso complica un poco más el proceso. De manera similar, los procesadores que utilizan el complemento de unos , el signo y la magnitud , IEEE-754 u otras representaciones binarias requieren ajustes específicos al proceso de multiplicación.
Enteros sin signo
Por ejemplo, suponga que queremos multiplicar dos enteros de ocho bits sin signo : a [7: 0] yb [7: 0]. Podemos producir ocho productos parciales realizando ocho multiplicaciones de un bit, una por cada bit del multiplicando 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]
donde {8 {a [0]}} significa repetir un [0] (el bit 0 de a) 8 veces ( notación Verilog ).
Para producir nuestro producto, necesitamos sumar los ocho productos parciales, como se muestra aquí:
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]
En otras palabras, P [15: 0] se produce sumando p 0, p 1 << 1, p 2 << 2, y así sucesivamente, para producir nuestro producto final de 16 bits sin signo.
Enteros firmados
Si b había sido un firmado número entero en lugar de un unsigned entero, entonces los productos parciales tendrían que haber sido signo extendido plano a la anchura del producto antes de la suma. Si a hubiera sido un entero con signo, entonces el producto parcial p7 tendría que restarse de la suma final, en lugar de sumarle.
El multiplicador de matriz anterior se puede modificar para admitir números con signo de notación en complemento a dos invirtiendo varios de los términos del producto e insertando uno a la izquierda del primer término del producto parcial:
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]
Donde ~ p representa el complemento (valor opuesto) de p.
Hay muchas simplificaciones en la matriz de bits anterior que no se muestran y no son obvias. Las secuencias de un bit complementado seguidas de bits no complementados están implementando un truco de complemento a dos para evitar la extensión del signo. La secuencia de p7 (bit no complementado seguido de todos los bits complementados) se debe a que estamos restando este término, por lo que todos se negaron al principio (y se agregó un 1 en la posición menos significativa). Para ambos tipos de secuencias, el último bit se invierte y se debe agregar un -1 implícito directamente debajo del MSB. Cuando se suman el +1 de la negación del complemento a dos para p7 en la posición de bit 0 (LSB) y todos los -1 en las columnas de bits 7 a 14 (donde se encuentran cada uno de los MSB), se pueden simplificar al 1 único que "mágicamente" está flotando hacia la izquierda. Para obtener una explicación y una prueba de por qué voltear el MSB nos ahorra la extensión del signo, consulte un libro de aritmética informática. [6]
Números de punto flotante
Un número flotante binario contiene un bit de signo, bits significativos (conocidos como significando) y bits de exponentes (para simplificar, no consideramos el campo base y de combinación). Los bits de signo de cada operando se XOR para obtener el signo de la respuesta. Luego, se suman los dos exponentes para obtener el exponente del resultado. Finalmente, la multiplicación del significado de cada operando devolverá el significado del resultado. Sin embargo, si el resultado de la multiplicación binaria es mayor que el número total de bits para una precisión específica (por ejemplo, 32, 64, 128), se requiere redondeo y el exponente se cambia de manera apropiada.
Implementación de hardware
El proceso de multiplicación se puede dividir en 3 pasos: [7] [8]
- generando producto parcial
- reduciendo el producto parcial
- computación del producto final
Las arquitecturas de multiplicador más antiguas empleaban un cambiador y un acumulador para sumar cada producto parcial, a menudo un producto parcial por ciclo, intercambiando velocidad por área de troquel. Las arquitecturas de multiplicadores modernas utilizan el algoritmo de Baugh-Wooley (modificado) , [9] [10] [11] [12] árboles de Wallace o multiplicadores de Dadda para sumar los productos parciales en un solo ciclo. El rendimiento de la implementación del árbol de Wallace a veces se mejora mediante la codificación Booth modificada de uno de los dos multiplicandos, lo que reduce el número de productos parciales que se deben sumar.
Para la velocidad, los multiplicadores de cambio y suma requieren un sumador rápido (algo más rápido que el acarreo de ondas). [13]
Un multiplicador de "ciclo único" (o "multiplicador rápido") es pura lógica combinacional .
En un multiplicador rápido, el proceso de reducción del producto parcial suele ser el que más contribuye al retardo, la potencia y el área del multiplicador. [7] Para la velocidad, las etapas de "reducir el producto parcial" se implementan típicamente como un sumador de acarreo-ahorro compuesto por compresores y el paso de "calcular el producto final" se implementa como un sumador rápido (algo más rápido que el acarreo de rizo).
Muchos multiplicadores rápidos utilizan sumadores completos como compresores ("compresores 3: 2") implementados en CMOS estático . Para lograr un mejor rendimiento en la misma área o el mismo rendimiento en un área más pequeña, los diseños de multiplicadores pueden utilizar compresores de orden superior, como compresores 7: 3; [8] [7] implementan los compresores en una lógica más rápida (como la lógica de la puerta de transmisión, la lógica del transistor de paso, la lógica dominó ); [13] conecte los compresores en un patrón diferente; o alguna combinación.
Circuitos de ejemplo
Ver también
- Algoritmo de multiplicación de Booth
- Fusionar multiplicar - agregar
- Árbol de Wallace
- Algoritmo BKM para logaritmos complejos y exponenciales
- Multiplicación de Kochanski para multiplicación modular
- Desplazamiento lógico a la izquierda
Referencias
- ^ "La evolución de Forth" por Elizabeth D. Rather et al. [1] [2]
- ^ "Interfaz de un multiplicador de hardware a un microprocesador de propósito general"
- ^ M. Rafiquzzaman (2005). Fundamentos de Lógica Digital y Diseño de Microcomputadoras . John Wiley e hijos . pag. 251. ISBN 978-0-47173349-2.
- ^ Krishna Kant (2007). Microprocesadores y Microcontroladores: Arquitectura, Programación y Diseño de Sistemas 8085, 8086, 8051, 8096 . PHI Learning Pvt. Ltd. p. 57. ISBN 9788120331914.
- ^ Krishna Kant (2010). Instrumentación agrícola basada en microprocesadores . PHI Learning Pvt. Ltd. p. 139. ISBN 9788120340862.
- ^ Parhami, Behrooz, Aritmética informática: algoritmos y diseños de hardware, Oxford University Press , Nueva York, 2000 ( ISBN 0-19-512583-5 , 490 + xx págs.)
- ^ a b c Mahnoush Rouholamini; Omid Kavehie; Amir-Pasha Mirbaha; Somaye Jafarali Jasbi; y Keivan Navi. "Un nuevo diseño para compresores 7: 2" .
- ^ a b Yuhao Leong, HaiHiung Lo, Michael Drieberg, Abu Bakar Sayuti y Patrick Sebastian. "Revisión de comparación de rendimiento del compresor 8-3 en FPGA" .
- ^ Baugh, Charles Richmond; Wooley, Bruce A. (diciembre de 1973). "Algoritmo de multiplicación de matriz paralela de complemento a dos". Transacciones IEEE en computadoras . C-22 (12): 1045–1047. doi : 10.1109 / TC.1973.223648 . S2CID 7473784 .
- ^ Hatamian, Mehdi; Efectivo, Glenn (1986). "Un multiplicador de canalización en paralelo de 8 bits × 8 bits de 70 MHz en CMOS de 2,5 μm" . Revista IEEE de circuitos de estado sólido . 21 (4): 505–513. doi : 10.1109 / jssc.1986.1052564 .
- ^ Gebali, Fayez (2003). "Multiplicador de Baugh-Wooley" (PDF) . University of Victoria , CENG 465 Lab 2. Archivado (PDF) desde el original el 14 de abril de 2018 . Consultado el 14 de abril de 2018 .
- ^ Reynders, Nele; Dehaene, Wim (2015). Diseño de ultra bajo voltaje de circuitos digitales energéticamente eficientes . Circuitos analógicos y serie de procesamiento de señales . Circuitos analógicos y procesamiento de señales (ACSP) (1 ed.). Cham, Suiza: Springer International Publishing AG Suiza . doi : 10.1007 / 978-3-319-16136-5 . ISBN 978-3-319-16135-8. ISSN 1872-082X . LCCN 2015935431 .
- ^ a b Peng Chang. "Un multiplicador digital reconfigurable y un diseño de células compresoras 4: 2" . 2008.
- Hennessy, John L .; Patterson, David A. (1990). "Sección A.2, sección A.9". Arquitectura informática: un enfoque cuantitativo . Morgan Kaufmann Publishers, Inc. págs. A-3..A-6, A-39..A-49. ISBN 978-0-12383872-8.
enlaces externos
- Diseños de multiplicadores dirigidos a FPGA
- Circuito multiplicador binario que utiliza Half-Addders y puertas digitales.