Corrección y Detección de ErroresCorrección y Detección de Errores
Profesora Maria Elena [email protected]@ciens.ucv.ve
Comunicación de Datos
Error en un Bit de una TramaError en un Bit de una Trama
Comunicación de Datos
Errores en Múltiples Bits de una Trama: E Ráf (b t )Errores en Ráfagas (burst error)
Comunicación de Datos
Codificación por Bloques:
• Cada bloque de k bits es codificado con un bloque de n
Códigos para la detección de errores
q qbits denominado palabra código (codeword).
• La palabra código es la que se transmite.• En el receptor varias cosas pueden pasar:• En el receptor varias cosas pueden pasar:
– Si no hay errores, la salida de decodificador es igual al código original.Para ciertos errores el decodificador puede detectar y corregir– Para ciertos errores, el decodificador puede detectar y corregir los mismos.
– Para ciertos patrones de errores, el decodificador puede detectar el error pero no corregirlo.p g
– Para ciertos errores el decodificador no puede detectar el error y produce una señal de salida que difiere de la original.
Comunicación de Datos
Detección/Corrección de ErroresDetección/Corrección de Errores
Palabra código
Comunicación de Datos
Aritmética Módulo N, N=2Aritmética Módulo N, N 2
Comunicación de Datos
P i i i d l d t ió dPrincipios de la detección de errores• El algoritmo suma (n-r) bits al bloque de datos de k bits.• Los k bits en la señal original se transmiten en la palabra código de
n bits.• La distancia de Hamming, d(v1,v2) se define como el número de
bit l l 1 2 difibits en los cuales v1 y v2 difieren.• La distancia mínima para una palabra código que consiste de
w1,w2, …ws donde s = 2m .dmin = min [d(wi wj)]dmin = mini≠j [d(wi,wj)]
• Por ejemplo, si v1 = 011011 y v2 = 110001 d(v1,v2) = 3• La función de la forma vc = f(vd) donde vd es un vector de data de k
bits y vc la palabra códigobits y vc la palabra código.• El radio de redundancia (ie redundancia) es (n-k)/k.• La tasa del código es k/n y mide la cantidad adicional de ancho de
banda que se necesita
Comunicación de Datos
banda que se necesita.
Principios de la detección de errores
• Las siguientes consideraciones se deben tener gen el diseño de un código:– Dado k y (n-k), nos gustaría el valor mas grande de
dmin.– El codificador debería ser sencillo requiriendo un
mínimo de memoria y tiempo de procesamiento.– Nos gustaría un pequeño número de extra bits (n-k),Nos gustaría un pequeño número de extra bits (n k),
para reducir el ancho de banda.– Nos gustaría una gran número de extra bits (n-k) para
reducir la tasa de error.educ a asa de e o• Note que los dos últimos objetivos están en
conflicto y deben negociarse.
Comunicación de Datos
Principios de la detección de erroresPrincipios de la detección de errores
• Para detectar d errores se requiere unaPara detectar d errores se requiere una distancia de d+1. Por ejemplo, bit de paridadparidad.
• Para corregir d errores, se requiere una distancia de 2d+1distancia de 2d+1.
Comunicación de Datos
Ejemplo un Código de BloqueEjemplo un Código de Bloque
• El esquema 4B/5B de codificaciónEl esquema 4B/5B de codificación discutido anteriormente es un ejemplo de codificación por bloques En estede codificación por bloques. En este esquema, k=4 y n = 5. Tenemos entonces 2k = 16 y 2n = 32 palabrasentonces 2 = 16 y 2 = 32 palabras códigos. Tenemos 16 de las 32 palabras códigos para la transferenciapalabras códigos para la transferencia de mensajes y el resto son usados para otros procesos o no usados
Comunicación de Datos
otros procesos o no usados.
Proceso de Codificación y Descodificación en l C difi ió Blla Codificación por Bloques
Comunicación de Datos
Códigos de Bloques LinealesCódigos de Bloques Lineales
• En un código lineal por bloques el OREn un código lineal por bloques el OR exclusivo de cualquiera palabra código crea otra palabra código válidacrea otra palabra código válida.
Comunicación de Datos
Bit de ParidadBit de Paridad
• Es un código de detección de erroresEs un código de detección de errores simples con n= k+1 y dmin = 2
Comunicación de Datos
Bit de ParidadBit de Paridad
• Sumar un bit al final • Ventajas:de un bloque de data.
• De forma tal que, el á i
j– Simple
• Desventajas:– Un número par de errorescarácter tiene:
– Un número par de unos (paridad par).
Un número par de errores no se pueden detectar.
• Ejemplos (paridad par):Data = 1110011unos (paridad par).
– Un número impar de unos (paridad impar).
– Data = 1110011– Transmite (A)= 11100111– Llega = 11100101
Cálculo en el receptor (B) =– Cálculo en el receptor (B) = 11100100
– |Distancia A-B| = 2
Comunicación de Datos
Código de Paridad C(5,4)Código de Paridad C(5,4)
Comunicación de Datos
Bit de Paridad: Codificador/DecodificadorBit de Paridad: Codificador/Decodificador
Comunicación de Datos
Bit de ParidadBit de Paridad
• r0 = a3 + a2 + a1 + a1 (módulo-2)r0 = a3 + a2 + a1 + a1 (módulo 2)• Síndrome (calculado por el receptor)
0 b3 b2 b1 b0 0 ( ód l 2)• s0 = b3 + b2 + b1 + b0 + q0 (módulo-2)
Comunicación de Datos
Código de Hamming
• Diseñado para corregir errores de bit simples. • Familia de bloques de corrección de error (n,k) con los siguientes
parámetros:– Longitud del bloque: n = 2m – 1g q– Número de bits de dato: k = 2m – m – 1– Número de bits de chequeo: n – k = m
Distancia mínima: d = 3– Distancia mínima: dmin = 3• En el receptor el resultado de la comparación (XOR de la señal
recibida y otra de la calculada) es realizada.El lt d l b í d• El resultado se conoce como palabra síndrome.
Comunicación de Datos
Código de HammingCódigo de Hamming
• La palabra síndrome tiene un rango de 2(n-k) – 1.p g• 0 indica no error entonces no se cuenta.• Como un error puede ocurrir en los k bits de p
data o (n-k) bits de chequeo:• 2(n-k) - 1 >= k+(n-k) = n• Esto nos permite calcular el número de bits de
chequeo.
Comunicación de Datos
Códi d H iCódigo de Hamming• Codificación: k bits de datos + (n -k) bits de chequeo.• Decodificación: compara los (n-k) bits recibido con los (n -k) bits
calculados bits usando XOR.• Los (n-k) bits resultantes se llaman palabra síndrome.• El rango del síndrome esta entre 0 y 2(n-k)-1.• El síndrome indica:
– Si contiene solo 0s, no se han detectados errores.– Si el síndrome contiene un solo bit en 1 entonces un error ha
ocurrido en uno de los bits de chequeo. Por lo tanto, no se requiere corrección.Si l í d ti á d bit 1 t l l– Si el síndrome contiene más de un bit en 1, entonces el valor numérico del síndrome indica la posición de un bit de data en error. El bit en error es invertido para su corrección.
Comunicación de Datos
Código de Hamming-EjemploCódigo de Hamming EjemploBloque de datos = 00111001
Comunicación de Datos
Código de Hamming-EjemploCódigo de Hamming Ejemplo
Bit con error
Comunicación de Datos
Chequeo Cíclico Redundante (CRC)Chequeo Cíclico Redundante (CRC)
• Para un bloque de k bits, el i
• Lógica aritméticatransmisor genera una secuencia de n-k = r bits.
• El transmisor transmite una secuencia de n bits la cual es
– T = trama de n bits.– M= mensaje de k bits.– F = secuencia FCS de n-k
bitssecuencia de n bits, la cual es exactamente divisible por un número.
• La secuencia de n-k bits se
bits.– P = divisor con un patrón
predeterminado. Tiene (n-k)+1 bits.
llama secuencia de chequeo de trama (frame check sequence, FCS).
Comunicación de Datos
Ch Cí li R d d t (CRC)• El objetivo es que T/P no tenga resto.
Chequeo Cíclico Redundante (CRC)
• Es claro que:T = 2rM + F– 2rM desplaza el mensaje a la izquierda y lo rellena con ceros (0).
• Dividir 2rM entre P:2rM/P= Q + R/P
• Usemos R como el FCST = 2rM + R y T/P = 2rM /P+ R/P = Q + (R/P + R/P) = Q
• Así que no hay resto.• Esto es por la suma modulo 2 basada en la operación OR-exclusivo:
0 ⊕ 0 = 0 0 ⊕ 1 = 1 1 ⊕ 0 = 1 1 ⊕ 1 = 0.• Entonces, dividir 2rM entre P y usar el resto como el FCS.
Comunicación de Datos
Representación PolinomialRepresentación Polinomial
Comunicación de Datos
CRC: EjemploCRC: Ejemplo
• M = 1001 (4 bits) <-> X3+1M = 1001 (4 bits) < > X +1• P = 1011 (4 bits) <-> X3+X1+1
FCS ?• FCS = ?• K = 4• n- k +1 = 4• n - k= r =3n k r 3• Genere el mensaje a ser transmitido.
Comunicación de Datos
CRC: Ejemplo - TransmisorCRC: Ejemplo Transmisor
Comunicación de Datos
CRC: Ejemplo - ReceptorCRC: Ejemplo Receptor
Comunicación de DatosCaso 1 Caso 2
CRC usando Lógica Digital
• El circuito consiste de:El circuito consiste de:– Compuertas XOR
• Hasta n – k compuertas XOR• Hasta n – k compuertas XOR• La presencia o ausencia de una compuerta se
corresponde con la presencia de un término del divisor polinomial P(X).
– Un registro de desplazamiento• Un serie de dispositivos de memoria de 1 bit.• Los registros contienen n-k bits, igual a la longitud
del FCS
Comunicación de Datos
del FCS.
Circuito del EjemploCircuito del Ejemplo
Comunicación de Datos
Otro Ejemplo: P(X) = X5+X4+X2+1 (generador predeterminado)
Comunicación de Datos10.31
Chequeo Cíclico Redundante (CRC)Chequeo Cíclico Redundante (CRC)
• Se puede demostrar que los siguientes errores son detectables:– Si el generador tiene mas de un término y el coeficiente x0 es 1
todos los errores sencillos pueden ser detectados.– Si el generador no puede dividir a xt + 1
(t t 0 1) t d l i l d d d bit d(t entre 0 y n – 1), todos los errores aislados de dos bits pueden ser detectados.
– Un generador que contiene un factor de x + 1 puede detectar números impares de erroresx + 1 puede detectar números impares de errores.
– Todos los errores en ráfaga con L <= r serán detectados.– Todos los errores en ráfaga con L = r + 1 serán detectados con
probabilidad 1 – (1/2)r–1.probabilidad 1 (1/2) .– Todos los errores en ráfaga con L > r + 1 serán detectados con
probabilidad1 – (1/2)r.
Comunicación de Datos
CRC: Características DeseablesCRC: Características Deseables
• Un buen generador polinomial necesita tener las siguientes características:
• Debería tener al menos dos términos• El coeficiente del termino x0 debería ser 1.• No debería ser divisible entre xt + 1, para t
entre 2 y n − 1.• Debería tener el factor x + 1Debería tener el factor x + 1.
Comunicación de Datos
Generadores Polinomiales EstándaresGeneradores Polinomiales Estándares
Comunicación de Datos
Corrección de ErroresCorrección de Errores
• Las técnicas de detección de erroresLas técnicas de detección de errores combinadas con las técnicas de ARQ (retransmisiones) son inadecuadas en ( )ambientes inalámbricos porque:
La tasa de error de bit es alta.En algunos casos como lo son los satélites el retardo de propagación es largo comparado con el tiempo de transmisión de una tramacon el tiempo de transmisión de una trama.
En estos casos se necesitan usar técnicas capaces de corregir ciertos errores
Comunicación de Datos
capaces de corregir ciertos errores.
Proceso de Corrección de Errores hacia Ad l t (F d E C ti FEC)Adelante (Forward Error Correction, FEC)
Comunicación de Datos
FECFEC
• Las siguientes condiciones se cumplen:– dmin >= 2t+1, el código puede corregir hasta e incluyendo t bits.– dmin >= 2t puede corregir todos los errores <= t-1 bits y los
errores de t bits pueden ser detectados.Otra forma de expresar esta relación es:• Otra forma de expresar esta relación es:– El máximo número de errores corregibles es:
• t=[(dmin-1)/2]• [x] el más grande de los enteros que no excede x[x] el más grande de los enteros que no excede x.
– El máximo número de errores que pueden ser detectados es:• t=dmin-1
Comunicación de Datos
FEC: EjemploFEC: Ejemplo
• k=2 y n=5 Bloque de Palabra Códigok 2 y n 5• Suponga que se
recibe 00100.
datos00 0000001 00111
• El cual es un código inválido.
01 0011110 1100111 11110
• La distancia de Hamming a cada código válido es:
Comunicación de DatosDistancia mínima
FEC: EjemploFEC: Ejemplo
• Observe que dmin entre cada códigoObserve que dmin entre cada código válido es 3 por lo tanto:
Se pueden corregir errores de un bit– Se pueden corregir errores de un bit.– Se pueden detectar errores dobles.
Comunicación de Datos
FEC: EjemploFEC: Ejemplo
Comunicación de DatosObsérvese que si ocurren dos errores no se pueden corregir.
ChecksumChecksum
• Usado en Internet por varios protocolosUsado en Internet por varios protocolos.• No es usado en la capa de enlace.
Comunicación de Datos
ChecksumChecksum
• Supongamos que tenemos una lista de cinco números p g qde 4 bits que queremos enviar a un destino. Además de enviar estos números, le enviamos la suma de los mismos. Por ejemplo, si el conjunto de los números es j p j(7, 11, 12, 0, 6), enviamos (7, 11, 12, 0, 6, 36), donde 36 es la suma de los números originales. El receptor añade los cinco números y compara el resultado con la suma. y pSi los dos son lo mismo, el receptor asume ningún error, acepta los cinco números, y descarta la suma. De lo contrario, hay un error en alguna parte y los datos no , y g p yson aceptados.
Comunicación de Datos
ChecksumChecksum
• Podemos facilitarle el trabajo al receptor siPodemos facilitarle el trabajo al receptor si enviamos el negativo (complemento) de la suma llamada la suma de comprobaciónsuma, llamada la suma de comprobación (checksum). En este caso, enviamos (7, 11 12 0 6 -36) El receptor puede sumar11, 12, 0, 6, 36). El receptor puede sumar todas las cifras recibidas (incluyendo la suma de control) Si el resultado es 0suma de control). Si el resultado es 0, asume que no hubo error, de lo contrario, hay un error
Comunicación de Datos
hay un error.
ChecksumChecksum
• ¿Cómo podemos representar el número 21 en ¿ p paritmética de complemento a uno usando solamente cuatro bits? S l ió• Solución El número 21 en binario es 10101 (que necesita cinco bits) Podemos ajustar el bit más a lacinco bits). Podemos ajustar el bit más a la izquierda y añadirlo a los cuatro bits más a la derecha.
• Tenemos (0101 + 1) = 0110 o 6.
Comunicación de Datos
ChecksumChecksum
• ¿Cómo podemos representar el número -6 en ¿ p pcomplemento a uno usando solamente cuatro bits?
• Solución En complemento a uno, la negativa o complemento deEn complemento a uno, la negativa o complemento de un número se encuentra invirtiendo todos los bits. Positivo 6 es 0110, 6 negativo es 1001. Si consideramos solamente los números sin signo esto es 9 En otrassolamente los números sin signo, esto es 9. En otras palabras, el complemento de 6 es 9. Otra forma de encontrar el complemento de un número en un complemento a la aritmética es restar el número de 2n -complemento a la aritmética es restar el número de 21 (16 - 1 en este caso).
Comunicación de Datos
ChecksumChecksum
• Vamos a repetir el ejercicio anterior usando l tcomplemento a uno.
• El remitente inicializa el control a 0 y suma todos los elementos de datos y la suma de control, checksum (la
d t l id d l t dsuma de control es considerado como un elemento de datos y se muestra en color).
• El resultado es 36. S• Sin embargo, 36 no puede ser expresado en 4 bits. Los dos bits extras se envuelven y se añaden con la suma para crear el valor de la suma envuelta 6. L l t l l d l d• La suma se complementa, en el valor de la suma de comprobación 9 (15 - 6 = 9).
• El remitente envía ahora seis objetos de datos para el t i l d l 9 l h k
Comunicación de Datos
receptor incluyendo el 9 en el checksum.
ChecksumChecksum
• El receptor sigue el mismo procedimiento que el p g p qremitente.
• Suma todos los elementos de datos (incluyendo la suma de control), el resultado es 45.de control), el resultado es 45.
• La suma se envuelve y se convierte en 15. El importe ajustado se complementa y se convierte en 0. D d l l d l d b ió 0• Dado que el valor de la suma de comprobación es 0, esto significa que los datos no están dañado.
• El receptor elimina el control y mantiene los elementos yde datos.
• Si la suma de comprobación, checksum, no es cero, se elimina el paquete.
Comunicación de Datos
elimina el paquete.
ChecksumChecksum
1 11
1 10
Comunicación de Datos
ChecksumChecksum
Remitente: 1. El mensaje se divide en palabras de 16 bits. 2. El valor de la palabra control se establece en 00. 3. Todas las palabras, incluyendo la suma de control se suman utilizando complemento a puno. 4. La suma se complementa y se convierte en la suma de comprobación checksumla suma de comprobación, checksum. 5. La suma es enviado con los datos.
Comunicación de Datos
ChecksumChecksum
Receptor:Receptor: 1. El mensaje (incluido el control) se divide en palabras de 16 bits. p2. Todas las palabras se suman utilizando el complemento a uno. 3 L l t3. La suma se complementa y se convierte en el nuevo checksum. 4 Si el valor de suma de comprobación es4. Si el valor de suma de comprobación es 0, el mensaje es aceptado, de lo contrario, se rechaza
Comunicación de Datos
se rechaza.
ChecksumChecksum
F
F F F F
Comunicación de Datos