ALGORITMOS Y PROCESADORES ARITMÉTICOS 1.1 - INTRODUCCIÓN - Procesador aritmético - Características - Niveles de descripción funcional - Nivel abstracto - Nivel de algoritmo aritmético - Nivel de implementación

1.2 - SISTEMA DE REPRESENTACIÓN DE NÚMEROS - Conjunto de valores de los dígitos - Regla de interpretación - Rango - Clasificación - No redundantes - Redundantes - Ponderados - Vector de pesos - Vector de base - Base mixta - Base fija -No ponderados - Sistema de numeración convencional en base ℜ

1.3 - REPRESENTACIÓN Y SUMA DE NATURALES

- Introducción 1.3.2 - Algoritmo aritmético 1.3.3 - Algoritmo de suma a nivel de representación - Full adder - Half adder 1.3.4 - Tipos de sumadores - Secuencial - Paralelo - 2 niveles de puertas 1.3.5 - Aceleración de la suma (CLA) - CLA: Carry Look Ahead 1.4 - REPRESENTACIÓN, SUMA Y RESTA DE ENTEROS 1.4.1 - Introducción - Representaciones 1.4.2 - Teoría de los sistemas complementados - Representación gráfica - Complemento a la base - Complemento a la base disminuida - Mapeo directo 1.4.3 - Suma en sistemas complementados - Suma en C'2 - Overflow en C'2 - Suma en C'1 - Overflow en C'1 1.4.4 - Cambio de signos en sistemas complementados - Cambio de signo en C'1 - Cambio de signo en C'2 - Overflow en cambio de signo 1.4.5 - Resta de enteros en sistemas complementados - Cambio de signo y suma en C'1

- Cambio de signo y suma en C'2 - Overflow - Implementación de un sumador/restador 1.4.6 - Extensión de rango -Ν -Ζ 1.4.7 - Signo y magnitud - Mapeo directo - Algoritmo de suma en S. y M. - Implementación 1.4.8 - Representación de enteros en exceso (o polarizados) - Suma en exceso 2 n−1 -1 - Cambio de signo - Resta en exceso - Sumador/Restador en exceso 2 n−1 -1

1.5 - DESPLAZAMIENTOS ARITMÉTICOS -Ν - Ζ Sistemas complementados, base 2. - C '2 - C '1

1.6 - ALGORITMOS ARITMÉTICOS PARA LA MULTIPLICACIÓN DE Ν 1.6.1 - Multiplicación Secuencial de naturales - Algoritmo aritmético - Recurrencias - Implementación secuencial del algoritmo - Base 2 - General

1.6.2 - Aceleración de la multiplicación secuencial para naturales - Carry Save Adder (CSA) - Carry Save Multiplication - Exploración simultánea de varios dígitos sin solapamiento 1.6.3 - Algoritmos paralelos para multiplicar naturales - Replicar el CPA en el espacio - Replicar el CSA en el espacio - Multiplicación con árboles de CPA'S.

1.7 - ALGORITMOS ARITMÉTICOS PARA MULTIPLICAR ENTEROS 1.7.1 - Multiplicación secuencial de enteros en C'2 - Implementación secuencial con CPA - Implementación secuencial con CSA 1.7.2 - Algoritmos paralelos para multiplicar enteros (arrays) C'2

1.8 - REPRESENTACIÓN, SUMA, RESTA: MULTIPLICACIÓN DE REALES - Punto fijo - Punto flotante - Mantisa normalizada con bit escondido 1.8.1 - Representación punto flotante IEEE 754-1985 - Características - Representación en precisión simple - Rango, precisión, error, overflow - Suma y Resta en punto flotante

TEMA 1 - ALGORITMOS Y PROCESADORES ARITMÉTICOS

1.1 - INTRODUCCIÓN

- Procesadores Aritméticos

Operandos

Resultados

P.A

Operación START

END Señales Sincronismo

- Las señales de sincronismo (Start, End) indican al PA cuando las operaciones y el código de las operaciones son válidas en la entrada y a otras partes del sistema cuando los resultados están preparados.

Características: - Representación de los operandos - Rango sobre el que puede trabajar el P.A. (finito) (Aparece debido a la representación digital) - Operaciones que puede hacer (1 o más de una) - Velocidad - Coste - Área del Chip

Niveles de descripción funcional 1 - Nivel abstracto: funciones matemáticas, propiedades --> NÚMEROS 2 - Nivel de algoritmo aritmético: los números son representados por VECTORES DE DÍGITOS y las operaciones son descritas por algoritmos que operan con este vector de dígitos.

x ∈Ζ → X ∈Ζ n x

y

( xn−1 xn−2 ,... x1 , x0 )

↓ Χ

OP ↓ Ζ ↓ Z

↓ Υ

f( Χ ) = x Z = x OP y

3 - Nivel de implementación: El vector de dígitos se codifica en un VECTOR DE BITS ya que la máquina trabaja en binario. Este nivel es el hardware que implementa el nivel anterior.

Ζn → Bk

