Multiplicador binario

El método que se enseña en la escuela para multiplicar números decimales se basa en calcular productos parciales, desplazarlos a la izquierda y luego sumarlos. La parte más difícil es obtener los productos parciales, ya que esto 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 a la izquierda) + 492 (esto es 123 × 4, desplazado dos posiciones a la izquierda) ===== 56088

Una computadora binaria realiza 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), lo cual es mucho más sencillo que en 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 a la izquierda y luego sumarlos (una suma 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 a la izquierda) 1011 (esto es 1011 × 1, desplazado dos posiciones a la izquierda) + 1011 (esto es 1011 × 1, desplazado tres posiciones a la izquierda) ========= 10011010 (esto es binario para decimal 154)

Esto es mucho más sencillo que en el sistema decimal, ya que no hay que memorizar ninguna tabla de multiplicar: solo se trata de 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 aritmético-lógica 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 podría implementar un sumador paralelo dedicado para productos parciales, lo que permitiría multiplicar dos números de 64 bits con solo 6 rondas de sumas, en lugar de 63.

Supongamos que queremos multiplicar dos enteros sin signo de 8 bits: 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]}} & 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]}} & 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]}} y 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 se utiliza la siguiente notación Verilog :

• {8{a[0]}} significa repetir a[0] (el bit 0 de a) 8 veces.
• a [7:0] significa seleccionar a desde su bit 7 hasta su bit 0, ambos inclusive, para un total de 8 bits.
• &El símbolo representa una operación AND bit a bit.

Para obtener nuestro producto, debemos 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 p0 , p1 << 1, p2 << 2, y así sucesivamente, para producir nuestro producto final sin signo de 16 bits:

P [15:0] = p0[7:0] + (p1[7:0] << 1) + (p2[7:0] << 2) + (p3[7:0] << 3) + (p4[7:0] << 4) + (p5[7:0] << 5) + (p6[7:0] << 6) + (p7[7:0] << 7)

Supongamos que ahora queremos multiplicar dos enteros sin signo de 16 bits: u [15:0] y v [15:0], utilizando el multiplicador de 8x8 bits anterior. Utilizando el método de productos parciales (justificado por la asociatividad de la multiplicación) y operando en bloques de 8 bits, tenemos:

p0[15:0] = u[7:0] × v[7:0] p1[15:0] = u[15:8] × v[7:0] p2[15:0] = u[7:0] × v[15:8] p3[15:0] = u[15:8] × v[15:8]

El producto final sería entonces:

P[31:0] = p0 + p1 << 8 + p2 << 8 + p3 << 16

Se observa que si solo se requiere P[15:0] (los 16 bits inferiores del resultado), no es necesario calcular p3.

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, sacrificando velocidad por área del chip. Para lograr la capacidad de realizar una acumulación por ciclo, se requiere un sumador rápido (algo más rápido que el acarreo en cascada). ^{[ 8 ]}

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.

En un multiplicador rápido, el proceso de reducción de productos parciales (es decir, el cálculo de sumas parciales) suele ser el que más contribuye al retardo, la potencia y el área del multiplicador. ^{[ 6 ]} Para mayor velocidad, las etapas de "reducción de productos parciales" se implementan típicamente como un sumador con acarreo guardado compuesto por compresores y el paso de "cálculo del producto final" se implementa como un sumador rápido.

Un compresor es cualquier dispositivo que recibe más bits de entrada de los que genera como salida. En el contexto de la ingeniería de multiplicadores, se refiere a un sumador con acarreo de entrada y de salida. El compresor básico es el sumador completo, un "compresor 3:2": muchos multiplicadores rápidos utilizan un compresor de este tipo implementado 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 usar compresores de orden superior como compresores 7:3; ^{[ 7 ] [ 6 ]} implementar los compresores en lógica más rápida (como lógica de puerta de transmisión, lógica de transistor de paso, lógica de dominó ); ^{[ 8 ]} conectar los compresores en un patrón diferente; o alguna combinación.

El rendimiento de la implementación del árbol de Wallace a veces mejora al codificar uno de los dos multiplicandos mediante una codificación Booth modificada , lo que reduce el número de productos parciales que deben sumarse.

Un multiplicador de "ciclo único" (o "multiplicador rápido") es lógica combinacional pura .

Si b hubiera sido un entero con signo en lugar de un entero sin signo , los productos parciales habrían necesitado extenderse con signo hasta el ancho del producto antes de sumarlos. Si a hubiera sido un entero con signo, el producto parcial p7 habría necesitado 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 de complemento a dos invirtiendo varios de los términos del producto e insertando un uno a la izquierda del primer y último término parcial del producto:

 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.

En la matriz de bits anterior existen muchas simplificaciones que no se muestran y que 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 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 ubican los MSB), se pueden simplificar al único 1 que "mágicamente" flota hacia la izquierda. Para una explicación y demostración de por qué invertir el MSB nos ahorra la extensión de signo, consulte un libro de aritmética computacional. ^{[ 13 ]}

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 la base ni el campo de combinación). Los bits de signo de cada operando se combinan mediante la operación XOR para obtener el signo del resultado. A continuación, se suman los dos exponentes para obtener el exponente del resultado. Finalmente, la multiplicación de la mantisa de cada operando devuelve 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 el exponente se ajusta en consecuencia.