El síndrome

El receptor tiene en la mano una sola cosa: lo que llegó. No sabe qué se transmitió —eso es lo que quiere averiguar— ni dónde se equivocó el canal. El síndrome es una cuenta sobre lo recibido que da un resultado que no depende de lo transmitido: sólo de lo que hizo el canal. Toda la decodificación algebraica, de acá hasta BCH, se apoya en eso.

01 · La definición

Se transmite una palabra de código $v$ de un código $(n, k)$ y llega $r$ . Lo que el canal hizo se escribe como un vector más, el patrón de error $e$ , con un 1 en cada posición que el canal invirtió y un 0 en las demás:

r = v + e

La suma es bit a bit, módulo 2: sumar un 1 es dar vuelta el bit. Con $H$ la matriz de paridad del código, de $(n - k) \times n$ , el síndrome de lo recibido es el vector de $n - k$ bits

s = r H^{T} = (s_{0}, s_{1}, \dots, s_{n - k - 1})

Cada bit es una ecuación de paridad: $s_{j}$ es la suma de los bits de $r$ en las posiciones donde la fila $j$ de $H$ tiene un 1, y vale 1 cuando esa ecuación no cierra. En el Hamming (7,4) del curso,

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})

y las tres ecuaciones son

\begin{array}{rcl} s_{0} & = & r_{0} + r_{2} + r_{3} + r_{4} \\ s_{1} & = & r_{0} + r_{1} + r_{2} + r_{5} \\ s_{2} & = & r_{1} + r_{2} + r_{3} + r_{6} \end{array}

Las cuatro primeras posiciones son el mensaje y las tres últimas la paridad, porque $G = [I P]$ y $H = [P^{T} I]$ . Cada ecuación mezcla tres bits de mensaje con un solo bit de paridad: $s_{0}$ repite la cuenta con la que el codificador armó $v_{4}$ y se fija si lo que llegó en la posición 4 coincide.

02 · No depende de lo transmitido

Paso 1: reemplazar lo recibido. El receptor calcula sobre $r$ , que es $v + e$ :

s = r H^{T} = (v + e) H^{T}

Paso 2: distribuir. El producto por una matriz es lineal, también sobre $GF (2)$ :

s = v H^{T} + e H^{T}

Paso 3: lo transmitido se anula. $v$ es palabra de código, y una palabra de código es justo un vector con $v H^{T} = 0$ : es el criterio de pertenencia. Queda

s = e H^{T}

El receptor no conoce $v$ ni $e$ , pero calcula sobre $r$ una cantidad que es función de $e$ solo. Los dieciséis mensajes del (7,4), con el mismo patrón de error encima, dan el mismo síndrome. Es lo que vuelve viable toda la decodificación: cualquier pregunta sobre el error se puede contestar mirando $s$ , sin pasar por las $2^{k}$ palabras.

De ahí sale el criterio de detección, que es asimétrico. Si $s \neq 0$ , hubo error con certeza: ninguna palabra de código da un síndrome no nulo. Si $s = 0$ , lo recibido es palabra de código, que no es lo mismo que decir que no hubo error.

03 · La suma de columnas

Leída por columnas, la cuenta se vuelve más útil que la matricial. Con $h_{i}$ la columna $i$ de $H$ y $E$ el conjunto de posiciones con error,

s^{T} = \sum_{i = 0}^{n - 1} e_{i} h_{i} = \sum_{i \in E} h_{i}

Las posiciones sin error multiplican su columna por 0 y desaparecen. El síndrome es la suma de las columnas de $H$ donde hubo error, y nada más. Las del (7,4), escritas de arriba abajo como $s_{0} s_{1} s_{2}$ , son

\begin{array}{l} h_{0} = 110, & h_{1} = 011, & h_{2} = 111, & h_{3} = 101, \\ h_{4} = 100, & h_{5} = 010, & h_{6} = 001 \end{array}

los siete vectores no nulos de tres bits, cada uno una vez. Con un solo error en la posición $i$ , el síndrome es $h_{i}$ ; como las siete son distintas y ninguna es nula, cada error simple da un síndrome propio y queda localizado.

