Detección de Errores.

1. Tipos de Errores

Simples

El tipo de error simple sería el cambio de un bit.

Error de ráfaga:

Se considera un error de ráfaga a partir de que sean dos o más los bits que se han cambiado durante la transmisión. Esto no implica que, necesariamente, los errores se hayan producido en bits consecutivos.

El largo de las ráfagas se pueden caracterizar en un canál y esto permite luego elegir un polinómio en relación al la longitud o tiempo que demore la ráfaga del canál, como es el caso de Código de Redundancia Cíclica que veremos mas adelante.

2. Tratamiento

El tratamiento de errores  tiene un par de posibilidades que no siempre se usan en conjunto.

Detección de Errores

Se puede detectar el error y descartar la trama o gestionar un reenvío o intentar recuperar la trama original con la información redundante si es que existe.

Corrección de Errores.

La corrección de errores se puede implementar a partir de la Detección del Error. Si hay redundancia suficiente se puede recuperar la información completa sin errores y si no se puede gestionar la retransmisión.

3. Bit de Paridad ( código Lineal)

4. Comprobación de Redundancia Cíclica.

¿Que es CRC?

El núcleo de la verificación CRC es implementar la operación de división sin pedir prestado.

Aritmética módulo 2

La aritmética módulo 2 hace uso de sumas binarias sin acarreo, lo cual es exactamente igual que la operación lógica exclusive-OR. La operación de resta binaria sin acarreos es también igual que la operación lógica exclusive-OR. Por ejemplo:

El siguiente es un ejemplo para ilustrar cómo implementar la verificación CRC.

101101  => 1 2⁵ + 0 2⁴ + 1 2³+ 1 2² + 0 2¹ + 1 2⁰  

101101  => 1. 32 + 0 . 16+ 1. 8 + 1. 4 + 0. 2 + 1.1  

Podemos ver que no es mas que el Polinomio que permite pasar de un número binario a un número decimal.

Justificación del CRC

Esto es lo que usaremos , esta forma de presentación de un Polinomio para justificar el uso de CRC para Detección de errores en la transmisión.

En el receptor divido nuevamente por el MISMO polinómio.

M / P = (T . 2 ^n-k + R)/P = T/P  . 2 ^n-k  + R/P  por (1)

Q + R/P + R/P  = Q + R/P + R/P 

Si la  suma +   fuera una or exclusiva y si los sumandos R/P son iguales, esta suma da CERO, lo que implicaría que lo transmitido y lo recibido coinciden!!. Este es el principio del Código de Redundancia Cíclica.

Polinomios de Uso Frecuente.

Suelen usarse alguno de estos cuatro polinomios, los mismos son definidos en un Standar.

Observación: El método NO es de cifrado.

A menudo se piensa que si, cuando llega un mensaje, este y su CRC coinciden, quiere decir que el mensaje no ha podido ser alterado durante su transmisión, aunque se haya transmitido por un canal abierto.  Esta suposición es falsa porque CRC es un mal método de cifrado de datos. De hecho, el CRC no se trata realmente de un método de cifrado, lo que realmente hace es utilizarse para el control de integridad de datos, pero en algunos casos se supone que se utilizarán para el cifrado.

Librería en C que permite hacer un cálculo de CRC

Implementación Electrónica

Esto sería:

5. Ejemplo de Cálculo de CRC

Obtenido del Stalling.

Ejemplo 6.6.

La arquitectura de este circuito se explica mejor considerando un caso particu- lar, como el ejemplo que se muestra en la Figura 6.5. En este ejemplo se usa:}

 Datos D=1010001101 =>  D(X) = X⁹  +  X⁷  + X³  + X²  + 1

Divisor P = 110101 => P(X)=X⁵ + X⁴ + X² + 1

definidas anteriormente.

En la Figura  se muestra la realización del registro de desplazamiento. El proceso co- mienza con la puesta a cero de todo el registro (todo ceros). El mensaje, o dividendo, se intro- duce a continuación, bit a bit, comenzado por el bit más significativo. La Figura 6.5b es una tabla que muestra el funcionamiento paso a paso por cada bit de entrada. Cada fila de la tabla muestra los valores almacenados en los cinco elementos de memoria del registro de desplaza- miento. Las filas muestran, además, los valores que aparecerán en las salidas de los tres circui- tos exclusive-OR. Finalmente, en cada columna se muestra el valor del siguiente bit de entrada, disponible para el siguiente paso.

Nótese que la operación exclusive-or afectará a C4, C2 y C0 en el siguiente desplazamiento. Esto es idéntico al procedimiento de división binaria mencionado anteriormente. El procedi- miento continúa para todos los bits del mensaje. Para generar la salida se usan dos conmutado- res. Los bits correspondientes a los datos de entrada se introducen poniendo los dos conmutado- res a la posición A. A resultas, tras 10 pasos, los bits de entrada se introducirán en el registro de desplazamiento, a la vez que serán generados a la salida. Tras proceder el último bit, el registro de desplazamiento contendrá el resto (la FCS) (mostrado en cajas sombreadas). Tan pronto co- mo el último bit de datos entra en el registro de desplazamiento, los dos conmutadores se ponen en la posición B. Esto causa dos efectos:

1. Todas las puertas exclusive-or se convierten en simples elementos de paso, es decir, no cambia ningún bit.

2. Al seguir desplazando el registro, se generarán los 5 bits correspondientes a la CRC.

En el receptor se utiliza la misma lógica. Cada bit de un bloque de M se introducirá en el regis- tro de desplazamiento. Si no ha habido errores, el registro de desplazamiento debería contener el patrón de bits R al final de M. Los bits transmitidos de R empiezan a llegar y el efecto consis- tirá en que, cuando concluya la recepción, el registro debe contener todas las posiciones igual a cero.

6. Código de Hamming ( código Lineal)

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 solo un bit, pero no pueden corregirlo.

Se define distancia de Hamming d(v₁ ,  v₂) entre dos palabras de n bits al número de bits en el que v₁  y  v₂ difieren.

Por Ejemplo:

Esta distancia de Hamming me indica una medida de fortaleza del código,

La idea es agregar un conjunto de bits, con esto las secuencias de bits autorizadas no son todas, se eligen algunas. Las que se eligen son las que tengan muchos una distancia de Hamming lo mas grande posible.

Ver que si se agregan mas bits, se logra una mayor distancia...pero aumenta la cantida de bits a enviar.

En el Stalling se muestra un ejemplo. No es propósito de la materia profundizar en esto, solamente entender y saber el concepto.

7. Código Cíclico Reed-Solomon (informativo)

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 mecanismo permite la 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.

Usa la transformada discreta de Fourier.

Los códigos QR contienen una redundancia de información basada en la corrección de errores Reed-Solomon que permite la personalización de los códigos QR, ya sea con colores o con imágenes y con textos incrustados.

Este código se encuentra actualmente aplicado 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.

El tratamiento de este tema escapa a la materia y se incluye a los efectos de dejar claro que hay una serie de métodos de detección y correción de errores que no son vistos en esta asignatura.