Unidad 1 SISTEMAS NUMERICOS

Objetivos
Comprender el manejo de nmeros y operaciones aritmticas desde un lenguaje de programacin de bajo nivel. Repasar los mtodos de representacin numrica de los sistemas: decimal, binario, octal y hexadecimal, para nmeros enteros y fraccionarios. Discutir los mtodos de conversin entre los sistemas numricos de nuestro inters, tanto para nmeros enteros y fraccionarios. Comprender la representacin de nmeros binarios con signo empleando la notacin complemento a 2. Repasar las operaciones aritmticas elementales: suma, resta, multiplicacin y divisin. Establecer claramente el concepto de overflow y su comparacin con el carry. Concepto de punto fijo y flotante. Comprender la necesidad de codificar la informacin. Describir lo mtodos de deteccin y correccin de errores: paridad, checksum, cdigos de redundancia cclica y Hamming.

1 INTRODUCCION
Un microprocesador, como cualquier sistema digital, emplea dos estados (0 y 1) para la representacin de informacin. Cabe recordar que los smbolos 1 y 0 representan esos dos estados y no tienen ningn significado numrico por s mismos. Sin embargo, cuando estos smbolos se utilizan para representar los dgitos del sistema numrico binario, ellos se deben manejar de acuerdo a las reglas del sistema numrico. Por lo tanto, en esta unidad se ver el tratamiento de los sistemas numricos necesario para su implementacin en computadoras. Al final de la unidad veremos la necesidad de codificar la informacin y distintas alternativas para la deteccin y correccin de errores en la transmisin de datos.

2 SISTEMA DE NUMERACIN
Un sistema de numeracin es un conjunto de smbolos y reglas de generacin que permiten construir todos los nmeros vlidos en el sistema. Un sistema de numeracin puede representarse como N = S + R donde:

 N es el sistema de numeracin considerado. S son los smbolos permitidos en el sistema. En el caso del sistema decimal son

{0,1...9}; en el binario son {0,1}; en el octal son {0,1...7}; en el hexadecimal son {0,1...9,A,B,C,D,E,F}.
R son las reglas de generacin que nos indican qu nmeros son vlidos y cules son

no-vlidos en el sistema. Estas reglas son diferentes para cada sistema de numeracin considerado, pero una regla comn a todos es que para construir nmeros vlidos en un sistema de numeracin determinado slo se pueden utilizar los smbolos permitidos en ese sistema (para indicar el sistema de numeracin utilizado se aade como subndice al nmero). De una forma general y amplia podemos clasificar los sistemas de numeracin en dos grandes tipos: Posicionales: El valor de los smbolos que componen el sistema depende del valor que se les ha asignado, y de la posicin que ocupan en el nmero (Nmeros decimales). No Posicionales: El valor de los smbolos que componen el sistema es fijo, y no depende de la posicin que ocupa el smbolo dentro del nmero (Nmeros romanos)

3 METODOS DE REPRESENTACION NUMERICA

Un nmero N, en un sistema de numeracin posicional, se representa como: N = dp-1*bp-1 + dp-2*bp-2 + .....+ d0*b0 + d-1*b-1 + d-q*b-q donde: b : base o raz del sistema numrico. ds: dgitos o smbolos del sistema numrico, que son los b dgitos permitidos. p : nmero de dgitos enteros. q : nmero de dgitos fraccionarios. N se puede expresar como: N = dp-1dp-2 ... d0.d-1d-2 ... d-q punto base p=0 q=0 p<>0 y q<>0 nmero fraccionario nmero entero nmero mixto [1]

3.1 Sistema Decimal

N10 = 27,510 = 2*101 + 7*101 + 5*10-1

b (base)= 10 d (dgito)= 0,1,2,3,4,5,6,7,8,9 p=2 y q=1.

3.2 Sistema Binario

N2 = 101.012 = 1*22 + 0*21 + 1*20 + 0*2-1 + 1*2-2 = 4 + 0 + 1 + 0 + 1/4 = 5.2510 b (base) = 2 d (dgito)= 0,1 p=3 y q=2.

3.3 Sistema decimal codificado en BCD

Decimal 0 1 2 3 4 5 6 7 8 9 | | no usados | Binario 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

El cdigo BCD es la representacin de los 10 dgitos del sistema decimal con 4 bits del sistema binario.

3.4 Sistema Octal

N8 = 34.18 = 3*81 + 4*80 + 1*8-1 = 24 + 4 + 1/8 = 28.12510 b (base) = 8 d (dgito) = 0,1,2,3,4,5,6,7 p=2 y q= 1.

3.5 Sistema Hexadecimal

N16 = D56.A216 = 13*162 + 5*161 + 6*160 + 10*16-1 + 2*16-2 = 3414.632810

b (base) = 16 d (smbolo) = 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F p=3 y q=2 La utilidad y conversin con el sistema binario es similar al sistema octal, con la nica diferencia que los bits se agrupan de a cuatro. Este sistema es usado como entrada/salida en muchas aplicaciones con microprocesadores, como kits de desarrollo, interfaces, etc., ya que provee un medio eficiente para especificar direcciones, datos e instrucciones (8 y 16 bits).

4 RANGO DE UN NUMERO
Cuando se representan nmeros en una base b y m dgitos, hay bm nmeros posibles en un rango de 0....bm-1. Sea Nb un nmero entero cualquiera, ste tendr un equivalente decimal que caer en el rango 0...bm-1, y podr ser representado exactamente como muestra la Fig. 1.1 Sea: b: base m: nmero de dgitos Entonces habr bm nmeros en el rango [0 ..... bm1 ] Nmeros Enteros |__________|_________|__________| 00 01 10 11 b=2 m=2 Nb = 012 =110

