La matriz de paridad y el código dual

La matriz generadora $G$ describe un código desde adentro: dice cómo fabricar cada palabra de código. El receptor no fabrica nada. Tiene en la mano $n$ bits y una sola pregunta: ¿esto es una palabra o no? Para contestarla hace falta la otra descripción, desde afuera: la lista de condiciones que toda palabra cumple. Esa lista es la matriz de paridad $H$ . Y sus filas, tomadas como palabras, forman otro código: el dual.

01 · La definición

Sea $C$ un código $(n, k)$ : un subespacio de $V_{n}$ de dimensión $k$ . Su espacio dual $C_{d}$ es el conjunto de todos los vectores de $V_{n}$ ortogonales a todas las palabras de $C$ , con el producto interno de $GF (2)$ :

v \cdot w = v_{0} w_{0} + v_{1} w_{1} + \dots + v_{n - 1} w_{n - 1} (mód 2)

$C_{d}$ es un subespacio de dimensión $n - k$ . Una matriz de paridad de $C$ es cualquier matriz $H$ de $(n - k) \times n$ cuyas filas sean una base de $C_{d}$ . Cada fila de $H$ es ortogonal a cada fila de $G$ , y eso, escrito de una vez, es

G H^{T} = 0

De ahí sale el criterio de pertenencia. Un vector $v$ de $V_{n}$ es palabra de $C$ si y sólo si

v H^{T} = 0

La ida es una línea: si $v = u G$ , entonces $v H^{T} = u G H^{T} = 0$ . La vuelta es por dimensiones. Los vectores con $v H^{T} = 0$ son el espacio nulo de $H$ , que tiene dimensión $n - (n - k) = k$ porque $H$ tiene rango $n - k$ . Ese espacio contiene a $C$ , que también tiene dimensión $k$ : son el mismo. El código queda descripto dos veces, como el espacio fila de $G$ y como el espacio nulo de $H$ .

Cada fila de $H$ es una ecuación de control de paridad: una suma módulo 2 de ciertas posiciones de $v$ que tiene que dar cero. $v H^{T}$ junta las $n - k$ sumas en un vector. Cuando $v$ es lo que llegó del canal y ese vector no da cero, se llama síndrome, y es el tema de la nota que sigue.

02 · De G a H, paso a paso

Paso 1: la G sistemática. Se lleva $G$ a su forma sistemática, con $P$ de $k \times (n - k)$ :

G = [I_{k} P]

El mensaje sale intacto en las primeras $k$ posiciones y la paridad en las últimas $n - k$ .

Paso 2: proponer H. Se traspone el bloque de paridad y se le pega una identidad del otro lado:

H = [P^{T} I_{n - k}]

Paso 3: comprobar que G Hᵀ da cero. Por bloques, $H^{T}$ es $P$ arriba de $I_{n - k}$ , y el producto da dos veces lo mismo:

G H^{T} = I_{k} P + P I_{n - k} = P + P = 0

En $GF (2)$ todo elemento es su propio opuesto, así que sumar un bloque consigo mismo lo anula.

Paso 4: comprobar que sus filas son una base. El bloque identidad hace que las $n - k$ filas sean independientes: cada una tiene un 1 en una posición donde las demás tienen 0. Son $n - k$ vectores independientes de $C_{d}$ , que tiene dimensión $n - k$ , así que son una base.

Para el (7,4) del curso, con $k = 4$ y $n - k = 3$ :