1.2 - SISTEMAS DE REPRESENTACIÓN DE NÚMEROS

- Los elementos que forman un sistema de representación son: - Conjunto de valores de los dígitos llamamos Di al conjunto de valores de Χ i Ejem: Di = {0,1,2,...,9} para el sistema decimal convencional - Regla de interpelación Busca una función que a partir del vector de dígitos retorne un valor. f ( Χ) = x

n −1

Ejem: Base 10

x = ∑ X i 10i i =0

- Rango: Conjunto de valores que puede tomar un número en nuestra representación. El rango se obtiene del conjunto de valores y de la regla. El número máximo de vectores de dígitos viene dado por: n −1

K = ∏ Di

Siendo:

i =0

Di : nº valores posibles n: nº de dígitos

- Clasificación de los sistemas: - No Redundantes: Todo vector de dígitos representa un número diferente.

Χ≠Υ⇒x≠ y - Redundantes: Hay números que son representados por más de un vector de dígitos. ventajas --> incrementan la velocidad de ejecución. desventajas ---> disminuye el rango. n −1

- Ponderados: regla de interpretación:

x = ∑ Χ i Wi i =0

Donde: W = (Wn −1 ,Wn − 2 ,...,W1 ,W0 ) → VECTOR DE PESOS El vector de pesos va asociado con el VECTOR DE BASE: R = ( Rn −1 ,..., R1 , R0 ) Existen 2 tipos de ponderados: 1 - Base mixta W0 = 1

Wi = Wi −1 . Ri −1

(1 ≤ i ≤ n-1)

Ejem: sistema horario: representación del tiempo en términos de horas, minutos y segundos en un periodo de 24 horas: R = (24,60,60) --> vector de base W = (3600,60,1) --> vector de pesos 2 - Base fija: Todos los elementos del vector de base tienen el mismo valor, r. R = (r,r,...,r)

(

)

 n −1  x = Χi .r i  ∑ i =0  

W = r n −1 , r n − 2 ,..., r ,1

- No ponderados: Sistema de numeración romano. 1.3 - REPRESENTACIÓN Y SUMA DE NATURALES

- Ν = {0,1,...}

El sistema que utilizaremos será el sistema convencional en base r. Χ = X n −1 ,..., X 1 , X 0 n −1

x = ∑ X i .r i i =0

x1 ∈ {0,..., r − 1} El rango es: 0 ≤ x ≤ r n − 1 SUMA: S = X + Y X ≡ Χ n −1 Χ n − 2 .... Χ 1 Χ 0 Y ≡ Υn −1 Υn − 2 ..... Υ1 Υ0

0 ≤ x ≤ rn −1 0 ≤ y ≤ rn −1

S ≡ S n S n −1 S n − 2 .... S1 S 0

0 ≤ s ≤ 2. r n − 2 ↓ necesitamos n+1 dígitos n +1 0 ≤ s ≤ r −1

A nivel de dígitos: n −1

s = x +y =

n −1

∑ x .r + ∑ y .r i

i

i =0

i

i

y =0

n

∑ S .r i

i =0

i

n −1

= ∑ ( X i + Yi )r i i =0

Pero nosotros sólo queremos utilizar n dígitos. Podríamos considerar: Si = X i + Yi , i = 0,....,n-1

Sn = 0

  Pero no es válido, aparecen dígitos  fuera de rango.

Vamos a ver como podemos hacer la suma sólo para n dígitos pero detectando el dígito Sn: x = X n −1 . r n −1 +.......+ X i +1 . r i +1 + X i r i +.......+ X 0

