ARQUITECTURA DE COMPUTADORAS UNIDAD 1

SISTEMAS DE NUMERACIN
INTRODUCCIN Los nmeros naturales aparecen al contar los objetos de un conjunto. En la primera infancia se empieza por aprender a contar, luego ms tarde se coordinan conjuntos prescindiendo del orden. Lo mencionado parece justificar la introduccin del nmero natural mediante la formulacin axiomtica que revele en qu consiste la operacin de contar. Con posterioridad a la invencin del nmero natural surge la necesidad de ampliar el concepto de nmero. Surge as el nmero entero, el racional, el irracional y el nmero real. Aceptando la existencia del nmero podemos definir un Sistema de Numeracin como el conjunto de reglas y convenios que permiten la representacin de todos los nmeros mediante varios signos, o varias palabras. Existen Sistemas de Numeracin muy conocidos como el Romano que descompone el nmero en suma o diferencia de otros varios, cada uno de los cuales est representado por un smbolo especial: I, V, X, L, C, D, M Otro sistema es el Decimal que en vez de introducir nuevos smbolos para estos diversos sumandos, utiliza el principio del valor relativo (posicional), es decir una misma cifra representa valores distintos segn el lugar que ocupa. Estos de sistemas son los que representan inters matemtico. El Sistema Decimal que fue inventado en la India en el siglo IV antes de Cristo y llevado a Europa por los rabes en la Edad Media, est fundado en el nmero fijo que llamamos diez (habiendo elegido este y no otro porque tenemos diez dedos en las manos). Toda combinacin de operaciones fundamentales efectuadas con nmeros cualesquiera que da origen a un nuevo nmero, se llama algoritmo de numeracin. Para los sistemas de numeracin basados en el valor relativo (posicionales), el algoritmo de numeracin consiste en un polinomio: N = anbn + an-1bn-1 + an-2bn-2 + ..... + a1b1 + a0b0 + a-1b-1 + a-2b-2 + ...... + a-kb-k Donde: N : Nmero ai : nmero natural menor que b (smbolo) b : base del sistema (cantidad de smbolos diferentes del sistema, es un nmero natural mayor que 1) n + 1: cantidad de cifras enteras. k : cantidad de cifras fraccionarias. Obsrvese que la parte entera del nmero se corresponde a los trminos del polinomio que tienen la base b elevada a exponentes cero o positivos mientras que la parte fraccionaria se corresponde con los exponentes negativos. Puede apreciarse el principio de valor relativo, por ejemplo el nmero 24,2 en el conocido sistema de numeracin decimal tiene el siguiente polinomio: 24,2 = 2 x 10 1 + 4 x 10 0 + 2 x 10 - 1 Obsrvese que 2 tiene un valor que depende de la posicin que ocupa en el nmero. Las propiedades de los nmeros, que se estudian en Matemticas, son vlidas cualquiera sea la base utilizada, siempre que se utilice el mismo algoritmo de numeracin. Es decir que si elegimos otra base podramos realizar operaciones algebraicas (suma, resta, multiplicacin, divisin, etc.) sin ningn problema ya que la axiomtica y teoremas parten del algoritmo de numeracin. Como se dijo anteriormente la eleccin de 10 (diez) como base, fue que tenemos diez dedos en las manos, pero podemos hacernos esta pregunta: Es el Sistema de Numeracin Decimal el ms adecuado para ser usado en sistemas fsicos de representacin y tratamiento de la informacin? La respuesta resulta de consideraciones de costo y confiabilidad del Sistema Fsico a construir. Confiabilidad Podemos decir que un sistema es ms confiable cuanto ms independiente sea de la temperatura en la que trabaja, el envejecimiento y la dispersin de los componentes que lo forman. UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 1 de 20

Los componentes que se utilizan en la construccin de los sistemas fsicos de procesamiento de informacin, son elctricos y electrnicos (transistores, diodos, resistores, capacitores, inductores, etc.), todos ellos cambian sus parmetros con el envejecimiento y la temperatura. Adems es imposible construir dos componentes idnticos, a esto se lo llama dispersin. Los fabricantes especifican el porcentaje de dispersin mximo de los componentes que comercializan. A fin de aclarar lo mencionado comparemos dos sistemas fsicos (ver fig. 1) que representan nmeros en distintas bases: base 10 y base 2:

b) FIG. 1 La fig.1a indica un circuito elctrico capaz de representar un nmero decimal (base 10), y la fig.1b indica un circuito elctrico capaz de representar un nmero binario (base 2). Ambos consisten en un foco que se enciende con distintas intensidades luminosas al mover la llave (diez en el caso a y dos en el caso b), y suponen que un observador tiene que ser capaz de determinar el nmero en cuestin apreciando la intensidad luminosa. Como primera conclusin resulta evidente que es ms fcil determinar el estado del foco en caso b (prendido o apagado) que en el caso a (diez intensidades posibles). Como segunda conclusin. Supongamos que aumenta la temperatura ambiente o que el circuito ha envejecido, esto modifica el valor de las resistencias y de la intensidad emitida por el foco. La temperatura y el envejecimiento afectan mucho ms al caso a que al b. Como tercera conclusin. Supongamos que tenemos que reponer el foco porque se quem. El nuevo foco, debido a la dispersin, tendr seguramente parmetros diferentes al anterior. (Mismas consideraciones si debisemos reemplazar una resistencia). La dispersin afecta ms al caso a que al b. Como conclusin final puede decirse que el circuito que trabaja en binario es ms confiable que el decimal. Podemos decir que es ms confiable que cualquier circuito que trabaje en cualquier base. Si bien los sistemas digitales no se construyen con focos y llaves, lo considerado es aplicable a los componentes que se utilizan en la realidad. Costo Nuevamente observando la fig.1 desde el punto de vista del costo podemos afirmar que es ms costoso construir el circuito en decimal que en binario: el Costo es proporcional a la base del sistema de numeracin utilizado, sin embargo necesitamos ms circuitos binarios para representar una misma cantidad, (por ejemplo para representar el nmero 25 necesitaramos dos circuitos decimales como el de la fig.1a y cinco circuitos binarios como el de la fig.1b). : el Costo es proporcional a la cantidad de cifras. Entonces podemos escribir: Costo = k . b . (n+1) Entre b y (n + 1) existe una relacin: b(n+1) = M Donde M : Mdulo del Sistema (mximo nmero representable con n+1 cifras) (n+1).Ln b = Ln M n + 1 = (Ln M / Ln b) reemplazando UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 2 de 20

a)

