Descripcion de errores

CONTROL DE ERRORES

DETECCIÓN DE ERRORES • Ejecutada por el receptor y consiste en tener mecanismos para saber si lo que ha llegado está correcto o no. • Si está correcto debe ser procesada y enviada al nivel inmediatamento superior. • Si está mala, debe ignorarlo o tratarlo de corregir. • Se utilizan códigos detectores de errores • Algunas técnicas para la detección de errores son:
–Duplicidad – Paridad – Códigos de Redundancia Cíclica
Fundamentos de Protocolos

Edwin Montoya

1

PARIDAD • Puede ser “par” o “impar” • Se adiciona un bit a cada caracter, y este bit completará un número “par” de 1´s o un número “impar” de 1´s.
– Ej: Paridad “par”: 01011010[0], 11000100[1] – Ej: Paridad “impar”: 11011001[1], 10101101[0]

• Su eficiencia es del 50% • Puede combinarse paridadhorizontal o vertical

Fundamentos de Protocolos

Edwin Montoya

CÓDIGO DE REDUNDANCIA CICLICA - CRC
• Los mensajes en la red se tratan como POLINOMIOS con coeficientes 0 y 1. • Un mensaje de k bits, se considera un polinomio x^(k-1) a x^0. • Tanto transmisor como receptor deben tener un acuerdo respecto al POLINOMIO GENERADOR G(x) • Definamos M(x) el polinomio del mensaje original delongitud m bits y de grado m-1. • El grado de M(x) debe ser mayor que el de G(x). • El algoritmo para calcular la Suma de Comprobación es: • Sea r el grado de G(x), agrege r bits en 0 al final del mensaje, quedando x^rM(x)
Fundamentos de Protocolos Edwin Montoya

2

CRC (cont.) • Divida x^rM(x) entre G(x) usando división módulo 2. • Reste el residuo a x^rM(x) usando resta modulo 2 • Este resultadollamado T(x) es el que se transmite por la red • En el lado del receptor al realizar la operación T(x) / G(x) el residuo debe ser 0, de lo contrario hubo un error

Fundamentos de Protocolos

Edwin Montoya

CORRECCIÓN DE ERRORES • Estas acciones se toman cuando la unidad de datos esta mala. • Una de las técnicas más utilizadas es la de RETROALIMENTACIÓN, que consiste en avisarle al ORIGEN deléxito o fracaso de la transmisión. • La otra forma de corregir es en el mismo destino, generalmente se conocen como técnicas de Corrección de Errores Adelante (Forward Error Correction – FEC), se utilizan técnicas de códigos correctores de errores como el de Hamming y técnicas de Entrelazado

Fundamentos de Protocolos

Edwin Montoya

3

CÓDIGO CORRECTORES DE ERRORES - HAMMING • Se tieneunidades de datos de m bits, adicionamos r bits redundantes, entonces la longitud total es: n = m + r. • Palabra códido = datos + bits redundantes. • La cantidad de bits en los que difieren DOS palabras código, se le conoce como DISTANCIA HAMMING d. • Si dos palabras código están tienen una distancia d, se requieren d errores de bit para convertir una en la otra • Normalmente todas lascombinaciones de 2^m son posibles, pero dependiendo de la forma en como se calculan los bits redundantes, no será posible que se de todas las 2^n combinaciones.
Fundamentos de Protocolos Edwin Montoya

HAMMING (cont.) • La propiedad de detección y corrección dependen de su distancia: • PARA DETECTAR d ERRORES se necesita un código con distancia d+1 • PARA CORREGIR d ERRORES se necesita un código condistancia 2d+1 • Por ejemplo con PARIDAD par o impar, que es un código de un bit, tiene una distancia 2. • Ejemplo de corrección: código con 4 palabras válidas: 00000000, 11110000, 00001111, 11111111. • El código tiene una distancia d = 5, lo que significa que puede corregir errores dobles
Fundamentos de Protocolos Edwin Montoya

4

CORRECCIÓN DE ERRORES MEDIANTE RETRANSMISIÓN • Las técnicas decorrección mediante Retransmisión, consiste en que el receptor informa al transmisión por el éxito o fracaso de la transmisión. • Los protocolos en los cuales el receptor envia un reconocimiento POSITIVO, suele llamarse PAR (positive acknowledgment with retransmission) o ARQ (automatic repeat request) • El transmisor debe activar temporizadores de espera de ACKs o NAKs, si expira este timer, se...