y = Yn −1 . r n −1 +........+Yi +1 . r i +1 + Yi . r i +........+Y0 S =.............+ ( X i +1 + Yi +1 ) r i +1 + ( X i + Yi ) r i +...+ ( X 0 + Y0 ) +1 -r X i +1 + Yi +1 + 1 X i + Yi − r para X i + Yi ≥ r {

Esta operación no altera el resultado ya que quitar la base a un dígito y sumar un carry al siguiente es no hacer nada

1.3.2 - Algoritmo Aritmético

C0 = 0 DO i = 0, n-1 If X i + Yi + Ci ≥ r x+y rn

Si = X i + Yi + Ci − r

Cn =

Ci +1 = 1

Solo el cociente

Else

Esto comprueba si la suma se Si = X i + Yi + Ci

puede representar con n dígitos

Ci+1 = 0

o no

END DO Sn = Cn Y

X n

n Co (0,1)

Cn (0,1) n S Cn siempre será 0 o 1 ---> Sn también

Cn = 0 --> resultado correcto representado con n dígitos. Cn = 1 --> resultado incorrecto representado con n dígitos.

1.3.3 - Algoritmo de suma a nivel de representación

Di ∈ {0,1}   Los dígitos son representados ahora como bits.  La suma la encontraremos con operaciones lógicas.

r=2

Particularización del algoritmo:

C0 = 0 DO i = 0, n-1 If X i + Yi + Ci > r

Si = 1 Ci +1 = 1 Else If

X i + Yi + Ci = r Si = 0 Ci +1 = 1

Else

Si = 1 Ci+1 = 0 END DO Full Adder: Xi Yi Ci 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

Si Ci+1

0 1 0 1 0 1 0 1

0 1 1 0 1 0 0 1

0 0 0 1 0 1 1 1

Otra particularización del algoritmo:

C0 = 0 DO i = 0, n-1 If X i + Yi + Ci ≥ r

Xi Yi Ci

F.A

Ci+1

Si

Si = X i + Yi + Ci − r Ci +1 = 1 Else Si = X i + Yi + Ci

Ci+1 = 0 END DO Sn = Cn Vamos a implementarlo con el mínimo número de puertas: Xi

Ci Yi 00 01 11 10

Xi

Ci Yi 00 01 11 10

0

0

1

0

1

0

0

0

1

0

1

1

0

1

0

1

0

1 1 Ci+1

1

Si Si = C i. Xi. Yi + C i. Xi.Y i + Ci. Xi.Y i + Ci. Xi. Yi Ci+1 = XiYi + CiXi + CiYi Ci Xi Yi

Ci+1

Si

Xi Yi Ci Tiempo de respuesta = 2 niveles de puertas (no tenemos en cta los inversores).

F.A

T=2Z Ci+1

Si

Vamos a realizar el mismo circuito pero utilizando puertas HALF ADDER: a b a 0 0 1 1

b Ci+1 Si 0 0 0 1 0 1 0 0 1 1 1 0

a

b H.A

Si = a + b Ci+1 = a . b Ci+1

Ci+1

Si

Si hacemos la suma a partir de H.A: X H.A.1 X X X X H.A.2 X X X H.A.3 Nunca podrá ser 1+1 --> podemos poner una OR. X XXX Seguro que es '0'

X

Yi Xi

X

X

Ci

H.A T = 3Z H.A

Si

Ci+1 Ci+1

Si = Xi ⊕ Yi ⊕ Ci

Ci+1 = Xi.Yi + Ci (Xi ⊕ Yi) Conclusiones: - Con F.A más puertas que con H.A

Si

Si

---> Compromiso entre vel. y coste. - Con F.A más rápido que con H.A

1.3.4 - Tipos de Sumadores

1- Secuenciales 2- Paralelo CPA CLA CSA 3- 2 niveles de puertas: es el más rápido pero con muchas puertas y cada puerta con muchas entradas.

1 - Secuencial

n x

- Reg. de desplazamiento - Registro

y c

F.A s

T = n(TFA + TBI ) TFA = Depende del diseño del F.A TBI = Tiempo del biestable 2 - Paralelo CPA (Carry Propagation Adder)

Xn-1

Yn-1

x2 .......

F.A

Sn-1 T = n 2Z

y2

x1

y1

x0

y0

F.A

F.A

F.A

S2

S1

S0

C0

Mejor que el anterior

1.3.5 - Aceleración de la suma

El problema es el carry. Vamos a analizarlo:

Ci + 1 = Xi. Yi + Ci. Xi + Ci. Yi = Xi. Yi + Ci ( Xi ⊕ Yi ) -------------Gi Pi ↓ ↓ Generador Propagador de Carry de Carry

Por tanto, tendremos un carry en la salida si: Gi = 1 independientemente de Pi ---> genera un carry Ci = 1 y Pi =1 ---> se propaga el carry anterior Ejem: 01101101011100 01001011001010 Una primera idea: Podríamos empezar a sumar por la combinación 1/1 que sabemos que seguro genera acarreo o por la 0/0 que el acarreo siempre es cero --> PARALELISMO. El tiempo de suma viene dado por la cadena más larga:

0101001111011 1000110001101 3 t=8 Este sistema no acaba de ser bueno ya que tendríamos que detectar las combinaciones 0/0 y 1/1 --> añadir puertas --> más lento. CLA (Carry Look Ahead) Anticipación de Carry Pretendemos acelerar los carry. Vamos a analizar la expresión del carry: Ci+1 = Gi + Ci.Pi

C1 = G0 + C0 P0 C2 = G1 + C1 P1 = G1 + G0 P1 + C0 P0 P1 C3 = G2 + C2 P2 = G2 + G1 P2 + G0 P1 P2 + C0 P0 P1 P2 Observar que los carry no dependen del acarreo de la etapa anterior sino sólo de Pi, Gi, C0 .

Si lo implementamos, por ejemplo para 4 bits:

X3

Y3

X2

P/G

P3

Y2

X1

P/G

G3

Y1

X0

P/G

P2

G2

P1

Y0

P/G

G1

P0

G0 CLA C0

P3

P1

P2

C4

S2

S3

C4

P0

Xi Yi

C0

C1

C2

C3

S0

S1

Pi Ci

Si = Xi + Yi + Ci

P/G

Pi

Gi

Tiempo de respuesta:

Pi

Independiente de n (aconsejable n ≤ 4)

T = 4Z X

Y 4

4

C4

S - CLA 4 S

Normalmente se dibuja:

Si

C0

T = 4Z

S3 X3

Y3

S2 X2

FA'

Y2

S1 X1

FA'

Y1

S0 X0

FA'

Y0

C0

FA'

CLA

C4

Xi

Yi

Si

Gi

Ci

Pi

Ejemplo: Realizar un sumador de palabras de 16 bits con CLA. - Una opción: Y15..12

X15..12

4

4

X11.8

Y7..4

X7..4

Y3..0

X3..0

4

4

4

4

4

4

S15..12

S11..8

C0

C4

C8

C12

S-CLA

S-CLA

S-CLA

S-CLA C16

Y11..8

S7..4

S3..0

Volvemos a tener problemas con la propagación del carry. Este sistema no se utiliza. - Otra opción: Utilizar un CLA para los carry´s C4, C8, C12, C16 Si analizamos C4:

C4 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1G0 + P3 P2 P1 P0 C0 − 1 −4 −4− 4− − 4 −44−2− 4− −4 −4−4− 4− − 43− − 1 −2 −3− G0*

generador de grupo

C4 = G0' + P0' C0 Así quedará:

P0*

propagador de grupo

Xi

Yi

4

4

S - CLA

Ci+1

Ci

4 S

C12

C8

C0

C4

C16

C0* C4*

C3*

P0*

C1*

C2* CLA

P**

G**

En general: El número de niveles de CLA es: log r n r: número de entradas del sumador (normalmente 4) n: número de bits que se quieren sumar El tiempo de respuesta será: Tn = 4 Z [log 4 n]

Nota: log a N =

log b N log b a

1.4 - REPRESENTACIÓN, SUMA Y RESTA DE ENTEROS 1.4.1 - Introducción

Ζ → Νn x → Χ(vector _ de_ digitos)

} mapeo directo

