Deteccion Y Correccion De Errores 3q2z4v

ALGORITMO DE CORRECCION Y DETECCION DE ERRORES INTRODUCCION La comunicación entre varias computadoras produce continuamente un movimiento de datos, generalmente por canales no diseñados para este propósito (línea telefónica), y que introducen un ruido externo que produce errores en la transmisión. Por lo tanto, debemos asegurarnos que si dicho movimiento causa errores, éstos puedan ser detectados. El método para detectar y corregir errores es incluir en los bloques de datos transmitidos bits adicionales denominados redundancia. Se han desarrollado dos estrategias básicas para manejar los errores: Incluir suficiente información redundante en cada bloque de datos para que se puedan detectar y corregir los bits erróneos. Se utilizan códigos de corrección de errores. Incluir sólo la información redundante necesaria en cada bloque de datos para detectar los errores. En este caso el número de bits de redundancia es menor. Se utilizan códigos de detección de errores. Si consideramos un bloque de datos formado por m bits de datos y r de redundancia, la longitud final del bloque será n, donde n = m + r.

TIPOS DE DETECTORES Paridad simple (paridad horizontal) Consiste en añadir un bit de más a la cadena que queremos enviar, y que nos indicará si el número de unos (bits puestos a 1) es par o es impar. Si es par incluiremos este bit con el valor = 0, y si no es así, lo incluiremos con valor = 1. Ejemplo de generación de un bit de paridad simple: Queremos enviar la cadena “1110100”: 1º Contamos la cantidad de unos que hay: 4 unos 2º El número de unos es par por tanto añadimos un bit con valor = 0 3º La cadena enviada es 1110100

El receptor ahora, repite la operación de contar la cantidad de “unos” que hay (menos el último bit) y si coincide, es que no ha habido error. Problemas de este método: Hay una alta probabilidad de que se cuelen casos en los que ha habido error, y que el error no sea detectado, como ocurre si se cambian dos números en la transmisión en vez de uno.

Paridad cruzada (paridad horizontal-vertical)

Para mejorar un poco el método anterior, se realiza una paridad que afecte tanto a los bits de cada cadena o palabra como a un conjunto de todos ellos. Siempre se utilizan cadenas relativamente cortas para evitar que se cuelen muchos errores. Para ver más claro este método, se suelen agrupar los bits en una matriz de N filas por K columnas, luego se realizan todas las paridades horizontales por el método anterior, y por último, se hace las misma operación de calcular el número de unos, pero ahora de cada columna. La probabilidad de encontrar un solo error es la misma, pero en cambio, la probabilidad de encontrar un número par errores ya no es cero, como en el caso anterior. Aun así, existen todavía una gran cantidad de errores no detectables Un ejemplo de paridad cruzada (o de código geométrico) 1º Tenemos este código para transmitir: 1100101111010110010111010110 2º Agrupamos el código en cada una de las palabras, formando una matriz de N x K: 1100101 1110101 1001011 1010110 3º Añadimos los bits de paridad horizontal: 1100101 1110101 1001011 1010110

0 1 0 0

4º Añadimos los bits de paridad vertical: 1100101 1110101 1001011 1010110

0 1 0 0

0001101 1

Una vez creada la matriz, podemos enviar ésta por filas, o por columnas. Enviando las palabras por columnas aumentamos la posibilidad de corregir una palabra que haya sufrido un error de ráfaga (errores que afectan a varios bits consecutivos, debidos a causas generalmente electrónicas, como chispazos, y que harían que se perdiera toda una palabra completa).

Códigos de redundancia cíclica también llamados CRC Intentando mejorar los códigos que sólo controlan la paridad de bit, aparecen los códigos cíclicos. Estos códigos utilizan la aritmética modular para detectar una mayor cantidad de errores, se usan operaciones en módulo 2 y las sumas y restas se realizan sin acarreo (convirtiéndose en operaciones de tipo Or-Exclusivo o XOR). Además, para facilitar los cálculos se trabaja, aunque sólo teóricamente, con polinomios. La finalidad de este método es crear una parte de redundancia la cual se añade al final del código a transmitir (como en los métodos de

paridad) que siendo la más pequeña posible, detecte el mayor número de errores que sea posible. Pero además de esto, debe ser un método sistemático, es decir, que con un mismo código a transmitir (y un mismo polinomio generador) se genere siempre el mismo código final. El polinomio generador: es un polinomio elegido previamente y que tiene como propiedad minimizar la redundancia. Suele tener una longitud de 16 bits, para mensajes de 128 bytes, lo que indica que la eficiencia es buena. Ya que sólo incrementa la longitud en un aproximado 1,6%. (16bits / (128bytes * 8bitsporbyte)) * 100 = 1,5625

