Matriz generatriz y matriz de paridad

Un código lineal es un subespacio, y un subespacio se puede describir de dos maneras: dando una base (las palabras «ladrillo» con las que se construye todo) o dando ecuaciones (las condiciones que cumplen sus vectores). Cada descripción da una matriz y cada matriz sirve para algo distinto: la primera, para codificar; la segunda, para comprobar si lo que ha llegado es una palabra del código. Es una idea parecida a la del dígito de control del DNI o del IBAN, pero para códigos que además corrigen.

La idea

Piensa en el código de Hamming $[7,4,3]$. Para enviar 4 bits necesitas una regla que los convierta en una palabra de 7: multiplicar el mensaje por una matriz. Si el mensaje se copia en las primeras 4 posiciones y se añaden 3 bits de control, el receptor lo lee sin hacer cuentas.

La otra cara es el control. Cada bit de control es una ecuación: «la suma de estas posiciones ha de ser 0». Si una palabra cumple las tres ecuaciones, es del código. Si falla alguna, algo ha ido mal. Escribir las ecuaciones como filas de una matriz da la matriz de paridad.

Matriz generatriz

Una matriz generatriz de un código $[n,k]_q$ es una matriz $G$ de tamaño $k\times n$ cuyas filas forman una base del código. Codificar es multiplicar:

$$c = mG, \qquad m\in\mathbb{F}_q^k,\ c\in C.$$

Como las palabras son vectores fila, $mG$ es la combinación de las filas de $G$ con los coeficientes de $m$. Cada mensaje da una palabra distinta (las filas son independientes), y se recorren las $q^k$ palabras del código.

Un código tiene muchas matrices generatrices (una por base), pero la más cómoda es la forma sistemática

$$G=[\,I_k \mid P\,],$$

con $I_k$ la identidad $k\times k$ y $P$ una matriz $k\times(n-k)$. Entonces $c=mG=(m \mid mP)$: los primeros $k$ símbolos son el propio mensaje y los $n-k$ restantes son la redundancia.

Si G no está en forma sistemática

Se aplica el método de Gauss a las filas: intercambiarlas, multiplicar una por un escalar no nulo y sumar a una un múltiplo de otra. Así cambia la base, pero no el código: cada operación se puede deshacer.

Ejemplo: el código binario con filas $F_1=1101000$, $F_2=0110100$, $F_3=0011010$ y $F_4=0001101$ (volverá a salir en la lección 7). Vamos limpiando columnas, módulo 2:

• Columna 2: $F_1+F_2=1011100$ pasa a ser la fila 1.
• Columna 3: la fila 1 pasa a $1011100+F_3=1000110$ y la fila 2 a $F_2+F_3=0101110$.
• Columna 4: la fila 2 pasa a $0101110+F_4=0100011$ y la fila 3 a $F_3+F_4=0010111$.

$$G'=\begin{pmatrix}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{pmatrix}=[\,I_4\mid P'\,].$$

Si falta algún pivote, hay que reordenar las posiciones: sale un código equivalente (mismos parámetros), no el mismo.

Matriz de paridad

Una matriz de paridad (o matriz de control) de un código $[n,k]_q$ es una matriz $H$ de tamaño $(n-k)\times n$ y rango $n-k$ tal que

$$c\in C \iff Hc^T=0.$$

Aquí $c^T$ es $c$ escrita en columna. Cada fila de $H$ es una ecuación: $n-k$ ecuaciones independientes dejan $k$ grados de libertad.

Si $G=[\,I_k\mid P\,]$, una matriz de paridad se obtiene sin cálculo:

$$H=[\,-P^T \mid I_{n-k}\,].$$

La razón tiene dos partes. Primero, $GH^T = -P + P = 0$ al multiplicar por bloques: cada fila de $G$ cumple las ecuaciones de $H$, y con eso todas sus combinaciones, así que $C$ está dentro de las soluciones de $Hc^T=0$. Segundo, como $H$ contiene la identidad $I_{n-k}$, tiene rango $n-k$, y las soluciones forman un subespacio de dimensión $n-(n-k)=k$, la misma que $C$. Por eso coinciden. En binario, $-P^T=P^T$.

