		*Últimos Cambios*
	Blog personal: El hilo del laberinto

Códigos detectores y correctores de errores: Códigos de Redundancia Cíclica (CRC)

Última Actualización: 30 de Agosto de 2003 - Sábado

Un código cíclico es aquel en el que cualquier rotación cíclica (lo que sale por un lado, entra por el otro) de una palabra código produce otra palabra código válida. Los códigos cíclicos son una familia de códigos bloque lineales que son especialmente fáciles y eficientes de generar y verificar.

Tradicionalmente los códigos cíclicos se expresan como polinómios en cuerpo de Galois GF(q), típicamente GF(2). Suponiendo una palabra código X[D]=(x_n-1, ..., x₀), también la podemos expresar como un polinomio de grado "n-1". de la forma X[D]=x_n-1D^n-1+ ... + x₁D + x₀.

Si X[D] es una palabra código de un código cíclico, el resto de dividir D*X[D] entre (Dⁿ-1) es otra palabra código. De hecho esta operación lo que produce es una rotación cíclica del código.

Dado un polinomio mónico (su coeficiente de mayor grado es 1) g[D] que es una palabra código de menor grado (m) de un código cíclico (generador del código), y un polinomio de información a[D] sobre GF(q), tenemos que a[D]*g[D] es una palabra código.

g[D] y sus primeras (n-1-m) rotaciones cíclicas forman una base del espacio vectorial que genera el código. Recordemos que el códgio tiene como parámetros (n, k) y un polinomio generador de grado "m".

El polinomio generador g[D] debe ser factor de (Dⁿ-1). Esto es necesario para que se genere un código cíclico.

Por lo tanto, cualquier código cíclico sobre un cuerpo de Galois de "q" elementos GF(q), con "k" dígitos de información y una longitud de bloque de "n", es generado por un polinomio mónico de grado m = n-k sobre el cuerpo de Galois GF(q) y que divide a (Dⁿ-1).

Y a la inversa, cualquier polinómio mónico g[D] de grado m = n-k sobre un cuerpo de Galois de "q" elementos GF(q) y que divida a Dⁿ-1, genera un código cíclico con "k" dígitos de información y longitud de bloque "n".

Si se aplican directamente las ecuaciones C[D]=X[D]*g[D], no se obtiene un código sistemático. Para conseguirlo, desplazamos la información (n-k) lugares a la derecha y añadimos la redundancia al final. La redundancia es el resto de dividir D^n-kX[D] entre g[D]. Es decir, lo que se transmite tiene la forma C[D]=(D^n-kX[D]-R[D]).

Para verificar el código, tendremos un polinomio comprobador h[D], que cumple que g[D]*h[D]=Dⁿ-1, y calculamos F[D]=C[D]*h[D]. El síndrome son los componentes de F[D] entre "k" y "n-1", inclusive. Si no hay errores, esos valores serán cero.

Por supuesto, se puede ver que h[D] es, a su vez, un polinomio generador (también es mónico) de código cíclico, y que su polinomio comprobador es g[D].

C[D] es una palabra código si y solo si es divisible de forma exacta por g[D]. Por lo tanto, para detectar un error es preciso que dicho error e[D] NO sea divisible por g[D], por ser un código lineal.

Puede verse fácilmente que siempre se detectan errores simples.

Si el polinomio generador g[D] es de la forma (1+D^h)m[D], tendrá un número par de términos distintos de cero y se puede comprobar fácilmente que detecta cualquier número impar de errores.

Se define el polinomio p[D] de grado "r" como "primitivo" si es irreducible, es un factor de (D^{(2^r-1)}-1) y no es factor de ningún otro polinomio (D^N-1) para N < 2^r-1. Si g[D]= p[D]*a[D], detectamos todos los errores dobles.

Una ráfaga de errores de longitud B es un grupo de B dígitos en los que el primero y el último es uno. Los del medio pueden serlo o no. Un código cíclico detecta todos los errores de ráfaga de longitud menor o igual a n-k. Si la ráfaga tiene tamaño n-k+1, la probabilidad de que el error nos pase desapercibido es de 2^-(n-k-1). Para ráfagas de mayor tamaño, la probabilidad de que el error nos pase desapercibido es de 2^-(n-k), suponiendo que los errores ocurran al azar. Supongamos g[D]=(1+D)*p[D], con p[D] polinomio primitivo de grado "r". Bajo estas circunstancias, g[D] es un polinomio generador con parámetros (2^r-1, 2^r-r-2) y que cumple las siguientes propiedades:

Detecta todos los errores simples.
Detecta cualquier número de errores impares.
Detecta todos los errores dobles.
Detecta todas las ráfagas de error de longitud <=r+1
Detecta todas las ráfagas de error de longitud r+2 con probabilidad 1-2^-r.
Detecta todas las ráfagas de error de longitud r+3 o superior con probabilidad 1-2^-r-1.

Por ejemplo, el CCITT V.41 tiene un polinomio generador D¹⁶+D¹²+D⁵+1, que es (D+1)*(D¹⁵+D¹⁴+D¹³+D¹²+D⁴+D³+D²+D+1, y genera un código (32767, 32751).

Los polinomios generadores están muy vinculados, por lo tanto, a polinomios primitivos, y éstos a Linear Feedback Shift Registers.

Historia

30/Ago/03: Primera versión de este documento.

Más información sobre los OpenBadges

Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS