ESCUELA POLITECNICA DEL EJÉRCITOExtensión Latacunga

CIRCUITOS DIGITALES

Nombre: Emily Karina Tobar VidalCurso: Tercero Electrónica “A”Fecha: 06 de septiembre del 2013

CODIGOS DE DETECCION Y CORRECCION DE ERRORES

1.1 CÓDIGOS DETECCIÓN Y CORRECCIÓN DE ERRORES

Los errores de transmisión en las líneas se deben a diversos factores, como el ruido térmico, ruido impulsivo, etc. Dependiendo del medio de transmisión y del tipo de codificación empleado, se pueden presentar otros tipos de anomalías como ruido de redondeo y atenuación, así como cruce de líneas y eco [2].

La capacidad para detectar posibles errores en la información manipulada por las Computadoras es esencial para poder confiar en los resultados ofrecidos.

El error es la alteración del valor correcto en uno o más bits de información producida durante su almacenamiento, transmisión o manipulación.

1.2 VERIFICACIÓN DE ERRORES

Existen algunos mecanismos que garantizan un nivel de integridad de los datos para que los datos que obtiene el destinatario sean similares a los datos transmitidos. Existen dos maneras de proteger la transferencia de datos para que no se produzcan errores. instalando un medio de transmisión más seguro, es decir, una capa de protección física. Una conexión convencional tiene, por lo general, un porcentaje de error entre 10-5 y 10-7. Implementando mecanismos lógicos para detectar y corregir errores.La mayoría de los sistemas de control lógico de errores se basan en la suma de información (esto se denomina "redundancia") para verificar la validez de los datos. Esta información adicional se denomina suma de comprobación.Se han perfeccionado mejores sistemas de detección de errores mediante códigos denominados:

Códigos de autocorrección.

Códigos de auto verificación [3].

1.3 PARIDAD

La transmisión de datos binarios de un sitio a otro es un lugar común en todos los sistemas digitales como: la salida de datos binarios desde una computadora y que están registrándose en cinta magnética, transmisión de datos binarios por línea telefónica, información almacenada en un disco flexible se lee para cargarse en la memoria de una computadora personal.

Como se dijo este proceso está sujeto a error aun cuando los equipos modernos están diseñados para reducir la probabilidad de error.

Un bit de paridad es un bit extra que se agrega a un grupo codificado el cual se transfiere de una localización a otra. El bit de paridad se hace ya sea (0) o (1) dependiendo del número de unos que están en el grupo codificado.

Se usan dos métodos diferentes. En el método de paridad par el valor del bit de paridad se escoge de tal manera que el número total de unos en el grupo codificado (incluyendo el bit de paridad) sea un número par. Supóngase por ejemplo, que el grupo codificado es 10110. El grupo codificado tiene tres unos. Por tanto, se añade un bit de paridad de 1 para hacer el número total de unos un valor par. El nuevo grupo codificado, incluyendo el bit de paridad es:

10110 1 bit de paridad añadido

El método de paridad impar se usa exactamente de la misma manera, excepto que el bit de paridad se escoge de tal modo que el número total de unos (incluyendo el bit de paridad) sea un número impar. Por ejemplo, para el grupo codificado 01100, el bit de paridad asignado sería un 1. Para el grupo 11010, el bit de paridad sería un 0. En la tabla 1, observamos la forma de obtener los bits de paridad para el código binario de 3 bits paridad par (Pp), y paridad impar (Pi) [4].

1.4 CÓDIGO DE HAMMING

Es un Es un método general propuesto por R. W Hamming usando una distancia mínima m. Con este método, por cada entero m existe un código de hamming de 2m−1 bits que contiene m bits de paridad y 2m−1−m bits de información. En este código, los bits de paridad y los bits de paridad se encuentran entremezclados de la siguiente forma: Si se numeran las posiciones de los bits desde 1 hasta2m−1, los bits en la posición2k, donde , son los bits de paridad y los bits restantes son bits de información.

El valor de cada bit de paridad se escoge de modo que el total de unos en un número específico de bits sea par, y estos grupos se escogen de tal forma que ningún bit de información se cubra con la misma combinación de bits de paridad. Es lo anterior lo que proporciona al código su capacidad de corrección.

