Se necesitan mecanismos de detección de errores para garantizar transmisiones libres de errores. Si el receptor detecta algún error, puede actuar de diversas maneras según los protocolos que esté utilizando. La solución más sencilla es enviarle un mensaje al emisor pidiéndole que le reenvíe de nuevo la información que llegó defectuosa.
Los mecanismos de detección se basan en añadir a las transmisiones una serie de bits adicionales, denominados bits de redundancia. La redundancia es aquella parte del mensaje que sería innecesaria en ausencia de errores (es decir, no aporta información nueva: sólo permite detectar errores). Algunos métodos incorporan una redundancia capaz de corregir errores. Estos son los mecanismos de detección y corrección de errores.

 

PARIDAD

Las transmisiones se dividen en palabras de cierto número de bits (por ejemplo, 8 bits) y se envían secuencialmente. A cada una de estas palabras se le añade un único bit de redundancia (bit de paridad) de tal forma que la suma de todos los bits de la palabra sea siempre un número par (paridad par) o impar (paridad impar).
El emisor envía las palabras añadiendo los correspondientes bits de paridad. El receptor comprobará a su llegada que la suma de los bits de la palabra incluyendo la redundancia es un número par (si la codificación convenida entre emisor-receptor es de paridad par) o un número impar (paridad impar). Si el receptor encuentra alguna palabra que no se ajuste a la codificación establecida, le solicitará al emisor que le reenvíe de nuevo la información.
La paridad únicamente permite detectar errores simples, esto es, que varíe un único bit en cada palabra. Si varían 2 bits, este mecanismo no es capaz de detectar el error.
Veamos un ejemplo de paridad par:

 

El receptor realizará la suma de bits a la llegada del mensaje. Si alguna palabra no suma un número par, significará que se ha producido un error durante la transmisión.

CODIGO DE REDUNDANCIA CICLICA (crc)

Los códigos de paridad tienen el inconveniente de que se requiere demasiada redundancia para detectar únicamente errores simples. En el ejemplo que hemos visto, sólo un 8/9 de la información transmitida contenían datos, el resto era redundancia. Los códigos de redundancia cíclica (CRC) son muy utilizados en la práctica para la detección de errores en largas secuencias de datos. Se basan en representar las cadenas de datos como polinomios. El emisor realiza ciertas operaciones matemáticas antes de enviar los datos. El receptor realizará, a la llegada de la transmisión, una división entre un polinomio convenido (polinomio generador). Si el resto es cero, la transmisión ha sido correcta. Si el resto es distinto significará que se han producido errores y solicitará la retransmisión al emisor.
El tratamiento que tienen los mensajes están explicados mediante planteamientos matemáticos, mas directamente de manera polinomial, ya que estos mensajes son tratados como si fueran Polinomios, cuyos coeficientes son 1 y 0.
Si se analiza un mensaje cuyo tamaño sean k bits como un polinomio cuyos exponentes estarán en el rango [ 0 , k-1 ].
Un aspecto bien importante es el que tanto el emisor como receptor del mensaje pongan una regla o dejen bien en claro la generación del Polinomio Generador G (x).

Se debe definir el polinomio M(x) que representa al mensaje original :
" Longitud: r bits
" Grado: ( r > k )
" Rango: [ 0 , r - 1 ]

 

La Suma de Comprobación

" Añade r bits de 0 a M(x), el mensaje, produciendo xrM(x).
" Divide xrM(x) por G(x), produciendo un resto.
" Transmite T(x) = xrM(x) - resto. T(x) es divisible por G(x). Sus últimos r bits son el checksum.
" Si hay errores en la transmisión recibiremos T(x)+E(x) en vez de T(x). El recibidor divide T(x)+E(x) por G(x). Ya que el resto debido a T(x) es 0, el resto obtenido es completamente debido a E(x). Si E(x) tiene G(x) como un factor, el resto será 0 y no detectaremos el error, de otro modo, sí.
" Si hay un error de un bit, E(x) = xi . Si G(x) tiene más de un término, no puede dividir E(x). Entonces podemos detectar todos los errores de un bit.

Podemos detectar todos los errores en grupo con longitudes menos de o igual a r. Si el grupo tiene una longitud de k, lo podemos escribir como xi(xk-1+...+1) (i ubica el grupo en el marco). Si G(x) contiene un término de x0, xi no puede ser un factor y G(x) no puede ser igual a xk-1+...+1 (el grado k-1 es menos de r).
Si el grupo tiene una longitud de r+1, la probabilidad que el grupo es G(x) es la probabilidad que los r-1 bits intermedios del grupo son iguales (por definición el primer y el último bits del grupo son 1), que es (1/2)r-1

 

CODIGOS CONVOLUCIONALES

 

El código CRC acepta un mensaje de k bits y genera una palabra código de n bits. Es decir, se debe introducir un bloque completo para generar la secuencia código. Hay aplicaciones sin embargo, donde los bits mensaje entran en serie en lugar de en bloques, por lo que sería necesario el uso de "buffers" de tamaño considerable para almacenar momentáneamente los bloques a codificar. Para evitar el uso de estos "buffers", en los casos en los que los bits del mensaje entran en forma serie es preferible el uso de la codificación convolucional.
Las operaciones que se llevan a cabo sobre los k bits de entrada se pueden ver como la convolución discreta en el tiempo de la entrada con la respuesta impulsiva del codificador.
El codificador de un código convolucional binario de razón 1/n, se puede ver como una máquina de estados finitos que consiste en un registro de desplazamiento de M etapas con conexiones de sumadores (módulo 2), y un multiplexor que convierte en serie la salida de los sumadores. Una secuencia de mensaje de L bits produce una secuencia de salida codificada de longitud n(L + M) bits. La razón del codificador ("rate") viene dada por:

r = L / n (L+M) bits/simbolo

Normalmente, se tiene que L>>M. Por lo tanto, la velocidad se simplifica como:

r = 1 / n

La profundidad de un código convolucional, expresado en términos de los bits de mensaje, se define como el número de desplazamientos en los que influye un bit de mensaje en la salida codificada. Si un codificador tiene un registro de desplazamiento de M estados, la memoria del codificador es M, y se necesitan K = M + 1 desplazamientos para que un bit de mensaje entre y salga finalmente. Por lo tanto la profundidad del codificador es K.