El código lineal y la matriz G

Por un canal de $n$ bits pueden pasar $2^{n}$ palabras. Un código declara válidas sólo $2^{k}$ , que alcanzan justo para los $2^{k}$ mensajes de $k$ bits; las otras $2^{n} - 2^{k}$ quedan prohibidas, y si llega una, hubo error. Toda la teoría de los códigos de bloque es elegir bien ese subconjunto. Un código lineal pide una sola cosa más: que el subconjunto sea un subespacio. Con eso alcanzan $k$ vectores para describirlo entero, y codificar pasa a ser un producto de un vector por una matriz.

01 · La definición

Un código de bloque lineal $(n, k)$ sobre $GF (2)$ es un subespacio de dimensión $k$ de $V_{n}$ , el espacio de las $n$ -tuplas binarias. Sus $2^{k}$ elementos son las palabras de código. $n$ es la longitud de bloque, $k$ la cantidad de bits de información, y los $n - k$ que sobran son redundancia, o paridad. La tasa es la fracción del flujo que es información:

R = \frac{k}{n}

El ejemplo de toda la unidad es el Hamming $(7, 4)$ : 16 palabras válidas entre 128, una de cada ocho, y $R = 4 / 7 \approx 0,571$ . De cada siete bits que viajan, cuatro son del usuario. Es el mismo Hamming que cruza a no codificar en 5,85 dB.

De ser un subespacio salen dos propiedades que se usan todo el tiempo:

La palabra nula está siempre, sea cual sea el código.
La suma de dos palabras es otra palabra. La suma es bit a bit, módulo 2: un XOR.

Sobre $GF (2)$ esas dos son la definición entera, no una consecuencia. Los únicos escalares son 0 y 1, así que multiplicar por un escalar no agrega ninguna exigencia; y la primera sale de la segunda, porque $v + v = 0$ para cualquier $v$ . Un conjunto no vacío de vectores binarios es un código lineal si y sólo si es cerrado para la suma. El conjunto {0000, 1100, 1010, 0111} tiene cuatro palabras, $2^{2}$ , pero no es lineal: 1100 + 1010 = 0110 no está.

La segunda propiedad tiene un costado que rinde mucho más adelante. Sumarle una palabra fija $v$ a todas las palabras del código las devuelve a todas, sólo que en otro orden: el resultado está en el código por la suma cerrada, y dos palabras distintas no pueden ir a parar a la misma. El código se ve igual desde cualquiera de sus palabras, y por eso para analizar los errores alcanza con suponer que se transmitió la nula: es lo que hace que la distancia mínima se lea como un peso.

02 · La matriz generadora

Un subespacio de dimensión $k$ tiene una base de $k$ vectores linealmente independientes, $g_{0}, g_{1}, \dots, g_{k - 1}$ . Puestos como filas forman la matriz generadora $G$ , de $k \times n$ . El mensaje $u = (u_{0}, \dots, u_{k - 1})$ se codifica como

v = u \cdot G = u_{0} g_{0} + u_{1} g_{1} + \dots + u_{k - 1} g_{k - 1}

Leído bit a bit: cada $u_{i} = 1$ elige la fila $g_{i}$ , y la palabra es el XOR de las filas elegidas. Con eso la suma cerrada se ve en una línea: si $v = u G$ y $v^{'} = u^{'} G$ , entonces $v + v^{'} = (u + u^{'}) G$ : la suma de dos palabras es la palabra de la suma de los mensajes.

Lo que cuesta. El codificador no guarda las $2^{k}$ palabras: guarda las $k \cdot n$ entradas de $G$ . Para el $(255, 239)$ del trabajo final es la diferencia entre una tabla de $2^{239}$ palabras, que no entra en ningún universo, y 60.945 bits. Ésa es la razón de pedir linealidad: no es una comodidad matemática, es lo que vuelve al código implementable.

Las filas tienen que ser independientes. Si una fila es suma de otras, dos mensajes distintos caen en la misma palabra. Con las filas del $(7, 4)$ pero la cuarta cambiada por $g_{0} + g_{1}$ , el mensaje 1101 suma $g_{0} + g_{1} + (g_{0} + g_{1}) = 0$ , la misma palabra que 0000. Los 16 mensajes dan sólo 8 palabras distintas, cada una dos veces, y el receptor no tiene forma de saber cuál de los dos se mandó.

