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.

– 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 menor que Bn pode ser expresso na forma

onde cada coeficiente é um número natural menor que B. E existe somente um vetor ( ) representando .

00

22

11 ...... BxBxBxx n

nn

n

ix021 ...xxx nn

x

x

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.

287645 = 17977.16 + 13

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.

x(i)=xmodB

x = x/B

n = 0

n = n-1

B

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 maiores que 1, qualquer número natural menor que pode ser expresso na forma

onde

e cada coeficiente xi é um número natural menor que bi. E existe somente um vetor representando x.

• Nota-se que na Base-B, os pesos são Bi, enquanto que no sistema misto os pesos são dados por:

002211 ...... BxBxBxx nnnn

021 ... bbbB nnn x

0321012010 ...,...,,,1 bbbBbbBbBB nnn

021 ...xxx nn

021 ... bbbB iii

021 ,...,, bbb nn

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):

287645 = 23970.12 + 5

23970 = 2179.11 + 1

2179 = 145.15 + 4

145 = 12.12 +1

12 = 0.13 + 12

287645 = 12. (12.15.11.12) + 1.(15.11.12) + 4.(11.12) + 1.12 + 5

x mod b(i) x/b(i) b(i)

i = 0

i = n-1

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,

onde

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

0.

22.

11. ...... BxBxBxX si

sssi

sssii

00

22