Representamos un valor entero por un vector de dígitos de números naturales. Otra forma: '

2

f f Ζ  → Ν  →Ν

x → x e  → Χ

} mapeo directo

x: valor implícito x e : valor explícito n −1

xe = ∑ Χ i r i i =0

El número entero con signo, 'x', se representa con un valor entero positivo, x e , el cual se representará por un vector de dígitos, Χ . REPRESENTACIONES (de un número entero como un natural) - S y M (Signo y magnitud) - Sistemas complementados - Exceso 2 m (polarizado) - r < 0 (base negativa)

1.4.2 - Teoría de los sistemas complementados

En los sistemas complementados no hay separación entre la representación del signo y de la magnitud, lo que hacemos es representar el número entero con un número natural x e . La función que nos da x e siendo:

x e = x mod c

c: constante de complementación

La función mod viene definida como: x → x ≥ 0 xe  c − x →≤ 0

Ejem: c = 8 , x = 2 , x = -2 -

7

0

6

2

5 4

x e = 2 mod 8 = 2 x e = -2 mod 8 = 6

+

1

3

Es necesario que no se produzcan solapamientos, por tanto: x max <

c 2

REPRESENTACIÓN GRÁFICA

Z

-C

-1

N

0

1

0 C/2 queda fuera

La función inversa será:

x=

