NUMEROS CON SIGNO CODIGOS DETECTORES Y CORRECTORES DE ERROR

Sistemas Digitales

Representacin de Nmeros con Signo:

El signo de los nmeros almacenados bajo los sistemas digitales se especifica mediante un dgito llamado bit de signo, que por lo general se coloca en la posicin extrema izquierda de los dgitos del nmero. Los nmeros positivos se indican con un digito de signo igual a cero, y los negativos, con un digito de signo distinto de cero (para el caso binario 1). Nmeros con Magnitud y Signo: El mtodo ms sencillo es representar los nmeros con signo es el de magnitud y signo. Sin embargo, el empleo de este mtodo requiere circuitos aritmticos y algoritmos con un costo mayor en trminos de componentes y de tiempo de clculo.
Sistemas Digitales
2

Se puede escribir un nmero con signo, en el formato magnitud y signo como sigue: N = (san-1...a0.a-1...a-m)r Donde: s=0 si N es positivo y s=r-1, si N es negativo. Ejemplo: + 13 = 0,1101 + 127 = 0,1111111 + 0 = 0.0000000 -13 = 1,1101 -127 = 1,1111111 -0 = 1,0000000

Un entero en magnitud y signo de n bits est en el rango de: (2n-1-1) a +(2n-1-1), con dos posibles representaciones del cero.
Sistemas Digitales
3

Sistemas Numricos Complementarios: En estos sistemas, los nmeros positivos se representan de la misma manera que en un sistema de magnitud y signo, mientras que los nmeros negativos se representan como el complemento del numero positivo correspondiente. 1. Complemento a la Base: El complemento a una base [N]r de un nmero (N)r dado, se define como: [N]r = rn - (N)r Donde n = # de dgitos de (N)r

El complemento a 2 es un caso especial para nmeros binarios. [N]2 = 2n - (N)2

Sistemas Digitales
4

Este es el formato ms comn de uso para nmeros con signo en los sistemas digitales.

Ejemplo
(N)2 [N]2 = (01100101)2 = [01100101]2 = 28 - (01100101)2 = (100000000)2 - (01100101)2

= (10011011)2 Regla Practica: Para obtener el complemento a dos de un numero, se complementan los bits y se aade 1 al resultado.
Sistemas Digitales
5

2. Complemento a la Base Disminuida:

El complemento disminuido a una base [N]r-1de un nmero (N)r se define como:

[N]r-1=rn-(N)r-1
Donde: n = # de dgitos de (N)r El complemento a uno es un caso particular del complemento disminuido a una base para los nmeros binarios (r=2) y est dado por: [N]2-1=2n-(N)2-1

Sistemas Digitales

Ejemplo: (N)2 = (01100101)2 [N]2-1 = 28 - (01100101)2 - 1 = (100000000)2 - (01100101)2 - (00000001)2

= (10011011)2 - (00000001)2
= (10011010)2 Regla Practica: Para obtener el complemento a uno de un numero, se complementan todos los bits del numero dado.

Sistemas Digitales

OPERACIONES ARITMETICAS: 1. Suma y Resta de nmeros no decimales: La tabla muestra la suma y resta para nmeros binarios.
Cin o bin
0 0 0

x
0 0 1

y
0 1 0

Cout
0 0 0

S
0 1 1

bout
0 1 0

D
0 1 1

0
1 1 1 1

1
0 0 1 1

1
0 1 0 1

1
0 1 1 1

0
1 0 0 1

0
1 1 0 1

0
1 0 0 1
8

Sistemas Digitales

Cdigos para Deteccin y Correccin de Errores: Un error en un dato binario se define como un valor incorrecto en uno o ms bits, los errores pueden deberse a fallas de hardware, interferencia externa (ruido) u otros eventos no deseados. Si I y J son palabras de informacin binaria de n bits. El peso de I, W(I), se define como el nmero de bits de I iguales a 1. La distancia entre I y J, o d(I,J), es igual al nmero de posiciones de bit en que difieren I y J. Ejemplo determinar los pesos y la distancia de: I=01101100, J=11000100 W(I)=4, W(J)=3 d(I,J)=3
Sistemas Digitales
9

Propiedades generales de los cdigos de deteccin y correccin de errores Si la distancia entre dos palabras de cdigo de un cdigo C es mayor o igual que dmin. Las propiedades de deteccin y correccin de errores de un cdigo quedan determinadas en parte por su distancia mnima. En general, un cdigo permite corregir t errores y detectar s errores adicionales si y slo si se cumple la siguiente desigualdad: dmin 2t+s+1

Sistemas Digitales

10

PALABRA DE ERROR

PALABRA DE CDIGO VLIDA

dmin=2

dmin=3

dmin=4

Sistemas Digitales

11

