Aritmética
Representação de números
1
Representação de inteiros

Números inteiros com sinal


A representação mais comum é a representação em
complemento para 2

Boas propriedades para adição e subtracção

Como já viram em AC I...
No entanto existem outras formas de representar:

Magnitude

Complemento para 1

Excesso m
2
Representação de inteiros

Magnitude

1 bit de sinal seguido do valor absoluto do número

Exemplos (em 8 bits)
0 0000 0000
-0 1000 0000
1 0000 0001
-1 1000 0001
41 0010 1001
-41 1010 1001
78 0100 1110
-78 1100 1110
OBS:
A notação não tem boas propriedades para a adição:
se fizer N + (-N) o resultado não dá 0...
O ‘0’ pode ter duas representações diferentes...
3
Representação de inteiros

Complemento para 1

O simétrico é a negação bit a bit

Exemplos (em 8 bits)
0 0000 0000
-0 1111 1111
1 0000 0001
-1 1111 1110
41 0010 1001
-41 1101 0110
78 0100 1110
-78 1011 0001
OBS:
Boas propriedades para adição,
mas o ‘0’ pode ter duas representações diferentes...
4
Representação de inteiros

Excesso m

Representa-se o valor do número acrescido de m

O menor número vale –m e é representado por 0’s

Exemplo: excesso 128 (8 bits)
0 1000 0000
-0 1000 0000
1 1000 0001
-1 0111 1111
41 1010 1001
-41 0101 0111
78 1100 1110
-78 0011 0010
OBS:
Quando m=2n-1 fica semelhante ao complemento para 2,
mas com o bit de sinal trocado
5
Representação de inteiros


Apesar de muito utilizada, a notação em complemento
para 2 também tem um defeito:

Existe mais um número negativo do que o número de positivos

No caso da notação excesso-m, esse desequilíbrio pode ainda
ser maior
No entanto, não existe nenhuma notação “ideal”:

o zero ter um única representação

existirem tantos números negativos como positivos

ter boas propriedades para adição/subtracção
6
Representação de números reais

Norma IEEE 754 (versão mais recente: Ago/2008)

Até meados dos anos 80, a representação de números reais não
estava normalizada...

Cada fabricante usava a sua representação

Para ultrapassar problemas de compatibilidade, surgiu em 1985
a primeira versão da norma IEEE 754

A norma define:

Os formatos de representação dos números reais

Como devem ser feitos os arredondamentos

Como devem ser feitas as operações

Tratamento de excepções (ex: divisão por zero, underflow, overflow)

…
7
Representação de números reais

Formato de um número real (virgula flutuante)

Precisão simples – 32 bits – float

1 bit que define o sinal (0 – positivo; 1 – negativo)

8 bits para o expoente (representado em excesso 127)

23 bits para a mantissa, representada em magnitude
1
Bit de
sinal
8 bits
23 bits
Expoente
Mantissa
32 bits
Valor do número: (-1)sinal  1.mantissa  2expoente
8
Representação de números reais

Exemplo:
Qual será o valor do número real C160 0000(hex)?
1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
expoente
mantissa
sinal
Sinal = 1  número negativo
Expoente = 1000 0010 = 130
 o expoente vale 3 (não esquecer que está em excesso 127)
Mantissa = 0.1100 0000 … = 2-1 + 2-2 = 0.5 + 0.25 = 0.75
O valor do número será então:
–1.75  23 = –14.0
9
Representação de números reais

Significados especiais
Expoente
Mantissa
Valor
Obs.
–127
== 0
0
128
== 0
 infinito
Depende do sinal
128
!= 0
NaN (not a number)
Valores não reais
–127
!= 0
0.mantissa  2-126
Forma desnormalizada
Exemplos:
0000 0000(hex) = 0.0
7F80 0000(hex) = +
FFFF FFFF(hex) = NaN
0040 0000(hex) = 0.5 * 2-126
10
Representação de números reais

Precisão dupla – double

Obtêm-se os valores de forma idêntica, mas




os números são representados em 64 bits
com 11 bits para o expoente (em excesso 1023)
e 52 bits para a mantissa
Gamas de representação (na forma normal)

Precisão simples


  1.2  10-38 a 3.4  1038
Precisão dupla

  2.2  10-308 a 1.8  10308
11
Aritmética
Multiplicação binária
12
Multiplicação binária

Multiplicação (sem sinal)
1101
multiplicando (A)
× 1010
multiplicador (B)
0000
1101
0000
1101
10000010
produto (P)
Quando se multiplicam dois números
de n bits (sem sinal), o resultado
terá, no máximo, 2n bits.
1101 (13) × 1010 (10) = 10000010 (130)
13
Multiplicação binária