Un ejemplo de polinomio generador redes WAN es: g(x) = x16 + x12 + x5 + 1

usado

normalmente

en

las

Los cálculos que realiza el equipo transmisor para calcular su CRC son: • • • • •

Añade tantos ceros por la derecha al mensaje original como el grado del polinomio generador Divide el mensaje con los ceros incluidos entre el polinomio generador El resto que se obtiene de la división se suma al mensaje con los ceros incluidos Se envía el resultado obtenido Estas operaciones generalmente son incorporadas en el hardware para que pueda ser calculado con mayor rapidez, pero en la teoría se utilizan los polinomios para facilitar los cálculos.

Ejemplo de obtención del CRC: Datos: Mensaje codificado en binario: 1101001 Polinomio generador: x4 + x + 1 Operaciones: 1º Obtener el polinomio equivalente al mensaje: x6 + x5 + x3 + 1 2º Multiplicar el x10 + x9 + x7 + x4

mensaje

por

x4

(añadir

4

ceros

por

la

derecha):

3º Dividir en binario el mensaje por el polinomio generador y sacar el resto: x2 + 1 4º Concatenar el mensaje x10 + x9 + x7 + x4 + x2 + 1

con

el

resto

(en

módulo

2

también):

5º Transmitir el mensaje

El equipo receptor debe comprobar el código CRC para detectar si se han producido o no errores. Ejemplo de los cálculos del receptor: 1º Mediante el protocolo correspondiente acuerdan el polinomio generador 2º Divide el código recibido entre el polinomio generador 3º Comprueba el resto de dicha operación

3.1 Si el resto es cero, no se han producido errores 3.2 Procesar el mensaje 3.1 Si el resto es distinto de cero, significa que se han producido errores 3.2 Reenviar el mensaje 3.2 Intentar corregir los errores mediante los códigos correctores

En resumen, este método requiere de un polinomio generador que, elegido correctamente, puede llegar a detectar gran cantidad de errores: • • • • •

Errores simples: todos Errores dobles: todos Errores en las posiciones impares de los bits: todos Errores en ráfagas con una longitud menor que el grado del polinomio generador: todos Otras ráfagas: un porcentaje elevado y cercano al 100%

Suma de comprobación Es un método sencillo pero eficiente sólo con cadenas de palabras de una longitud pequeña, es por esto que se suele utilizar en cabeceras de tramas importantes u otras cadenas importantes y en combinación con otros métodos. Funcionalidad: consiste en agrupar el mensaje a transmitir en cadenas de una longitud determinada L no muy grande, de por ejemplo 16 bits. Considerando a cada cadena como un número entero numerado según el sistema de numeración 2L − 1. A continuación se suma el valor de todas las palabras en las que se divide el mensaje, y se añade el resultado al mensaje a transmitir, pero cambiado de signo. Con esto, el receptor lo único que tiene que hacer es sumar todas las cadenas, y si el resultado es 0 no hay errores. Ejemplo: Mensaje 101001110101 1º Acordar la longitud de cada cadena: 3 2º Acordar el sistema de numeración: 23 − 1 = 7 3º Dividir el mensaje: 101 001 110 101 4º Asociar cada cadena con un entero: 5 1 6 5 5º Sumar todos los valores y añadir el número cambiado de signo: -17 6º Enviar 5 1 6 5 -17 codificado en binario El receptor: 1º Suma todos los valores; si la suma es 0, procesa el mensaje; si no, se ha producido un error.

Este método al ser más sencillo es óptimo para ser implementado en software ya que se puede alcanzar velocidades de cálculo similares a la implementación en hardware.

Distancia de Hamming basada en comprobación

