Atrapar errores y ráfagas

Los tres ejercicios usan los dos códigos de referencia de la práctica, que se presentan así: «Los ejercicios se apoyan en dos códigos cíclicos, ambos de distancia mínima 7 y capacidad correctora $t = 3$ .» El (15,5), con polinomio generador

g (X) = 1 + X + X^{2} + X^{4} + X^{5} + X^{8} + X^{10}

y el Golay (23,12), con

g_{1} (X) = 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10} + X^{11}

Corrigen lo mismo, y sin embargo uno se deja decodificar con el método más simple de la unidad y el otro no. Los ejercicios 8 y 9 son esa comparación. El 10 cambia de tema: no corrige, detecta, y cuenta qué ráfagas se le escapan a un código cíclico.

01 · Ejercicio 8: el enunciado y lo que pide

«El código (15,5) tiene $n - k = 10$ y $t = 3$ . La ventana de paridad abarca 10 posiciones consecutivas del anillo de 15.

Justificar, razonando sobre el anillo, que todo patrón de dos errores puede capturarse.
Analizar el patrón de tres errores en las posiciones ${2, 3, 6}$ . ¿Se captura? ¿Con cuántos desplazamientos?
Analizar el patrón ${0, 5, 10}$ . ¿Se captura?
Contar cuántos patrones de tres errores no pueden capturarse.»

Antes de resolver. Se entregan cuatro cosas: un argumento que valga para los 105 patrones dobles a la vez, no un recorrido de casos; un sí y un número de desplazamientos; un sí o un no; y un número, con la forma de los patrones que lo componen. En ninguno hace falta conocer la palabra transmitida: la captura mira sólo el patrón de error, porque el síndrome depende sólo de él. Y «capturar» tiene un sentido preciso, que conviene fijar antes de contar.

02 · Las herramientas de la captura

Tres resultados de la teoría, los tres en la nota de captura de errores y en la del síndrome cíclico.

El síndrome es un resto. Con $r (X) = v (X) + e (X)$ y $v (X)$ múltiplo de $g (X)$ , el síndrome es $s (X) = R_{g (X)} {e (X)}$ . Si todos los errores caen en las $n - k$ posiciones de paridad, que en la forma sistemática cíclica son las primeras, de la 0 a la $n - k - 1$ , entonces $\deg e (X) < n - k$ , la división tiene cociente nulo y

s (X) = e (X)

El registro contiene el patrón de error, bit por bit.

Un ciclo del registro gira la palabra. Por el teorema 5, $R_{g (X)} {X s (X)}$ es el síndrome de $R_{X^{n} + 1} {X r (X)}$ , la palabra recibida desplazada un lugar. Después de $i$ ciclos el registro tiene $s^{(i)} (X)$ , el síndrome de $X^{i} e (X)$ módulo $X^{n} + 1$ . Cada error subió $i$ posiciones, y el que pasa de la $n - 1$ vuelve a la 0. Sobre las posiciones puestas en círculo, el patrón gira y la ventana de paridad queda quieta.

El test de peso no se equivoca. El decodificador no ve dónde están los errores: ve el peso del síndrome. Si los errores están en la ventana, el síndrome es el patrón y pesa a lo sumo $t$ . Al revés, si $w [s^{(i)}] \leq t$ pero el patrón girado no fuera $s^{(i)}$ , la suma de los dos sería una palabra de código no nula de peso a lo sumo $2 t = 6$ , menos que la distancia 7. Entonces el peso cae a $t$ o menos si y sólo si los errores están capturados. Si en $n$ ciclos eso no pasa, el decodificador declara la falla: hace decodificación incompleta, y nunca entrega una palabra equivocada.

Con eso, «se captura» deja de ser una pregunta sobre el registro y pasa a ser una pregunta sobre el anillo: ¿hay algún giro que meta los errores en las posiciones 0 a $n - k - 1$ ? O, lo que es lo mismo, ¿hay $n - k$ posiciones consecutivas del anillo que los contengan a todos?

03 · El razonamiento: k posiciones limpias

Contar ventanas que contienen errores es incómodo. Lo que conviene mirar es el complemento. Las $n - k$ posiciones de la ventana y las $k$ restantes parten el anillo en dos arcos. Los errores caben en la ventana exactamente cuando el otro arco, el de $k$ posiciones, cae entero sobre posiciones sin error. Así:

un patrón se captura si y sólo si el anillo tiene $k$ posiciones consecutivas sin errores.

En el (15,5) eso es pedir cinco posiciones limpias seguidas. La cuenta se hace con los tramos limpios: $w$ errores sobre un anillo de $n$ dejan $n - w$ posiciones limpias, repartidas en a lo sumo $w$ tramos, uno entre cada error y el siguiente.

Paso 1: dos errores. Quedan 13 posiciones limpias en dos tramos, $a + b = 13$ . Si los dos tuvieran 4 o menos, sumarían 8 a lo sumo. Uno tiene por lo menos 7, y 7 ≥ 5.

Paso 2: tres errores. Quedan 12 limpias en tres tramos, $a + b + c = 12$ . Para que ninguno llegue a 5, los tres tienen que valer 4 o menos, y como suman 12, $a = b = c = 4$ : los errores están a distancia 5 uno de otro.

Paso 3: contar los que fallan. Un patrón con tramos 4, 4, 4 queda fijado por la posición de su primer error: ${i, i + 5, i + 10}$ . Con $i$ de 0 a 14 cada patrón aparece tres veces, una por cada error que se elija como primero: son $15 / 3 = 5$ .

El razonamiento no usa nada del (15,5) salvo $n$ , $k$ y que corrija tres errores. Es una cuenta sobre el anillo, y por eso la misma cuenta va a servir para el Golay. Y la captura misma se puede seguir ciclo por ciclo: el registro de abajo es el síndrome de verdad, calculado como resto.

Arranca con errores en 10, 12 y 14, fuera de la ventana: el síndrome pesa más de tres, y cada ciclo los sube un lugar hasta que el 14 da la vuelta. Probá después ${0, 5, 10}$ : el peso del síndrome va y viene entre 4 y 7 y no baja nunca, y a los quince ciclos el decodificador se rinde. Y pasá al Golay con ${11, 22}$ : con sólo dos errores pasa lo mismo, y el peso no baja de 5 en ninguno de los 23 ciclos.

04 · Ejercicio 8 resuelto

1. Dos errores dejan 13 posiciones limpias en dos tramos, así que uno de los tramos tiene al menos 7. Ese tramo contiene cinco posiciones limpias seguidas, y girando el patrón hasta que esas cinco queden en las posiciones 10 a 14, los dos errores caen en la ventana, de la 0 a la 9. Dicho de otra forma: dos posiciones del anillo de 15 distan a lo sumo 7 por el arco más corto, y ese arco ocupa 8 posiciones, menos que las 10 de la ventana. Los 105 dobles se capturan.

2. El patrón ${2, 3, 6}$ ya está en la ventana: $e (X) = X^{2} + X^{3} + X^{6}$ tiene grado 6 < 10, y el síndrome es él mismo, 0011001000, de peso 3. Se captura con cero desplazamientos: el test de peso se cumple en el primer síndrome, antes del primer ciclo.

3. El patrón ${0, 5, 10}$ tiene sus tres tramos limpios de 4 posiciones. Ningún giro deja cinco limpias seguidas fuera de la ventana, así que no se captura. Calculado ciclo por ciclo, el peso del síndrome recorre 4, 4, 7, 7, 4 y se repite: nunca llega a 3, y el decodificador declara la falla.

4. Fallan los patrones de tramos 4, 4, 4, que son los ${i, i + 5, i + 10}$ con $i = 0, \dots, 4$ : 5 de los $(\binom{15}{3}) = 455$ , el 1,1 %. Corriendo el decodificador sobre los 455 triples, captura 450 y declara la falla en los 5; no entrega mal ninguno. Para el (15,5), la captura simple corrige todo lo que el código promete salvo esos cinco, y a esos cinco los avisa.

05 · Ejercicio 9: el Golay, con la misma t

«El Golay (23,12) tiene $n - k = 11$ y $t = 3$ : la misma capacidad correctora que el código del ejercicio anterior.