Tabla 1.

Tabla 2.

Posición de los bits

Para cada bit de paridad en la posición 2k, su grupo de bits de información correspondiente incluye todos esos bits de información correspondiente cuya representación binaria tenga un uno en la posición 2k. La siguiente tabla muestra los grupos de paridad para un código de hamming de 7 bits o sea de la forma 2m−1 con m = 3. En este ejemplo, los bits de información son 4 y los bits de paridad son 3. Los bits de información están en las posiciones 7, 6, 5,3. Los bits de paridad están en las posiciones 1, 2, 4.

En la tabla 2 el grupo de paridad del bit de paridad situado en la posición 4 son los bits de información situados en las posiciones 7,6, 5 que contienen unos en la posición 2k es decir 4 cuando k=2.

El grupo de paridad del bit de paridad situado en la posición 2 son los bits de información situados en las posiciones 7, 6, 3 que contienen unos en la posición 2k o sea 2 cuando k = 1.

El grupo de paridad del bit de paridad situado en la posición 1 son los bits de información situados en las posiciones 7, 5, 3 que contienen unos en la posición 2k o sea 1 cuando K = 0 [5].

1.5 CHEQUEO DE REDUNDANCIA CÍCLICA (CRC)

Este método es mucho más efectivo en la detección de errores en los sistemas de comunicaciones. No permite la corrección de errores. Se envía uno o más caracteres adicionales de redundancia denominados FCS ("frame check sequence") o BCC ("block check caracter"), que difieren fundamentalmente en la forma de calcularlo. El CRC consiste en considerar a los bits a ser transmitidos como un polinomio en x (para n bits el orden es n-1) tal que la presencia de un término significa un "1", y la ausencia, un "0"; es decir: sean 1010101 los bits a transmitir, entonces el mensaje podrá ser considerado como un polinomio G(x) tal que: G(x) = x7 + x5 + x3 + 1. Un mensaje de código cíclico consiste en un número de bits de datos y el BCC. Sea n el número total de bits y k el número de bits de datos, por lo tanto, el número de bits del BCC es n - k. El código del mensaje (BCC) se obtiene de 2 polinomios:

1.5.1 PASOS A SEGUIR PASAR GENERAR EL CÓDIGO CRC

Multiplicar el mensaje G(x) por x, siendo n - k el número de bits del BCC para dar lugar al BCC (multiplicar por x, es lo mismo que desplazar el mensaje polinomial de datos n-k lugares completando con ceros a la derecha).

G(x) * xn-k.

Dividir el producto resultante G(x) * xn-k por el polinomio generador P(x).G(x) * xn-k = Q(x) P(x) + C(x)

Despreciar el cociente y sumarle a G(x) * xn-k el resto C(x) de la división para producir el código de mensaje polinomial F(x).F(x) = G(x) * xn-k + C(x); “Mensaje Polinomial a Transmitir”.

A continuación un ejemplo que dará a entender el procedimiento: transmitir 10011011. Polinomio generador: G(x)= x3+1. Entonces polinomio generador es: 1001 (r=3). Se añaden 3 bits de 0 al final del mensaje: 10011011000 Y se divide como se muestra en la figura 1.

2 CRITERIO PERSONAL

Generalmente en la transmisión de información desde un transmisor a un receptor se generan errores en los datos que se pueden corregir aplicando métodos y algoritmos. El método de Hamming permite verificar los bits de paridad transmitidos y compararlos con los bits de obtenidos por el receptor, ya sea paridad par o paridad de esta forma se puede hallar el error y corregirlo. El código por medio del método de CRC se lo obtiene aplicando divisiones binarias para ser transmitido este método no corrige el error pide retransmisión.

Figura 1. Codificación por método CRC.

3 FUENTES

1. TOCCI, R. J. y WIDMER, N. S., “Sistemas Digitales”, octava edición, Pearson Educacion, México, 2003.

2. GIL SANCHEZ, L., “Introducción a la Electrónica digital”, [online], Disponible en: http://books.google.com.ec