Figura 1.1 Nmeros Fraccionarios (rango [0...1] )

Cuando se trabaja con nmeros fraccionarios hay infinitos nmeros en el intervalo entre 0 y 1, por lo tanto, como m (nmero de dgitos) es finito, nicamente se pueden representar bm fracciones (puntos), siendo el salto entre puntos: @ = b-m (@: Intervalo de resolucin) [2]

|____|____|____|____|____|__....__|____|____| 0 | | 1 @
valor de fraccin que puede ser representado exactamente.

Figura 1.2

Aproximaciones: Para representar una fraccin (punto) que no corresponda a los valores de representacin exacta, ser necesario aproximar. Para ello hay dos formas comunes: Truncacin Redondeo

Sea Fb el valor verdadero del nmero tal cual se expresa a continuacin: Fb = .a-1a-2a-3...a-ma-(m+1)a-(m+2)....a-(m+p)

i i = (m + p)

a *b

[3]

Siendo m el nmero de dgitos a utilizar.

4.1 Truncacin
Se dice que una fraccin es truncada cuando todos los dgitos a la derecha de a-m se desprecian. @ |______...__________|___________.______|________..... 0 fv Fb fv+1 Et Figura 1.3 fv: valor truncado Fb: valor real Et: error por truncacin (Et < b-m) El mximo error cometido (ver Fig 1.3) ser siempre menor que el intervalo de resolucin; es decir: Et < b-m Ejemplo Fb = .23749 fv = .237 m=3 donde fv es el valor truncado.

4.2 Redondeo
Se dice redondeo cuando se selecciona el valor ms prximo al valor deseado, es decir que verifica si el valor se encuentra de la mitad del intervalo de resolucin a la derecha o a la izquierda. Por supuesto, esto requiere una complejidad adicional en el hardware. @ |______...__________|___________.______|________..... 0 fv Fb fv+1 Et Figura 1.4 Er: error por redondeo (Er @/2 ) Fb = .23749 fv = .238 m=3 donde fv es el valor por redondeo.

5 CONVERSION DE SISTEMAS NUMERICOS

Las conversiones ms importantes son: decimal-binario, decimal-octal y decimalhexadecimal, ya que cualquier otra conversin entre esos cuatro sistemas se puede realizar como una combinacin de los anteriores. En muchos casos, la conversin de un nmero fraccionario finito, expresado en un sistema numrico de base b1, no produce un nmero fraccionario finito equivalente en una base b2. El error entre ambas representaciones lo determina el nmero de dgitos empleados en la representacin en la base b2.

5.1 Conversin Decimal-Binario

La conversin de nmeros enteros y fraccionarios decimales en binarios, se lleva a cabo por sucesivas divisiones y multiplicaciones, respectivamente, por la base (2). Nmeros Enteros Como resultado de la divisin de un nmero decimal por dos, se obtiene un cociente Q y un resto R. Los restos que se obtienen de las sucesivas divisiones son los bits del nmero binario. El resto R es siempre un nmero entero menor que el divisor (dos en este caso), por lo tanto R puede ser 0 1. N = dp-1*2p-1 + dp-2*2p-2 + .....+ d0*20 1. N/2 = dp-1*2p-2 + dp-2*2p-3 + .....+ d0*2-1 |____________________||______| Q0: cociente R0: resto d0=R0: bit menos significativo

2. . . . p.

Q0/2 = Q1 + d1 * 2-1 d1=R1: prximo bit . . . donde Qp-1= 0 Qp-2/2 = Qp-1 + Rp-1 dp-1=Rp-1: bit ms significativo.

Ejemplo: N=13 13/2 = 6 6/2 = 3 3/2 = 1 1/2 = 0 y R0=1 y R1=0 y R2=1 y R3=1

1310 = 11012

Nmeros Fraccionarios En este caso se multiplica sucesivamente por dos. Los enteros resultantes son los sucesivos dgitos a la base convertida. N = d-1*2-1 + d-2*2-2 + ... + d-q*2q 1. 2*N = d-1*20 + d-2*2-1 + ... + d-q*2-q+1 |_____| |_________________|
I-1: entero X-1: fraccin

d-1=I-1: bit menos significativo. 2. 2*X-1 = d-2*20 + d-3*2-1 + ... + d-q*2-q+2 |_____| |__________________|
I-2: entero X-2: fraccin

. . q+1.

d-2=I-2: prximo bit . . 2*X-q+1 = d-q*20 = I-q d-q=I-q: bit ms significativo

Ejemplo N=0.55 2*0.55 = 1.1 ---> 2*0.1 = 0.2 ---> 2*0.2 = 0.4 ---> 2*0.4 = 0.8 ---> 2*0.8 = 1.6 ---> 0.5510 = 0.100012

d-1= 1 d-2= 0 d-3= 0 d-4= 0 d-5= 1

5.2 Conversin Decimal-Octal

La conversin de nmeros enteros y fraccionarios decimales a octales se lleva a cabo por sucesivas divisiones y multiplicaciones, respectivamente, por la base (8). Ejemplo: N=1310 13/8 = 1 y R0 = 5 1/8 = 0 y R1 = 1 1310 = 158

5.3 Conversin Decimal-Hexadecimal

La conversin de nmeros enteros y fraccionarios decimales a hexadecimales se lleva a cabo por sucesivas divisiones y multiplicaciones, respectivamente, por la base (16). Ejemplo: N=1310: 13/16 = 0 y R0 = 13 1310 = D16

6 NUMEROS CON SIGNO