Para comprobar una palabra recibida $r$ se multiplica: si $Hr^T=0$, es del código; si no, hay un error (la lección 6 llama a $Hr^T$ síndrome).

De H a G

Si te dan $H$, las palabras del código son las soluciones del sistema $Hc^T=0$. Basta resolverlo: una base de soluciones es una matriz generatriz. Si $H=[\,A\mid I_{n-k}\,]$, la receta de antes al revés da $G=[\,I_k\mid -A^T\,]$.

Ejemplo: la matriz de paridad del Hamming «de manual», cuya columna $i$ es el número $i$ escrito en binario:

$$H=\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{pmatrix}.$$

Sus ecuaciones son $c_4=c_5+c_6+c_7$, $c_2=c_3+c_6+c_7$ y $c_1=c_3+c_5+c_7$ (en binario, restar es sumar). Las incógnitas libres son $c_3,c_5,c_6,c_7$. Dando a una de ellas el valor 1 y a las demás 0 salen cuatro soluciones:

$$G=\begin{pmatrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\0&1&0&1&0&1&0\\1&1&0&1&0&0&1\end{pmatrix}.$$

Son independientes (cada una es la única con un 1 en su incógnita libre), así que forman una base. El mensaje va en las posiciones 3, 5, 6 y 7, y el control en las 1, 2 y 4.

Código dual

Las filas de $H$ son $n-k$ vectores independientes de $\mathbb{F}_q^n$. Generan otro código, de dimensión $n-k$, que se llama el código dual $C^\perp$: el formado por todas las palabras $y$ con $y\cdot c=0$ para toda $c\in C$. Así, $H$ es matriz generatriz de $C^\perp$ y $G$ es matriz de paridad de $C^\perp$. Por ejemplo, el dual del código de repetición $[3,1]$ es el código de paridad $[3,2]$. Ojo: en un cuerpo finito un vector puede ser ortogonal a sí mismo, como $(1,1)\cdot(1,1)=1+1=0$ en binario; no pasa nada.

Leer la distancia mínima en H

Llama $h_1,\dots,h_n$ a las columnas de $H$. Entonces

$$Hc^T=c_1h_1+c_2h_2+\dots+c_nh_n.$$

Una palabra de peso $w$ es, por tanto, una combinación nula de $w$ columnas con coeficientes no nulos. En binario: $c$ es del código si y solo si suman cero las columnas de las posiciones donde $c$ tiene un 1. Es decir:

La distancia mínima $d$ de un código es el menor número de columnas de $H$ que son linealmente dependientes.

Consecuencias inmediatas, y la clave de los códigos de Hamming:

• Si ninguna columna de $H$ es nula, no hay palabras de peso 1: $d\ge 2$.
• Si además ninguna columna es múltiplo de otra (en binario: si todas son distintas), no hay palabras de peso 2: $d\ge 3$.

En $\mathbb{F}_3$ no basta con que sean distintas: las columnas $(1,0)$ y $(2,0)$ son distintas, pero su suma es cero.

Códigos de Hamming

Para $r\ge 2$ tomamos como columnas de $H$ todos los vectores no nulos de $\mathbb{F}_2^r$, cada uno una vez. Hay $2^r-1$, y esa es la longitud. El código resultante es el código de Hamming de parámetros

$$[\,2^r-1,\ 2^r-1-r,\ 3\,].$$

Tiene $d\ge3$ porque las columnas son binarias, distintas y no nulas, y $d=3$ porque hay tres columnas dependientes: $(1,0,\dots,0)$, $(0,1,0,\dots,0)$ y su suma, que también es columna de $H$. Para $r=2$, las columnas $(1,0)$, $(0,1)$ y $(1,1)$ dan el código de repetición $[3,1,3]$; para $r=3$, el $[7,4,3]$; para $r=4$, el $[15,11,3]$. Todos corrigen un error, y la tasa crece con $r$: $1/3$, $4/7$, $11/15$.

Ejemplo resuelto

Con el ejemplo hilo: el código de Hamming $[7,4,3]$ con

$$G=\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\end{pmatrix},\qquad H=\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}.$$