Cubos - n y Distancia Una cadena de n bits puede visualizarse geomtricamente como un vrtice de un objeto llamado cubo n, en la figura se muestra cubos n para n=1,2,3,4. Un cubo n tiene 2n vrtices, cada uno de los cuales est rotulado con una cadena de n bits. Las aristas se dibujan entre vrtices adyacentes. Para valores razonables de n, los cubos n facilitan la visualizacin de ciertos cdigos y de los problemas de minimizacin lgica. Los cubos proporcionan una interpretacin geomtrica para el concepto de distancia llamada la distancia de Hamming. El concepto de distancia es fundamental en el diseo y comprensin de los cdigos detectores de error.

Sistemas Digitales

12

110 0 1 10 11 010

111

011 100 101

00 1110 0110 0111 1010 0010 0011 0101 0100 0000 0001 1000 1001 1100

01 1111 1011

000

001

0110

0111

0010 0011 1101 1110 1011 1010 1100 0100 1001 1101 0101 1111

1000

0000

0001

Sistemas Digitales

13

Cdigos de Hamming: En 1950, Richard Hamming public la descripcin de una clase de cdigos para correccin de errores que han tenido amplio uso. Se pueden ver como una extensin de los cdigos de paridad simple, en el sentido de que se utilizan varios bits de paridad o bits de verificacin. Cada bit de verificacin se define sobre un subconjunto de los bits de informacin de una palabra. Los subconjuntos se traslapan de modo que cada bit de informacin est en al menos dos subconjuntos.

Sistemas Digitales

14

Para datos de 4 bits, es decir X3X5X6X7

se generan los bits de paridad: P1P2P4, donde:

P1: Se selecciona de modo que se establezca la paridad par sobre los bits: 3,5,7. P2: Se selecciona de modo que se establezca la paridad par sobre los bits: 3,6,7. P4: Se selecciona de modo que se establezca la paridad par sobre los bits: 5,6,7.
Ejemplo: Hallar el caracter codificado de acuerdo a Hamming que corresponde al caracter de informacin: X3X5X6X7 = 1010
Sistemas Digitales
15

Luego la cadena Hamming queda: P1P2X3P4X5X6X7 = 1011010 El proceso de correccin en el extremo receptor es muy conveniente, puesto que se debe suponer que slo un bit est equivocado. La localizacin de este bit se logra comprobando la paridad impar en las mismas combinaciones de bits, para las cuales se estableci la paridad par, como sigue:
Sistemas Digitales
16

Donde, si por ejemplo C1 = 1 debe haber un error en uno de los cuatro bits 1,3,5,7 y as sucesivamente. El bit errneo se puede determinar de la siguiente manera:
C4 Paridad impar sobre 4,5,6,7 0 0 0 0 1 1 1 1

C2
C1

Paridad impar sobre 2,3,6,7

Paridad impar sobre 1,3,5,7 Bit errneo

0
0 X

0
1 1

1
0 2

1
1 3

0
0 4

0
1 5

1
0 6

1
1 7
17

Sistemas Digitales

Para palabras de datos de 8 bits, se incluyen 4 bits de paridad, de modo que se arreglan 12 bits de la siguiente manera: P1P2X3P4X5X6X7P8X9X10X11X12

Los bits de paridad se obtienen:

Sistemas Digitales

18

La paridad se verifica con la misma combinacin de bits, incluyendo el bit de paridad. Estos bits se evalan de la siguiente manera:

Un resultado C8C4C2C1=0000 indica que no ha ocurrido ningn error.

19

Sistemas Digitales

El bit errneo se determina de la tabla:

C8
C4 C2 C1 BIT ERRNEO

0
0 0 0

0
0 0 1

0
0 1 0

0
0 1 1

0
1 0 0

0
1 0 1

0
1 1 0

0
1 1 1

1
0 0 0

1
0 0 1

1
0 1 0

1
0 1 1

1
1 0 0

1
1 0 1

1
1 1 0

1
1 1 1

10 11 12 -

Sistemas Digitales

20

En el mercado se pueden conseguir C.I. que se valen de un Cdigo Hamming modificado para generar y verificar bits de paridad de un esquema de correccin de un solo error y deteccin de errores dobles. Uno que emplea una palabra de datos de 8 bits y una palabra de verificacin de 5 bits es el C.I. 74637. Se dispone de otros C.I. para palabras de datos de 16, 32 bits.

Sistemas Digitales

21

CODIGOS DE BLOQUES Y CONVOLUCIONALES: En los cdigos de bloques, un bloque de k dgitos de datos se codifica mediante una palabra de cdigo de n dgitos ( n > k). Para cada sucesin de dgitos de datos, existe una palabra de cdigo distinta de n dgitos. En los cdigos convolucionales, la sucesin de n dgitos codificada depende no solo de los k dgitos de datos sino tambin de los anteriores N-1 dgitos de datos (N > 1). Por lo tanto, la sucesin codificada para un cierto grupo de k dgitos no es nica sino que depende de los N-1 dgitos de datos anteriores.