Si queremos detectar d bit erróneos en una palabra de n bits, podemos añadir a cada palabra de n bits d+1 bits predeterminados al final, de forma que quede una palabra de n+d+1 bits con una distancia mínima de Hamming de d+1. De esta manera, si uno recibe una palabra de n+d+1 bits que no encaja con ninguna palabra del código (con una distancia de Hamming x <= d+1 la palabra no pertenece al código) detecta correctamente si es una palabra errónea. Aún más, d o menos errores nunca se convertirán en una palabra válida debido a que la distancia de Hamming entre cada palabra válida es de al menos d+1, y tales errores conducen solamente a las palabras inválidas que se detectan correctamente. Dado un conjunto de m*n bits, podemos detectar x <= d bits errores correctamente usando el mismo método en todas las palabras de n bits. De hecho, podemos detectar un máximo de m*d errores si todas las palabras de n bits son transmitidas con un máximo de d errores. Ejemplo Palabras a enviar: 000001 000001 000010 Codificadas con distancia mínima de Hamming = 2 000001 0000 000001 0011 000010 1100 Si las palabras recibidas tienen una distancia de Hamming < 2, son palabras incorrectas.

ALGORITMO DE CHECKSUM DE INTERNET La idea en la que se basa la suma de chequeo de Internet es muy sencilla: se suman todas las palabras de 16 bits que conforman el mensaje y se

transmite, junto con el mensaje, el resultado de dicha suma (este resultado recibe el nombre de checksum). Al llegar el mensaje a su destino, el receptor realiza el mismo cálculo sobre los datos recibidos y compara el resultado con el checksum recibido. Si cualquiera de los datos transmitidos, incluyendo el mismo checksum, esta corrupto, el resultado no concordará y el receptor sabrá que ha ocurrido un error. El checksum se realiza de la siguiente manera: los datos que serán procesados (el mensaje) son acomodados como una secuencias de enteros de 16 bits. Estos enteros se suman utilizando aritmética complemento a uno para 16 bits y, para generar el checksum, se toma el complemento a uno para 16 bits del resultado. En aritmética complemento a uno, un entero negativo -x se representa como el complemento de x; es decir, cada bit de x es invertido. Cuando los números se adicionan, si se obtiene un acarreo (carry) en el bit más significativo, se debe incrementar el resultado. Por ejemplo, sumemos -5 y -3 en aritmética complemento a uno con enteros de 4 bits. En este caso +5 se representaría con 0101 y -5 con 1010; +3 se representaría con 0011 y -3 con 1100. Al sumar 1010 y 1100, ignorando el acarreo (carry) que queda en el bit más significativo, tendremos como resultado 0110. En la aritmética complemento a uno, cuando una operación genera un acarreo (carry) en el bit más significativo, se debe incrementar el resultado; es decir que 0110 se convierte en 0111, que es la representación complemento a uno de -8 (obtenido de invertir los bits 1000). El uso del algoritmo de checksum de Internet en los headers de los protocolos se puede resumir en tres pasos simples. Los octetos adyacentes que se deben verificar con al suma de chequeo deben ser acomodados para formar enteros de 16 bits, luego se calcula la suma complemento a uno de estos enteros (de 16 bits) Para generar el checksum, el campo de checksum del header del PDU que será transmitido es puesto en cero, luego la suma complemento a uno es calculada sobre los octetos correspondientes y el complemento a uno de esta suma se coloca en el campo de checksum. Para revisar el checksum, la suma es calculada sobre los mismo octetos, incluyendo el campo de checsum. Si el resultado es 16 bits con valor 1 (-0 en aritmética complemento a uno), el chequeo es correcto. Como un ejemplo sencillo del cálculo del checksum supongamos que tenemos tres "palabras" de 16 bits 0110011001100110 0101010101010101 0000111100001111 La suma de las dos primeras palabras sería: 0110011001100110 0101010101010101 1011101110111011

Adicionando ahora la tercera "palabra" al resultado anterior tenemos 1011101110111011 0000111100001111 1100101011001010 La suma complemento a uno se obtiene convirtiendo todos los ceros en unos y todos los unos en ceros. De esta forma la suma complemento a uno de 1100101011001010 sería 0011010100110101. Que vendría a ser el checksum. Al llegar al receptor las cuatro palabra de 16 bits, incluyendo el checksum son sumados y el resultado debe ser 1111111111111111. Si uno de los bits es cero, un error ha sido detectado. Dependiendo del protocolo, se deben seleccionar ciertos campos de los headers para realizar los cálculos del checksum. En IP el checksum se calcula sólo sobre los octetos que componen el header del datagrama (RFC791), en UDP (RFC768) se calcula sobre un seudo-header , el header UDP y los datos que transporta UDP y en T (RFC793) se hace un cálculo similar que en UDP. Si desea conocer los detalles del cáculo del checksum puede ver los siguientes ejemplos. Cálculo del campo de checksum en el header de IP Cálculo del campo de checksum en el header de UDP Cálculo del campo de checksum en el header de T El RFC1071, Computing the Internet Checksum, discute métodos para calcular de manera eficiente el checksum de Internet que se utiliza en los protocolos IP, UDP y T. La siguiente rutina es una implementación directa del algoritmo de checksum de Internet. El argumento cantidad trae la longitud del buffer medido en unidades de 16 bits. La rutina asume que buffer ha sido rellenado de ceros (0) para que se ajuste a un tamaño múltiplo de 16 bits. u_short checksum (u_short *buffer, int cantidad) { u_long suma = 0; while (cantidad--) { suma += *buffer++; if (suma & 0xFFFF0000) { /* hubo acarreo, se debe incrementar el resultado */ suma &= 0xFFFF; suma++; } } return ~(suma & 0xFFFF); }