Costo = k Ln M (b / Ln b) Haciendo la derivada respecto a la base (dCosto/db= 0) e igualando a cero obtenemos: bptima = e Concluimos que la base ptima, desde el punto de vista del costo, est entre 2 y 3. En realidad,la expresin del costo planteada es aproximada y teniendo en cuenta la confiabilidad, es el Sistema Binario el que se utiliza en la construccin de los Sistemas Digitales. Sistema de Numeracin Binario En el Sistema Binario los smbolos utilizados son el 0 y el 1, llamados dgitos binarios (bits o bitios). Es posible, aplicando el algoritmo de numeracin, obtener los nmeros binarios correspondientes a las primeras 1610 (el subndice 10 indica que el nmero esta en Sistema Decimal) cantidades. Igualmente podramos obtener los nmeros en el Sistema Octal y en el Sistema Hexadecimal. La fig.2 indica las correspondencias. DECIMAL b = 1010 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BINARIO b = 210 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 OCTAL b = 810 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 HEXADECIMAL b = 1610 0 1 2 3 4 5 6 7 8 9 A B C D E F

Obsrvese que en el Sistema Hexadecimal de han agregado las letras A, B, C, D, E y F para obtener los 16 smbolos distintos necesarios. La razn de tener en cuenta este Sistema es que 24 = 16, por lo tanto a cada 4 cifras binarias se corresponder 1 cifra hexadecimal. Tambin en el Sistema Octal se da algo parecido ya que 23 = 8, por lo tanto cada tres cifras binarias se corresponde una Octal. Esto ltimo nos permite encontrar rpidamente las equivalencias entre binario, Octal y hexadecimal, por ejemplo: 0010 1001 1110 01012 = 29E516 110 111 111 001 000 1108 = 6771068 Un grupo de cuatro bits recibe el nombre de nible y un grupo de ocho bits recibe el nombre de octeto o byte. Es usual en estos temas utilizar los prefijos kilo, mega, giga, tera de una manera similar que en el Sistema Mtrico Decimal, pero con algunas diferencias, a saber: 1 Kilo = 1K = 1024 = 210 1 Mega = 1M = 1024K = 220 1 Giga = 1G = 1024M = 230 1 Tera = 1T = 1024G = 240 As, cuando decimos por ejemplo 1Mbit, estamos indicando que se trata de 1.048.576 bits (220), o si decimos 1Kbyte estamos indicando 1024 bytes (210) Todas las operaciones aritmticas estudiadas en el lgebra aplicadas a nmeros al Sistema Decimal, son aplicables a los nmeros binarios por cuanto ambos Sistemas responden al mismo algoritmo de numeracin.

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 3 de 20

Conversin entre nmeros de distintas bases Para convertir las expresiones de nmeros entre distintas bases puede usarse el siguiente procedimiento general: a) Parte entera del nmero (trminos del polinomio con la base elevada a exponentes cero o positivos) Supongamos que el primer miembro de la siguiente igualdad esta expresado en un Sistema de Numeracin en base b = b1, y el segundo miembro en base b = b2 Nb1 = an b2n + an-1 b2n-1 + ........ + a1 b21 + a0 b20 Si dividimos miembro a miembro entre b1 vemos que el ltimo trmino del segundo miembro ser a0, que es el resto de la divisin y la cifra menos significativa del nmero en base b2. Repitiendo la divisin entre el cociente anterior y b2, obtendremos como resto a1, y as sucesivamente hasta llegar a an. Un ejemplo aclarar lo expuesto: Ejemplo: b1 = 1010 Nb1 = 2510 b2 = 210 25 Resto = 1 2 12 Resto = 0 2 6 Resto = 0

2 3 Resto = 1

2 Resto = 1

De acuerdo a lo mencionado, tenemos: 2510 = 110012 b) Parte fraccionaria del nmero (trminos del polinomio con la base elevada a exponentes negativos) Supongamos que el primer miembro de la siguiente igualdad esta expresado en un Sistema de Numeracin en base b = b1, y el segundo miembro en base b = b2 Nb1 = a-1 b2-1 + a-2 b2-2 + ........ + ak+1 b2k+1 + a-k b2-k Si multiplicamos miembro a miembro por b1 observamos que el primer trmino del segundo miembro es a-1, es decir la primera cifra ms significativa de la parte fraccionaria. Reiterando la multiplicacin slo sobre la parte fraccionaria del resultado, vamos obteniendo las sucesivas cifras menos significativas. Un ejemplo aclarar lo expuesto: Ejemplo: b1 = 1010 Nb1 = 0,2110 b2 = 210 0,21 x 2 = 0,42 0,42 x 2 = 0,84 0,84 x 2 = 1,68 0,68 x 2 = 1,36 0,36 x 2 = 0,72 0,72 x 2 = 1,44 0,44 x 2 = 0,88 ............. ............. De acuerdo a lo mencionado tenemos: 0,2110 = 0,0011010........2 Si tenemos nmeros con parte entera y fraccionaria, aplicamos la parte a) y la parte b). Complementos Complemento a la base: El complemento a la base de un nmero N que posee m cifras enteras, se define como: UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 4 de 20

Cb(N) = bm - N Complemento a la base disminuida: El complemento a la base disminuida de un nmero N que posee m cifras enteras, se define como: Cb-1(N) = bm - N - 2-k Donde k es la cantidad de cifras fraccionarias. Si bien los complementos se aplican a Sistemas de Numeracin de cualquier base, los utilizaremos especialmente en el Sistema de Numeracin Binario, en este caso los llamaremos Complemento a Dos y Complemento a Uno. Veamos algunos ejemplos: Ejemplo de Complemento a 2: C2(100112) = 1021012 - 100112 = 1000002 - 100112 = 011012 Ejemplo de Complemento a 1: C1(100112) = 1021012 - 100112 - 12 = 1000002 - 100112 -12 = 011002 De ahora en adelante se omitirn los subndices 2 para indicar nmeros binarios, a menos que no se pueda interpretar correctamente. Observando los ejemplos vemos que el Complemento a 1 puede obtenerse cambiando ceros por unos y viceversa. Esto es consecuencia de restar a m unos un nmero de m bits. Como consecuencia de lo anterior el Complemento a 2 de un nmero binario puede obtenerse cambiando unos por ceros y viceversa y sumando uno, de acuerdo a la definicin de Complemento a 2. Para el caso de nmeros binarios con parte fraccionaria ( por ejemplo 1100011,110) la definicin y reglas mencionadas siguen siendo vlidas. Representacin de los nmeros negativos en binario Los nmeros negativos se pueden representar de distintas formas, a saber: a) Valor Absoluto y Signo: Supongamos un nmero binario de n bits, el bit ms significativo se reserva para el signo (bit de signo Bs) y los restantes para el valor absoluto (Mantisa M), esta es la forma en que representamos los nmeros negativos en decimal. Bit de Signo 0 (cero) : + (positivo), 1 (uno) : - (negativo). b) Mediante el Convenio de Complemento a 2: El bit ms significativo es el bit de signo, los restantes (Mantisa M), si el nmero es negativo, son el complemento a 2. . Bit de Signo 0 : + (positivo), 1 : - (negativo). Mediante el Convenio de Complemento a 1: El bit ms significativo es el bit de signo, los restantes (Mantisa M), si el nmero es negativo, son el complemento a 1. Bit de Signo 0 : + (positivo), 1 : - (negativo).

