6.4 MECANISMOS DE DETECCIÓN Y CORRECCIÓN DE ERRORES
En matemáticas, computación y teoría de la información, la detección y corrección de errores
es una importante práctica para el mantenimiento e integridad de los
datos a través de diferentes procedimientos y dispositivos como medios
de almacenamiento confiables. Se considera como precursor de este tipo
de tecnologías el Acme Comodity and Phrase Code usado en los telegramas
Tipo de códigos detectores
Paridad simple (paridad horizontal)
Consiste en añadir un bit de más a la cadena que queremos enviar, y que nos indicará si el número de unos (bits puestos a 1) es par o es impar. Si es par incluiremos este bit con el valor = 0, y si no es así, lo incluiremos con valor = 1.Ejemplo de generación de un bit de paridad simple:
Queremos enviar la cadena “1110100”:
1º Contamos la cantidad de unos que hay: 4 unos
2º El número de unos es par por tanto añadimos un bit con valor = 0
3º La cadena enviada es 11101000
Verificación de errores o corrección de errores
La
codificación binaria es de gran utilidad práctica en dispositivos
electrónicos como ordenadores, donde la información se puede codificar
basándose en la presencia o no de una señal eléctrica.
Sin
embargo, esta señal eléctrica puede sufrir alteraciones (como
distorsiones o ruidos), especialmente cuando se transportan datos a
grandes distancias. Por este motivo, ser capaz de verificar la
autenticidad de estos datos es imprescindible para ciertos propósitos
(incluido el uso de información en entornos profesionales, bancarios,
industriales, confidenciales o relacionados con la seguridad).
Por este motivo existen algunos mecanismos que garantizan un nivel de integridad
de los datos, es decir, que el destinatario obtiene una confirmación de
que los datos recibidos son, de hecho, similares a los datos
transmitidos.
Existen dos maneras de proteger la transferencia de datos para que no se produzcan errores:
· instalando un medio de transmisión más seguro, es decir, una capa de protección física. Una conexión convencional tiene, por lo general, un porcentaje de error entre 10-5 y 10-7.
· implementando mecanismos lógicos para detectar y corregir errores.
La mayoría de los sistemas de control lógico de errores se basan en la suma de información (esto se denomina "redundancia") para verificar la validez de los datos. Esta información adicional se denomina suma de comprobación.
Verificación de errores
Se han perfeccionado mejores sistemas de detección de errores mediante códigos denominados:
· Códigos de autocorrección
· Códigos de auto verificación
La verificación de paridad (a veces denominada VRC o verificación de redundancia vertical) es uno de los mecanismos de verificación más simples. Consiste en agregar un bit adicional (denominado bit de paridad) a un cierto número de bits de datos denominado palabra código (generalmente 7 bits, de manera que se forme un byte cuando se combina con el bit de paridad) cuyo valor (0 o 1) es tal que el número total de bits 1 es par. Para ser más claro, 1 si el número de bits en la palabra código es impar, 0 en caso contrario.
Tomemos el siguiente ejemplo:
En este ejemplo, el número de bits de datos 1 es par, por lo tanto, el bit de paridad se determina en 0. Por el contrario, en el ejemplo que sigue, los bits de datos son impares, por lo que el bit de paridad se convierte en 1:
Supongamos
que después de haber realizado la transmisión, el bit con menos peso
del byte anterior (aquel que se encuentra más a la derecha) ha sido
víctima de una interferencia:
El bit de paridad, en este caso, ya no corresponde al byte de paridad: se ha detectado un error.
Sin
embargo, si dos bits (o un número par de bits) cambian simultáneamente
mientras se está enviando la señal, no se habría detectado ningún error.
Ya
que el sistema de control de paridad puede detectar un número impar de
errores, puede detectar solamente el 50% de todos los errores. Este
mecanismo de detección de errores también tiene la gran desventaja de
ser incapaz de corregir los errores que encuentra (la única forma de
arreglarlo es solicitar que el byte erróneo sea retransmitido).
Verificación de redundancia longitudinal
La verificación de la redundancia longitudinal (LRC, también denominada verificación de redundancia horizontal)
no consiste en verificar la integridad de los datos mediante la
representación de un carácter individual, sino en verificar la
integridad del bit de paridad de un grupo de caracteres.
Digamos
que "HELLO" es el mensaje que transmitiremos utilizando el estándar
ASCII. Estos son los datos tal como se transmitirán con los códigos de
verificación de redundancia longitudinal:
Letra
|
Código ASCII
(7 bits) |
Bit de paridad
(LRC) |
H
|
1001000
|
0
|
E
|
1000101
|
1
|
L
|
1001100
|
1
|
L
|
1001100
|
1
|
0
|
1001111
|
1
|
VRC
|
1000010
|
0
|
La verificación de redundancia cíclica (abreviado, CRC
) es un método de control de integridad de datos de fácil
implementación. Es el principal método de detección de errores utilizado
en las telecomunicaciones.
Concepto
La verificación de redundancia cíclica consiste en la protección de los datos en bloques, denominados tramas. A cada trama se le asigna un segmento de datos denominado código de control (al que se denomina a veces FCS, secuencia de verificación de trama, en el caso de una secuencia de 32 bits, y que en ocasiones se identifica erróneamente como CRC). El código CRC
contiene datos redundantes con la trama, de manera que los errores no
sólo se pueden detectar sino que además se pueden solucionar.
