proyecto de matee











Tema 4:
Detección y Corrección de Errores







Escuela Politécnica Superior Ingeniería Informática Universidad Autónoma de Madrid



Detección y Corrección de Errores




O
B Conocer cómo pueden detectarse y
J prevenirse errores que puedan
E aparecer en los distintos
T intercambios de información que
Irealiza el ordenador.
V Aplicar distintos métodos de
O detección y corrección de errores.
S





TEMA 4: DETECCIÓN Y CORRECCIÓN DE ERRORES

4.1 Control de errores usando paridad

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.
Conceptosprevios




• Concepto de Código:




- De un conjunto de palabras (por ejemplo: Posibles palabras binarias 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}


• Posibilidad de errores
- En informática (entre variosordenadores o en el interior de ellos) la informació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)• 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:


Escuela Politécnica Superior5


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 se corrige


- Situaciones:
• Cuando no es conveniente retransmitir la informaciónEscuela Politécnica Superior 6


de tratamientos de errores





• Códigos detectores de errores
- Uso:
• Se recibe la información, si se detecta el error se solicita la retransmisión


- Situaciones:
• Suele ser más costoso corregir que detectar
• Cuando es posible laretransmisión, se solicita


• Distancia de Hamming entre dos palabras

- Nº de bits que difieren dos palabras

- Ejemplo:





Distancia Hamming = 4








Se necesitan 4 errores para transformar una palabra en la otra





• 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




• 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 sedetecta
- Un error en 001 ⇒ 101, 011, 000, ∉ C
• Dos errores aislados no se detectan
- Dos errores en 001 ⇒ 111, 010, 100. Dos pertenecen a C




• Propiedades para la corrección de errores

- Para corregir d errores de un bit entre dos

palabras es necesario un código con una distancia de

Hamming de al menos 2d+1

- De otra forma: Con una distancia de Hamming de d se pueden...