Verificación de redundancia vertical (vrc)

Organización de Computadoras (5744)

Códigos Detección de Errores
Organización de Computadoras – Detección de Errores Mg. Javier Echaiz

Posibles errores

Organización de Computadoras Clase 16
Mg. Javier Echaiz D.C.I.C. – U.N.S. http://cs.uns.edu.ar/~jechaiz je@cs.uns.edu.ar

2

Organización de Computadoras – Detección de Errores

Mg. Javier Echaiz

Organización de Computadoras –Detección de Errores

Mg. Javier Echaiz

Comunicación interna
HOY

¿Qué hacer con los errores?
• Códigos de detección de errores
Enviar información junto con los datos que permita deducir que un error ocurrió, pero no cual, y se solicite una retransmisión.
PROXIMA

• Códigos de corrección de errores
Enviar información redundante junto con cada bloque de datos a enviar al receptor paradeducir bits fallaron.

3

4

Organización de Computadoras – Detección de Errores

Mg. Javier Echaiz

Organización de Computadoras – Detección de Errores

Mg. Javier Echaiz

Tipos de Errores
• Para conseguir una comunicación fiable es necesario detectar y corregir errores.
– Error de bit, sólo cambia 1 bit de la unidad de datos. – Error de ráfaga (burst), consiste en el cambio devarios bits consecutivos o no. El tamaño de la ráfaga se mide desde el último bit correcto hasta el primero que vuelve a serlo después del error.
5

Tipos de Errores

Veamos cada uno de ellos en detalle
6

Mg. Javier Echaiz

1

Organización de Computadoras (5744)

Códigos Detección de Errores
Organización de Computadoras – Detección de Errores Mg. Javier Echaiz

Organización deComputadoras – Detección de Errores

Mg. Javier Echaiz

Single-bit error

Burst error

Multiple-bit error

7

8

Organización de Computadoras – Detección de Errores

Mg. Javier Echaiz

Organización de Computadoras – Detección de Errores

Mg. Javier Echaiz

Distancia y Peso
• d(I,J): distancia entre I y J.
– número de posiciones de bits en los cuales las palabras I y J sondiferentes.

Ejemplos de w y d
• Considerar las siguientes palabras
I = 01101100 J = 11000100

• El peso de cada una es
w(I) = w(J) =

• w(P): peso de la palabra P.
– número de bits dentro de P iguales a 1.

• La distancia entre las dos es
d(I,J) =
9 10

Organización de Computadoras – Detección de Errores

Mg. Javier Echaiz

Organización de Computadoras – Detección de ErroresMg. Javier Echaiz

Distancia mínima
• Sea un código con palabra de n bits. • La distancia mínima de un código es el número de bits en los cuales dos caracteres de un código difieren. • Ejemplo: código de 4 caracteres y 5 bits. A B C D 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1
11

Ejemplo
• Distancia mínima: 3 bits. • Ejemplo de detección error:
– Dato enviado: 11011 (D). – Dato recibido:11000. – 11000 no es confundido con ningún otro dato. – 2 bits erróneos en una letra no causarán confusión con ningún otro dato.
12

Mg. Javier Echaiz

2

Organización de Computadoras (5744)

Códigos Detección de Errores
Organización de Computadoras – Detección de Errores Mg. Javier Echaiz

Organización de Computadoras – Detección de Errores

Mg. Javier Echaiz

Concluyendo…
•Errores en dos o menos bits pueden detectarse con una distancia mínima de 3. • Errores en tres o más bits no siempre se pueden detectar en un código de distancia mínima de 3.
– Un error en 3 bits en la letra B del ejemplo anterior puede convertirla en A.
A B 0 1 0 1 0 1 0 0 0 0
13

Detección
• Un error es cada una de las diferencias entre el dato correcto y el que se recibe. • Para detectarerrores es necesario añadir una redundancia que permita determinar mediante algún algoritmo que la información recibida no es correcta. • REDUNDACIA (o Recurrencia), es la información extra que se envía para la detección/corrección de errores y que no sería necesaria si podemos garantizar la ausencia de fallos. • Tipos de comprobaciones de redundancia:
– – – – – VRC, verificación de redundancia...