{

xe ,

si x e < c / 2

xe - c

si

xe > c / 2

C-1

C

C-1

C

X Xe

Consideración: Si ' c ' es par consideraremos ' c / 2 ' en los negativos: - c par

→

c c   c ∈ Ν → rango: − ..... − 1 2 2   2

- c impar

→

 −(c − 1) c c − 1 ∉ Ν → rango:  .....  2 2   2

De esta forma conseguimos que haya el mismo número de números negativos que positivos. Dado n dígitos el rango válido es: 0 ≤ x e ≤ r n − 1 Según sea 'c' tenemos: - c = r n → complemento a la base.

Si r = 2 → c ' 2

- c = r n − 1 → complemento a la base disminuida. Si r = 2 → c ' 1 COMPLEMENTO A LA BASE rango: 0 ≤ x e ≤ r n − 1

c = r n → par c c rango: − ≤ x ≤ − 1 → Desequilibrio 2 2

Z 0

-C/2

C/2

N C/2

C-1 C

COMPLEMENTO A LA BASE DISMINUIDA c = r n −1

→

Impar Si r = 2 → Complemento a 1

rango: 0 ≤ x e ≤ r n − 1 * Ejemplo: r = 2 , n = 4

→ c = 2 4 −1 = 15 →

c = 7,5 2

7,5

-15 ......... -8

-7

-6 ...............

-1

0 1 .......................... 7

8

15

15

8

El 15 se mapea sobre el '0'

  rn   rn rango: − − 1 .... − 1 2    2 

[ −( 2

rango (n = 2)

n −1

) (

)]

− 1 − 2 n −1 − 1

MAPEO DIRECTO ( Solo es válido cuando la base es 2 ). Permite encontrar un camino directo sin tener que pasar por x e C ‘2

si

xe

x=

x e ≤ 2 n −1

  

( xn−1 = 0) →

xe − 2 n

si

x e ≥ 2 n −1

( xn−1 = 1)

n −2  n −1 i X 2 = X i 2i ∑ ∑ i i =0  i =0 x =  n −1 n−2 n−2  X 2 i − 2 n = 2 n −1 +  X 2 i  − 2 n = −2 n −1 + X i 2i ∑ ∑ i i ∑  i =0  i =0 i =0

generalizando: n−2

x = −2 n −1 X n −1 + ∑ X i 2 i i =0

C ‘1

 x e ,.... si..... x e < 2 n −1 x= →  x e − (2 n − 1),.... si....., x e ≥ 2 n −1

n−2  n −1 i X X i 2i 2 = ∑ ∑ i  i =0 i =0 x =  n −1 n−2  X 2 i − (2 n − 1) = −2 n −1 + X i 2 i + X n −1 ∑ i ∑ i =0 i =0

n −2

x = −2 n −1 X n −1 + ∑ X i 2 i + X n −1 i =0

1.4.3 - Suma en sistemas complementados

Ζ → Ν → Νn x xe X

S=x+y

Interesa que la suma quede en valores explícitos S e = ( x e + y e ) mod c S e = f ( xe, ye ) En un principio hacer la suma representa: Xe

Ye

n

Suma vista hasta ahora

+N We mod n Se

SUMA EN C’2

hacer la suma depende de la cte de complementación

S e = We mod c We = X e + Ye

Para garantizar que la suma sea correcta ( ∃/ problemas de overflow) tenemos que añadir un bit.

↓

( Wn , Wn-1, Wn-2 .......W 0 ) → n+1 bits We ..... si.....We < 2 n → W e mod 2  We − 2 n ...... si.....We ≥ 2 n n

We → 1 Wn-1 Wn-2 Wn-3.....W1 W 0 - 1 0 0 0 0 0 0 Wn-1 Wn-2 Wn-3.....W1 W 0

para W e ≥ 2 n

Es equivalente a despreciar el bit de mayor peso El carry no es el bit de mayor peso ya que lo despreciamos. Ejercicios: 21,9,6 Ahora necesitamos detectar cuando se produce overflow: OVERFLOW EN C’2

[

]

rango: −2 n −1 ....2 n −1 − 1

[

con n bits

]

X, Y ,S ∈ −2 n −1 ....2 n −1 − 1 → tendremos problemas en la suma 0 ≤ X e ≤ 2n − 1 CASOS: 1 - Suma de X , Y con signos diferentes → S es representable 2 - Suma de X , Y con mismo signo → S no siempre representable

−2 n ≤ X + Y ≤ 2(2 n −1 − 1)

 X + Y ... si... X + Y > 0 S e = S mod 2 n =  n 2 + X + Y ... si... X + Y < 0

-2 n −1

-2 n

2 n −1

0

2n

Z N 2 n −1

0

2n

la expresión del overflow: OVF = Xn-1.Yn-1. S n-1 + X n-1. Y n-1.Sn-1

El ovf existe cuando los números son ‘+’ → Xn-1 = Yn-1 = 0 y el bit de signo de la suma es Sn-1 = 0 o los números son negativos → Xn-1 = Yn-1 = 1 y el bit de signo de la suma es Sn-1 = 0. La implementación: Xn-1 Yn-1

Cn

OVF

FA

FA

.......

Sn-1

Para el caso concreto de complemento a 2: OVF = Cn ⊕ Cn-1

SUMA EN C’1

Existe OVF si los carry más significativos son diferentes.

Se = ( X e + Ye ) mod c 14 2 43

Lo único que varia respecto al c’2 es

C = 2 −1

la operación mod.

We

n

1)We ..... si.................0 ≤ We ≤ 2 n − 1  n 2)0....... si................We = 2 − 1 n W e mod ( 2 − 1)  n n −1 n 3)We − (2 − 1).. si....2 < We < 2(2 − 1) 4)0....... si................W = 2(2 n − 1) e 

rango: 0 ≤ We ≤ 2(2 n − 1) W e = ( Wn, Wn-1, ......W 1 W 0 ) → n+1 dígitos 1) (0,X,X....,X) ≠ (0,1,1....1)

} Wn = 0

2) (0,1,1,......1) 3) (1,X,X,....X) ≠ (1,1,...,1,0)

}

Wn = 1

4) (1,1......,1,0) Casos: 1 , 2 → (Wn-1 , Wn-2 ,.....,W 1 ,W0 )

3

→ W e −2 n + 1 1XXX....XX 10 0 0.....0 0 XXX....XX +1

4

no podemos con los n-1 bits de menor peso

→ 11......10 1 11.......11

Despreciamos el bit de mayor peso y sumamos 1

Despreciamos el bit de mayor peso y sumamos 1

El circuito que lo implementa:

Xe

Ye n

n +N

Las combinaciones peligrosas son las que tienen bits que todas propagan el carry

n 1

Un sumador que funciona:

+N

Es mejor que el anterior pero requiere más area. El tiempo es el mismo.

INC