c)

d) Mediante el Convenio Exceso 2n-1: El bit ms significativo es el bit de signo, los restantes (Mantisa M), si el nmero es negativo, son el complemento a 2. . Bit de Signo 0 : - (negativo), 1 : + (positivo). Veamos un ejemplo de los distintos Convenios para un nmero de 3 bits. (n = 3). Obsrvese que: Usando Complemento a 2 se tiene un solo cero lo que puede resultar una ventaja como despus se ver. Usando Exceso 4 a menores combinaciones binarias absolutas se corresponden menores equivalentes decimales. Esto es til para la representacin de los exponentes en Punto Flotante, como veremos luego. En Unidades posteriores se ver la conveniencia del uso de los Convenios que usan Complementos ya que de esta forma la operacin resta se puede realizar mediante una suma. Esto simplifica los circuitos lgicos. UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 5 de 20

Combinacin Binaria (n = 3) Bs Mantisa 0 00 0 01 0 10 0 11 1 00 1 01 1 10 1 11

Valor absoluto y Signo +0 +1 +2 +3 -0 -1 -2 -3

Usando Complemento a 2 0 +1 +2 +3 -4 -3 -2 -1

Usando Complemento a 1 +0 +1 +2 +3 -3 -2 -1 -0

Exceso 4 -4 -3 -2 -1 0 +1 +2 +3

A excepcin del Valor Absoluto y Signo, la utilizacin de estas representaciones para realizar operaciones aritmticas requiere de definir reglas apropiadas que se irn exponiendo ms adelante. No obstante adelantaremos algunos conceptos. En la tabla de arriba puede observarse que para el caso de los Convenios que usan Complemento a 2 y Complemento a 1 se puede incluir el bit de signo como un bit ms del nmero, as por ejemplo para encontrar la combinacin binaria correspondiente a -3 en el Convenio que usa Complemento a 2, basta con partir de la combinacin correspondiente a +3 (011) y encontrar su Complemento a 2 incluyendo el Bit de Signo, es decir C2(011) = 1000 - 011 = 101. De esta forma el Bit de Signo se utiliza como un bit ms. Veamos el siguiente ejemplo: +3 + (-3) = 0 ser usando el Convenio de Complemento a 2: 011 + 111 _______ 1000 Donde el 1 de la izquierda se rechaza por tratarse de nmeros de 3 bits. Si usamos el Convenio de Complemento a 1 ser: +1+ ( - 3) = -2 001 + 100 _______ 101 Como se ve hemos usado el bit de signo como si se tratara de un bit ms. Punto Fijo y Punto Flotante Lamentablemente no todos los nmeros son enteros, as surgen representaciones binarias con una, dos, tres o ms dgitos (bits) fraccionarios segn la necesidad. La llamada Notacin en Punto Fijo resuelve ese problema, por ejemplo un formato podra ser: 1101001,101 en este caso disponemos de 10 bits para representar el nmero de los cuales 7 son enteros y 3 fraccionarios. Al construir un Sistema Digital debemos fijar el mismo formato para todos los nmeros. Adems en las ciencias es usual la necesidad de representar nmeros muy pequeos y a la vez nmeros muy grandes. Con una cantidad limitada de dgitos resulta imposible abarcar un amplio rango de cantidades sin usar la llamada Notacin en Punto Flotante. Esta Notacin, muy similar a la Notacin Cientfica, divide al nmero en tres campos, a saber: Signo de la Mantisa Exponente: Signo del Exponente Mantisa del Exponente Mantisa UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 6 de 20

Signo de la Mantisa

Exponente

Mantisa

Signo de la Mantisa (S) Es un campo de 1 bit. 0 positivo ( + ) 1 negativo ( - ) Exponente (E) Es un campo de varios bits con la Convencin Exceso 2n-1, por ejemplo el Exceso 64 (7 bits) y el Exceso 128 (8 bits). Mantisa(M) Es un campo de varios bits fraccionarios. Para que el nmero est normalizado, el bit ms significativo debe ser 1, es decir que la mantisa debe ser mayor o igual a 1/2 y menor que 1.

Operaciones Aritmticas Las operaciones aritmticas con nmeros en punto flotante tienen ciertas particularidades. Sean S1E1M1 y S2E2M2 dos nmeros en punto flotante normalizados y en Exceso 64. Multiplicacin El producto de los dos nmeros ser SpEpMp, donde: Signo de la mantisa Sp = 0 si S1 = S2 Sp = 1 si S1 | S2 Exponente Ep = E1 + E2 - 64 - K, siendo K el valor que satisface 1/2 <= M1 x M2 x 2K < 1 Mantisa Mp = M1 x M2 x 2K Divisin La divisin de los dos nmeros ser SdEdMd, donde: Signo de la mantisa Sd = 0 si S1 = S2 Sd = 1 si S1 | S2 Exponente Ed = E1 - E2 + 64 - K, siendo K el valor que satisface 1/2 <= (M1 / M2) 2K < 1 Mantisa Md = (M1 / M2) 2K Suma y resta Para sumar o restar los dos nmeros debemos igualar sus exponentes. Debido a que los exponentes estn en Exceso y en esta convencin menores nmeros se corresponden con menores combinaciones binarias absolutas, la comparacin es muy sencilla. Supongamos que: E1 > E2 Entonces encontramos j, tal que j = E1 - E2 Modificamos S2E2M2 a fin de igualar los exponentes: S2(E2 + j)M2/2j Procedemos a sumar o restar las mantisas segn sea el caso. El resultado debe ser luego normalizado como se expuso en la divisin y el producto. Base de Exponenciacin A fin de aumentar el rango de representacin la base de exponenciacin en vez de 2 puede ser 4, 8 o 16. Por ejemplo si en una representacin en punto flotante la base de exponenciacin es 8, la mantisa debe interpretarse en Octal (grupos de 3 bits partiendo desde la coma hacia la derecha). La normalizacin en estos casos se entiende cuando el dgito ms significativo (grupo de tres bits) de la mantisa no es cero. Norma IEEE 754 A fin de estandarizar la representacin en punto flotante el IEEE dict la Norma 754 (1985) la cual es respetada actualmente por la mayora de los fabricantes de procesadores. Esta norma establece tres tipos de representacin: UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 7 de 20

