INVESTIGACION SOBRE EL CODIGO DE REDUNDANCIA CICLICA (CRC)

INTEGRANTES DEL EQUIPO

Aguayo Castellanos Roberto

Arriaga Fuentes Ricardo

Romero Salas Victor

Brenda

Mayo 2001

INVESTIGACION SOBRE EL CODIGO DE REDUNDANCIA CICLICA (CRC)

INDICE

PAGINA

1.- Objetivo 3

2.- Introducción 3

3.- Antecedentes 4

4.- Marco teórico 6

5.- Desarrollo 8

6.- Ejemplo 10

7.- Resumen 11

8.- Conclusión 11

9.- Referencias 12

INVESTIGACION SOBRE EL CODIGO DE REDUNDANCIA CICLICA (CRC)

1.- Objetivo

Comprender e ilustrar con ejemplos el principio de funcionamiento del código de redundancia cíclica, sus estándares y aplicaciones en la detección de errores de transmisión de datos.

2.- Introducción

En la primera parte de esta investigación brindaremos algunos antecedentes para ubicar al lector de cómo ha evolucionado las técnicas de codificación de datos a través de la historia.

Con el marco teórico damos algunas definiciones útiles para comprensión del código de redundancia cíclica. En esta misma parte analizamos los motivos de la codificación de datos, vemos la protección de errores y resumimos como han evolucionado los códigos de detección de errores hasta llegar a los códigos polinómicos como es el caso del código de redundancia cíclica.

En la parte fuerte de la investigación definimos al código de redundancia cíclica, damos el procedimiento de la creación de este código, el cálculo de la redundancia, las normas internacionales de este código, su implementación y un ejemplo de la creación de este código ante una trama de bits de entrada.

3.- Antecedentes

LA CODIFICACIÓN DE LAS SEÑALES EN LA HISTORIA

Las sociedades antiguas han empleado siempre unas señales convencionales para transmitir los mensajes más urgentes y de uso más corriente, los contenidos más importantes que se codificaron por su significado secreto moderno datan de finales del siglo XVII, hechos por la Armada, en donde vemos la aplicación de la codificación en la marina.

A partir de aquella época cada marina puso en uso su propio código de señales, y con ello aparecieron distintos métodos y sistemas. Posteriormente se hizo evidente la necesidad de disponer de un código internacional de señales que solucionara el inconveniente de la diversidad de idiomas e hiciera posible las comunicaciones entre personas de habla distinta.  

El primer código internacional fue recopilado por el Ministerio de Comercio Británico y comprendía, 7.000 señales utilizando 18 banderas. Estaba divido en dos partes: La primera edición se publicó en 1887, e inmediatamente fue objeto de varias revisiones y modificaciones (Conferencia Internacional de Washington, 1.889; Conferencia Internacional de Madrid, 1932; Asamblea de la I.M.C.O. de 1961, que acordó efectuar una revisión total y adaptarla a las exigencias actuales).

Las señales contenidas en el código pueden ser transmitidas con todo los medios de comunicación, que son:

·         Banderas.

·         Señales de Humo

·         Señales de Luz

·         Destellos, empleados los signos del alfabeto Morse.

·         Sonidos, con símbolos Morse.

·         Oral con megáfono.

·         Brazos, y utilizando el semáforo o Morse.

·         Radiotelegrafía y Radiotelefonía.

. Comunicaciones alámbricas de datos

. Comunicaciones via satélite de datos

Otro gran avance de las radiocomunicaciones se produjo en 1950 con la miniaturización de los componentes y la aparición del transistor. Esto hizo posible el uso de frecuencias más altas y mayores potencias a un consumo más bajo e instalaciones menos costosas.  

Después de 1962, cuando fue puesto en órbita el primer satélite de comunicaciones "Telstar", se hizo posible transmitir mensajes por radio vía satélite, que eran reemitidos a cualquier punto deseado de la Tierra.

Con esta breve reseña vemos como a través de la historia siempre ha habido la necesidad de emplear códigos estándares para el transmisor y el receptor para poder comunicarse con un mismo lenguaje, sin importar a veces de que país sean o que lengua hablen.

Pero aunado a este tipo de codificación el la actualidad aparte de los códigos que empleamos para transmitir las señales también necesitamos agregarle un nuevo código a nuestra señal para poder detectar errores en la transmisión.

Estos nuevos códigos de detección de errores serán explicados en el marco teórico de la presente investigación.

4.- Marco Teórico

Primero empezaremos definiendo el termino datos, este se refiere a toda aquella información que represente un mensaje ya sea de tipo analógico o digital. El traslado de estos datos entre dos puntos situadas a cierta distancia es la transmisión de datos.

Entendemos por codificación de datos las técnicas que vamos a usar para mandar un tipo de datos utilizando señales analógicas o digitales. 

Motivos de la codificación:

Aprovechar ancho de banda.

Sincronización. A partir de la señal que mando me gustaría poder recuperar el reloj del emisor.

Inmunidad ante el ruido e interferencias.