Un resultado de suma no será nunca todo ‘0’ a no ser que sea forzado (sumando ‘0’ + ‘0’) OVERFLOW EN C’1 - Igual que en C’2.

1.4.4 - Cambio de signo en sistemas complementados

Z = - X → Z e = f (X e ) Donde Z y X son números enteros Z e = Z mod c = ( -X ) mod C = C - ( X mod C ) = C - X e Demo: − X , X < 0 -X mod C =  C − X , X ≥ 0

→ Equivalente

C − X , X ≥ 0 C - X mod C =  C − (C − X ), X < 0)

CAMBIO DE SIGNO EN C’1

Z e = C-X e C = r n −1 (2 n − 1) n −1

Ze =

∑Z r

i

i

i =0

n −1

X e = ∑ Xiri i =0

X i , Z i ∈[0.. r − 1]

n −1

n −1

n −1

n −1

i =0

i =0

i =0

i =0

Z e = (r n − 1) − ∑ X i r i = ∑ (r − 1)r i − ∑ X i r i = ∑ ( r − 1 − X i )r i

En concreto si C = 2 n −1

 X i = 0 → Zi = 1  Zi =   → Z i = X i →Z e = X e  X i = 1 → Zi = 0  Complementando bit a bit

CAMBIO DE SIGNO EN C’2 C = 2n Z e = C - X e = 2 n −1 + 1 − X e = X e + 1 OVERFLOW EN CAMBIO DE SIGNO - C’1:

[

]

Rango simétrico: − (2 n −1 − 1).....2 n −1 − 1 → ∃/ overflow - C’2:

[

]

Rango asimétrico: −2 n −1 .....2 n −1 − 1 → Existe overflow para 100...0 ( −2 n −1 ) Ejem: n = 3 x = -4 ↓ Xe= 4

→

Χ: 1 0 0 Χ: 0 1 1 +1 Ze = 4 → 1 0 0

1.4.5 - Resta de enteros en sistemas complementados

- 2 opciones: 1.- Algoritmo directo 2.- Cambio de signo y suma → R = X - Y = X + (-Y) CAMBIO DE SIGNO EN C’1 Xe

Ye

n

n

+N

R

ADD Ν ( X e , Y e , Cout ) CAMBIO DE SIGNO Y SUMA EN C’2 Xe

Ye

n

n

+N

R

ADD Ν ( X e , Y e ,1) OVERFLOW C’1: Igual que en la suma C’2: Existen 2 posibles overflow: - OVF1 → cambio de signo - OVF2 → en la suma

También podríamos hacer:

1

Xe

Ye

OVF1 1

INC n

n

Esta suma es más eficiente que la anterior.

+N

OVF2

R

IMPLEMENTACIÓN DE UN SUMADOR/RESTADOR C’2: Xn-1

Yn-1

Xn-2 Yn-2

X0 Y0

S/R

FA

Cout

OVF

C’1: Pareado.

FA

...........

FA

1.4.6 - Extensión de Rango

- Es necesario para hacer multiplicaciones.

[

]

Queremos representar el valor de X de n bits

]

con un vector de dígitos de m bits tal que: X =Y m>n

X ∈ −2 n −1 ...2 n −1 − 1

[

Y ∈ −2

m −1

...2

m −1

−1

Es decir , queremos la representación de Y cuyo valor es igual al de X pero tiene ‘m’ bits (m > n). a ) Para naturales Ν :

 X i , i = 0.... n − 1 ⇔ añadimos ‘0’ a la izquierda. Yi =  0, i = n..... m − 1 b) Para enteros Ζ :

 X i , i = 0..... n − 1  Yi = 0, i = n.... m − 1 → X ≥ 0 (r − 1), i = n.... m − 1 → X < 0  Para el caso concreto de r = 2 lo que hacemos es replicar el signo: X = (Xn-1 , Xn-2 , ......... X1X0) Y = (Xn-1 , Xn-1 , Xn-1.......Xn-1 , Xn-2 , .... X1X0) m

n

Demostración para C’2:  rn X , X <  e e 2 X = n X − rn, r ≤ X < rn e  e 2

obtención de X a partir de X e

 rm Ye , Ye < 2 Y= m Y − r m , r ≤ Y < r m e  e 2

Si X e <

rn →Y = X ≡Ν 2

Si X e ≥

rn → Ye − r m = X e − r n → Ye = X e + r m − r n 2

Ejemplo: r = 2 , n = 4 , m = 6 , X = -7 → X e = 9 >

Ye = 9 + 2 6 − 2 4 = 9 + 64 − 16 = 57 C'2(-7)

Y

111001 n

m

* Demostrarlo para C ‘1

24 2

1.4.7 - Signo y Magnitud

X = (Xs, Xm)

