Los códigos de Hamming

La unidad anterior dejó un criterio para leer una matriz de paridad: la distancia mínima es la menor cantidad de columnas de $H$ que suman cero. Leído al revés, es una receta: elegir las columnas es elegir el código. La construcción de Hamming es la respuesta más directa posible a esa receta. Pide que ninguna columna sea nula y que no haya dos iguales, y después toma todas las que cumplen.

01 · La definición

Con $m$ filas, los vectores no nulos de $m$ bits son exactamente $2^{m} - 1$ . Para cada $m \geq 2$ , el código de Hamming de orden $m$ es el código lineal cuya $H$ tiene por columnas esos $2^{m} - 1$ vectores, cada uno una vez. Los parámetros se leen de la definición: hay una columna por posición y una fila por bit de paridad, así que

n = 2^{m} - 1, k = n - m = 2^{m} - 1 - m, m = n - k

Con $m = 3$ sale el (7,4) de la unidad anterior. Escritas las columnas en el orden de los números que representan, del 1 al 7, con el bit más significativo arriba:

H = (\begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix})

La definición fija el conjunto de columnas, no su orden. Dos órdenes distintos dan códigos equivalentes: los mismos parámetros, la misma distribución de pesos, y las posiciones permutadas. El orden es la única libertad de diseño que queda, y se usa para dos cosas distintas que la sección 04 separa. Los primeros miembros de la familia:

m	código	tasa R = k/n	t
3	(7,4)	0,5714	1
4	(15,11)	0,7333	1
5	(31,26)	0,8387	1
6	(63,57)	0,9048	1
7	(127,120)	0,9449	1
8	(255,247)	0,9686	1

La tasa tiende a 1, porque la paridad crece como $m$ y el largo como $2^{m}$ . La capacidad de corrección se queda en $t = 1$ para toda la familia. Esas dos columnas son la tensión entera de la nota.

02 · La distancia mínima es 3

Paso 1: al menos 3. Ninguna columna es nula, así que ninguna sola suma cero. No hay dos iguales, así que ningún par suma cero: $h_{i} + h_{j} = 0$ sólo pasa si $h_{i} = h_{j}$ . Por el criterio de las columnas, $d_{min} \geq 3$ .

Paso 2: la tercera columna. Para ver que no es más, hace falta una palabra de peso 3. Se toman dos columnas cualesquiera, $h_{i}$ y $h_{j}$ con $i \neq j$ . Su suma es un vector de $m$ bits, no nulo porque son distintas. Y como $H$ tiene todos los vectores no nulos, esa suma es la columna de alguna posición $l$ :

h_{l} = h_{i} + h_{j} ⟹ h_{i} + h_{j} + h_{l} = 0

con $l$ distinto de $i$ y de $j$ , porque si fuera $i$ sería $h_{j} = 0$ . El vector con unos en $i$ , $j$ y $l$ cumple $v H^{T} = 0$ : es palabra, de peso 3. Entonces $d_{min} = 3$ y $t = 1$ : corrige un error, o detecta dos.

Paso 3: no se puede alargar. Con $m$ filas no hay una columna número $2^{m}$ que no sea nula ni repetida. Agregarla mete una columna repetida, y dos columnas iguales son una palabra de peso 2. Los Hamming son los códigos más largos con $m$ bits de paridad y $d_{min} = 3$ ; dicho de otro modo, los de mayor tasa para esa distancia.

03 · Perfectos: ningún síndrome libre

La cota de Hamming pide que las $2^{k}$ esferas de radio $t$ quepan en el espacio sin solaparse: $\sum_{i = 0}^{t} (\binom{n}{i}) \leq 2^{n - k}$ . Con $t = 1$ el miembro izquierdo es $1 + n$ , y con $n = 2^{m} - 1$ ,

1 + n = 2^{m} = 2^{n - k}

La cota se cumple con igualdad: todo código de Hamming es un código perfecto. Leído en síndromes, hay $2^{m}$ y se reparten así: el nulo para «sin error» y uno por cada error simple, que es su columna. Los líderes de coset son exactamente la palabra nula y los $n$ vectores de peso 1. No sobra ninguno.

Eso tiene dos caras. La buena: no hay síndromes desperdiciados, y la tabla de decodificación es la lista de las columnas. La mala: no queda ningún síndrome libre para avisar. Con dos errores en $i$ y $j$ el síndrome es $h_{i} + h_{j}$ , que por el paso 2 es la columna $h_{l}$ de una tercera posición. El decodificador invierte $l$ y entrega una palabra con tres bits mal, sin ninguna señal: es con dos errores, el decodificador empeora, y vale para toda la familia, no sólo para el (7,4). Lo arreglan el bit de paridad global del código extendido y los códigos acortados, que dejan síndromes sin dueño.