1 bit 1 bit 1 bit 15 bits 11 bits

Simple Precisin (32 bits) 8 bits 23 bits Doble Precisin (64 bits) 52 bits Precisin Extendida (80 bits) 64 bits

Los exponentes mnimo y mximo se utilizan para casos especiales.

Ya que las mantisas normalizadas siempre empiezan con 1, no es necesario almacenarlo y la coma implcita se coloca a la derecha del 1, entonces la mantisa, ahora llamada significando, es mayor o igual a 1 y menor que 2. Se consideran 5 clases de nmeros, a saber: 1. +/2. +/3. +/4. +/5. +/Normalizados 0 < E < Mximo Cualquier patrn de bits

Desnormalizados (el bit 1 a la izquierda de la coma del significando, ahora es 0) 0 Cualquier patrn de bits excepto cero Cero (el bit 1 a la izquierda de la coma del significando, ahora es 0) 0 0 Infinito 1111....1111111 0

No numero (Indica el cociente Infinito/Infinito) 1111....1111111 Cualquier patrn de bits excepto cero

CDIGOS Definicin: CDIGO: ley de correspondencia biunvoca entre los elementos de dos conjuntos. Cdigo es una representacin unvoca de algn conjunto de elementos de tal forma que, a cada uno de estos, se le asigna una combinacin de smbolos determinados y viceversa. Para comunicarse hay que conocer el cdigo utilizado. codificar

F= {F1 , F2 , ...Fq}
Alfabeto fuente Conjunto de smbolos de un alfabeto dado decodificar

C= {C1 , C2 , ...Cq}
Alfabeto cdigo Palabra cdigo: cada secuencia CiCj Longitud de la palabra: nmero de smbolos Ci Nmero de smbolos: base del cdigo

Cdigos numricos: son cuando los elementos de los dos conjuntos son nmeros CDIGOS BINARIOS Los sistemas de numeracin (binario, octal, hexadecimal, etc) estudiados constituyen cdigos de representacin de las cantidades. CDIGOS BINARIOS: la base del cdigo es 2, son los utilizados por los sistemas digitales. El sistema de numeracin binario recibe el nombre de cdigo binario natural:

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 8 de 20

decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

binario natural 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Con n cifras binarias (bits) se pueden obtener 2n combinaciones diferentes. Cada combinacin se puede asignar a un elemento (o cantidad) distinto. Es decir, que: Un grupo de n bits binarios es un cdigo de n bits que puede asumir 2n combinaciones distintas de 1s y 0s. Para que el cdigo sea til no se puede asignar ninguna combinacin a ms de un elemento, y varan de 0 a (2n 1) Aunque el mnimo nmero de bits requerido para escribir un cdigo con 2n elementos distintos es n, el mximo nmero de bits no est especificado. Con estas combinaciones podramos tener 2n! (las permutaciones de las 2n combinaciones) cdigos distintos; aunque solo se vern algunos con caractersticas particulares. En el estudio de los cdigos binarios existen algunos con ciertas caractersticas, como: Cdigos binarios continuos (o progresivos): son aquellos que las combinaciones correspondientes a nmeros decimales consecutivos son adyacentes. Se llaman combinaciones binarias adyacentes las que difieren solamente en un bit. Cdigos binarios cclicos: son aquellos cdigos continuos que la ltima combinacin es adyacente a la primera. Ejemplos: decimal 0 1 2 3 4 5 6 7 continuo 0000 0001 0011 0110 0111 1111 1110 1100 cclico 0000 0001 0011 0111 1111 1110 1100 1000 Entre dos combinaciones seguidas cambia un solo bit

Entre primero y ltimo cambia un solo bit El ejemplo ms tpico de un cdigo continuo y cclico es el llamado de GRAY, el cual puede tener 2, 3, 4 ms bits de acuerdo a la necesidad. Tambin llamado reflejado porque para construir el cdigo de n bits, se reflejan las combinaciones del cdigo n-1. Se utiliza principalmente en convertidores muy rpidos y en codificadores. Como de una combinacin binaria a la contigua slo cambia un bit, se aumenta la velocidad y se elimina el riesgo de transiciones intermedias. Para ampliar palabras codificadas en este cdigo, en un bit ms, basta con repetir simtricamente las combinaciones (como si fuera un espejo) y agregar un bit a la izquierda, siendo cero para la primera mitad y uno para la segunda mitad de las combinaciones posibles. Representamos a continuacin el cdigo de Gray para 2, 3 y 4 bits.

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 9 de 20

decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 bits 00 01 11 10

GRAY 3 bits 0 00 0 01 0 11 0 10 1 10 1 11 1 01 1 00 4 bits 0 000 0 001 0 011 0 010 0 110 0 111 0 101 0 100 1 100 1 101 1 111 1 110 1 010 1 011 1 001 1 000

Otro ejemplo de cdigo binario continuo y cclico es el de Johnson, el cual representamos a continuacin con 5 bits: decimal 0 1 2 3 4 5 6 7 8 9 Cdigo JOHNSON 00000 00001 00011 00111 01111 11111 11110 11100 11000 10000

Cdigos BCD: Los nmeros puros se representan con la notacin octal o con la hexadecimal, por su facilidad de conversin. Sin embargo, la conversin binaria a decimal es bastante difcil, y en las calculadoras, los juegos electrnicos, y los instrumentos digitales, en los que que generalmente es comn la entrada y salida de nmeros en notacin decimal, se emplea un cdigo especial para representar esta notacin . A este cdigo se le llama CODIGO BCD: decimal codificado en binario (binary - coded - decimal). Con esta tcnica es posible convertir cada numero decimal a su equivalente en binario, en lugar de convertir el valor decimal entero a su forma binaria pura. Para poder representar los diez dgitos decimales (del 0 al 9) son necesarios 4 bits. De las 16 combinaciones posibles (24) que se obtienen con los 4 bits, slo se utilizan diez. Los cdigos BCD se pueden clasificar en: Ponderados: poseen una regla de formacin que adjudica un cierto peso a los unos binarios segn la posicin que ocupan en el conjunto de los 4 bits, debindose verificar que la suma algebraica de los pesos de cada combinacin sea igual al nmero decimal representado. Los ejemplos ms tpicos son el BCD natural (que tiene los pesos 8 4 2 1) y el AIKEN (que tiene los pesos 2 4 2 1). Libres o no ponderados: en estos la correspondencia decimal-binaria es arbitraria con respecto a que no existen pesos ni sumas algebraicas, aunque en general las combinaciones se forman segn ciertas reglas especficas para cada cdigo. El ejemplo tpico es el Exceso 3 que se forma partiendo del BCD natural y sumndole 3 a cada combinacin.

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 10 de 20

