Universidad Distrital, Maestría en Teleinformática,
Bogotá D.C., Colombia.
Mayo de 2012
INTEGRANTES

ALVARO HUMBERTO CISNEROS
DANIEL SEPULVEDA NUÑEZ
CONTENIDO





HISTORIA
TÉCNICAS DE DETECCIÓN DE ERRORES
TÉCNICAS DE CORRECCIÓN DE ERRORES
RICHARD WESLEY HAMMING
 CÓDIGO HAMING






CORRECCIÓN DE ERRORES
SÍNDROME Y CORRECCIÓN DE ERROR
DETECCIÓN Y EFICIENCIA SOBRE CANAL
HAMING EXTENDIDO
CONCLUSIONES
BIBLIOGRAFÍA
HISTORIA

 Cuando se transmite información, se corre el riesgo de la presencia
de interferencia o ruido.
 El origen de la teoría de códigos correctores de errores se encuentra
en los trabajos de Golay, Hamming y Shannon.
 Inicio enfoque probabilístico, pasa a un enfoque más algebraico
[códigos de Golay y de Hamming, los códigos cíclicos y BCH, o los
códigos de Reed-Solomon y de Reed-Muller].
HISTORIA

 En los 70 Goppa – Construye códigos lineales a partir de curvas
algebraicas lisas llamados códigos AG (álgebro-geométricos).
 Los códigos AG apenas han sido implementados en la práctica
debido a la profundidad matemática de las ideas subyacentes.
 Los métodos de decodificación para códigos geométricos de
Goppa son efectivos, su preprocesamiento es de una elevada
dificultad e involucra complejos algoritmos basados en métodos
de la geometría algebraica computacional.
TÉCNICAS DE
DETECCIÓN DE ERRORES

 Códigos VRC (Vertical Redundancy Check).
En esta técnica, un bit redundante, denominado bit de paridad, se
añade al final de cada bloque de datos.
 Código LRC (Longitudinal Redundancy Check).
Esta técnica consiste en VRC de dos dimensiones, se agrupa un
determinado número de unidades de datos en un bloque, cada uno
con su bit VRC correspondiente. Se calcula el bit de paridad entre
cada bit de todas y cada una de las unidades de datos (primeros
bits, segundos, etc.). Se reúnen los bits de paridad de todas las
posiciones en una nueva unidad de datos y se añade al final del
bloque.
TÉCNICAS DE
DETECCIÓN DE ERRORES

 Comprobación de redundancia cíclica (CRC).
Dado un bloque o mensaje de k bits, el transmisor genera una
secuencia de n bits, denominada secuencia de comprobación de
trama (FCS Frame Check Sequence), la trama resultante, de n +
k bits sea divisible por algún número predeterminado (patrón
de bits). El receptor dividirá la trama recibida por el mismo
patrón de bits y, si el resto en la división (resto 0), indica que la
transmisión ha sido correcta, sin error.
TÉCNICAS CORRECCIÓN
DE ERRORES

 Requerimiento automático de repetición (ARQ)
Pare y espere ( stop and wait ARQ ): Cuando el receptor recibe una
trama procede a validarla, si no contiene errores envía una señal de
confirmación hacia el emisor ACK (acknowledge). Si hay error envía
una señal de recepción errónea llamada NAK (negative
acknowledge).
Envío continuo ( Continuos ARQ ): Presenta el inconveniente de
reducir el tiempo de utilización efectiva de los canales de
comunicación dado que cada mensaje debe ser confirmado
individualmente y todo se paraliza hasta que ello ocurre.
TÉCNICAS CORRECCIÓN
DE ERRORES

 Corrección de errores hacia adelante (FEC)
Códigos de bloque: Un código de bloques convierte k bits de entrada
en n bits de salida con n>k, este es un código sin memoria.
Códigos de árbol: Un código de árbol es producido por un
codificador con memoria, a este grupo pertenecen los códigos
convolucionales, los cuales tienen como característica que a cada
bit de una secuencia se le aplica una operación binaria especifica.
Richard Wesley
Hamming

 Programó el computador que realizo los campos para la 1ra. Bomba
Atómica.
 1950 Trabajando en los laboratorios Bell junto a Shannon, desarrolló y
público la teoría de codificación.
 Fue el Precursor de los lenguajes de programación de alto nivel.
 Su descubrimiento fue uno de los más importantes en la ciencia de la
informática.
 Su método permite identificar un bit erróneo en una palabra
codificada (en binario). Esto es, si un bit es incorrecto, por ejemplo: el
cambio de un 1 por un 0 en una transmisión, podemos no solo detectar
el bit erróneo, sino además corregirlo.
CÓDIGO HAMING

 Es un código que se utiliza en la detección y corrección de errores que se
producen en la transmisión de códigos binarios, la palabra de código se
conforma por los bits de comprobación y los bits de información.
 Las distancia mínima de Haming está dada por la siguiente ecuación:
Dm= 2X+1
 Donde Dm es la distancia mínima de un código para permitir la corrección
