En este artículo vamos a aplicar la recodificación de Booth de a dos bits (radix-4) para acelerar el cómputo de multiplicaciones de enteros binarios signados en dos complemento. Y así lograr reducir el número de iteraciones a la mitad.



La recodificación de Booth surgió como una técnica para acelerar el proceso de multiplicación cuando el multiplicador presenta un tres de unos. Siendo que en la multiplicación de números enteros binarios los unos del multiplicador involucran procesamiento (sumar), mientras que los ceros no, el objetivo es transformar unos en ceros sin alterar el producto.

Suponiendo un tren de unos de longitud k, en lugar de realizar k sumas del multiplicando, la recodificación lo transforma en una suma y una resta, independientemente de la longitud del tren de unos. Esta técnica surge de la siguiente idea: en binario 15 es igual a 16 menos 1.

01111 = 10000 - 1

En el ejemplo anterior: 23 + 22 + 21 + 20 = 24 - 1.

Esta recodificación de Booth puede ser expresada en dígito signado de la siguiente forma:

10001

Donde 1 = 1 y 1 = -1.

De igual forma en que, en decimal, 9999 es igual a 10000 - 1.

Lo que intenta Booth en operación asincrónica es realizar la menor cantidad posible de sumas (una especie de skip de sumas en trenes de unos). Claro está que el beneficio se presenta sólo si el multiplicador cuenta con trenes de unos.

Sin embargo, las bondades de Booth aparecen cuando se busca recodificar de a dos bits para reducir a la mitad el número de iteraciones. Típicamente al recodificar de a más de un bit se reducen las iteraciones pero se requieren generar múltiplos del multiplicando (ya no es suma o no). Pero, cuando se combina la recodificación de a más de un bit con Booth, aparecen dos beneficios insospechados: se reduce la cantidad de múltiplos requeridos; y se soluciona automáticamente la cuestión del multiplicador negativo.

Vamos a analizar el caso de recodificar el multiplicador de a dos bits (radix-4), que es el que mayores beneficios trae pues los múltiplos necesarios para el multiplicando son triviales (se resuelven con simple shift,tal como veremos).

Para recodificar un número binario de a dos bits existen dos técnicas: mirar al futuro; o mirar al pasado (técnica de flag).

Mirando al futuro:

Mirando al pasado:

Mirando al futuro sólo requiere los múltiplos: 0; 2; -2; 4 y -4.

Por otro lado, mirando al pasado requiere: 0; 1; -1; 2 y -2.

En ambos casos, los múltiplos no triviales (0, 1 y -1) se calculan con simples shifts, con lo cual la tabla de multiplicar es trivial y no implica cómputo alguno:

  • 2x: shift a izquierda
  • -2x: shift a izquierda del dos complemento de x
  • 4x: dos shift a izquierda
  • -4x: dos shift a izquierda del dos complemento de x

Al recodificar de a dos bits, el número de iteraciones se reduce a la mitad: para operandos de 8 bits se requieren sólo 4 iteraciones del algoritmo (en lugar de 8). Mientras que la sobrecarga es mínima ya que no se requiere cómputo de múltiplos (son simples shifts).

Un ejemplo de recodificación de a dos bits de un multiplicador utilizando la técnica de Booth mirando al futuro:

y = 25 (10) = 011001 (2)

La primera iteración comienza en la posición -2 agregando dos bits virtuales (00):

En cada iteración, el bit de futuro es el siguiente bit en el multiplicador. En la última iteración se utiliza extensión de signo. Tanto la extensión de signo como los dos bits de comienzo son virtuales ya que no se requiere hardware adicional para representarlos.

Es posible comprobar que el resultado es correcto: 32x - 8x + 2x -x = 25x.

Otra cuestión que resuelve Booth de forma automática es el signo negativo en el multiplicador. Veamos un ejemplo con un multiplicador negativo de 4 bits. Con y < 0 tenemos un pseudo-positivo de valor 2n - 1 que claramente termina en unos (signo negativo).

Tratándolo como un pseudo-positivo, a la izquierda habrá un cero de terminación. Basta que Booth ignore el cero de terminación de la "magnitud" para que no se considere la última suma en el resultado y este sea correcto.

     (6)  0110     2 + 4 = 6
  Booth   1010    -2 + 8 = 6

    (-4)  1100     4 + 8 = 12
  Booth  10100   -4 + 16 = 12
         |0100   -4

Dado que codificamos sólo n (4) bits, en la posición n+1-1 (n) aparece la suma (según Booth). Al no considerarla en el resultado (por estar fuera de rango) se hace de forma automática la resta y el resultado es correcto.

Por esta razón en Booth nunca es necesario corregir cuando el multiplicador es negativo, y siempre hay que utilizar extensión de signo al hacer los dos shifts a derecha en cada iteración.

Ahora veamos un ejemplo operando como lo hace el hardware de multiplicación (ALU) trabajando con operandos de 8 bits en dos complemento:

x * y = 26 (10) * -35 (10) = 00011010 (2) * 11011101 (2)

El algoritmo procede exactamente igual que cuando se ejecuta una multiplicación de enteros binarios en dos complemento. Se carga el multiplicador (y) en MQ, el multiplicando (x) en B y se inicializa A con ceros. Excepto que esta vez, en lugar de mirar el bit menos significativo (LSB) de MQ, se miran los últimos dos bits menos significativos junto con el pasado (el cual se inicializa en 0).

Comparando ambas técnicas, mirando al pasado requiere hardware adicional, pues es necesario mantener un bit más para almacenar el pasado (que viene del descarte de shift de la iteración anterior). Mirando al futuro no requiere un bit adicional, ya que en la última iteración se utiliza extensión de signo virtual.

Ahora bien, ¿por qué no es conveniente recodificar de a más de dos bits, por ejemplo 3 (radix-8) o 4 (radix-16)? Porque al recodificar de a más de dos bits, los múltiplos requeridos dejan de ser triviales, sino que involucran un cómputo previo y no se pueden resolver con simples shifts (por ejemplo el múltiplo 3x).

Referencias


Tal vez pueda interesarte


Compartí este artículo