Códigos
Prof. Mario Medina C.
Prof. Jorge Salgado S.
mariomedina@[Link]
jorgesalgado@[Link]
Mario Medina
Conceptos generales
Código: es un conjunto de símbolos usados
para representar letras, números, palabras,
conceptos u otros símbolos.
Ejemplos: Código Morse, ASCII, emoticones, etc.
En un número codificado, los símbolos
representan algo, y sólo podremos saber su
significado si conocemos el código que las
generó
Conceptos generales
Ventajas de la codificación:
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
Son de difícil comprensión para el ser
humano, pero es el lenguaje natural en
circuitos.
Es una representación fácil y eficiente en:
Circuitos eléctricos, mecánicos o hidráulicos
Medios de almacenamientos ópticos y magnéticos
Definiciones (importantes…)
Capacidad de un código:
Es el número de valores distintos en el código
Depende del número de dígitos en el código
Ej. Un código de 3 bits tiene capacidad 23 = 8
Utilización de un código:
Es el número de valores distintos definidos como
válidos en el código.
La utilización del código puede ser menor que la
capacidad. Ej: 10/16 (BCD)
Existen palabras no válidas en el código.
Definiciones…
La distancia entre 2 palabras de un código
es el número de símbolos de una palabra
que deben modificarse para obtener la otra
palabra.
La distancia mínima de un código se da entre
2 palabras válidas adyacentes cualesquiera de
un código.
Código adyacente es aquel en que todas las
palabras tienen distancia 1 con sus vecinos.
Ej: Código Gray.
Tipos de códigos
Códigos ponderados
Códigos BCD
Códigos autocomplementados
Códigos adyacentes
Código Gray
Códigos ponderados
Las palabras del código son generadas
por un polinomio, cuyos dígitos tienen una
ponderación establecida.
Ejemplo:
Binary-Coded Decimal (BCD)
Es el código ponderado más usado.
Cada digito decimal se representa por 4 bits
Capacidad del código: 16
Utilización del código: 10/16
Existen diferentes tipos de BCD, dependiendo
de las ponderaciones de cada bit.
Códigos ponderados…
BCD 8421 (Similar al binario puro)
Usa 4 bits para representar un dígito decimal.
Las secuencias 1010 al 1111 no son válidas.
Dec 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
Códigos BCD 10/65
Existen otros códigos BCD
BCD 2421, BCD 1224, BCD 7421, BCD 6321, etc.
En algunos, un dígito decimal no tiene
representación única.
Ej: 610 en BCD 2421 puede ser 1100 o 0110
Se prefiere 1100. Los dígitos 0 a 4 comienzan con 0
Es necesario definir normas particulares
BCD 8421 asegura representación única
Los códigos BCD son válidos para números
enteros y fraccionarios
Permiten operaciones aritméticas de gran tamaño.
Ejemplo de códigos BCD
Representación Decimal BCD 7421 BCD 4321
0 0000 0000
del número 25
1 0001 0001
En binario 2 0010 0010
11001 3 0011 0100 ó 0011
En BCD 7421 4 0100 0101 ó 1000
5 0101 1001 ó 0110
0010 0101
6 0110 1010 ó 0111
En BCD 4321 7 1000 ó 0111 1011 ó 1100
0010 1001 8 1001 1101
Se prefiere que 9 1010 1110
dígitos 0 a 4
empiecen con 0
Códigos autocomplementados
Códigos en que el complemento disminuido
de una palabra también es una palabra válida
En binario, elcomplemento a 1 se obtiene
invirtiendo cada uno de los bits originales.
Especialmente útiles para realizar restas
Simplifican circuitos de complementación
Más utilizados:
Exceso 3(código BCD 8421 + 3)
BCD 2421
Códigos autocomplementados…
Decimal Exceso 3 BCD 2421
0 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 ok
Códigos autocomplementados…
Ejercicio: Dado el numero 90710 hallar el complemento
a la base disminuída (C´9).
Solución:
Representar el numero 90710 en BCD exceso-3, y usar
el complemento a 1 para encontrar el complemento a
la base disminuida del número (C´ 9).
1100 0011 1010Exc 3
90710 09210 en complement o a 9
0011 1100 0101Exc 3
Verificar que el resultado está correcto:
El complemento a 9 de 90710 es : 999-907 = 09210 Ok
Ejemplos de números BCD 8421
0111 7 Válido
1111 15 Inválido
1011 11 Inválido
1001 9 Válido
1000 8 Válido
Códigos adyacentes
Llamados también códigos reflejados.
Los 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
Código Gray
Es un código adyacente no ponderado.
Los digitos decimales consecutivos difieren
en un solo bit.
Simplifica la transición entre estados.
Útil para sistemas físicos con transiciones
mecánicas
Util en presencia de ruido y elevado consumo
de potencia.
Códigos adyacentes…
Decimal Codigo Gray Reflejado Exc. 3
0 0000 0010
1 0001 0110
2 0011 0111
3 0010 0101
4 0110 0100
5 0111 1100
6 0101 1101
7 0100 1111
8 1100 1110
9 1101 1010 Ok…
Codificador de posición rotatorio ¿Error en colores?
Aplicación común: determinar posición
y velocidad de ejes (rotary encoder)
Con código Gray todas las posiciones son adyacentes
Conversión binaria a Gray 20/65
Definiendo la operación Ejemplo: pasar 11002
XOR a Gray
00 0
g0 b0 b1 0 0 0
0 1 1
g1 b1 b2 0 1 1
1 0 1
g2 b2 b3 1 1 0
1 1 0
g3 b3 b4 1 0 1
La relación para pasar
de binario a Gray es Entonces, 11002 es
1010Gray
gi bi bi1 ok
Conversión Gray a binario
Regla de conversión: Ejemplo: Transformar
bMSB gMSB el dato 1101Gray a
bi bi1 gi binario
b3 = g3=1
Se copia el bit más b2 = b3 ⊕ g2 = 1 ⊕ 1= 0
significativo b1 = b2 ⊕ g1 = 0 ⊕ 0= 0
Se usa XOR para calcular b0 = b1 ⊕ g0 = 0 ⊕ 1= 1
bits siguientes
Entonces,
1101Gray = 10012 Ok.
Generación código Gray
Gray de 1 bit
Los dos valores posibles son 0 y 1
Gray de 2 bits
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.
ok
Generación código Gray…
0 00 000 0000
1 01 001 0001
Código Gray
11 011 0011
10 010 0010
110 0110
111 0111
101 0101
100 0100 Código reflejado
1100 exceso 3 ok
1101
1111
1110
1010
1011
1001
1000
Código Gray y
código reflejado exceso 3
Código Gray es reflejado, cíclico y adyacente
Distancia 1 entre dígitos 0 al 15
Distancia 3 entre el 9 y el 0
Código reflejado exceso 3 es cíclico y es
adyacente
Distancia 1 entre dígitos 0 al 9
Distancia 1 entre 9 y 0
Se obtiene sumando 3 al código Gray y después
reflejar.
Códigos de largo variable
Los códigos anteriores son de largo fijo.
Todos las combinaciones (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 uso del símbolo en el mensaje.
Las secuencias más cortas corresponden a símbolos
más frecuentes.
Se reduce el largo promedio de los mensajes.
Propiedad prefijo
Para que un código de largo variable esté
completamente definido, debe cumplirse
la 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
Construcción de un código
Huffman
Pasos para construir el árbol de decodificación:
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 sucesor.
Frecuencia será suma de frecuencias de los dos nodos
Repetir hasta que quede solo un nodo sin sucesor.
Construcción de un código Huffman…
Rotular los arcos del grafo
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
Asignar a cada nodo la secuencia de 0s y 1s
correspondientes al camino desde la raíz al nodo
en cuestión
Ejemplo código Huffman
Dada la siguiente Se genera el siguiente
frecuencia de símbolos árbol
Dato Frecuencia 0
(0.6)
1
(0.4)
A 0.35
0 0 1
B 0.25 A (0.35) 1 C (0.15) (0.25)
B (0.25)
C 0.15 0 1
D 0.15 D (0.15) E (0.1)
E 0.10
Ejemplo código Huffman 30/65
Este código cumple con la propiedad prefijo
Largo promedio de un símbolo: 2.25 bits
Dato Frecuencia Código
A 0.35 00
B 0.25 01
C 0.15 10
D 0.15 110
E 0.10 111
Ejemplo código Huffman
Símbolo Frecuencia 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
31
Tarea
1. Dados los símbolos a, b,c,d, e con probabilidades
1/8, 1/8, 1/4 ,1/4, 1/4, desarrollar el algoritmo de Huffman y
determinar promedio de los símbolos codificados.
2. Sea el alfabeto fuente S= {a1, a2, a3, a4} y la distribución de
probabilidades siguiente P={0,4; 0,3; 0,2; 0,1}, mediante el algoritmo
de Huffman determinar la palabra binaria asociada a cada símbolo, y
la longitud promedio de las palabras encontradas.
3. Aplicar el método de Huffman para obtener el código instantáneo
óptimo para una fuente de alfabeto S = {a1, …a6} y con la
distribución de probabilidades siguiente:
p(a1)=0,3; p(a2)=0,25; p(a3)=0,2; p(a4)=p(a5)=0,1; p(a6)=0,05T
4. Se ha recibido una palabra del código CRC, 1101 1101 0111 10001,
el que durante la transmisión tuvo un cambio en tres bits sucesivos.
Si el polinomio divisor es G(x) =110101.
Calcular el resto R(x) en el receptor. ¿Qué puede concluir después
del cálculo?.
5. Al transmitirse un mensaje de 12 bits, usando el código CRC, se han
modificado 6 bits no sucesivos, el dato recibido es: 1111 1100 1111 10001.
El polinomio divisor es el mismo del caso anterior. Calcular el resto y concluir
sobre la validez del dato recibido.
6. Usando el código CRC calcular el resto R(x) en el receptor, si G(x) es 1011,
y el dato recibido es: 1101 0011 1011 00.
7. Enviar el dato binario BCD 0011 codificado en Hamming.
Calcular los bits de paridad p1p2p3 en el Tx.
Calcular los bits de comprobación C4C2C1, en el receptor.
¿Hubo error durante la transmisión del dato?
8. Determinar los códigos binarios ASCII que se han introducido a través del
teclado de la computadora cuando se han escrito las instrucciones siguientes:
20 PRINT”A=”,X
VIVA EL 18 DE SEPTIEMBRE …VIVA CHILE.
Sistemas Digitales. II-2013.
Códigos detectores de errores
El 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 velocidad de transmisión y potencia de la señal
Códigos detectores de errores…
Se desea detectar errores y pedir retransmisión
de datos erróneos.
Deben existir palabras no válidas en el código
La inversión no deseada de uno o más bits
genera una palabra no válida.
La distancia mínima de un código debe ser mayor
que D (número de errores a detectar).
Códigos detectores de errores…
Tipos de códigos detectores:
Códigos de paridad
Agregar un bit a la palabra para verificar si
número de bits en estado 1 es par o impar.
Códigos de peso constante
También llamados m de n.
Mantienen un número constante de bits en 1.
Cyclic Redundancy Check (CRC)
Códigos de paridad
Paridad: cardinalidad de los 1s en una palabra.
Ésta puede ser par o impar.
Código de paridad
Se agrega un bit a cada palabra transmitida para
asegurar que el número de 1´s sea par o impar.
Transmisor y receptor se ponen de acuerdo
Duplica la cantidad de palabras del código.
Igual número de palabras válidas e inválidas
Asegura una distancia mínima de 2
Códigos de paridad…
Ejemplo:
Expresar el binario 1001010 en un código de paridad par.
Solución:
1 1001010
Paridad Dato
Palabras como 01001010 y 10001010 son inválidas en el
código. ¿Porqué?
Número de 1s es impar
El código sólo detecta número impar de unos y no
la estructura del número
Códigos de peso constante
Mantienen un número constante m de bits
en 1 en las palabras del código.
Códigos de 5 bits (pentádicos).
Más usados:
Walking code 2 de 5
BCD 63210
Códigos de 7 bits
Qui-binario (10-86420)
Bi-quinario (50-43210)
Códigos de peso constante…
40/65
Decimal 2 de 5 BCD 63210 50-43210 10-86420
0 00011 00110 01-00001 01-00001
1 00101 00011 01-00010 10-00001
2 00110 00101 01-00100 01-00010
3 01010 01001 01-01000 10-00010
4 01100 01010 01-10000 01-00100
5 10100 01100 10-00001 10-00100
6 11000 10001 10-00010 01-01000
7 01001 10010 10-00100 10-01000
8 10001 10100 10-01000 01-10000
9 10010 11000 10-10000 10-10000
Cyclic Redundancy Check (CRC)
Dados:
Un Polinomio M(x) (mensaje a transmitir).
[Es un número binario de orden (n-1) y n
bits].
Un Polinomio generador G(x) de orden r < n,
G(x) = 101001 = x5+ x3+1
Algortimo de los códigos de redundancia cíclica
Los pasos del algoritmo utilizado por el control de
redundancia cíclica son los siguientes:
1. Se añaden r bits “0” a la derecha del mensaje (tantos
ceros como el grado del polinomio generador).
2. Se divide por G(x) el nuevo polinomio así obtenenido,
para obtener el resto R(x) de la división .
Cyclic Redundancy Check (CRC)… 40/62
3. Después, se añade el resto de la división a la derecha
del mensaje original y, se envía el mensaje al
Receptor (Rx).
4. El receptor divide la palabra codificada, por el mismo
polinomio G(x).
Si el resto es 0 : No hubo errores
Si el resto no es 0 : Hubo error en la transmisión
Cyclic Redundancy Check
(CRC)…
Resumen:
I. El transmisor transmite un mensaje de p
bits, formado por M(x) seguido de R(x).
II. El receptor divide, la palabra recibida y
codificada, por el mismo polinomio G(x).
Si el resto es 0: no hubo errores
Si el resto es distinto de 0: hubo error en la
transmisión.
Ejemplo 1 de CRC
Un mensaje M(x) de 12 bits: 110100110111
M(x) = x11+x10+x8+x5+x4+x2+x1+x0
Polinomio generador G(x) = x5+x4+x2+1 =110101
Solución:
En el transmisor:
Dividir 11010011011100000 por 110101
El Resto de la división es: R(x) = 10001 (Ver diapos. siguiente)
Palabra transmitida es 110100110111 10001
Tarea: Comprobar, mediante CRC, que en el receptor el resto es cero.
Ok…
Ejercicio 1: Cálculo del resto CRC (en el Tx)
División mediante restas independientes sin
préstamo
Alinear MSB de G(x) con el 1er bit en 1 de M(x)´
Realizar XOR entre los bits
Repetir paso 1 hasta obtener el resto de la división
Fácil de implementar con desplazamientos y XORs
11010011011100000
110101____________
111011100000
110101______
1110100000
110101____
11110000
110101__
100100
110101
010001 = R(x)
Ejemplo 2 de CRC: Supongamos que un error
de transmisión modifica 3 bits sucesivos.
Dato recibido es 1101 110 1 0111 10001
Resto de división por G(x) es distinto de 0. Error detectado.
Ok….verificado…
Ejemplo 3: Supongamos que un error de
transmisión modifica 6 bits no sucesivos. G(x) ya dado
Dato recibido es 11111100111110001
Resto de división por G(x) es 0. El error no es detectado!
CRC sirve para verificar la integridad del mensaje, pero
no para saber si es correcto.
Tarea: Usando el CRC calcular el resto si el dato recibido en el Rx es:
11010011101100 y G(x) = 1011. Sol: R(x) = 0101
Resumen de Cyclic Redundancy Check (CRC)
Un CRC de r bits detecta una cadena de
errores en bits consecutivos.
Existen combinaciones de errores no detectables
Pueden obtenerse del análisis matemático
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): (X.25, Bluetooth)
Códigos correctores de errores
El código con bit de paridad y el CRC permiten
detectar pero no corregir los errores.
La corrección requiere la inserción de más bits
redundantes.
Requieren una distancia mínima 3
Muy usados para respaldo de información son:
Código Hamming
Transmisión de bloques
Códigos correctores de errores…
Código corrector de errores
50/65
m bits corresponden al dato
n bits transmitidos
k=n-m es la información redundante
Se debe cumplir M – 1 = D+ C, C≤D
M: distancia mínima del código
D: número de errores a detectar
C: número de errores a corregir
M 1 2 3 4 5 6
C 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 Ok
Código Hamming (7/4)
Es un código que detecta y corrige un error
di : bits del dato original
pi : bits redundantes en las posiciones que son
potencias de 2
Un dato de 4 bits, d1d2d3d4, requerirá 3 bits
de redundantes de validación p1p2p4
Posición 1 2 3 4 5 6 7
Bit p1 p2 d1 p4 d2 d3 d4
Generación del Código Hamming
Cada bit de validación (pi) verifica la paridad
de un subconjunto de bits del dato. (BCD 8421)
Estos bits verifican los datos decimales:
Posición 1 (p1): decimal 1, 3, 5, 7, 9, 11, 13, …
Posición 2 (p2): decimal 2, 3, 6, 7, 10, 11, 14, 15, …
Posición 4 (p4): decimal 4, 5, 6, 7, 12, 13, 14, 15, …
Posición 8 (p8): decimal 8, 9, 10, 11, 12, 13, 14, 15, 24, …
Ok… ver tabla siguiente…
El bit de validación se escoge para generar
paridad par sobre los bits verificados.
Generación del Código Hamming…
El bit de paridad de la posición 2k comprueba los bits 1 en los
números (posiciones) que tengan al bit k en su representación binaria
Binario Posición
P1 P2 P4 P8
P1 20 1 0001 0001 1 X
P 2 21 2 0010 0010
0011
2
3 X
X
P 4 22 4 0100 0100
0101
4
5 X
X
P 8 23 8 1000 0110 6 X X
0111 7 X X X
1000 8 X
1001 9 X X
1010 10 X X
1011 11 X X X
1100 12 x X
Código Hamming…
I. Cálculo de los bits de paridad
Ejemplo1:
Enviar BCD 0110 codificado en Hamming
1. Calcular los bits de paridad p1p2p4
p1 = b3 ⊕ b5 ⊕ b7 = 0 ⊕ 1 ⊕ 0 = 1
p2 = b3 ⊕ b6 ⊕ b7 = 0 ⊕ 1 ⊕ 0 = 1
p4 = b5 ⊕ b6 ⊕ b7 = 1 ⊕ 1 ⊕ 0 = 0 Ok
Posición 1 2 3 4 5 6 7
Bit p1 p2 d1 p4 d2 d3 d4
Hamming 1 1 0 0 1 1 0
Código Hamming…
II. Verificación de los bits de paridad Cj
2. Cálculo de los bits de comprobación
(en el receptor)
Cada bit verifica la paridad para el subconjunto
asociado a la posición j (tabla anterior)
c1 = b1 ⊕ b3 ⊕ b5 ⊕ b7
c2 = b2 ⊕ b3 ⊕ b6 ⊕ b7
c4 = b4 ⊕ b5 ⊕ b6 ⊕ b7
El valor decimal equivalente a c4c2c1 indicará la
posición donde hubo un error.
Si no hubo error: c4c2c1 será 000
Ejemplo 2: Código Hamming…
Si el dato recibido es 1100100:
Calcular los bits de comprobación c4c2c1
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
El error está en el bit c4c2c1 = 110
Receptor puede invertir bit 6 y corregir el error
Se debió haber recibido 1100110
Dato transmitido correcto es 0110 ok…
Tarea: Verificar esto último.
Resúmen del Código Hamming(7,4)…
El código Hamming (7,4) es el más usado
en conjunto con BCD 8421.
Este código puede corregir cualquier error en
un bit, y detectar todos los errores de 2 bits.
La probabilidad de 2 errores es bajísima.
El código Hamming(7,4) es ineficiente.
Agrega 3 bits de paridad por cada 4 bits de datos.
Transmisión de bloques de datos
Al transmitir bloques de datos:
Cada dato tiene un bit de paridad (paridad horiz.)
El bloque incluye una palabra extra de validación
(paridad vertical)
El error en un bit modifica ambas paridades
Error puede ser identificado y corregido
Es eficiente para grandes cantidades de datos
Disminuye los bits redundantes en cada dato
Permite detectar múltiples errores
Aunque no corregirlos
Transmisión de bloques de datos…
Ej1. Transmitir 5 datos Error en la transmisión
usando paridad par puede ser corregido
vertical y horizontal Paridad Recibido
0 101101
Paridad Dato
0 100100
1 01101
0 010010
1 00100
1 001011
0 10010
0 011110
0 01001
0 001100
0 11110
1 000010
0 01100
error
Códigos alfanuméricos
60/65
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)
Utiliza 7 bits (128 dígitos o símbolos diferentes)
Un octavo bit se utiliza como bit de paridad
EASCII Extendido (8 bits)
Permite representar 256 símbolos
Engorroso e incompatible entre lenguajes
No hay estándar definido
Código de Barras 60/62
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
63
Tarea:
Investigar sobre:
• El código ASCII
• El código de barras.
Fin de códigos