Sistemas Digitales

22

Si k dgitos de datos se transmiten mediante una palabra de cdigo de n dgitos, el numero de dgitos de comprobacin es m = n k. La eficiencia del cdigo (ndice del cdigo) es k/n. Este cdigo se conoce como (n, k).
Para encontrar la relacin entre n y k, se observa que 2n vrtices o palabras se encuentran disponibles para 2k palabras de datos, y 2n - 2k son vrtices redundantes.

Sistemas Digitales

23

Algunos ejemplos de cdigos de correccin de errores:

n 3 4 5 6 7 15 31 10 15 10 15 23 k 1 1 2 3 4 11 26 4 8 2 5 12 Cdigo (3, 1) (4, 1) (5, 2) (6, 3) (7, 4) (15, 11) (31, 26) (10, 4) (15, 8) (10, 2) (15, 5) (23, 12) Eficiencia 0,33 0,25 0,4 0,5 0,57 0,73 0,838 0,4 0,533 0,2 0,33 0,52

Correccin de un solo error t=1

dmin = 3
t = 3, dmin = 7 Correccin de doble error t = 2, dmin = 5
24

Sistemas Digitales

Cdigos Lineales de Bloque: Una palabra de cdigo consta de n dgitos, y una palabra de datos consta de k dgitos. Luego: c = (c1, c2, . . . , cn) d = (d1, d2, . . , dk) En general en los cdigos lineales de bloque, los n dgitos de c se forman mediante combinaciones lineales de k dgitos de datos. Un caso especial en el cual c1 = d1, c2 = d2, . . , ck = dk Y los dgitos restantes de ck+1 a cn son combinaciones lineales de se conoce como cdigo d1, d2, . . . . ., dk

sistemtico.

Luego en estos cdigos, los k primeros dgitos de la palabra de cdigo son los dgitos de datos, y los ltimos m = n-k dgitos son los dgitos de comprobacin de paridad.

Sistemas Digitales

25

Luego: c1 = d1 c2 = d2 . . . ck = dk ck+1 = h11d1+h12d2+. . . +h1kdk ck+2 = h21d1+h22d2+ . . . +h2kdk . . . cn = hm1d1+hm2d2+ . . . +hmkdk O equivalentemente: c = d.G, donde la matriz G de orden kxn se llama Matriz Generadora.
Sistemas Digitales
26

La matriz G se puede separar en una matriz identidad de orden k, y una matriz P de orden kxm, llamada matriz de paridad. La palabra de cdigo se puede expresar por: c = dG = d[Ik P] = [d dP] = [d cp] Siendo cp la matriz fila de m dgitos de comprobacin de paridad: cp = dP
Sistemas Digitales
27

Decodificacin: En el proceso de decodificacin, se define la matriz H llamada matriz de comprobacin de paridad. Luego si:

Entonces:

Si c es una palabra de cdigo, se verifica: cHT = O Todas las palabras de cdigo deben satisfacer la ecuacin anterior. Si se recibe la palabra r, y debido a errores causados por el ruido del canal, r en general difiere de la palabra de cdigo c que se transmiti, siendo:

Sistemas Digitales

28

Donde e es un vector de error de n elementos. Si el mensaje llega sin errores, entonces: rHT = O Pero si el mensaje llega con error, se define:

Donde la matriz fila s se llama sndrome, la cual ser un vector nulo si el dato recibido no presenta error.

Sistemas Digitales

29

SUMAS DE CONTROL (CHECKSUM): Otro mtodo de deteccin consiste en generar todas las palabras de datos en un bloque, por ejemplo, sumando sus valores ASCII, luego dividiendo entre algn numero fijo. El residuo que resulte de esta divisin se transmite al final del bloque. El receptor lleva a cabo la misma divisin y debe obtener el mismo residuo. El protocolo XMODEM usa este mtodo. COMPROBACION DE REDUNDANCIA CICLICA: Los cdigos CRC (Cyclic Redundant-Checksum) se utilizan en muchos sistemas digitales complejos, como en el CD. Este tipo de cdigo de correccin utiliza una forma de realimentacin en el que el estado de cada bit de mensaje depende del estado de los bits previos en el bloque.
Sistemas Digitales
30

Los cdigos CRC son particularmente buenos para detectar rfagas de errores, en los que varios bits consecutivos faltan o son incorrectos. Los cdigos CRC se generan al calcular un polinomio a partir de los bits de mensaje. Se considera al mensaje completo como un polinomio y se divide entre un polinomio fijo llamado polinomio generador y se obtiene un cociente y un residuo. El residuo se anexa al mensaje y se transmite como un carcter de comprobacin de bloque (Block Check Character, BCC). En el receptor se repite el calculo y se comprueba el residuo. Pueden implantarse en Hardware y Software. Compresin de Datos y Criptografa.

Sistemas Digitales

31