Analizar el patrón de dos errores ${0, 1}$ . ¿Se captura?
Analizar el patrón de dos errores $e (X) = X^{11} + X^{22}$ . Calcular las distancias entre ambas posiciones por los dos arcos del anillo y decidir si existe alguna ventana de 11 posiciones que las contenga.
Concluir qué ocurre con la captura simple aplicada al Golay.
Comparar con el ejercicio anterior y enunciar la regla de diseño que se desprende.»

Antes de resolver. Los dos primeros ítems son el ejercicio 8 con otros números. El tercero pide una conclusión, y una conclusión honesta lleva una cuenta: cuántos dobles se pierden, y qué pasa con los triples, que el Golay también promete corregir. El cuarto pide una regla, y la regla tiene que salir de lo único que cambia entre los dos códigos, porque $d_{min}$ y $t$ son iguales.

Las herramientas son las de la sección 02, sin cambios: el test de peso vale en el Golay porque su distancia también es 7. Lo que cambia es el criterio de la sección 03: ahora $k = 12$ , y un patrón se captura si el anillo de 23 tiene doce posiciones limpias seguidas.

El razonamiento. Dos errores dejan 21 limpias en dos tramos. Si ninguno llega a 12, son de 10 y 11: los dos errores están a distancia 11 por un arco y 12 por el otro. Eso pasa para ${i, i + 11}$ con $i$ de 0 a 22, y los 23 son distintos: 23 dobles que no se capturan. Tres errores dejan 20 limpias en tres tramos, $a + b + c = 20$ , y el patrón falla si los tres valen 11 o menos. Ternas ordenadas de enteros no negativos que suman 20 hay $(\binom{22}{2}) = 231$ ; las que tienen un tramo de 12 o más son, restándole 12 a ese tramo, ternas que suman 8, $(\binom{10}{2}) = 45$ por cada uno de los tres lugares, y dos tramos de 12 no entran en 20. Quedan $231 - 135 = 96$ ternas. Cada una, con su primer error en cualquiera de las 23 posiciones, da un patrón, y cada patrón sale tres veces:

\frac{23 \cdot 96}{3} = 736

triples que no se capturan, de $(\binom{23}{3}) = 1771$ . Se capturan 1035.

La resolución.

1. ${0, 1}$ son dos errores adyacentes, en la ventana desde el principio: el síndrome es $1 + X$ , de peso 2, y se captura sin desplazar.

2. Entre la 11 y la 22 hay 11 posiciones por un arco y $23 - 11 = 12$ por el otro. Una ventana de 11 posiciones consecutivas abarca diferencias de a lo sumo 10, así que no hay ninguna que contenga a las dos. Calculado sobre los 23 ciclos, el peso del síndrome no baja nunca de 5. No se captura.

3. La captura simple no alcanza la capacidad del Golay: falla ya con dos errores, en los 23 patrones de distancia cíclica 11 de los 253 dobles, y con tres errores falla en 736 de 1771, más de cuatro de cada diez. Corrido el decodificador sobre todos, captura 230 dobles y 1035 triples, y en los demás declara la falla: tampoco acá entrega mal ninguno. Para corregir todo patrón de peso 3 hacen falta los refinamientos de la teoría, el de Kasami o la búsqueda sistemática.

4. Lado a lado:

código	ventana / anillo	tramo limpio	dobles	triples
(15,5)	10 / 15	5	105 de 105	450 de 455
Golay (23,12)	11 / 23	12	230 de 253	1035 de 1771

Los dos tienen $d_{min} = 7$ y $t = 3$ . Lo único que cambia es cuánto del anillo cubre la ventana: dos tercios en el (15,5), menos de la mitad en el Golay, y por eso el Golay pide doce posiciones limpias seguidas donde el (15,5) pide cinco. La regla de diseño: la captura de errores sirve cuando $n - k$ es grande respecto de $n$ , en códigos de tasa baja o moderada, y se vuelve ineficaz en los largos y de tasa alta. Y es el método natural para errores que vienen juntos, porque una ráfaga de hasta $n - k$ posiciones deja limpio todo el resto del anillo.

El mismo Golay, factorizado, codificado y acortado, está en el Golay por dentro.

06 · Ejercicio 10: las ráfagas que no se ven

«Sea el código cíclico generado por $g (X) = 1 + X^{2} + X^{4} + X^{5}$ .

