CONTROL DE

ERRORES
Redes de Datos I
 • Introducción

CONTROL DE • Detección de errores

ERRORES • Corrección de errores

• Delimitación de tramas

2 Redes de datos I
Introducción

100 bps

El receptor tiene un
reloj sincronizado
Se debe mantener 10 ms con el transmisor
un sincronismo
entre transmisor y
receptor
100 bps

El receptor tiene un
reloj un 5% más
9,5ms rápido que el del
Muestrea en transmisor
el bit anterior
3 Redes de datos I
Introducción

Asincrónica
Bit de 5 a 8 bits de datos Paridad Bits de
inicio parada
(1 o 2)
Reposo Reposo

Bit de Bits de Bit de Bits de

Datos Datos
inicio parada inicio parada

Redes de datos I
Técnicas de comunicación

Sincrónica

Flag Bits de Bits de Flag

Datos
8 bits control control 8 bits

• En la transmisión síncrona, cada bloque de bits se transmite como una cadena

continua sin utilizar códigos de comienzo o parada.

• Los relojes del transmisor y receptor se deberán sincronizar de alguna manera

(reloj independiente o en la misma señal).

• El receptor requiere además que pueda determinar dónde está el comienzo y el

final de cada bloque de datos (preámbulo y final).

• Se añaden otros bits que se utilizan en los procedimientos de control del enlace.
5 Redes de datos I
Errores

Errores

0 1 0 1 1 0 0 1 1 1 0 0

error que altera

Simples 0 1 0 0 1 0 0 1 1 1 0 0
un solo bit

Ráfaga de B bits

Ráfagas 0 1 1 1 0 1 0 0 1 0 0 0

Una ráfaga de longitud B es una secuencia de B bits

en la que el primero, el último y cualquier número
de bits intermedios son erróneos.

6 Redes de datos I
Introducción
Existen dos estrategias básicas para manejar los errores:

• Códigos de detección de errores: incluyen sólo suficiente redundancia para permitir que el
receptor sepa que ha ocurrido un error (pero no qué error) y entonces solicite una
retransmisión.

Se utilizan en conjunto con protocolos ARQ (Automatic repeat request) (enlace o

transporte).

• Códigos de corrección de errores: incluyen suficiente información redundante para que el

receptor pueda deducir cuáles debieron ser los datos transmitidos.

FEC: Forward Error Correction (Corrección de Errores hacia Adelante).

7 Redes de datos I
 • Introducción

CONTROL DE • Detección de errores

ERRORES • Corrección de errores

• Delimitación de tramas

8 Redes de datos I
Detección de errores

Métodos sencillos de detección de errores

Redundancia Envío dos veces el elemento

Ecoplex El receptor reenvía el elemento

Codificación
cuenta Los caracteres tienen número fijo de 1 y 0
exacta

9 Redes de datos I
Detección de errores

Esquema genérico de un sistema de detección de errores

k bits

Datos Datos’ k bits de datos

r bits de verificación
n palabra codificada
E = f(Datos) E’ = f(Datos´) X n=k+r
Tasa de código: k/n
Comparador
r bits
E, E’: códigos de
Datos detección de errores
n bits f : función de código de
detección de errores

Transmisor Receptor
10 Redes de datos I
Detección de errores

0 Paridad par
Paridad 0 1 1 0 1 0 1
1 Paridad impar

LRC 11100111 11011101 00111001 10101001

Longitudinal
11100111
/ Vertical
11011101
Redundancy 00111001
LRC /
Check 10101001
VRC
10101010

11100111 11011101 00111001 10101001 10101010

Datos originales LRC

11 Redes de datos I
Detección de errores

Paridad

12 Redes de datos I
Detección de errores

Compara la suma de los valores de los caracteres

Checksum Se utiliza aritmética complemento a uno, con acarreo

Al resultado, se lo complementa a uno

El receptor realiza la suma, incluido el checksum: el

resultado debería ser todos 1s

