APLICACIÓN DE LOS POLINOMIOS PARA LA CORRECCIÓN Y DETECCIÓN EN LA TRANSMISÓN DE DATOS

APLICACIÓN DE LOS POLINOMIOS PARA LA CORRECCIÓN Y DETECCIÓN EN LA TRANSMISÓN DE DATOS

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.

Marco teórico

Objetivo

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.

Detección y corrección de datos:

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.

Detección de errores: La detección de errores es la detección de errores causados por el ruido u otros deterioros durante la transmisión desde el transmisor al receptor.

La corrección de errores: Es la detección de errores y de reconstrucción de los datos originales, sin errores.

Redundancia: Significa transmitir cada carácter dos o tres veces, o si se emplea a nivel de mensaje repetir el mensaje dos o tres veces, en caso que las versiones difieran habrá error o errores.

Comprobación de redundancia cíclica

La comprobación de redundancia cíclica (CRC) es un código de detección de errores usado frecuentemente en redes digitales y en dispositivos de almacenamiento para detectar cambios accidentales en los datos. Los bloques de datos ingresados en estos sistemas contiene un valor de verificación adjunto, basado en el residuo de una división de polinomios.

Esta técnica es ampliamente usada debido a que es fácil de implementar en los circuitos integrados a muy gran escala (VLSI) que forman el hardware. Un mensaje puede verse como un simple número binario, el cual puede ser dividido por una cantidad que consideraremos constante, al efectuar la división (a módulo 2) se obtiene un cociente y un residuo, este último es transmitido después del mensaje y es comparado en la estación receptora con el residuo obtenido por la división de los datos recibidos y el mismo valor constante. Si son iguales los residuos se acepta el mensaje, de lo contrario se supone un error de transmisión. En el proceso de datos comercial es ampliamente usada la verificación por redundancia cíclica de 16 bits de longitud, aunque también es posible usar 32 bits lo cual puede ser más efectivo.

Matemáticas del CRC

Este apartado se refiere al análisis matemático de este proceso de división, como pone de manifiesto la manera de elegir un divisor que garantiza la detección de errores buenas propiedades. En este análisis, los dígitos de las cadenas de bits son considerados como los coeficientes de un polinomio en algunos variables x/coeficientes, que son elementos del campo finito binario en lugar de los números decimales. Este polinomio forma unas cadenas de bits que pueden observarse como elementos de un anillo. Un anillo es, hablando en términos generales, un conjunto de elementos, es decir como los números que pueden ser operados por una operación semejante pero no idéntica a la de la suma y además alguna otra operación semejante a la multiplicación, estas operaciones poseen muchas de las propiedades de la aritmética conmutatividad, asociativa, y distributiva.

Especificación de un CRC

El CRC se utiliza como una detección de errores de código, el cual tiene una serie de aplicaciones usadas cuando se implementa mediante normas, convirtiéndolo así en un sistema práctico.

Estas son algunas de las aplicaciones:

• Se usa un patrón de prefijos de bit para comprobar su autenticidad. Esto es útil cuando la trama podría tener errores en los bits de delante de un mensaje, una alteración que, de otro modo dejaría sin cambios al CRC. A veces un envío agrega n bits (n es el tamaño de la CRC)

...