La base no es única. Cualquier otra base del mismo subespacio da otra $G$ con el mismo código: cambia qué palabra le toca a cada mensaje, no el conjunto de palabras. Cuántas hay se cuenta eligiendo las filas en orden, cada una fuera del subespacio que generan las anteriores:

(2^{4} - 1) (2^{4} - 2) (2^{4} - 2^{2}) (2^{4} - 2^{3}) = 15 \cdot 14 \cdot 12 \cdot 8 = 20.160

El $(7, 4)$ tiene 20.160 matrices generadoras, y recorriendo todas las cuaternas de palabras no nulas e independientes salen exactamente ésas. Todas codifican el mismo conjunto de 16 palabras, y las capacidades de detectar y corregir dependen sólo del conjunto. Lo que decide cuál usar es la comodidad.

03 · La forma sistemática

De todas esas matrices, hay una que se prefiere. $G$ está en forma sistemática cuando se escribe

G = [I_{k} P]

con $I_{k}$ la identidad de $k \times k$ y $P$ de $k \times (n - k)$ . Desarrollando $u \cdot G$ con esa forma, el mensaje sale intacto en las primeras $k$ posiciones y detrás vienen $n - k$ bits de paridad:

v = (\underset{mensaje}{\underset{⏟}{u_{0}, \dots, u_{k - 1}}}, \underset{paridad}{\underset{⏟}{p_{0}, \dots, p_{n - k - 1}}}), p_{j} = \sum_{i = 0}^{k - 1} u_{i} p_{i j}

Cada bit de paridad es el XOR de los bits de mensaje que marca la columna $j$ de $P$ : una ecuación de paridad. Todo el diseño del código vive en $P$ . La ventaja es del receptor: si no hubo errores, lee el mensaje directamente, sin deshacer ninguna transformación. Y la matriz de paridad sale sin hacer cuentas, $H = [P^{T} I_{n - k}]$ .

Es una sola. De las 20.160 $G$ del $(7, 4)$ , la sistemática es exactamente una, y no por casualidad: si las primeras cuatro posiciones de $u G$ tienen que repetir $u$ , la fila $g_{i}$ tiene que ser la única palabra del código que empieza con un 1 en la posición $i$ y ceros en las otras tres. No queda nada para elegir. La convención de poner el mensaje adelante sí es una elección, y en toda la unidad se usa ésta.

La $G$ del $(7, 4)$ , con las posiciones de 0 a 6 de izquierda a derecha:

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}] = [I_{4} P]

Leyendo las tres columnas de $P$ de arriba abajo salen las tres ecuaciones de paridad:

\begin{matrix} p_{0} = u_{0} + u_{2} + u_{3} \\ p_{1} = u_{0} + u_{1} + u_{2} \\ p_{2} = u_{1} + u_{2} + u_{3} \end{matrix}

En hardware. El codificador del RTL del curso es exactamente eso. Los cuatro bits de mensaje pasan como cables a las posiciones 0 a 3 de la salida, y la paridad son tres asignaciones, una por columna de $P$ . El bit $i$ de cada bus es la posición $i$ : i_info[i] es $u_{i}$ y parity[j] es $p_{j}$ , que va a la posición $4 + j$ .

assign parity[0] = i_info[0] ^ i_info[2] ^ i_info[3];
assign parity[1] = i_info[0] ^ i_info[1] ^ i_info[2];
assign parity[2] = i_info[1] ^ i_info[2] ^ i_info[3];

Cada columna de $P$ tiene tres unos, así que cada bit de paridad es un XOR de tres entradas, y el codificador entero es combinacional: cuatro cables y tres compuertas, sin un solo registro. Simulado sobre los 16 mensajes, entrega las mismas 16 palabras que $u \cdot G$ .

Con u = 0000 no hay ninguna fila elegida y la palabra es la nula. Prendé $u_{0}$ y $u_{3}$ : se suman $g_{0}$ y $g_{3}$ , y sale 1001 011, con el mensaje adelante y la paridad atrás. Guardala, armá 0110 y mirá la suma: 1111 111, que es la palabra de 1111. Probá con las que quieras: no hay suma de dos palabras que se salga del código. Y prendé la otra base, la que cambia $g_{0}$ por $g_{0} + g_{1}$ : el mismo 1001 sale 1101 000, y las primeras cuatro posiciones ya no son el mensaje. De los 16 mensajes, 8 cambian de palabra, pero las palabras que aparecen en la grilla son las mismas 16. Cambió la correspondencia, no el código.

