Reducción de sumandos

En la multiplicación binaria, cada fila de los sumandos será cero o uno de los números que se van a multiplicar. Consideremos lo siguiente:

 1001 x1010 ----- 0000 1001 0000 1001

La segunda y la cuarta fila de los sumandos son equivalentes al primer término. La producción de los sumandos requiere una puerta lógica AND simple para cada uno. Con suficientes puertas lógicas AND, el tiempo para producir los sumandos será un ciclo de la unidad aritmético-lógica .

Los sumandos se reducen utilizando un sumador completo común de 1 bit que acepta dos términos de 1 bit y un bit de acarreo de entrada. Esto crea una suma y un acarreo de salida. Los sumadores completos están dispuestos de manera que la suma permanezca en la misma columna de sumandos, pero el acarreo de salida se desplaza a la izquierda. En cada ronda de reducción, se utilizan tres bits de una sola columna como los dos términos y el acarreo de entrada para el sumador completo, produciendo un único bit de suma para la columna. Esto reduce los bits de la columna en un factor de 3. Sin embargo, la columna a la derecha desplazará los bits de acarreo de salida, aumentando los bits de la columna en un tercio del número de filas de sumandos. En el peor de los casos, la reducción será de 2/3 del número de filas por ronda de reducción.

A continuación se muestra cómo se realiza la primera ronda de reducción. Nótese que todas las posiciones "vacías" de los sumandos se consideran cero (aquí se utiliza un punto como indicador de los "valores cero asumidos"). En cada fila, los tres bits superiores son las tres entradas del sumador completo (dos términos y acarreo de entrada). La suma se coloca en el bit superior de la columna. El acarreo de salida se coloca en la segunda fila de la columna a la izquierda. El bit inferior es una única entrada a un sumador. La suma de este sumador se coloca en la tercera fila de la columna. El acarreo de salida se ignora ya que siempre será cero, pero por diseño se colocaría en la cuarta fila de la columna a la izquierda. Por diseño, es importante tener en cuenta que las filas 1, 3, 5, ... (contando desde arriba) se llenan con sumas de la propia columna. Las filas 2, 4, 6, ... se llenan con valores de acarreo de salida de la columna a la derecha.

 1011 x0110 ----- ...0000 ..1011. .1011.. 0000... ------- 0111010 000100. 00000..

La reducción se realiza de nuevo exactamente de la misma manera. Esta vez, solo interesan las tres primeras filas de sumandos, ya que todos los demás sumandos deben ser cero.

0111010 000100. 00000.. ------- 0110010 001000.

Cuando solo hay dos filas significativas de sumandos, los ciclos de reducción terminan. Un sumador completo básico normalmente requiere tres ciclos de la unidad aritmético-lógica . Por lo tanto, cada ciclo de reducción suele durar 3 ciclos.

Cuando solo quedan dos filas de sumandos, se suman mediante un sumador rápido. Existen muchos diseños de sumadores rápidos, cualquiera de los cuales puede utilizarse para completar este algoritmo.