En el sistema binario (b=2) si se disponen de m dgitos, es posible representar 2m nmeros en un rango de 0 hasta 2m-1. Con esta restriccin, si se necesita representar nmeros con signo, es necesario resignar el rango de operacin (2m-1-1), ya el bit ms significativo representa el signo del nmero. Las premisas ms importantes que debe cumplir un buen sistema de representacin son: que tenga igual cantidad de nmeros positivos como negativos, que exista un nico cero, que se puedan realizar las operaciones aritmticas bsicas (suma, resta, multiplicacin y divisin), etc.

6.1 Representacin
Hay tres formas bsicas de representar nmeros con signo en el sistema binario. Bit de Signo o "Magnitud Signada" Complemento a dos Complemento a uno

Debido a que en el sistema binario no se encuentran otros smbolos ms que 0 y 1, es que se utiliza el bit ms significativo del nmero como signo del nmero. Donde un 0 significa que el nmero positivo, y un 1, que es un nmero negativo.

6.1.1

Bit de Signo o Magnitud Signada

En esta representacin, para una palabra de n bits, los n-1 bits de la derecha representan la magnitud del nmero y el nmero positivo si comienza con cero (0) y si el mismo empieza con uno (1) el nmero es negativo. Ejemplo: Sea N = 810 = 10002 8 = 01000 -8 = 11000

6.1.2

Complemento a Dos

