Codigo hamming
-
Upload
alvaro-humberto-cisneros -
Category
Documents
-
view
1.790 -
download
2
Transcript of Codigo hamming
![Page 1: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/1.jpg)
Universidad Distrital, Maestría en Teleinformática,
Bogotá D.C., Colombia.
Mayo de 2012
![Page 2: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/2.jpg)
ALVARO HUMBERTO CISNEROS
DANIEL SEPULVEDA NUÑEZ
INTEGRANTES
![Page 3: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/3.jpg)
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
CONTENIDO
![Page 4: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/4.jpg)
Cuando se transmite información, se corre el riesgo de la presenciade interferencia o ruido.
El origen de la teoría de códigos correctores de errores se encuentraen 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 loscódigos de Reed-Solomon y de Reed-Muller].
HISTORIA
![Page 5: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/5.jpg)
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ácticadebido a la profundidad matemática de las ideas subyacentes.
Los métodos de decodificación para códigos geométricos deGoppa son efectivos, su preprocesamiento es de una elevadadificultad e involucra complejos algoritmos basados en métodosde la geometría algebraica computacional.
HISTORIA
![Page 6: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/6.jpg)
Códigos VRC (Vertical Redundancy Check).
En esta técnica, un bit redundante, denominado bit de paridad, seañ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 undeterminado número de unidades de datos en un bloque, cada unocon su bit VRC correspondiente. Se calcula el bit de paridad entrecada bit de todas y cada una de las unidades de datos (primerosbits, segundos, etc.). Se reúnen los bits de paridad de todas lasposiciones en una nueva unidad de datos y se añade al final delbloque.
TÉCNICAS DE DETECCIÓN DE ERRORES
![Page 7: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/7.jpg)
Comprobación de redundancia cíclica (CRC).
Dado un bloque o mensaje de k bits, el transmisor genera unasecuencia de n bits, denominada secuencia de comprobación detrama (FCS Frame Check Sequence), la trama resultante, de n +k bits sea divisible por algún número predeterminado (patrónde bits). El receptor dividirá la trama recibida por el mismopatrón de bits y, si el resto en la división (resto 0), indica que latransmisión ha sido correcta, sin error.
TÉCNICAS DE DETECCIÓN DE ERRORES
![Page 8: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/8.jpg)
Requerimiento automático de repetición (ARQ)
Pare y espere ( stop and wait ARQ ): Cuando el receptor recibe unatrama procede a validarla, si no contiene errores envía una señal deconfirmación hacia el emisor ACK (acknowledge). Si hay error envíauna señal de recepción errónea llamada NAK (negativeacknowledge).
Envío continuo ( Continuos ARQ ): Presenta el inconveniente dereducir el tiempo de utilización efectiva de los canales decomunicación dado que cada mensaje debe ser confirmadoindividualmente y todo se paraliza hasta que ello ocurre.
TÉCNICAS CORRECCIÓN DE ERRORES
![Page 9: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/9.jpg)
Corrección de errores hacia adelante (FEC)
Códigos de bloque: Un código de bloques convierte k bits de entradaen 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 uncodificador con memoria, a este grupo pertenecen los códigosconvolucionales, los cuales tienen como característica que a cadabit de una secuencia se le aplica una operación binaria especifica.
TÉCNICAS CORRECCIÓN DE ERRORES
![Page 10: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/10.jpg)
Richard WesleyHamming
Programó el computador que realizo los campos para la 1ra. BombaAtómica.
1950 Trabajando en los laboratorios Bell junto a Shannon, desarrolló ypú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 lainformática.
Su método permite identificar un bit erróneo en una palabracodificada (en binario). Esto es, si un bit es incorrecto, por ejemplo: elcambio de un 1 por un 0 en una transmisión, podemos no solo detectar
el bit erróneo, sino además corregirlo.
![Page 11: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/11.jpg)
CÓDIGO HAMING
Es un código que se utiliza en la detección y corrección de errores que seproducen en la transmisión de códigos binarios, la palabra de código seconforma 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ónde 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.
![Page 12: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/12.jpg)
CÓDIGO HAMING
Combinaciones posibles
Orden para asignar combinaciones
Combinación asignada a la situación en que no haya error en latransmisió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ónh = número de bits de la cadena = 2c -1La notación sería la siguiente (h,n)
![Page 13: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/13.jpg)
CÓDIGO HAMING
Combinaciones posibles
Orden para asignar combinaciones
Combinación asignada a la situación en que no haya error en latransmisió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ónh = número de bits de la cadena = 2c -1La notación sería la siguiente (h,n)
![Page 14: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/14.jpg)
CÓDIGO HAMING
Diseño de tabla para codificar datos de unafuente ASCII de 7 bits.
Para la asignación de los eventos se realiza losiguiente:
Contar Número de unos en las combinaciones
Si el número de unos es cero es una situación deno error y no se utiliza para enviar dato
Si el número de unos es 1, debemos empezar aorganizar los bits de paridad desde el primerohasta el último y darles su respectiva asignación.
Si el número de unos es 2 en estos debencolocarse para los datos, si las combinaciones de2 unos no son suficientes para los datosdebemos empezar con los de 3 y luego los de 4así sucesivamente, se prefiere que se coloquenlos datos primero en los grupos de 2.
Si no se tienen más datos esas líneas no sonválidas y se omiten en el sistema de verificación.
# b
Combinacion
es
# DE
"1"
2^
3
2^
2
2
^
1 2^0
CORRESPONDE
NCIA
b0 0 0000 0 0 0 0 0
SITUACIÓN DE
NO ERROR
b1 1 0001 1 0 0 0 1
BIT DE PARIDAD
"1"
b2 2 0010 1 0 0 1 0
BIT DE PARIDAD
"2"
b3 3 0011 2 0 0 1 1 DATO 1
b4 4 0100 1 0 1 0 0
BIT DE PARIDAD
"3"
b5 5 0101 2 0 1 0 1 DATO2
b6 6 0110 2 0 1 1 0 DATO 3
b7 7 0111 3 0 1 1 1 DATO 4
b8 8 1000 1 1 0 0 0
BIT DE PARIDAD
"4"
b9 9 1001 2 1 0 0 1 DATO 5
b10 10 1010 2 1 0 1 0 DATO 6
b11 11 1011 3 1 0 1 1
NO SE USA EN EL
EJEMPLO
b12 12 1100 2 1 1 0 0 DATO 7
b13 13 1101 3 1 1 0 1
NO SE USA EN EL
EJEMPLO
b14 14 1110 3 1 1 1 0
NO SE USA EN EL
EJEMPLO
b15 15 1111 3 1 1 1 1
NO SE USA EN EL
EJEMPLO
![Page 15: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/15.jpg)
CÓDIGO HAMING
Los bits de paridad b1, b2, b4, b8, no tienen un valor fijo estevalor 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
![Page 16: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/16.jpg)
CÓDIGO HAMING
Se obtienen los coeficientesb1 , b2, b3, b4 de lasrelaciones anteriormentedescritas
# b 2^3 2^2 2^1 2^0 b8 b4 b2 b1
b1 b1 0 0 0 1 0
b2 b2 0 0 1 0 0
b3 d1 0 0 1 1 1 1 1
b4 b4 0 1 0 0 0
b5 d2 0 1 0 1 0 0 0
b6 d3 0 1 1 0 0 0 0
b7 d4 0 1 1 1 1 1 1 1
b8 b8 1 0 0 0 1
b9 d5 1 0 0 1 0 0 0
b10 d6 1 0 1 0 0 0 0
b11 1 0 1 1 0 0 0
b12 d7 1 1 0 0 1 1 1
b13 1 1 0 1 0 0 0
b14 1 1 1 0 0 0 0
b15 1 1 1 1 0 0 0 0
1 0 0 0
![Page 17: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/17.jpg)
CORRECCIÓN DE ERRORES
DATOS TX DATOS RX
# b b8 b4 b2 b1 b8 b4 b2 b1
b1 b1 0 b1 1
b2 b2 0 b2 1
b3 d1 1 1 1 d1 1 1 1
b4 b4 0 b4 1
b5 d2 0 0 0 d2 0 0 0
b6 d3 0 0 0 d3 0 0 0
b7 d4 1 1 1 1 d4 0 0 0 0
b8 b8 1 b8 1
b9 d5 0 0 0 d5 0 0 0
b10 d6 0 0 0 d6 0 0 0
b11 0 0 0 0 0 0
b12 d7 1 1 1 d7 1 1 1
b13 0 0 0 0 0 0
b14 0 0 0 0 0 0
b15 0 0 0 0 0 0 0 0
1 0 0 0 1 1 1 1
![Page 18: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/18.jpg)
Como se observa en la recepción hay un valor
diferente de los datos transmitidos, si se realizan losvalores de b1, b2, b4, b8, son distintos en amboslados.
Ahora debemos compararlo.
SÍNDROME Y CORRECCIÓN DE ERROR
![Page 19: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/19.jpg)
Es un proceso donde se suman los valores de bits de
paridad encontrados en el receptor con los valores deparidad envidados, se debe realizar una operación EXORuno a uno y el resultado que se obtiene es la ubicacióndonde 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
![Page 20: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/20.jpg)
En el ejemplo es 0111 si
esto se pasa a decimal es7 si vemos en la tabla delejemplo el dato que seencuentra erróneo seencuentra en lacombinación 7 la cual esla asignada al dato 4.
Por lo tanto se realiza elcambio de signo de 0 a 1
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 7
2^3 2^2 2^1 2^0 #b dato dañado
![Page 21: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/21.jpg)
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 deun 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
![Page 22: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/22.jpg)
DETECCIÓN Y EFICIENCIA SOBRE CANAL
![Page 23: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/23.jpg)
El Código Haming extendido se logra con dos
métodos:
1 - Añadiendo un bit de paridad a cada palabra decódigo
2- Añadir una ecuación general de paridad
Para ambos casos la distancia de Haming debe sermayor o igual a 4
Se puede corregir errores simples y errores dobles.
HAMING EXTENDIDO
![Page 24: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/24.jpg)
CONCLUSIONES
La integración de código redundante permite realizar la correcciónen cierta medida de los errores presentados en la transmisión; sinembargo hace menos eficiente el proceso de codificación, por locual se deberá lograr un equilibrio entre codificación redundante yeficiente dadas las características del canal.
Aunque los parámetros de los códigos AG son mejores que losclásicos para códigos de longitud arbitrariamente grande, lasaplicaciones técnicas no se han visto aún en la necesidad prácticade sustituir los códigos que actualmente se utilizan por otros demayor longitud sin que se dispare simultáneamente el coste y latasa de error.
![Page 25: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/25.jpg)
CONCLUSIONES
El Código Hamming, es un sistema de detección y correcciónautomática de errores en información electrónica, el cual asociauna serie de bits de validación o paridad a los bits de datos, de talforma que una alteración en cualquiera de esos bits de datos puedaser detectada y corregida adecuadamente.
La distancia Hamming permite establecer el numero de bitserróneos que pueden ser corregidos ó detectados mediante lasformulas:
Detección=(m-1)Corrección=(m-1)/2
![Page 26: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/26.jpg)
CONCLUSIONES
El síndrome es una operación que relaciona los bits de paridad pormedio de una función EXOR bit a bit, si este resultado es 0 en cadabit de paridad no indica que el paquete de datos llego sin errorespero si nos indica un error o un 1 nos debe indicar el lugar dondese presenta dicho problema.
Para entender de una manera más sencilla la elaboración delcódigo se utilizaron tablas pero por lo general se utilizan matricesy relaciones entre ellas para poder lograr relaciones cruzadas yobtener los valores de bits de paridad.
El sistema de códigos Haming es muy utilizado en elementoscomo memorias y en comunicaciones en las tramas de Wifi.
![Page 27: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/27.jpg)
Comunicaciones y Redes de Procesamiento de Datos. Nestor GonzálesSainz. 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_Redundancia_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 RedundanciaCíclica. < http://www.argo.es/~jcea/pics/artic/ecc-crc.htm>
MODIANO, Eytan. [online]. La capa de enlace de Datos: Entramado yDetecció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
BIBLIOGRAFÍA
![Page 28: Codigo hamming](https://reader034.fdocumento.com/reader034/viewer/2022042514/559752941a28abe75b8b4668/html5/thumbnails/28.jpg)
GRACIAS