Paso 1: forma sistemática. $G=[I_4\mid P]$ con

$$P=\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\\1&1&1\end{pmatrix}.$$

Trasponemos $P$ y la ponemos a la izquierda de $I_3$: $H=[P^T\mid I_3]$, la matriz de arriba.

Paso 2: codificar. El mensaje $m=(1,0,1,1)$ da $c=mG$, la suma de las filas 1, 3 y 4 de $G$:

$$(1,0,0,0,1,1,0)+(0,0,1,0,0,1,1)+(0,0,0,1,1,1,1)=(1,0,1,1,0,1,0).$$

Los cuatro primeros símbolos son el mensaje, $1011$, y los tres últimos, la redundancia, $010$.

Paso 3: comprobar $GH^T=0$. Por bloques, $GH^T=P+P=0$ en binario. A mano, la fila 1 de $G$, $(1,0,0,0,1,1,0)$, coincide con la fila 1 de $H$ en las posiciones 1 y 5 ($1+1=0$), con la fila 2 en las posiciones 1 y 6 ($1+1=0$) y con la fila 3 en ninguna.

Paso 4: ¿es palabra del código? Para $r=(1,0,1,1,0,1,0)$, fila por fila:

• Fila 1: $1+0+0+1+0+0+0=0$.
• Fila 2: $1+0+1+1+0+1+0=0$.
• Fila 3: $0+0+1+1+0+0+0=0$.

Sale $(0,0,0)^T$: sí es palabra del código. Si cambiamos el bit de la posición 6 y recibimos $r'=(1,0,1,1,0,0,0)$, resulta $Hr'^T=(0,1,0)^T\neq 0$: no es palabra del código, ha habido un error.

Paso 5: distancia mínima en $H$. Las siete columnas de $H$ son $(1,1,0)$, $(1,0,1)$, $(0,1,1)$, $(1,1,1)$, $(1,0,0)$, $(0,1,0)$ y $(0,0,1)$: los siete vectores no nulos de $\mathbb{F}_2^3$, todos distintos. Luego $d\ge3$. Y las columnas 1, 2 y 3 suman $(0,0,0)$, así que $d=3$.

Paso 6: el dual. Las combinaciones de las filas de $H$ son $0000000$, las filas $1101100$, $1011010$, $0111001$ y sus sumas $0110110$, $1010101$, $1100011$ y $0001111$. Las siete no nulas pesan 4: el dual es un $[7,3,4]$.

Ejercicios

Ejercicio 1

Codifica $m=(0,1,1,0)$ con la $G$ del ejemplo y comprueba con $H$ que sale palabra del código. ¿Lo es $r=(0,1,1,0,0,1,1)$?

Ver la solución

$mG$ es la suma de las filas 2 y 3 de $G$: $(0,1,0,0,1,0,1)+(0,0,1,0,0,1,1)=(0,1,1,0,1,1,0)$.

Con $H$: fila 1, posiciones 1, 2, 4, 5: $0+1+0+1=0$; fila 2, posiciones 1, 3, 4, 6: $0+1+0+1=0$; fila 3, posiciones 2, 3, 4, 7: $1+1+0+0=0$. Es palabra del código.

Para $r$: fila 1: $0+1+0+0=1$; fila 2: $0+1+0+1=0$; fila 3: $1+1+0+1=1$. Resulta $(1,0,1)^T\neq 0$: $r$ no es palabra del código.

Ejercicio 2

Un código binario $[5,2]$ tiene matriz generatriz

$$G=\begin{pmatrix}1&0&1&1&0\\0&1&1&0&1\end{pmatrix}.$$

Halla una matriz de paridad $H$, comprueba $GH^T=0$ y averigua $d$ a partir de las columnas de $H$.

Ver la solución

Está en forma sistemática, $G=[I_2\mid P]$ con $P=\begin{pmatrix}1&1&0\\1&0&1\end{pmatrix}$. En binario, $H=[P^T\mid I_3]$:

$$H=\begin{pmatrix}1&1&1&0&0\\1&0&0&1&0\\0&1&0&0&1\end{pmatrix}.$$

Comprobación: por bloques, $GH^T=P+P=0$; a mano, cada fila de $G$ coincide con cada fila de $H$ en un número par de unos.

Las columnas de $H$ son $(1,1,0)$, $(1,0,1)$, $(1,0,0)$, $(0,1,0)$ y $(0,0,1)$: binarias, no nulas y distintas, así que $d\ge3$. Además, las columnas 1, 3 y 4 suman $(0,0,0)$, por lo que $d=3$. Coincide con el ejercicio 2 de la lección anterior.

Ejercicio 3

Sobre $\mathbb{F}_3$, el tetracódigo tiene matriz generatriz

$$G=\begin{pmatrix}1&0&1&1\\0&1&1&2\end{pmatrix}.$$

Halla $H=[-P^T\mid I_2]$. Codifica el mensaje $m=(2,1)$ y comprueba el resultado con $H$.

Ver la solución

Aquí $P=\begin{pmatrix}1&1\\1&2\end{pmatrix}$, que es simétrica: $P^T=P$. Cambiamos el signo módulo 3: $-1=2$ y $-2=1$. Entonces

$$H=\begin{pmatrix}2&2&1&0\\2&1&0&1\end{pmatrix}.$$

Codificamos: $c=mG=2\,(1,0,1,1)+1\,(0,1,1,2)=(2,1,3,4)=(2,1,0,1)$ módulo 3.

Comprobamos: fila 1 de $H$: $2\cdot2+2\cdot1+1\cdot0+0\cdot1=6=0$; fila 2: $2\cdot2+1\cdot1+0\cdot0+1\cdot1=6=0$. Resulta $Hc^T=(0,0)^T$. Los dos primeros símbolos de $c$ son el mensaje $(2,1)$.

Ejercicio 4

Halla el código dual $C^\perp$ del código $[5,2,3]$ del ejercicio 2: escribe sus palabras y da sus parámetros. Comprueba su distancia mínima mirando las columnas de su matriz de paridad.

Ver la solución

$C^\perp$ está generado por las filas de la $H$ del ejercicio 2: $11100$, $10010$ y $01001$. Sus $2^3=8$ palabras son $00000$, las tres filas y sus sumas:

$$11100+10010=01110,\quad 11100+01001=10101,\quad 10010+01001=11011,\quad 11100+10010+01001=00111.$$

Los pesos no nulos son $3, 2, 2, 3, 3, 4, 3$. El mínimo es 2: $C^\perp$ es un $[5,3,2]$.

Comprobación: una matriz de paridad de $C^\perp$ es la $G$ del ejercicio 2. Sus columnas son $(1,0)$, $(0,1)$, $(1,1)$, $(1,0)$ y $(0,1)$. La 1 y la 4 son iguales, así que suman cero y $d=2$: es la palabra $10010$.

En resumen

• La matriz generatriz $G$ ($k\times n$) codifica: $c=mG$. Con el método de Gauss se lleva a la forma sistemática $G=[I_k\mid P]$, en la que el mensaje aparece en las primeras $k$ posiciones.
• La matriz de paridad $H$ ($(n-k)\times n$) comprueba: $c\in C\iff Hc^T=0$. Si $G=[I_k\mid P]$, entonces $H=[-P^T\mid I_{n-k}]$. Al revés, $G$ sale de resolver el sistema $Hc^T=0$.
• El código dual $C^\perp$ tiene a $H$ como matriz generatriz y a $G$ como matriz de paridad.
• La distancia mínima es el menor número de columnas de $H$ linealmente dependientes. Columnas no nulas y sin ninguna múltiplo de otra dan $d\ge3$; en binario, basta con que sean no nulas y distintas.
• El código de Hamming usa como columnas todos los vectores no nulos de $\mathbb{F}_2^r$ y tiene parámetros $[2^r-1,\,2^r-1-r,\,3]$.

Siguiente lección: Errores y borrones