El complemento (N') de un nmero (N) en una base b se define como: N' = bp N p: nmero de dgitos de N b: base bp: mdulo El mdulo toma distintas denominaciones de acuerdo con el sistema numrico que se emplee. Por ejemplo, para el sistema decimal, se denomina complemento a 10, y para el sistema binario, complemento a 2. Ejemplo N=2010 -----> N' = 100 - 20 = 80 N=10012 -----> N' = 10000 - 1001 = 0111 Es importante notar que el complemento de un nmero depende del mdulo elegido. Hay dos formas de hallar el complemento a dos de un nmero: Hallar el complemento lgico del nmero y luego sumarle 1. 1001 -----> 0110 ------> 0110 + 1 = 0111 Comenzando del bit menos significativo, dejar todos los bits sin cambio hasta el primer 1 inclusive, luego complementar los restantes. [4]

6.1.3

Complemento a Uno

El complemento a 1 (N") de un nmero (N), tambin llamado complemento de base disminuida, no es ms que el complemento lgico del nmero o el complemento a dos menos uno. N" = bp - N - 1

si el nmero fuese mixto (q <> 0), N" = bp - b-q - N

6.1.4

Complemento Como Nmeros Negativos

Para representar nmeros con signo en la forma de complemento, se consideran nmeros negativos a aqullos cuyo bit ms significativo es "1", y nmeros positivos a aqullos cuyo bit ms significativo es "0". La diferencia con magnitud-signada, radica en la forma de interpretar los bits restantes. La representacin de nmeros positivos y negativos como complemento, tiene significativas ventajas sobre la representacin bit de signo desde el punto de vista de hardware y de software.

6.1.5

Nmeros en Complemento a Dos

Un nmero entero expresado en complemento a dos tiene la siguiente expresin: N = -d7*27 + . . . + di*2i Un nmero fraccionario expresado en complemento a dos tiene la siguiente expresin: N = -d0*20 + . . . . + d-i*2-i La representacin en una recta sera:
1001 1000 1011 1101 1111 0001 0000 0011 0101 0111

[5]

[6]

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1010 1100 1110 0010 0100 0110

-8 -7 -6 -5 -4 -3 -2 -1 0

1 2

3 4 5 6

Sea p el nmero de bits incluido el bit de signo, entonces habr 2p nmeros posibles siendo el rango de variacin de nmeros: -2p-1 <= N <= 2p-1 -1 6.1.6 Nmeros en Complemento a Uno

La representacin en una recta sera:

1001 1000 1011 1100 1101 0001 0011 0101 0111 0110

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1010 1110 0000 0010 0100

-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5

6 7

Sea p el nmero de bits incluido el bit de signo, entonces habr 2p nmeros posibles siendo el rango de variacin de nmeros: -(2p-1-1) <= N <= 2p-1 -1

Uno de los inconvenientes de esta representacin es que tiene dos formas de representar el cero. Esto requiere de interpretaciones adicionales de los resultados para la toma de decisiones.

6.1.7

Eleccin del Sistema de Representacin Numrica

Se pueden mencionar tres razones principales por las cuales la eleccin de la representacin en complemento a dos es la ms adecuada: 1. El hardware aritmtico es ms simple que en bit de signo y no mucho ms complejo que en complemento a uno. 2. En complemento a uno y bit de signo existen dos formas de representar al cero (existe un +0 y un -0). Esto causa ciertos problemas en el hardware para la toma de decisiones, por ejemplo saltar si el resultado es negativo. 3. Hay resultados incorrectos en complemento a uno y bit de signo que se deben corregir. Ejemplo:(-107)+(-10)= =-117

6.2 OPERACIONES ARITMETICAS

En un microprocesador la ALU (Unidad Aritmtico-Lgica) es la parte del procesador encargada de realizar las operaciones aritmticas y lgicas con los datos suministrados. Los datos manejados por la ALU provienen y se almacenan en registros. La ALU debe adems activar indicadores (banderas o flags) como resultados de las operaciones realizadas. Por lo tanto definiremos una serie de banderas que nos permitirn interpretar los resultados obtenidos. Y para poder descifrar a las banderas, debemos observar las operaciones aritmticas elementales.

6.2.1

Suma Binaria M+N=S

La suma de M + N produce:

N 0 0 1 1 M 0 1 0 1 ___________________________ S 0 1 1 10 transporte (carry) Las funciones lgicas que implementan la operacin suma con la generacin de su respectivo carry son: S = X + Y = X XOR Y Cy = X AND Y

El carry se produce cuando se supera la capacidad del dgito (en la base que se trabaje 1: binaria, 9: decimal) en una columna (peso) determinada. Cuando se trabaja con computadoras no se puede tener infinitos bits de representacin de nmeros. Es decir, que los nmeros se representan por n bits (generalmente 4, 8, 16, 32 bits). Por lo tanto el flag de carry indica que tuve un desborde en el rango de representacin de los nmeros naturales (sin signo). Si el mximo rango de representacin de nmeros con signos (positivos o negativos) se excede, el flag de carry no nos brinda informacin de desborde del rango de representacin. Cuando se trabaja con nmeros enteros (con signo), la condicin de desborde se indica con un flag denominado "overflow" (si se desbordan los nmeros positivos) o "underflow" (si se desbordan los nmeros negativos). [Link] Suma en Complemento a Dos En complemento a dos, con (n+1) bits se pueden representar nmeros en el rango de (2n 1) a (-2n). Por ejemplo, con 8 bits el rango es de +127 a -128. Por lo tanto, cualquier operacin que exceda dicho rango producir "overflow".

Condiciones para la Deteccin de Overflow Se analizarn cuatro casos testigos, que permiten encontrar cules son las condiciones en las que se produce overflow, y as poder generalizarlo. 0110 (+6) 0110 (+6) 1001 (-7) + + + + 0011 (+3) 0001 (+1) 1101 (-3) ------ ---- ------ ---- ------ ---0 1001 -7 0 0111 +7 1 0110 +6 C=0 Cs=1 donde: C : es el carry Cs: es el carry al bit de signo (bit2 bit3) C=0 Cs=0 C=1 Cs=0 1010 (-6) 1111 (-1) ------ ---1 1001 -7 C=1 Cs=1

Por lo tanto, ocurre overflow si y slo si la suma de dos nmeros de igual signo produce un nmero de signo opuesto. C 0 0 1 1 Cs 0 1 0 1 V 0 1 1 0

Cs XOR C = V

Otra forma de determinar el overflow (V) es: Z XOR C. Sin embargo es necesario verificar previamente los signos de los operandos.

6.2.2

Resta Binaria M-N=R (Borrow)

La resta binaria produce: M 0 0 1 1 N 0 1 0 1 R 0 1 1 0 B 0 1 0 0

R = M - N = M XOR N B = /M AND N donde: M: minuendo N: sustraendo Si trabajamos con nmeros naturales, el "borrow" significa que el minuendo es menor que el sustraendo, y se debe "pedir prestado" a la prxima columna. Una de las mayores ventajas de usar complemento, es que la resta se lleva a cabo tomando el complemento del sustraendo y luego se realiza la suma de los mismos. Es decir, se podra simplificar el hardware. M - N = M + (comp N) Ejemplo: 1100 (-4) 1100 (-4) + 0110 (+6) 1010 (-6) -----------0 0110 -10 1 0110 -10

[Link] Relaciones Overflow/Underflow Carry/Borrow Se analizarn distintos casos que permitirn establecer relaciones entre los flags Overflow/Underflow Carry/Borrow resultantes de operaciones de resta entre 2 nmeros enteros.

0100 (+4) 0100 (+4) + 1011 (-5) 0101 (+5) ------ --------- ---1 1001 +9 0 1001 +9 B=1 Bs=0 C=0 Cs=1

1100 (-4) 0110 (+6) ------ ---0 0110 -10 B=0 Bs=1 +

1100 (-4) 1010 (-6) ------ ---1 0110 -10 C=1 Cs=0

donde: C : carry Cs: carry al bit de signo (bit2 ---> bit3) B : borrow Bs: borrow del bit de signo (bit3 ----> bit2) Analizando los cuatro casos del ejemplo anterior se puede deducir que el borrow es el carry complementado y que el overflow es: V' = /B XOR /Bs = C XOR Cs = V donde: V: es el overflow (denominado underflow ) que se produce en la resta. Por lo tanto, los circuitos que detectan el overflow en la suma tambin lo harn en la resta. En general, los procesadores utilizan el mismo bit para representar el carry y el borrow. Esto se debe a que son complementarios.

6.3 Doble Precisin

Cuando se desea mayor precisin en las operaciones aritmticas que las que provee un microprocesador utilizando la longitud de palabra estndar, se debe recurrir a la mltiple precisin.

6.3.1

Suma

Para realizar la suma se procede en igual forma que en simple precisin, con la nica diferencia que la parte ms significativa se debe sumar agregando el carry de la operacin anterior.

1 0110 + 1001 1001

1101 0110 0110

6.3.2

Resta

Para realizar la resta se procede en igual forma que en simple precisin, con la nica diferencia que la parte ms significativa se debe restar teniendo en cuenta el borrow anterior. Una forma alternativa de implementarla sera complementar el sustraendo, y proceder como en el caso de la suma. 1 0001 + 1110 0000 1001 + 1110 0111 (-18) 07 (25)

Con respecto a las condiciones de overflow, valen las mismas reglas que en el caso de simple precisin.

6.4

Operaciones en BCD

El cdigo BCD es la representacin de los 10 dgitos del sistema decimal con 4 bits del sistema binario. Esta representacin genera un conjunto de 6 valores no permitidos, que requiere que algunos resultados de operaciones aritmticas sean corregidos.

6.4.1

Suma en BCD

Los smbolos BCD son 0...9, por lo tanto, con 4 bits de representacin, los smbolos A...F no son vlidos. Esto quiere decir que al realizar operaciones aritmticas ser necesario hacer algunas correcciones al resultado. Veremos los tres casos resultantes de una operacin de suma aritmtica: I. 0110 (6) + 0010 (2) 0 1000 (8) correcto [0] [8] II. 0110 (6) + 0111 (7) 0 1101 (13) incorr. + 0110 (6) 1 0011 [1] [3] correcto III. 1001 (9) + 1001 (9) 1 0010 (18) incorr. + 0110 (6) 1 1000 [1] [8] correcto

El caso I. es el nico resultado correcto, por lo tanto no necesita ningn tipo de correccin. Los casos II. y III. Dan resultados incorrectos, por lo tanto es necesario adicionarle 6 para obtener el valor correcto. Resumiendo, hay dos casos de ajuste decimal de la suma de dos nmeros A y B: si A + B 10 con carry = 0 si A + B < 10 con carry = 1

Para usar BCD con signo ser necesario usar un bit adicional (en un lugar de memoria) para llevar el signo.

6.4.2

Resta BCD

Hay dos formas posibles para realizar la resta BCD: a. Realizar un hardware que realice la resta decimal con borrow. b. Hallar el complemento a 10 del sustraendo en BCD y luego sumarlos. Para hallar el complemento a 10 de un nmero BCD de dos dgitos se puede hacer lo siguiente: a. Obtener el complemento a dos de cada dgito individualmente, sin tener en cuenta el carry. b. Sumar al dgito menos significativo 1010, y al ms significativo, 1001. Ejemplo 0010 0110 (26) 1110 1010 + 1001 1010 0111 1010 complemento a 2 individual

7410

10010 - 2610 = 7410

6.5 Representacin Punto Flotante (FP)

Hasta ahora tratamos con nmeros enteros y/o fraccionarios en notacin punto fijo. Es decir, que los nmeros se representan por una cantidad fija de dgitos y cuyo punto base (decimal, binario, etc.) era fijo. Este tipo de representacin limita el rango de nmeros a representar (por ejemplo, en complemento a 2 es: [2m-1- 1] a [-2m-1] ). La representacin en punto flotante (FP) bsicamente presenta las ventajas de ajustar automticamente la escala y extender el rango de nmeros que el procesador puede manejar. Los primeros microprocesadores (4 y 8 bits) no implementaban aritmtica en punto flotante (FP) debido al reducido canal de datos y a la baja velocidad de operacin. Slo cuando era necesario, se recurra a implementaciones por software. El advenimiento de los microprocesadores de 16, 32 y 64 bits hicieron posible las implementaciones de aritmtica en FP. La representacin de un nmero en FP se la siguiente: N * rp

donde: N: es la mantisa r: es la base p: es el exponente Dado un nmero fijo de bits para la representacin en FP, existe un compromiso entre rango y precisin: Cuando mayor es el rango, menor es la precisin. Formato Actualmente la Sociedad del IEEE propuso el estndar P754 para aritmtica en FP para nmeros binarios. Este estndar especifica los formatos de nmeros en FP, los resultados de las operaciones en FP, conversin de nmeros, etc. Un nmero en FP se representa como una cadena de bits compuesta por tres componentes bsicos: Signo de la mantisa (s) Mantisa (l.f) Exponente entero con signo (e) En algunos casos se considera un cuarto campo que corresponde al signo del exponente. Bit: s Exponente (e) 1 Fraccin (f) . 0 1 8 9 10 31

Si s = 0 el nmero es positivo y si s = 1, es negativo. El exponente e es la potencia de 2 que determina el rango del nmero. Y la mantisa, (l.f), determina la precisin del nmero. La mayor exactitud se logra cuando l = 1. De esta forma, cualquier nmero, distinto de cero, se puede expresar como: 2e * (1.f) Exponente El exponente de un nmero binario en FP puede ser:

Exponente con signo en complemento a dos o en magnitud y signo. Exponente polarizado.

En el primer caso, el exponente es un nmero con expresado en alguna de las formas de expresin de nmeros con signo. En el segundo caso, correspondiente a la representacin estndar del IEEE, al exponente se le adiciona un nmero entero constante (polarizacin) que lo mantiene siempre positivo. Sea N el nmero de bits del exponente, por lo tanto la polarizacin ser: 2N-1-1 (es decir, la polarizacin ser de la forma 0111....111).

6.6 Multiplicacin
El producto binario P de 2 nmeros X (multiplicando) e Y (multiplicador) es: X 0 0 1 1 Sea N: Y 0 1 0 1 P 0 0 0 1

N = dp-1*2p-1 + dp-2*2p-2 + .....+ d0*20

Si multiplicamos por la base (2) ser: 2 * N = dp-1*2p + dp-2*2p-1 + .....+ d0*21 Ejemplo: N = 101 2 * N = 1010 o sea, multiplicar por dos es equivalente a desplazar un bit a la izquierda completando con ceros en la derecha. Ejemplo 1011 * 1101 1011 0000 1011 1011 10001111 Veamos algunos algoritmos de multiplicacin: Algoritmo de multiplicacin de nmeros naturales: Sean X e Y dos nmeros de p y q bits, respectivamente. Para implementar el producto ser necesario utilizar dos registros: uno de p+q lugares, para almacenar el producto parcial, y otro, de p+q-1 lugares, a donde se llevar y rotar X. En los microprocesadores, esto se puede realizar por hardware o software. En el primer caso, se consigue mayor velocidad, y en el segundo, mayor flexibilidad.

Algoritmo de Booth: Este es un algoritmo para multiplicar nmeros con signo expresados en complemento a dos, sin tener necesidad de testear previamente los signos.
Testear Transiciones en el Multiplicador

Iguales N N Sumar
0 1

Restar

Desplazamiento Aritmtico N

ltimo Bit S

Ejemplo: Se aplicar el algoritmo de Booth para realizar el producto de dos nmeros negativos (-3 * -5).

-3 111101 * -5 111011(0) 15 000000 000011 000011 0000011 00000011 111101 11110111 111110111 000011 000001111 0000001111 00000001111 000000001111 \/ signo

15

6.7 Divisin
La divisin de un nmero M/N es: M = N*Q + R1 donde: M: dividendo N: divisor R1: resto Q: cociente Un algoritmo que pueda realizar la divisin de nmeros naturales, M/N, consiste en restar sucesivamente R-N (donde R es inicialmente igual a M, y luego R=R-N) hasta que haya borrow. Entonces en Q nos queda la cantidad de veces que entra el divisor en el dividendo.

7 CODIGOS
Algunos ejemplos de cdigos son: ASCII EBCDIC EXCESO 3 GRAY

7.1 Manejo de Informacin Empaquetada y Desempaquetada

Es muy importante el manejo de informacin en la memoria del microprocesador. Por ejemplo, informacin codificada en ASCII se puede almacenar en la memoria en forma empaquetada o desempaquetada: supongamos que se desea almacenar los caracteres hexadecimales A, B, C y D. Ejemplo: Cdigo ASCII: A (41H), B (42H), C (43H), D (44H) Empaquetada 41 42 43 44 Desempaquetada 41 42 43 44

La ventaja de utilizar la forma empaquetada, es que se emplea mejor la memoria, sin embargo, en forma desempaquetada, la informacin se puede manejar ms fcil y rpidamente.

7.2 Cdigos Detectores y Correctores de Errores

La capacidad para detectar posibles errores en la informacin manipulada por las computadoras es esencial para poder confiar en los resultados ofrecidos. El error es la alteracin del valor correcto en uno o ms bits de informacin producida durante su almacenamiento, transmisin o manipulacin. Cuando se transmite informacin entre sistemas digitales, se puede producir prdida de informacin debido a problemas de ruido, deformacin de la seal (desadaptacin de impedancias, ancho de banda, "crosstalk", etc.). Los errores en un sistema de comunicaciones digitales se producen fundamentalmente por dos tipos de fallas: Eventos estticos Eventos dinmicos

Los eventos estticos (EE) son aquellos de comportamiento y existencia conocidos, como podra ser: distorsin de seal, prdida por atenuacin, crosstalk, etc. Los eventos dinmicos (ED) son aquellos que ocurren en forma aleatoria, como sera los disturbios elctricos producido por descargas atmosfricas, transitorios en lneas elctricas de alimentacin, etc, y todo aquello que por su naturales no se pueda prever su ocurrencia. ED

S1 EE

S2

Para ello, es necesario detectar los errores producidos. Aquellos provenientes de EE son ms fciles de manejar, ya que sus efectos son predecibles, no sucede lo mismo con los ED, cuya naturaleza aleatoria los hace impredecibles. Hay muchos mtodos y cdigos sofisticados, siendo posible en algunos casos recuperar la informacin transmitida. Para poder detectar o incluso corregir posibles errores en la informacin, es preciso aadir informacin redundante de comprobacin. La redundancia (R) es la informacin agregada a los datos (D) de acuerdo con alguna formulacin matemtica conocida. El proceso de deteccin de errores consiste en comprobar si el conjunto datos/redundancia (D,R) cumple o no dicho formulacin, entonces: Si la formulacin se cumple, se asume que la informacin es correcta. Si la formulacin no se cumple, est claro que la informacin contiene errores. Si la informacin redundante agregada permite conocer cules son los bits errneos, es posible realizar la correccin de los mismos y reconstruir la informacin original. Un concepto muy importante relativo a la correccin y deteccin de cdigo de errores es el trmino distancia. La distancia entre dos nmeros binarios es igual a la cantidad de bits que difieren entre s, se decir, es la cantidad de bits diferentes entre un nmero y otro. Por ejemplo entre 000 y 001, la distancia es 1 y entre 000 y 011, es 2.

Sean X e Y dos palabras de un cdigos de n bits, y sea el operador w el nmero de 1's del mensaje w. Luego la distancia entre X e Y se define como: D(X,Y) = X Y La distancia mnima se define como el nmero de bits que deben cambiar para pasar de una palabra de cdigo vlida a otra palabra de cdigo vlida. Por lo tanto un cdigo que detecte un error simple, tendr una distancia mnima de 2. La regla general para la correccin de errores es: sea un cdigo de n bits y sea k la cantidad de errores a corregir. La combinaciones deberan elegirse de tal manera que una de otra difieran de al menos de una distancia 2k + 1. En general si la distancia mnima entre las combinaciones de un cdigo es 2k, luego es posible detectar 2k-1 errores o detectar hasta k errores y simultneamente corregir k - 1 errores. Si la distancia mnima es 4, puede detectar errores dobles y corregir errores simples. Regla General: Cdigo Cantidad de Errores a Corregir Distancia Mnima En general: Detecta 2k-1 n bits k bits 2k + 1bits

Dmin = 2 k Los cdigos que vamos a estudiar son: Mayora Paridad Checksum Cdigos de Redundancia Cclica (CRC) Hamming Detecta k Corrige k-1

Como se dijo anteriormente, si D es el campo de datos y R la redundancia a ser agregada, entonces el paquete de informacin I a ser enviado ser una funcin de la forma: I = [D+R]. Por lo tanto, el paquete de informacin I se formar por los dos campos: Dgitos de Informacin (D) Dgitos de Checheo (R)

7.2.1

Funcin Mayora

El mecanismo denominado Funcin Mayora, consiste en repetir la informacin un determinado nmero n de veces, normalmente un nmero impar (n 3). Por lo tanto, el receptor dispondra de varias copias de la informacin que deberan ser exactamente iguales. Si hay errores en la informacin recibida, normalmente afectarn a una sola copia o a un nmero pequeo de ellas. En consecuencia, el receptor seleccionar como informacin correcta a la copia que se repite mayor cantidad de veces. De ah surge la importancia de elegir un nmero de copias impar. Es posible considerar que la funcin mayora se comporte como un mecanismo para detectar y/o corregir errores. 7.2.2 Paridad

Consiste en enviar un bit extra a cada caracter enviado, para mantener un nmero par o impar de unos (paridad par o impar, respectivamente). Para calcular la redundancia para paridad par, se debe implementar la funcin or-exclusiva entre los bits: P=dn1dn2...d1d0 Para calcular la redundancia para paridad impar, se debe implementar la funcin orexclusiva negado entre los bits: I=dn1dn2...d1d0 Ejemplo: 0 1010110 Paridad par 1 1010110 Paridad impar A este mtodo tambin se lo llama Chequeo de Redundancia Longitudinal ("Longitudinal Redundancy Check" LRC). Una forma alternativa de chequear paridad, es enviando un carcter adicional, en donde se han calculado las paridades de los bits en columna de cada caracter: Ejemplo: 10110011 10100011 10011110 10001110 Caracter 1 Caracter 2 Caracter 3 Caracter de Chequeo (paridad par)

Ejemplo de un cdigo ASCII correspondiente a la secuencia CINCO:

En este caso se denomina Chequeo de Redundancia Vertical ("Vertical Redundancy Check" VRC). El agregado de un bit de paridad de redundancia, hace que la distancia mnima sea 2.

7.2.3

Checksum

El "Checksum" se calcula como la suma mdulo 256 del total de caracteres a enviar (es decir que no se tiene en cuenta el carry producido). Este mtodo consiste, por lo tanto, en enviar el resultado del clculo como un carcter adicional. Ejemplo: 11001001 10000110 00101101 01111100 Caracter 1 Caracter 2 Caracter 3 Checksum

Este cdigo puede verse como una variedad de VRL. Los mtodos descriptos tienen el inconveniente de detectar nicamente un error simple, ya que si se genera un error doble stos no lo detectan. 7.2.4 Chequeo de Redundancia Cclica (CRC)

Este mtodo es mucho ms efectivo que los anteriores en la deteccin de errores en los sistemas de comunicaciones. No permite la correccin de errores. En este mtodo, en forma similar a los anteriormente descriptos, se enva uno o ms caracteres adicionales de redundancia denominados FCS ("frame check sequence") o BCC ("block check caracter"), que difieren fundamentalmente en la forma de calcularlo. El CRC consiste en considerar a los bits a ser transmitidos como un polinomio en x (para n bits el orden es n-1) tal que la presencia de un trmino significa un "1", y la ausencia, un "0"; es decir: sean 1010101 los bits a transmitir, entonces el mensaje podr ser considerado como un polinomio G(x) tal que: G(x) = x7 + x5 + x3 + 1 Un mensaje de cdigo cclico consiste en un nmero de bits de datos y el BCC. Sea n el nmero total de bits y k el nmero de bits de datos, por lo tanto, el nmero de bits del BCC es n - k. El cdigo del mensaje (BCC) se obtiene de 2 polinomios: Dados: P(x): polinomio generador G(x): polinomio de mensaje de datos polinomio generador P(x) mensaje polinomial G(x) (bits de datos).

Se desea hallar F(x), cdigo del mensaje polinomial, como sigue:

Multiplicar el mensaje G(x) por x, siendo n - k el nmero de bits del BCC para dar lugar al BCC (multiplicar por x, es lo mismo que desplazar el mensaje polinomial de datos n-k lugares completando con ceros a la derecha). G(x) * xn-k G(x) 0........0

Dividir el producto resultante G(x) * xn-k por el polinomio generador P(x). G(x) * xn-k = Q(x) P(x) + C(x)

Despreciar el cociente y sumarle a G(x) * xn-k el resto C(x) de la divisin para producir el cdigo de mensaje polinomial F(x). F(x) = G(x) * xn-k + C(x) ; Mensaje Polinomial a Transmitir

Para entender las operaciones anteriores, es necesario tener en cuenta que estamos utilizando aritmtica mdulo 2. Es decir que tanto la suma como la resta binaria son la funcin OR exclusivo bit a bit sin acarreo. Adems es importante notar que la cantidad de bits del resto C(x) (n-k) ser de un orden menor que el del polinomio generador P(x) (n-k+1). Por lo tanto, conociendo el nmero de bits de P(x), se puede determinar la cantidad de ceros que se debe agregar a G(x) para realizar la divisin polinomial. Para hallar el polinomio G(x) se considera que la mayor potencia de x corresponde al bit ms significativo, es decir: sean 101000111 los bits a transmitir, entonces G(x) ser: Ejemplo de clculo de la redundancia: Sea la informacin original G(x) = 11001, patrn P(x)=101 Primero se multiplica G(x) por 22: G(x) 2k = 1100100 El resultado anterior se divide entre P(x)=101

Entonces la trama enviada ser: 1100110

 Ejemplo de implementacin: Sea el mensaje de datos: 101000111 entonces: G(x) = x8 + x7 + x6 + x2 + 1 El hardware necesario para realizar la divisin en aritmtica mdulo 2 ser el siguiente:

x0 donde el polinomio generador es: P(x) = x5 + x4 + x2 + 1

x2

x4

x5

Un polinomio generador muy conocido es el CRC-16 cuyo P(x) es: P(x) = x16 + x15 + x12 + 1 Con respecto al receptor, ste se implementa realizando la divisin de la informacin recibida por el mismo polinomio generador que el transmisor. Si el resto de la divisin es 0, entonces la informacin se recibi sin error, en caso contrario se asumir que hubo un error en la transmisin. El efecto general que se observa en el chequeo por medio del CRC, es que cualquier bit se refleja en varios bits por un tiempo considerable despus que ste fue transmitido. Esto es muy importante, ya que se ha comprobado que la mayora de los problemas de errores en comunicacin de datos se producen en pequeos grupos de bits ("burst"). Caractersticas ms significativas del CRC: Detecta todos los errores de 1 y 2 bits (errores simples y dobles). Detecta todos los errores de un Burst menor que el grado de P(x) Detecta el 99 % de los errores de un Burst mayor que el grado de P(x) Cdigo corrector de errores por paridad vertical y horizontal

7.2.5

Este cdigo corrector de errores, emplea un mtodo combinado de chequeo de errores, paridad horizontal y vertical. Si un error simple ocurre en una palabra de cdigo, luego ambos chequeadores indican, en conjunto, la fila y la columna donde se halla el bit con error. Por lo tanto, este cdigo, es capaz de detectar y corregir un error simple.

LCR 1000 1001 0110 0100 0010 0111 VCR 1001

0 1 1 0 0 0 1

7.2.6

Cdigos Hamming

El cdigo Hamming es un cdigo de distancia 3, capaz de detectar errores dobles y corregir si hay un error simple. El cdigo Hamming se forma por n bits de informacin (Mn, Mn-1, ... M1) y k bits de chequeo (Ck, Ck-1, ..... C1) de paridad par o impar. El mensaje codificado est formado por n + k bits, siendo k el menor entero que cumple que: 2k n+k+1 [7]

(por ejemplo, si n = 7, entonces k = 4). Hamming es un cdigo capaz de corregir un error simple por lo tanto debe identificar un bit errneo en una cadena de bits. Entonces la ecuacin [7] nos dice que el nmero de combinaciones de los bits de chequeo (2k) debe ser al menos igual al nmero de bits del mensaje ms los bits de redundancia ms una combinacin extra para identificar que no hubo errores. Los bits de chequeo ocupan posiciones especficas en el mensaje codificado. Esas posiciones son potencias enteras de 2, es decir 1,2,4,8, .... 2k-1, es decir que los bits de paridad se ubican en los posiciones que tienen un nico bit a 1 en su ordinal. Los valores de cada Ci se calculan chequeando la paridad en lugares especficos del mensaje original M. Por ejemplo para un cdigo de 6 bits de mensaje, el mensaje codificado ser: M6
1010

M5
1001

C4
1000

M4
0111

M3
0110

M2
0101

C3
0100

M1
0011

C2
0010

C1
0001

C1 = M1 M3 M5 M7 M9 ....... C2 = M2 M3 M6 M7 M10 ....... C3 = M4 M5 M6 M7 ............ C4 = M8 M9 M10 . ............. Para el clculo de los coeficientes Cis, los valores de Mis empleados, se refieren a la posicin que ocupan los elementos en el mensaje codificado, tomando a M1 igual a cero (ya que corresponde al valor de Ci del mensaje codificado) para el clculo inicial. Luego se reemplazan los valores de los Ci calculados en las posiciones del mensaje codificado. En el receptor: se chequea la misma paridad aplicada al mensaje codificado. Es decir que se vuelven a calcular los coeficientes de la misma manera como fueron generados. Luego se calcula el nmero posicional P como:

P = pkpk-1....p2p1 Si P = 0, el resultado es correcto. Si P 0, el nmero indica la posicin (el bit) con error. Ejemplo error simple: Supongamos que se recibe un carcter ASCII f (1100110B) con un error simple en la posicin M4: M7 M6 M5 C4 M4 M3 M2 C3 M1 C2 C1
1 1 0 0 1 1 1 0 0 1 0

C1 = 0 0 1 1 0 1 = 1 C2 = 1 0 1 1 1 1 = 1 C3 = 0 1 1 1 = 1 C4 = 0 1 1 0 = 0 Entonces la posicin a corregir ser: P = p4p3p2p1 = 0111 (o sea la 7). Ejemplo error doble: Supongamos que se recibe un carcter ASCII f (1100110B) con un error doble en las posiciones M2 y M4: M7 M6 M5 C4 M4 M3 M2 C3 M1 C2 C1
1 1 0 0 1 1 0 0 0 1 0

C1 = 0 0 0 1 0 1 = 0 C2 = 1 0 1 1 1 1 = 1 C3 = 0 0 1 1 = 0 C4 = 0 1 1 0 = 0 Si se asume que hay un nico bit errneo, se trata del que tiene el ordinal 2, es decir, C2 que era un bit correcto. Por lo tanto se realiza una correccin errnea, ya que hay un error doble. Para distinguir el caso de error simple del de error doble, se puede aadir un bit de paridad transversal T, o LRC, a la cadena de bits enviados (que no se usa para calcular las paridades de Hamming), tal que: Si no hay errores, P = 0 y T: correcto. Si hay un error simple, P 0 y T: incorrecto. Es posible corregir el bit errneo. Si hay un error doble, P 0 y T: correcto. No es posible corregir el error.