Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES UNIDAD 6: Errores en la transmisión de datos Control de Errores en la transmisión de datos Tipos de Errores y Tasa de Errores en la transmisión de datos: BER Códigos usados en transmisión de datos. Códigos ASCII y EBCDIC Métodos de Detección de Errores: Redundancia, Cuenta Exacta Métodos de Detección y Corrección de Errores Control de Paridad, VRC, LRC Detección de Errores por el método de redundancia cíclica (CRC). Algoritmo CRC. Métodos de Corrección de Errores Técnicas de control de errores. ARQ, Parada y Espera, Transmisión Continua FEC - Forward Error Correction Distancia Hamming - Códigos auto correctores Hamming. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Control de Errores en la transmisión de datos Un sistema de comunicación está expuesto a que ocurran errores durante la transmisión e interpretación de los datos, en especial por problemas de ruido que afectan a las diversas partes del sistema, principalmente a los canales de transmisión. Es necesario entonces, desarrollar e implementar procedimientos para el control de estos errores. El control de errores consta de dos partes: La detección de errores La corrección de errores Una forma de disminuir, detectar y corregir errores de transmisión es enviar datos adicionales en el contenido del mensaje (redundancia). Aunque se logra una mayor protección contra errores, cuanto mayor es la cantidad de bits adicionales que no llevan información, la eficiencia del proceso de transmisión disminuye. Cuanto más pequeños sean los bloques, menos probable será la necesidad de retransmitirlos, pero la eficiencia de la transmisión disminuye apreciablemente. Cuando más largos, con el objeto de aumentar la eficiencia, una mayor proporción de estos bloques tendrán errores y será necesario retransmitirlos, lo que a largo plazo puede disminuir aún más su eficiencia. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES El control de errores implica técnicas de diseño, fabricación de equipos y enlaces de transmisión de datos que reduzcan el porcentaje de errores. Además incluye metodologías para detectarlos y corregirlos. Una metodología posible es no tomarlos en cuenta. Esto parece algo trivial, pero no lo es tanto si se considera que en muchos casos, por el tipo de información a transmitir y el uso que la misma recibirá, no es necesario que los errores sean tenidos en cuenta. Esta metodología reduce los costos aumenta el procesamiento total. El proceso de monitorear la información recibida y determinar cuando un error de transmisión ha ocurrido se denomina control del error. Las técnicas usadas para la detección de errores no identifican cual bit es erróneo, solamente se indica que un error ha ocurrido. El propósito de la detección de errores no es impedir que éstos ocurran, pero previene que los errores detectados no ocurran. Control de Errores en la transmisión de datos UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Según su distribución en el tiempo, los errores se pueden clasificar en los siguientes tipos: Errores simples o aislados: son aquellos que afectan a un solo bit cada vez y, además son independientes entre sí en cuanto al momento de ocurrencia. Errores en ráfagas: son aquellos que afectan a varios bits consecutivos y ocurren en períodos indeterminados de tiempo. Errores agrupados: son aquellos que ocurren en tandas sucesivas de una cierta duración y que no afectan necesariamente a varios bits seguidos Tipos de Errores: UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Tipos de Errores: 0.5 seg Velocidad R=600 bps Ruido impulsivo con duración de 0.5 seg Velocidad R=1200 bps Se pierden 600bps*0,5seg=300 bits Se pierden 1200bps*0,5seg=600 bits UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Tasa de Errores en la transmisión de datos: BER La tasa de errores relaciona la cantidad de bits recibidos con error en el receptor con la cantidad total de bits transmitidos en un determinado tiempo o sesión. Se la denomina VER (Bit Error Rate) y su valor es típico para cada medio de transmisión en particular. Ejemplo: Una computadora recibe desde una fuente remota, un total de 2Mbit que corresponden a un archivo y a los datos de control para su transmisión. Si durante la transmisión se produjeron 20 bits erróneos, determinar la tasa de errores de dicha transmisión: ିହ UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES En la actualidad, las redes telefónicas han mejorado la calidad de sus medios de transmisión y tienen tasas típicas de 10-6 BER. En las redes de área local, donde las distancias son más cortas y la construcción de las redes es más exigente y con pares trenzados de cobre, las tasas de errores son mucho menores y del orden de 10-8 a 10-9 BER. Si se emplean fibras ópticas, la tasa de error pude alcanzar hasta 10-11 BER. Tipo de canal Velocidad bps Tasa de errores BER Línea de grado voz 2400 1:50Kb 2.10-5 9600 1:20Kb 5.10-5 14400 1:10Kb 10-4 28800 1:10Kb/100Kb 10-4/10-5 Línea digital tecnología ATM 155 Mbps a 1:100Mb 10-8 622 Mbps 1:1Gb 10-9 Línea digital “Frame Relay” 2 Mbps 1:10Mb 10-7 1:100Mb 10-8 Télex 50 1:50Kb 2.10-5 La calidad de los sistemas de transmisión digital puede ser ponderad por tu tasa de errores BER como: Sistemas muy buenos 10-9 a 10-10 Sistemas buenos 10-6 Sistemas degradados 10-3 a 10-6 Sistemas dañados >10-3 Tasa de Errores en la transmisión de datos: BER UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES ASCII es un conjunto de caracteres de 7 bits que tiene 128 combinaciones. El bit menos significativo (LSB) se designa b0 y el mas significativo (MSB) se designa b6. El bit b7 no es parte del código reservándose para el bit de paridad. Código ASCII: American Standard Code for Information Interchange https://elcodigoascii.com.ar/ UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES EBCDIC es un código binario que representa caracteres alfanuméricos, controles y signos de puntuación. Cada carácter está compuesto por 8 bits = 1 byte, por eso EBCDIC define un total de 256 caracteres. Este código se originó con el System/360 y aún se usa en mainframes IBM y en la mayoría de los computadores de medio rango de IBM EBCDIC: Extended Binary Coded Decimal Interchange Code UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Si en un código binario de longitud constante se utilizaran todas las combinaciones posibles de sus N dígitos binarios (2N), resultaría imposible detectar si se ha producido error, ya que una combinación del código se transformaría en otra que también pertenece a él. Esto quiere decir, que la posibilidad de detectar errores se logra no utilizando todas la combinaciones posibles, de forma que al recibir una determinada combinación se puede identificar como errónea si no pertenece al código SIMBOLO BCD Natural A 0 0 0 B 0 0 1 C 0 1 0 D 0 1 1 F 1 0 0 G 1 0 1 H 1 1 0 I 1 1 1 CANAL ? Detección de Errores UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Queremos transmitir dígitos decimales para lo que usamos el código BCD natural. En éste no se emplean más que 10 de las 16 combinaciones posibles con 4 dígitos binarios. Supongamos que se emite la combinación 0011 y tras producirse error en un dígito binario durante la transmisión se recibe la 1011; como no pertenece al código utilizado es inmediato deducir que nunca ha podido ser transmitida, por lo que el error será detectado. Sin embargo, esta condición es necesaria pero no suficiente. Supongamos ahora que al transmitir la combinación 0011 se produce el error en el primer dígito, recibiendo la 0010. Como también pertenece al código el centro receptor la considerará correcta, identificando, erróneamente,al dígito decimal 2 como el mensaje emitido. Se deduce intuitivamente que la condición necesaria y suficiente para poder detectar error en un dígito binario es que toda combinación del código se transforme, al variar uno cualquiera de sus dígitos, en una combinación que no pertenezca al código. Detección de Errores UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Detección de Errores: Redundancia El mecanismo más inmediato es la simple repetición de cada símbolo transmitido un número n de veces. Si los n símbolos recibidos son iguales, se supondrá que en ninguna de las transmisiones ha existido error y, por lo tanto, el centro receptor identificará como símbolo transmitido el n veces repetido. Si los n símbolos recibidos no son todos iguales, implicará error en alguna de las transmisiones y se identificará como símbolo transmitido más probable al que aparezca repetido más veces en la recepción. Vista la mejora de la fiabilidad de la transmisión, es fácil de inducir que la probabilidad de error disminuirá con el número de repeticiones, pero a costa de incrementar el tiempo de la transmisión, por lo que el procedimiento repetitivo descrito plantea un compromiso entre la velocidad de los mensajes y su fiabilidad UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Detección de errores: Codificación de cuenta exacta En esta técnica de codificación de cuenta exacta, lo que se hace es configurar el código de manera que cada carácter esté representado por una secuencia de unos y ceros que contiene un número fijo de unos, por ejemplo tres de ellos. En caso de recibirse un carácter cuyo número de unos no sea tres, se tratará de un error. Es claro que este método, al igual que los demás, tiene limitaciones: cuando se recibe un 0 en vez de un 1 y a la vez un 1 en vez de un 0 dentro del mismo carácter los errores no serán detectados. Ésta no es la única posibilidad de errores indetectados. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección y Corrección de Errores UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Control de Paridad Concepto de paridad: Se dice que una combinación binaria tiene paridad par si el número de unos de esa combinación es par. Se dice que una combinación tiene paridad impar si su número de unos es impar. Es el esquema de detección de error más usado para los sistemas de comunicación de datos y se usa con chequeo de redundancia vertical y horizontal. Con la paridad, un solo bit (el bit de paridad) se agrega a cada caracter para forzar el total de números unos en el caracter, incluyendo el bit de paridad, para que sea un número impar (paridad impar) o un número par (paridad par). Para detectar si existe o no error en la palabra de código recibida, se comprueba si ésta cumple el criterio de paridad preestablecido, si es así se supondrá que no ha existido error en la transmisión, si no es así es que algún dígito ha variado de valor, no podemos saber cual es, pero sí que ha existido error. Dígito decimal Digito de paridad BCD Natural 0 0 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 0 3 0 0 0 1 1 4 1 0 1 0 0 5 0 0 1 0 1 6 0 0 1 1 0 7 1 0 1 1 1 8 1 1 0 0 0 9 0 1 0 0 1 UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Control de paridad vertical (VRC) Conocido como VRC (Vertical Redundancy Check), se aplica a cada carácter o byte, y su uso está relacionado fundamentalmente con el código ASCII. Consiste básicamente en añadir un bit adicional al conjunto de 7 bits que constituyen el carácter en el código mencionado. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Control de paridad vertical (VRC) El grave inconveniente de este método es que no se puede detectar la doble inversión de bits, que se produce cuando hay un doble error en un byte que afecta simultáneamente a dos unos, transformándolos en cero, o viceversa. Si esto ocurre, la paridad resultante del carácter será correcta, pero evidentemente el dato transmitido es erróneo Sin embargo, este sencillo sistema permite que en una línea telefónica discada que transmite entre 103 y 104 bps con una tasa de error (BER) de 10-5 mejore a 10-7. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Control de paridad longitudinal (LRC) La paridad LRC (Longitudinal Redundancy Check) denominada longitudinal u horizontal (HRC) utiliza el mismo esquema anterior, con la diferencia que el control de la paridad se realiza en cada una de las posiciones correspondientes de los bits del grupo de caracteres de datos con lo que se forma un bloque de bits de paridad o carácter de paridad que se agrega como bits redundantes a la cadena de caracteres de datos para el control. Al finalizar el bloque de N caracteres, se transmitirá un carácter completo denominado Carácter de Control del Bloque, más conocido por su expresión en inglés Block Check Carácter (BCC). UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Control de paridad longitudinal (LRC) El transmisor realiza el cálculo de la paridad en cada carácter y luego para todo el bloque generando un BCC que se transmite en esta cadena de bytes. El receptor, cuando recibe esta cadena, recalcula la paridad de los bytes de datos y la BCC. Si los BCC son iguales, se da por aceptado el bloque de caracteres, caso contrario, se notifica por algún método al transmisor del error ocurrido en la cadena. Históricamente entre el 75 y el 98% de los errores presentes son detectados por LRC, los que pasan desapercibidos se deben a limitaciones propias del método, así por ejemplo un error en b2 en dos diferentes caracteres simultáneamente produce un LRC válido. BCC o UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Control de paridad bidimensional (VRC/LRC) La combinación de los dos métodos VRC y LRC proporciona mayor protección y no supone gran consumo de recursos y, aunque tiene la misma sencillez conceptual de los métodos de paridad lineal, es más complicado y por ello menos popular El uso simultáneo de VRC y LRC hace que pasen indetectados errores en un número par de bits que ocupan iguales posiciones en un número par de caracteres, circunstancia muy poco probable. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES CANAL Métodos de Detección: Control de paridad bidimensional (VRC/LRC) Ejemplo: Bytes recibidos con un bit de error en la posición de la fila 4, columna 6 de la tabla de bits Al efectuar el control de la paridad VRC y LRC en el receptor, se verifica un error VRC en el D6 y un error LRC en la posición del B4 que sirve para determinar en forma matricial que hay un error en esa posición de la cadena transmitida. En caso que se trate de un solo error el uso simultáneo de VRC y LRC permite determinar con precisión cual es el bit erróneo y por lo tanto corregirlo. Otras combinaciones de errores pueden ser detectadas y algunas además corregidas. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Código de Redundancia Cíclica - CRC Los métodos basados en el uso de paridad son sencillos de comprender y de implementar, suministran cierto grado de protección contra los errores pero son limitados y su efectividad es cuestionable en determinadas aplicaciones. Por ello se utilizan solamente cuando resulta muy complicado ó muy costoso implementar otros métodos. Además, el de paridad vertical requiere que cada carácter lleve su protección contra errores, lo que lo hace adecuado en entornos asíncronos, en entornos síncronos el uso de tantos bits de detección de errores consume un porcentaje importante de la capacidad del canal y resulta oneroso. Por ello es necesario, en entornos síncronos, emplear métodosque tengan en cuenta dos factores importantes: 1. Detección más segura de los errores. Dado que los datos se envían en bloques un solo error corrompe toda la información contenida en él, que es considerable, además muchas veces los errores se presentan en “ráfagas”, por ello se requieren esquemas más poderosos. 2. Eficiencia. No se deben consumir demasiados recursos dejando libre la mayor parte del canal para datos. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Detección: Código de Redundancia Cíclica - CRC El método se basa en la detección de errores por medio de operaciones aritméticas con polinomios que utilizan la técnica conocida como de módulo 2, en la que no hay términos de acarreo para la suma, ni de préstamo para la resta. Estas operaciones son realizadas con circuitos digitales convencionales que ejecutan la función OR EXCLUSIVA Para una mayor comprensión de lo expuesto, se muestra una operación de suma/resta y luego otra de división: Ejemplo de división G(x) C(x) R(x) P(x) UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES 1. Definimos un polinomio M(x) de grado n con los bits del mensaje a transmitir. 2. Definimos un polinomio G(x) de grado r (generador). 3. Definimos un polinomio auxiliar de valor X r de grado r más alto que tenga G(x). El grado n del polinomio M(x) debe ser: n>>r grado del polinomio G(x) 4. Se forma un nuevo polinomio que contenga (r+n) bits, de la forma P(x) = X r .M(x). 5. Se divide el nuevo polinomio formado de la forma P(x) = X r .M(x) por el polinomio generador G(x). De dicha división se obtendrá un polinomio resto R(x) que siempre debe tener un número de bits menor o igual que r, grado del polinomio G(x). 6. Finalmente, se procede a obtener un polinomio que denominaremos: T(x)= P(x) + R(x), que es el polinomio a transmitir. 7. Se transmite T(x) y se recibe T´(x) = T(x) + E(x), donde E(x) seria el error provocado por el canal. 8. Finalmente en el receptor se realiza la operación T´(x)/ G(x) y se obtendrá un R(x). Si R(x)=0 NO hay error, caso contrario los datos recibidos poseen error Métodos de Detección: Código de Redundancia Cíclica - CRC UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES 1. Consideremos la cadena de bits a transmitir como el conjunto de coeficientes de un polinomio, por ejemplo si enviamos 10110111, el polinomio equivalente es: M(x) = 1 x7 + 0 x6 + 1 x5 + 1 x4 + 0 x3 + 1 x2 + 1 x1 + 1 x0 10110111 = M(x) = x7 + x5 + x4 + x2 + x1 + x0 Métodos de Detección: Código de Redundancia Cíclica - CRC 2. Debemos ahora especificar la clave para efectuar la división. La selección de esta clave es esencial para la capacidad de respuesta del código frente a los diversos tipos de errores. Ejemplo: 110011 = G(x) = x5 + x4 + x1 + x0 3. Definimos el polinomio auxiliar: Ejemplo: X r = x5 4. Se forma un nuevo polinomio que contenga (r+n) bits, de la forma P(x) = X r .M(x): x5(x7 + x5 + x4 + x2 + x1 + x0) = x12 + x10 + x9 + x7 + x6 + x5 = 1011011100000 UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES 1011011100000 110011 110011 1101011 0111101 110011 00111010 110011 00100100 110011 0101110 110011 0111010 110011 001001 5. Se divide el nuevo polinomio formado de la forma P(x) = X r .M(x) por el polinomio generador G(x): Métodos de Detección: Código de Redundancia Cíclica - CRC G(x)P(x) R(x) UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES 6. Finalmente, se procede a obtener un polinomio T(x)= P(x) + R(x): P(x) 1011011100000 R(x) 1001 T(x) 1011011101001 que es el polinomio a transmitir. 1011011101001 110011 110011 1101011 0111101 110011 00111010 110011 00100110 110011 0101010 110011 0110011 110011 000000 G(x)T´(x) R(x) Métodos de Detección: Código de Redundancia Cíclica - CRC 7. Finalmente en el receptor se realiza la operación T´(x)/ G(x) y se obtendrá un R(x). Si R(x)=0 NO hay error Si R(x) 0 SI hay error UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES El polinomio generador La selección del polinomio generador es esencial si queremos detectar la mayoría de los errores que ocurran Ejemplos de polinomios generadores (estándares internacionales): CRC-12: x12+ x11 + x3 + x2 + x + 1 CRC-16: x16+ x15 + x2 + 1 CRC-CCITT: x16+ x12 + x5 + 1 »100% errores simples »100% errores dobles »100% errores en un número impar de bits »100% errores en ráfagas de igual a o menos de 16 bits »99.997% errores de ráfagas de 17 bits »99.998% de errores en ráfagas de 18 o más bits Métodos de Detección: Código de Redundancia Cíclica - CRC UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Hasta aquí hemos considerado solamente la detección de los errores, sin embargo, a partir de la verificación de la existencia de los mimos, se pueden adoptar dos posturas diferentes: No tomarlos en cuenta Corregirlos Métodos de Corrección de Errores Existen dos estrategias fundamentales para la corrección de errores: 1. Corrección hacia atrás. Requerimiento automático de repetición: ARQ (Automatic Request for Repeat). 2. Corrección hacia delante. Corrección de errores hacia adelante: FEC (Forward Error Correction). Si bien resulta casi imposible corregir la totalidad de los errores, la mayoría de las técnicas que normalmente se emplean, como se ha visto anteriormente, llegan a corregir el 99,99% de los mismos. En algunas aplicaciones, la no corrección de errores, puede producir problemas graves. Imaginemos, por ejemplo, una aplicación bancaria y nos daremos cuenta de los daños que se podrían producir si no se resuelve adecuadamente la corrección de los errores. De ahí la importancia de este tema en el diseño de cualquier sistema. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: Corrección hacia atrás Requerimiento automático de repetición: ARQ (Automatic Request for Repeat): Consiste en el uso de sistemas de detección de errores. Cuando se detecta un error en el equipo receptor, éste solicita al equipo transmisor la repetición del bloque de datos transmitidos. De ahí la llamada corrección hacia atrás Este sistema implica la retransmisión de los datos tantas veces como sea necesario, hasta que sean recibidos libre de errores. La corrección por retransmisión requiere una tecnología sencilla y poca capacidad de memoria. Una vez detectada la existencia de un error (por intermedio del o los bits de paridad o por códigos de redundancia cíclica), el método consiste en pedir la retransmisión del carácter o grupos de caracteres hacia el receptor Parada y Espera Transmisión Continua Ir N bloques atrás Retransmisión selectiva ARQ UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Cuando el emisor envía una trama, espera a recibir una respuesta de confirmación (ACK) de la trama desde el receptor. Cuando recibe esa respuesta, envía la siguiente trama (FRAME) Si no llega la respuesta dentro de un tiempo límite (time-out), el emisor procede a reenviar la trama anterior (control de errores, interpreta que la trama no llegó a su destino). Si se recibe una trama de no aceptación o rechazo (NACK) se interpreta que la trama anterior no era válida, y que el receptor está preparado para recibir. El emisor reemite la trama anterior. Métodos de Corrección de Errores: ARQ - Parada y Espera UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: ARQ - Transmisión Continua Se caracteriza por la transmisión de tramas consecutivas eliminando o disminuyendo las paradas en espera de confirmaciones. Se define por protocolo la cantidad máxima de tramas que pueden ser enviadas sin recibir confirmación (ancho de la ventana de transmisión) Es preciso numerar las tramas, destinando para ello un campo en el encabezamiento de lamisma. Ir N bloques atrás No es obligatorio dar asentimientos trama a trama. La confirmación positiva de la trama “N” implica también la confirmación positiva de todas las anteriores. Recibir el NAK de la trama “N” equivale a confirmar positivamente las tramas anteriores y hacer repetir las transmisiones de las tramas a partir de la rechazada. Las tramas quedan ordenadas en el buffer de recepción. Pérdida de eficiencia por descartar tramas que pudieran haber llegado correctamente. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: ARQ - Transmisión Continua Retransmisión selectiva Si un receptor recibe una trama dañada, envía el NAK para la trama en la que se detecta un error o daño. El número NAK, como en go-back-n también indica el reconocimiento de las tramas recibidas anteriormente y el error en la trama actual. El receptor sigue recibiendo los nuevos cuadros mientras espera que el cuadro dañado sea reemplazado. Las tramas que se reciben después de la trama dañada no se reconocen hasta que la trama dañada ha sido reemplazada. Alcanza mayor eficiencia en el uso del medio de transmisión Se puede recibir una trama fuera de orden, al ordenar, si se omite un número de trama, el receptor reconoce que se perdió una trama y envía NAK para esa trama al remitente. Después de recibir NAK para el cuadro perdido, el remitente busca ese cuadro en su ventana y lo retransmite. Si se pierde la última trama transmitida, el receptor no responde y este silencio es un reconocimiento negativo para el emisor. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: FEC - Forward Error Correction Este técnica se denomina también FEC (Forward Error Correction), se basa en el uso de códigos auto correctores que se diseñan sobre la base de sistemas de codificación redundante y corrigen los errores detectados en la misma estación que recibe el bloque de datos. Aunque estos métodos hacen innecesaria la retransmisión, no son neutros al usuario, pues para posibilitar la corrección en destino deben enviar un número de bits varias veces superior al que se necesita cuando se utilizan códigos convencionales. Sin embargo, en muchas aplicaciones es necesario el uso de este tipo de código porque no resulta posible o conveniente pedir la retransmisión de los datos, ya sea por razones de seguridad o por necesidades de la misma operación del sistema informático asociado Se define como el número de bits que tienen que cambiarse para transformar una palabra de código válida en otra palabra de código válida. Si dos palabras de código difieren en una distancia d, se necesitan d errores para convertir una código válida en la otra código válida. Cuanto mayor sea esta diferencia, menor es la posibilidad de que un código válido se transforme en otro código válido por una serie de errores. Por ejemplo la distancia Hamming entre 1011101 y 1001001 es 2 2143896 y 2233796 es 3 "tener" y "reses" es 3 {100, 111, 011} mín {d(100, 111), d(100, 011), d(111, 011)} = mín {2, 3, 1} = 1 Métodos de Corrección de Errores: Distancia Hamming UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Propiedades para la detección de errores: Para detectar d errores de un bit entre dos palabras, es necesario un código con una distancia de Hamming de al menos d+1 De otra forma: Con una distancia de Hamming de d se pueden detectar d-1errores Ejemplo: C = {001, 010, 100}, d. Hamming = 2 Un error aislado siempre se detecta: un error en 001 101, 011, 000, entonces C Dos errores aislados no se detectan: dos errores en 001 111, 010, 100. Dos ϵ a C Métodos de Corrección de Errores: Distancia Hamming UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: Distancia Hamming Propiedades para la corrección de errores: Para corregir d errores de un bit entre dos palabras, es necesario un código con una distancia de Hamming de al menos 2d+1 De otra forma: Con una distancia de Hamming de d se pueden detectar (d-1)/2 errores Ejemplo: C = {0000000000, 0000011111, 1111100000, 1111111111} d. Hamming = 5 Se pueden detectar d-1 = 5-1 = 4 errores Se pueden corregir (d-1)/2 = 4/2 = 2 errores UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Mínima Distancia de un Código Sea M la mínima distancia de un código, de modo que: M-1 = cap. de Detección + cap. de Corrección M-1 = D + C para D C Ejemplos: Con M=2 (control de Paridad) 2-1 = 1 = D+C D=1 y C=0 (detecto pero no corrijo) Con M=3 (Redundancia) 3-1 = 2 = D+C D=2 y C=0 (detecto 2 pero no corrijo) D=1 y C=1 (detecto y corrijo un error) Con M=4 4-1 = 3 = D+C D=3 y C=0 (detecto 3 pero no corrijo) D=2 y C=1 (detecto 2 y corrijo 1 error) UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: FEC - Codificación Hamming Los códigos de Hamming están basados en la adición de p bits a un código de distancia Hamming unidad y de n bits, obteniéndose un nuevo código de n + p bits. En este nuevo código se realizan p detecciones de paridad en bits seleccionados de la cadena, obteniéndose un bit de paridad uno o cero según el número de bits sea par o impar. El conjunto de los p bits de paridad forma un número en el sistema binario natural, cuyo equivalente decimal nos indica la posición del bit erróneo. En caso de que no exista error, dicho número debe ser cero. El número p de bits añadidos ha de ser suficiente para permitir la detección y la ausencia de error en las n + p posiciones. Dado que con p bits se obtienen 2p combinaciones, se debe cumplir la relación: 2p >= n + p +1 La posición de estos bits de paridad en la cadena de bits, están en relación al valor 20, 21, 22, 23 y así sucesivamente, o sea posiciones 1, 2, 4, 8 …. UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: FEC - Codificación Hamming n+p n7 n6 n5 p4 n4 n3 n2 p3 n1 p2 p1 posición decimal 11 10 9 8 7 6 5 4 3 2 1 posición en binario 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 n 1 0 0 1 1 0 1 p1 1 0 1 0 1 1 p2 1 0 1 1 1 0 p3 1 1 0 0 p4 1 0 0 1 n+p a TX 1 0 0 1 1 1 0 0 1 0 1 n7 n6 n5 p4 n4 n3 n2 p3 n1 p2 p1 11 10 9 8 7 6 5 4 3 2 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 n+p a RX 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 SIN ERROR UNIDAD 6: Errores en la transmisión de datos UTN-FRT – ISI - COMUNICACIONES Métodos de Corrección de Errores: FEC - Codificación Hamming n+p n7 n6 n5 p4 n4 n3 n2 p3 n1 p2 p1 posición decimal 11 10 9 8 7 6 5 4 3 2 1 posición en binario 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 n 1 0 0 1 1 0 1 p1 1 0 1 0 1 1 p2 1 0 1 1 1 0 p3 1 1 0 0 p4 1 0 0 1 n+p a TX 1 0 0 1 1 1 0 0 1 0 1 n7 n6 n5 p4 n4 n3 n2 p3 n1 p2 p1 11 10 9 8 7 6 5 4 3 2 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 n+p a RX 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 HAY ERROR
Compartir