G = [\begin{matrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{matrix}] H = [\begin{matrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{matrix}]

Las tres filas de $H$ , como ecuaciones:

\begin{array}{l} v_{0} + v_{2} + v_{3} + v_{4} = 0 \\ v_{0} + v_{1} + v_{2} + v_{5} = 0 \\ v_{1} + v_{2} + v_{3} + v_{6} = 0 \end{array}

Pasando el último término de cada una al otro lado, que en $GF (2)$ no le cambia el signo, quedan $p_{0} = u_{0} + u_{2} + u_{3}$ , $p_{1} = u_{0} + u_{1} + u_{2}$ y $p_{2} = u_{1} + u_{2} + u_{3}$ : las tres paridades del codificador. La $H$ sistemática es el codificador escrito como verificación. La palabra 1001 011 las cumple: $1 + 0 + 1 + 0$ , $1 + 0 + 0 + 1$ y $0 + 0 + 1 + 1$ dan cero. Contando sobre los 128 vectores de $V_{7}$ , cada ecuación sola la cumplen 64, y las tres juntas, 16: las palabras.

H no es única. Cualquier base de $C_{d}$ sirve. Reemplazando la primera fila por la suma de las dos primeras sale 0101110 en lugar de 1011100: cambian las ecuaciones, y el conjunto de vectores que las cumple, comprobado sobre los 128, es el mismo. Una base ordenada de un espacio de dimensión 3 sobre $GF (2)$ se elige de $7 \cdot 6 \cdot 4 = 168$ maneras, así que el (7,4) tiene 168 matrices de paridad. La de la forma $[P^{T} I]$ es la que se escribe sin hacer cuentas.

Y G tiene que poder ser sistemática. Si las primeras $k$ columnas de $G$ son dependientes, no hay $[I_{k} P]$ sin permutar columnas. Con $G$ de filas 1100 y 0011, las dos primeras columnas son iguales. Intercambiando las posiciones 1 y 2 queda $[I_{2} I_{2}]$ , la receta da $H^{'} = [I_{2} I_{2}]$ , y hay que deshacer el intercambio en $H^{'}$ para volver al código original: sale $H$ con filas 1100 y 0011, igual a $G$ . No es casualidad, y vuelve en la sección 06.

03 · Las columnas de H

Leída por filas, $H$ son ecuaciones. Leída por columnas dice otra cosa. La columna $h_{i}$ es lo que aporta la posición $i$ a las $n - k$ sumas: si $v$ tiene unos en las posiciones $i$ , $j$ y $l$ , entonces $v H^{T}$ es la suma de $h_{i}$ , $h_{j}$ y $h_{l}$ , puestas en fila. Las siete columnas de la $H$ del (7,4) son

h_{0} = [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}], h_{1} = [\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}], h_{2} = [\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}], h_{3} = [\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}], h_{4} = [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}], h_{5} = [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}], h_{6} = [\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}]

Son los siete vectores no nulos de $V_{3}$ , cada uno una sola vez. De ahí salen dos cosas que la $G$ no deja ver. Ninguna columna es nula, así que cambiar un solo bit de una palabra rompe al menos una ecuación. Y no hay dos columnas iguales, así que cambiar dos bits tampoco las deja en cero: dos columnas distintas no se cancelan. La distancia mínima es justamente la menor cantidad de columnas de $H$ que suman cero, y en el (7,4) son tres: $h_{0} + h_{4} + h_{5} = 0$ , que es la palabra 1000 110.

La segunda consecuencia es la que corrige. Con un solo bit cambiado, en la posición $i$ , las tres sumas dan exactamente $h_{i}$ . Como las siete columnas son distintas, el resultado dice cuál bit fue. Ésa es la definición de los códigos de Hamming —columnas distintas y no nulas, todas las que entran en $V_{n - k}$ — y la Unidad 4 los construye así, eligiendo la $H$ antes que la $G$ .

Desde 1000 000 fallan las dos primeras ecuaciones: la columna $h_{0} = 110$ . Tocá sólo los tres últimos bits, $v_{4}$ a $v_{6}$ . Cada uno aparece en una sola ecuación —es el bloque identidad de $H$ —, así que cada uno arregla o rompe la suya sin tocar las otras, y para el mensaje 1000 hay exactamente una paridad que cumple las tres: 110. Lo mismo con cualquier mensaje: las 16 palabras son los 16 mensajes, cada uno con su única paridad. Después, desde una palabra, cambiá un bit cualquiera: se rompen una, dos o tres ecuaciones, según cuántos unos tenga su columna, y nunca ninguna.