Abaratar los costos.

Disminuir la complejidad

En la transmisión de datos además de los códigos originales de la información, los equipos de comunicación de datos añaden bits de control que permiten detectar si ha habido algún error en la transmisión. Los errores se deben principalmente a ruido en el canal de transmisión que provoca que algunos bits o dígitos binarios se mal interpreten. La forma mas común de evitar estos errores es añadir a cada palabra (conjunto de bits) un bit que indica si el número de 1 en la palabra es par o impar. Según sea lo primero o lo segundo se dice que el control de paridad es par o impar. Este simple mecanismo permite detectar la mayor parte de errores que aparecen durante la transmisión de la información

Protección contra Errores

En toda transmisión pueden aparecer errores. Se determina la tasa de error por la relación entre el numero de bits erróneos y los bit totales. Lo mismo que con bits, se puede establecer una tasa para caracteres o bloques. Se denomina Error Residual al número de bits erróneos no corregidos en relación al total de bits enviados. Las señales emitidas suelen sufrir dos tipos de deformación; atenuación (reducción de su amplitud); y desfase, siendo esta ultima la que más afecta a la transmisión. Otros factores que afectan a la señal son: ruido blanco (por los componentes eléctricos de los transformadores), ruido impulsivo, ecos, diafonias, etc. Las distorsiones físicas de la señal las trata el Equipo Terminal de Tratamiento de Datos y los problemas a nivel de bit los trata el Equipo Terminal del Circuito de Datos

Los sistemas de protección contra errores realizan una codificación del mensaje de datos y una posterior decodificación. En ambos casos se trabaja con dato binarios a nivel de enlace. Los errores se pueden detectar y/o corregir. La corrección la puede realizar el propio decodificador (corrección directa) o se realiza por retransmisión.

A los datos enviados se les asocian bits de control (se añade redundancia al mensaje). Estos se pueden calcular para cada bloque de datos, o en función de bloques precedentes (recurrentes).

Como ejemplos de procedimientos de control de errores se pueden citar:

  Ø       Control de paridad por carácter: consiste en hacer el número de unos que aparecen en el dato (byte) par o impar. Puede fijarse también la paridad a un valor de 1 (Mark) ó 0 (Space).

  Ø       Control de paridad por Matriz de caracteres: se determina la paridad de filas y columnas, y se envían los bits de control por filas. Permite tanto la detección como la corrección de los errores.

  Ø       Códigos Lineales: el conjunto de todos los bloques de datos posibles y sus respectivos bits de control, forman las palabras del código corrector. Cada palabra de n bits se componen de k bits de datos y n – k bits de control (se llaman códigos n,k). Cada palabra de un código linear se determina multiplicando el vector de datos por una matriz generatriz. El decodificador determina si la palabra recibida pertenece al código o no (caso de un error).

Ø       Códigos Polinomicos: es un código lineal donde cada palabra del código es múltiplo de un polinomio generador. Los bits de control pueden obtenerse del resto de dividir los bits de información por el polinomio generador

 Ø       Códigos Cíclicos: son códigos lineales en los que cualquier permutación del vector pertenece al código. Los elementos del vector se consideran como coeficientes de un polinomio. La codificación/decodificación se realiza gracias a registros de desplazamiento (multiplicación o división del vector información con el generador). Un polinomio generador CRC – 16 (X16 + X15 + X2 + 1) puede detectar errores en grupos de 16 bits, disminuyendo la tasa de error.

 Existen otros códigos de detección y corrección de errores pero para nuestro estudio analizaremos el código de redundancia cíclica.

5.- Desarrollo

El código de redundancia cìclica ( también conocido como código de redundancia cíclica o código CRC). Los códigos polinomicos se basan en el tratamiento de series de bits como si fueran representaciones de polinomios, con coeficientes de valor 0 y 1 únicamente.

Una trama de k bits se ve como una lista de coeficientes de un polinomio con k términos, cubriendo un rango desde X^k-1 hasta X⁰. A este tipo de polinomio se le conoce como polinomio de grado (k - 1).

El bit de orden mas alto (el de más a la izquierda) es el coeficiente correspondiente al termino X^k-1; el siguiente bit es el coeficiente de X^k-2, y así sucesivamente.

Por ejemplo, el código 110001 tiene 6 bits y, por consiguiente, representa a un polinomio de seis términos, que contiene los siguientes coeficientes 1, 1, 0, 0, 0, y 1, es decir: X⁵ + X⁴ + X⁰.

De acuerdo con las reglas de la teoría del campo algebraico, la aritmética del polinomio se realiza en modulo 2. No hay términos de acarreo para la suma ni de préstamo para la resta; las dos operaciones son idénticas al OR EXCLUSIVO.

Por ejemplo:

10011011 00110011 11110000 01010101

+ 11001010 + 11001101 - 10100110 - 10101111

01010001 11111110 01010110 11111010

La división larga se realiza de la misma manera que en el caso binario, con excepción de la resta que se efectúa en módulo 2, como en el caso anterior. Se dice que el divisor "cabe en" el dividendo, si tiene tantos bits como este último.

