El código de Golay

Hamming resolvió el caso de un error, y lo resolvió con una familia entera: un código para cada cantidad de bits de paridad. Para más de un error, fuera de las repeticiones, hay una sola respuesta perfecta, y no es una familia sino un código suelto de 23 bits. Su versión de 24 es la que se usa, y trae adentro una estructura combinatoria que no tiene nada que ver con corregir errores y que, sin embargo, explica exactamente qué pasa cuando llegan cuatro.

01 · El (23, 12, 7)

El código de Golay es un código lineal binario $(n, k, d_{min}) = (23, 12, 7)$ . Con distancia mínima 7, su capacidad de corrección es

t = ⌊ \frac{d_{min} - 1}{2} ⌋ = 3, R = \frac{k}{n} = \frac{12}{23} \approx 0,522

con once bits de paridad. Una matriz generadora tiene doce filas, y la más corta de escribir arma cada una corriendo la anterior un lugar. La primera es el vector de los exponentes de

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

o sea $10101110 00110000 0000000$ , con la posición 0 a la izquierda, y la fila $i$ es ese mismo vector desplazado $i$ lugares a la derecha: $X^{i} g (X)$ , para $i = 0, \dots, 11$ . Que un polinomio genere el código entero es la estructura cíclica del Golay, y con ella su decodificación eficiente: las dos son tema de la Unidad 5. Acá alcanza con la $G$ . El apunte menciona otras construcciones —por residuos cuadráticos módulo 23, desde el icosaedro, lexicográfica—, y todas dan el mismo código salvo una permutación de las posiciones.

Enumeradas las $2^{12} = 4096$ palabras, los pesos son éstos, los de la Figura 5 del apunte:

código	0	7	8	11	12	15	16	23	24
(23, 12)	1	253	506	1288	1288	506	253	1	—
(24, 12)	1	0	759	0	2576	0	759	0	1

Los dos renglones suman 4096. El primero no tiene ninguna palabra de peso entre 1 y 6, y por eso $d_{min} = 7$ . El segundo es el extendido de la sección 03. Los dos son simétricos, $A_{i} = A_{n - i}$ , porque la palabra de todos unos está en los dos códigos: sumarla a una palabra de peso $i$ da una de peso $n - i$ .

02 · Por qué es perfecto

Paso 1: contar una esfera. Alrededor de cada palabra, los vectores a distancia $\leq 3$ son la palabra misma, los 23 que difieren en un bit, los que difieren en dos y los que difieren en tres:

\sum_{i = 0}^{3} (\binom{23}{i}) = 1 + 23 + 253 + 1771 = 2048 = 2^{11}

Paso 2: multiplicar por las palabras. Las esferas de radio 3 no se pisan, porque $d_{min} = 7$ . Entre las $2^{12}$ esferas juntan $2^{12} \cdot 2^{11} = 2^{23}$ vectores: todos los de largo 23. No queda ninguno afuera. Es la igualdad en la cota de Hamming, que es la definición de código perfecto.

Paso 3: leerlo con síndromes. Hay $2^{n - k} = 2048$ síndromes y exactamente 2048 patrones de peso $\leq 3$ , cada uno con su síndrome propio. Armada la tabla de decodificación, los líderes de coset son 1 de peso 0, 23 de peso 1, 253 de peso 2 y 1771 de peso 3: sin empates y sin síndromes libres. La decodificación por tabla del apunte es esa: 2048 entradas, una por cada patrón que el código promete corregir, y ni una más.

Que una igualdad así sólo se dé, con $t \geq 2$ y fuera de las repeticiones, en este código —y que el $(90, 78)$ cumpla la cuenta sin existir— está en las cotas de Singleton y de Hamming. Lo que importa acá es el precio. Con cuatro errores lo recibido cae, siempre, en la esfera de otra palabra: de los 8855 patrones de peso 4, los 8855 tienen un líder de peso 3 en su síndrome, y el decodificador entrega una palabra que está a distancia 7 de la enviada. Le pasa a todo código perfecto, y en el $(7, 4)$ lo mide en un código perfecto, la bandera no se levanta.

03 · El extendido (24, 12, 8)

A cada palabra se le agrega en la posición 23 un bit de paridad global, la suma de las otras 23. Es el código extendido, y el teorema de la extensión dice que una distancia impar sube en uno: las palabras de peso 7 ganan un 1 y pasan a peso 8, las de peso 8 quedan como estaban. Queda un $(24, 12, 8)$ , y el segundo renglón de la tabla de arriba es esa cuenta hecha: $253 + 506 = 759$ palabras de peso 8, $1288 + 1288 = 2576$ de peso 12.

Ya no es perfecto. Con $d_{min} = 8$ sigue corrigiendo 3, pero ahora sobra margen: $3 + 4 + 1 \leq 8$ , así que en modo mixto corrige 3 y detecta 4. El apunte da tres razones para preferirlo al perfecto: la tasa es exactamente $R = 1 / 2$ , el largo es de tres octetos, y es auto-dual. La tercera es la que da casi todo lo demás.