de datos y X es las líneas de datos.
 n: número de bits del código original que se pretende transmitir.
 p: número de bits de paridad par generados en el transmisor, o sea,
número de líneas que añadimos al código inicial.
 c: número de bits detectores de paridad par generados por el receptor.
CÓDIGO HAMING

 Combinaciones posibles
 Orden para asignar combinaciones
 Combinación asignada a la situación en que no haya error en la
transmisión.
 Combinaciones asignadas a los bits de paridad generados en el transmisor.
 Combinaciones asignadas a los bits de datos del código original.
 Notación (k,n)
n = número de bits de información
h = número de bits de la cadena = 2c -1
La notación sería la siguiente (h,n)
CÓDIGO HAMING

 Combinaciones posibles
 Orden para asignar combinaciones
 Combinación asignada a la situación en que no haya error en la
transmisión.
 Combinaciones asignadas a los bits de paridad generados en el transmisor.
 Combinaciones asignadas a los bits de datos del código original.
 Notación (k,n)
n = número de bits de información
h = número de bits de la cadena = 2c -1
La notación sería la siguiente (h,n)
CÓDIGO HAMING
Combinacion # DE
es
"1"
#b
b0
0
0000
0
b1
1
0001
1
b2
b3
2
3
0010
0011
1
2
b4
b5
b6
b7
4
5
6
7
0100
0101
0110
0111
1
2
2
3
b8
b9
b10
8
9
10
1000
1001
1010
1
2
2
b11
b12
11
12
1011
1100
3
2
b13
13
1101
3
b14
14
1110
3
b15
15
1111
3
2
2^ 2^ ^
CORRESPONDE
3 2 1 2^0 NCIA
SITUACIÓN DE
0 0 0
0 NO ERROR
BIT DE PARIDAD
0 0 0
1 "1"
BIT DE PARIDAD
0 0 1
0 "2"
0 0 1
1 DATO 1
BIT DE PARIDAD
0 1 0
0 "3"
0 1 0
1 DATO2
0 1 1
0 DATO 3
0 1 1
1 DATO 4
BIT DE PARIDAD
1 0 0
0 "4"
1 0 0
1 DATO 5
1 0 1
0 DATO 6
NO SE USA EN EL
1 0 1
1 EJEMPLO
1 1 0
0 DATO 7
NO SE USA EN EL
1 1 0
1 EJEMPLO
NO SE USA EN EL
1 1 1
0 EJEMPLO
NO SE USA EN EL
1 1 1
1 EJEMPLO





Diseño de tabla para codificar datos de una
fuente ASCII de 7 bits.
Para la asignación de los eventos se realiza lo
siguiente:
Contar Número de unos en las combinaciones

Si el número de unos es cero es una situación de
no error y no se utiliza para enviar dato

Si el número de unos es 1, debemos empezar a
organizar los bits de paridad desde el primero
hasta el último y darles su respectiva asignación.

Si el número de unos es 2 en estos deben
colocarse para los datos, si las combinaciones de
2 unos no son suficientes para los datos
debemos empezar con los de 3 y luego los de 4
así sucesivamente, se prefiere que se coloquen
los datos primero en los grupos de 2.

Si no se tienen más datos esas líneas no son
válidas y se omiten en el sistema de verificación.
CÓDIGO HAMING

 Los bits de paridad b1, b2, b4, b8, no tienen un valor fijo este
valor se encuentra por las siguientes relaciones:




b1 = b3 ⊕ b5 ⊕ b7 ⊕ b9 ⊕ b11 ⊕ b13 ⊕ b15
b2 = b3 ⊕ b6 ⊕ b7 ⊕ b10 ⊕ b11 ⊕ b14 ⊕ b15
b4 = b5 ⊕ b6 ⊕ b7 ⊕ b12 ⊕ b13 ⊕ b14 ⊕ b15
b8 = b9 ⊕ b10 ⊕ b11 ⊕ b12 ⊕ b13 ⊕ b14 ⊕ b15
CÓDIGO HAMING
#b
b1
b2
b3
b4
b5
b6
b7
b8
b9
b1
b2
d1
b4
d2
d3
d4
b8
d5
b10
d6
2^3 2^2 2^1 2^0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
b13
1
1
0
b14
1
1
b15
1
1
b11
b12
d7

b8 b4 b2 b1
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
0
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
 Se obtienen los coeficientes
b1 , b2, b3, b4 de las
relaciones
anteriormente
descritas
CORRECCIÓN DE
ERRORES

DATOS TX
#b
b8
b4
b2
b1
b1
b2
b3
b4
b5
b6
b7
b8
b9
b1
b2
d1
b4
d2
d3
d4
b8
d5
0
0
1
0
0
0
1
1
0
0
b10
d6
0
0
0
0
0
b11
b12
d7
1
1
0
0
1
DATOS RX
b8
1
0
0
1
1
0
1
1
b13
0
0
b14
0
0
0
b15
0
1
0
0
0
0
b1
1
1
1
1
0
0
0
1
0
0
d6
0
0
0
0
0
d7
0
0
b2
b1
b2
d1
b4
d2
d3
d4
b8
d5
0
0
b4
1
1
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
SÍNDROME Y
CORRECCIÓN DE ERROR

 Como se observa en la recepción hay un valor
diferente de los datos transmitidos, si se realizan los
valores de b1, b2, b4, b8, son distintos en ambos
lados.
 Ahora debemos compararlo.
SÍNDROME Y
CORRECCIÓN DE ERROR

 Es un proceso donde se suman los valores de bits de
paridad encontrados en el receptor con los valores de
paridad envidados, se debe realizar una operación EXOR
uno a uno y el resultado que se obtiene es la ubicación
donde se encuentra el error.
Su formula es:
 Donde C son los bits de paridad de transmisión y envió.
SÍNDROME Y
CORRECCIÓN DE ERROR

1
1
1
1 bloque par recibido
1
0
0
0 bloque par enviado
0
1
1
1
2^3 2^2 2^1 2^0 #b dato dañado
7
 En el ejemplo es 0111 si
esto se pasa a decimal es
7 si vemos en la tabla del
ejemplo el dato que se
encuentra erróneo se
encuentra
en
la
combinación 7 la cual es
la asignada al dato 4.
 Por lo tanto se realiza el
cambio de signo de 0 a 1
DETECCIÓN Y EFICIENCIA
SOBRE CANAL

 Si m es igual a la distancia mínima de un código Haming
podemos determinar que el factor de detección y corrección de
un código depende de:
 Además si n = numero de bits de la cadena de salida
 k = numero de bits de información
 La eficiencia sobre el canal de transmisión será la siguiente:
n/k
 Con estos datos se puede obtener la siguiente tabla
DETECCIÓN Y EFICIENCIA
SOBRE CANAL

HAMING EXTENDIDO

 El Código Haming extendido se logra con dos
métodos:
 1 - Añadiendo un bit de paridad a cada palabra de
código
 2- Añadir una ecuación general de paridad
 Para ambos casos la distancia de Haming debe ser
mayor o igual a 4
 Se puede corregir errores simples y errores dobles.
CONCLUSIONES

 La integración de código redundante permite realizar la corrección
en cierta medida de los errores presentados en la transmisión; sin
embargo hace menos eficiente el proceso de codificación, por lo
cual se deberá lograr un equilibrio entre codificación redundante y
eficiente dadas las características del canal.
 Aunque los parámetros de los códigos AG son mejores que los
clásicos para códigos de longitud arbitrariamente grande, las
aplicaciones técnicas no se han visto aún en la necesidad práctica
de sustituir los códigos que actualmente se utilizan por otros de
mayor longitud sin que se dispare simultáneamente el coste y la
tasa de error.
CONCLUSIONES

 El Código Hamming, es un sistema de detección y corrección
automática de errores en información electrónica, el cual asocia
una serie de bits de validación o paridad a los bits de datos, de tal
forma que una alteración en cualquiera de esos bits de datos pueda
ser detectada y corregida adecuadamente.
 La distancia Hamming permite establecer el numero de bits
erróneos que pueden ser corregidos ó detectados mediante las
formulas:
Detección=(m-1)
Corrección=(m-1)/2
CONCLUSIONES

 El síndrome es una operación que relaciona los bits de paridad por
medio de una función EXOR bit a bit, si este resultado es 0 en cada
bit de paridad no indica que el paquete de datos llego sin errores
pero si nos indica un error o un 1 nos debe indicar el lugar donde
se presenta dicho problema.
 Para entender de una manera más sencilla la elaboración del
código se utilizaron tablas pero por lo general se utilizan matrices
y relaciones entre ellas para poder lograr relaciones cruzadas y
obtener los valores de bits de paridad.
 El sistema de códigos Haming es muy utilizado en elementos
como memorias y en comunicaciones en las tramas de Wifi.
BIBLIOGRAFÍA

 Comunicaciones y Redes de Procesamiento de Datos. Nestor Gonzáles
Sainz. Ed Mac Graw . 1987.
 Wikipedia.[online]. Algoritmos de Código de Redundancia Cíclica.
<http://es.wikipedia.org/wiki/Algoritmo_de_los_C%C3%B3digos_de_Re
dundancia_C%C3%ADclica>
 Tio
Petros.
[online].
Aritmética
Modular.
<http://tiopetrus.blogia.com/2005/060401-aritmetica-modular-4-.php>
 Códigos Detectores y Correctores de Errores. Códigos de Redundancia
Cíclica. < http://www.argo.es/~jcea/pics/artic/ecc-crc.htm>
 MODIANO, Eytan. [online]. La capa de enlace de Datos: Entramado y
Detección de Errores< http://mit.ocw.universia.net>.
 Demeter. Codificación de Señales. Ver. 1.1. 2 de Diciembre de 2003
 [email protected] Apuntes de IIC 3512 -- El nivel de enlace. Dic. 1996.
<http://www.cs.virginia.edu/~knabe/iic3512/apuntes_4.html>
 Códigos Lineales. http://jungla.dit.upm.es/~trdt/apuntes

GRACIAS
Descargar

código haming