Las cotas de Singleton y de Hamming

Un código $(n, k)$ gasta $n - k$ bits de paridad por bloque. Lo que compra con ellos es distancia mínima, y la pregunta es cuánta. Hay dos respuestas elementales, y las dos son techos: dicen qué $d_{min}$ no se puede tener, nunca cómo conseguir el que sí. La de Singleton sale de mirar una sola palabra; la de Hamming, de contar vectores. En binario la segunda casi siempre aprieta más, y los códigos que la tocan exactamente son tan pocos que se pueden nombrar todos.

01 · La cota de Singleton

Todo código lineal $(n, k)$ cumple

d_{min} \leq n - k + 1

Paso 1: llevar el código a forma sistemática. Todo código lineal tiene una matriz generadora en forma sistemática, $G = [I P]$ , permutando posiciones si hace falta. Permutar posiciones no le cambia el peso a ninguna palabra, así que tampoco la $d_{min}$ .

Paso 2: mirar un mensaje de un solo uno. Su palabra es una fila de $G$ . En las $k$ posiciones del mensaje tiene exactamente un uno; en las $n - k$ de paridad, como mucho $n - k$ . Su peso no pasa de $1 + (n - k)$ .

Paso 3: la distancia mínima es el peso mínimo. En un código lineal $d_{min} = w_{min}$ , y acabamos de encontrar una palabra no nula de peso $\leq n - k + 1$ .

La misma cota sale desde la matriz de paridad. $H$ tiene $n - k$ filas, así que sus columnas viven en un espacio de dimensión $n - k$ , y cualquier conjunto de $n - k + 1$ columnas es linealmente dependiente: algún subconjunto suma cero. Como $d_{min}$ es la menor cantidad de columnas de $H$ que suman cero, no pasa de $n - k + 1$ .

En el (7,4) las filas de $G$ son 1000 110, 0100 011, 0010 111 y 0001 101, de pesos 3, 3, 4 y 3. Singleton da $d_{min} \leq 4$ ; la $d_{min}$ real es 3. Pasada a capacidad de corrección, con $t = ⌊ (d_{min} - 1) / 2 ⌋$ , la cota dice $t \leq ⌊ (n - k) / 2 ⌋$ : cada error que se quiere corregir cuesta por lo menos dos bits de paridad.

02 · Los MDS, y por qué en binario no hay

Un código que alcanza la cota con igualdad, $d_{min} = n - k + 1$ , se llama de máxima distancia separable, MDS. Cada bit de paridad compra exactamente un bit de distancia: no se desperdicia nada. Los Reed–Solomon son el ejemplo por excelencia.

En binario, los únicos MDS son tres familias triviales: la repetición $(n, 1)$ , con $d_{min} = n$ ; la paridad simple $(n, n - 1)$ , con $d_{min} = 2$ ; y $V_{n}$ entero, con $d_{min} = 1$ . La prueba es corta.

Paso 1: un MDS con $2 \leq k \leq n - 2$ tendría las filas de $P$ llenas de unos. Con $G = [I P]$ , cada fila de $G$ es una palabra y tiene que pesar por lo menos $n - k + 1$ . Tiene un solo uno en la parte de $I$ , así que los $n - k$ bits de su parte de $P$ tienen que ser todos uno.

Paso 2: entonces dos filas suman una palabra liviana. Si todas las filas de $P$ son iguales, la suma de dos filas de $G$ tiene dos unos en la parte de $I$ y ceros en la de $P$ : pesa 2. Y $2 < n - k + 1$ porque $n - k \geq 2$ . Contradicción.

Los casos que la prueba deja afuera, $k = 1$ , $k = n - 1$ y $k = n$ , son justo las tres familias. Como control, se recorrieron todas las $G$ sistemáticas con $4 \leq n \leq 8$ y $2 \leq k \leq n - 2$ , enumerando las palabras de cada una: son 150.672 matrices y ninguna llega a $n - k + 1$ . Para un código binario de verdad, Singleton es una cota floja. La que aprieta es la otra.

03 · La cota de Hamming

Alrededor de cada palabra de código se dibuja una esfera de radio $t$ : los vectores que están a distancia $\leq t$ de ella. Si el código corrige $t$ errores,

\sum_{i = 0}^{t} (\binom{n}{i}) \leq 2^{n - k}

Paso 1: contar una esfera. Los vectores a distancia exactamente $i$ de una palabra son los que difieren en $i$ posiciones, y elegir esas posiciones se puede de $(\binom{n}{i})$ maneras. Sumando las capas de $i = 0$ a $t$ sale el lado izquierdo. No depende de la palabra: todas las esferas tienen el mismo volumen.

