Decodificación por síndrome: corregir sin comparar con todo

En la lección anterior vimos cuántos errores puede corregir un código. Ahora toca hacerlo de verdad. La idea de la lección 1 era buscar la palabra código más cercana a la recibida, pero comparar con las $2^k$ palabras es lento: un código con $k=100$ tiene $2^{100}$ palabras, imposible de recorrer. Con la matriz de paridad se puede hacer mucho mejor: basta una multiplicación y una búsqueda en una tabla pequeña.

La idea

Recibes una palabra $r$. Sabes que es la palabra enviada $c$ más un error $e$, es decir, $r = c + e$. No ves $e$, pero puedes hacerle una pregunta indirecta: ¿qué te dice la matriz $H$ sobre $r$?

Como $Hc^T = 0$ para toda palabra código, la matriz «no ve» a $c$. Solo ve el error. Así que el resultado de multiplicar $H$ por $r$ es una huella del error, que no depende de qué palabra se envió. Esa huella se llama síndrome, como en medicina: un conjunto de síntomas que apunta a la enfermedad.

El plan es entonces: calcular la huella, buscar en una tabla qué error deja esa huella, y quitarlo.

Definición

El síndrome de una palabra recibida $r$ es

$$s = Hr^T,$$

un vector de $n-k$ símbolos. Al multiplicar sale en columna; en el texto lo escribiremos a veces como fila seguida de ${}^T$, por ejemplo $(0,1,1)^T$. Si $r=c+e$ con $c\in C$:

$$s = H(c+e)^T = Hc^T + He^T = He^T.$$

El síndrome solo depende del error. Además $s=0$ si y solo si $r$ es palabra código.

Repaso Clase lateral

Si $C$ es un subespacio y $v$ un vector, el conjunto $v + C = \{v + c : c \in C\}$ es la clase lateral de $v$. Es el subespacio $C$ desplazado. Dos clases son iguales o no se cortan nunca, así que el espacio entero queda repartido en clases, todas con el mismo número de elementos que $C$.

Dos palabras $u$ y $v$ tienen el mismo síndrome si y solo si su diferencia es una palabra código. Por eso el espacio $\mathbb{F}_q^n$ se reparte en $q^{n-k}$ grupos, uno por síndrome, cada uno con $q^k$ palabras. Cada grupo es una clase lateral de $C$: todas las palabras de la forma $e + C$. La clase del síndrome 0 es el propio código.

La clase de $r$, es decir $r+C$, contiene todos los errores que pueden haber producido $r$: si se envió $c$, el error fue $r-c$. Elegir el de menor peso es elegir la palabra código más cercana. Y si el canal estropea cada símbolo por separado y con poca probabilidad (en binario, menos de 1/2), es también el error más probable. Ese error de menor peso es el líder de la clase. La tabla de síndromes lista, para cada síndrome, su líder. Es la versión reducida de la llamada tabla estándar, que contiene las clases completas.

Decodificar:

1. Calcula $s = Hr^T$.
2. Busca en la tabla el líder $e$ de ese síndrome.
3. Responde $\hat c = r - e$ (en binario, $r + e$). El gorro de $\hat c$ indica que es nuestra estimación de $c$.

En el Hamming, el síndrome es la posición

Con un solo error en la posición $i$, el vector $e$ tiene un único 1 y

$$He^T = \text{(columna } i \text{ de } H).$$

Para el Hamming $[7,4,3]$ las columnas de $H$ son los siete vectores no nulos de $\mathbb{F}_2^3$, todos distintos:

posición del error	1	2	3	4	5	6	7
síndrome	(1,1,0)	(1,0,1)	(0,1,1)	(1,1,1)	(1,0,0)	(0,1,0)	(0,0,1)

Esa es toda la tabla de síndromes: 8 filas, la del 0 («sin error») y las 7 de arriba. Como el código es perfecto (lección 5), no queda ningún síndrome sin líder de peso 1. No hay que buscar nada: se mira el síndrome, se localiza la columna igual y se cambia ese bit.

Ejemplo resuelto

Enviamos el mensaje $m=(1,0,1,1)$, que se codifica como

$$c = mG = (1,0,1,1,0,1,0).$$

Por el canal se cambia el bit de la posición 3 y recibimos $r=(1,0,0,1,0,1,0)$.

Paso 1: el síndrome. Con $H$ de la lección 4, cada fila suma las posiciones donde tiene un 1, módulo 2:

• Fila 1: $r_1+r_2+r_4+r_5 = 1+0+1+0 = 0$.
• Fila 2: $r_1+r_3+r_4+r_6 = 1+0+1+1 = 1$.
• Fila 3: $r_2+r_3+r_4+r_7 = 0+0+1+0 = 1$.

Así que $Hr^T = (0,1,1)^T$, distinto de cero: hay un error.

Paso 2: la tabla. El síndrome $(0,1,1)$ es la columna 3 de $H$. El error está en la posición 3.

Paso 3: corregir. Cambiamos el bit 3:

$$\hat c = (1,0,0,1,0,1,0) + (0,0,1,0,0,0,0) = (1,0,1,1,0,1,0).$$

Es la palabra enviada. Como el código es sistemático, el mensaje son las 4 primeras posiciones: $(1,0,1,1)$.

Cuando se pasa de errores. El código solo corrige 1 error. ¿Qué ocurre con 2? Cambiamos las posiciones 1 y 2 de $c$ y recibimos

$$r' = (0,1,1,1,0,1,0).$$