El ejemplo del apunte: el mensaje $u = 1001$ se codifica como $v = 1001 011$ , el canal invierte la posición 2 y llega $r = 1011 011$ . Por las ecuaciones, $s_{0} = 1 + 1 + 1 + 0 = 1$ , $s_{1} = 1 + 0 + 1 + 1 = 1$ y $s_{2} = 0 + 1 + 1 + 1 = 1$ : $s = 111 = h_{2}$ . Por columnas la cuenta es más corta, porque $e = 0010 000$ elige una sola. En ningún momento se comparó $r$ con las dieciséis palabras.

El apunte y la filmina dicen que, para este código, el síndrome es la posición del error escrita en binario. Con la $H$ sistemática de arriba no lo es: $h_{4}$ es $100$ y $h_{5}$ es $010$ , y leídas como números en cualquiera de los dos sentidos las siete columnas no dan 0 a 6 ni 1 a 7. Lo que sí vale es que la correspondencia entre síndromes no nulos y posiciones es uno a uno, y por eso el localizador sigue siendo un decodificador de 3 a 7 líneas: una tabla fija, no la lectura de un número. La $H$ cuyas columnas son las posiciones en binario existe, y es otro ordenamiento de las mismas siete columnas: da un código equivalente, con las posiciones permutadas, no el mismo.

04 · El calculador del (7,4) en SystemVerilog

El calculador de síndrome del RTL del curso es esas tres ecuaciones y una compuerta más. El bit $i$ de cada bus es la posición $i$ , así que cada línea se lee contra una fila de $H$ sin traducir nada:

always_comb begin
    syndrome[0] = message_d[0] ^ message_d[2] ^ message_d[3] ^ message_d[4];
    syndrome[1] = message_d[0] ^ message_d[1] ^ message_d[2] ^ message_d[5];
    syndrome[2] = message_d[1] ^ message_d[2] ^ message_d[3] ^ message_d[6];
end

