Algoritmo de multiplicação de Booth

O algoritmo de multiplicação de Booth é um algoritmo de multiplicação para números binários com sinal na notação complemento de 2. O algoritmo foi inventado por Andrew D. Booth em 1951 enquanto fazia pesquisas sobre Cristalografia no Colégio Birkbeck em Bloomsbury, Londres. Booth usava calculadoras que eram mais rápidas em deslocar do que em somar e criou o algoritmo para aumentar sua velocidade. O algoritmo de Booth é interessante para o estudo de arquitetura de computadores.

Processo

Se x é a representação binária em complemento de dois do multiplicando e y a do multiplicador :

• Desenhe uma grade com 3 linhas, com x + y + 1 colunas e um espaço para cada bit. Chame as linhas de A (adição), S (subtração), e P (produto).
• Preencha os primeiros x bits de cada linha com:
  • o A: o multiplicando
  • o S: o negativo do multiplicando
  • o P: zeros
• Preencha os próximos y bits de cada linha com :
  • o A: zeros
  • o S: zeros
  • o P: o multiplicador
• Coloque zero no último bit de cada linha.

• Faça y vezes cada um destes passos:
• 1. Se os dois últimos bits do produto são...
  • o 00 or 11: não faça nada.
  • o 01: P = P + A. Ignore qualquer estouro.
  • o 10: P = P + S. Ignore qualquer estouro.
• 2. Desloque P para a direita um bit.

• Descarte o primeiro (nós contamos da direita para esquerda quando lidamos com bits) bit do produto para o resultado final.

Exemplo

Encontre 3 × -4:

• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0

• Execute o loop quatro vezes :
  1. P = 0000 1100 0. Os últimos dois bits são 00.
     • P = 0000 0110 0. Um deslocamento a direita.
  2. P = 0000 0110 0. Os últimos dois bits são 00.
     • P = 0000 0011 0. Um deslocamento a direita.
  3. P = 0000 0011 0. Os últimos dois bits são 10.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. Um deslocamento a direita.
  4. P = 1110 1001 1. Os últimos dois bits são 11.
     • P = 1111 0100 1. Um deslocamento a direita.

• O produto é 1111 0100, que representa -12.

A técnica mencionada acima é inadequada quando o multiplicando é um número negativo mais comprido que o que pode ser representado (i.e. se o multiplicando tem 8 bits então esse valor é -128). Uma correção possível para esse probelam é adicionar mais um bit a esquerda de A, S e P. Abaixo, nós demonstramos a técnica melhorada multiplicando -8 por 2 usando 4 bits para o multiplicando e o multiplicador:

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0

• Faça o loop quatro vezes:
  1. P = 0 0000 0010 0. Os últimos dois bits são 00.
     • P = 0 0000 0001 0. Deslocar a direita.
  2. P = 0 0000 0001 0. Os últimos dois bits são 10.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. Deslocar a direita.
  3. P = 0 0100 0000 1. Os últimos dois bits são 01.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. Deslocar a direita.
  4. P = 1 1110 0000 0. Os últimos dois bits são 00.
     • P = 1 1111 0000 0. Deslocar a direita.

• O produto é 11110000 (depois de descartar o primeiro e o último bit) que é -16.

Como funciona

Considere um multiplicador positivo consistindo de um bloco de 1s rodeados por 0s. Por exemplo, 00111110. O produto é dado por :

$M\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62$

onde M é o multiplicando. O número de operações podem ser reduzidas a duas, reescrevendo a mesma como

$M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62$

In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:

$(\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}$.

Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that $99=100-1$ while multiplying by 99.

This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,

$M\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58$

$M\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58$

O algoritmo de Booth segue esse esquema por executar uma adição quando encontra o primeiro dígito de um bloco de 1s (0 1) e uma subtração quando encontra o final de um bloco (1 0). Isso funciona também para númerios negativos. Quando os 1s no multiplicador são agrupados em blocos longos, o algoritmo de Booth executa menos adições e subtrações que o algoritmo normal de multiplicação.

Ligações externas

• Radix-4 Booth Encoding
• Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmatic

Referências

1. Collin, Andrew. Andrew Booth's Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
2. Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
3. Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.