En Internet se lo utiliza en protocolos como IP, TCP y UDP,

como suma de palabras de 16 bits

13 Redes de datos I
Detección de errores

Checksum D1 D2 D3 D1+ D2+D3

D1 1001 D2 0001 D3 1001

D1+D2 D1+D2+D3
1001 1010 0011 (complemento a 1)
0001 1001 1 1011
1010 10011 0100

1001 0001 1001 1011

14 Redes de datos I
Detección de errores

• División de polinomios
CRC • Aritmética módulo 2, sin acarreo

0+0 (mod 2) = 0 0-0 (mod 2) = 0

0+1 (mod 2) = 1 0-1 (mod 2) = 1
1+0 (mod 2) = 1 1-0 (mod 2) = 1
1+1 (mod 2) = 0 1-1 (mod 2) = 0

• Representación polinomial
0 1 1 0 1 0 1

0𝑥 6 +1𝑥 5 +1𝑥 4 +0𝑥 3 +1𝑥 2 +0𝑥 1 +1𝑥 0

𝑥5 + 𝑥 4 + 1𝑥 2 + 1𝑥 0

15 Redes de datos I
Detección de errores

Dado un bloque o mensaje de k bits, el transmisor genera

una secuencia de r bits, denominada secuencia de
comprobación de la trama (FCS, Frame Check Sequence),
CRC de tal manera que la trama resultante, con n bits, sea
divisible por algún número predeterminado

k bits r bits

n bits

El receptor dividirá la trama recibida entre ese número y

si no hay resto en la división, supondrá que no ha habido
errores.

16 Redes de datos I
Detección de errores

T: trama de n bits
D F D: mensaje con k bits
F: (n-k) bits de FCS
T P: patrón de n-k+1 bits (divisor)
CRC
𝑇 = 2 𝑛−𝑘𝐷 + 𝐹
• El objetivo es que la división T/P no tenga resto (T divisible entre P).

• Si se divide 2 𝑛−𝑘 𝐷 entre 𝑃 2𝑛−𝑘 𝐷 𝑅

=𝑄+
𝑃 𝑃
• Transmisor: 𝐹𝐶𝑆 = 𝐹 = 𝑅 𝑇 = 2𝑛−𝑘 𝐷 + 𝑅 Resto nulo

• Receptor: 𝑇 2𝑛−𝑘 𝐷 + R 2𝑛−𝑘 𝐷 R 𝑇 R R

= = + =𝑄+ + =𝑄
𝑃 𝑃 𝑃 𝑃 𝑃 𝑃 𝑃

17 Redes de datos I
Detección de errores

Generación
• M(x) : Polinomio con mensaje a transmitir (grado k)
• P(x) : Polinomio generador (grado n)
CRC
• Multiplicar M(x) por xn
• Dividir xn M(x) por P(x)
• Obtener el resto de la división C(x)
• Transmito: F(x) = xn M(x) + C(x)

Recepción
• Recibo F’(x)
• Divido F’(x) por P(x)
• Si el resto es igual a cero, sin errores

18 Redes de datos I
Detección de errores

101000110100000 110101
110101
1101010110
111011
CRC
110101
111010
110101
Transmisor 111110
110101
mensaje D = 1010001101 (10 bits) 101100
patrón P = 110101 (6 bits) 110101
FCS R = a calcular (5 bits) 110010
110101
01110
El mensaje se multiplica por 25 :
101000110100000
y luego se divide por P
T= 101000110101110

19 Redes de datos I
Detección de errores

101000110101110 110101
110101
1101010110
111011
CRC
110101
111010
110101
Receptor 111110
110101
Divido el mensaje recibido por P 101111
Si el resto es nulo, no hubo errores 110101
110101
110101
00000

20 Redes de datos I
Detección de errores

➢ Detecta todos los errores simples, si P(x) tiene mas de un

término y x0 = 1

CRC ➢ Detecta todos los errores dobles, si P(x) no divide a xt + 1