04 · Las 16 palabras del (7,4)

Los cuatro primeros bits son el mensaje; los tres últimos, la paridad. La columna $w$ es el peso, la cantidad de unos de la palabra:

u	v	w	u	v	w
0000	0000 000	0	0110	0110 100	3
1000	1000 110	3	0101	0101 110	4
0100	0100 011	3	0011	0011 010	3
0010	0010 111	4	1110	1110 010	4
0001	0001 101	3	1101	1101 000	3
1100	1100 101	4	1011	1011 100	4
1010	1010 001	3	0111	0111 001	4
1001	1001 011	4	1111	1111 111	7

Una es de peso 0, siete de peso 3, siete de peso 4 y una de peso 7. La más liviana que no es nula tiene tres unos, y eso, por la suma cerrada, es lo mismo que decir que dos palabras distintas difieren siempre en tres posiciones o más: es la distancia mínima del código, y lo que le permite corregir un error. Las cuatro filas de $G$ están en la tabla —son las palabras de 1000, 0100, 0010 y 0001— y las otras doce son sumas de ellas.

05 · Cuándo no hay forma sistemática

El apunte dice que toda $G$ de rango $k$ se lleva a $[I_{k} P]$ con operaciones de fila y, si hace falta, permutando columnas. Ese «si hace falta» tiene un precio. Las operaciones de fila cambian la base y dejan el código igual; permutar columnas cambia el código.

El caso más chico: el $(4, 2)$ {0000, 1100, 0011, 1111}. En todas sus palabras las posiciones 0 y 1 son iguales, así que ninguna empieza con 10 y el mensaje no puede ir intacto ahí. Escalonando sus filas, los pivotes caen en las columnas 0 y 2, no en 0 y 1. Intercambiando las posiciones 1 y 2 sale {0000, 1010, 0101, 1111}, que sí tiene $G = [I_{2} P]$ . Es un código equivalente: los mismos pesos, las mismas distancias, la misma capacidad de corregir. Pero son otras palabras, y un decodificador escrito para uno no sirve para el otro sin deshacer la permutación.

El $(7, 4)$ también tiene posiciones donde el mensaje no entra. De las 35 formas de elegir cuatro posiciones, 28 sirven para llevar el mensaje intacto y 7 no. Las siete que fallan son las que dejan afuera, exactamente, las tres posiciones de una palabra de peso 3. Esa palabra vale cero en las cuatro elegidas, igual que la nula, y si dos palabras distintas coinciden ahí, esas cuatro posiciones no pueden distinguir 16 mensajes. Por ejemplo, 0100 011 tiene sus unos en 1, 5 y 6: las posiciones 0, 2, 3 y 4 no alcanzan.

Para tener a mano

Un código lineal $(n, k)$ es un subespacio de dimensión $k$ de $V_{n}$ : $2^{k}$ palabras entre $2^{n}$ , con tasa $R = k / n$ . Sobre $GF (2)$ , lineal es lo mismo que cerrado para la suma; la nula viene incluida.
$v = u \cdot G$ : cada $u_{i} = 1$ elige la fila $g_{i}$ y la palabra es el XOR de las elegidas. Las filas tienen que ser independientes, o dos mensajes chocan.
El codificador guarda $k \cdot n$ bits, no $2^{k}$ palabras: es lo que hace implementable al código.
Otra base da otra $G$ y el mismo código. El $(7, 4)$ tiene 20.160, y una sola es sistemática.
$G = [I_{k} P]$ : el mensaje va intacto adelante y cada bit de paridad es un XOR de bits de mensaje, uno por columna de $P$ . Entonces $H = [P^{T} I_{n - k}]$ .
En el $(7, 4)$ : $p_{0} = u_{0} + u_{2} + u_{3}$ , $p_{1} = u_{0} + u_{1} + u_{2}$ , $p_{2} = u_{1} + u_{2} + u_{3}$ . En hardware, cuatro cables y tres XOR de tres entradas.
Permutar columnas para llegar a la forma sistemática da un código equivalente, no el mismo.