Multiplicação (sem sinal)
A3
A2
A1
A0
B3
B2
B1
B0
B0A3
B0A2
B0A1
B0A0
B1A3
B1A2
B1A1
B1A0
B2A3
B2A2
B2A1
B2A0
B3A3
B3A2
B3A1
B3A0
P6
P5
P4
P3
×
P7
P2
ANDs entre os
bits de A e os
bits de B
P1
P0
14
Multiplicação binária

Utilizando vários adicionadores...
A3
A2
A1
A0
×
B3
B2
B1
B0
0
B0A3
B0A2
B0A1
B0A0
+
B1A3
B1A2
B1A1
B1A0
cout1
S13
S12
S11
S10
+
B2A3
B2A2
B2A1
B2A0
cout2
S23
S22
S21
S20
+
B3A3
B3A2
B3A1
B3A0
cout3
S33
S32
S31
S30
P7
P6
P5
P4
P3
Somadores
P2
P1
P0
15
Multiplicação binária
A3 A2 A1 A0
B0
Pode-se seguir
esta estrutura
A3 A2 A1 A0
B1
X
A3 A2 A1 A0
Cout
B2
Cout
B3
ADD
Y
S
X
A3 A2 A1 A0
0
ADD
Y
S
X
Cout
ADD
Y
S
P7 P6 P5 P4 P3 P2 P1 P0
16
Multiplicação binária

Utilização de vários adicionadores

Se os números a multiplicar são compostos por n bits
então são necessários n – 1 adicionadores de n bits
cada um

Eventuais problemas:

Excesso de material


por exemplo, para multiplicar dois números de 32 bits seriam
necessários 31 somadores de 32 bits
Demasiado consumo de tempo durante um ciclo

Num processador, ter um multiplicador deste género pode
aumentar de forma significativa a duração de cada ciclo, devido
aos tempos de propagação dos somadores
17
Multiplicação binária

Alternativa: usar um único somador e registos

O adicionador efectua todas as adições necessárias
em n ciclos

É necessário:

Um registo para acumular as somas – RP

Um registo de deslocamento para a esquerda e outro para a
direita – RA e RB

RP e RA são registos de 2n bits

para RB, um registo de n bits é suficiente
18
Multiplicação binária

Algoritmo básico (para inteiros sem sinal)

Inicialização:
RP ← 0, RA ← A, RB ← B

Ciclo (n iterações)
se ( RB0 == 1 )
// bit menos significativo em RB
RP ← RP + RA
RA ← RA << 1, RB ← RB >> 1

No final, o resultado da multiplicação está em RP
19
Multiplicação binária

Hardware para o algoritmo básico
B
A
Shift right
Shift left
RB
RA
RB0
ADD
Load
RP
20
Multiplicação binária

Exemplo – multiplicar 1010 por 1001 (i.e. 109)
Inicialização:
RP: 0000 0000
RA: 0000 1010
RB: 1001
Ciclo 3 (RB0 = 0)
RP: 0000 1010
RA: 0101 0000
RB: 0001
Ciclo 1 (RB0 = 1)
RP: 0000 1010
RA: 0001 0100
RB: 0100
Ciclo 4 (RB0 = 1)
RP: 0101 1010
RA: 1010 0000
RB: 0000
Ciclo 2 (RB0 = 0)
RP: 0000 1010
RA: 0010 1000
RB: 0010
O resultado será então:
RP: 01011010 = 21+23+24+26 = 2+8+16+64 = 90
21
Aritmética
Aceleração da adição
22
Adição básica (Ripple-carry)

Um circuito full adder (dado em AC1)
A
B
Cin
S
Cout
Soma os bits A e B com o transporte anterior (Cin), dando
o resultado da soma (S) e o transporte que sai (Cout)
23
Adição básica (Ripple-carry)

Adicionador Ripple-carry de n bits
A0
B0
FA
C0
S0

A1
C1
B1
FA
S1
A2
C2
B2
FA
S2
A3
C3
B3
FA
C4
S3
Problema:


Os transportes (Ci’s) têm que se propagar entre os full adders
Admitindo que cada full adder impõe um atraso, o tempo
necessário para ser feita a soma será proporcional a n
24
Adição básica (Ripple-carry)

Outra maneira de ver
PFA
A
B
Cin
S
Cout
PFA – Partial Full Adder
25
Adição básica (Ripple-carry)

Outra maneira de ver
A
B
PFA
Cin
P
G
S
Cout
Em que:
Propagação de carry
Geração de carry
P  AB
G  AB
26
Adição básica (Ripple-carry)

Para um ripple adder de 4 bits
A0
B0
PFA
C0
P0
G0
A1
S0
C1
B1
PFA
P1
G1
A2
S1
C2
B2
PFA
P2
G2
A3
S2
C3
B3
PFA
P3
S3
G3
C4
P’s e G’s podem ser calculados em paralelo (ao mesmo tempo)
As somas (os S’s) têm que esperar que chegue o Ci respectivo
27
Adição básica (Ripple-carry)

