Los CRC y los códigos cíclicos acortados

Un código cíclico tiene el largo que le deja la factorización de $X^n+1$: 7, 15, 31, 32 767. Una trama de datos tiene el largo que le toca. Un CRC (cyclic redundancy check) junta las dos cosas: es un código cíclico acortado al largo de la trama y usado sólo para detectar. Lo que ofrece no sale de una distancia mínima, que depende del largo, sino de una garantía que no depende: toda ráfaga de hasta $n-k$ bits se ve.

01 · La ráfaga

Un error en ráfaga de largo $l$ es un patrón de error cuyos unos caben en $l$ posiciones consecutivas, con la primera y la última no nulas. En polinomios:

$$e(X)=X^{i}B(X),gradoB=l-1,B_0=1$$

$X^i$ dice dónde empieza y $B(X)$ qué forma tiene. Los dos extremos de $B$ valen 1 y los $l-2$ coeficientes del medio son libres: en cada posición de comienzo hay $2^{l-2}$ ráfagas de largo $l$.

Sobre el anillo de $n$ posiciones hay además ráfagas que se cortan en el extremo de mayor orden y siguen en el de menor: las ráfagas cíclicas (end-around bursts). El ejemplo del apunte, con $n=15$ y la posición 0 a la izquierda,

$$e=(\mathrm{1\; 0\; 1\; 0\; 0\; 0\; 0\; 0\; 0\; 0\; 0\; 1\; 1\; 0\; 1})$$

parece un patrón disperso de peso 5. Leído desde la posición 11, ocupa las posiciones 11, 12, 13, 14, 0, 1 y 2: es $X^{11}B(X)$ módulo $X^{15}+1$, con $B(X)=1+X+X^3+X^4+X^6$, una ráfaga de largo 7.

02 · Toda ráfaga de hasta n − k

Teorema 6. Un código cíclico $(n,k)$ detecta toda ráfaga de largo $l\le n-k$, incluidas las cíclicas.

Paso 1: no detectar es ser palabra. Una ráfaga pasa sin verse si y sólo si su síndrome es nulo, o sea si es una palabra de código. Las palabras son los múltiplos del polinomio generador, así que $g(X)$ tendría que dividir a $X^{i}B(X)$.

Paso 2: el comienzo no importa. $g(X)$ divide a $X^n+1$, que vale 1 en $X=0$; por eso $g_0=1$ y $X$ no divide a $g$. Sin factores comunes con $X^i$, $g$ tendría que dividir a $B(X)$ sola.

Paso 3: no cabe. $B(X)$ no es nulo y tiene grado $l-1<n-k$, menor que el de $g$. Ningún polinomio no nulo es múltiplo de otro de grado mayor.

Las cíclicas entran por la misma puerta. Una ráfaga cíclica es $X^{i}B(X)$ reducido módulo $X^n+1$, y como $g$ divide a $X^n+1$, reducir no cambia el resto:

$$R_{g(X)}\{R_{X^n+1}\{X^{i}B(X)\}\}=R_{g(X)}\{X^{i}B(X)\}$$

Sobre el anillo no hay extremos: una ráfaga cíclica es una ráfaga común vista desde otro origen. La garantía tampoco pasa por la distancia. El (7,4) de $g=1+X+X^3$ tiene $d_{\text{min}}=3$ y siete palabras de peso 3, pero ninguna cabe en tres posiciones consecutivas del anillo: la ráfaga $1+X+X^2$, de peso 3, se ve igual que las de peso 1 y 2.

03 · Las que se escapan

Con $l>n-k$ ya caben múltiplos de $g$. Los pasos 1 y 2 siguen valiendo, así que una ráfaga se escapa exactamente cuando $B(X)=q(X)g(X)$, y contar las que se escapan es contar los $q$ posibles.

Paso 1: el multiplicador. $q$ tiene grado $l-1-(n-k)$. Como $B_0=q_0{g}_0=1$, su término independiente vale 1, y su coeficiente principal también.

