Codigos Para Correccion De Errores 4y373x

UNIVERSIDAD NACIONAL DE SAN ANTONIO ABAD DEL CUSCO FACULTAD DE INGENIERÍA: ELÉCTRICA, ELECTRÓNICA, MECÁNICA Y MINAS

CARRERA PROFESIONAL DE INGENIERÍA CODIGOS PARA DETECCIÓN Y CORRECCIÓN DE ERRORES (Sistemas Digitales) ELÉCTRICA TEMA:

Curso: Sistemas Digitales I Docente: Ing. Edgar Z. Alarcón Valdivia Alumno: Abel Edwin Ccoyccosi Chura Código: 121280 Semestre: 2015-I Fecha: Cusco, 20 de mayo del 2015

CUSCO-PERU 2015

PRESENTACIÓN El presente trabajo es una compilación de información principalmente teórico del tema: “Códigos para Detección y Corrección de Errores” en que son de mucha importancia y de mucha aplicación hoy en día en muchos sistemas digitales. Además en este trabajo de obtención de nuevos conocimientos, aparte de lo estudiado en clase es una importante acotación para poder comprender mejor este tema tan importante. Finalmente espero cumplir con lo requerido para este fin.

Atentamente: Abel Edwin

Detección y corrección de errores En matemáticas, computación y teoría de la información, la detección y corrección de errores es una importante práctica para el mantenimiento e integridad de los datos a través de diferentes procedimientos y dispositivos como medios de almacenamiento confiables. 1 Se considera como precursor de este tipo de tecnologías el Acme Comodity and Phrase Code usado en los telegramas.

Introducción 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. Tipo de códigos 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 11101000 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. Un ejemplo de polinomio generador usado normalmente en las redes WAN es:

Los cálculos que realiza el equipo transmisor para calcular su CRC son: 1. Añade tantos ceros por la derecha al mensaje original como el grado del polinomio generador 2. Divide el mensaje con los ceros incluidos entre el polinomio generador 3. El resto que se obtiene de la división se suma al mensaje con los ceros incluidos 4. 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: Operaciones: 1º Obtener el polinomio equivalente al mensaje: 2º Multiplicar el mensaje por

(añadir 4 ceros por la derecha):

3º Dividir en binario el mensaje por el polinomio generador y sacar el resto: 4º Concatenar el mensaje 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 .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: 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

Hipercubo binario de dimensión cuatro. 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: 1. 000001 2. 000001 3. 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.

Lista de los métodos de corrección y detección de errores  Dígito verificador  FEC (Forward Error Correction)  Código Binario de Golay  Código Hamming

 Bit de paridad  Reed-Solomon

Código de control El código de control es un mecanismo de detección de errores utilizado para verificar la corrección de un dato, generalmente en soporte informático. Los dígitos de control se usan principalmente para detectar errores en el tecleo o transmisión de los datos. Generalmente consisten en uno o más caracteres numéricos o alfabéticos añadidos al dato original y calculados a partir de éste, mediante un determinado algoritmo. Algunos de los ejemplos de uso frecuentes son los números de identificación personal, códigos de barras, tarjetas de crédito y códigos bancarios.

Denominación No existe unanimidad en la denominación de esta técnica en el mundo hispanoparlante. La traducción directa del inglés check digit sería dígito de chequeo, de verificación o de control. Estas denominaciones solamente son aplicables cuando se trata, efectivamente, de uno o varios dígitos y no de otros caracteres. Más correctas son las variantes carácter de chequeo, de verificación o de control, aunque ésta última tiene otro significado específico en el contexto de la informática. También son aplicables código de control (la forma más usada de entre las correctas), de chequeo o de verificación, aunque esta última expresión se refiere casi siempre a técnicas para filtrar el a páginas web, como los captcha.

Utilización Es utilizado normalmente en representaciones numéricas que exijan integridad, como por ejemplo: 

Documentos de identificación: Algunos documentos de identificación como la cédula de identidad o el DNI dependiendo del país.



Códigos de pagos: Número de factura, número de identificación tributaria, etc.



Códigos en general: Cuenta bancaria, cuenta corriente, número de matrícula, código de barras, ISBN, etc.

Cálculo del dígito verificador El método de cálculo de esos dígitos varía conforme el caso. Sin embargo, muchos de ellos se basan en dos rutinas tradicionales: Módulo 11 y Módulo 10.

