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 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 ( binario ) de base 2 .
Entre 1947 y 1949, Arthur Alec Robinson trabajó para English Electric , como estudiante aprendiz y luego como ingeniero de desarrollo. Fundamentalmente, 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 . Sin embargo, hasta finales de la década de 1970, la mayoría de las minicomputadoras no tenían una instrucción de multiplicación, por lo que los programadores usaban una "rutina de multiplicación" [1] [2] [3] que cambia y acumula repetidamente resultados parciales, a menudo escritos mediante desenrollado de bucles . Las computadoras centrales tenían instrucciones de multiplicación, pero hacían el mismo tipo de cambios y sumas como una "rutina de multiplicación".
Los primeros microprocesadores tampoco tenían instrucciones de multiplicación. Aunque la instrucción multiplicada se volvió común con la generación de 16 bits, [4] al menos dos procesadores de 8 bits tienen una instrucción multiplicada: el Motorola 6809 , introducido en 1978, [5] y la familia Intel MCS-51 , desarrollada en 1980. y posteriormente los modernos microprocesadores Atmel AVR de 8 bits presentes en los microcontroladores ATMega, ATTiny y ATXMega.
A medida que hubo más transistores por chip disponibles 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 considerable del chip para realizar la multiplicación lo más rápido posible; una unidad de acumulación y multiplicación de un solo ciclo a menudo consumía 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, desplazarlos hacia la izquierda y luego sumarlos. 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 (0 o 1), y eso es mucho más fácil que en la codificación 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 hacia la izquierda y luego sumarlos (una suma binaria, por supuesto):
1011 (esto es binario para el decimal 11) × 1110 (esto es binario para el 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 el decimal 154)
Esto es mucho más simple que en el sistema decimal, ya que no hay una tabla de multiplicación que recordar: solo desplazamientos y sumas.
Este método es matemáticamente correcto y tiene la ventaja de que una pequeña CPU 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 porque implica muchas adiciones intermedias. Estas adiciones requieren mucho tiempo. Se pueden diseñar multiplicadores más rápidos para hacer 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 necesaria ]
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 número mismo, generalmente en la representación en 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 utilizan complemento de 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 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, etc., para producir nuestro producto final de 16 bits sin signo.
Si b hubiera sido un entero con signo en lugar de un entero sin signo , entonces los productos parciales deberían haberse extendido con signo hasta el ancho del producto antes de sumar. Si a hubiera sido un entero con signo, entonces el producto parcial p7 debería restarse de la suma final, en lugar de sumarse.
El multiplicador de matriz anterior se puede modificar para admitir números con signo en notación en 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 signos. 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 fueron negados 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 en 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 encuentra 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 significado) y bits de exponente (para simplificar, no consideramos el campo base y combinado). Los bits de signo de cada operando se realizan mediante 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 apropiadamente.
El proceso de multiplicación se puede dividir en 3 pasos: [7] [8]
Las arquitecturas multiplicadoras más antiguas empleaban una palanca de cambios y un acumulador para sumar cada producto parcial, a menudo un producto parcial por ciclo, compensando la velocidad por el área del troquel. Las arquitecturas multiplicadoras modernas utilizan el algoritmo Baugh-Wooley (modificado), [9] [10] [11] [12] árboles de Wallace o multiplicadores Dadda para sumar los productos parciales en un solo ciclo. El rendimiento de la implementación del árbol de Wallace a veces se mejora modificando la codificación de Booth de uno de los dos multiplicandos, lo que reduce el número de productos parciales que se deben sumar.
Para obtener velocidad, los multiplicadores de cambio y adición requieren un sumador rápido (algo más rápido que el transporte 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 contribuir más al retraso, la potencia y el área del multiplicador. [7] Para la velocidad, las etapas de "reducir el producto parcial" generalmente se implementan como un sumador de ahorro de acarreo 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 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 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 lógica de puerta de transmisión, lógica de transistor de paso, lógica dominó ); [13] conecte los compresores en un patrón diferente; o alguna combinación.
