¿Cómo funciona el algoritmo de Booth?

No estoy completamente seguro si está preguntando sobre el algoritmo de Booth o el algoritmo de Modified Booth. Entonces, repasaré ambos.

Desde una perspectiva aritmética de computadora, para comprender el algoritmo de Booth, primero debemos comprender algunos conceptos clave:

• Representación numérica
• Multiplicación
• Multiplicación de la cabina
• Multiplicación de cabina modificada

Primero veremos la representación numérica . Probablemente conozca la representación binaria , que es cuando cada dígito tiene un peso posicional de [matemática] 2 ^ n [/ matemática], donde [matemática] n [/ matemática] es la posición indexada a cero del dígito. Por ejemplo, el número binario 0111 se vería así:

• ¿Qué computadora portátil debo comprar si quiero usarla tanto para programación como para juegos? (Menos de 75k)
• ¿Son realmente baratos los mercados mayoristas de computadoras?
• ¿Cuál sería la mejor computadora portátil con menos de 35000?
• ¿Cuál es el problema con mi computadora si no muestra nada en la pantalla pero cuando hago clic en Win + Prt Sc, tiene una pantalla y luego se apaga?
• ¿Puedo cambiar la CPU de una computadora portátil Dell?

El valor de un número binario sería la suma de los pesos posicionales donde vemos un 1. Entonces, el número binario 0111 se evaluaría a [matemáticas] 4 + 2 + 1 = 7 [/ matemáticas].

Probablemente también haya oído hablar de la representación del complemento a dos . El complemento a dos es similar al binario, excepto que el dígito más significativo tiene un peso posicional de [matemática] -2 ^ n [/ matemática], no [matemática] 2 ^ n [/ matemática]. Por ejemplo, el número 1001 de los dos se vería así:

Al igual que con el binario, el valor del número de complemento a dos es la suma de los pesos posicionales donde vemos un 1, por lo que el valor de 1001 sería [matemática] -8 + 1 = -7 [/ matemática].

Ahora veremos algo de lo que probablemente no hayas oído hablar. Con el complemento a dos, sabemos que el dígito más significativo es implícitamente negativo, aunque solo estamos usando dos valores, 1 y 0. Sin embargo, a veces es útil poder arbitrariamente hacer negativo cualquier peso posicional , y para hacer esto, necesitaremos expandir nuestra representación para incluir: [math] \ overline {1} [/ math]. Tomamos [matemáticas] \ overline {1} [/ matemáticas] para significar simplemente -1. Llamaremos a esta representación ternaria equilibrada .

Con esta representación, representaríamos -7 de la siguiente manera:

Como puede ver, cada peso posicional es positivo, y posteriormente podemos tener pesos posicionales negativos arbitrarios al poner [math] \ overline {1} [/ math] en ese peso.

Ahora, por supuesto, te das cuenta de que un número dado puede tener múltiples representaciones con este sistema. Por ejemplo, podríamos representar 7 como 0111, o podríamos representarlo como 100 [math] \ overline {1} [/ math]. Esto será importante más adelante.

Ahora que conocemos algunas formas de representar números, echemos un vistazo a cómo multiplicarlos .

Multiplicar números binarios es bastante sencillo. Si tenemos un multiplicando de 0111 (7) y un multiplicador de 0011 (3), miramos el multiplicador, y para cada peso posicional donde hay un 1, multiplicamos el multiplicando por el peso posicional (logrado a través de un cambio simple ) y sumar todos los resultados juntos. Entonces, obtienes algo como esto:

Para los números de complemento a dos, el proceso es similar, excepto por el hecho de que debemos recordar que el dígito más significativo del multiplicador es negativo. Esto significa que, si el dígito más significativo del multiplicador es un 1, debemos restar el multiplicando.

También es importante tener en cuenta que también debemos firmar-extender el multiplicando cuando hacemos nuestras sumas / restas. Entonces, como ejemplo, cuando multiplicamos 1001 (-7) por 1101 (-3), obtenemos algo como esto:

Lo importante a tener en cuenta sobre la multiplicación del complemento a dos es que el número de sumas / restas que hacemos es idéntico al número de 1 en el multiplicador . Por lo tanto, un multiplicador con diez 1 requerirá diez operaciones de suma / resta, mientras que un multiplicador con solo un 1 solo requerirá una operación de suma / resta.

Ahora podemos llegar a la multiplicación de Booth, que sirve para tratar de reducir el número de operaciones de suma / resta. La idea clave de la multiplicación de Booth es que estamos convirtiendo efectivamente nuestro multiplicador de la representación del complemento de dos en una representación ternaria equilibrada. La observación clave es lo que vimos anteriormente, que 0111 se puede representar alternativamente como 100 [math] \ overline {1} [/ math]. Como notamos anteriormente, un multiplicador de 0111 requerirá 3 operaciones de suma / resta, mientras que un multiplicador de 100 [matemática] \ overline {1} [/ matemática] requerirá solo 2 operaciones de suma / resta.

El algoritmo para convertir esto es bastante sencillo. Conceptualmente, todo lo que queremos hacer es identificar el comienzo de una cadena de 1. Cuando lo hacemos, lo convertimos a [math] \ overline {1} [/ math], y luego agregamos 0 hasta que terminemos la cadena de 1, en cuyo punto agregamos un 1. El algoritmo es así:

