PDF de programación - 1.5 Técnicas de comunicaciones de datos

REDES DE

COMPUTADORES

1.5 Técnicas de comunicaciones de datos

1.5.1 Control de errores

1.5.1.1 Detección y retransmisión (ARQ)
1.5.1.2 Corrección directa (FEC)

Redes de Computadores

REDES DE

COMPUTADORES

Control de Errores

Errores de bit

Errores de ráfagas

Redes de Computadores

REDES DE

COMPUTADORES

Control de Errores

Distancia de Hamming

d(v1, v2) de dos secuencias binarias v1 y v2 de r bits consiste en un valor
numérico que indica el número de bits en los que v1 y v2 no coinciden

Para cada código válido se calcula la distancia de Hamming con todos los
demás, y de entre ellas se obtiene la mínima distancia de Hamming, dmin. Esta
distancia permite garantizar que, en una transmisión errónea:

• Mínima distancia de Hamming

» se pueden detectar hasta t errores, siendo t = dmin-1
» se pueden corregir hasta t errores, siempre que dmin ≥ 2t+1

Redes de Computadores

3

REDES DE

COMPUTADORES

Control de Errores

Métodos

ARQ (Automatic Repeat Request)

– Sólo detectan errores de transmisión (bits cambiados)

– Requieren menos información adicional o redundancia

» Códigos de paridad

» Polinómicos o CRC (Cyclic Redundancy Check)

– Utilización en los protocolos de comunicaciones (TCP)

FEC (Forward Error Correction)

– Detectan y corrigen errores de transmisión (bits cambiados)

– Requieren mucha información adicional o redundancia

– Utilización en redes móviles (GSM, 3G)

Redes de Computadores

4

 REDES DE

COMPUTADORES

Control de Errores

ARQ-Detección de Errores

 La protección de errores consiste en la adición de redundancia a

los mensajes para detectar errores y la recuperación se realiza
mediante retransmisión

 Técnicas de detección de errores:

 Comprobación de la paridad

 Comprobación de redundancia cíclica (CRC)

Redes de Computadores

5

REDES DE

COMPUTADORES

Control de Errores

Comprobación de la Paridad

 Añadir un bit de paridad al final del bloque de datos

• Paridad impar: El valor del bit añadido se determina de modo que el

número total de 1´s sea impar

• Paridad par: El valor del bit añadido se determina de modo que el número

total de 1´s sea par

 Errores detectados:

 Número impar de errores

Redes de Computadores

Ej. Detección

de ráfagas

[TANE11]

6

REDES DE

COMPUTADORES

Control de Errores

Códigos de Redundancia Cíclica (CRC)

 Dado un mensaje de m bits, el emisor genera una secuencia

de r bits (SVT)

 La trama resultante (m+r bits) será divisible por algún

número determinado

 El receptor divide la trama por ese número y si no hay resto,

se supone que no hay errores

 Códigos polinómicos:

 Representa las ristras de bits como polinomios con coeficientes

binarios

 Las operaciones se realizan en módulo 2 (XOR)

Redes de Computadores

7

REDES DE

COMPUTADORES

 Sea:

Control de Errores

CRC

 M(x): mensaje original (m bits)

 G(x): polinomio generador de grado r (r+1 bits)

 T(x): mensaje a transmitir (m+r bits)

 En emisión:

 En recepción:

siendo

Si R’(x) = 0, no hay errores

Si R’(x)  0, hay errores

Redes de Computadores