decimal 0 1 2 3 4 5 6 7 8 9

Binario natural 8421 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 ponderados

AIKEN 2421 0000 0001 0010 0011 0100 1011 1100 1101 1110 1111

Exceso 3 n+3 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 Libre

La conversin de un nmero decimal a un cdigo BCD se realiza simplemente expresando cada dgito mediante la combinacin binaria que le corresponde de acuerdo al cdigo especificado. Por ejemplo el nmero decimal 926 lo representamos en distintos cdigos: Nmero decimal 9 2 6 BCD natural 1000 0010 0110 BCD AIKEN 1111 0010 1100 BCD exceso 3 1100 0101 1001

Cdigos Alfanumricos Muchas aplicaciones de computadoras digitales, requieren manejar datos que consisten no solamente de nmeros sino tambin de letras. Por ejemplo una compaa de seguros con millones de clientes pueden usar un computador digital para procesar sus historias. Para representar el nombre del dueo de una pliza en forma binaria, es necesario tener un cdigo binario para el alfabeto. Adems el mismo cdigo binario puede representar nmeros decimales y algunos otros caracteres especiales. Un cdigo alfanumrico es un cdigo binario de un grupo de elementos consistente de los diez nmeros decimales, los 26 caracteres del alfabeto y de cierto nmero de smbolos especiales tales como el $ Uno de estos cdigos es conocido como ASCII (American Standard Code for Information Interchange = Cdigo normalizado americano para el intercambio de informacin). A continuacin se muestra una lista del cdigo ASCII de 7 bits para los nmeros, letras maysculas y signos de puntuacin. El cdigo ASCII completo tiene cdigos para letras minsculas y signos de control. ASCII incluye 256 cdigos divididos en dos conjuntos, estndar y extendido, de 128 cada uno. Estos conjuntos representan todas las combinaciones posibles de 7 u 8 bits. El conjunto ASCII bsico, o estndar, utiliza 7 bits para cada cdigo, lo que da como resultado 128 cdigos de caracteres desde 0 hasta 127 (00H hasta 7FH hexadecimal). El conjunto ASCII extendido utiliza 8 bits para cada cdigo, dando como resultado 128 cdigos adicionales, numerados desde el 128 hasta el 255 (80H hasta FFH extendido). En el conjunto de caracteres ASCII bsico, los primeros 32 valores estn asignados a los cdigos de control de comunicaciones y de impresora caracteres no imprimibles, como retroceso, retorno de carro y tabulacin empleados para controlar la forma en que la informacin es transferida desde una computadora a otra o desde una computadora a una impresora. Los 96 cdigos restantes se asignan a los signos de puntuacin corrientes, a los dgitos del 0 al 9 y a las letras maysculas y minsculas del alfabeto latino. Los cdigos de ASCII extendido, del 128 al 255, se asignan a conjuntos de caracteres que varan segn los fabricantes de computadoras y programadores de software. Estos cdigos no son intercambiables entre los diferentes programas y computadoras como los caracteres ASCII estndar. Por ejemplo, IBM utiliza un grupo de caracteres ASCII extendido que suele denominarse conjunto de caracteres IBM extendido para sus computadoras personales. Apple Computer utiliza un grupo similar, aunque diferente, de caracteres ASCII extendido para su lnea de computadoras Macintosh. Por ello, mientras que el conjunto de caracteres ASCII estndar es universal en el hardware y el software de los microordenadores, los caracteres ASCII extendido pueden interpretarse correctamente slo si un programa, computadora o impresora han sido diseados para ello. UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 11 de 20

CODIFICACION PARA DETECCION Y CORRECCION DE ERROR En la transmisin de informacin es posible que se produzcan errores debido a diferentes factores, como la presencia de ruido en el proceso, la avera de alguno de los componentes, etc. Especialmente cuando la informacin es numrica, no se aceptan errores, por lo que es necesario poder detectar la presencia de los mismos si se han producido. Si se detecta la presencia de un error es necesario retransmitir la informacin, mientras que si se puede detectar y corregir el error producido, no se produce la retransmisin. Cuando en un cdigo binario se utilizan todas las combinaciones posibles, no se pueden detectar errores; debido a que si cambia algunos de sus bits por error de una combinacin vlida, dara por resultado otra combinacin de bits vlida. Por lo tanto, podemos decir que para detectar errores es necesario no utilizar todas las combinaciones posibles. Esto ltimo es una condicin necesaria pero no suficiente. Para poder efectivamente detectar y/o corregir errores se da el concepto de distancia mnima de un cdigo: Distancia de un cdigo entre dos combinaciones binarias es el nmero de bits que cambian para pasar de una combinacin a la otra. Distancia mnima de un cdigo es la menor de las distancias entre dos combinaciones cualesquiera pertenecientes al cdigo. La distancia mnima de los cdigos vistos hasta ahora es la unidad, y por lo tanto no se pueden detectar errores. Por lo anterior, se deduce que, para poder detectar y/o corregir errores, es imprescindible que:

Distancia mnima > 1

Este concepto capacidad de deteccin y correccin de errores de un cdigo: nos da una idea de la

Distancia mnima 1 2 3 4

Significado Sin deteccin ni correccin Deteccin de error simple Deteccin de error doble y/o correccin de error simple Deteccin de error triple y/o correccin de error doble

CDIGOS DETECTORES DE ERROR: La manera ms simple de codificar un mensaje binario para permitir la deteccin de un error (un bit errado en cada combinacin) es contar el nmero de 1s (unos binarios) contenidos en el mensaje y agregarle un dgito binario (un bit) de forma tal que el mensaje tenga un nmero par de 1s (o un nmero impar de 1s). A esto se llama cdigo con paridad y al uno que se adiciona bit de paridad. Si el nmero de 1s es par se trabaja con paridad par y sino es impar. Antes de enviar una informacin es necesario ponerse de acuerdo en cual de las dos convenciones se trabaja. Al adicionarle un bit al cdigo se consigue que la distancia mnima sea por lo menos de 2. Ejemplo del cdigo BCD natural: decimal 0 1 2 3 4 5 6 7 8 9 BCD natural 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 BCD natural c/paridad par 0000 0 0001 1 0010 1 0011 0 0100 1 0101 0 0110 0 0111 1 1000 1 1001 0 BCD natural c/ paridad impar 0000 1 0001 0 0010 0 0011 1 0100 0 0101 1 0110 1 0111 0 1000 0 1001 1 Distancia mnima entre cualquier combinacin mayor que 1