Módulo 11 El método denominado módulo 11 detecta errores en un solo dígito e intercambios simples o dobles. Se basa en aplicar un factor de chequeo ponderado a cada dígito del número original. El cálculo se realiza como sigue: [1]

1. A cada dígito del número base se le asigna un factor de chequeo ponderado. Dicho factor será 2 para el dígito menos significativo (el que está más a la derecha) y, en orden, 3, 4, 5, 6, 7 para los siguientes. Si hubiera más de 6 dígitos la secuencia se repetiría de modo que el séptimo dígito se multiplicaría por 2, el octavo por 3, etc. 2. Cada dígito del número base se multiplica por el factor de chequeo asignado. 3. Se suman los resultados de todas las multiplicaciones. 4. Al resultado de la suma se le calcula el módulo 11 (de ahí el nombre del método), es decir, el resto de la división entera entre 11. 5. A 11 se le resta el módulo calculado en el punto anterior. Si el resultado de la resta es < 10, dicho resultado es el dígito de control que buscábamos. Si el resultado es 11 el dígito de control es 0 y si el resultado es 10 el dígito de control resultante es 1.

El siguiente esquema desarrolla un ejemplo de cálculo: Número ejemplo: 41261533-? Pasos 1 y 2 +---+---+---+---+---+---+---+---+ +---+ |4|1|2|6|1|5|3|3|-|?| +---+---+---+---+---+---+---+---+ +---+ | | | | | | | | x3 x2 x7 x6 x5 x4 x3 x2 | | | | | | | | =12 =2 =14 =36 =5 =20 =9 =6 Paso 3 12 +2 +14 +36 +5 +20 +9 +6 = 104 Paso 4 104 mod 11 = 5

(ya que 104 = 11 x 9 + 5)

Paso 5 11 - 5 = 6 Resultado = 41261533-6 A veces se usan variantes, como sustituir el resultado por una letra cuando el resultado es 10. Por ejemplo, en Chile el Rol Único Nacional (RUN) y el Rol Único Tributario (RUT) utilizan este sistema y cuando el resultado del algoritmo es 10 el carácter de control es la letra "K".

Módulo 10 Conforme al esquema de abajo, cada dígito del número, comenzando de la derecha para la izquierda (menos significativo para el más significativo) es multiplicado, en orden, por 2, después 1, después 2, después 1 y así sucesivamente. Número ejemplo: 261533-4 +---+---+---+---+---+---+ +---+ |2|6|1|5|3|3|-|4| +---+---+---+---+---+---+ +---+ | | | | | | x1 x2 x1 x2 x1 x2 | | | | | | =2 =12 =1 =10 =3 =6 +---+---+---+---+---+-> = (16 / 10) = 1, resto 6 => DV = (10 - 6) = 4

En vez de ser hecha la sumatoria de las multiplicaciones, será hecha la sumatoria de los dígitos de las multiplicaciones (si una multiplicación da 12, por ejemplo, será sumado 1 + 2 = 3). La sumatoria será dividida por 10 y si el resto (módulo 10) es diferente de cero, el dígito será 10 menos este valor. En caso que el resto sea cero, ese será el dígito verificador. Estas condiciones finales, sin embargo, podrán ser alteradas conforme el caso.

Corrección de errores hacia adelante La corrección de errores hacia adelante (en inglés, Forward Error Correction o FEC) es un tipo de mecanismo de corrección de errores que permite su corrección en el receptor sin retransmisión de la información original. Se utiliza en sistemas sin retorno o sistemas en tiempo real donde no se puede esperar a la retransmisión para mostrar los datos. Este mecanismo de corrección de errores se utiliza por ejemplo, en las comunicaciones vía satélite, en las grabadoras de DVD y CD o en las emisiones de TDT para terminales móviles (estándar DVB-H), concretamente en este último caso se trata de un tipo especial de FEC, el denominado MPE-FEC. Funcionamiento La posibilidad de corregir errores se consigue añadiendo al mensaje original unos bits de redundancia. La fuente digital envía la secuencia de datos al codificador, encargado de añadir dichos bits de redundancia. A la salida del codificador obtenemos la denominada palabra código. Esta palabra código es enviada al receptor y éste, mediante el decodificador adecuado y aplicando los algoritmos de corrección de errores, obtendrá la secuencia de datos original. Los dos principales tipos de codificación usados son: 

Códigos bloque. La paridad en el codificador se introduce mediante un algoritmo algebraico aplicado a un bloque de bits. El decodificador aplica el algoritmo inverso para poder identificar y, posteriormente corregir los errores introducidos en la transmisión.



Códigos convolucionales. Los bits se van codificando tal y como van llegando al codificador. Cabe destacar que la codificación de uno de los bits está enormemente influenciada por la de sus predecesores. La decodificación para este tipo de código es compleja ya que en principio, es necesaria una gran cantidad de memoria para estimar la secuencia de datos más probable para los bits recibidos. En la actualidad se utiliza para decodificar este tipo de códigos algoritmo de Viterbi, por su gran eficiencia en el consumo de recursos.

Ventajas FEC reduce el número de transmisiones de errores, así como los requisitos de potencia de los sistemas de comunicación e incrementa la efectividad de los mismos evitando la necesidad del reenvío de los mensajes dañados durante la transmisión. Compromisos En general incluir un número mayor de bits de redundancia supone una mayor capacidad para corregir errores. Sin embargo, este hecho reduce notablemente el régimen binario de transmisión, y aumenta el retardo en la recepción del mensaje.

Código Hamming En informática, el código de Hamming es un código detector y corrector de errores que lleva el nombre de su inventor, Richard Hamming. En los datos codificados en Hamming se pueden detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores de dos bits y de un bit (para lo que se usa Hamming extendido). Esto representa una mejora respecto a los códigos con bit de paridad, que pueden detectar errores en sólo un bit, pero no pueden corregirlo.

Códigos pre-Hamming Antes de los códigos Hamming se utilizaron ciertos códigos detectores de error, como lo fueron el código linteing, pero ninguno llegó a ser tan eficaz como los de Hamming. A continuación se describen algunos de estos códigos.

Paridad La paridad consiste en añadir un bit, denominado bit de paridad, que indique si el número de los bits de valor 1 en los datos precedentes es par o impar. Si un solo bit cambiara por error en la transmisión, el mensaje cambiará de paridad y el error se puede detectar (nótese que el bit donde se produzca el error puede ser el mismo bit de paridad). La convención más común es que un valor de paridad 1 indica que hay un número impar de unos en los datos, y un valor de paridad de 0 indica que hay un número par de unos en los datos. La comprobación de paridad no es muy robusta, dado que si cambia de forma uniforme un número par de bits, el bit de paridad será válido y el error no será detectado. Se utiliza cuando se cumplen simultáneamente dos condiciones: que la probabilidad de que falle un bit es baja y que las fallas de bits son sucesos independientes. De esta forma la probabilidad de que fallen dos (o más) bits es muy baja, por lo que cuando no detecta error es altamente probable que el código sea efectivamente correcto. Cabe destacar que dichas condiciones se ajustan al caso de las memorias de las computadoras modernas pero no ocurre lo mismo con los dispositivos de almacenamiento que guardan la información en forma serial (un bit a continuación de otro) ni con los sistemas de transmisión de datos seriales ya que en estos casos el hecho que falle un bit está vinculado, en forma no despreciable, a la falla de otro adyacente. Por otro lado, la paridad, aunque puede detectar que hay error, no indica en qué bit se cometió. Los datos se deben desechar por entero y volverse a transmitir. En un medio ruidoso, una transmisión correcta podría tardar mucho tiempo o incluso, en el peor de los casos, no darse nunca. El chequeo de paridad, aunque no es muy bueno, usa un único bit, por lo que produce muy poca sobrecarga, y además permite la corrección de ese bit si es conocida su posición.

Dos entre cinco En los años 40, Bell utilizó un código algo más sofisticado conocido como dos-entrecinco. Este código se basa en que cada bloque de cinco bits (conocido como penta-bit) tuviera exactamente dos unos, asegurando así que tenga una Distancia de Hamming igual a dos. De este modo, la computadora podría detectar posibles errores cuando en su entrada no había exactamente dos unos en cada penta-bit.

Este código seguía únicamente detectando errores por cambio en un solo bit; si en un mismo penta-bit un 0 cambiaba a 1 y un 1 cambiaba a 0, la regla de dos-entre-cinco se seguía cumpliendo y el error quedaba sin descubrir.