El botón del dual cambia la matriz por la $G$ del (7,4): cuatro ecuaciones, ocho palabras, y cada palabra que encuentres tiene peso 4 o es la nula. Con el (8,4) la matriz es otra vez una $[P^{T} I]$ , pero las palabras que salen esconden algo: las dos secciones que siguen lo explican.

04 · El código dual

$C_{d}$ es un subespacio de $V_{n}$ , así que es a su vez un código lineal, de parámetros $(n, n - k)$ : el código dual de $C$ . Su matriz generadora es la $H$ de $C$ , y su matriz de paridad es la $G$ de $C$ . Los roles se cambian: lo que para uno es verificar, para el otro es fabricar. Y la relación es simétrica: el dual del dual es el código original.

El dual del (7,4) es un (7,3), con tasa $R = 3 / 7$ y $2^{3} = 8$ palabras: las combinaciones de las tres filas de $H$ .

0000000 · 1011100 · 1110010 · 0101110 · 0111001 · 1100101 · 1001011 · 0010111

Las siete no nulas tienen peso 4. Su enumerador de pesos es $B (z) = 1 + 7 z^{4}$ , y su distancia mínima, 4: un código donde todas las palabras no nulas están a la misma distancia de todas las demás. Se lo llama símplex.

El dual sirve también para contar. La identidad de MacWilliams da el enumerador de un código a partir del de su dual:

A (z) = 2^{- (n - k)} (1 + z)^{n} B (\frac{1 - z}{1 + z})

Con $B (z) = 1 + 7 z^{4}$ , $n = 7$ y $n - k = 3$ devuelve $A (z) = 1 + 7 z^{3} + 7 z^{4} + z^{7}$ , la distribución del (7,4), sin enumerar sus 16 palabras. Cuando $n - k$ es chico y el dual tiene pocas palabras, ése es el camino corto. Para un código con 16 bits de paridad son 65 536 palabras del dual contra las $2^{k}$ del código.

05 · Paridad simple y repetición, un par dual

El código de paridad simple $(n, n - 1)$ agrega a $n - 1$ bits de mensaje un único bit que deja par la cantidad de unos. Su matriz de paridad es una sola fila de unos,

H = [1 1 \dots 1]

y la única ecuación dice que la suma de todos los bits es cero. Todas sus palabras tienen peso par, así que $d_{min} = 2$ : detecta cualquier cantidad impar de errores y no corrige ninguno. Su tasa, $(n - 1) / n$ , es casi 1.

El código de repetición $(n, 1)$ tiene dos palabras, la nula y la de todos unos. Su matriz generadora es

G = [1 1 \dots 1]

la misma fila. La $G$ de uno es la $H$ del otro: son duales. Medido con $n = 5$ : la repetición (5,1) tiene $d_{min} = 5$ , y su dual, un (5,4) con 10 palabras de peso 2 y 5 de peso 4, tiene $d_{min} = 2$ .

El par marca los dos extremos. Con $n$ fijo, la paridad simple tiene la mayor tasa posible para un código que detecte algo, y la repetición la mayor $d_{min}$ posible, $n$ . Con $n$ impar la repetición corrige hasta $(n - 1) / 2$ errores votando por mayoría, y es un código perfecto. Todo código interesante vive en algún punto entre los dos.

06 · El (8,4), que es su propio dual

Un código es auto-dual si coincide con su dual: $C = C_{d}$ . Las dimensiones ya ponen la condición: $k = n - k$ , así que $n$ es par y la tasa es exactamente $1 / 2$ . El (7,4) no puede serlo.

Que existan depende de algo que en los reales no pasa: en $GF (2)$ un vector no nulo puede ser ortogonal a sí mismo, porque $v \cdot v$ es la cantidad de unos de $v$ módulo 2. $C \subseteq C_{d}$ pide que cada palabra sea ortogonal a todas, ella incluida, así que todas las palabras de un código auto-dual tienen peso par. Con $G$ alcanza mirar las filas: $C \subseteq C_{d}$ si y sólo si $G G^{T} = 0$ . Y si $G = [I_{k} P]$ , entonces $G G^{T} = I_{k} + P P^{T}$ : el código es auto-dual cuando $k = n / 2$ y $P P^{T} = I$ , o sea cuando $P^{T}$ es la inversa de $P$ .

