La ráfaga que más se escapa

Un CRC de $n-k$ bits de redundancia ve toda ráfaga de hasta $n-k$ bits. Con las más largas falla a veces, y uno esperaría que fallara más cuanto más larga es la ráfaga. No pasa. La ráfaga que más se escapa no es la más larga: es la que se pasa por uno, con el doble de fracción que cualquier otra. En el CRC CCITT de 16 bits se escapa una de cada $2^{15}$ ráfagas de largo 17, y una de cada $2^{16}$ de largo 18, 19 o cualquier otro. Con 32 bits, el peor caso es una de cada 2 147 483 648.

01 · El código, la ráfaga y el resto

Un código cíclico $(n,k)$ escribe cada vector de $n$ bits como un polinomio, $v(X)=v_0+v_{1}X+\dots +v_{n-1}{X}^{n-1}$, y queda entero determinado por su polinomio generador $g(X)$, de grado $n-k$ y con $g_0=1$. Las palabras de código son exactamente los múltiplos de $g(X)$ de grado menor que $n$.

Para detectar, se divide lo recibido por $g(X)$ y se mira el resto, que es el síndrome: $s(X)=R_{g(X)}\{r(X)\}$. Si lo recibido es $r(X)=v(X)+e(X)$, con $e(X)$ el patrón de error, el resto de $v(X)$ es cero y el síndrome sólo depende de $e(X)$. Un error pasa sin verse exactamente cuando $e(X)$ es él mismo un múltiplo de $g(X)$: otra palabra de código. Un CRC es esto mismo, un cíclico, o un cíclico acortado, usado sólo para detectar.

Una ráfaga de largo $l$ es un patrón de error cuyos unos caben en $l$ posiciones consecutivas, con la primera y la última en error; las del medio pueden estar bien o mal. En polinomios, una ráfaga que empieza en la posición $i$ es

$$e(X)=X^{i}B(X),\mathrm{deg}B=l-1,B_0=B_{l-1}=1$$

De los $l$ coeficientes de $B(X)$, dos están fijos y $l-2$ son libres: hay $2^{l-2}$ ráfagas de largo $l$ por cada lugar donde empezar. La fracción no detectada de un largo es cuántas de esas son múltiplos de $g(X)$, sobre el total. Si todas las ráfagas de un largo son igual de probables, es la probabilidad de que una ráfaga de ese largo pase sin verse.

02 · Hasta n − k no se escapa ninguna

Si la ráfaga $X^{i}B(X)$ fuera una palabra, $g(X)$ la dividiría. Como $g_0=1$, $X$ no es factor de $g(X)$, así que $g(X)$ y $X^i$ no comparten nada y la división tiene que caer entera sobre $B(X)$. El lugar donde empieza la ráfaga no importa: lo único que cuenta es $B(X)$.

Y un múltiplo no nulo de $g(X)$ tiene grado $n-k$ o más. Si $l\le n-k$, el grado de $B(X)$ es $l-1<n-k$, y no hay forma. Toda ráfaga de hasta $n-k$ bits se detecta, también las que dan la vuelta por el extremo del bloque: en el anillo de $n$ posiciones son una ráfaga común vista desde otro origen.

03 · Con n − k + 1 se escapa una sola

Que $g(X)$ divida a $B(X)$ es que exista un multiplicador $a(X)$ con

$$B(X)=a(X)g(X),\mathrm{deg}a=d=l-1-(n-k)$$

Contar las ráfagas que se escapan es contar multiplicadores. Y el multiplicador tiene sus propias condiciones. El término independiente de $B(X)$ es $a_0{g}_0=a_0$, y tiene que valer 1: $a_0=1$. Para que $B(X)$ tenga grado $l-1$ justo, $a(X)$ tiene que tener grado $d$ justo: $a_d=1$.

En $l=n-k+1$, el grado del multiplicador es $d=0$: $a(X)$ es una constante, la única no nula es 1, y $B(X)$ tiene que ser exactamente $g(X)$. De las $2^{n-k-1}$ ráfagas de ese largo, se escapa una sola: el propio generador, corrido a donde haya caído.

