|
CODIGO DE HAMMING.
Un código de Hamming es un código de bloque lineal. Al igual que en los códigos de bloque lineales sistemáticos,
podemos denotar un código de Hamming mediante un par (n,k). Sin embargo los valores de n y k deberán verificar una serie de
condiciones:
- n es la longitud de la palabra de código
- k es el número de bits de datos de la palabra original sin codificar
- el número de bits de paridad será m = n - k, pero deberá cumplirse la siguiente relación entre
la longitud de la palabra de código y el número de bits de paridad:
n = 2m - 1 con m >= 3
- según esto también se cumplirá la siguiente relación entre el número de bits de datos y el
número de bits de paridad:
k = 2m - m - 1
Por lo tanto, a cada palabra original la añadiremos unos bits de paridad para obtener la palabra de código, de forma
que estos bits de paridad sirvan posteriormente para encontrar y corregir errores que se produzcan en la transmisión.
Cada uno de los bits de paridad que añadimos a una palabra original va a afectar a unas determinadas posiciones
de la nueva palabra de código, de forma que tomarán un valor adecuado para que se cumpla el criterio de paridad (par o impar)
preestablecido en las subcombinaciones afectadas por cada uno de estos bits de paridad.
El siguiente paso consistirá en determinar a que posiciones de los bits de las palabras de código afecta cada bit
de paridad. Para ello construiremos todas las combinaciones posibles con m bits de paridad e interpretamos cada una en binario
natural:
bm ..................... b3 b2 b1 Posición
0 ....................... 0 0 0 ............ 0
0 ....................... 0 0 1 ............ 1
0 ....................... 0 1 0 ............ 2
0 ....................... 0 1 1 ............ 3
......................................
Cada bit de paridad va a afectar a aquellas posiciones en las que ese bit vale 1.
Bit de paridad Posiciones
b1 ................. 1,3,5,7,..........
b2 ................. 2,3,6,7,..........
..................................................
bm ................. 2m, 2m+1,2m+2,......
Por último sólo nos queda determinar que posiciones de cada palabra de código ocupará cada bit de paridad. Los bits
de paridad han de colocarse en aquellas posiciones en las que no se vean afectados por otros bits de paridad. Estas posiciones
serán:
Bit de paridad Posición
b1 ................... 20
b2 ................... 21
b3 ................... 22
....................................
De esta forma queda completado el proceso de construcción de un código de Hamming.
En el proceso de decodificación, el receptor recibe una palabra de un código de Hamming, y deberá comprobar si es
correcta o no, y en el caso de que no fuera correcta deberá comprobar en que bit se produjo el error y corregir ese error.
Para comprobar si la palabra recibida es correcta, el receptor debe utilizar los bits de paridad de la palabra y
hacer con ellos un control de paridad.
Para realizar el control de paridad creamos una palabra que tendrá un bit por cada uno de los bits de paridad utilizados.
Cada uno de los bits de esta palabra tomará el valor 0 o 1 dependiendo de si el número de unos de las posiciones de la palabra
de código afectadas por su correspondiente bit de paridad cumplen o no el criterio de paridad establecido. Interpretando la
combinación resultante en binario natural tendremos dos posibilidades:
- que sea un 0, lo cual quiere decir que no se han producido errores en la transmisión
- que se corresponda a un número distinto de 0, lo cual quiere decir que durante la transmisión
ha variado el bit situado en la posición indicada por ese número.
Una vez obtenida la palabra de código correcta, basta con quitar los bits de paridad para obtener la palabra original
enviada por el emisor.
El siguiente Apple permite al usuario interactuar para construir su propio código de Hamming y poder realizar ejemplos
de decodificación y control y corrección de errores.
CODIGO REDUNDANCIA CICLICA (CRC)
Son un tipo de códigos cíclicos especialmente buenos para la detección de errores:
- Se diseñan para detectar muchas combinaciones de errores.
- La implementación práctica es sencilla. Son los que se usan en la práctica.
Existen distintos polinomios generadores en base a pruebas:
g(x) n
- k
CRC-12 x12 + x11 + x3 + x2 + x + 1 12
CRC-16 x16 + x15 + x2 + 1 16
CRC-ITU
ó x16 + x12 + x5 + 1 16
CRC-CCITT
- Los tres contienen H(x) como factor primo
- CRC-12 se usa con palabras de datos de 6 bits
- CRC-16 y CRC-ITU con palabras de datos de 8 bits
|