Ζ → Ν2 → Νn X → ( X s , X m ) → Χ = ({ X n −1 , X n − 2 .... X 1 , X 0 ) 1 4 4 2 4 43 Xs Xm

x < r n −1 → rango simétrico pero salen 2 ‘0’

Ζ → Ν → Νn X → Xe → Χ

El valor explícito: X , X ≥ 0 X e =  n −1 r − X , X < 0

Inversa: n −1  X e ,0 ≤ X e < r ,( X n −1 = 0) X =  n −1 r − X e , r n −1 ≤ X e < 2r n −1 ,( X n −1 = 1)

De forma gráfica:

-rn-1

0

rn-1

2rn-1

Z N rn-1

2rn-1

MAPEO DIRECTO (Para r = 2)

n−2 i ∑ Χ i 2  i =0 X = ⇒ n −1 n −2 2 n −1 − Χ 2 i = 2 n −1 − 2 n −1 − Χ 2 i ∑ ∑ i i  i =0 i =0 n−2

X = (1 − 2 X n −1 )∑ Χ i 2 i i =0

ALGORITMO DE SUMA EN S Y M S = ( S s , Sm )

if X = (Xs, Xm) Y = (Ys , Ym )

( X s = Ym ) then S m = ( X m + Ym ) mod 2 n −1

OVF = Cn else if ( X m ≥ Ym ) then S m = X m − Ym S s = Xs else S m = Ym − X m S s = Ys end if OVF = 0 end if

Pero para implementarlo es necesario un hardware muy complejo. Debemos optimizar el algoritmo. Intentaremos que la complejidad sea parecida a la de la suma en C’1 o C’2.

MEJORA:

if

( X s = Ys ) then S s = Xs S m = ( X m + Ym ) mod 2 n −1 OVF = Cn else

S’ m = X m − Ym if ( S ' m ≥ 0 ) then S m = S 'm S s = Xs else S m = − S 'm S s = Ys end if OVF = 0

end if Nos ahorramos girar los operandos, haciendo un cambio de signo. ¿Que convenio de complementación utilizaremos C’1 o C’2? - Tenemos que hacer una resta y un cambio de signo → es más sencillo en C’1. Implementación * Codificar X m , Ym en C’1 0 X n − 2 , X n − 3 ..... X 1 , X 0 → X m en C`1 0Yn − 2 , Yn − 3 ..... Y1 , Y0 → Ym en C`1 * Operar con + , - en C’1 ( n bits ) i) ( X s ≠ Ys ) → X m − Ym

0 Cn

X n−2

Cn-1

Cn-2

X n−3 .............

X1

X0

1 Y n−2 Y n−3 ............. Y 1 Y0 -----------------------------------------------------S ' n −1 S ' n −2 S ' n −3 .............. S1 ' S 2 '

Observar que:

Cn = Cn −1 y

S ' n −1 = Cn −1

Por tanto: Cn-1

Sn-1

X n−2

X n−3

........... X 1

X0

Y n−2 Y n−3 ........... Y1 Y0 ------------------------------------------S ' n −2 S ' n −3 ............ S1 S 0

En este caso: - No existe overflow - Si S' n−1 = 1 → Magnitud negativa → hay que complementar ya que el resultado estará en C'1 y lo quieres en signo y módulo. ii) ( X s = Ys ) → X m + Ym

Cn

0 Cn-1X n−2

X n−3

........... X 1

X0

0 Yn−2 Yn−3 ........... Y1 Y0 ------------------------------------------------S ' n −1 S ' n −2 S ' n −3 ............ S'1 S' 0

-¿Necesitamos el último FA? Observar que: C n = 0 y

S ' n −1 = Cn −1

Casos posibles: - Cn−1 = 0 - Cn −1 = 1 → S ' n −1 = 1 → OVERFLOW

Estamos sumando 2 magnitudes ⊕ → no puede dar un resultado negativo.

Por tanto:

X n−2

X n−3

........... X 1

X0

Yn−2 Yn−3 ........... Y1 Y0 ------------------------------------------S n−2 S n−3 ............ S '1 S ' 0

OVF = X s Ys Cn −1 + X s Y s Cn −1

El circuito será:

Xs

Ys

1

0

Ss

Xn-2 Yn-2

Cn-1

FA

Sn-2

Faltaría el circuito de detección de overflow.

X0 Y0

...........

FA

S0

1.4.8 - Representación De Enteros En Exceso (o Polarizado) Ζ → Ν → Νn  Xe = X + C X → X e → Χ En función de 'C' tendremos diferentes excesos.

2 n −1 − 1 C =  n −1 2

Para C = 2 n−1 − 1

X e = X + 2 n −1 − 1 Como X e es un número natural → 0 ≤ X e ≤ 2 n − 1 Por tanto:

X MIN → X e = 0 → X = −2 n −1 + 1 X MAX → X e = 2 n − 1 → X = 2 n − 1 − 2 n −1 + 1 = 2 n −1 El rango será:

[

]

X ∈ −2 n −1 + 1....2 n −1 → es asimétrico

-2 n−1

0

2 n−1

2n

Z N 0

2n-1

2n

Este rango los mantiene ordenados → bueno para comparaciones rápidas X n −1 = 0 → X ≤ 0 X n −1 = 1 → X > 0

SUMA EN EXCESO 2 n−1 − 1

