Deteccion y correcion 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 errores usando paridad realizael 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 palabras binarias de una longituddeterminada), 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) la información circula entre diferentesdispositivos 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: Error aislado simple: Errores aislados triples: Ráfaga de error:

1 1 1 1

0 0 0 0 0 1 0 0

0 0 0 1

1 0 1 0 1 0 0 1

1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 11 1 1 0

1 1 0 1
5

1 0 1 0 1 0 1 0

Escuela Politécnica Superior

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ódigos correctores de errores
- Uso:
• Se recibe la información, si se detecta el error corrige se

- Situaciones:

• Cuando noes 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 Superior7

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

Se necesitan 4 errores para transformar una palabra en la otra

Escuela Politécnica Superior

8

Conceptos asociados a errores
• Distancia de Hamming de un código - Distancia mínima entre las palabrasque 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

• Propiedades para la detección de errores - Para detectar d errores de un bit entre dos

Conceptos asociados a errores

palabras, es necesario un código con una distancia de Hamming de al menos d+1 - De otra forma: Con una distancia de Hammingde d se pueden detectar d-1 errores - Ejemplo: C = {001, 010, 100}, d. Hamming = 2 • Un error aislado siempre se detecta • Dos errores aislados no se detectan
- Dos errores en 001 ⇒ 111, 010, 100. Dos pertenecen a C
Escuela Politécnica Superior 10

- Un error en 001 ⇒ 101, 011, 000, ∉ C

• Propiedades para la corrección de errores
- Para corregir d errores de un bit entre dos palabras es...