assign o_syndrome      = syndrome;
assign o_zero_syndrome = (|syndrome == 1'b0);

Cada fila de $H$ tiene cuatro unos, así que cada bit del síndrome es un XOR de cuatro entradas: tres en total, sin memoria. message_d es la palabra recibida $r$ retenida un ciclo de reloj por un registro de entrada; el cálculo en sí es combinacional. Y o_zero_syndrome es el detector: el OR de los tres bits, negado. Vale 1 exactamente cuando $s = 0$ , con la misma asimetría de la sección anterior.

Lo que el circuito no tiene es $e$ . Calcula sobre $r$ , que es lo único que le llega, y le sirve porque $r H^{T} = e H^{T}$ . Simulado el (7,4) entero sobre los dieciséis mensajes por los 128 patrones, la bandera de corrección del decodificador —que es o_zero_syndrome negado— se levanta en los 2048 casos exactamente cuando $e H^{T} \neq 0$ . Cómo se usa ese síndrome para corregir es el standard array y la decodificación por síndrome.

05 · Dieciséis patrones por síndrome

El síndrome tiene $n - k$ bits y el patrón de error $n$ . Hay $2^{n - k}$ síndromes para $2^{n}$ patrones, y a cada síndrome le tocan

\frac{2^{n}}{2^{n - k}} = 2^{k}

patrones distintos. El sistema $e H^{T} = s$ tiene $n$ incógnitas y $n - k$ ecuaciones: está indeterminado, y sus $2^{k}$ soluciones son un patrón cualquiera más cada una de las palabras de código, porque sumar una palabra no mueve el síndrome. En el (7,4) son 16 por síndrome. Enumerando los 128 patrones y agrupándolos por síndrome y por peso:

síndrome	peso 0	1	2	3	4	5	6	7
000	1	0	0	7	7	0	0	1
los otros 7	0	1	3	4	4	3	1	0

Los siete síndromes no nulos tienen el mismo reparto: uno de peso 1, tres de peso 2, y así hasta uno de peso 6. Para $s = 111$ los de peso 2 son $0001 010$ , $0100 100$ y $1000 001$ : $h_{3} + h_{5}$ , $h_{1} + h_{4}$ y $h_{0} + h_{6}$ dan todas $h_{2}$ .

Ninguna cuenta sobre $r$ elige entre los dieciséis: todos cumplen las ecuaciones por igual. La elección es estadística. Sobre un canal que invierte cada bit con probabilidad $p$ , un patrón de peso $w$ tiene probabilidad $p^{w} (1 - p)^{n - w}$ , y cada bit de más multiplica por $p / (1 - p)$ : con $p = 10^{- 2}$ , el de peso 1 es 99 veces más probable que cada uno de peso 2. Sumando los dieciséis, dado un síndrome no nulo el patrón de peso 1 es el que ocurrió con probabilidad 0,970, y con $p = 10^{- 1}$ baja a 0,720. El de menor peso de cada grupo es el líder de coset, y es la apuesta del decodificador.

Con $e = 0$ el síndrome es $000$ y la lista de abajo son las dieciséis palabras de código. Prendé un bit de $e$ : se marca una columna de $H$ y el síndrome pasa a ser esa columna. Ahora apretá «Siguiente mensaje» varias veces: cambian $v$ y $r$ , cambian los términos de las tres ecuaciones, y el síndrome no se mueve; el contador lleva cuántos mensajes probaste y cuántos síndromes distintos dieron. Con dos bits de error, la suma de dos columnas cae siempre en una tercera, y el síndrome queda igual al de un error solo en otra posición. Con tres bits bien elegidos — $1000 110$ , por ejemplo— la suma da cero.

06 · Lo que el síndrome no puede ver

Las dos cosas que el síndrome no resuelve salen de la misma cuenta.

Un error que es palabra de código pasa sin dejar rastro. Si $e$ es una palabra no nula, $e H^{T} = 0$ y lo recibido es otra palabra válida: el receptor la acepta. En el (7,4) son las $2^{k} - 1 = 15$ palabras no nulas, la fila del $000$ en la tabla de arriba: siete de peso 3, siete de peso 4 y una de peso 7. Ningún patrón de peso 1 o 2 está entre ellas, porque la distancia mínima es 3; cuánto pesa lo que se escapa está en un síndrome cero no prueba nada.

Dentro de un grupo, el síndrome no distingue. En el (7,4) dos columnas suman siempre una tercera, porque las siete son todos los vectores no nulos de tres bits y la suma de dos distintas no es nula ni igual a ninguna de las dos. Los 21 patrones dobles dan, los 21, el síndrome de un error simple en otra posición: $e = 1000 010$ da $h_{0} + h_{5} = 110 + 010 = 100 = h_{4}$ . El decodificador, que apuesta al patrón más liviano, corrige la posición 4 y entrega una palabra con tres bits mal: con dos errores, el decodificador empeora. No es un defecto del circuito: es el límite de la sección anterior, ocho síndromes para 128 patrones.

Para tener a mano

$r = v + e$ y $s = r H^{T}$ , de $n - k$ bits. Cada bit es una ecuación de paridad evaluada sobre lo recibido.
$s = e H^{T}$ , porque $v H^{T} = 0$ : el síndrome depende sólo del error, no de lo que se mandó.
$s \neq 0$ prueba que hubo error; $s = 0$ sólo dice que llegó una palabra de código. Pasan sin ser vistos los $2^{k} - 1$ errores que son palabras.
$s^{T} = \sum_{i \in E} h_{i}$ : la suma de las columnas de $H$ donde hubo error. Un error simple en $i$ da $h_{i}$ .
En el (7,4): $s_{0} = r_{0} + r_{2} + r_{3} + r_{4}$ , $s_{1} = r_{0} + r_{1} + r_{2} + r_{5}$ , $s_{2} = r_{1} + r_{2} + r_{3} + r_{6}$ : tres XOR de cuatro entradas. Las columnas son los siete no nulos de tres bits, pero no en el orden binario de las posiciones.
Cada síndrome corresponde a $2^{k}$ patrones, uno cualquiera más las palabras de código. En el (7,4), 16 por síndrome; en los no nulos, uno de peso 1 y tres de peso 2. Elegir entre ellos es estadística, no álgebra.