Representação de Números
Aula - 5
Introdução
• A aritmética lida com operações sobre números, portanto a
representação dos números é um tópico fundamental.
• A escolha de um sistema de representação de números tem
repercussões na complexidade dos algoritmos e sobre o custo e
desempenho dos circuitos.
• Um outro aspecto é a interface com outros circuitos e a interface
humana.
Consideremos como exemplo, o sistema de números com resíduos
(Residue Number Systems, RNS) que permite uma implementação muito
rápida e circuitos aritméticos custo-efetivos. Não obstante, o RNS necessita
de um certo tipo de interface de entrada e saída de custo relativamente alto,
e conversores AD e DA não entendem esse tipo de representação. Assim,
o uso de RNS é limitado a casos em que o custo extra de codificação e
decodificação RNS seja desprezível com respeito ao custo total.
• Neste capítulo, os sistemas de representação de números mais
comuns são descritos.
• O capítulo é dividido em 3 seções correspondentes aos números
naturais, inteiros e reais.
Números naturais
– Sistemas ponderados
• Qualquer número natural (inteiro não negativo) pode ser representado
numa única forma, de soma de potências Bi de certo número natural B,
maior que 1, cada uma das quais multiplicada por um número natural
menor que B.
x
– O seguinte teorema define um sistema
de numeração de base-B.
– Teorema. Dado um número natural B maior que 1, qualquer número
natural x menor que Bn pode ser expresso na forma
x  xn1.Bn1  xn2 .Bn2  ... x0 .B0
onde cada coeficiente xi é um número natural menor que B.
E existe somente um vetor ( xn1 xn2 ...x0 ) representando x .
Algoritmo para computar xi
(algoritmo 3.1)
•
•
For i in 0..n-1 loop x(i):= x mod B; x := x/B; end loop;
Exemplo: Computar a representação hexadecimal de 287645.
n=0
287645 = 17977.16 + 13
B
x(i)=xmodB
x = x/B
n = n-1
17977 = 1123.16 + 9
1123 = 70.16 + 3
70 = 4.16 + 6
4 = 0.16 + 4
287645 = 4.164 + 6.163 + 3.162 + 9.161 + 13.160 = [4639D]base16.
Sistema de numeração misto, com
várias bases
(mixed-radix system)
•
Exemplo: o sistema de tempo expresso em dias, horas, minutos, segundos e
milisegundos.
•
Teorema (3.2): dados n números naturais bn1 , bn2 ,...,b0 maiores que 1,
qualquer número natural x menor que B  b  b  ... b
pode ser expresso
n
n1
n2
0
na forma
x  xn1.Bn1  xn2 .Bn2  ... x0 .B0
onde
B0  1, B1  b0 , B2  b1  b0 ,...,Bn1  bn2  bn3  ... b0
e cada coeficiente xi é um número natural menor que bi.
E existe somente um vetor xn1 xn2 ...x0
representando x.
•
Nota-se que na Base-B, os pesos são Bi, enquanto que no sistema misto os pesos
são dados por:
Bi  bi 1  bi 2  ... b0
Algoritmo 3.2
(para computar os coeficientes xi num sistema de numeração misto)
for i in 0..n-1 loop x(i) := x mod b(i); x := x /b(i); end loop;
Exemplo:
computar a representação de 287645 na base mista (13,12,15,11,12):
i=0
287645 = 23970.12 + 5
x/b(i)
b(i)
x mod b(i)
23970 = 2179.11 + 1
2179 = 145.15 + 4
145 = 12.12 +1
i = n-1 12 = 0.13 + 12
287645 = 12. (12.15.11.12) + 1.(15.11.12) + 4.(11.12) + 1.12 + 5
Comentário
•
•
Dado um número natural s, a conversão de uma representação na base B de x, a uma
representação base Bs, e vice-versa, é direta.
Supõe-se que n = s.q (se n não for divisível por s, então
zeros
iniciais devem ser adicionados. Então,
n / s.s  n
onde
x  X q1.(Bs )q1  X q2 .(Bs )q2  ... X 0 .(Bs )0
X i  xi.ss1.Bs1  xi.ss2 .Bs2  ... xi.s .B0
Como exemplo, a representação binária de um número decimal 287645 é
01000110001110011101.
A conversão para a representação hexadecimal é direta:
[0100 0110 0011 1001 1101] base 2 = [4639D] base 16.
n = 20, s = 4 e 20 = 4. q, portanto q = 5.
X4 = x4x4 + 4 -1 B4-1+ x4.4 +4-2 B4-2+x4.4 +4-3 B4-3+x 4.4 B0
X4 = x19 B3+ x18 B2+x17 B1+x16 B0
X4 = 0.23+ 1.22+0.21+0.20
X4 = 4
X4
Sistema numérico de resíduos (RNS)
Um RNS é definido por um conjunto de s valores módulo[mi].
Se os mis são primos entre si, o RNS é dito não-redundante.
A representação RNS de um dado número natural é um vetor R(N), cujos
componentes ri são os respectivos resíduos módulo mi, isto é, os
sucessivos restos da divisão inteira de N/mi
ri = N mod mi.
O mínimo múltiplo comum de {mi} é o intervalo de RNS, geralmente denotado
por M.
O maior número natural que pode ser representado em RNS definido por {mi}
é
M – 1 = (m1-1, m2-1,...,ms-1).
Se os mis são primos entre si então
M  1is mi
Exemplo
• Seja {mi} = {31, 17, 7, 5, 3} e N = (789)10. Computar {ri}
• Solução:
s = 5;
ri = N mod mi
r1 = 789 mod 3 = 0
r2 = 789 mod 5 = 4
r3 = 789 mod 7 = 5
r4 = 789 mod 17 = 7
r5 = 789 mod 31 = 14
(789)10 = (14,7,5,4, 0) RNS
Como mis são primos entre si,
M  1i  s mi
 m1.m2 .m3 .m4 .m5
 3.5.7.17.31
 55335
onde M é o mínimo múltiplo comum de {mi}.
Representação de Inteiros
•
•
Representação sinal e magnitude – um inteiro pode ser representado na
forma +x ou –x, onde x é um número natural. O número natural x pode ser
representado na base B e ao invés de usar os símbolos + e -, é usado um
dígito adicional de sinal igual a 0 (número positivo) e 1 (número negativo).
Definição:
O inteiro representado na forma xn1 xn2 ...x1 x0 onde xn-1 é o bit de
sinal é
x .Bn2  x .Bn3  ... x .B0 se x  0 e

n 2
n3
0
 xn2 .Bn2  xn3.Bn3  ... x0 .B0

n1
se xn1  1
O intervalo de números representados é
 B n1  x  B n1
•
É uma forma natural de representar um número inteiro. Não obstante, não é
a forma mais conveniente.
Representação excesso de E
•
Uma outra forma de representar um número inteiro x consiste em
associar um número natural R(x) a x, onde R é uma função um-a-um, e
R(x) é representada na base B.
•
Definição 3.3: no sistema de numeração excesso de E, onde E é um
número natural,
R(x) = x + E
tal que o inteiro representado na forma xn1 xn2 ...x1 x0
seja
xn1.Bn1  xn2 .Bn2  ... x0 .B0  E
e o intervalo de números representados,
 E  x  Bn  E
Comentários sobre excesso de E
•
Se B é par, e E é escolhido igual a Bn/2, então, o número representado
na forma xn1 xn2 ...x1 x0 é
xn1.B n1  xn 2 .B n 2  ...  x0 .B 0  E
 ( xn1  B / 2).B n 1  xn2 .B n2  ...  x0 .B 0
•
A regra de definição do sinal é: se x é negativo então xn1  B / 2
e se x é positivo xn1  B / 2
•
Em alguns casos práticos, o valor de E é diferente de Bn/2. Como
exemplo, no sistema de ponto-flutuante de precisão simples ANSI/IEEE
o expoente é um número de 8 bits que representa um inteiro x no
intervalo
 127  x  128
de acordo com o método excesso de E com E = 127 e não Bn/2=128.
Comentários (cont.)
•
Se B= 2 e E = 2n-1, então o número representado na forma
xn1 xn2 ...x1 x0
é
( xn1  1).2n1  xn2 .2n2  ...  x0
  x'n1.2n1  xn2 .2n2  ...  x0
onde
•
x'n1
significa o complemento de
xn 1
A função de representação R é unate, tal que a comparação de
magnitude é fácil.
Função binária unate positiva é tal que se aplicar o valor 1 a um bit, o valor da função
é maior ou igual que a aplicação do valor 0 no mesmo bit, desde que os demais bits
sejam iguais.
Exemplo
• Representar x = -287645 com n = 6 dígitos na base B = 10 com E =
106/2.
B6 =106= 1000000
E = B6/2 = 106/2= 500000
R(x) = x + E = – 287645 + 500000 = 212355
• Observa-se que:
(2-10/2).105 + 12355 = - 300000 + 12355 = - 287645
E
212355 – 500000= 2x105+12355 – 500000
Número em excesso de E
Representação Complemento de B
É obtido um número natural R(x), aplicando uma função um-a-um a x.
Definição: No sistema de numeração complemento de B, cada inteiro x,
pertencente ao intervalo  B n / 2  x  B n / 2
é representado pelo
número natural
n
R( x)  x modB
tal que o inteiro representado na forma
xn1 xn2 ...x1 x0 seja
xn1.Bn1  xn2 .Bn2  ... x0
se
e
positivo
xn1.Bn1  xn2 .Bn2  ... x0  Bn / 2
xn1.Bn1  xn2 .Bn2  ... x0  Bn
se
xn1.Bn1  xn2 .Bn2  ... x0  Bn / 2
negativo
Essas condições podem ser reescritas na forma:
xn1.Bn1  xn2 .Bn2  ... x0
se
e
( xn1  B / 2).Bn1  xn2 .Bn2  ... x0  0
positivo
xn1.Bn1  xn2 .Bn2  ... x0  Bn
negativo
se
( xn1  B / 2).Bn1  xn2 .Bn2  ... x0  0
E se B é par, as últimas condições são equivalentes a:
e
xn1.Bn1  xn2 .Bn2  ... x0
se
xn1  B / 2
xn1.Bn1  xn2 .Bn2  ... x0  Bn
se
xn1  B / 2
Complemento de 2
Se B = 2, o número representado por
xn1 xn2 ...x1 x0 é
 xn1.2n1  xn2 .Bn2  ... x0
e o bit mais significativo xn 1 é também o bit de sinal.
Se
x  0 então xn1  1
e se
x  0 então xn1  0
comentários
O sistema complemento de B é baseado na operação, a saber
R(x) = x mod Bn.
Para representar um número de n dígitos com n+1 dígitos (extensão do
número), a seguinte regra deve ser usada (B par):
Se
xn1  B / 2 então xn  B 1
e se
xn1  B / 2 então xn  0
Se B = 2, o vetor de n+1 bit
número como o vetor de n bit
xn1 xn1 xn2 ...x1x0
xn1 xn2 ...x1 x0
representa o mesmo
Sistema de numeração
complemento de B reduzido
•
•
Num sistema de numeração complemento de B reduzido, o dígito mais
significativo xn-1 é 0 ou B-1.
Definição: no sistema de numeração complemento de B reduzido (B par),
cada inteiro x pertencente ao intervalo  B n1  x  B n1 é representado por
R( x)  x modBn
•
Se
0  x  B n1
então
R( x)  x  Bn1 e xn1  0
•
e se  B
n 1
 x0
então
R( x)  Bn  x  Bn  Bn1  (B 1).Bn1 e xn1  B 1
Sistema de numeração
complemento de B reduzido (cont.)
Assim, o inteiro representado por
xn1 xn2 ...x1 x0 é
x  Bn1  xn2 .Bn2  ... x0 se xn1  B 1
e
x  xn2 .Bn2  ... x0 se xn1  0
e a regra de definição de sinal é a seguinte:
se x é negativo,
xn1  B 1
e se x é positivo,
xn1  0 .
De fato, o sistema complemento de B reduzido é obtido da representação
complemento de B adicionando um dígito, se o dígito mais significativo é
diferente de 0 ou B-1.
Exemplo
Representar x = -287645 com n = 6 dígitos em complemento de B com B = 10.
B6 = 1000000
B6/2 = 500000
R(x) = x + B6 = 712355
Observa-se que
x’5 = 7 – 10 = -3
-3.105 + 12355 = -287645
No sistema complemento de B reduzido, n = 7 dígitos são necessários:
( -287645 < -Bn-1=-100000 ):
R(x) = x + B7 = 9712355.
Observa-se que -106 + 712355 = -287645 e que 9712355 é deduzido de
712355 adicionando um dígito de acordo com a regra de extensão.
Codificação de Booth
xn1 xn2 ...x1 x0
A representação complemento de 2,
, de um inteiro x
pode ser vista como uma representação com dígito de sinal.
xn1.2n1  xn2 .2n2  ... x0
onde
xn1 {1,0}
e todos os outros dígitos
xi {0,1}
A codificação de Booth gera uma outra representação com dígito de sinal.
Definição: Considera-se um inteiro x cuja representação complemento de 2 é
xn1 xn2 ...x1 x0 e define-se
y0   x0 ,
y1   x1  x0 ,
y2   x2  x1 ,
........
yn 1   xn 1  xn  2 .
Codificação de Booth
•
Então, multiplicando a primeira equação por 20, a segunda por 21, e
terceira por 22, e assim por diante, e adicionando as n equações, é obtida
a seguinte equação:
yn 1.2n 1  yn 2 .2n 2  ...  y0 .20 
  xn 1.2n 1  xn 2 .2n 2  ...  x0 .20
•
O vetor ( yn1 yn2 ...  y0 ) cujos componentes yi pertencem a {-1,0,1}
é a representação Booth-1 de x e
x  yn1.2n1  yn2 .2n2  ... y0 .20
•
Observa-se que a representação de Booth de um inteiro é formalmente a
mesma de uma representação binária de um número natural. O método
de codificação de Booth pode ser generalizado.
Codificação Booth-2
Definição: considerar um inteiro cuja representação em complemento de 2 é
xn1 xn2 ...x1 x0 com n = 2.m bits, e definir
y0  2.x1  x0 ,
y1  2.x3  x2  x1 ,
y2  2.x5  x4  x3 ,
........
ym 1  2.x2.m 1  x2.m  2  x2.m 3
Multiplicando a primeira equação por 40, a segunda por 41, a terceira por 42, e
assim por diante, e adicionando m equações, a seguinte equação é obtida:
ym1.4m1  ym2 .4m2  ...  y0 .40 
  xn 1.2n 1  xn 2 .2n 2  ...  x0 .20
( ym1 ym2 ...y1 y0 ) cujos componentes yi pertencem a {-2,-1,0,1,2} é a
O vetor
representação Booth-2 de x e
x  ym1.4m1  ym2 .4m2  ... y0 .40
Codificação Booth-r
Definição: considerar um inteiro x cuja representação em complemento de 2 é
xn1 xn2 ...x1 x0 com n = r.m bits, e definir
y0   xr 1.2 r 1  xr  2 .2 r  2  ...  x1.2  x0 ,
yi   xi.r  r 1.2 r 1  xi.r  r  2 .2 r  2  ...  xi.r 1.2  xi.r 
 xi.r 1 , i  {1,2,...,m  1}
O vetor ( ym1 ym2 ...y1 y0 )
 2
r 1
cujos componentes yi pertencem a
,(2r 1 1),...,2,1,0,1,2,...,2r 1 1,2r 1
é a representação Booth-r de x e
x  ym1.Bm1  ym2 .Bm2  ... y0 .B0
onde B=2r.

Exemplo
Computar a codificação de Booth de -287645, cuja representação
complemento de 2 é:
10111001110001100011
De acordo com a representação Booth-1 é
-1100-10100-10010-10010-1
e de acordo cm a representação Booth-2 é
-10-22-102-21-1
Números reais
• Para números reais, existem dois tipos de abordagens de sistemas
de numeração: ponto fixo e ponto flutuante.
• O sistema ponto fixo é uma simples extensão da representação de
números inteiros, que permite a representação de um intervalo
relativamente reduzido de números com certa precisão absoluta.
• O sistema ponto flutuante permite uma representação de um
intervalo muito grande de números, com uma precisão relativa.
Sistema de numeração ponto-fixo
No sistema de numeração ponto-fixo, o número representado na forma:
xn p1xn p2 ...x1x0 . x1x2 ...x p
é x/Bp onde x é o inteiro representado pela mesma sequência de dígitos
sem o ponto.
Seja xmin e xmax os inteiros mínimo e máximo que podem ser
representados com n dígitos, isto é, xmin = 1 – Bn-1 e xmax = Bn-1 -1 na
representação sinal e magnitude, e xmin = -Bn/2 e xmax = Bn/2 -1 em
complemento de B ou excesso de Bn/2. Então, qualquer número real x
no intervalo
B p . xmin  x  B p . xmax
pode ser representado com erro igual ao valor absoluto da diferença
entre x e sua representação.
A distância d entre os números exatamente representados é igual à
unidade na posição menos significativa (unit in the least significant
position – ulp), isto é, B-p, tal que o erro máximo seja igual a
ulp / 2  B  p / 2
p
O erro relativo máximo é igual a ulp /(2. x )  1/(2. x B ) . Se x  0
1
então x  B  p tal que o erro relativo máximo seja menor ou igual a
2
exemplo
O intervalo de números x que podem ser representados em complemento de
B com B = 10, n = 9 dígitos, e ulp = 10-3 é
 106 / 2  x  106 / 2
Os seguintes números podem ser representados exatamente:
-500000.000, -499999.99, - 499999.998,...,-0.001, 0.000, 0.001, ...,
499999.999.
A distância entre eles é igual a ulp = 0.001.
Sistema de numeração ponto- flutuante
Num sistema de numeração ponto-flutuante, a representação consiste de dois
números: um número em ponto-fixo ( significando) +s ou –s, onde s é um
número positivo, e um expoente (inteiro) e. O número correspondente é  s.b e
onde b é a base (não-necessariamente igual a B).
Seja smin, smax, emin e emax os valores mínimo e máximo de s e e respectivamente. O
intervalo de números representados é
 smax.bemax  x  smax.bemax
e o valor absoluto mínimo de um número representado é
x  smin.bemin
Seja ulp a unidade na posição menos significativa do significando. Então a distância
D entre os números exatamente representados é D = d.be, onde d = ulp é a
distância entre dois valores sucessivos do significando. Assim, o valor de D
depende do expoente e. O erro máximo é igual a
Dmax / 2  ulp.bemax / 2
O erro relativo máximo é igual a D /(2. x )  ulp.be /(2.s.be )  ulp / 2.s
1
Como no caso anterior, o erro relativo máximo é menor ou igual a
2
exemplo
No sistema de ponto-flutuante de precisão simples ANSI/IEEE, o significando é
um inteiro representado em sinal e magnitude
 s  1.s1s2 ...s23
onde s1s2 ...s23
é chamado mantissa, e o expoente
inteiro em excesso de 127.
A palavra de 32 bits
e7e6 ...e0
sign e7e6 ...e0 s1s2 ...s23
representa o número
(1) sign .(1  s1.21  s2 .22  ... s23 .223 ).2e
onde
Assim
e  e7 .27  e6 .26  ... e0 .20 127
smin  1, smax  1.11...1  2, ulp  223 , emin  127, emax  128
é um
Apesar de emin e emax não serem usados para representarem números
ordinários, eles são usados para representar
0  1.0  2127 ,  0  1.0  2127 ,    1.0  2128 ,    1.0  2128
e outros números não-ordinários. Os valores mínimo e máximo são:
emin  126, emax  127
tais que o intervalo de números representados seja
isto é
 2128  x  2128
e o menor número positivo representado é 1.2-126.
 2.2127  x  2.2127