CODIGOS
Algunos ejemplos de códigos son:
ASCII
EBCDIC
EXCESO 3
GRAY
Manejo de Información Empaquetada y Desempaquetada
Es muy importante el manejo de
información en la memoria del microprocesador. Por ejemplo, información
codificada en ASCII se puede almacenar en la memoria en forma empaquetada o
desempaquetada: supongamos que se desea almacenar los caracteres hexadecimales
A, B, C y D.
Ejemplo: Código ASCII: A (41H), B
(42H), C (43H), D (44H)
Empaquetada Desempaquetada
41 42 41
43 44 42
43 44
La ventaja de utilizar la forma
empaquetada, es que se emplea mejor la memoria, sin embargo, en forma
desempaquetada, la información se puede manejar más fácil y rápidamente.
Códigos Detectores
y Correctores de Errores
La capacidad para detectar posibles
errores en la información manipulada por las
Computadoras es esencial para poder
confiar en los resultados ofrecidos.
El error es la alteración del valor
correcto en uno o más bits de información producida durante su almacenamiento,
transmisión o manipulación.
Un concepto muy importante relativo a
la corrección y detección de código de errores es el término “distancia”.
La distancia entre dos números binarios es igual a la cantidad de bits que
difieren entre sí, es decir, es la cantidad de bits diferentes entre un número
y otro.
Chequeo de
Redundancia Cíclica (CRC)
Este método es mucho más efectivo que
los anteriores en la detección de errores en los sistemas de comunicaciones. No
permite la corrección de errores.
En este método, en forma similar a los
anteriormente descriptos, se envía uno o más caracteres adicionales de
redundancia denominados FCS ("frame check sequence") o BCC ("block
check caracter"), que difieren fundamentalmente en la forma de calcularlo.
El CRC consiste en considerar a los
bits a ser transmitidos como un polinomio en x (para n bits el orden es n-1)
tal que la presencia de un término significa un "1", y la ausencia,
un "0"; es decir: sean 1010101 los bits a transmitir, entonces el
mensaje podrá ser considerado como un polinomio G(x) tal que: G(x) = x7 + x5 +
x3 + 1. Un mensaje de código cíclico consiste en un número de bits de datos y
el BCC. Sea n el número total de bits y k el número de bits de datos, por lo
tanto, el número de bits del BCC es n - k. El código del mensaje (BCC) se
obtiene de 2 polinomios:
·
Polinomio
generador P(x)
·
Mensaje
polinomial G(x) (bits de datos).
Dados:
·
P(x): polinomio generador
·
G(x): polinomio de mensaje de datos
Se
desea hallar F(x), código del mensaje polinomial, como sigue:
·
Multiplicar
el mensaje G(x) por x, siendo n - k el número de bits del BCC para dar lugar al
BCC (multiplicar por x, es lo mismo que desplazar el mensaje polinomial de datos
n-k lugares completando con ceros a la derecha).
G(x) * xn-k
·
Dividir
el producto resultante G(x) * xn-k por el polinomio generador P(x).
G(x) * xn-k = Q(x) P(x) + C(x)
·
Despreciar
el cociente y sumarle a G(x) * xn-k el resto C(x) de la división para producir
el código de mensaje polinomial F(x).
F(x) = G(x) * xn-k + C(x); Mensaje
Polinomial a Transmitir
El efecto general que se observa en el
chequeo por medio del CRC, es que cualquier bit se refleja en varios bits por
un tiempo considerable después que éste fue transmitido. Esto es muy
importante, ya que se ha comprobado que la mayoría de los problemas de errores
en comunicación de datos se producen en pequeños grupos de bits
("burst").
Características
más significativas del CRC:
·
Detecta
todos los errores de 1 y 2 bits (errores simples y dobles).
·
Detecta
todos los errores de un “Burst” menor que el grado de P(x)
·
Detecta
el 99 % de los errores de un “Burst” mayor que el grado de P(x)
Códigos Hamming
El código Hamming es un código de
distancia 3, capaz de detectar errores dobles y corregir si hay un error
simple. El código Hamming se forma por n bits de información (Mn, Mn-1,... M1)
y k bits de chequeo (Ck, Ck-1,..... C1) de paridad par o impar. El mensaje codificado
está formado por n + k bits, siendo k el menor entero que cumple que: 2k ≥
n+k+1 [7] (por ejemplo, si n = 7, entonces k = 4). Hamming es un código capaz de corregir
un error simple por lo tanto debe identificar un bit erróneo en una cadena de
bits. Entonces la ecuación [7] nos dice que el número de combinaciones de los
bits de chequeo (2k) debe ser al menos igual al número de bits del mensaje más
los bits de redundancia más una combinación extra para identificar que no hubo errores.
Los bits de chequeo ocupan posiciones
específicas en el mensaje codificado. Esas posiciones son potencias enteras de
2, es decir 1, 2, 4,8,.... 2k-1, es decir que los bits de paridad se ubican en
los posiciones que tienen un único bit a 1 en su ordinal. Los valores de cada Ci
se calculan chequeando la paridad en lugares específicos del mensaje original
M. Por ejemplo para un código de 6 bits de mensaje, el mensaje codificado será:
M6 M5 C4 M4 M3 M2 C3 M1 C2 C1
1010 1001 1000 0111 0110 0101 0100
0011 0010 0001
C1 = M1 ⊕ M3 ⊕
M5 ⊕ M7 ⊕ M9.......
C2 = M2 ⊕ M3 ⊕
M6 ⊕ M7 ⊕ M10.......
C3 = M4 ⊕ M5 ⊕
M6 ⊕ M7............
C4 = M8 ⊕ M9 ⊕
M10. .............
Para el cálculo de los coeficientes Ci´s,
los valores de Mi´s empleados, se refieren a la posición que ocupan los
elementos en el mensaje codificado, tomando a M1 igual a cero (ya que
corresponde al valor de Ci del mensaje codificado) para el cálculo inicial.