Los códigos binarios perfectos son pocos. La lista completa son las repeticiones de largo impar, los Hamming y el Golay (23,12). No hay otros.

04 · El orden natural: el síndrome es la dirección

Hay dos órdenes de columnas que valen la pena, y no se pueden tener a la vez.

El orden sistemático pone al final las $m$ columnas de peso 1, de modo que $H = [P^{T} I_{m}]$ y $G = [I_{k} P]$ : es la forma sistemática, con el mensaje intacto en las primeras $k$ posiciones. Es el que usa el (7,4) del curso, y ahí el síndrome no se lee como número: la correspondencia con las posiciones es una tabla.

El orden natural pone en la posición $i$ la columna que representa en binario al número $i + 1$ , con el bit más significativo en la fila 0. Como el síndrome de un error simple es su columna,

s = h_{i} = i + 1 en binario

El síndrome es la dirección del bit errado, contada desde 1. El corrimiento no es un capricho: el número 0 ya está tomado, porque $s = 0$ quiere decir que no hubo error. En el (15,11), un error en la posición 10 —la undécima— da $s = 1011$ , que es 11. El localizador deja de ser una tabla de $2^{m}$ entradas y pasa a ser un decodificador binario de $m$ a $2^{m} - 1$ líneas, una red combinacional que crece linealmente con $n$ .

El precio está en el codificador. Las columnas de peso 1 —los números 1, 2, 4, 8— caen en las posiciones 0, 1, 3 y 7, y el mensaje ocupa las once restantes, intercalado con la paridad. Un orden simplifica el codificador; el otro, el localizador.

Con dos errores la dirección miente de una forma precisa. El síndrome es la suma de las dos columnas, y sumar módulo 2 los dos números en binario es un XOR bit a bit: errores en las posiciones 2 y 9, direcciones 3 y 10, dan $0011 + 1010 = 1001$ , que es 9. El decodificador invierte la posición 8, que estaba bien.

Prendé un bit cualquiera: el síndrome, leído de la fila 0 a la 3, es la posición más uno, y la marca de abajo cae justo sobre el error. Ahora prendé un segundo bit. La marca se va a otra posición, la del XOR de las dos direcciones, y el contador de bits mal pasa de 2 a 3. Probá con tres errores elegidos de modo que una dirección sea el XOR de las otras dos —1, 2 y 3, en las posiciones 0, 1 y 2—: el síndrome da cero y el decodificador no hace nada.

05 · El dual es el símplex

El código dual de un Hamming tiene a $H$ por generadora: es un $(2^{m} - 1, m)$ , y tiene una propiedad rara.

Todas sus palabras no nulas pesan lo mismo, $2^{m - 1}$ . Una palabra del dual es $c = a H$ con $a$ un vector de $m$ bits, y su componente $i$ es el producto $a \cdot h_{i}$ . Con $a \neq 0$ , la función $x \mapsto a \cdot x$ es lineal y no nula, así que vale 0 en un subespacio de dimensión $m - 1$ y 1 en los otros $2^{m - 1}$ vectores, ninguno de ellos nulo. Las columnas de $H$ son todos los no nulos, de modo que exactamente $2^{m - 1}$ de ellas dan $a \cdot h_{i} = 1$ . El peso de $c$ no depende de $a$ .

Un código cuyas palabras están todas a la misma distancia unas de otras se llama símplex, por la figura de vértices equidistantes. En el dual del (15,11) las quince palabras no nulas pesan 8. Su enumerador de pesos tiene dos términos:

B (z) = 1 + n z^{(n + 1) / 2}

06 · La distribución de pesos

Con el dual en la mano, la identidad de MacWilliams da el enumerador del Hamming sin recorrer sus $2^{k}$ palabras. Se reemplaza $B (z)$ en $A (z) = 2^{- (n - k)} (1 + z)^{n} B (\frac{1 - z}{1 + z})$ , se usa $2^{n - k} = n + 1$ , y queda

A (z) = \frac{1}{n + 1} [(1 + z)^{n} + n (1 + z)^{(n - 1) / 2} (1 - z)^{(n + 1) / 2}]

Para el (7,4) da

\frac{1}{8} [(1 + z)^{7} + 7 (1 + z)^{3} (1 - z)^{4}] = 1 + 7 z^{3} + 7 z^{4} + z^{7}

que es la distribución de la unidad anterior. Para el (15,11), enumeradas sus 2048 palabras, la distribución coincide con la de la fórmula término a término:

peso	0	3	4	5	6	7	8	9	10	11	12	15
palabras	1	35	105	168	280	435	435	280	168	105	35	1

El dato que más importa es $A_{3}$ , cuántas palabras hay a la distancia mínima, y sale sin álgebra del paso 2. Cada par de columnas ${h_{i}, h_{j}}$ cierra con una única tercera y da una única palabra de peso 3. Cada palabra de peso 3 se cuenta así tres veces, una por cada par de sus tres posiciones:

A_{3} = \frac{1}{3} (\binom{n}{2}) = \frac{n (n - 1)}{6}

Da 7 en el (7,4), 35 en el (15,11), 155 en el (31,26) y 10 795 en el (255,247). La distancia mínima es 3 para todos, pero la cantidad de vecinos a esa distancia crece con el cuadrado del largo.

07 · Sobre el canal binario simétrico

Sobre un canal que invierte cada bit con probabilidad $p$ , las dos formas de usar el código dan dos probabilidades.

Sólo detectar. Un error pasa sin ser visto cuando el patrón de error es una palabra no nula: $P_{u} (E) = \sum_{i \geq 1} A_{i} p^{i} (1 - p)^{n - i}$ . Con $p$ chico manda el término más bajo, $P_{u} (E) \approx A_{3} p^{3}$ .

Corregir. Como los líderes son el nulo y los de peso 1, la decodificación acierta si y sólo si el canal metió a lo sumo un error:

P (E) = 1 - [(1 - p)^{n} + n p (1 - p)^{n - 1}] \approx (\binom{n}{2}) p^{2}

La aproximación es el primer término de la cola. Sin codificar, un bloque de $n$ bits llega con algún error con probabilidad $1 - (1 - p)^{n} \approx n p$ : el código cambia la dependencia de lineal a cuadrática. Pero el coeficiente $(\binom{n}{2})$ crece con el cuadrado del largo, y a igual $p$ el código largo pierde más bloques que el corto. Con $p = 10^{- 3}$ , la fórmula exacta da $2,09 \cdot 10^{- 5}$ en el (7,4) y $2,74 \cdot 10^{- 2}$ en el (255,247). El largo apuesta todo a que el bloque, cada vez más grande, traiga a lo sumo un error.

La aproximación también tiene su límite, y es el mismo: vale mientras $n p$ sea chico, porque descarta los bloques con tres errores o más. Con $p = 10^{- 2}$ todavía anda en el (7,4), con un 3 % de más, pero en el (255,247) da 3,24: una probabilidad mayor que 1, donde la exacta es 0,724.

08 · La familia por largo

La probabilidad de bloque a igual $p$ no es una comparación justa entre largos, porque el código largo paga menos redundancia. Sobre un enlace BPSK con ruido gaussiano y decisión dura, el código reparte la energía de cada bit de mensaje entre $1 / R$ símbolos, y la probabilidad de cruce del canal es

p = Q (\sqrt{2 R E_{b} / N_{0}})

Un código de tasa alta casi no le quita energía al símbolo. La métrica es la tasa de error de bit después de decodificar, que el apunte aproxima con su ec. (6),

P_{b} \approx \frac{1}{n} \sum_{i = t + 1}^{n} (i + t) (\binom{n}{i}) p^{i} (1 - p)^{n - i}

y la ganancia de codificación es la distancia horizontal entre esa curva y la de no codificar, a igual tasa de error de bit: cuántos dB de $E_{b} / N_{0}$ se ahorran. Para el (7,4) está medida en el código que todos inventan primero no paga nunca. Cuando el objetivo se vuelve cada vez más exigente, la ganancia con decisión dura tiende a un límite, la ganancia asintótica

10 \log_{10} (R (t + 1)) = 10 \log_{10} 2 R

que crece con el largo hacia $10 \log_{10} 2 \approx 3,01$ dB. El porqué está en las pendientes: con $p$ chico, $P_{b}$ va como $p^{t + 1}$ , porque hacen falta $t + 1$ errores para equivocarse, y cada $p$ cae como $e^{- R E_{b} / N_{0}}$ . La cuenta con $d_{min}$ en lugar de $t + 1$ , $10 \log_{10} (R d_{min})$ , es el límite con decisión blanda, y con decisión dura no se alcanza: le faltan $10 \log_{10} (3 / 2) \approx 1,76$ dB. Medido con la ec. (6), la ganancia del (15,11) va 1,15 · 1,53 · 1,61 · 1,64 dB a $10^{- 5}$ , $10^{- 12}$ , $10^{- 20}$ y $10^{- 30}$ : se acerca a 1,66, no a los 3,42 de la otra fórmula. Y llega despacio. Tampoco es un techo estricto: el (7,4) lo pasa, con 0,59 dB a $10^{- 12}$ y 0,61 a $10^{- 30}$ , y recién después vuelve a bajar hacia su 0,58. La ganancia que se especifica es la de una tasa de error concreta, no el límite.