Paso 2: las esferas no se tocan. Si dos esferas de radio $t$ compartieran un vector, sus centros estarían a distancia $\leq 2 t$ , y $2 t < d_{min}$ .

Paso 3: caben en $V_{n}$ . Son $2^{k}$ esferas disjuntas dentro de $2^{n}$ vectores. Dividiendo por $2^{k}$ queda la cota. Por eso se la llama también cota de empaquetamiento de esferas.

El lado derecho tiene una lectura más directa. $2^{n - k}$ es la cantidad de síndromes, y para corregir todos los patrones de error de peso $\leq t$ , cada uno tiene que ser el líder de su propio coset, con su propio síndrome. La cota dice que no hay más patrones para corregir que síndromes para distinguirlos.

En el (7,4) hay $2^{3} = 8$ síndromes, y los patrones de peso $\leq 1$ son $1 + 7 = 8$ : no sobra ninguno. Para corregir dos errores harían falta $1 + 7 + 21 = 29$ . Leída al revés, la cota es un precio: con $n = 15$ y $t = 2$ hay $1 + 15 + 105 = 121$ patrones que proteger, más que $2^{6} = 64$ , así que hacen falta por lo menos 7 bits de paridad.

04 · Cuál de las dos aprieta

Las dos cotas se pueden comparar en la misma moneda, el $t$ máximo. Singleton da $⌊ (n - k) / 2 ⌋$ ; Hamming, el mayor $t$ cuya esfera entra en $2^{n - k}$ . Calculadas en aritmética entera exacta:

código	d_min ≤ n − k + 1	Singleton: t ≤	Hamming: t ≤	esfera / síndromes
(7,4)	4	1	1	8 / 8
(8,4)	5	2	1	9 / 16
(15,11)	5	2	1	16 / 16
(15,7)	9	4	2	121 / 256
(23,12)	12	5	3	2048 / 2048
(24,12)	13	6	3	2325 / 4096
(255,239)	17	8	2	32.641 / 65.536

Recorriendo todos los pares con $1 \leq k < n \leq 64$ , que son 2016, Hamming da un $t$ estrictamente menor en 1887 y el mismo en los otros 129. En ninguno da uno mayor. La brecha crece con el largo: un (255,239) binario, el largo del BCH del trabajo final, no puede corregir más de 2 errores, aunque Singleton le dejaría 8. Con 16 símbolos de paridad de un byte, un Reed–Solomon sí corrige 8, porque cuenta símbolos y no bits.

05 · Los códigos perfectos

Un código que alcanza la cota de Hamming con igualdad es perfecto:

\sum_{i = 0}^{t} (\binom{n}{i}) = 2^{n - k}

Las esferas cubren $V_{n}$ sin dejar un solo vector afuera: todo vector recibido está a distancia $\leq t$ de exactamente una palabra. Dicho con síndromes, los líderes son exactamente los patrones de peso $\leq t$ y no queda ninguno libre. Eso tiene un costo que se suele pasar por alto: un decodificador nunca encuentra un vector entre esferas, así que todo patrón de más de $t$ errores termina en una palabra equivocada, en silencio. La decodificación incompleta no tiene dónde levantar la bandera; lo mide el ensayo de la bandera.

Los códigos binarios perfectos son éstos:

Los triviales. $V_{n}$ entero, con $k = n$ y $t = 0$ . Y la repetición de largo impar, $(2 t + 1, 1)$ : por simetría, las capas de peso $\leq t$ son la mitad exacta de $V_{n}$ , o sea $2^{n - 1}$ . Con largo par la capa del medio queda partida entre las dos esferas: la (6,1) cubre 22 de sus 32 síndromes.
Los Hamming. Con $t = 1$ la igualdad es $1 + n = 2^{n - k}$ , que pide $n = 2^{m} - 1$ y $k = n - m$ : (7,4), (15,11), (31,26)… El (7,4) es el caso $8 = 1 + 7$ .
El Golay (23,12), con $t = 3$ : $1 + 23 + 253 + 1771 = 2048 = 2^{11}$ . Es el único que corrige más de un error sin ser una repetición.