Repetición Otro código utilizado, consistía en repetir cada bit de datos varias veces para asegurarse de que la transmisión era correcta. Por ejemplo, si el bit de datos que se envía fuera un 1, un código de repetición con n=3, enviaría "111". Si los tres bits recibidos no eran idénticos, había un error. En un ambiente sin demasiado ruido, la mayoría de las veces solamente cambiaría un bit en cada paquete de tres bits. Por lo tanto, datos del tipo 001, 010, y 100 se corresponden al bit 0, mientras que 110, 101, y 011 se corresponden con el bit 1. Un código con esta capacidad de reconstruir el mensaje original en la presencia de errores se conoce como código corrector de errores. Sin embargo, este código no puede reparar correctamente todos los errores. En nuestro ejemplo, si el error en la transmisión provocara el cambio simultáneo de dos bits y el receptor recibiera "001", el sistema detectaría el error, pero considerando que el bit original era 0, lo cual es incorrecto. Si se aumenta el número de veces que se repite cada bit a cuatro (n=4), es posible detectar los errores en dos bits pero obviamente no se podrán corregir; con cinco, es posible corregir errores de dos bits, pero no lo podrá hacer en errores de tres bits. Por otra parte, el código de la repetición es extremadamente ineficaz, pues reduce la velocidad de transmisión por tres en nuestro ejemplo original y su eficacia cae drásticamente al aumentar el número de veces que cada bit se repite para detectar y corregir más errores. El uso del código de bloques no lineales para detección de errores no es muy implementado por lo tanto emplearemos el código de errores lineales para la corrección de errores.

Códigos Hamming Si se añaden junto al mensaje más bits detectores-correctores de error y si esos bits se pueden ordenar de modo que diferentes bits de error producen diferentes resultados, entonces los bits erróneos podrían ser identificados. En un conjunto de siete bits, hay sólo siete posibles errores de bit, por lo que con tres bits de control de error se podría especificar, además de que ocurrió un error, en qué bit fue. Hamming estudió los esquemas de codificación existentes, incluido el de dos entre cinco, y generalizó sus conclusiones. Para empezar, desarrolló una nomenclatura para describir el sistema, incluyendo el número de los bits de datos y el de los bits detectores-correctores de error en un bloque. Por ejemplo, la paridad incluye un solo bit para cualquier palabra de datos, así que las palabras del Código ASCII que son de siete bits, Hamming las describía como un código (8.7), esto es, un total de 8 bits de los cuales 7 son datos. con base a la anterior repetición, sería un código (3.1), siguiendo la misma lógica. La relación de la información es el segundo número dividido por el primero, por nuestro ejemplo de la repetición, 1/3. Hamming también estudió los problemas que surgían al cambiar dos o más bits a la vez y describió esto como "distancia" (ahora llamada distancia de Hamming en su honor). La paridad tiene una distancia de 2, dado que cualquier error en dos bits no será detectado. La repetición (3.1)tiene una distancia de 3, pues son necesarios el cambio simultáneo de tres bits para obtener otra palabra de código. La repetición (4.1) (cada bit se repite cuatro veces) tiene una distancia de 4, así que el cambio de dos bits en el mismo grupo quedará sin definir.

Hamming estaba interesado en solucionar simultáneamente dos problemas: aumentar la distancia tanto como sea posible, a la vez que se aumentan al máximo los bits de información. Durante los años 40 desarrolló varios esquemas de codificación que mejoraban notablemente los códigos existentes. La clave de todos sus sistemas era intercalar entre los bits de datos los de paridad. Hamming (7,4) Hoy, el código de Hamming se refiere al (7.4) que Hamming introdujo en 1950. El código de Hamming agrega tres bits adicionales de comprobación por cada cuatro bits de datos del mensaje. El algoritmo de Hamming (7.4) puede corregir cualquier error de un solo bit, pero cuando hay errores en más de un bit, la palabra transmitida se confunde con otra con error en un sólo bit, siendo corregida, pero de forma incorrecta, es decir que la palabra que se corrige es otra distinta a la original, y el mensaje final será incorrecto sin saberlo. Para poder detectar (aunque sin corregirlos) errores de dos bits, se debe añadir un bit más, y el código se llama Hamming extendido. El procedimiento para esto se explica al final. El algoritmo es el siguiente: 1. Todos los bits cuya posición es potencia de dos se utilizan como bits de paridad (posiciones 1, 2, 4, 8, 16, 32, 64, etc.). 2. Los bits del resto de posiciones son utilizados como bits de datos (posiciones 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.). 3. Cada bit de paridad se obtiene calculando la paridad de alguno de los bits de datos. La posición del bit de paridad determina la secuencia de los bits que alternativamente comprueba y salta, a partir de éste, tal y como se explica a continuación. Posición 1: salta 0, comprueba 1, salta 1, comprueba 1, etc. Posición 2: salta 1, comprueba 2, salta 2, comprueba 2, etc. Posición 4: salta 3, comprueba 4, salta 4, comprueba 4, etc. Posición 8: salta 7, comprueba 8, salta 8, comprueba 8, etc. Posición 16: salta 15, comprueba 16, salta 16, comprueba 16, etc. Regla general para la posición n es: salta n-1 bits, comprueba n bits, salta n bits, comprueba n bits... Y así sucesivamente. En otras palabras, el bit de paridad de la posición comprueba los bits en las posiciones que tengan al bit k en su representación binaria. Dicho a la inversa, el bit 4, chequea los bits 4, 5, 6, 7, al ser estos los de su representación binaria: 4=100(2), 5=101(2), 6=110(2) y 7=111(2). Por el contrario, el mismo bit de paridad no comprueba el bit 8, debido a que en su representación binaria el bit número 3 (=4) es igual a 0 (8=1000B). Así, por ejemplo, para los primeros términos se tiene: En la Posición 1 (2^0 = 1), comprobaríamos los bits: 1, 3, 5, 7, 9, 11, 13... En la Posición 2 (2^1 = 2), los bits: 2, 3, 6, 7, 10, 11, 14, 15... En la Posición 4 (2^2 = 4), los bits: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23... En la Posición 8 (2^3 = 8) tendríamos: 8, 9, 10, 11, 12, 13, 14, 15, 24-31... Siguiendo el algoritmo hasta completar la nueva cadena.