Este código asegura que el cálculo utiliza aritmética complemento a uno, antes que aritmética complemento a dos que es la utilizada por la mayoría de máquinas. Observe el if dentro del ciclo while. Si existe un acarreo (carry) al final de la suma de 16 bits, entonces se incrementa suma.

Al utilizar este checksum, se agregan 16 bits al mensaje original como código de detección de errores, pero esta no es una técnica fuerte de detección de errores. ¿por qué? Por ejemplo, si una pareja de bits individuales, uno de los cuales incrementa una palabra de 16 bits, de las que conforman el mensaje, en cierta cantidad y el otro bit decrementa otra palabra de 16 bits en la misma cantidad, al realizar la suma de chequeo no será detectado el error. La razón por la cual un algoritmo como éste es utilizado, aunque tenga una protección débil contra errores, es simple: este algoritmo es fácil de implementar en software (el algoritmo de CRC utilizado en los protocolos de la capa de enlace, como Ethernet y Token Ring se implementan en el hardware de las tarjetas de red). Además la experiencia observada en ARPANET sugirió que un checksum era adecuado: este checksum es la última línea de defensa en los protocolos de T/IP pues la gran mayoría de errores son descubiertos por algoritmos de detección de errores más fuertes, tales como los CRCs utilizados en la capa de enlace (capa 2 del modelo OSI).

VITERBI DECODIFICADOR El algoritmo de Viterbi es una programación dinámica algoritmo para encontrar la más probable secuencia de estados ocultos - llamada la ruta de Viterbi - que se traduce en una secuencia de eventos observados, especialmente en el contexto de las fuentes de información de Markov , y, en general, los modelos ocultos de Markov . El algoritmo de avance es un algoritmo estrechamente relacionados para calcular la probabilidad de una secuencia de hechos observados. Estos algoritmos pertenecen al reino de la teoría de la probabilidad . El algoritmo realiza una serie de supuestos: 

En primer lugar, tanto en los hechos observados y los eventos ocultos debe estar en una secuencia. La secuencia es a menudo temporal, es decir, para el momento del suceso.



En segundo lugar, estas dos secuencias deben ser alineados: un ejemplo de un hecho observado debe corresponder exactamente a una instancia de un evento oculto.



En tercer lugar, la computación en la secuencia oculta más probable (que conduce a un estado en particular), hasta un cierto punto t debe depender sólo en el caso observado en el punto t , y la secuencia más probable es que conduce a ese estado en el punto t - 1.

Estos supuestos se satisfacen en un modelo oculto de Markov de primer orden. Los términos "camino Viterbi" y "algoritmo de Viterbi" se aplican también a los relacionados con algoritmos de programación dinámica que descubre la explicación más probable para una observación. Por ejemplo, en el análisis estadístico de un algoritmo de programación dinámica se puede utilizar para descubrir el contexto único sin más probable derivación (análisis) de una cadena, que es a veces llamado el "Viterbi analizar". El algoritmo de Viterbi fue concebido por Andrew Viterbi en 1967 como un algoritmo de decodificación de códigos convolucionales más ruidosos los

enlaces de comunicación digital.Para más detalles sobre la historia de la evolución del algoritmo ver David Forney artículo 's. [ 1 ] El algoritmo ha encontrado una aplicación universal en la descodificación de los códigos convolucionales utilizados tanto en CDMA y GSM celular digital, dialup módems, satélites, en el fondo -espacio de las comunicaciones, y 802.11 LAN inalámbricas. Ahora es también de uso general en el reconocimiento de voz , detección de palabras clave , la lingüística computacional y bioinformática . Por ejemplo, en la voz a texto (reconocimiento de voz), la señal acústica se considera como la secuencia de los eventos observados, y una cadena de texto es considerado como la "causa oculta" de la señal acústica. El algoritmo de Viterbi encuentra la cadena más probable del texto dado la señal acústica.