Indicar la redundancia $n - k$ del código.
Determinar la fracción de ráfagas no detectadas para longitudes $l = 4, 5, 6, 7$ y 8.
Explicar por qué la fracción se estabiliza a partir de cierta longitud.»

Antes de resolver. Se entregan un número, cinco fracciones y una explicación. El enunciado no da $n$ , y no hace falta: la fracción no depende de él. Para ubicarse igual, $g (1) = 1 + 1 + 1 + 1 = 0$ , así que $1 + X$ lo divide, y

g (X) = (1 + X) (1 + X + X^{4})

con $1 + X + X^{4}$ primitivo. El menor $n$ con $g (X)$ divisor de $X^{n} + 1$ es 15: es el (15,10) de distancia 4, las palabras de peso par del Hamming cíclico (15,11). Y una ráfaga de largo $l$ es un patrón cuyos errores caen en $l$ posiciones consecutivas, con la primera y la última erradas; lo del medio puede valer cualquier cosa.

Las herramientas. Polinómicamente, una ráfaga de largo $l$ es

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

y como los coeficientes de los dos extremos valen 1 y los $l - 2$ del medio son libres, hay $2^{l - 2}$ ráfagas de largo $l$ para cada arranque $i$ . La ráfaga no se detecta cuando $e (X)$ es una palabra de código, o sea, un múltiplo de $g (X)$ . Como $g_{0} = 1$ , $g (X)$ y $X^{i}$ no comparten factores, y eso pasa si y sólo si $g (X)$ divide a $B (X)$ . De ahí sale el teorema 6: si $l \leq n - k$ , $B (X)$ es no nulo y de grado menor que $g (X)$ , y toda ráfaga se detecta, también las que dan la vuelta por el extremo del bloque.

El razonamiento. Para $l > n - k$ hay que contar los múltiplos. Un $B (X) = a (X) g (X)$ de grado $l - 1$ pide $\deg a (X) = l - 1 - (n - k)$ , y $B_{0} = 1$ pide $a_{0} = 1$ . Con $l = n - k + 1$ el único $a (X)$ posible es 1: una sola ráfaga, la propia $g (X)$ . Con $l \geq n - k + 2$ , $a (X)$ tiene sus dos extremos en 1 y $l - n + k - 3$ coeficientes libres. Las fracciones:

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

\frac{2^{l - n + k - 3}}{2^{l - 2}} = 2^{- (n - k)} con l \geq n - k + 2

Las cuentas a la vista, con $n - k = 5$ . Para reducir módulo $g (X)$ alcanza con una regla: como $g (X) = 0$ en el resto,

X^{5} \equiv 1 + X^{2} + X^{4} (\mod g (X))

La ráfaga de largo 6 con el medio limpio, $B (X) = 1 + X^{5}$ , da

R_{g (X)} {1 + X^{5}} = 1 + (1 + X^{2} + X^{4}) = X^{2} + X^{4} \neq 0

y se detecta. De las 16 de largo 6, la única con resto nulo es $g (X)$ misma. De largo 7, la única es

(1 + X) g (X) = (1 + X^{2} + X^{4} + X^{5}) + (X + X^{3} + X^{5} + X^{6})

= 1 + X + X^{2} + X^{3} + X^{4} + X^{6}

una de 32. De largo 8 son dos de 64: $(1 + X^{2}) g (X) = 1 + X^{5} + X^{6} + X^{7}$ y $(1 + X + X^{2}) g (X) = 1 + X + X^{3} + X^{7}$ . Todas pesan par, y no es casualidad: $1 + X$ divide a $g (X)$ , así que toda palabra del código pesa par, y una ráfaga de peso impar no se le escapa nunca. Buscalas a mano abajo.

Con largo 4 o 5 no hay nada que encontrar: el resto nunca se anula. Con 6 hay exactamente una, y con 8 hay dos. Contadas también sobre el código de largo 15, poniendo cada ráfaga en sus 15 arranques, incluidos los que dan la vuelta, se escapan 15 de 240 de largo 6, 15 de 480 de largo 7 y 30 de 960 de largo 8: las mismas fracciones.

07 · Ejercicio 10 resuelto

1. La redundancia es el grado del generador: $n - k = 5$ .