El ejemplo que importa es el Hamming extendido (8,4): el (7,4) con un octavo bit de paridad global, que deja par cada palabra.

G = [\begin{matrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{matrix}] H = [\begin{matrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \end{matrix}]

$G G^{T} = 0$ , y su enumerador es $A (z) = 1 + 14 z^{4} + z^{8}$ : catorce palabras de peso 4, la nula y la de todos unos, todas de peso par. Su $d_{min}$ es 4. Las dos matrices son distintas y generan el mismo código: las filas de $H$ son las palabras de los mensajes 1011, 1110, 0111 y 1101. Cada palabra del (8,4) es a la vez algo que se transmite y una ecuación que toda palabra cumple. El (7,4), en cambio, tiene filas de peso 3 en su $G$ , y una fila de peso impar no es ortogonal a sí misma: $G G^{T} \neq 0$ .

El auto-dual más chico es la repetición (2,1), 00 y 11, que es también la paridad simple de largo 2: con $n = 2$ el par dual de la sección anterior colapsa en un solo código. Y el (4,2) de filas 1100 y 0011 de la sección 02 es otro: por eso ahí la $H$ salía igual a la $G$ .

07 · Lo que no se traslada de los reales

Con vectores reales, un subespacio y su complemento ortogonal sólo comparten el cero y, juntos, generan todo el espacio. Es tentador pensar el dual así, y en $GF (2)$ se rompe. El dual del (7,4) no está al costado del código: está adentro. Las ocho palabras del (7,3) son exactamente las ocho palabras de peso par del (7,4), comprobado sobre las 16. Entonces $C \cap C_{d} = C_{d}$ , y $C + C_{d} = C$ , de dimensión 4: no es $V_{7}$ . En el (8,4) es el caso extremo, la intersección es todo.

Lo único que sobrevive es la cuenta de dimensiones, $\dim C + \dim C_{d} = n$ : $4 + 3 = 7$ . No hay una descomposición de un vector en «parte en el código más parte en el dual», porque las dos partes juntas no llegan a todo $V_{n}$ . Dual quiere decir ortogonal, no complementario.

Y el criterio de pertenencia tiene su propio límite. $v H^{T} = 0$ dice si $v$ es una palabra, no si es la que se mandó. Un patrón de error que sea él mismo una palabra de código pasa las ecuaciones sin dejar rastro: en el (7,4) son 15 de los 127 patrones no nulos, y un síndrome cero no prueba nada.

Para tener a mano

$H$ es $(n - k) \times n$ , sus filas son una base del dual, y $G H^{T} = 0$ . Un vector es palabra si y sólo si $v H^{T} = 0$ : el código es el espacio nulo de $H$ .
Con $G = [I_{k} P]$ , $H = [P^{T} I_{n - k}]$ , sin signo menos porque en $GF (2)$ menos uno es uno. Despejando, sus ecuaciones son las paridades del codificador.
$H$ no es única: cualquier base del dual sirve. El (7,4) tiene 168.
Por filas, ecuaciones; por columnas, lo que aporta cada posición. Columnas no nulas y distintas: $d_{min} \geq 3$ . En el (7,4) son los siete no nulos de $V_{3}$ .
El dual es un $(n, n - k)$ con $G_{d} = H$ y $H_{d} = G$ . El del (7,4) es el símplex (7,3): siete palabras de peso 4, todas dentro del (7,4).
Paridad simple $(n, n - 1)$ y repetición $(n, 1)$ son duales: $d_{min} = 2$ con la mayor tasa, $d_{min} = n$ con la menor.
Auto-dual: $C = C_{d}$ , $k = n / 2$ , todas las palabras de peso par, $G G^{T} = 0$ . El (8,4) lo es, con $d_{min} = 4$ y enumerador $1 + 14 z^{4} + z^{8}$ .
Dual no es complemento: en $GF (2)$ el código y su dual pueden compartir palabras, y sólo vale $\dim C + \dim C_{d} = n$ .