(t entre 0 y n – 1)
➢ Detecta cualquier número de errores impares, si P(x)
contiene (x + 1)
➢ Detecta todas las ráfagas de error de longitud <=n-k
➢ Detecta todas las ráfagas de error de longitud n-k+1, con
probabilidad 1- 2-(n-k-1)
➢ Detecta todas las ráfagas de error de longitud superior a
n-k+1, con probabilidad 1- 2-(n-k)

21 Redes de datos I
Detección de errores

➢ Características deseables de un polinomio generador:

➢ Contener al menos dos términos

CRC ➢ El coeficiente de x0 debería ser 1

➢ No ser divisible por xt + 1 (t entre 2 y n – 1)

➢ Contener el factor x + 1

➢ Algunos CRCs característicos:

• CRC-16 = X16+X15+X2+1 (HDLC)

• CRC-32 = X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+
X4+X2+X+1 (LANs)

22 Redes de datos I
Detección de errores
n bits r bits

DATO FCS

Palabra código: n + r bits

1-a) Dada el siguiente dato 110100 y el polinomio generador 101, calcular la palabra código transmitida
Agrego la misma cantidad
Dato: 6 bits de bits que el FCS
Polinomio: 3 bits 1 1 0 1 0 0 0 0 1 0 1
El FCS debe ser de un grado 1 0 1 1 1 1 0 10
menor que el polinomio 1 11
generador: 2 bits 1 0 1
1 0 0
Palabra código: 6 + 2 bits 1 0 1
0 1 00
1 0 1
Palabra código transmitida: 0 1 0
0 0 0
1 1 0 1 0 0 1 0
1 0
23 Redes de datos I
Detección de errores
n bits r bits

DATO FCS

Palabra código: n + r bits

1-b) Verificar si la palabra código recibida 11010010 tiene errores o no.
Dato
Dato: 6 bits
Polinomio: 3 bits 1 1 0 1 0 0 1 0 1 0 1
El FCS debe ser de un grado 1 0 1 111010
menor que el polinomio 1 11
generador: 2 bits 1 0 1
1 0 0
Palabra código: 6 + 2 bits 1 0 1
0 1 01
1 0 1
Palabra código recibida sin error 0 0 0
0 0 0
1 1 0 1 0 0
0 0
24 Redes de datos I
Detección de errores
n bits r bits

DATO FCS

Palabra código: n + r bits

1-c) Verificar si la palabra código recibida 11011010 tiene errores o no.

Dato Bit con error
Dato: 6 bits
Polinomio: 3 bits 1 1 0 1 1 0 1 0 1 0 1
El FCS debe ser de un grado 1 0 1 1 11 0 0 0
menor que el polinomio 1 11
generador: 2 bits 1 0 1
1 0 1
Palabra código: 6 + 2 bits 1 0 1
0 0 0 1 0
0 0 0
Palabra código recibida con error
1 0
1 1 0 1 0 0
25 Redes de datos I
Detección de errores
n bits r bits

DATO FCS

Palabra código: n + r bits

1-d) Verificar si la palabra código recibida 11011110 tiene errores o no.
Dato
Dato: 6 bits
Polinomio: 3 bits 1 1 0 1 1 1 1 0 1 0 1
El FCS debe ser de un grado 1 0 1 1 1 10 0 1
menor que el polinomio 1 11
generador: 2 bits 1 0 1
1 0 1
Palabra código: 6 + 2 bits 1 0 1
0 0 11 0
1 0 1
Palabra código recibida con error
1 1
1 1 0 1 0 0
26 Redes de datos I
Detección de errores
n bits r bits

DATO FCS

Palabra código: n + r bits

1-e) Verificar si la palabra código recibida 11000011 tiene errores o no.
Dato
Dato: 6 bits
Polinomio: 3 bits 1 1 0 0 0 0 1 1 1 0 1
El FCS debe ser de un grado 1 0 1 1 1 111 1
menor que el polinomio 1 1 0
1 0 1
generador: 2 bits 1 1 0
Palabra código: 6 + 2 bits 1 0 1
1 1 0
1 0 1
¿Palabra código recibida sin error? 1 1 1
1 0 1
1 0 1
1 1 0 0 0 0 1 0 1
27 Redes de datos I 0 0
Detección de errores