Andá del (7,4) al (255,247) de a uno, con el objetivo en $10^{- 5}$ . Las primeras barras suben y la asintótica también; en algún punto la barra deja de seguirla. Cambiá después el objetivo a $10^{- 12}$ y mirá dónde queda el máximo.

Calculada con la ec. (6) y la $Q$ del canal, buscando por bisección el $E_{b} / N_{0}$ al que cada curva llega a la tasa objetivo:

código	a 10⁻⁵	a 10⁻⁸	a 10⁻¹²	asintótica 10·log₁₀ 2R	cruce
(7,4)	0,41	0,54	0,59	0,58	5,86
(15,11)	1,15	1,41	1,53	1,66	4,16
(31,26)	1,45	1,81	1,99	2,25	4,18
(63,57)	1,52	1,97	2,20	2,58	4,58
(127,120)	1,47	2,00	2,28	2,76	5,10
(255,247)	1,35	1,95	2,28	2,87	5,66

Todo en dB. A $10^{- 5}$ la ganancia crece hasta el (63,57), con 1,52 dB, y después baja, aunque la asintótica siga subiendo. Son los dos efectos de la sección anterior tirando para lados opuestos: el largo le devuelve energía al símbolo, porque $R$ se acerca a 1, y le cobra en $(\binom{n}{2})$ , porque el bloque tiene más lugar para un segundo error. Cuanto más exigente el objetivo, más chico es $p$ en el punto de trabajo, menos pesa el coeficiente y más lejos queda el máximo: a $10^{- 8}$ está en el (127,120), y a $10^{- 12}$ el (127,120) y el (255,247) empatan en 2,28 dB, a tres milésimas.

El cruce —donde la curva codificada corta a la de no codificar, y por debajo del cual codificar empeora— tampoco es monótono: baja de 5,86 dB en el (7,4) a 4,16 en el (15,11) y vuelve a subir. Por encima de 5 dB quedan el (7,4), el (127,120) y el (255,247); los tres del medio cruzan entre 4,16 y 4,58. Y la ganancia no es «una fracción de dB»: a $10^{- 5}$ pasa de 1 dB desde el (15,11). La ec. (6) es una aproximación, pero no es la que mueve estos números: enumerando los $2^{15}$ patrones del (15,11), decodificando por síndrome y contando los bits de mensaje errados, la ganancia exacta a $10^{- 5}$ también da 1,15 dB.

La elección de $m$ en un diseño queda atada a dos cosas de afuera: la redundancia que el sistema tolera, que pone un piso a $m$ , y la tasa de error de bloque que se acepta al $p$ del canal, que pone un techo. Las longitudes $2^{m} - 1$ rara vez coinciden con el bloque que el sistema impone, y por eso en la práctica casi todo Hamming viaja acortado.

Para tener a mano

$H$ tiene por columnas los $2^{m} - 1$ vectores no nulos de $m$ bits: $n = 2^{m} - 1$ , $k = n - m$ . El orden de las columnas da códigos equivalentes.
$d_{min} = 3$ : columnas no nulas y distintas dan $\geq 3$ ; la suma de dos columnas es una tercera, y eso da una palabra de peso 3. Corrige uno.
Perfectos: $1 + n = 2^{m}$ . No queda síndrome libre, y dos errores se corrigen en silencio hacia una tercera posición.
Orden natural: la posición $i$ lleva el número $i + 1$ en binario, y el síndrome de un error simple es esa dirección. Con dos errores, el XOR de las dos direcciones. No es sistemático.
El dual es el símplex $(2^{m} - 1, m)$ : todas sus palabras no nulas pesan $2^{m - 1}$ . Por MacWilliams sale $A (z)$ , y $A_{3} = n (n - 1) / 6$ : 7, 35, 155.
$P_{u} (E) \approx A_{3} p^{3}$ y $P (E) \approx (\binom{n}{2}) p^{2}$ , válida mientras $n p$ sea chico. A igual $p$ , el largo pierde más bloques.
Ganancia con decisión dura a $10^{- 5}$ : 0,41 · 1,15 · 1,45 · 1,52 · 1,47 · 1,35 dB del (7,4) al (255,247). El máximo está en el (63,57) y se corre a códigos más largos cuando el objetivo baja. La asintótica con decisión dura es $10 \log_{10} (R (t + 1))$ , no $10 \log_{10} (R d_{min})$ .