Sistemas Digitales

Códigos

Códigos Prof. Mario Medina [email protected]

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 1010Exc3  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 00=0 01=1 10=1 11=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