Su síndrome es $He^T = (1,1,0)^T + (1,0,1)^T = (0,1,1)^T$, la columna 3. El decodificador, que no sabe que hubo dos errores, concluye «error en la posición 3» y devuelve

$$(0,1,0,1,0,1,0).$$

Es una palabra código válida, pero no es la enviada: difiere de $c$ en 3 posiciones. No salta ninguna alarma, porque el resultado parece perfecto. Esto es lo que cuesta un código perfecto: no sobran síndromes para avisar de que algo va mal. Si necesitas detectar errores dobles, hay que aumentar $d$. Por ejemplo, se añade un octavo bit que hace par el número de unos de cada palabra: las de peso 3 pasan a peso 4 y sale un $[8,4,4]$, que corrige 1 error y además detecta 2.

Y si el código no es de Hamming

En general el síndrome no es una columna, sino una suma de columnas, y hay que construir la tabla. Se recorren los errores por peso creciente (0, 1, 2…) y, para cada síndrome nuevo, se apunta el primer error que lo produce. Puede haber empates: dos errores del mismo peso con el mismo síndrome. Entonces el código no puede decidir cuál es el correcto, y se elige uno cualquiera (o se declara fallo). Si $q>2$, un error de valor $a$ en la posición $i$ da como síndrome $a$ veces la columna $i$: la tabla de peso 1 tiene esos múltiplos.

El coste. La tabla tiene $q^{n-k}$ entradas, una por síndrome. Para el Hamming son $2^3 = 8$, nada. Pero para un código con $n-k=32$ hacen falta más de cuatro mil millones de filas, y esto ya no cabe en la práctica. Por eso se usan familias con estructura extra (BCH, Reed-Solomon…) cuyos decodificadores hallan el error sin tabla. En la lección 11 verás uno para Reed-Solomon.

Ejercicios

Ejercicio 1

En el Hamming $[7,4,3]$ recibes $r=(0,1,1,0,1,0,0)$. Calcula el síndrome, localiza el error y da la palabra enviada.

Ver la solución

Cada fila de $H$ con $r=(0,1,1,0,1,0,0)$, módulo 2:

• Fila 1: $r_1+r_2+r_4+r_5 = 0+1+0+1 = 0$.
• Fila 2: $r_1+r_3+r_4+r_6 = 0+1+0+0 = 1$.
• Fila 3: $r_2+r_3+r_4+r_7 = 1+1+0+0 = 0$.

Síndrome $(0,1,0)^T$, que es la columna 6. El error está en la posición 6. Corregimos y queda $(0,1,1,0,1,1,0)$, que es la palabra enviada si hubo como mucho un error. (Se puede comprobar que su síndrome es $(0,0,0)^T$.)

Ejercicio 2

Se envía $c=(0,1,1,0,1,1,0)$ por el canal del Hamming $[7,4,3]$ y se cambian las posiciones 5 y 7. ¿Qué recibe el decodificador, qué síndrome obtiene y qué devuelve? ¿Acierta?

Ver la solución

Recibe $r=(0,1,1,0,0,1,1)$. Su síndrome es la suma de las columnas 5 y 7 de $H$:

$$(1,0,0)^T + (0,0,1)^T = (1,0,1)^T,$$

que es la columna 2. El decodificador cambia la posición 2 y devuelve $(0,0,1,0,0,1,1)$. Es una palabra código, pero no la enviada (difiere en las posiciones 2, 5 y 7). No acierta, y sin avisar: dos errores superan lo que corrige el código.

Ejercicio 3

Considera el código binario con matriz de paridad

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

(es un código $[5,2,3]$ con palabras $00000$, $01011$, $10110$ y $11101$). Construye su tabla de síndromes y decodifica $r=(1,0,1,1,1)$. Después intenta decodificar $r=(0,1,1,1,0)$.

Ver la solución

Hay $2^{5-2}=8$ síndromes. Los cinco errores de peso 1 dan las columnas de $H$:

síndrome	líder
(0,0,0)	00000
(1,1,0)	10000
(0,1,1)	01000
(1,0,0)	00100
(0,1,0)	00010
(0,0,1)	00001

Quedan dos síndromes, $(1,0,1)$ y $(1,1,1)$, que solo se obtienen con errores de peso 2. Cada uno tiene dos líderes empatados: $(1,0,1)$ con $11000$ o $00101$; $(1,1,1)$ con $01100$ o $10001$.

Para $r=(1,0,1,1,1)$: el síndrome es $(0,0,1)^T$, líder $00001$, y se devuelve $(1,0,1,1,0)$, que es palabra código.

Para $r=(0,1,1,1,0)$: el síndrome es $(1,0,1)^T$. Con el líder $11000$ se obtiene $10110$; con $00101$, se obtiene $01011$. Ambas son palabras código a distancia 2 de $r$. El decodificador no puede decidir entre las dos, porque el código solo garantiza corregir 1 error.

En resumen

• El síndrome $s=Hr^T=He^T$ solo depende del error, no de la palabra enviada; $s=0$ significa palabra código.
• Las palabras con el mismo síndrome forman una clase lateral; su elemento de menor peso es el líder.
• Decodificar es calcular el síndrome, buscar el líder en la tabla y restarlo.
• En el Hamming, el síndrome de un error simple es la columna de la posición dañada: no hace falta tabla.
• Con más errores de los permitidos, el decodificador se equivoca (a veces sin avisar). La tabla crece como $q^{n-k}$.

Siguiente lección: Códigos cíclicos