Z = X +Y Ze = Z + 2 n −1 − 1 = X + Y + 2 n −1 = X + Ye = X + 2 n −1 − 1 + Ye − 2 n −1 + 1 = X e + Ye − 2 n −1 + 1

Cout

Sn-1

Sn-2 ............ S1 S0

M

Zi = Si

S

0

0

1

C B

A

0

-2n-1

0 0

Sn-2 .............. S1 S0

Cout

Sn-1

0 0 1 1

0 1 0 1

(B=Cout - M)

M A C B 1 0 1 0

1 0 1 0

1 0 0 0

Zi=Si i = 0....n-2

underflow

1 0 0 1

overflow

i = 0 ..... n-2

A = Z n −1 = S n −1

[Z

e

]

= Z + 2 n −1 − 1 ;

Z = Ze − 2

n −1

+ 1 ≥ −2 n −1 + 1

Ze ≥ 0

C

B

1

1 ← Underflow (ovf. por debajo) 1 ← Overflow (por arriba)

0 OVERF = Cout ⊕ A

↑ overflow + underflow Representación:

A = Z n −1 = S n −1

Xe

Ye n

n

1

+

Cout

bit de mayor peso (n-1)

1

Xe+Ye+1

n-1 S - 2n-1 n

Ze CAMBIO DE SIGNO EN EXCESO

Z = −X ;

X e = X + 2 n −1 − 1 → X = X e − 2 n −1 + 1

Z e = Z + 2 n −1 − 1 = − X + 2 n −1 − 1 = 2 n −1 − 1 + 2 n −1 − 1 − X e =

((

)

)

 2n − 1 − X e − 1 = X e − 1  2 −1− Xe −1 =  n  2 − 1 − ( X e + 1) = X e + 1(mejor ) n

(

)

RESTA EN EXCESO

Z = X − Y = X + ( −Y ) Otra opción es realizar un algoritmo directo manipulando expresiones. Z e = Z + 2 n −1 − 1   Ye = Y + 2 n −1 − 1 Z e = X − Y + 2 n −1 = X e − Y = X e + 2 n −1 − 1 − Ye = X e = X + 2 n −1 − 1

= X e + 2 n −1 − 1 − Ye − 2 n −1 + 2 =

Cout Sn-1 0

1

=

X e + 2 n − 1 − Ye − 2 n −1 = X e + Ye − 2 n −1 1 4 2 43 14 2 43 S Ye

Sn-2 .......... S 1 S 0 0

n −1

0

0

→

Los bits que faltan se obtienen igual que en la suma.

Las operaciones en exceso son igual que hasta ahora sólo que hay que restar 2 n−1 al final. Este produce overflow y underflow.

SUMADOR/RESTADOR EN EXCESO Xe

Ye

n

n n

n

+ n

1

n-1 n

Ze ovf * Ejercicios 20 , 15 , 25

2 n−1 − 1

resta/suma

1.5 - DESPLAZAMIENTOS ARITMÉTICOS

→ Multiplicar o dividir por la base * Desplazamiento izquierda: z=x.r * Desplazamiento derecha: x¡ r d z

z . r + d = x ↔ z + d/r = x/r

Vamos a estudiar el desplazamiento para naturales y enteros. A) Ν - Desplazamiento izquierda:

x = X n −1r n −1 + X n − 2 . r n − 2 +......+ X 1r + X 0 → Χ = ( X n −1 , X n − 2 ,..., X 1 , X 0 ) z = r . x = X n −1r n + X n − 2 r n −1 +.....+ X 1r 2 + X 0 r + 0 →   Ζ =  X n −1 , X n − 2 ,..., X 1 , X 0 ,0 1 4 44 2 4 4 43   n ↓ Si es distinto de '0' → overflow

- Desplazamiento derecha: d x X r n −1 + X n − 2 . r n − 2 +......+ X 1r + X 0 + z = = n −1 = r r r X n −1r n − 2 + X n − 2 . r n − 3 +......+ X 2 r + X 1 + Ζ = (0, X n −1 , X n − 2 ,...., X 2 , X 1 ) B) Ζ sistema complementado, base = 2

X0 → r

- C '2 - Desplazamiento izquierda: z = r . x = 2. x = x + x X n−1 X n− 2 ........ X 1 X 0 X n−1 X n− 2 ........ X 1 X 0 --------------------------------------X n−1 X n− 2 X n− 3 .......... X 0 0 ≡Ν ↓ ∃ overflow cuando X n −1 ≠ X n − 2

- Desplazamiento derecha: d x +z= r r Z e , si ,( Z n −1 = 0) z= n Z e − 2 , si , Z n −1 = 1)

Vamos a verlo para el caso < 0: x = X e − 2n →

x Xe = − 2 n −1 2 2

X X X d d + Z e − 2 n = e − 2 n −1 → + Z e = e − 2 n −1 + 2 n = e + 2 n −1 2 2 2 r r Ν

(0, 0 , X n−1 ,...... X 1 )

→ replicamos el bit de signo