Para um ripple adder de 4 bits
A0
B0
PFA
C0
P0
G0
A1
S0
C1
B1
PFA
P1
G1
A2
S1
C2
B2
PFA
P2
G2
A3
S2
C3
B3
PFA
P3
S3
G3
C4
Caminho crítico – corresponde ao pior caso na propagação dos sinais
Tipicamente é o que atravessa mais portas lógicas
28
Acelerar a adição

Genericamente tem-se:
Ci 1  Gi  Pi Ci
Gi  Ai Bi
Pi  Ai  Bi
C1  G0  P0C0
C2  G1  P1C1
 G1  P1 G0  P0C0  
 G1  P1G0  P1P0C0
C3  G2  P2C2
 G2  P2 G1  P1C1  
 G2  P2 G1  P1 G0  P0C0  
 G2  P2G1  P2P1G0  P2P1P0C0
C4  ...
29
Acelerar a adição

Com base nessas equações obtém-se:
A0
B0
PFA
C0
P0
G0
A1
S0
C1
B1
PFA
P1
A2
S1
G1
B2
PFA
P2
A3
S2
G2
B3
PFA
P3
S3
G3
C2
C3
C4
30
Adicionador Carry Lookahead

Este tipo de adicionador designa-se por
carry lookahead adder (CLA)

Repare no atraso associado à propagação do carry


neste caso corresponde ao de 2 portas lógicas
E se quisesse construir um CLA de 8 bits ?


Problema com o desenho anterior:

para calcular carrys de ordem elevada (e.g. C7) precisaria de portas
lógicas com muitas entradas...

...difícil de implementar na prática
Uma abordagem mais realista seria usar portas com 2 entradas
31
Adicionador Carry Lookahead
A0
C0
B0
A1
S0
PFA
P0
G0
P01
B1
A2
S1
PFA
C1
P1
G1
G01
B2
A3
S2
PFA
P2
P23
G2
B3
S3
PFA
C3
P3
G3
G23
C2
P03
G03
C4
32
Adicionador Carry Lookahead
A0
C0
B0
A1
S0
PFA
P0
G0
P01
B1
A2
S1
PFA
C1
P1
G1
G01
B2
A3
S2
PFA
P2
P23
G2
B3
S3
PFA
C3
P3
G3
G23
C2
P03
G03
O caminho crítico está representado a vermelho
C4
33
Adicionador Carry Lookahead
A0
C0
B0
PFA
A1
S0
B1
PFA
A2
S1
B2
PFA
A3
S2
B3
PFA
A4
S3
B4
PFA
A5
S4
B5
PFA
A6
S5
B6
PFA
A7
S6
B7
PFA
S7
C8
34
Adicionador Carry Lookahead

Comparação entre os adicionadores:
(supondo que apenas são utilizadas portas lógicas com 2 entradas)
Ripple-carry
CLA
Nº de bits
Tempo
Nº de portas
Tempo
Nº de portas
4
9tPD
20
7tPD
29
8
17tPD
40
11tPD
61
16
33tPD
80
15tPD
125
32
65tPD
160
19tPD
253
64
129tPD
320
23tPD
509
128
257tPD
640
27tPD
1021
35
Outros adicionadores


Carry select adder

A ideia consiste em preparar somas parciais para
ambas as hipóteses de carry in

O carry out do bloco anterior irá seleccionar qual dos
2 resultados é válido
Carry skip adder

Composto por vários blocos onde são calculados os
P’s, mas não os G’s

Os P’s são utilizados para propagar o carry ao bloco
seguinte
36
Outros adicionadores

Carry select adder (8 bits)
A0...A3
0
Cin
B0...B3
4-bit
adder
Cout
A4...A7
0
Cin
B4...B7
4-bit
adder
1
0
Sel
Sel.
S0...S3
Cin
4-bit
adder
1
Mux
S4...S7
37
Outros adicionadores

Carry skip adder (16 bits)
A0..A3
C0
Ci
B0..B3
4-bit
adder
Co
A4..A7
Ci
B4..B7
4-bit
adder
Co
P4,7
S0..S3
S4..S7
A8..A11
Ci
B8..B11
4-bit
adder
Co
A12..A15 B12..B15
Ci
4-bit
adder
Co
C16
P8,11
S8..S11
S12..S15
38
Síntese

Evolução do tempo necessário para fazer uma soma de
dois números representados com n bits
Adicionador
Tempo
Ripple
O(n)
Carry lookahead
O(log2 n)
Carry skip
O(√n)
Carry select
O(√n)
n – número de bits
O(x) – significa “evolui proporcionalmente com a grandeza x”
39
Síntese
Adicionadores (tempos)
300
Ripple
Tempo (x tPD )
250
CLA
200
Select
150
Skip
100
50
0
0
32
64
96
128
Número de bits
40
Síntese
Número de portas lógicas
Adicionadores (número de portas)
2000
Ripple
CLA
1500
Select
1000
Skip
500
0
0
32
64
96
128
Número de bits
41