Que no hay otros es un teorema, y hay que enunciarlo con cuidado. Tietäväinen, y por su lado Zinoviev y Leontiev, probaron en 1973 que todo código binario perfecto no trivial tiene los parámetros de un Hamming o del Golay (23,12). Si además es lineal, es un Hamming o un Golay, salvo el orden de las posiciones. Sin linealidad la frase no vale: existen códigos perfectos no lineales con los parámetros de Hamming que no son el Hamming (Vasil'ev, 1962).

El widget de abajo deja buscar las igualdades a mano. Como control, la búsqueda exhaustiva con $1 \leq k < n \leq 300$ y $t \geq 1$ encuentra, con $k = 1$ , exactamente las 149 repeticiones de largo impar de 3 a 299. Con $k \geq 2$ encuentra ocho ternas $(n, k, t)$ : los seis Hamming de (7,4) a (255,247), el Golay, y una más que no está en la lista.

En el (8,4) la esfera de radio 1 ocupa 9 de los 16 síndromes y quedan 7 vacíos; la capa de peso 2 trae 28 patrones y no entra. Bajá $n$ a 7 y el hueco desaparece: es el (7,4). Subí a $n = 15$ con $k = 11$ y pasa lo mismo, y con cualquier $k$ más chico el hueco vuelve. Las igualdades son aisladas: casi toda la grilla de $(n, k)$ deja síndromes de sobra. El botón salta a la próxima. Entre el (63,57) y el (127,120) aparece una que no es ningún código conocido.

06 · Donde la cuenta cierra y el código no existe

Con $n = 90$ , $k = 78$ y $t = 2$ , la igualdad se cumple:

1 + 90 + 4005 = 4096 = 2^{12}

Y no hay ningún código binario de largo 90 con $2^{78}$ palabras y $d_{min} \geq 5$ , lineal o no. Lo notó Golay en 1949, y la prueba es una cuenta.

Paso 1: suponer que existe y que tiene al cero. Sumarle a todas las palabras una palabra fija no cambia ninguna distancia, así que se puede suponer que la palabra nula está en el código. Perfecto con $t = 2$ quiere decir que todo vector está a distancia $\leq 2$ de exactamente una palabra.

Paso 2: a un vector de peso 3 lo cubre una palabra de peso 5 que lo contiene. Sea $x$ de peso 3. Está a distancia 3 del cero, así que lo cubre otra palabra $c$ , con $w (c) \geq 5$ . Como $d (x, c) \geq w (c) - 3$ y tiene que valer $\leq 2$ , queda $w (c) = 5$ con los tres unos de $x$ adentro de los cinco de $c$ .

Paso 3: fijar dos posiciones y contar. Los vectores de peso 3 con unos en las posiciones 0 y 1 son 88: el tercer uno va en cualquiera de las otras 88. Cada uno está adentro de exactamente una palabra de peso 5, que también tiene unos en 0 y 1. Y una palabra de peso 5 con unos en 0 y 1 contiene exactamente 3 de esos vectores, uno por cada una de sus otras tres posiciones. Si hay $N$ palabras así, $3 N = 88$ . Pero 88 no es múltiplo de 3.

La misma cuenta, sobre los perfectos que sí existen, da enteros: en el (7,4), fijando una posición, 6 vectores de peso 2 se reparten de a 2 entre 3 palabras de peso 3; en el Golay, fijando tres, 20 vectores de peso 4 se reparten de a 4 entre 5 palabras de peso 7. La cota de Hamming es necesaria, no suficiente: una igualdad entre números no fabrica un código.

Para tener a mano

Singleton: $d_{min} \leq n - k + 1$ , porque una fila de $[I P]$ ya pesa eso como mucho. En corrección, $t \leq ⌊ (n - k) / 2 ⌋$ : dos bits de paridad por error.
MDS es alcanzarla. En binario sólo la alcanzan la repetición, la paridad simple y $V_{n}$ ; los MDS útiles, como Reed–Solomon, viven sobre símbolos de $GF (2^{m})$ .
Hamming: $\sum_{i = 0}^{t} (\binom{n}{i}) \leq 2^{n - k}$ : las $2^{k}$ esferas caben en $V_{n}$ , o los patrones a corregir no superan a los síndromes.
En binario aprieta más Hamming: con $n \leq 64$ , da un $t$ menor en 1887 de 2016 pares y nunca uno mayor.
Perfecto es la igualdad: sin hueco entre esferas, y por eso sin margen para detectar nada más allá de $t$ .
Binarios perfectos: $V_{n}$ , la repetición de largo impar, los parámetros de Hamming $(2^{m} - 1, 2^{m} - 1 - m)$ y los del Golay (23,12). Lineales, son exactamente esos códigos.
La igualdad es necesaria, no suficiente: (90,78) la cumple y no existe, porque 88 vectores no se reparten de a 3.