1. Inicializar el producto parcial a 0
2. Agregue un bit ficticio 0 al lado del bit menos significativo del multiplicador
3. A partir de los dos bits menos significativos, verifique lo siguiente:
1. Si 00, no hagas nada
2. Si 01, suma el multiplicando al producto parcial
3. si 10, reste el multiplicando del producto parcial
4. si 11, no hagas nada
4. Multiplica el multiplicando por 2
5. Mire los siguientes dos bits del multiplicador y repita los pasos 3 y 4.
6. Cuando nos quedemos sin bits multiplicadores, devuelva el producto parcial, que ahora será el producto completo

Entonces, para el ejemplo anterior de 0111 multiplicando y 0011 multiplicador, haría lo siguiente:

1. El producto parcial es 0
2. Agregar un maniquí 0: 0011 -> 0011 | 0
3. Mira los 2 bits menos significativos, que son 10
1. 10 significa que hacemos una resta, por lo que restaremos nuestro multiplicando y obtendremos un producto parcial de 1001
4. Ahora multiplicamos nuestro multiplicando por 2, dándonos 01110
5. Mira los siguientes 2 bits, que son 11
1. No hacemos nada
6. Multiplica nuestro multiplicando por 2 nuevamente, dándonos 011100
7. Mira los siguientes 2 bits, que son 01
1. Agregue nuestro multiplicando, entonces tenemos 011100 + 111001 = 010101
8. Multiplica nuestro multiplicando por 2 nuevamente, dándonos 011000
9. Nuestros dos últimos bits son 00, por lo que no hacemos nada y devolvemos 010101 como nuestra respuesta final

Escrito, la multiplicación se ve así:

El objetivo de este algoritmo es reducir el número de operaciones de suma / resta al hacer la multiplicación. Sin embargo, hay dos casos de esquina muy obvios. Si nuestro multiplicador es 010101, terminamos convirtiéndolo en 1 [matemática] \ overline {1} [/ matemática] 1 [matemática] \ overline {1} [/ matemática] 1 [matemática] \ overline {1} [/ matemática ] Esto termina dándonos 6 operaciones de suma / resta, mientras que si dejáramos el multiplicador como estaba, habríamos tenido 3 operaciones.

El otro caso es cuando nuestro multiplicador es 101011. Nuestro algoritmo convierte esto a [matemática] \ overline {1} [/ matemática] 1 [matemática] \ overline {1} [/ matemática] 10 [matemática] \ overline {1} [ /mates]. Esto nos da 5 operaciones, mientras que originalmente solo teníamos 4.

Modified Booth corrige estos dos casos mirando el multiplicador de tres dígitos a la vez. Conceptualmente, cuando vemos 010, simplemente queremos hacer una adición. De manera similar, cuando vemos 101, podemos reescribir esto como 0 [math] \ overline {1} [/ math] 0 y, en consecuencia, hacer una sola resta.

Sin embargo, existe cierta complejidad adicional en este algoritmo. Primero veamos el caso 010. Cuando vemos 010, con el algoritmo de Booth, lo habremos convertido a 1 [math] \ overline {1} [/ math] 0. Si queremos mantener la representación 010, ¿qué operación debemos hacer en el siguiente paso después de hacer la suma única? Si, por ejemplo, tenemos 0010 como nuestro segmento, los 3 bits menos significativos son 010, y los 3 bits más significativos son 001. ¿Eso significa que deberíamos hacer dos sumas?

Por supuesto que la respuesta es no . Lo que realmente queremos hacer en el próximo paso es nada . La razón por la que no queremos hacer nada es un poco difícil de explicar. Una adición típica de 001 habrá supuesto que hicimos una resta en el paso anterior. Como en realidad hicimos una suma en lugar de una resta, efectivamente ya hemos hecho la suma requerida en este paso, lo que significa que en realidad no tenemos que realizarla. Una lógica similar se puede ver con el caso 101.

Entonces, para el caso 010, después de hacer la suma, debemos reemplazar el 1 con un 0 para asegurarnos de que no hacemos nada en el siguiente paso, y del mismo modo con el caso 101, reemplazamos el 0 con un 1.

El algoritmo de la cabina modificada es así:

1. Agregue un cero ficticio en el bit menos significativo, y firme extender el bit más significativo
2. El producto parcial es 0
3. Mira los 3 bits menos significativos
1. Si 000, no hagas nada
2. Si 001, suma el multiplicando
3. Si 010, haga una suma y reemplace el 1 con un 0
4. Si 011, no hagas nada
5. Si es 100, no hagas nada
6. Si es 101, reste y reemplace el 0 con un 1
7. Si 110, haz una resta
8. Si 111, no hagas nada
4. Multiplica el multiplicando por 2
5. Mire los siguientes 3 bits del multiplicador y repita los pasos 3 y 4
6. Cuando nos quedemos sin bits, devolvemos el producto parcial, que ahora será el producto completo.

Validar este algoritmo se deja como un ejercicio para el lector, pero debería funcionar.

EDITAR:

Para ver un ejemplo del algoritmo que describí anteriormente, así como una explicación para la multiplicación de Booth radix-4, puede ir aquí:

La respuesta de Raymond Paseman a ¿Cuál es el multiplicador de Radix-2 Booth y cuál es el multiplicador de Radix-4 Booth?