04 · Auto-dual, con pesos múltiplos de 4

Un código es auto-dual cuando es igual a su código dual: $C = C^{⊥}$ . La misma $G$ sirve de matriz de paridad.

Paso 1: las filas son ortogonales. Cada fila de $G$ es $X^{i} g (X)$ , de peso 7, más su paridad: peso 8, par, así que cada fila es ortogonal a sí misma. Y los 144 productos $g_{i} \cdot g_{j}^{T}$ , contados todos los pares con $i = j$ incluidos, dan 0. Por linealidad cualquier par de palabras es ortogonal: $C \subseteq C^{⊥}$ .

Paso 2: las dimensiones cierran. El dual de un $(24, 12)$ tiene dimensión $24 - 12 = 12$ , la misma que $C$ . Un subespacio contenido en otro de la misma dimensión es ese otro: $C = C^{⊥}$ . Por eso hace falta el bit de paridad: un código es auto-dual sólo si $k = n - k$ , y con largo impar eso no se puede.

Paso 3: todo peso es par. Toda palabra es ortogonal a sí misma, y $v \cdot v^{T}$ es la suma de sus unos módulo 2: $w (v)$ es par.

Paso 4: y múltiplo de 4. Con $a \land b$ el vector que tiene un 1 donde $a$ y $b$ tienen un 1 los dos, el peso de una suma descuenta dos veces lo compartido:

w (a + b) = w (a) + w (b) - 2 w (a \land b)

Que $a$ y $b$ sean ortogonales es que $w (a \land b)$ sea par, y entonces el último término es múltiplo de 4. Si $a$ y $b$ tienen peso múltiplo de 4, su suma también. Las filas pesan 8, y toda palabra es una suma de filas: todas las palabras pesan 0, 4, 8, 12, 16, 20 o 24. De ésos, la tabla muestra que el 4 y el 20 no aparecen, porque $d_{min} = 8$ .

05 · Las 759 octadas

Las 759 palabras de peso 8 se llaman octadas, y conviene mirarlas como conjuntos: las ocho posiciones donde valen 1. Forman un sistema de Steiner $S (5, 8, 24)$ : subconjuntos de 8 elementos de un conjunto de 24 tales que cada subconjunto de 5 está en exactamente uno de ellos.

Paso 1: a lo sumo una. Si dos octadas distintas compartieran cinco posiciones, su suma, que también es palabra del código, tendría peso $8 + 8 - 2 \cdot 5 = 6$ , menos que $d_{min}$ . Dos octadas comparten como mucho cuatro posiciones. Medido sobre los 287 661 pares: comparten 0, 2 o 4, y nunca otra cantidad.

Paso 2: contar quintetos. Cada octada contiene $(\binom{8}{5}) = 56$ quintetos, y por el paso 1 ninguno se repite entre octadas. Entre todas cubren

759 \cdot 56 = 42 504 = (\binom{24}{5})

quintetos distintos, que son todos los que hay. Cada uno está en una octada, y en una sola. La enumeración lo confirma uno por uno: los 42 504 quintetos, cada uno en exactamente una de las 759.

La misma cuenta, hecha con menos posiciones, dice cuántas octadas contienen $i$ posiciones dadas, y que el número no depende de cuáles: se cuentan los quintetos que extienden esas $i$ y se divide por los que caen en cada octada,

λ_{i} = \frac{(\binom{24 - i}{5 - i})}{(\binom{8 - i}{5 - i})}

El widget deja hacerlo a mano antes de leer los valores.

Con una posición quedan 253 octadas; con dos, 77; con tres, 21; con cuatro, 5; con cinco, 1. Son $λ_{0}, \dots, λ_{5} = 759, 253, 77, 21, 5, 1$ , y con cada $i$ hasta 5 se recorrieron todos los subconjuntos de $i$ posiciones: el número no cambia en ninguno. El 253 es el $A_{7}$ del perfecto: las octadas con un 1 en la posición 23 son las palabras de peso 7 con su paridad agregada. Con cuatro elegidas pasa lo más interesante: las cinco octadas agregan cuatro posiciones cada una, y esas cinco tétradas no se pisan. Con las tuyas son seis tétradas que reparten las 24 posiciones. El quinto toque cae en una de ellas, y eso elige la octada.

06 · Cuatro errores: corregir no, detectar sí

El $(24, 12)$ tiene $2^{12} = 4096$ síndromes. Los patrones de error de peso $\leq 3$ son $1 + 24 + 276 + 2024 = 2325$ , cada uno con un síndrome propio: son los que se corrigen. Los otros $4096 - 2325 = 1771$ síndromes quedan para los 10 626 patrones de peso 4, que no comparten síndrome con ninguno de peso menor y se reparten de a seis: $1771 \cdot 6 = 10 626$ .