Cuando se emplea el método del código polinomico, el emisor y el receptor deberán estar de acuerdo respecto a un polinomico generador, G(x), en forma anticipada. Los bits de orden superior e inferior del generador deben ser 1. Para calcular el código de redundancia de alguna trama con m bits, correspondiente al polinomio M(x), la trama deberá ser mas grande que el polinomio generador.

La idea básica consiste en incluir un código de redundancia al final de la trama, de tal manera que, el polinomio representado por la trama con el código de redundancia sea divisible por G(x). Cuando el receptor recibe la trama de suma comprobada, intenta dividirla entre G(x). Si existe un resto, habrá ocurrido un error de transmisión.

Cálculo de la redundancia

1.-Sea r el grado de G(x). Agregar r bits a cero al extremo de orden inferior de la trama, de tal manera que ahora contenga m + r bits, y corresponda al polinomio x^r M(x).

2-Dividir la serie de bits correspondientes a x^r M(x) entre la serie de bits correspondientes a G(x), empleando la división en modulo 2.

3.-Restar el resto (que siempre tiene r o menos bits) de la serie de bits correspondientes a xr M(x), empleando la resta en modulo 2. El resultado es la trama lista para transmitir. Llámese T(x) a este polinomio.

Normas internacionales

CRC-12 = x¹² + x¹¹ + x³ + x² + x¹ + 1

CRC-16 = x¹⁶ + x¹⁵ + x² + 1

CRC-ITU-T = x¹⁶ + x¹² + x⁵ + 1

CRC32-ITU-T = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x¹ + 1

Los tres contienen el término x + 1 como factor primo. El CRC-12 se utiliza cuando la longitud del carácter es de 6 bits; en tanto que los otros dos se emplean para caracteres de 8 bits. Un código de redundancia de 16 bits, como las normas CRC-16 o CRC-CCITT, captura todos los errores simples y dobles, todos los errores con un numero impar de bits, todos los errores de ráfagas con longitudes de 16 o menos bits. 99.997% de los errores de ráfagas de 17 bits y 99.998% de los errores de ráfagas de longitudes de 18 bits o mayores.

Implementación

Aunque el cálculo requerido para obtener los bits de redundancia puede parecer complicado, Peterson y Brown (1961) han demostrado que un simple circuito de registro de desplazamiento puede construirse para calcular y comprobar los bits de redundancia por hardware. En la practica, casi siempre se utiliza este hardware.

6.- Ejemplo

Cálculo para la trama 1101011011 y G(x) =x⁴+x+1.

Deberá quedar claro que T(x) es divisible (modulo 2) por G(x). En cualquier problema de división, si se le disminuye el resto al dividendo, lo que queda es divisible por el divisor.

7.- Resumen

El CRC es una de las herramientas más comunes y potentes para la detección de errores. Este consiste en considerar los bits de entrada como los coeficientes de un polinomio. Se utiliza el llamado "polinomio generador" compartido por el emisor y el receptor. La idea es construir con el polinomio de entrada un segundo polinomio que sea divisible por el polinomio generador. El mensaje que se transmite es el polinomio calculado. El polinomio recibido si no ha sufrido errores seguirá siendo divisible por el polinomio generador. Si no es divisible, es que se han producido errores

Dado un bloque de datos de k bits, el transmisor genera una secuencia de m bits, de forma que la trama resultante está formada por los k bits más los m bits generados. El código permite detectar todas las ráfagas de error que afectan a m bits, además de detectar todas las ráfagas que afecten a un número impar de bits.

8.- Conclusión

De esta investigación sobre el código de redundancia cíclica, concluimos primero que los códigos de detección y corrección de errores en cualquier transmisión de datos es de suma importancia ya que con estos evitamos que se tenga que reenviar la información por causa de un error y aseguramos que nuestra información llegará adecuadamente.

Dentro de las ventajas que encontramos con el código de redundancia cíclica en primera es que no solo detectamos un error en la transmisión sino que detectamos en donde ocurrió este error y asì podemos realizar la corrección de errores fácilmente, y además que la implementación de este código es muy sencilla por lo que con unos simples registros de corrimiento por hardware podemos efectuar la generación de la trama de redundancia en el transmisor y la detección y corrección de errores en el receptor siempre y cuando se acuerde en ambas partes el polinomio generador que ocupen. Y dentro de las desventajas que encontramos con este código es que al aumentarle la trama de redundancia al mensaje de transmisión requerimos un mayor ancho de banda.

9.- Referencias

Historia de la transmisión de datos . [ON LINE]. http://www.foromaritimovasco.com

TANUNBAUM, Andrew S. Redes de Computadoras. Tercera Edición. Prentice-Hall Hispanoamericana, S.A., México, 1997.

W. Wesley Peterson and E. J. Weldon. Error-Correcting Codes, Second Edition. MIT Press,1972.

Stanford University; Error-Correcting Codes.

http://www.stanford.edu/class/ee387/, 2000-2001