11 ).(...).().( sqs

qqs

q BXBXBXx

nssn ./

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

isi mM 1

Exemplo

• Seja {mi} = {31, 17, 7, 5, 3} e N = (789)10. Computar {ri}

• Solução: s = 5;

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

ri = N mod mi

55335

31.17.7.5.3

.... 54321

1

mmmmm

mM isi

Como mis são primos entre si,

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 onde xn-1 é o bit de sinal é

O intervalo de números representados é

• É uma forma natural de representar um número inteiro. Não obstante, não é a forma mais conveniente.

11 nn BxB

0...... 10

03

32

2

nn

nn

n xseBxBxBx

0121 ... xxxx nn

1...... 10

03

32

2

nn

nn

n xseBxBxBx

e

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 seja

e o intervalo de números representados,

0121 ... xxxx nn

EBxBxBx nn

nn

0

02

21

1 ......

EBxE n

Comentários sobre excesso de E

• Se B é par, e E é escolhido igual a Bn/2, então, o número representado na forma é

• A regra de definição do sinal é: se x é negativo então

e se x é positivo

• 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

de acordo com o método excesso de E com E = 127 e não Bn/2=128.

2/1 Bxn

2/1 Bxn

0121 ... xxxx nn

00

22

11

00

22

11

.....).2/(

......

BxBxBBx

EBxBxBxn

nn

n

nn

nn

128127 x

Comentários (cont.)

• Se B= 2 e E = 2n-1, então o número representado na forma

é

onde significa o complemento de

• 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.

1' nx 1nx

0121 ... xxxx nn

02

21

1

02

21

1

...2.2.'

...2.2).1(

xxx

xxxn

nn

n

nn

nn

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

212355 – 500000= 2x105+12355 – 500000

Número em excesso de E

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 é representado pelo número natural

tal que o inteiro representado na forma seja

se

e

se

0121 ... xxxx nn

nBxxR mod)(

2/2/ nn BxB

02

21

1 ..... xBxBx nn

nn

2/..... 02

21

1nn

nn

n BxBxBx

nnn

nn BxBxBx

02

21

1 .....

2/..... 02

21

1nn

nn

n BxBxBx

positivo

negativo

Essas condições podem ser reescritas na forma:

se

e

se

E se B é par, as últimas condições são equivalentes a:

se e se

02

21

1 ..... xBxBx nn

nn

0....).2/( 02

21

1

xBxBBx n

nn

n

nnn

nn BxBxBx

02

21

1 .....

0....).2/( 02

21

1

xBxBBx n

nn

n

02

21

1 ..... xBxBx nn

nn

2/1 Bxn

nnn

nn BxBxBx

02

21

1 ..... 2/1 Bxn

positivo

negativo

Complemento de 2

Se B = 2, o número representado por é

e o bit mais significativo é também o bit de sinal.

Se

e se

10 1 nxentãox

0121 ... xxxx nn

1nx

02

21

1 ....2. xBxx nn

nn

00 1 nxentãox

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

e se

Se B = 2, o vetor de n+1 bit representa o mesmo

número como o vetor de n bit

01211 ... xxxxx nnn

12/1 BxentãoBx nn

02/1 nn xentãoBx

0121 ... xxxx nn

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 é representado por

• Se então

• e se então

10 nBx

nBxxR mod)(

11 nn BxB

0)( 11

n

n xeBxxR

01 xBn

1).1()( 111

BxeBBBBxBxR nnnnn

Sistema de numeração complemento de B reduzido (cont.)

Assim, o inteiro representado por é

e

e a regra de definição de sinal é a seguinte:

se x é negativo,

e se x é positivo, .

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.

1.... 102

21

BxsexBxBx nn

nn

0121 ... xxxx nn

11 Bxn

0.... 102

2

nn

n xsexBxx

01 nx

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 quex’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

A representação complemento de 2, , de um inteiro x pode ser vista como uma representação com dígito de sinal.

onde e todos os outros dígitos

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 é

e define-se

02

21

1 ...2.2. xxx nn

nn

}0,1{1 nx

0121 ... xxxx nn

}1,0{ix

0121 ... xxxx nn

.

........

,

,

,

211

122

011

00

nnn xxy

xxy

xxy

xy

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:

• O vetor cujos componentes yi pertencem a {-1,0,1} é a representação Booth-1 de x e

• 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.

00

22

11 2....2.2. yyyx n

nn

n

)...( 021 yyy nn

00

22

11

00

22

11

2....2.2.

2....2.2.

xxx

yyyn

nn

n

nn

nn

Codificação Booth-2

Definição: considerar um inteiro cuja representação em complemento de 2 é com n = 2.m bits, e definir

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:

O vetor cujos componentes yi pertencem a {-2,-1,0,1,2} é a representação Booth-2 de x e

00

22

11 4....4.4. yyyx m

mm

m

0121 ... xxxx nn

3.22.21.21

3452

1231

010

.2

........

,.2

,.2

,.2

mmmm xxxy

xxxy

xxxy

xxy

00

22

11

00

22

11

2....2.2.

4....4.4.

xxx

yyyn

nn

n

mm

mm

)...( 0121 yyyy mm

Codificação Booth-r

Definição: considerar um inteiro x cuja representação em complemento de 2 é com n = r.m bits, e definir

O vetor cujos componentes yi pertencem a

é a representação Booth-r de x e

onde B=2r.

00

22

11 ...... ByByByx m

mm

m

0121 ... xxxx nn

}1,...,2,1{,

2....2.2.

,2....2.2.

1.

.1.2

2.1

1.

012

21

10

mix

xxxxy

xxxxy

ri

ririr

rrir

rrii

rr

rr

1111 2,12,...,2,1,0,1,2),...,12(,2 rrrr

)...( 0121 yyyy mm

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-fixoNo sistema de numeração ponto-fixo, o número representado na forma:

é 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

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

O erro relativo máximo é igual a . Se então tal que o erro relativo máximo seja menor ou igual a

maxmin .. xBxxB pp

ppnpn xxxxxxx ....... 210121

2/2/ pBulp ).2/(1).2/( pBxxulp 0x

pBx 2

1

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 é

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.

2/102/10 66 x

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 é

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 é

e o valor absoluto mínimo de um número representado é

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

O erro relativo máximo é igual a

Como no caso anterior, o erro relativo máximo é menor ou igual a

min.minebsx

maxmax .. maxmaxee bsxbs

ebs.

2/.2/ maxmax

ebulpD

sulpbsbulpxD ee .2/)..2/(.).2/(

2

1

exemploNo sistema de ponto-flutuante de precisão simples ANSI/IEEE, o significando é

um inteiro representado em sinal e magnitude

onde é chamado mantissa, e o expoente é um inteiro em excesso de 127.

A palavra de 32 bits

representa o número

onde

Assim

2321 ... sss 067 ...eee

2321 ....1 ssss

2321067 ...... ssseeesign

esign sss 2).2....2.2.1.()1( 2323

22

11

1272....2.2. 00

66

77 eeee

128,127,2,21...11.1,1 maxmin23

maxmin eeulpss

Apesar de emin e emax não serem usados para representarem números ordinários, eles são usados para representar

e outros números não-ordinários. Os valores mínimo e máximo são:

tais que o intervalo de números representados seja

isto é

e o menor número positivo representado é 1.2-126.

127127 2.22.2 x

127,126 maxmin ee

128128127127 20.1,20.1,20.10,20.10

128128 22 x