largo	ráfagas	no detectadas	fracción	por qué
4	4	0	0	l ≤ n − k
5	8	0	0	l ≤ n − k
6	16	1	1/16 = 2⁻⁴	l = n − k + 1
7	32	1	1/32 = 2⁻⁵	l > n − k + 1
8	64	2	1/32 = 2⁻⁵	l > n − k + 1

La columna de ráfagas cuenta las de un arranque fijo; con cualquier otro la cuenta es la misma, porque multiplicar por $X^{i}$ no cambia si $g (X)$ divide o no.

3. Una ráfaga se escapa si y sólo si es $X^{i} a (X) g (X)$ . Pasado $l = n - k + 1$ , cada bit más de largo duplica las ráfagas posibles, que pasan de $2^{l - 2}$ a $2^{l - 1}$ , y duplica también los $a (X)$ posibles, que ganan un coeficiente libre. El cociente queda fijo en $2^{- (n - k)}$ , que depende de la redundancia y no del largo de la ráfaga ni del bloque. En $l = n - k + 1$ la cuenta es otra porque $a (X)$ no tiene dos extremos sino uno solo, el 1, y la fracción sale el doble.

08 · Lo que se lleva a otros ejercicios, y las trampas

Capturar es dejar limpio el arco del mensaje. Un patrón se captura si y sólo si el anillo tiene $k$ posiciones consecutivas sin error. Con eso, contar los patrones que fallan es repartir las posiciones limpias en tramos y pedir que todos sean cortos: sirve para cualquier código cíclico y cualquier peso, sin enumerar.

La que más se escapa es la que se pasa por uno. La fracción de ráfagas no detectadas no crece con el largo: salta en $l = n - k + 1$ y después baja a la mitad y se queda. Para un CRC de 32 bits, el peor caso es $2^{- 31}$ , una de cada 2 147 483 648 ráfagas de largo 33; las de 34 o más pasan una de cada $2^{32}$ . Está contado entero en la ráfaga que más se escapa.

Y las trampas:

Dónde está la ventana. En la forma sistemática cíclica la paridad va primero: la ventana son las posiciones 0 a $n - k - 1$ , con la posición 0 a la izquierda del vector. Pensarla al final, como en la forma sistemática de la Unidad 3, da los mismos conteos pero otros números de desplazamientos.
Hacia dónde gira. Un ciclo del registro multiplica por $X$ : el error en la posición $j$ pasa a la $j + 1$ . El patrón ${10, 12, 14}$ se captura en el ciclo 5, como ${0, 2, 4}$ , y al corregir hay que deshacer el giro: el contenido del registro está en las posiciones originales menos 5.
Cero también es un número. ${2, 3, 6}$ se captura con cero desplazamientos, no con uno: el test se aplica al síndrome antes del primer ciclo.
No capturar no es decodificar mal. Lo que la captura simple pierde lo declara: ni en el (15,5) ni en el Golay entrega una palabra equivocada con tres errores o menos.
El largo de una ráfaga se cuenta con sus dos extremos. $1 + X^{5}$ es una ráfaga de largo 6, no de 5 ni de 2. Y como los extremos están fijos en 1, hay $2^{l - 2}$ de cada largo, no $2^{l}$ .

Para tener a mano

Si $\deg e (X) < n - k$ , el síndrome es el patrón de error. Cada ciclo del registro gira la palabra un lugar hacia arriba.
Test de peso: $w [s^{(i)}] \leq t$ si y sólo si los errores están en la ventana, porque $d_{min} \geq 2 t + 1$ . Lo que no se captura en $n$ ciclos se declara.
Se captura si y sólo si hay $k$ posiciones consecutivas limpias en el anillo.
(15,5): los 105 dobles y 450 de 455 triples; fallan los 5 ${i, i + 5, i + 10}$ .
Golay: 230 de 253 dobles (fallan los 23 a distancia 11) y 1035 de 1771 triples. Misma $t$ , ventana de 11 sobre 23 contra 10 sobre 15.
Ráfagas: todas detectadas hasta $l = n - k$ ; $2^{- (n - k - 1)}$ en $l = n - k + 1$ ; $2^{- (n - k)}$ después. Con $g (X) = 1 + X^{2} + X^{4} + X^{5}$ : 0, 0, 1/16, 1/32, 1/32.