Upload
raul-munoz-ventura
View
214
Download
0
Embed Size (px)
DESCRIPTION
KUH
Citation preview
Algunos Códigos Usados en Sistemas Digitales
Código BCD (Binary Code Decimal):
Cada cifra decimal se codifica según una serie de bits binarios ¿Cuantos?,
como existen diez cifras del 0 al 9 necesitamos 4 bits por cifra. Ahora resultaque con 4 bits podríamos codificar hasta 16 cifras, luego vemos que hay 6
combinaciones (de 1010 a 1111) que nunca se utilizan en el código BCD; de
ahí que este código sea menos compacto que el binario puro.
Comunicaciones Digitales
1
ahí que este código sea menos compacto que el binario puro.
Algunos ejemplos:010001001101
010100110001
531)135(
10==
00100101010011101001100000110101
9835)5389( 10 ==
10011000010000000110001000000001
6201)1026( 10 ==
Clase N°3
Código BCD
Decimal BCD Decimal BCD Decimal BCD Decimal BCD
00 0000 0000 10 0001 0000 20 0010 0000 30 0011 0000
01 0000 0001 11 0001 0001 21 0010 0001 31 0011 0001
02 0000 0010 12 0001 0010 22 0010 0010 32 0011 0010
03 0000 0011 13 0001 0011 23 0010 0011 33 0011 0011
Comunicaciones Digitales
2
04 0000 0100 14 0001 0100 24 0010 0100 34 0011 0100
05 0000 0101 15 0001 0101 25 0010 0101 35 0011 0101
06 0000 0110 16 0001 0110 26 0010 0110 36 0011 0110
07 0000 0111 17 0001 0111 27 0010 0111 37 0011 0111
08 0000 1000 18 0001 1000 28 0010 1000 37 0011 1000
09 0000 1001 19 0001 1001 29 0010 1001 39 0011 1001
Clase N°3
Código BCD
Exprese en BCD las siguientes cantidades:
1. 23567
2. 1267
3. 87643
4. 102349
Comunicaciones Digitales
3
5. 23578
6. 7654
7. 90876
8. 8070
9. 1245
10. 367890
Clase N°3
Código Gray
El código Gray es otro tipo de código basado en un sistema binario.
Su principal característica es que 2 números sucesivos, cualesquiera,solo varían en 1bit.
Un Código Gray de 2 bits sería: de 4 bits :
00 0000
01 0001
11 0011
10 0010
Comunicaciones Digitales
4
10 0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000Clase N°3
Código Gray
Una forma sencilla de construir un código Gray de “n” bits es tomarun código Gray de “n-1” bits y agregarle un “0” por la izquierda, luegopara completar el código se traza una línea imaginaria (línea o eje desimetría) y se agrega un “1” y se copian los bits de código de “n-1”bits como espejo:
0 00
Comunicaciones Digitales
5
0 00
0 01
0 11
0 10
1 10
1 11
1 01
1 00
Clase N°3
Código Graydecimal hexadecimal binario Gray 2 bits Gray de 3 bits Gray de 4 bits
0 0 0000 00 000 0000
1 1 0001 01 001 0001
2 2 0010 11 011 0011
3 3 0011 10 010 0010
4 4 0100 110 0110
5 5 0101 111 0111
6 6 0110 101 0101
Comunicaciones Digitales
6
7 7 0111 100 0100
8 8 1000 1100
9 9 1001 1101
10 A 1010 1111
11 B 1011 1110
12 C 1100 1010
13 D 1101 1011
14 E 1110 1001
15 F 1111 1000
Clase N°3
Conversión Binario a Gray
Sea un Número Binario :
El mismo número en Código Gray:
Donde : ,
0121... bbbbb nnn −−
0121..... ggggg nnn −−
11 −−⊕= iii bbg ni <<0
Comunicaciones Digitales
7
Y
Es la suma módulo dos
11 −− iii ni <<0
nn bg =
""⊕
011
101
110
000
=⊕
=⊕
=⊕
=⊕
Clase N°3
Conversión Binario a Gray
• Ejemplos: convertir (10111001) en binario a Gray:
10011101
⊕⊕⊕⊕⊕⊕⊕
10100111
Comunicaciones Digitales
8
• Otros ejemplos:
• Comprobar:
0101⊕⊕⊕
1111
gray
gray
gray
)011011111110()011101010100(
)010101()011001(
)100100()111000(
2
2
2
=
=
=
Clase N°3
Convertir los siguientes números binarios en Código Gray:
1. 111000111000
2. 1010101010
3. 11111111
Conversión Binario a Gray
Comunicaciones Digitales
9
4. 1000011
5. 100100100100
6. 110110110110
7. 1111100001
Clase N°3
Conversión Gray a Binario
Sea un número Gray:
El mismo número Binario:
0121 ... ggggg nnn −−
0121 ... bbbbb nnn −−
Comunicaciones Digitales
10
El procedimiento se comienza por el bit más significativo, donde
si el número de unos (“1”) que preceden a es par,
y si el número de unos (“1”) es impar, para
y
,ii gb =
ig
ii gb = ni <<0
nn gb =
Clase N°3
1,21º11101
0,11º1110
1,11º001
1711
444
555
666
777
==⇒==
==⇒==
==⇒==
==⇒==
gbpardeng
gbimpardeng
gbimpardeng
gbng
Conversión Gray a Binario
Ejemplo: convertir (10111001) en Gray a Binario:
Comunicaciones Digitales
11
1,41º111011100
0,41º00101110
0,41º0010111
0,31º111011
1,21º11101
000
111
222
333
444
==⇒==
==⇒==
==⇒==
==⇒==
==⇒==
gbpardeng
gbpardeng
gbpardeng
gbimpardeng
gbpardeng
Entonces: 2
)11010001()10111001( =gray
Clase N°3
Conversión Gray a Binario
Convertir los siguientes números en Código Gray a su equivalente en Binario:
1. 111000111000
2. 1010101010
Comunicaciones Digitales
12
3. 11111111
4. 1000011
5. 100100100100
6. 110110110110
7. 1111100001
Clase N°3
Asumiremos que se trata de transmitir información que ha sidodigitalizada en forma de una secuencia de ceros y unos. Esto no es
difícil de hacer si la información es numérica, porque podemosrepresentar los números en notación binaria, usando 2 como base delsistema de numeración en vez del sistema decimal habitual construido
sobre el 10, lo que requiere sólo los dígitos 0 y 1. También es posible
traducir caracteres de texto, imágenes, música, etc, en listas de ceros
Detección de Errores y Codificación
traducir caracteres de texto, imágenes, música, etc, en listas de cerosy unos.
Llamaremos palabras a las listas de unos y ceros de longitud k ,que podremos utilizar en un mensaje, disponemos de un conjuntode palabras o diccionario P que, en general, será una familia delistas de longitud k formadas por ceros y unos.
Comunicaciones Digitales
Clase N°3 14
Detección de Errores y Codificación
En un esquema general de transmisión de la información, tendríamos los siguientes elementos:
• Un emisor, que desea mandar un cierto mensaje.• Un codificador, que transformaría el mensaje original de manera que pudiera ser transmitido • Un canal físico por el que se transmita el mensaje codificado. • Un decodificador, que recibe el mensaje y realiza el proceso de detección • Un decodificador, que recibe el mensaje y realiza el proceso de detección de los errores.• Por último, el receptor final del mensaje.
27/03/2012 15clase N°3
En la memoria de los computadores PC se agrega un bit de paridad por
cada byte (8bits) de datos, de esta forma al leer la memoria se compara laparidad almacenada con la paridad calculada de los datos leídos, si estas
son distintas, significa que existe un mal funcionamiento de la memoria, estoes una verdadera catástrofe para el sistemas operativo y termina con el
computador detenido y el mensaje “Parity Error System Halted “ enpantalla.
Detección de Errores y Codificación
pantalla.
En un proceso de codificación general ocurre algo parecido. Una vez
escrito el mensaje en los términos adecuados, el codificador transformarácada una de las palabras de longitud k del mensaje en otra lista de ceros y
unos, que tendrá en general una longitud distinta, n > k.
La información introducida en los n — k dígitos que se agregan en el
proceso de codificación crea la redundancia que nos permitirá detectar ycorregir errores.
Comunicaciones Digitales
Clase N°3 16
¿Cuál es la utilidad de todo esto? Cuando queramos transmitir p la
codificaremos y enviaremos en su lugar c. ¿Por qué? Porque si se
producen errores en la transmisión sabremos corregirlos, al menos enalgunos casos, a partir de la redundancia que el código introduce. No
seríamos capaces de eliminar errores, ni siquiera de enterarnos de que un
error se produjo, si enviáramos la palabra p sin procesar.
Detección de Errores y Codificación
Subrayemos que en todo esto el código cumple una función auxiliar que
consiste en ayudarnos a transmitir de forma fiel las palabras del
diccionario original P, que son los objetos que realmente nos interesan.
Por lo tanto, cada vez que el receptor de un mensaje tenga una palabra cdel código deseará saber cuál es la palabra p de la que proviene. Hay un
requisito obvio que debe satisfacer entonces la función de codificación: no
puede enviar dos palabras diferentes de V a la misma palabra de C. Siesto ocurriera no podríamos decodificar. Por lo tanto, la función f tiene
que ser inyectiva.
Comunicaciones Digitales
Clase N°3 17
El segundo requisito que impondremos es que toda palabra del código C
provenga de una palabra de P a través de la función de codificación, cosaque permitirá determinar p para cualquier c. Este segundo requisito implica
que la función f debe ser sobreyectiva. Estas dos condiciones aseguran que
la codificación puede deshacerse para cualquier palabra c perteneciente a C.Naturalmente, esta decodificación de palabras código es equivalente a
invertir la función f para obtener:
Detección de Errores y Codificación
Por lo tanto, si se recibe c debemos interpretar que se está enviando la
palabra p = (c) del diccionario P.
El diseño de buenos códigos depende de una correcta elección de f lo que
incluye fijar los valores de k y n, en el marco del las listas de ceros y unostendremos una estructura geométrica de la que asirnos, y la posibilidad de
operar algebraicamente con las palabras de nuestro diccionario.
Comunicaciones Digitales
Clase N°3 18
Comencemos con un sencillo ejemplo: supongamos que tenemos tres
secuencias de ceros y unos de longitud 5,
1 0 0 0 1 1 1 0 0 1 0 0 1 1 1
Detección de Errores y Codificación
Cualquier persona diría que las dos primeras secuencias se parecen entre
sí, que están mas "cerca" entre ellas que con respecto a la tercera. Si
aplicamos como criterio de comparación el número de posiciones en que lassecuencias difieren, entonces, las dos primeras sólo difieren en la segunda
posición, mientras que, en relación a la tercera, difieren en más posiciones.
Lo que vamos a hacer es nombrar la forma de medir cuan distintas son dossecuencias como "distancia “.
Comunicaciones Digitales
Clase N°3 19
Códigos y la corrección de errores
• La función principal de las técnicas de control de errores es introducirredundancia controlada permitiendo que los mensajes transmitidos que
hayan sido corrompidos sean corregidos antes de ser procesados. Con
esta redundancia controlada sólo un subconjunto de todos los posiblesmensajes (secuencias de bits) contiene mensajes válidos. Esto quiere decirque si formamos secuencias de 7 bits, podremos recibir 27=128 secuencias
distintas, pero los posibles mensajes transmitidos no serán 128 sino unsubconjunto de ellos, luego si no hemos recibido una secuencia de 7 bitssubconjunto de ellos, luego si no hemos recibido una secuencia de 7 bitsque coincida con uno de los posibles mensajes transmitidos, habremos
recibido una secuencia con errores.
• Este subconjunto de posibles mensajes transmitidos se llama código y a
los mensajes válidos que lo forman los llamamos codewords o
codevectors.
• Pues bien, un buen código es aquel en el que los codewords están tanseparados que la probabilidad de que los errores conviertan al codeworddeseado en otro codeword es muy pequeña.
Comunicaciones Digitales
Clase N°3 20
Códigos y la corrección de errores
• Según esto, la detección de errores se limita a responder a la pregunta :"¿Es el mensaje recibido un codeword o no ?" Si es un codeword, uno
supone que no hay errores, de esta manera la probabilidad de no detectar
un error es la probabilidad de que los posibles errores conviertan uncodeword en otro.
• Cuando se detecta un error existen dos métodos para corregirlo :• Cuando se detecta un error existen dos métodos para corregirlo :
• 1º.- El receptor rechaza el mensaje recibido y solicita al transmisor que
retransmita el mensaje.
• 2º.- El receptor corrige el error al encontrar el codeword válido más próximo
al mensaje recibido. Este procedimiento se llama forward error correction
(FEC).
Comunicaciones Digitales
Clase N°3 21
Códigos correctores de errorCuando se transmite una información binaria desde un emisor a unreceptor a través de un medio susceptible a perturbaciones o ruido, aparece
el problema que algunos bits de la palabra original pueden modificarse yden lugar a una nueva combinación que será una información errónea
Comunicaciones Digitales
Clase N°3 22
ejemplo
• Los códigos de distancia mínima 2 pueden ser de peso constante, por ejemplo 2 unos de entre 5 bits, o bien de paridad constante
Comunicaciones Digitales
Clase N°3 23
Limitaciones de los códigos detectores de errores
En las figuras anteriores se observa la transmisión de una combinación binaria a
la que se le ha añadido un bit de paridad par (BPP).Si el código original es el
binario de cuatro bits, el nuevo código formado en el sistema serpa de 5 bits y la
recepción de una palabra con un número de bits impar indica a recetor que es
errónea.
Para que el sistema receptor detecte el bit erróneo hay que analizar la palabra
recibida y ver cual es la palabra que pertenece al código original y que se ha
transmitido. El problema es que hay tantas combinaciones posibles correctas
Comunicaciones Digitales
Clase N°3 25
transmitido. El problema es que hay tantas combinaciones posibles correctas
como bits tiene la palabra recibida
Esta tabla pone de manifiesto
esto, al comprobar que con
códigos de distancia mínima 2
y tomando todas las
combinaciones posibles es
imposible detectar el bit
erróneo.
Limitaciones de los códigos detectores de errores
Comunicaciones Digitales
Clase N°3 26
Para corregir un error binario es suficiente con la inversión lógica del valor recibido
por la línea de datos. En la figura B no hay suficiente información para saber cual
de los hilos ha sufrido un cambio de valor, por este motivo, el segundo envío de la
información se efectúa codificando a través de bits de paridad para que la línea de
datos sea única.
Distancia Hamming y distancia de código
Sean los mensajes secuencias binarias de n bits, esto hace que los
mensajes o vectores de n bits formen un conjunto de 2n posibles.
La distancia Hamming o distancia entre dos vectores es el número deposiciones de bits en los cuales dichos vectores toman valores diferentes.
Por ejemplo, sean 2 vectores de 4 bits :
c1 = 0 1 0 1 y c2 = 1 1 0 0
la distancia entre c1 y c2 es 2.la distancia entre c1 y c2 es 2.
Supongamos que de entre los 2n posibles vectores elegimos un subgrupo
que constituyen nuestro código. Pues la distancia del código será la mínimadistancia Hamming entre todas las posibles combinaciones de codewords.
Se demuestra que si la distancia de un código es d, entonces podemos
detectar y corregir los errores que afecten a t bits de cada codeword,
siendo :
Así si la distancia de un código es 5 entonces podemosdetectar y corregir errores en 2 bits.
Comunicaciones Digitales
Clase N°3 27