▪ Implementación de un CRC
• El registro contendrá n-k bits, igual a la
longitud de la FCS.
• Hay hasta n-k puertas exclusive-or.
• La presencia o ausencia de una compuerta
se corresponde los términos de P(X),
excluyendo a los términos 1 y Xn-k.

(Xn-k + An-1Xn-k-1 + …+ A2X2 + A1X + 1)

28 Redes de datos I
Detección de errores

Datos D=1010001101
D(X)=X9+X7+X3+X2+1

Divisor P=110101
P(X)=X5+X4+X2+1

29 Redes de datos I
 • Introducción

CONTROL DE • Detección de errores

ERRORES • Corrección de errores

• Delimitación de tramas

30 Redes de datos I
Corrección de errores

k bits
Datos Palabra Código

Codificador Decodificador
FEC FEC Sin errores o
1 errores
Palabra Código corregidos
1 2
n bits Errores
2
detectables pero
Datos no corregidos
Transmisor Receptor
La idea del corrector de errores es que el receptor sea capaz de corregir errores usando
exclusivamente los bits recibidos en la transmisión.
31 Redes de datos I
Corrección de errores

Distancia de Hamming:

Dadas dos palabras de n bits 𝑣1 y 𝑣2 se define como:

d(𝑣1 ; 𝑣2 ) el número de bits en que 𝑣1 y 𝑣2 difieren

𝑣1 = 0 1 1 0 0 1 d(𝑣1 ; 𝑣2 ) = 2
𝑣2 = 1 1 1 0 1 1

Su significado es que, si dos palabras codificadas están separadas una distancia

de Hamming d, se requerirán d errores de un solo bit para convertir una en la otra.

32 Redes de datos I
Corrección de errores

Códigos de bloque

Por ejemplo: Bloque de datos Código de palabra

k=2 bits de bloque de datos
00 00000
n=5 bits de código de palabra
01 00111
10 11001
11 11110

Si recibo 11101 d (11101, 00000) = 4 Si recibo 01010 d (01010, 00000) = 2

(inválida) d (11101, 00111) = 3 (inválida) d (01010, 00111) = 3
d (11101, 11001) = 1 d (01010, 11001) = 3
d (11101, 11110) = 2 d (01010, 11110) = 2

distancia mínima entre ¿Cuál elijo?

todas las posibles: elijo
esa palabra código
33 Redes de datos I
Corrección de errores

Códigos de bloques

• Un código de bloque (n, k) codifica k bits de datos en palabras-código de n bits.

• Generalmente, cada palabra-código válida incluye a los k bits de datos originales y les añade
(n-k) bits de comprobación para constituir la palabra-código de n bits.

• En un código de bloque (n, k), habrá 2k palabras-código válidas de un total de 2n posibles.

• Se define la redundancia del código como el cociente del número de bits redundantes entre
el número de bits de datos (n-k)/k.

• Se define la tasa del código como el cociente del número de bits de datos entre el número
de bits totales, k/n. (medida del ancho de banda adicional)

34 Redes de datos I
Corrección de errores

• Para un código constituido por las palabras-código 𝑤1, 𝑤2, ..., 𝑤𝑠, en el que 𝑠 = 2 𝑛 ,
se define la distancia mínima del código como:

𝑑𝑚 𝑖 𝑛 = min 𝑑(𝑤𝑖 , 𝑤𝑗 ) para i≠j

• Se puede demostrar que (con t entero positivo):

• El número de errores t que se pueden detectar es: 𝑡 = 𝑑 𝑚𝑖𝑛 − 1

• Para corregir errores de hasta t bits, se requiere que 𝑑 𝑚𝑖𝑛 ≥ 2𝑡 + 1