$$l=n-k+1:\frac{1}{2^{n-k-1}}=2^{-(n-k-1)}$$

04 · Después, los dos extremos cuestan dos bits

Con $l>n-k+1$, el multiplicador tiene grado $d\ge 1$ y $d+1$ coeficientes. Dos están fijos, $a_0$ y $a_d$, y los $d-1$ del medio son libres. Cada elección da una ráfaga distinta que se escapa, así que son $2^{d-1}$ de $2^{l-2}$:

$$l>n-k+1:\frac{2^{d-1}}{2^{l-2}}=2^{(l-2-(n-k))-(l-2)}=2^{-(n-k)}$$

El largo se cancela: alargar la ráfaga en un bit suma un bit libre a la ráfaga y uno al multiplicador, y las dos cuentas se duplican juntas. Por eso la fracción se queda quieta en $2^{-(n-k)}$ para siempre.

Y de ahí sale el factor 2. La ráfaga paga siempre dos bits por sus extremos; el multiplicador también, salvo cuando es una constante, en la que el primer coeficiente y el último son el mismo bit. En $l=n-k+1$ el multiplicador se ahorra una condición que la ráfaga no se ahorra, y la fracción queda un bit arriba: $2^{-(n-k-1)}$ en vez de $2^{-(n-k)}$. Si el conteo de arriba se aplicara a ciegas con $d=0$, daría $2^{-1}$ multiplicadores: medio. Hay uno entero.

Arranca con el generador del ejercicio 10 de la práctica, $g(X)=1+X^2+X^4+X^5$, con $n-k=5$ y una ráfaga de 4, que no se escapa nunca. Apostá antes de pasar de 5. El conteo no usa la fórmula: recorre las $2^{l-2}$ ráfagas y divide cada una por $g(X)$. Las que pasan se listan armadas como $a(X)g(X)$, y el aviso dice si las dos cuentas coinciden.

05 · Medido en el CCITT

El CRC CCITT X-25 tiene $g(X)=1+X^5+X^{12}+X^{16}$, con $n-k=16$. Se dividieron por $g(X)$ todas las ráfagas de cada largo, de 15 a 22, y se contaron las de resto cero:

Las filas de 17 y de 18 dejan pasar lo mismo, una sola ráfaga; lo que cambia es el total, que se duplica. En 17 la que pasa es el generador, 10000100000010001; en 18 es $(1+X)g(X)$. Desde ahí, las que pasan y el total se duplican al mismo paso. El ANSI, $1+X^2+X^{15}+X^{16}$, da la misma tabla fila por fila.

Da igual con cualquier generador, porque la cuenta no usó nada de $g(X)$ salvo su grado y su $g_0=1$. Se recorrieron los 1020 polinomios con $g_0=1$ de grado 3 a 10, cada uno con todos los largos de 1 a $n-k+5$: en los 14 312 casos el recuento dio exactamente cero, $2^{-(n-k-1)}$ o $2^{-(n-k)}$, donde la cuenta lo dice.

El $2^{-(n-k)}$ tiene una lectura. Un patrón elegido al azar entre los $2^n$ cae sobre una de las $2^k$ palabras con probabilidad $2^k/2^n=2^{-(n-k)}$. Las ráfagas largas se le escapan al CRC como se le escaparía ruido sin forma. La de $n-k+1$ es el único largo que le va peor que al azar.

06 · Con 32 bits, uno en dos mil millones

El CRC de IEEE 802.3 tiene $n-k=32$. Ve toda ráfaga de hasta 32 bits. De las ráfagas de 33 se le escapa una sola, su propio generador, entre $2^{31}$ posibles: una en 2 147 483 648. De 34 bits en adelante, una en $2^{32}=\mathrm{4\; 294\; 967\; 296}$. El peor caso no es la ráfaga larga, que se ve casi como ruido, sino la que se pasa por un bit.

Ninguna de las dos cifras depende del largo de la trama: el lugar donde empieza la ráfaga se fue en la sección 02. Lo que la trama decide es cuántos lugares hay. Las garantías de un CRC se leen de a largo de ráfaga, y la del largo $n-k+1$ es la más floja de todas.