Bit de paridad
UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 12 de 20

Esta caracterstica se puede realizar con cualquier cdigo con el cual se trabaje. La deteccin de errores en estos cdigos consiste en comprobar si el nmero de unos de cada combinacin cumple con la convencin adaptada. Es decir, si se trabaja con paridad par, se debe chequear que el dato recibido cumpla con esta condicin; si no es as existe un error, y se debe solicitar una nueva transmisin del dato. Otros cdigos detectores de error son los de cantidad constante de 1s, como:

decimal 0 1 2 3 4 5 6 7 8 9

2 entre 5 7421P 11000 00011 00101 00110 01001 01010 01100 10001 10010 10100

biquinario 5043210 0100001 0100010 0100100 0101000 0110000 1000000 1000010 1000100 1001000 1010000

Estos cdigos tienen dos unos en cada combinacin (o sea paridad par) y se forman de acuerdo a los pesos asignados. CDIGOS CORRECTORES DE ERROR Un cdigo corrector detecta si la informacin codificada presenta o no errores, y en caso afirmativo determina la posicin del bit o bits errneos, de manera de poder corregirlos por inversin (recordar que es el sistema binario, as que si un bit tiene error, se cambia por su complemento). Los cdigos de distancia mnima dos no permiten la correcccin de errores, porque al producirse un error la combinacin obtenida puede poseer dos adyacentes pertenenecientes a cdigo, y no es posible saber cul es la correcta. Por ejemplo si del cdigo 2 entre 5 se detecta la combinacin errnea 01000 (que no es vlida), no es posible conocer si el error se produjo en el primer bit (01001) o en el segundo bit (01010), ya que ambas combinaciones son vlidas. Por lo tanto se deduce que para corregir un bit de error es necesario una distancia mnima mayor a dos. En general para corregir bits de error se necesita una distancia dada por:

dm = 2n + 1
siendo n la cantidad de bits a corregir.

Un ejemplo tpico es el cdigo de Hamming: Su formacin parte de un cdigo cualquiera de n bits al que le adicionan p bits formando un nuevo cdigo de n + p bits. En este cdigo se realizan p detecciones de paridad, obtenindose un bit de paridad uno o cero (dependiendo si el nmero de bits es par o impar). El conjunto de los p bits de paridad forma un nmero en el sistema binario natural cuyo equivalente decimal nos indica la posicin del bit errneo. Si no hay error el nmero obtenido debe ser cero. Dado que con p bits se obtienen 2p combinaciones, se debe cumplir la siguiente realcin:

2p >= n + p + 1

II

Como ejemplo tomaremos el cdigo AIKEN, al cual queremos poder detectar y corregir un bit de error. Como n = 4 hay que agregarle p = 3 bits para cumplir con la condicin II, lo que nos queda un cdigo de 7 bits. Para detectar los siete posibles errores que se pueden producir en una combinacin (7 errores considerando 7 posiciones en cada combinacin) y la ausencia de error, son necesarias ocho combinaciones binarias (correctoras de error). Dichas combinaciones correctoras de error se obtiene mediante 3 bits (c1, c2 y c3), y el nmero decimal formado por ellos indica la posicin del bit errneo.

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 13 de 20

N decimal equivalente 0 1 2 3 4 5 6 7 Las combinaciones de estos bits son:

C3 C2 C1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

El bit c1 toma el valor 1 si se produce un error en los bits b1, b3, b5 y b7 de la combinacin del cdigo formado. Si el nmero de unos existentes en esas cuatro posiciones es siempre par, un error en uno cualquiera de esos cuatro bits lo convierte en impar. Por lo tanto, c1 vale uno si el nmero de unos en las posiciones dadas es impar, y cero en caso contrario. Si lo representamos en una funcin lgica: C1 = b1 b3 b5 b7

donde es el smbolo de la funcin OR-Exclusiva (que se estudiar despus), y que da como resultado 0 si el nmero de unos es par, y uno si el nmero de unos es impar. De igual manera obtenemos c2 y c3: C2 = b2 C3 = b4 b3 b5 b6 b6 b7 b7

Para generar los 3 bits (p bits) a agregarle al cdigo general consideremos que los bits b1, b2 y b4 aparecen una sola vez en las frmulas anteriores, con lo cual los generamos a partir de los otros, ya que por ejemplo b1 debe valer uno si el nmero de unos de b3, b5 y b7 es impar; por lo tanto: b1 = b3 b5 b7 b2 = b3 b6 b4 = b5 b6 b7 b7

de todo esto se deduce que el Cdigo Hamming resultante a partir del AIKEN es: N decimal equivalente 0 1 2 3 4 5 6 7 8 9 b7 b6 b5 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 b4 b3 b2 b1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 B3, b5, b6 y b7 son los bits del cdigo original AIKEN, mientras que los bits restantes se forman de acuerdo a las condiciones de paridad ( en este caso paridad par)

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 14 de 20

OTROS CODIGOS UTILIZADOS: CDIGO DE BARRAS El Cdigo de Barras es un arreglo en paralelo de barras y espacios que contiene informacin codificada en las barras y espacios del smbolo. Esta informacin puede ser leda por dispositivos pticos (lectores de cdigo de barras), los cuales envan la informacin leda hacia una computadora como si la informacin fuera una entrada de teclado. Otra definicin es: smbolos hechos de patrones de barras y espacios blancos y negros. Dentro de los cdigos de barra se codifican bits de informacin. Los datos son ledos por scanners especiales de cdigos de barra y se usan muy a menudo en conjunto con bases de datos. Los cdigos de barra no requieren ingreso manual por el ser humano ya que pueden ser ledos automticamente por los scanners y son virtualmente libres de error Los Scanners de cdigos de barra leen el patrn de barras blancas y negras (o mejor dicho, claras y oscuras) y decodifican el cdigo, convirtindolo en un string de caracteres que generalmente se guarda en una base de datos. Ventajas: Algunas de sus ventajas sobre otros procedimientos de coleccin de datos son: Se imprime a bajos costos Permite porcentajes muy bajos de error Los equipos de lectura e impresin de cdigo de barras son flexibles y fciles de conectar e instalar. Beneficios El cdigo de barras es una tcnica de entrada de datos, como son la captura manual, el reconocimiento ptico y la cinta magntica. Se considera que la tecnologa de cdigo de barras es la mejor tecnologa para implementar un sistema de coleccin de datos mediante identificacin automtica, y presenta muchos beneficios, entre otros. Virtualmente no hay retrasos desde que se lee la informacin hasta que puede ser usada Se mejora la exactitud de los datos Se tienen costos fijos de labor ms bajos Se puede tener un mejor control de calidad, mejor servicio al cliente Se pueden contar con nuevas categoras de informacin. Se mejora la competitividad. Aplicaciones Las aplicaciones del cdigo de barras cubren prcticamente cualquier tipo de actividad humana, tanto en industria, comercio, instituciones educativas, instituciones mdicas, gobierno, etc. Control de material en proceso Control de inventario Control de tiempo y asistencia Punto de venta Control de calidad Control de inventario Embarques y recibos Control de documentos Facturacin Bibliotecas Bancos de sangre Hospitales Control de acceso Control de tiempo y asistencia Caractersticas de un cdigo de barras Un smbolo de cdigo de barras puede tener, a su vez, varias caractersticas, entre las cuales podemos nombrar: Densidad: Es la anchura del elemento (barra o espacio) ms angosto dentro del smbolo de cdigo de barras. Est dado en mils (milsimas de pulgada). Un cdigo de barras no se mide por su longitud fsica sino por su densidad. WNR: (Wide to Narrow Ratio) UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 15 de 20

Es la razn del grosor del elemento ms angosto contra el ms ancho. Usualmente es 1:3 o 1:2. Quiet Zone: Es el rea blanca al principio y al final de un smbolo de cdigo de barras. Esta rea es necesaria para una lectura conveniente del smbolo.

Simbologas Un smbolo de cdigo de barras es la impresin fsica de un cdigo de barras. Una Simbologa es la forma en que se codifica la informacin en las barras y espacios del smbolo de cdigo de barras. Existen diferentes simbologas para diferentes aplicaciones, cada una de ellas con sus propias caractersticas. Las principales caractersticas que definen una simbologa de cdigo de barras son las siguientes: Numricas o alfanumricas De longitud fija o de longitud variable Discretas o continuas Nmero de anchos de elementos Autoverificacin. Las simbologas ms usadas son: EAN/UPC Comercio detallista, autoverificable, numrico, longitud fija.

Cdigo 39

Industrial, alfanumrico, 44 caracteres Codabar Bancos de sangre, bibliotecas I 2/5

Aplicaciones numricas, aerolneas, numrico Cdigo 93 Complementa al cdigo 39, alfanumrico UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 16 de 20

Cdigo 128 Industrial , alfanumrico, 128 caracteres ASCII

Caractersticas de un cdigo de barras Un smbolo de cdigo de barras puede tener, a su vez, varias caractersticas, entre las cuales podemos nombrar: Densidad: Es la anchura del elemento (barra o espacio) ms angosto dentro del smbolo de cdigo de barras. Est dado en mils (milsimas de pulgada). Un cdigo de barras no se mide por su longitud fsica sino por su densidad. WNR: (Wide to Narrow Ratio) Es la razn del grosor del elemento ms angosto contra el ms ancho. Usualmente es 1:3 o 1:2. Quiet Zone: Es el rea blanca al principio y al final de un smbolo de cdigo de barras. Esta rea es necesaria para una lectura conveniente del smbolo.

ENCRIPTACIN O CIFRADO Con la introduccin de las computadoras, especialmente en las empresas, fue evidente la necesidad de herramientas automticas para proteger los archivos y otras informaciones almacenadas en su memoria. El nombre genrico del tema que trata las herramientas diseadas para proteger los datos y frustrar a los usuarios no autorizados informticos es la Seguridad en Computadoras. Esta unidad temtica ha necesitado desarrollarse por la introduccin de redes y facilidades de comunicacin para transportar datos. La tecnologa esencial en todas las redes automticas y en las aplicaciones de seguridad en computadoras es la Encriptacin o Cifrado. La medida ms efectiva en contra de la amenaza de usuarios no autorizados es el encriptado o cifrado de datos, que debe interpretarse como el almacenamiento o transmisin de datos sensibles en forma cifrada. Dentro de la terminologa utilizada en este campo, se destaca el nombre de texto plano asignado a los datos originales. El texto plano es cifrado sometindolo a un algoritmo de cifrado, cuyas entradas son el texto plano y la clave de cifrado, y a la salida de este algoritmo (la forma cifrada del texto plano) se le llama texto cifrado. Aunque los detalles del algoritmo normalmente son de dominio pblico, la clase de cifrado se mantiene en secreto. El texto cifrado que debe ser ininteligible para cualquiera que posea la clave de cifrado, es lo que se guarda en las computadoras principales de la organizacin o se transmite por las lneas de comunicaciones de las redes. El esquema empleado debera ser tal, que el trabajo involucrado en romperlo sobrepase cualquier ventaja potencial que pudiera obtenerse al hacerlo. Existen dos tcnicas diferenciadas que pueden utilizar los algoritmos: la sustitucin y la permutacin. La sustitucin es uno de los enfoques bsicos del cifrado, como se practica tradicionalmente, donde se usa una clave de cifrado para determinar, para cada carcter del texto plano), un caracter de texto cifrado que va a sustituir a ese carcter. Con la tcnica de permutacin, los caracteres de texto plano son simplemente reorganizados en una secuencia diferente, bajo la influencia de la clave de cifrado. Por ejemplo, podramos usar una tcnica de sustitucin, en un algoritmo elemental, para cifrar el siguiente texto plano y clave de cifrado: Texto plano: Clave: ESTE ES UN TEXTO DEMO PRUEBA

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 17 de 20

Suponemos, por simplicidad, que los nicos caracteres de datos que tenemos que manejar son las letras maysculas y los espacios en blanco. Y que el algoritmo de cifrado por sustitucin sea el siguiente: 1. Dividimos el texto plano en bloques de longitud igual a la clave de cifrado. E M O

E S T E + E S + U N + T E X T O + D (los espacios en blanco son mostrados explcitamente como +). 2.

Reemplazamos cada carcter del texto plano por un entero que est en el rango de 00 a 26, usando espacio en blanco = 00, A = 01, ....., Z = 26. E S T E + E 05 19 20 05 00 05 S + U N + T 19 00 21 14 00 20 E X T O + D 05 24 21 15 00 04 E M O 05 13 15