Paso 2: un bit de más. Con $l=n-k+1$, $q$ es una constante, y la única ráfaga que se escapa es $B=g$: una de $2^{n-k-1}$.

Paso 3: más largas. Con $l>n-k+1$, $q$ tiene grado $d\ge 1$, dos extremos fijos y $d-1$ coeficientes libres: $2^{l-(n-k)-2}$ de las $2^{l-2}$ ráfagas.

$$\text{fracción que pasa}=\{\begin{array}{ll}0& l\le n-k\\ 2^{-(n-k-1)}& l=n-k+1\\ 2^{-(n-k)}& l>n-k+1\end{array}$$

En ningún lado aparecen $n$, el comienzo $i$ ni los coeficientes de $g$: sólo su grado. Con el generador del ejercicio 10 de la práctica, $g=1+X^2+X^4+X^5$, enumerando todas las ráfagas de cada largo pasan 0, 0, 1/16, 1/32 y 1/32 para $l=4$ a 8. Por qué la que se pasa por un bit es la que peor le va a un CRC, y cuánto es eso con 32 bits, está en la ráfaga que más se escapa.

04 · Acortar un cíclico

Acortar un código lineal ya está en los códigos acortados: se fijan en cero $\ell$ posiciones de información, no se transmiten, y queda un $(n-\ell ,k-\ell )$ cuyas palabras son un subconjunto de las del original, con la misma paridad y una distancia que no baja. Lo propio del cíclico son tres cosas.

Primero, qué posiciones se suprimen. En la forma sistemática cíclica la paridad va primero y el mensaje al final, así que las $\ell$ posiciones de información de mayor orden son las últimas $\ell$ del vector. Anularlas es pedir grado menor que $n-\ell$: el acortado son los múltiplos de $g$ de grado menor que $n-\ell$.

$$v(X)=a(X)g(X),gradoa<k-\ell$$

El ejemplo del apunte es el de Lin y Costello (sección 5.10, ejemplo 5.12): el Hamming cíclico (31,26) de $g=1+X^2+X^5$, acortado en $\ell =3$, da un (28,23).

Deja de ser cíclico. $X^{22}g=X^{22}+X^{24}+X^{27}$ tiene grado 27 y es palabra del (28,23). Girada una posición en el anillo de 28, el $X^{27}$ pasa a $X^{28}$, que da la vuelta a 1: queda $1+X^{23}+X^{25}$, de resto $1+X+X^2+X^4$. No es palabra. La razón es general: girar en el anillo de $n-\ell$ suma $X^{n-\ell }+1$ cada vez que un uno pasa por el borde, y $g$ no lo divide: $R_{g(X)}\{X^{28}+1\}$ es justamente ese $1+X+X^2+X^4$.

El circuito sirve igual. Codificar es $b(X)=R_{g(X)}\{X^{n-k}u(X)\}$, y unos ceros de mayor orden en $u(X)$ no cambian el polinomio ni su resto. En el registro de desplazamiento, que arranca en cero y recibe primero el bit de mayor orden, esos ceros entrarían primero y lo dejarían en cero: se pueden no mandar. El registro de $n-k$ etapas, las conexiones de $g$ y el circuito de síndrome son los del código entero. Es la razón práctica de acortar así.

El decodificador espera de más. Si lo recibido entra al registro de síndrome por el extremo derecho, lo que equivale a multiplicarlo por $X^{n-k}$, el detector del decodificador de Meggitt está armado para el código entero: espera el síndrome que corresponde a un error en la posición $n-1$. En el acortado el primer dígito que se decodifica es el $n-\ell -1$, y después de los $n-\ell$ ciclos de entrada el registro necesita $\ell$ desplazamientos más para llegar a ese síndrome. Se ahorran multiplicando lo recibido, mientras se lo divide, por

$$\rho (X)=R_{g(X)}\{X^{n-k+\ell }\}$$

que es un segundo juego de conexiones de entrada al registro. Para el (28,23), $\rho (X)=R_{g(X)}\{X^8\}=1+X^2+X^3$. La otra salida es dejar el registro como está y cambiar el detector, para que reconozca el síndrome que deja un error en la posición 27 del acortado: $R_{g(X)}\{X^5·X^{27}\}=X$, el vector (01000), porque $X^{31}$ deja resto 1. Las dos son cableado, no un circuito nuevo. El mismo cálculo para el Golay acortado está en el Golay por dentro.

05 · Los CRC normalizados

Un CRC agrega a la trama los $n-k$ bits de $b(X)$ y el receptor sólo mira si el resto es cero. La trama puede tener cualquier largo hasta el del cíclico del que sale. Sus generadores están normalizados; los de la tabla de Lin y Costello (sección 5.10), con su factorización medida en polinomios sobre GF(2):

CCITT X-25.

$$\begin{array}{l}g=X^{16}+X^{12}+X^5+1\\ =(X+1)(X^{15}+X^{14}+X^{13}+X^{12}\\ +X^4+X^3+X^2+X+1)\end{array}$$

ANSI.

$$g=X^{16}+X^{15}+X^2+1=(X+1)(X^{15}+X+1)$$

IBM-SDLC.

$$\begin{array}{l}g=X^{16}+X^{15}+X^{13}+X^7+X^4+X^2+X+1\\ ={(X+1)}^2(X^{14}+X^{13}+X^{12}+X^{10}+X^8+X^6\\ +X^5+X^4+X^3+X+1)\end{array}$$

IEC TC57. Se toma la forma desarrollada, la que la tabla da como el polinomio; su factorización medida tiene cinco factores:

$$\begin{array}{l}g=X^{16}+X^{14}+X^{11}+X^8+X^6+X^5+X^4+1\\ ={(X+1)}^2{(X^2+X+1)}^2(X^{10}+X^8+X^5+X^4+1)\end{array}$$

IEEE 802.3. Quince términos, y no se factoriza: es irreducible.

$$\begin{array}{l}g=X^{32}+X^{26}+X^{23}+X^{22}+X^{16}+X^{12}+X^{11}\\ +X^{10}+X^8+X^7+X^5+X^4+X^2+X+1\end{array}$$

Los factores de grado 15 del CCITT y del ANSI, el de grado 14 del SDLC, el de grado 10 del TC57 y el polinomio entero del 802.3 son primitivos: se probó que son irreducibles y que $X$ tiene orden $2^m-1$ módulo cada uno. Lin y Costello describen el CRC típico como un $p(X)$ primitivo o un $(X+1)p(X)$: el 802.3 es de la primera forma, el CCITT y el ANSI de la segunda.

De la factorización se leen tres garantías, cada una con su porqué.

Las ráfagas. Toda ráfaga de hasta 16 bits, o de hasta 32 en el 802.3, por el teorema 6. Vale en cualquier largo de trama, porque la prueba sólo usa que $g$ divida a $X^{i}B$.

El peso impar. Si $X+1$ divide a $g$, toda palabra cumple $v(1)=0$, y $v(1)$ es la paridad de su peso: todas pesan par, y ningún patrón de peso impar pasa. Lo cumplen cuatro de los cinco. El 802.3 no: con quince términos, $g(1)=1$.

Los dobles, hasta un largo. Dos errores son $X^i(1+X^j)$, y por el paso 2 de la sección 02 pasan sólo si $g$ divide a $1+X^j$. Eso pasa exactamente cuando $j$ es múltiplo del orden de $g$, el menor $N$ con $g\mid X^N+1$, que es el largo del cíclico que $g$ genera. En una trama de hasta ese largo, $j\le N-1$ y todo doble se ve.

El orden se midió de dos maneras: recorriendo $R_{g(X)}\{X^j\}$ hasta que vuelve a 1, y desde la factorización, como mínimo común múltiplo de los órdenes de los factores, duplicado donde hay un factor al cuadrado. Las dos dan lo mismo:

La última columna junta las dos garantías: uno y tres son impares, dos queda cubierto por el orden. En los cuatro que tienen el factor $X+1$, hasta ese largo el acortado tiene $d_{\text{min}}\ge 4$. El TC57 es el que antes la pierde: su factor primitivo es de grado 10, de orden 1023, y en una trama de 2047 bits $1+X^{2046}$ ya es palabra. En el 802.3, que no tiene el factor $X+1$, qué pasa con tres errores en una trama dada no sale de la factorización: depende de qué palabras de peso 3 entran en ese largo, y eso hay que buscarlo palabra por palabra.

Arranca en el CCITT con ráfagas de 12 bits: no pasa ninguna de las 1024. Subí el largo de a uno hasta pasar 16 y mirá cómo aparece la primera, que es el propio generador. Después, con el mismo largo, cambiá de CRC: las cuentas de ráfagas no se mueven entre los cuatro de 16 bits. Lo que los distingue está en la línea de abajo: poné la trama en 2047 bits y compará el TC57 con los otros tres.

06 · Lo que el acortado ya no garantiza

Las ráfagas cíclicas de la trama. El teorema 6 cubre las ráfagas que dan la vuelta al anillo de $n$, no al de $n-\ell$. En el (28,23),

$$e(X)=1+X+X^3+X^{27}$$

ocupa las posiciones 27, 0, 1, 2 y 3: leída como anillo de 28, es una ráfaga cíclica de largo 5, que es $n-k$. Y es palabra del código. Enumeradas las 32 ráfagas cíclicas de largo 5 que cruzan el borde del (28,23), pasa esa; en el (31,26) entero no pasa ninguna de sus 32. En el anillo de 31 esas mismas posiciones están separadas por el hueco de 28, 29 y 30, y ocupan ocho lugares. Con el CCITT en una trama de 1024 bits, entre las 24 576 ráfagas de largo 13 que cruzan el borde ya pasan cinco.

En una trama que sale en serie, el último bit y el primero no son vecinos en el canal, así que una ráfaga real no cruza ese borde. Lo que se pierde es la simetría del anillo, no la protección contra las ráfagas del canal.

La fracción no es una probabilidad del canal. Cuenta cuántos de los $2^{l-2}$ patrones de un largo pasan; se vuelve una probabilidad sólo si todos esos patrones son igual de probables. Un canal con su propia estadística de ráfagas puede caer más o menos seguido sobre los múltiplos de $g$.

Los errores aislados dependen del largo. Fuera de las ráfagas, lo que protege es la factorización, y sólo hasta el orden de $g$: el mismo CRC que en una trama de 2046 bits ve todo error de hasta tres bits, en una más larga deja pasar dobles.

Para tener a mano

1. Ráfaga de largo $l$: $e=X^{i}B(X)$, $gradoB=l-1$, $B_0=1$. Hay $2^{l-2}$ por posición. La cíclica cruza el extremo del anillo.
2. Teorema 6: un cíclico ve toda ráfaga de hasta $n-k$, cíclicas incluidas, porque $g_0=1$ y $B$ no alcanza el grado de $g$.
3. Más largas pasan si $B=qg$: $2^{-(n-k-1)}$ con $l=n-k+1$, $2^{-(n-k)}$ después. Sólo importa el grado de $g$.
4. Acortar en $\ell$: $(n-\ell ,k-\ell )$, los múltiplos de $g$ de grado menor que $n-\ell$. Deja de ser cíclico porque $g$ no divide a $X^{n-\ell }+1$; el codificador y el circuito de síndrome no cambian.
5. $\rho (X)=R_{g(X)}\{X^{n-k+\ell }\}$ ahorra los $\ell$ desplazamientos de espera. (31,26) a (28,23): $\rho =1+X^2+X^3$.
6. Un CRC garantiza: ráfagas de hasta $n-k$ en cualquier trama; peso impar si $X+1$ divide a $g$; dobles en tramas de hasta el orden de $g$.
7. Órdenes: CCITT y ANSI 32 767, SDLC 32 766, TC57 2046, 802.3 $2^{32}-1$. El 802.3 es primitivo y no tiene el factor $X+1$.
8. El acortado pierde las ráfagas cíclicas de la trama: en el (28,23), $1+X+X^3+X^{27}$ es palabra.