Información general Los supuestos enumerados anteriormente pueden ser elaborados de la siguiente manera. El algoritmo de Viterbi opera en una máquina de estados suposición. Es decir, en cualquier momento el sistema que se modela está en uno de un número finito de estados. Mientras que varias secuencias de estados (caminos) puede conducir a un estado determinado, por lo menos uno de ellos es un camino más probable para ese estado, llamada la "ruta de los sobrevivientes". Esta es una premisa fundamental del algoritmo porque el algoritmo examina todos los posibles caminos que conducen a un estado y sólo mantener la más probable. De esta manera el algoritmo no tiene que realizar un seguimiento de todos los caminos posibles, sólo uno por estado. Un segundo supuesto fundamental es que una transición de un estado anterior a un nuevo estado se caracteriza por un incremento métricas, por lo general un número. Esta transición se calcula a partir del evento. El supuesto de tercera clave es que los sucesos se acumulan más de un camino en cierto sentido, habitualmente adicional. Así que el quid del algoritmo es mantener un número para cada estado. Cuando ocurre un evento, el algoritmo analiza avanzar hacia un nuevo conjunto de estados mediante la combinación de la métrica de un estado anterior es posible con la métrica incrementales de la transición, debido al evento y elige lo mejor. La métrica incremental asociado a un evento depende de la posibilidad de transición desde el estado anterior al nuevo Estado. Por ejemplo, en comunicaciones de datos, es posible que sólo transmiten la mitad de los símbolos de un estado con números impares y la otra mitad de un estado de pares. Además, en muchos casos, el gráfico de transición de estado no está totalmente conectado. Un ejemplo sencillo es un coche que tiene tres estados - adelante, detener y revertir - y no se le permite experimentar una transición de avance a retroceso sin entrar en el estado de parada. Después de calcular las combinaciones de métricas adicionales y el estado métricas, sólo los mejores sobreviven y todos los otros caminos se descartan. Hay modificaciones en el algoritmo básico que permiten una búsqueda hacia adelante, además de la una hacia atrás se describe aquí.

La historia de ruta debe ser almacenada. En algunos casos, el historial de búsqueda es completa, porque la máquina del Estado en el codificador se inicia en un estado conocido y no hay memoria suficiente para guardar todos los caminos. En otros casos, una solución de programación debe ser encontrado por los recursos limitados: un ejemplo es la codificación convolucional, donde el decodificador debe truncar la historia, a una profundidad suficiente para mantener el rendimiento a un nivel aceptable. Aunque el algoritmo de Viterbi es muy eficiente y hay modificaciones que reducen la carga computacional, los requisitos de memoria tienden a permanecer constantes.

Algoritmo Supongamos que tenemos un modelo oculto de Markov (HMM) con los estados Y , las probabilidades iniciales π i de estar en el estado i , y las probabilidades de transición una i , j de la transición del estado i al estado j . Decir que observamos las salidas . La secuencia de estados más probable que han producido las observaciones está dado por las relaciones de recurrencia:

Aquí V t , k es la probabilidad de la secuencia de estado más probable responsable de la primera t + 1 observaciones (se añade una indexación, ya comenzó a 0) que tiene k como su estado final. El camino Viterbi puede ser recuperada por el ahorro punteros que recordar que el estado y se utilizó en la segunda ecuación. Vamos Ptr ( k , t ) es la función que devuelve el valor de y utiliza para calcular V t , k si t > 0 , o k si t = 0 . Entonces:

La complejidad de este algoritmo es

.

BIBLIOGRAFIA http://webcache.googlecontent.com/search? q=cache:NZFj0TDPLd4J:es.wikipedia.org/wiki/Correcci %C3%B3n_de_errores_hacia_adelante+algoritmo+de+correcion+de+datos &cd=2&hl=es&ct=clnk&gl=pe http://es.wikipedia.org/wiki/Detecci%C3%B3n_y_correcci %C3%B3n_de_errores http://www.arcesio.net/checksum/checksuminternet.html http://en.wikipedia.org/wiki/Viterbi_decoder http://en.wikipedia.org/wiki/Viterbi_algorithm