Story Transcript
Sistemas Digitales
Códigos
Códigos Prof. Mario Medina mariomedina@udec.cl
Conceptos básicos Definiciones Tipos de códigos numéricos
Conceptos generales
Código: conjunto de símbolos usados para representar letras, números, palabras, conceptos u otros símbolos.
Códigos ponderados Códigos autocomplementados Códigos de largo variable Códigos detectores y correctores de errores
Códigos alfanuméricos
Conceptos generales
Usos comunes de codificación
Ejemplos: código morse, emoticones, etc.
En un número codificado, las cifras representan algo, y sólo podremos saber su significado si conocemos el código que las generó
Transmisión de información fácil y rápida Compresión para optimizar el espacio de almacenamiento Expresar adecuadamente los datos para su procesamiento Detección y corrección de errores
Códigos binarios
Definiciones
Difícil comprensión para el humano, pero lenguaje natural en circuitos Representación fácil y eficiente en
Circuitos eléctricos, mecánicos o hidráulicos Medios de almacenamiento ópticos y magnéticos
©2013 Mario Medina C.
Capacidad de un código
Número de valores distintos en el código
Depende del número de dígitos en el código Código de 3 bits tiene capacidad 23 = 8
Utilización de un código
Número de valores distintos definidos como válidos en el código Utilización del código puede ser menor que la capacidad
Existencia de palabras no válidas
1
Sistemas Digitales
Definiciones
Distancia entre 2 palabras de un código
Número de símbolos de una palabra que deben modificarse para obtener la otra
Tipos de códigos
Código adyacente
Todas las palabras tienen distancia 1 con sus vecinos
Códigos ponderados Palabras del código son generadas por un polinomio cuyos dígitos tienen una ponderación establecida Binary Coded Decimal (BCD)
Códigos BCD
Códigos autocomplementados Códigos adyacentes Código Gray Códigos de largo variable Códigos detectores y/o correctores de errores
Distancia mínima de un código
Mínima distancia entre 2 palabras válidas cualesquiera de un código
Códigos ponderados
Códigos ponderados
BCD 8421 (Similar a binario puro)
Secuencias 1010 a 1111 no son válidas Usa 4 bits para representar un dígito decimal
Códigos ponderados más usados Cada cifra decimal se representa por 4 bits Capacidad del código: 16 Utilización del código: 5/8
Existen diferentes tipos de BCD, dependiendo de las ponderaciones de cada bit
Códigos ponderados BCD
Existen otros códigos BCD
BCD 2421, BCD 1224, BCD 7421, BCD 6321, etc. En algunos, un decimal no tiene representación única
Se prefiere 1100: dígitos 0 a 4 comienzan con 0
Es necesario definir normas particulares
BCD 8421 asegura representación única Códigos BCD son válidos para números enteros y fraccionarios
Permite operaciones aritméticas de gran tamaño
©2013 Mario Medina C.
BCD 8421
Dec
BCD 8421
0
0000
5
0101
1
0001
6
0110
2
0010
7
0111
3
0011
8
1000
4
0100
9
1001
Ejemplo de códigos BCD
Representación del número 25
Ej: 610 en BCD 2421 puede ser 1100 o 0110
Dec
En binario
En BCD 7421
11001 0010 0101
En BCD 4321
0010 1001
Se prefiere que dígitos 0 a 4 empiecen con 0
Decimal
BCD 7421
BCD 4321
0
0000
0000
1
0001
0001
2
0010
0010
3
0011
0100 ó 0011
4
0100
0101 ó 1000
5
0101
1001 ó 0110
6
0110
1010 ó 0111
7
1000
1011 ó 1100
8
1001
1101
9
1010
1110
2
Sistemas Digitales
Códigos autocomplementados
Códigos en que el complemento disminuido de una palabra también es una palabra válida
En binario, el complemento a 1 se obtiene invirtiendo cada uno de los bits originales
Especialmente útiles para realizar restas
Códigos autocomplementados
Simplifican circuitos de complementación
Más utilizados Exceso 3: código BCD 8421 + 3 BCD 2421 ó código Aiken
Códigos autocomplementados
Ejercicio:
Representar el numero 90710 en BCD exceso-3 y usar complemento a 1 para encontrar el complemento a la base disminuida del número (complemento a 9). 90710
Llamados también códigos cíclicos Números sucesivos difieren sólo en 1 bit Especialmente útiles en:
Conversión análoga-digital Control de máquinas-herramientas
Los más utilizados son
Código Gray Reflejado exceso 3
©2013 Mario Medina C.
BCD 2421
0011
0000
1
0100
0001
2
0101
0010
3
0110
0011
4
0111
0100
5
1000
1011
6
1001
1100
7
1010
1101
8
1011
1110
9
1100
1111
BCD 8421: cambiar de 710 a 810
Cambiar de 01112 a 10002 Qué pasa si los 4 bits no cambian simultáneamente?
complemento a 9 de 90710 es 999-907 = 09210
1100 0011 1010Exc3 09210 en complemento a 9 0011 1100 0101Exc 3
Códigos adyacentes
Exceso 3
0
Transiciones en códigos BCD
Demostrar que el resultado está correcto El
Decimal
0111
7
Válido
1111
15
Inválido
1011
11
Inválido
1001
9
Válido
1000
8
Válido
Códigos adyacentes Decimal 0
Codigo Gray 0000
Reflejado Ex. 3 0010
Código Johnson 00000
1 2 3 4 5 6 7 8 9
0001
0110
00001
0011
0111
00011
0010
0101
00111
0110
0100
01111
0111 0101 0100 1100 1101
1100
11111
1101
11110
1111
11100
1110
11000
1010
10000
3
Sistemas Digitales
Código Gray
Codificador de posición rotatorio
Código adyacente no ponderado Digitos decimales consecutivos difieren en un solo bit Simplifica la transición entre estados
Copiar el Gray de 1 bit dos veces, la segunda en forma invertida Anteponer un 0 a la formación original y un 1 a la parte reflejada
Gray de n bits
Repetir lo anterior con código Gray de n-1 bits
Código Gray y código reflejado exceso 3
Código Gray es adyacente
0 1
Los dos valores posibles son 0 y 1
Gray de 2 bits
Distancia 1 entre dígitos 0 al 9 Distancia 3 entre el 9 y el 0
Código reflejado exceso 3 es adyacente y circular (cíclico)
Con código Gray todas las posiciones son adyacentes
Generación código Gray
Gray de 1 bit
Útil para sistemas físicos con transiciones mecánicas Mucho ruido y elevado consumo de potencia
Generación código Gray
Aplicación común: determinar posición y velocidad de ejes (rotary encoder)
Distancia 1 entre dígitos 0 al 9 Distancia 1 entre 9 y 0 Se obtiene sumando 3 a código Gray
000 001 011 010 110 111 101 100
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Código Gray Código reflejado exceso 3
Conversión binario a Gray A veces, es necesario convertir de código binario a Gray y vice versa Para ello, primero definimos la operación lógica de OR exclusivo (XOR)
©2013 Mario Medina C.
00 01 11 10
También llamado operador de desigualdad 00=0 01=1 10=1 11=0
4
Sistemas Digitales
Conversión binario a Gray
La relación para pasar de binario a Gray es
gi = bi bi+1 g0 = b0 b1 = 0 0 = 0 g1 = b1 b2 = 0 1 = 1 g2 = b2 b3 = 1 1 = 0 g3 = b3 b4 = 1 0 = 1 (último bit b4 es 0)
Represente el número decimal 9876 en
Código BCD 8421 Código BCD 7421 Código BCD 2421 Código Gray Código Exceso-3 Código Reflejado exceso-3
Propiedad prefijo
Regla de conversión: b MSB g MSB b i b i 1 g i
Se copia el bit más significativo Se usa XOR para calcular bits siguientes
Entonces, 11002 es 1010Gray
Ejercicios
Ejemplo: pasar 11002 a Gray
Conversión Gray a binario
Para que un código de largo variable esté completamente definido, debe cumplirse la
Ejemplo: Transformar el dato 1101Gray a binario
b3 = g3=1 b2 = b3 ⊕ g2 = 0 b1 = b2 ⊕ g1 = 0 b0 = b1 ⊕ g0 = 1
Entonces, 1101Gray es 10012
Códigos de largo variable
Códigos anteriores son de largo fijo
Todos los símbolos se representan usando el mismo número de bits
Código Huffman
Asigna largo de representación en función de la frecuencia del símbolo Secuencias más cortas corresponden a símbolos más frecuentes Reduce largo promedio de mensajes
Construcción de un código Huffman
Construir el árbol de decodificación
propiedad prefijo
si a1a2…ak es una palabra válida del código, entonces no puede existir otra palabra válida definida como a1a2…aj, para j < k
©2013 Mario Medina C.
Agregar cada símbolo a una hoja del árbol Identificar los 2 nodos de más baja frecuencia que no poseen predecesores y construir el nodo predecesor
Frecuencia será suma de frecuencias de los dos nodos
Repetir hasta que quede sólo un nodo sin predecesor
5
Sistemas Digitales
Construcción de un código Huffman
Rotular los arcos del grafo
Este código cumple con la propiedad prefijo Largo promedio de un símbolo: 2.25 bits
Ruido aditivo en los medios de transmisión
Puede invertir los bits de datos Bit Error Rate (BER): Tasa de errores en la transmisión
Normalmente del orden de 10-9 Depende de la tasa de transmisión y potencia de la señal
Símbolo Frecuencia
Se genera el siguiente árbol 0
1
(0.6)
(0.4)
0 0 1 C (0.15) A (0.35) B (0.25) 0 D (0.15)
1 (0.25) 1 E (0.1)
Código
A
0,15
010
B
0,30
00
C
0,20
10
D
0,05
1110
E
0,15
011
F
0,05
1111
G
0,10
110
Códigos detectores de errores
Se desea detectar errores y pedir la retransmisión de datos erróneos
Deben existir palabras no válidas en el código
Inversión no deseada de un bit genera palabra no válida
©2013 Mario Medina C.
Frecuencia 0.35 0.25 0.15 0.15 0.10
Ejercicio código Huffman
Frecuencia Código 0.35 00 0.25 01 0.15 10 0.15 110 0.10 111
Códigos detectores de errores
Dada la siguiente frecuencia de símbolos Dato A B C D E
Asignar a cada nodo la secuencia de 0s y 1s correspondientes al camino desde la raíz al nodo en cuestión
Dato A B C D E
Asignar un 0 a uno de los arcos que salen del nodo raíz y un 1 al otro arco Repetir recursivamente hasta haber cubierto todos los nodos
Ejemplo código Huffman
Ejemplo código Huffman
Distancia mínima de un código debe ser mayor que n n: número de errores a detectar Inversión de hasta n bits da palabra no válida
6
Sistemas Digitales
Códigos detectores de errores
Códigos de paridad
Tipos
Códigos de paridad
de códigos detectores
Agregar un bit a la palabra para verificar si número de bits en 1 es par o impar
EMISOR DE INFORMACIÓN b0 Información En ASCII De 7 bits
RECEPTOR DE INFORMACIÓN b0 7 b1
b1
b6
b6
Generador / Detector de paridad
Generador / Detector de paridad
1
Bit de verificación de paridad
/
Bit de paridad
Códigos de peso constante Mantienen un número constante m de bits en 1 en las palabras del código Más usados: códigos pentádicos (5 bits)
Walking code 2 de 5 BCD 63210
Códigos de 7 bits
Duplica la cantidad de palabras del código Igual número de palabras válidas e inválidas Código de paridad asegura una distancia mínima de 2
Qui-binario (10-86420) Bi-quinario (50-43210)
Usado en ábacos romanos y chinos, y en lenguajes Khmer y Wolof
©2013 Mario Medina C.
Transmisor y receptor se ponen de acuerdo
Expresar el binario 1001010 en un código de paridad par
Información En ASCII De 7 bits
1
Códigos de paridad
b7
Agregar un bit a palabras transmitidas para asegurar que el número de 1s sea par o impar
CRC (Cyclic Redundancy Check)
Información en ASCII con paridad constante
También llamados códigos m de n Mantiene un número constante de bits en 1
Códigos de paridad
Puede ser par o impar
Código de paridad
Códigos de peso constante
Paridad: cardinalidad de los 1s en una palabra
1
1001010
Paridad
Dato
Palabras como 01001010 y 10001010 son inválidas en el código
Número de 1s es impar Código sólo detecta número impar de errores
Códigos de peso constante Decimal 0 1 2 3 4
2 de 5 00011
BCD 63210 00110
50-43210 01-00001
10-86420 01-00001
00101
00011
01-00010
10-00001
00110
00101
01-00100
01-00010
01010
01001
01-01000
10-00010
01100
01010
01-10000
01-00100
5
10100 11000 01001 10001 10010
01100
10-00001
10-00100
10001
10-00010
01-01000
10010
10-00100
10-01000
10100
10-01000
01-10000
11000
10-10000
10-10000
6 7 8 9
7
Sistemas Digitales
Cyclic Redundancy Check (CRC)
Número binario de n bits corresponde a un polinomio M(x)
Mensajes M de 12 bits es 110100110111
M(x) =
Se transmite mensaje de (n+r) bits formado por M(x) seguido de R(x)
El cuociente de la división es Q(x) El resto de la división es R(x) Se cumple que M(x)*xr/G(x) = Q(x) ⊕R(X)/G(x)
Ejemplo de CRC
101001 => x5+ x3+1
CRC divide polinomio M(x) de n bits por un polinomio generador G(x) de orden r < n (r bits)
Cyclic Redundancy Check (CRC)
El receptor divide la palabra codificada por el mismo polinomio G(x)
Resto es 0: no hubo errores
Resto es distinto de 0: error en la transmisión
x11+x10+x8+x5+x4+x2+x+1
División mediante restas sin 11010011011100000 110101 préstamo
Polinomio generador G(x) = x5+x4+x2+1 Dividir 11010011011100000 por 110101
Resto de la división R(x) = 10001 Palabra transmitida es 11010011011110001
Ejemplo de CRC
Supongamos que un error de transmisión modifica 3 bits sucesivos
Dato recibido es 11011101011110001 Resto de división por G(x) es distinto de 0: Error!
Supongamos que un error de transmisión modifica 7 bits sucesivos
Dato recibido es 11111100111110001 Resto de división por G(x) es 0: Error no detectado!
©2013 Mario Medina C.
O, no son detectables
Ejemplo de CRC
T(x) = M(x)*xr+R(x)
Completar mensaje con 0s hasta n+r bits Alinear MSB con 1er bit en 1 Realizar XOR entre los bits Repetir hasta obtener el resto de la división Fácil de implementar con desplazamientos y XORs
111011100000 110101 1110100000 110101 11110000 110101 100100 110101 10001
Cyclic Redundancy Check (CRC)
Un CRC de r bits detecta una cadena de error en bits consecutivos de largo menor a r
CRC detecta ráfagas de errores
Elección del polinomio generador es crítica Existen combinaciones de errores no detectables por un polinomio dado Pueden obtenerse del análisis matemático
8
Sistemas Digitales
Cyclic Redundancy Check (CRC)
Códigos correctores de errores
Polinomios usados en CRC se encuentran estandarizados para aplicaciones específicas
CRC-1 (x+1): bit de paridad CRC-5-USB (x5 + x2 + 1): USB token packets CRC-16-CCITT (x16 + x12 + x5 + 1): (Bluetooth) CRC-32 (x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1) (Ethernet, gzip, SATA, MPG)
Códigos correctores de errores
Código corrector de errores de n bits
Se debe cumplir M – 1 = C + D, C≤D
M: distancia mínima del código D: número de errores a detectar C: número de errores a corregir
2
3
4
5
6
0
0
0ó1
0ó1
0, 1 ó 2
0, 1 ó 2
D
0
1
2ó1
3ó2
4, 3 ó 2
5, 4 ó 3
Cada bit de validación verifica paridad de un subconjunto de bits del dato
Estas posiciones están dadas por: Posición 1 (p1): 1, 3, 5, 7, 9, 11, 13, … Posición 2 (p2): 2, 3, 6, 7, 10, 11, 14, 15, … Posición 4 (p4): 4, 5, 6, 7, 12, 13, 14, 15, … Posición 8 (p8): 8, 9, 10, 11, 12, 13, 14, 15, 24, …
Bit de validación se escoge para formar paridad par sobre bits verificados
©2013 Mario Medina C.
di : bits del dato original pi : bits dedundantes
pi en las posiciones que son potencias de 2
Generación de Código Hamming
Código que detecta y corrige un error
1
Código Hamming Transmisión de bloques
Código Hamming
C
Distancia mínima al menos 3
Muy usados para respaldo de información
M
Corrección requiere inserción de más bits redundantes
m bits corresponden al dato k=n-m son la información redundante
Paridad permite detectar pero no corregir errores
di en las posiciones restantes
Un dato de 4 bits d1d2d3d4 requerirá 3 bits de validación p1p2p4 Posición Bit
1 p1
2 p2
4 p4
3 d1
5 d2
6 d3
7 d4
Generación de Código Hamming
El bit de paridad de la posición 2k comprueba los bits en las posiciones que tengan al bit k en su representación binaria Binario
20
P1 P2 2 1 P4 2 2 P8 2 3
1 2 4 8
0001 0010 0100 1000
Posición
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
10
1011
11
1100
12
P1
P2
P4
P8
X X X
X X
X
X
X X
X
X
X X
X
X
X X
X
X
X x
X
9
Sistemas Digitales
Verificación de código Hamming
Calcular los bits de comprobación Cj
Ejemplo Código Hamming
Cada bit verifica paridad para el subconjunto asociado a la posición j (tabla anterior)
Enviar BCD 0110 codificado en Hamming
p1 = b3 ⊕ b5 ⊕ b7 = 0 ⊕ 1 ⊕ 0 = 1 p2 = b3 ⊕ b6 ⊕ b7 = 0 ⊕ 1 ⊕ 0 = 1 p4 = b5 ⊕ b6 ⊕ b7 = 0 ⊕ 1 ⊕ 1 = 0
c1 = b7 ⊕ b5 ⊕ b3 ⊕ b1 c2 = b7 ⊕ b6 ⊕ b3 ⊕ b2 c4 = b7 ⊕ b6 ⊕ b5 ⊕ b4
El valor decimal equivalente a c4c2c1 indicará la posición donde hubo un error
Dato recibido es 1100100
Posición Bit Hamming
Si no hubo error, c4c2c1 será 000
Ejemplo Código Hamming
Codifique el número decimal 7 en código Hamming(7, 4) Detecte la presencia de un error en el código Hamming(7, 4) 1010101 y corríjalo
5 d2 1
6 d3 1
7 d4 0
En conjunto con BCD 8421 Este código puede corregir cualquier error en un bit, y detectar todos los errores de 2 bits Probabilidad de 2 errores es bajísima Agrega 3 bits de paridad por cada 4 bits de datos
Transmitir bloques de datos
Dato tiene bit de paridad (paridad horizontal) Bloque incluye palabra de validación (paridad vertical)
Error en un bit modifica ambas paridades
Error puede ser identificado y corregido Eficiente para grandes cantidades de datos Disminuye los bits redundantes en cada dato Permite detectar múltiples errores
©2013 Mario Medina C.
4 p4 0
Transmisión de bloques
3 d1 0
Código Hamming(7, 4) es ineficiente
Se debió haber recibido 1100110 Dato transmitido correcto es 0110
Ejercicios
2 p2 1
Código Hamming(7, 4) es el más usado
Calcular bits de comprobación c4c2c1
El error está en el bit c4c2c1 = 110 Receptor puede invertir bit 6 y corregir el error
1 p1 1
Código Hamming(7, 4)
c4 = b4 ⊕ b5 ⊕ b6 ⊕ b7 = 0 ⊕ 1 ⊕ 0 ⊕ 0 = 1 c2 = b2 ⊕ b3 ⊕ b6 ⊕ b7 = 1 ⊕ 0 ⊕ 0 ⊕ 0 = 1 c1 = b1 ⊕ b3 ⊕ b5 ⊕ b7 = 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0
Calcular bits de paridad p1p2p4
Aunque no corregirlos
10
Sistemas Digitales
Transmisión de bloques
Transmitir 5 datos usando paridad par vertical y horizontal Paridad
Dato
1
01101
1
00100
0
10010
0
01001
0
11110
0
01100
Transmisión de bloques
Error en la transmisión puede ser corregido Paridad
Recibido
0
101101
0
100100
0
VRC: Vertical Redundancy Check BPI (VRC) b b b b b b b 6 5 4 3 2 1 0
LRC: Longitudinal Redundancy Check A
1
1
0
0
0
0
0
1
L
0
1
0
0
1
1
0
0
A
1
1
0
0
0
0
0
1
010010
R
0
1
0
1
0
0
1
0
1
001011
LRC
1
1
1
0
0
0
0
1
0
011110
0
001100
BPI
000010
1
BPI: Bit de Paridad Impar Información a transmitir
BPI 1100001
0
BPI 1010010
LRC
R
1
BPI 1000001 A
0
BPI 1001100 L
1
1000001 A t
error
Códigos alfanuméricos
Permiten transmisión de información para equipos complejos de procesamiento de datos Letras, números, símbolos y señales de control Más comunes con ASCII y Unicode UNICODE (utf-8) Utiliza 32 bits => 232 símbolos diferentes Incluye casi todos los alfabetos conocidos Aún quedan códigos libres Posibilidad de programación internacional
Códigos alfanuméricos
Código ASCII es el más usado hoy en día
American Standard Code for Information Interchange Codifica utilizando 7 bits (128 dígitos diferentes) Un octavo bit se utiliza como bit de paridad ASCII Extendido (8 bits) Permite representar 256 símbolos Engorroso e incompatible entre lenguajes No hay estándar definido para ASCII-8
Unicode
Estándar de codificación de caracteres
Incluye todos los caracteres de uso común en la actualidad Versión 5.1 contiene 100 713 caracteres
UTF-8: codifica caracteres en 1, 2, 3 ó 4 bytes
Alfabetos, sistemas ideográficos y símbolos diversos
1 bytes: US-ASCII 2 bytes: caracteres romances, griegos, signos 3 bytes: casi todo el resto, grupo CJK 4 bytes: lenguajes académicos, símbolos matemáticos
©2013 Mario Medina C.
11
Sistemas Digitales
Código de barras
Código QR
UPC (Universal Product Code)
Se puede leer de izquierda a derecha o de derecha a izquierda
Digit
Izquierdo
Derecho
Digit
Izquierdo
Derecho
0
0001101
1110010
5
0110001
1001110
1
0011001
1100110
6
0101111
1010000
2
0010011
1101100
7
0111011
1000100
3
0111101
1000010
8
0110111
1001000
4
0100011
1011100
9
0001011
1110100
Código QR (Quick Response Code)
Código de barras bidimensional Desarrollado por la industria automotriz Código incorpora corrección de errores, puede estar encriptado Capacidad ~3 KB
67
©2013 Mario Medina C.
12