3.

Repetimos el paso 2 para la clave de cifrado. P R U E B A 16 18 21 05 02 01

4.

Para cada bloque de texto plano reemplazamos cada carcter por la suma mdulo 27 de su codificacin de enteros ms la codificacin de enteros del carcter correspondiente de la clave de cifrado: 05 19 20 05 00 05 16 18 21 05 02 01 ============= 21 10 14 10 02 06 19 00 21 14 00 20 16 18 21 05 02 01 ============= 08 18 15 19 02 21 05 24 21 15 00 04 16 18 21 05 02 01 ============= 21 15 15 20 02 05 05 13 15 16 18 21 ======= 21 04 09

5. :

Reemplazamos cada codificacin de enteros del resultado del paso 4 por su equivalente en caracteres: U J N J B F H R O S B U U O O T B E U D I

El procedimiento de descifrado para este ejemplo es directo, siempre y cuando se tenga la clave. En este caso, pareciera que no sera tan difcil para un posible infiltrado determinar la clave sin ningn conocimiento previo, teniendo el texto plano y el texto cifrado. Aunque, es obvio que existen esquemas mucho ms sofisticados. Ninguna de las tcnicas de sustitucin y permutacin es particularmente segura en s misma, pero los algoritmos que combinan a las dos pueden proporcionar una alto grado de seguridad. Uno de estos algoritmos es el DES (Estndar de cifrado de datos) que usa clave de 64 bits. A travs de los aos muchas personas han sugerido que probablemente el DES no sea tan seguro para ciertas aplicaciones. Alternativamente, ha aparecido otros algoritmos que han ampliado el tamao de la clave, y/o usan dos claves (una para encriptar y otra para desencriptar) como el RSA.

CODIGOS CICLICOS EN LA TRANSFERENCIA DE DATOS Una vez definida la conexin fsica para poder transferir informacin entre los dispositivos o sistemas debe existir un formato para los datos y una estrategia de sincronizacin de como se enva y recepcionan los mensajes, incluyendo la deteccin y correccin de los errores. En un enlace de datos se presentan bloques que cumplen diferentes funciones.

DTE

DCE

RED/CANAL

DCE

DTE

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 18 de 20

DTE: EquipoTerminal de Datos DCE: Equipo de Comunicacin de Datos La trasferencia ordenada de informacin en un enlace de comunicacin se logra estableciendo una conexin entre los DTE, identificando el emisor y el receptor, asegurando que todos los mensajes se transfieran correctamente sin errores, controlando toda la transferencia de informacin. Los equipos (telfono, transmisor, modem ), las conexiones, los cables, repetidoras, etc., constituyen el soporte fsico que permiten el enlace de datos. Un elemento bsico a considerar es la estructura del mensaje, constituyendo una unidad de informacin denominada Cuadro, Bloque, Trama o Datagran. En general tiene la estructura siguiente

Delimitador Control

Informacin

Verificador de errores

Delimitador

Teniendo en cuenta que los equipos y el canal esta expuestos a ruidos internos y externos que pueden alterar la informacin que se transmite, resulta de fundamental importancia detectar y corregir errores. Hay varias formas de verificar los errores que se producen en la trama durante una transmisin. Cdigos Cclicos Resulta de inters la utilizacin de cdigos cclicos, que son aquellos que al realizar una rotacin cclica de una palabra se produce otra palabra que pertenece al mismo cdigo. La ventaja de emplear cdigos cclicos es que se puede implementar fcilmente su generacin a partir de del empleo de registros de desplazamientos con realimentacin Chequeo de Redundancia Longitudinal (LRC) Es un cdigo detector de error en un bit. Utilizado en la adquisicin de datos y control en la industria en la comunicacin entre dispositivos y con un PC.. Tomando como ejemplo una trama con informacin en ASCII: 3A 30 31 30 38 30 30 30 30 36 31 36 32 33 34
LRC

0D 0A

DATOS

Donde 3A es : / 0D es CR / 0A es LF ( Identifican el comienzo y final de la Trama) El resto es un binario equivalente: 01 08 00 00 61 62 El clculo del LRC consiste en realizar la suma hexadecimal de los datos y calcular el complemento a 2.

01 + 08 + 00 + 00 + 61 + 62 = CC = 0011 0011 +1 0011 0100 en hexadecimal: 33 34

Luego, LRC = 33 34 Chequeo de Redundancia Cclica (CRC) Es un cdigo detector de error en un bit. A cada bloque de datos se le agrega una cantidad de bits redundantes. Utilizado en la verificacin de datos grabados en disquetes y almacenamiento en memoria RAM La trama de los datos es asociada a un polinomio de datos D(X)de grado n - 1 (Cantidad de bits menos uno). Los coeficientes se corresponden a los valores binarios de la trama. A cada posicin de bit le corresponde un termino del polinomio Para el ejemplo 01 08 00 00 61 62 corresponde una estructura binaria de 6 bytes (48 bits), es decir 48 1 = 47 El grado del polinomio asociado ser de X^47: 0000 0001 0000 1000 0000 0000 0000 0000 0110 0001 0100 0010

D(X) = X^40 + X^35 + X^14 + X^13 + X^8 + X^6 + X^1

Los bits de redundancia se obtienen mediante un polinomio generador G(X). El polinomio asociado mas la redundancia debe ser divisible por el polinomio G(X), es decir resto nulo. UTN - FRM Arquitectura de las Computadoras I - Unidad 1 Pgina 19 de 20

Los polinomios generadores G(X) estn normalizados internacionalmente.

CRC-8 = X^8 + X^5 + X^4 + 1 CRC-12 = X^12 + X^11 + X^3 + X^2 + X^1 + 11 CRC-16 = X^16 + X^15 + X^2 + 1

(Redundancia de 8 bits) (Redundancia de 16 bits) (Redundancia de 16 bits)

Si se emplea el CRC-8, el procedimiento consiste en elevar a potencia de 8 el bloque de datos (desplazando a la izquierda 8 lugares). Luego se divide por X^8 + X^5 + X^4 + 1. La parte entera del cociente se elimina y resto en 8 bit se agrega al final del mensaje como CRC No se desarrolla el fundamento y procedimiento matemtico del mtodo. Cabe aclarar que se pueden implementar por hardware mediante registros de desplazamiento o por software. En general se realiza por hardware para reducir el tiempo de clculo.

UTN - FRM Arquitectura de las Computadoras I - Unidad 1

Pgina 20 de 20