Un multiplicador binario es un circuito electrónico utilizado en electrónica digital , como una computadora , para multiplicar dos números binarios .
Se pueden utilizar diversas técnicas aritméticas informáticas para implementar un multiplicador digital. La mayoría de las técnicas implican el cálculo del 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 de numeración de base 2 ( binario ) .
Entre 1947 y 1949, Arthur Alec Robinson trabajó para English Electric como 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 el primer ordenador Mark 1. Sin embargo, hasta finales de los años 1970, la mayoría de los miniordenadores no tenían una instrucción de multiplicación, por lo que los programadores utilizaban una "rutina de multiplicación" [1] [2] [3] que desplaza y acumula repetidamente resultados parciales, a menudo escritos mediante desenrollado de bucle . Los ordenadores mainframe tenían instrucciones de multiplicación, pero realizaban los mismos tipos de desplazamientos y sumas que una "rutina de multiplicación".
Los primeros microprocesadores tampoco tenían instrucción de multiplicación. Aunque la instrucción de multiplicación se volvió común con la generación de 16 bits, [4] al menos dos procesadores de 8 bits tienen una instrucción de multiplicación: el Motorola 6809 , presentado en 1978, [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 hicieron disponibles más transistores por chip debido a una integración a mayor escala, se hizo 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 uno a la vez.
Debido a que algunos algoritmos comunes de procesamiento de señales digitales pasan la mayor parte de su tiempo multiplicando, los diseñadores de procesadores de señales digitales sacrifican un área considerable del chip para hacer que la multiplicación sea lo más rápida posible; una unidad de multiplicación-acumulación de ciclo único a menudo utilizaba la mayor parte del área del chip de los primeros DSP.
El método que se enseña en la escuela para multiplicar números decimales se basa en calcular productos parciales, desplazándolos hacia la izquierda y luego sumándolos. La parte más difícil es obtener los productos parciales, ya que implica multiplicar un número largo por un dígito (del 0 al 9):
123 × 456 ===== 738 (esto es 123 × 6) 615 (esto es 123 × 5, desplazado una posición hacia la izquierda) + 492 (esto es 123 × 4, desplazado dos posiciones hacia 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 (ya sea 0 o 1), y eso es mucho más fácil que en el decimal, ya que el producto por 0 o 1 es simplemente 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 hacia la izquierda y luego sumarlos (una adición binaria, por supuesto):
1011 (esto es binario para decimal 11) × 1110 (esto es binario para decimal 14) ====== 0000 (esto es 1011 × 0) 1011 (esto es 1011 × 1, desplazado una posición hacia la izquierda) 1011 (esto es 1011 × 1, desplazado dos posiciones hacia la izquierda) + 1011 (esto es 1011 × 1, desplazado tres posiciones hacia la izquierda) ========= 10011010 (esto es binario para decimal 154)
Esto es mucho más sencillo que en el sistema decimal, ya que no hay tabla de multiplicación para recordar: sólo desplazamientos y sumas.
Este método es matemáticamente correcto y tiene la ventaja de que una CPU pequeña puede realizar la multiplicación utilizando las funciones de desplazamiento y suma de su unidad lógica aritmética en lugar de un circuito especializado. Sin embargo, el método es lento, ya que implica muchas sumas intermedias. Estas sumas consumen mucho tiempo. Se pueden diseñar multiplicadores más rápidos para realizar menos sumas; un procesador moderno puede multiplicar dos números de 64 bits con 6 sumas (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 + da +", "+ con − da −", etc.). Las computadoras modernas incorporan el signo del número en el propio número, generalmente en la representación del complemento a dos . Eso obliga a adaptar el proceso de multiplicación para manejar números en complemento a dos, y eso complica un poco más el proceso. De manera similar, los procesadores que usan complemento a uno , signo y magnitud , IEEE-754 u otras representaciones binarias requieren ajustes específicos en el proceso de multiplicación.
Por ejemplo, supongamos que queremos multiplicar dos números enteros de 8 bits sin signo : a [7:0] y b [7:0]. Podemos producir ocho productos parciales realizando ocho multiplicaciones de 1 bit, una por cada bit del multiplicando a :
p0[7:0] = a[0] × b[7:0] = {8{a[0]}} y b[7:0] p1[7:0] = a[1] × b[7:0] = {8{a[1]}} y b[7:0] p2[7:0] = a[2] × b[7:0] = {8{a[2]}} y b[7:0] p3[7:0] = a[3] × b[7:0] = {8{a[3]}} y b[7:0] p4[7:0] = a[4] × b[7:0] = {8{a[4]}} y b[7:0] p5[7:0] = a[5] × b[7:0] = {8{a[5]}} y b[7:0] p6[7:0] = a[6] × b[7:0] = {8{a[6]}} y b[7:0] p7[7:0] = a[7] × b[7:0] = {8{a[7]}} y b[7:0]donde {8{a[0]}} significa repetir a[0] (el bit 0 de a) 8 veces ( notación Verilog ).
Para obtener nuestro producto, necesitamos sumar nuestros 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 sin signo de 16 bits.
Si b hubiera sido un entero con signo en lugar de un entero sin signo , entonces los productos parciales deberían haberse extendido hasta el ancho del producto antes de sumar. Si a hubiera sido un entero con signo, entonces el producto parcial p7 debería haber sido restado de la suma final, en lugar de sumarse.
El multiplicador de matriz anterior se puede modificar para admitir números con signo de notación de complemento a dos invirtiendo varios de los términos del producto e insertando un 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 seguido de bits no complementados implementan un truco de complemento a dos para evitar la extensión de 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 para comenzar (y se agregó un 1 en la posición menos significativa). Para ambos tipos de secuencias, se invierte el último bit 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 único 1 que "mágicamente" flota hacia la izquierda. Para obtener una explicación y una prueba de por qué invertir el MSB nos ahorra la extensión de signo, consulte un libro de aritmética informática. [6]
Un número binario de punto flotante contiene un bit de signo, bits significativos (conocidos como mantisa) y bits de exponente (para simplificar, no consideramos el campo base ni el campo de combinación). Los bits de signo de cada operando se combinan para obtener el signo de la respuesta. Luego, se suman los dos exponentes para obtener el exponente del resultado. Finalmente, la multiplicación de la mantisa de cada operando devolverá la mantisa 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 se cambia el exponente según corresponda.
El proceso de multiplicación se puede dividir en tres pasos: [7] [8]
Las arquitecturas de multiplicadores más antiguas empleaban un desplazador y un acumulador para sumar cada producto parcial, a menudo un producto parcial por ciclo, intercambiando velocidad por área de matriz. Las arquitecturas de multiplicadores modernas utilizan el algoritmo 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 la cantidad de productos parciales que se deben sumar.
Para mayor velocidad, los multiplicadores de desplazamiento y adición requieren un sumador rápido (algo más rápido que el acarreo de ondulación). [13]
Un multiplicador de "ciclo único" (o "multiplicador rápido") es lógica combinacional pura .
En un multiplicador rápido, el proceso de reducción de producto parcial generalmente contribuye más al retardo, la potencia y el área del multiplicador. [7] Para la velocidad, las etapas de "reducción de producto parcial" generalmente se implementan como un sumador de acarreo-ahorro compuesto por compresores y el paso de "cálculo del producto final" se implementa como un sumador rápido (algo más rápido que el acarreo-ondulación).
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] implementar los compresores en una lógica más rápida (como lógica de compuerta de transmisión, lógica de transistor de paso, lógica dominó ); [13] conectar los compresores en un patrón diferente; o alguna combinación.