35 Redes de datos I
Corrección de errores

Códigos de bloque

Por ejemplo: Bloque de datos Código de palabra

k=2 bits de bloque de datos
00 00000
n=5 bits de código de palabra
01 00111
10 11001 Código (5,2)
11 11110
Tasa del código: 2/5
d (00000, 00111) = 3
d (00000, 11001) = 3
d (00000, 11110) = 4 𝑑 𝑚𝑖𝑛 = 3 Puede detectar 2 errores
d (00111, 11001) = 4 y corregir 1 error
d (00111, 11110) = 3
d (11001, 11110) = 3

36 Redes de datos I
Corrección de errores

37 Redes de datos I
Corrección de errores

38 Redes de datos I
 • Introducción

CONTROL DE • Detección de errores

ERRORES • Corrección de errores

• Delimitación de tramas

39 Redes de datos I
Delimitación de tramas

▪ La capa física proporciona la sincronización de bits para garantizar que el emisor y

el receptor utilicen las mismas duraciones de bits y la misma temporización.
▪ La capa de enlace de datos, por otro lado, necesita empaquetar los bits en tramas,
de modo que cada trama sea distinguible de otra
▪ Si las tramas son de longitud variable, es necesario delimitarlas: entramado
▪ Dos opciones:
▪ Entramado orientado a carácter
▪ Entramado orientado a bit

40 Redes de datos I
Entramado orientado a carácter

Conteo de bytes
• Un campo en el encabezado especifica el número de bytes en la trama.

• El conteo se puede alterar debido a un error de transmisión.

• Raras veces se utiliza el método de conteo de bytes por sí solo.

41 Redes de datos I
Entramado orientado a carácter

Bytes bandera con relleno de bytes

• Cada trama inicia y termina con bytes especiales.

• Con frecuencia se utiliza el mismo byte, ( f l a g o byte bandera) como delimitador

inicial y final.

• Generalmente se utiliza el carácter 0x7E (01111110 en binario)

Flag Bits de Bits de Flag

Datos
8 bits control control 8 bits

• El problema surge si el flag se repite dentro de los datos.

42 Redes de datos I
Entramado orientado a carácter

Bytes bandera con relleno de bytes

• Si el flag aparece dentro de los datos, se le añade el carácter de escape ESC (0x7D)

FLAG FLAG FLAG FLAG ESC FLAG FLAG

• ¿y si aparece el carácter ESC en los datos? Se le añade otro carácter ESC

FLAG ESC FLAG FLAG ESC ESC FLAG

FLAG ESC FLAG FLAG FLAG ESC ESC ESC FLAG FLAG

Byte stuffing

43 Redes de datos I
Entramado orientado a bit

▪ Se utiliza un flag delimitador (generalmente 01111110) para delimitar el inicio y fin de

la trama, que contiene un número variable de bits.

Bits de Bits de
01111110 Datos 01111110
control control

▪ ¿y si aparece el flag en los datos? Si en los datos se encuentran cinco bits 1

consecutivos, se inserta un 0 como relleno en el flujo de bits de salida.

Bits de Bits de
01111110
control 00101111101011011111110 control
01111110

Bits de Bits de
01111110
control 0010111110010110111110110 control
01111110

Bit stuffing

44 Redes de datos I
Violaciones de codificación de la capa física

• La codificación de bits como señales incluye a menudo redundancia para ayudar al receptor.

• Esta redundancia significa que algunas señales no ocurrirán en los datos regulares.

• Por ejemplo, en el código de línea 4B/5B se asignan 4 bits de datos a 5 bits de señal para
asegurar suficientes transiciones de bits. Esto significa que no se utilizan 16 de las 32 posibles
señales.

• Podemos usar algunas señales reservadas para indicar el inicio y el fin de las tramas. Se usan
“violaciones de código” para delimitar tramas.

• Como hay señales reservadas, es fácil encontrar el inicio y final de las tramas y no hay
necesidad de rellenar los datos.

45 Redes de datos I