Ejemplo Consideremos la palabra de datos de 7 bits "0110101". Para ver cómo se generan y utilizan los códigos Hamming para detectar un error, observe las tablas siguientes. Se utiliza la d para indicar los bits de datos y la p para los de paridad. En primer lugar los bits de datos se insertan en las posiciones apropiadas y los bits de paridad calculados en cada caso usando la paridad par. p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Palabra de datos (sin paridad): p1

0 1

0

1 1

1

0 0

1 1

0

1 1

p2

0

0

p3

0

1

1

0

1

0

p4 Palabra de datos (con paridad):

1

0

0

0

1

1

0

0

1

0

1

0

1

0

1

0

1

Cálculo de los bits de paridad en el código Hamming P1 = D1 exor D2 exor D4 exor D5 exor D7 P2 = D1 exor D3 exor D4 exor D6 exor D7 P3 = D2 exor D3 exor D4 P4 = D5 exor D6 exor D7 La nueva palabra de datos (con los bits de paridad) es ahora "10001100101". Consideremos ahora que el bit de la derecha, por error, cambia de 1 a 0. La nueva palabra de datos será ahora "10001100100". Sin errores

Palabra de datos recibida: p1

p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7

Prueba de paridad

1 0 0 0 1 1 0 0 1 0 1

1

1

p2

0

1

1 Correcto

0

1 0

0 1 Correcto

0

0 1 1 0

Correcto

0

0 1 0 1 Correcto

0

0 0

p3

0

p4

1

Bit de comprobación

Comprobación de los bits de paridad (con primer bit de la derecha sin cambiar) Con errores

Palabra de datos recibida: p1 p2 p3 p4

p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7

Prueba de paridad

1 0 0 0 1 1 0 0 1 0 0

1

0

0 1 0

1

0 1 0

0 1 1 0

1

Bit de comprobación

0 Error

1

0 0 Error

1

Correcto 1 1 0 0 Error

0 1

Comprobación de los bits de paridad (con primer bit de la derecha cambiado) Si se analiza en la tabla anterior la paridad que se debe obtener a la derecha tras la llegada del mensaje sin errores debe ser siempre 0 (por cada fila), pero en el momento en que ocurre un error esta paridad cambia a 1, de allí el nombre de la columna "prueba de paridad 1". Se observa que en la fila en que el cambio no afectó la paridad es cero y llega sin errores. El paso final es evaluar los bits de paridad (recuerde que el fallo se encuentra en d7). El valor entero que representan los bits de paridad es 11 (si no hubieran ocurrido errores

este valor seria 0), lo que significa que el bit décimo primero de la palabra de datos (bits de paridad incluidos) es el erróneo y necesita ser cambiado. p4 Binario

p3

1

Decimal

0 8

p2

p1

1

1 2

1

Σ = 11