8

)()·()(xRxxMxTr)()·(mod)(xGxxMxRr)()(mod)('xGxTxR REDES DE

COMPUTADORES

Control de Errores

CRC

 Errores detectados:

 Errores de un único bit

 Errores dobles, siempre que G(x) tenga al menos tres 1´s

 Número impar de errores, siempre que G(x) tenga el factor (x+1)

 Ráfagas de errores de longitud menor que la longitud de G(x)

 La mayoría de las ráfagas de longitud mayor

 Polinomios generadores frecuentes:

 CRC-12:

x12+ x11+ x3+ x2+ x + 1

 CRC-16:

x16+ x15+ x2+ 1

 CRC-CCITT: x16+ x12+ x5+ 1

 CRC-32:

x32+ x26+ x23+ x22+ x16+ x12+ x11+ x10+ x8+ x7+ x5+ x4+ x2+ x+1

Calcular la probabilidad de detectar una ráfaga de longitud 17 bits

Redes de Computadores

9

REDES DE

COMPUTADORES

REDES DE

COMPUTADORES

Control de Errores CRC

6

3

M(X)= X +

X +1

1001001000
1011
0010

00
1011
001110
1011
0101
0
1011
0001
0

3

G(X)= X +X+1

1011

1

0

1

01

1

0

M(X)=1001001

3

M(X)*X =1001001000

T(X) =1001001010

=R(X)

Redes de Computadores

10

REDES DE

COMPUTADORES

REDES DE

COMPUTADORES

Control de Errores

CRC

1011

1

0

1
01

1

0

=R’(X)

CORRECTO!!!

1001 00 10 1 0
1011
0010

00
1011
001110
1011
0101
1
1011
000 0
0

11
Redes de Computadores

REDES DE

COMPUTADORES

REDES DE

COMPUTADORES

Control de Errores

CRC

1011

1

0

1
01

1

0

ERROR!!!

100100 00 10
1011
0010

00
1011
001100
1011
0111
1
1011
01000

12
Redes de Computadores

Protocolos de Comunicaciones

REDES DE

COMPUTADORES

Control de Errores
FEC-Correción de Errores

 La protección de errores consiste en la adición de redundancia a

los mensajes para detectar y corregir errores

 Técnicas de corrección de errores:

 Códigos de la paridad

 Códigos de Hamming

Redes de Computadores

13

REDES DE

COMPUTADORES

Control de Errores

FEC (Forward Error Correction)

• Códigos de Doble paridad

[Forouzan13]

Redes de Computadores

14

REDES DE

COMPUTADORES

FEC (Forward Error Correction) Doble paridad

Corrige

Detecta

Corrige errores simples

Detecta errores dobles

Detecta errores triples

Ni detecta, ni corrige

Detecta

Redes de computadores

[Forouzan13]

15

REDES DE

COMPUTADORES

Control de Errores

FEC (Forward Error Correction)

Códigos de Hamming

Detectan y corrigen errores de transmisión (bits cambiados)

Requieren mucha información adicional o redundancia

» se pueden detectar hasta t errores, siendo t = dmin-1
» se pueden corregir hasta t errores, siempre que dmin ≥ 2t+1

–

–

–

d (mínima) = 3

Detecta hasta dos bits erróneos

Corrige 1

Redes de Computadores

16

REDES DE

COMPUTADORES

m bits

Control

de

Errores

FEC (Forward Error Correction)

Códigos de Hamming

n bits

r bits

m + r + 1<= 2r

• Los bits cuya posición es potencia de dos se utilizan como bits de paridad

• Los bits del resto de posiciones son utilizados como bits de datos

r1 r2 m1 r3 m2 m3 m4 r4………

La posición 1, comprobaría los bits 1, 3, 5, 7 ……

La posición 2, comprobaría los bits 2, 3, 6, 7 ……

La posición 4, comprobaría los bits 4, 5, 6, 7 ……

Redes de computadores

17

REDES DE

COMPUTADORES

Test

Indique, ¿Cuál de las siguientes afirmaciones es cierta?

a) Los códigos cíclicos de comprobación de errores, corrigen todos los errores
dobles (afectan a dos bits) con independencia del polinomio generador
empleado

b) Las comprobaciones de errores mediante paridad par, permiten corregir

todos los errores triples.

c) Los códigos cíclicos de comprobación de errores, detectan todos los errores

simples (afecten a un único bit)

d) Los códigos cíclicos de comprobación de errores, corrigen todos los errores

simples (afecten a un único bit)

Redes de computadores

REDES DE

COMPUTADORES

Test

Un código cuya distancia Hamming es 3 permite…..

a) corregir errores dobles

b) corregir ráfagas de longitud 3

c) detectar ráfagas de longitud 3

d) Permite corregir errores simples

La técnica de corrección de errores de transmisión más adecuada para
transmisión de voz en el acceso radio de las redes móviles es:

a) FEC (Forward Error Control)

b) El empleo de bits de paridad y retransmisión

c) El empleo de códigos cíclicos de 2 bytes

d) El empleo de códigos cíclicos de 4 bytes

Redes de computadores