correccion de errores

Tema 4:
Detección y Corrección de Errores
Escuela Politécnica Superior
Ingeniería Informática
Universidad Autónoma de Madrid

1

Detección y Corrección de Errores
O
B
J
E
T
I
V
O
S

Conocer cómo pueden detectarse y
TEMA 4: DETECCIÓN Y
prevenirse errores que puedan
CORRECCIÓN DE
aparecer en los distintos
ERRORES
intercambios de información que
4.1 Control de erroresusando paridad
realiza el ordenador.
Aplicar distintos métodos de
detección y corrección de errores.

4.2 Códigos de autochequeo
y autocorrectores

Bibliografía Tema 4:

- Introduction to Computer Hardware and Data Communications.
P.-A. GOUPILLE. (Prentice Hall, 1993). Cap. 5.

2

Conceptos previos
• Concepto de Código:
- De un conjunto de palabras (por ejemplo: Posibles
palabrasbinarias de una longitud determinada),
código es un subconjunto
- Ejemplo:
• Código: Palabras de tres bits con sólo un dígito a 1
• En las palabras binarias de longitud 3:
{000, 001, 010, 011, 100, 101, 110, 111}

Escuela Politécnica Superior

3

Necesidad del tratamiento de errores
•

Posibilidad de errores
- En informática (entre varios ordenadores o en el
interior de ellos) lainformación circula entre
diferentes dispositivos y reposa en ciertos dispositivos
- Posibles errores:
• Ruidos en las comunicaciones
• Defectos en las superficies de los discos, etc.

- Los errores consisten en la modificación de la
información desde que se emite (o almacena) hasta
que se recibe (o se recupera)
• Cambio de valor de algunos bits (0 ⇔ 1)

Escuela Politécnica Superior

4Necesidad del tratamiento de errores
• Tipos de errores
- Aislados: Bit afectado rodeado de bits correctos
• Simples: 1 bit afectado
• Múltiples: Más de 1 bit afectado

- Ráfagas de errores: Secuencia de bits contiguos con
errores
Información de partida:

1

0 0

0

1 0

1 0 0 0 0 0 0

1

1 0

Error aislado simple:

1

0 0

0

1 0

1 1 0 0 0 0 0

1

1 0Errores aislados triples:

1

0 1

0

1 0

1 1 0 0 0 0 0

0

1 0

Ráfaga de error:

1

0 0

1

0 1

0 1 1 1 1 1 0

1

1 0

Escuela Politécnica Superior

5

Tipos de códigos
de tratamientos de errores
• En lugar de manipular la información, se definen
códigos en los que se incluye la información que
permite detectar y/o corregir errores

• Códigoscorrectores de errores
- Uso:

• Se recibe la información, si se detecta el error
corrige

se

- Situaciones:

• Cuando no es conveniente retransmitir la información

Escuela Politécnica Superior

6

Tipos de códigos
de tratamientos de errores
• Códigos detectores de errores
- Uso:

• Se recibe la información, si se detecta el error
solicita la retransmisión

se

-Situaciones:

• Suele ser más costoso corregir que detectar
• Cuando es posible la retransmisión, se solicita

Escuela Politécnica Superior

7

Conceptos asociados a errores
• Distancia de Hamming entre dos palabras
- Nº de bits que difieren dos palabras
- Ejemplo:
0

1 0

1

0 1

0 1

0

0 0

0

1 1

1 1

Distancia Hamming = 4

Se necesitan 4 errores para transformar unapalabra en
la otra

Escuela Politécnica Superior

8

Conceptos asociados a errores
• Distancia de Hamming de un código
- Distancia mínima entre las palabras que componen el
código
- Ejemplo: {100, 111, 011}
mín{d(100, 111), d(100, 011), d(111, 011)} = mín{2, 3, 1} = 1

Escuela Politécnica Superior

9

Conceptos asociados a errores

• 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-1 errores
- Ejemplo: C = {001, 010, 100}, d. Hamming = 2
• Un error aislado siempre se detecta
- Un error en 001 ⇒ 101, 011, 000, ∉ C

• Dos errores aislados no se detectan
- Dos errores en...