Los seis patrones de un mismo síndrome son las seis tétradas del widget. Dos patrones de peso 4 dan el mismo síndrome cuando su suma es una palabra. Esa suma pesa a lo sumo 8, y como no hay palabras no nulas más livianas, pesa exactamente 8: los dos patrones son disjuntos y juntos forman una octada. Las cuatro posiciones de un error pertenecen a 5 octadas, cada una aporta la tétrada complementaria, y las seis son igual de probables: todas pesan 4. Medido sobre los 10 626 patrones de peso 4, siempre son seis, siempre reparten las 24 posiciones y siempre comparten síndrome. El decodificador no tiene cómo elegir, y lo que sí puede hacer es reconocer que el síndrome no es de ningún patrón de peso $\leq 3$ y avisar. Es la decodificación incompleta, y en el extendido sí tiene dónde levantar la bandera: los 1771 síndromes que el perfecto no tenía.

Decodificar con una tabla de 4096 entradas es realizable, y el apunte lo deja ahí. La estructura de $G$ permite hacerlo sin tabla, con unas pocas pruebas de peso sobre vectores de doce bits, y la decodificación del $(23, 12)$ por su estructura cíclica es de la Unidad 5.

07 · La cuenta en Python

Las dos distribuciones y el sistema de Steiner, desde $g (X)$ y sin nada más. Las palabras se arman sumando filas de a una: después de la fila $i$ la lista tiene todas las combinaciones de las primeras $i + 1$ . Lo de los comentarios es la salida de correrlo.

from itertools import combinations
from collections import Counter

g = [0, 2, 4, 5, 6, 10, 11]               # g(X) = 1 + X² + X⁴ + X⁵ + X⁶ + X¹⁰ + X¹¹
filas = [sum(1 << (e + i) for e in g) for i in range(12)]   # X^i g(X): 23 bits

def extender(v):                          # paridad global en la posición 23
    return v | (bin(v).count('1') % 2) << 23

palabras = [0]
for f in filas:                           # todas las sumas de filas de G
    palabras += [p ^ f for p in palabras]
c24 = [extender(v) for v in palabras]

print(sorted(Counter(bin(v).count('1') for v in palabras).items()))
# [(0, 1), (7, 253), (8, 506), (11, 1288), (12, 1288), (15, 506), (16, 253), (23, 1)]
print(sorted(Counter(bin(v).count('1') for v in c24).items()))
# [(0, 1), (8, 759), (12, 2576), (16, 759), (24, 1)]

octadas = [v for v in c24 if bin(v).count('1') == 8]
cubre = Counter()
for o in octadas:
    pos = [i for i in range(24) if o >> i & 1]
    cubre.update(combinations(pos, 5))
print(len(cubre), set(cubre.values()))
# 42504 {1}

La última línea es el sistema de Steiner: 42 504 quintetos distintos aparecen, y cada uno aparece una vez. El bit $i$ del entero es la posición $i$ , así que el bit 23 es la paridad, la última posición.

08 · Un código suelto

El apunte y Lin y Costello (§4.6) ubican al $(24, 12)$ en las sondas Voyager 1 y 2, en la transmisión de las imágenes en color de Júpiter y Saturno, entre 1979 y 1981. Años antes, Mariner 9 había usado un Reed-Muller $RM (1, 5)$ , un $(32, 6)$ que corrige 7 con tasa $6 / 32 = 3 / 16$ : por cada bit de imagen, más de cinco por el canal. El Golay manda dos.

Lo que no tiene es una familia. Un código de Hamming existe para cada $m$ , y un Reed-Muller para cada $(r, m)$ . El Golay es uno solo, con un largo y una tasa fijos: si un enlace pide corregir tres en otro largo, el Golay no tiene un hermano para ofrecer. Esa ausencia de un método general, que dado $n$ y $t$ dé un código y un decodificador, es con lo que cierra la unidad.

Para tener a mano

Golay: $(23, 12, 7)$ , $t = 3$ , $R \approx 0,522$ . $G$ con filas $X^{i} g (X)$ , $g (X) = 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10} + X^{11}$ .
Perfecto: $1 + 23 + 253 + 1771 = 2^{11}$ . La tabla tiene 2048 líderes, todos los patrones de peso $\leq 3$ , sin empates. Con cuatro errores decodifica siempre a otra palabra.
Pesos del $(23, 12)$ : 1, 253, 506, 1288, 1288, 506, 253, 1 en los pesos 0, 7, 8, 11, 12, 15, 16, 23.
Extendido $(24, 12, 8)$ : paridad global, $R = 1 / 2$ , corrige 3 y detecta 4. Pesos 1, 759, 2576, 759, 1 en 0, 8, 12, 16, 24.
Auto-dual: filas ortogonales y $k = n / 2$ . De ahí, pesos pares; y como $w (a + b) = w (a) + w (b) - 2 w (a \land b)$ , múltiplos de 4.
Las 759 octadas forman un $S (5, 8, 24)$ : $759 \cdot 56 = (\binom{24}{5})$ . Contienen a $i$ posiciones dadas 759, 253, 77, 21, 5 y 1 octadas, para $i = 0, \dots, 5$ .
En el extendido, 2325 síndromes corrigen y 1771 avisan: cada uno de éstos es de seis patrones de peso 4, las seis tétradas que reparten las 24 posiciones.