Cambiando el bit décimo primero 10001100100 se obtiene de nuevo 10001100101. Eliminando los bits de patrón de la paridad no se tienen en cuenta los bits de paridad. Si el error se produjera en uno de ellos, en la comprobación sólo se detectaría un error, justo el correspondiente al bit de paridad causante del mismo.

Hamming Extendido Finalmente, para detectar errores en 2 bits se utiliza un bit adicional de paridad (Hamming Extendido) donde puede darse el caso de 3 posibilidades: 1.-' No hay error -> Hamming =0, Paridad OK 2.- Un bit de error -> Paridad Fallo entonces a) Hamming = 0, P = incorrecto, en este caso se cambia el valor del bit de paridad. b) Hamming <> 0, corrijo según Hamming. 3.- Dos bit en error -> Paridad Ok, Hamming <> 0, por lo tanto informo, NO corrijo.

Bit de paridad Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Este aviso fue puesto el 1 de abril de 2013. Puedes añadirlas o avisar al autor principal del artículo en su página de discusión pegando: {{subst:Aviso referencias|Bit de paridad}} ~~~~ byte con bit de paridad

7 bits de datos

par

impar

0000000

00000000

00000001

1010001

10100011

10100010

1101001

11010010

11010011

1111111

11111111

11111110

Un bit de paridad es un dígito binario que indica si el número de bits con un valor de 1 en un conjunto de bits es par o impar. Los bits de paridad conforman el método de detección de errores más simple. La paridad par es un caso especial del control de redundancia cíclica (CRC), donde el bit de CRC se genera por el polinomio x+1. Nótese que este método detecta los errores, pero no los corrige (salvo en el caso de que la palabra transmitida sea de tamaño 1 bit). Existen dos variantes de este método, bit de paridad par y bit de paridad impar:

En el caso de la paridad par, se cuentan el número de unos. Si el total es impar, el bit de paridad se establece en uno y por tanto la suma del total anterior con este bit de paridad, daría par. Si el conteo de bits uno es par, entonces el bit de paridad(par) se deja en 0, pues ya es par. En el caso de la paridad impar, la situación es la contraria. Se suman los bits cuyo valor es uno, si da un número impar de bits, entonces el bit de paridad(impar) es cero. Y si la suma de los bits cuyo valor es uno es par, entonces el bit de paridad(impar) se establece en uno, haciendo impar la cuenta total de bits uno.

Reed-Solomon Reed-Solomon es un código cíclico no binario y constituye una subclase de los códigos BCH. Los códigos cíclicos son una subclase de los códigos de bloque estándar de detección y corrección de errores que protege la información contra errores en los datos transmitidos sobre un canal de comunicaciones. Este tipo de código pertenece a la categoría FEC (Forward Error Correction), es decir, corrige los datos alterados en el receptor y para ello utiliza unos bits adicionales que permiten esta recuperación a posteriori. El código fue inventado por Irving S. Reed y Gustave Solomon (de ahí su nombre) en el año 1960. Este código encuentra actualmente aplicado en áreas como los CD, telefonía móvil y sondas espaciales (la sonda Galileo a Júpiter en 1989, la sonda Magallanes a Venus ese mismo año o la sonda Ulises al Sol en 1990, por citar algunos ejemplos). También es de destacar el empleo del código Reed-Solomon en las comunicaciones por satélite Digital Video Broadcasting (DVB), en la transmisión digital de televisión ISDB-T, así como en los sistemas xDSL de comunicación por cable.

Características Este código se forma en base a grupos de bits que se denominan símbolos. El código Reed-Solomon trabaja con los símbolos en vez de con los bits individuales. Un símbolo es una secuencia de "m" bits individuales que aparecen en serie. Un símbolo es erróneo cuando al menos un bit del símbolo tiene error.

El código Reed-Solomon, tiene las siguientes características: 

Cada símbolo está constituido por "m" bits consecutivos agrupados.



Cada palabra-código consta de "k" símbolos de información (en lugar de bits), y "r" símbolos de paridad.



La longitud de la palabra-código es: expresada en nº de bit).

símbolos,(longitud=n m

CONCLUCIONES Concluimos que existen una diversidad de códigos para la detección y corrección de errores en sistemas digitales como pudimos observar y consiguientemente lo aclaramos con algunos ejemplos, que de alguna forma nos ayudaron a comprender mejor cada código de corrección. También observamos que tienen diversas aplicaciones en muchos aspectos reales en los sistemas digitales.

REFERENCIAS BIBLIOGRÁFICAS  www.wikipedia.com  Códigos para la detección y corrección de errores ( fuente externa).