Multiplicador de Booth explicado (con ejemplos)

Resumen: La recodificación Booth reescribe las rachas de bits 1 del multiplicador como dígitos con signo. Booth radix-2 examina el par $(Q_0,Q_{-1})$ en cada iteración: 01 suma el multiplicando, 10 lo resta y 00 o 11 no hacen nada antes de un desplazamiento aritmético a la derecha. Una implementación segura en anchura para $n$ bits extiende el signo del multiplicando y usa un acumulador de $(n+1)$ bits, evitando el fallo especial del valor más negativo. Booth modificado radix-4 reduce aproximadamente a la mitad el número de productos parciales al elegir entre $0,\pm M,\pm2M$.

La multiplicación binaria puede construirse con desplazamientos y sumas. El reto no es que sea imposible multiplicar operandos en complemento a 2 sin Booth —no lo es—, sino que el tratamiento del signo y la generación de productos parciales deben diseñarse correctamente.

El método de Booth proporciona una recodificación con signo uniforme y comprime las rachas de bits 1. Es útil en dos arquitecturas diferentes:

• un multiplicador iterativo, que reutiliza un sumador durante varios ciclos
• un multiplicador paralelo, que genera productos parciales recodificados y los reduce con un árbol de sumadores/compresores

Ambas arquitecturas comparten la idea de recodificación, pero tienen distinta latencia, área y temporización.

La identidad de las rachas de unos

Considera una racha de unos binarios desde el bit $j$ hasta el bit $k$, donde $k\ge j$:

Por ejemplo:

La técnica ordinaria de desplazamiento y suma sin signo añadiría cuatro copias desplazadas del multiplicando para 1111. La recodificación Booth representa esa racha con una resta en su límite inferior y una suma en la posición situada por encima de su límite superior.

Esto no garantiza menos operaciones distintas de cero para todos los patrones de bits. Una racha larga se beneficia; unos aislados o alternos pueden no reducir nada e incluso aumentar el número de decisiones de suma/resta. Un multiplicador iterativo radix-2 de latencia fija sigue realizando $n$ iteraciones: la recodificación cambia la acción aritmética de cada iteración, no el número de ciclos automáticamente.

Recodificación Booth radix-2

Añade un cero implícito por debajo del multiplicador:

En la iteración $i$, inspecciona el bit menos significativo actual del multiplicador, $Q_0$, y el bit anterior guardado, $Q_{-1}$:

Después desplaza aritméticamente a la derecha una posición el acumulador, el multiplicador y el bit guardado combinados.

El par detecta los límites:

• 10 marca el extremo bajo de una racha de unos, así que se resta
• 01 marca el extremo alto después de desplazar la racha, así que se suma
• dos bits adyacentes iguales están dentro de una racha constante, así que no hace falta acción aritmética

El orden de los bits de la tabla importa. Algunos textos imprimen $(Q_{-1},Q_0)$; eso invierte las etiquetas de las filas. Declara siempre la convención.

Ruta de datos iterativa segura en anchura

Sean ambos operandos de entrada valores con signo de $n$ bits en complemento a 2:

• $M$: multiplicando
• $Q$: multiplicador

Usa:

• $M_e$: $M$ extendido con signo a $n+1$ bits
• $A$: un acumulador de $n+1$ bits, inicialmente cero
• $Q$: el registro multiplicador de $n$ bits
• $Q_{-1}$: un bit guardado, inicialmente cero
• un contador de iteraciones de 0 a $n-1$

Para cada una de las $n$ iteraciones:

1. inspecciona $(Q_0,Q_{-1})$
2. si es 01, establece $A \leftarrow A+M_e$
3. si es 10, establece $A \leftarrow A-M_e$
4. si es 00 o 11, deja $A$ sin cambios
5. desplaza aritméticamente a la derecha una posición la concatenación $\{A,Q,Q_{-1}\}$

Después de $n$ iteraciones, descarta el bit superior redundante de extensión de signo de $A$. Los $n$ bits restantes de $A$, concatenados con $Q$, forman el producto con signo de $2n$ bits.

Por qué importa el bit adicional del acumulador

Para un número de $n$ bits en complemento a 2, el intervalo representable es:

La magnitud positiva de $-2^{n-1}$ no cabe en $n$ bits. Por tanto, un diseño que precalcule -M usando solo $n$ bits puede fallar cuando $M$ es el valor más negativo. Extender el signo de $M$ y usar un acumulador de $(n+1)$ bits hace representables tanto $M_e$ como $-M_e$ durante el algoritmo.

Ejemplo resuelto: $-3 \times 5$

Usa operandos de 4 bits:

Extiende con signo el multiplicando a cinco bits:

Inicializa:

La tabla muestra el par y la acción aritmética, seguidos del estado después del desplazamiento aritmético combinado a la derecha:

Después de cuatro iteraciones, descarta el bit de signo alto redundante de $A$:

Como valor de 8 bits en complemento a 2:

que coincide con $-3\times5$.

Traza un desplazamiento combinado

Después de la primera resta:

El desplazamiento aritmético a la derecha copia el bit de signo del acumulador en la nueva posición superior y mueve todos los demás bits una posición:

El desplazamiento debe actuar sobre el registro concatenado completo. Desplazar $A$ y $Q$ de forma independiente perdería la transferencia de bits entre sus límites.

Bloques de hardware

Un multiplicador Booth iterativo reutilizable contiene:

• un registro multiplicando o ruta de entrada de $(n+1)$ bits
• un acumulador de $(n+1)$ bits
• un registro multiplicador de $n$ bits más $Q_{-1}$
• un sumador/restador de $(n+1)$ bits
• control de decodificación del par para add, subtract o hold
• un desplazador aritmético combinado
• un contador de iteraciones y control busy/done

El sumador se reutiliza en todas las iteraciones, lo que ahorra área frente a un multiplicador totalmente paralelo, pero cuesta latencia. Que una iteración ocupe un reloj o varios micro pasos depende del controlador y de la ruta de datos.

El componente ALU puede proporcionar el comportamiento de suma/resta en un circuito didáctico, pero confirma su anchura y su comportamiento ante desbordamiento con signo. Un registro de desplazamiento ilustra el movimiento serie; la ruta de datos Booth necesita un registro combinado más ancho cuyo bit superior se rellene con el signo.

Booth modificado radix-4

Booth modificado radix-4 examina ventanas de 3 bits solapadas y recodifica dos bits del multiplicador por dígito. Añade un cero en el extremo bajo y extiende con signo el multiplicador en el extremo alto cuando sea necesario.

Para una ventana $(Q_{2i+1},Q_{2i},Q_{2i-1})$:

Los múltiplos disponibles son:

$2M$ es un desplazamiento a la izquierda, por lo que estos productos parciales son relativamente económicos de generar. Para un multiplicador de $n$ bits, radix-4 produce aproximadamente $\lceil n/2\rceil$ dígitos recodificados en lugar de $n$ dígitos radix-2.

Esa reducción puede:

• reducir a la mitad las iteraciones en un diseño iterativo radix-4
• reducir el número de filas de productos parciales en un diseño paralelo

No hace que el multiplicador completo sea automáticamente el doble de rápido. La recodificación, la corrección de signo, la generación de productos parciales, la reducción, el enrutamiento, la suma final y la segmentación contribuyen a la temporización.

Reducción paralela: Wallace, Dadda y sumadores finales

Un multiplicador de alto rendimiento puede generar productos parciales en paralelo, reducir sus columnas con compresores de acarreo guardado y terminar con un sumador de propagación de acarreo.

Los árboles de Wallace y Dadda son dos planificaciones clásicas de reducción. La recodificación Booth modificada puede colocarse antes de un árbol de este tipo para reducir el número de filas. El sumador final puede usar acarreo anticipado, prefijo paralelo, selección de acarreo u otra estructura elegida para la tecnología objetivo.

«Combinacional» no significa necesariamente «un ciclo de procesador». Un multiplicador ancho puede segmentarse en varias etapas para cumplir un periodo de reloj objetivo, y algunos procesadores usan unidades iterativas por razones de área o potencia. La arquitectura es una decisión de implementación.

Booth frente a otras estructuras de multiplicador

No hay un ganador universal. La anchura de los operandos, las celdas objetivo o los recursos FPGA, el rendimiento, la latencia, el área, la potencia y el esfuerzo de verificación determinan la estructura adecuada.

Constrúyelo en DigiSim

Para una implementación didáctica de 4 bits:

1. Crea un acumulador de 5 bits con elementos de almacenamiento visibles.
2. Extiende con signo el multiplicando de 4 bits a 5 bits.
3. Usa una ruta de suma/resta de 5 bits.
4. Almacena el multiplicador de 4 bits y un bit $Q_{-1}$ separado.
5. Decodifica (Q0, Q−1) como suma, resta o retención.
6. Implementa el desplazamiento aritmético sobre el estado completo {A,Q,Q−1}.
7. Cuenta exactamente cuatro iteraciones.
8. Expón busy, done y el producto final de 8 bits.

Recorre la tabla de $-3\times5$ y compara cada estado posterior al desplazamiento. Un desacuerdo en la primera iteración suele indicar que se invirtió el orden del par o la polaridad de la resta; un desacuerdo después de desplazar un acumulador negativo suele indicar un desplazamiento lógico en lugar de uno aritmético.

Lista de comprobación de verificación

Para verificar exhaustivamente un multiplicador pequeño de $n$ bits, prueba los:

pares de entrada frente a un producto de referencia con signo representado en $2n$ bits.

Como mínimo, incluye:

• $0\times x$ y $1\times x$
• positivo × positivo
• positivo × negativo
• negativo × positivo
• negativo × negativo
• valores positivos máximos
• el valor más negativo $-2^{n-1}$
• $-2^{n-1}\times -1$
• patrones del multiplicador 0000, 1111, 0101 y 1010
• reinicio o rearranque mientras está ocupado

Comprueba también que:

• se producen exactamente $n$ iteraciones radix-2
• done se emite una vez por cada operación aceptada
• las entradas se capturan o el contrato exige que permanezcan estables
• el resultado no se consume antes de ser válido
• el desplazamiento combinado conserva el signo del acumulador

Una simulación funcional ideal demuestra la secuencia aritmética, no la frecuencia máxima del reloj del hardware. Usa análisis temporal estático después de asignar el diseño a su objetivo.

Sigue aprendiendo

Repasa la aritmética en complemento a 2 para la extensión de signo y el intervalo, y después compara la suma con acarreo en cascada con las estructuras de acarreo anticipado.

Andrew D. Booth introdujo el método uniforme con signo en su artículo de 1951, «A Signed Binary Multiplication Technique». La recodificación central sigue siendo relevante, pero una implementación profesional aún necesita anchuras explícitas, un contrato de latencia definido, pruebas exhaustivas con signo y análisis temporal específico del objetivo.