Dados
e
, na notação em complemento de dois (isto é,
e
), calcule o resultado de
usando o algoritmo de Booth.
Passo 1
O enunciado dá:
e
na notação em complemento de dois (isto é,
e
). Pede-se calcular
usando o algoritmo de Booth.
Informações relevantes que temos de início:
Informações relevantes que temos de início:
- Representações em 4 bits:
, . - Vamos trabalhar com multiplicador
e multiplicando . - O resultado final deve caber em 8 bits (concatenação de dois registradores de 4 bits:
e ).
Passo 2
O algoritmo de Booth (modo clássico para multiplicação com sinais) usa estes registros:
-
: acumulador, inicializado em (4 bits aqui). -
: registrador do multiplicador (inicialmente ). -
: bit extra inicializado em . -
: multiplicando (aqui ).
Regras por iteração (olhando o par, onde é o bit menos significativo de ): -
ou : não faz operação em . -
: faz . -
: faz (equivalente a ).
Depois da operação (ou se não houver operação) faz-se uma rotação à direita aritmética no bloco(ou seja, deslocamento à direita com réplica do bit de sinal de ). Repetir por iterações (aqui ).
Passo 3
Configuração inicial:
Precisamos também de
em complemento de dois (4 bits). Para obter
:
inverte-se e soma-se
:
inverte-se
Logo
. Vou executar 4 iterações; em cada iteração mostro
, a operação feita, o novo
antes do shift, e o resultado do shift (novo
).
Passo 4
Iteração 1 (antes):
.
Pegamos e
→ par
→ não faz operação em
. Portanto
permanece
.
Agora faz-se o deslocamento aritmético à direita em :
concatenação antes do shift: . Deslocando à direita (com sinal de
= 0):
Pegamos
Agora faz-se o deslocamento aritmético à direita em
concatenação antes do shift:
- novo
, - novo
, - novo
.
Resumo Iteração 1 (depois do shift):.
Passo 5
Iteração 2 (antes):
.
Aqui e
→ par
→ subtrair
(ou somar
). Calculamos:
Aqui
Agora faz-se o deslocamento aritmético à direita de
:
- novo
, - novo
, - novo
.
Resumo Iteração 2 (depois do shift):.
Passo 6
Iteração 3 (antes):
.
Agora e
→ par
→ somar
. Calculamos:
Agora
Fazendo a soma bit a bit (sem expandir para mais bits):
-
(em 4 bits; carry final é descartado). Observação decimal: , que bate com .
Agora deslocamento aritmético à direita de: - novo
, - novo
, - novo
.
Resumo Iteração 3 (depois do shift):.
Passo 7
Iteração 4 (antes):
.
Aqui e
→ par
→ subtrair
novamente:
Aqui
(Confirmação decimal:
→
.)
Faz-se o deslocamento aritmético à direita final de :
Faz-se o deslocamento aritmético à direita final de
- novo
, - novo
, - novo
.
Resumo Iteração 4 (depois do shift):.
Passo 8
O algoritmo terminou após
iterações. O produto final
está na concatenação
seguido de
(8 bits):
Para verificar o valor decimal: em complemento de dois com 8 bits
representa um número negativo. Calculando seu valor:
inverter , somar
que é
em decimal, logo o número é
. Isso confere com
.
inverter