El standard array y la decodificación por síndrome

El síndrome dice algo exacto y algo insuficiente. Lo exacto: depende sólo del patrón de error, no de lo que se mandó. Lo insuficiente: en el (7,4) cada síndrome es compatible con $2^{k} = 16$ patrones distintos, y el decodificador tiene que apostar por uno. El standard array es esa apuesta hecha de una vez para los $2^{n}$ vectores que pueden llegar. La decodificación por síndrome es la misma apuesta guardada en una tabla de $2^{n - k}$ renglones.

01 · La regla: el patrón más liviano

Sobre un canal binario simétrico que da vuelta cada bit con probabilidad $p$ , independiente de los demás, un patrón de peso $w$ en una palabra de $n$ bits tiene probabilidad

P (e) = p^{w} {(1 - p)}^{n - w}

Pasar de peso $w$ a $w + 1$ multiplica esa probabilidad por $p / (1 - p)$ , que es menor que 1 mientras $p < 1 / 2$ . Entre los patrones que comparten síndrome, entonces, el más probable es el de menor peso. Elegirlo es la regla de máxima verosimilitud.

Es también la regla de mínima distancia. Si llegó $r = v + e$ , la distancia de $r$ a la palabra de código $v$ es $d (r, v) = w (r + v) = w (e)$ . Suponer el patrón más liviano es lo mismo que entregar la palabra más cercana a lo recibido.

Con palabras equiprobables, ninguna regla tiene menos probabilidad de entregar una palabra equivocada. Pero óptima no quiere decir infalible. Si el canal metió un patrón pesado y hay otro más liviano con el mismo síndrome, el decodificador elige el liviano y entrega otra palabra. La distancia mínima garantiza corregir cualquier patrón de hasta $t = ⌊ (d_{min} - 1) / 2 ⌋$ errores, la capacidad de corrección. Qué corrige la regla de verdad, patrón por patrón, lo dice el arreglo.

02 · Cómo se arma el arreglo

El standard array reparte los $2^{n}$ vectores de $V_{n}$ en una tabla de $2^{n - k}$ filas por $2^{k}$ columnas. Se arma fila por fila.

Paso 1: la primera fila es el código. Las $2^{k}$ palabras, empezando por la nula. Cada una encabeza una columna.

Paso 2: el líder es el más liviano que queda. Entre los vectores que todavía no aparecen en la tabla se elige uno de peso mínimo, $l$ , y va a la primera columna.

Paso 3: la fila es el líder más el código. Debajo de la palabra $v$ va $l + v$ . Debajo de la nula queda el propio $l$ .

Paso 4: repetir hasta agotar. Cuando todos los vectores de $V_{n}$ están en la tabla, se termina.

Cada fila es un coset del código, el conjunto $l + C$ , y el vector que la encabeza es su líder de coset. Cada fila agrega $2^{k}$ vectores nuevos, sin repetir ninguno (lo prueba la sección siguiente), así que las filas son $2^{n} / 2^{k} = 2^{n - k}$ . En el (7,4), 8 filas de 16.

03 · Tres propiedades, con su porqué

Cada vector aparece una sola vez. Dentro de una fila, $l + v = l + v^{'}$ obliga a $v = v^{'}$ . Entre filas: si un vector estuviera en la fila de $l$ y en la de un líder posterior $l^{'}$ , sería $l + v = l^{'} + v^{'}$ , o sea $l^{'} = l + (v + v^{'})$ . La suma de dos palabras es palabra, así que $l^{'}$ ya estaba en la fila de $l$ . Pero se lo eligió entre los que no estaban.

Dos vectores de una fila difieren en una palabra. $(l + v) + (l + v^{'}) = v + v^{'}$ : el líder se cancela.

Una fila, un síndrome, y al revés. Con $H$ la matriz de paridad, toda palabra cumple $v H^{T} = 0$ , y entonces $(l + v) H^{T} = l H^{T}$ : la fila entera comparte el síndrome de su líder. Dos filas no lo comparten: si $l H^{T} = l^{'} H^{T}$ , entonces $l + l^{'}$ es palabra y $l^{'}$ estaba en la fila de $l$ , el mismo absurdo de antes.

La tercera es la que hace práctico al arreglo. Hay exactamente tantas filas como síndromes posibles, $2^{n - k}$ , y el síndrome de lo recibido dice en qué fila cayó sin tener que buscarlo.

04 · Decodificar con el arreglo

Llega $r$ y se lo ubica en el arreglo. El líder de su fila es el patrón que se supone, $\hat{e}$ , y el encabezado de su columna es lo que se entrega:

\hat{v} = r + \hat{e}

Como el líder es el vector más liviano de la fila, es exactamente la regla de la sección 01.

De ahí sale lo más útil del arreglo: un patrón se corrige si y sólo si es un líder. Si se mandó $v$ y el canal metió $e$ , lo recibido $r = v + e$ cae en la misma fila que $e$ , porque difieren en una palabra. Si $e$ es el líder, se entrega $r + e = v$ . Si no lo es, el líder es otro vector $l \neq e$ y se entrega $v + e + l \neq v$ . Hay $2^{n - k}$ patrones corregibles, uno por fila, y ni uno más.

En el (7,4) son 8 de 128: la palabra nula y los siete errores simples. Ese $8 = 1 + 7$ es lo que hace perfecto al (7,4). En el (8,4), el mismo código con un bit de paridad global y $d_{min} = 4$ , son 16 de 256: la nula, los 8 errores simples y 7 de los 28 dobles. Ahí $t = 1$ y sin embargo se corrigen siete patrones de peso 2. $t$ es lo que se garantiza para todo patrón de ese peso, no lo único que se corrige.

Contando los líderes por peso, $α_{i}$ de peso $i$ , la probabilidad de que el decodificador entregue una palabra equivocada sale directa:

P (E) = 1 - \sum_{i = 0}^{n} α_{i} p^{i} {(1 - p)}^{n - i}

En el (7,4), $α_{0} = 1$ y $α_{1} = 7$ , y con $p = 10^{- 2}$ da $P (E) = 2,03 \cdot 10^{- 3}$ . Cuánto vale esto medido en $E_{b} / N_{0}$ —la ganancia de codificación, y el cruce del (7,4) con no codificar en 5,85 dB— está en «El código que todos inventan primero no paga nunca».

En el (7,4), cualquier vector que toques cae en una fila cuyo líder pesa 0 o 1, y el aviso dice lo mismo cada vez: se acierta sólo si el canal metió justo ese líder. Con 16 vectores por fila, quedan quince maneras de haber llegado ahí. En el (8,4) aparecen filas con un líder de peso 2, y con ellas cuatro candidatos en rojo. Ahí el botón «Otro líder» se habilita, y vale la pena apretarlo con un vector elegido para ver qué pasa con su columna.

05 · Los empates

En el (7,4) no hay nada que elegir: cada fila tiene un solo vector de peso mínimo. En el (8,4), las siete filas cuyo líder pesa 2 tienen cuatro vectores de peso 2 cada una —los 28 dobles se reparten así, siete por cuatro—, y los cuatro son igual de probables. Cuál encabeza la fila es una elección arbitraria, y no es inocente. Dos candidatos $l$ y $l^{'}$ de la misma fila difieren en una palabra, $l + l^{'}$ , que en el (8,4) pesa 4. Cambiar de líder le suma esa palabra a todo lo que la fila entrega. Medido en las siete filas y con cada candidato alternativo: cambia la palabra entregada en las 16 celdas de la fila. Mismo vector recibido, mismo síndrome, otra palabra.

Un empate sólo puede pasar por encima de $t$ . Dos vectores de peso a lo sumo $t$ en la misma fila diferirían en una palabra de peso a lo sumo $2 t < d_{min}$ , y esa palabra no existe. Por eso un líder de peso $\leq t$ es único, y es el que se corrige con garantía.

Al revés no vale: que el líder pese más que $t$ no obliga a empatar. El (7,1) cuya única palabra no nula es 1100001 tiene $d_{min} = 3$ y $t = 1$ . De sus 64 filas, 56 tienen un líder de peso entre 2 y 5, y ninguna tiene empate. Cada fila son dos vectores, $l$ y $l + 1100001$ , y como esa palabra pesa 3, sus pesos tienen distinta paridad: nunca coinciden. El coset de 0110000, por ejemplo, es {0110000, 1010001}, con un único vector de peso 2.

Y con decodificación completa, el bit de más del (8,4) no compra nada. Sus líderes son $α_{0} = 1$ , $α_{1} = 8$ y $α_{2} = 7$ , y sacando factor común ${(1 - p)}^{6}$ los dos códigos dan lo mismo:

{(1 - p)}^{2} + 8 p (1 - p) + 7 p^{2} = 1 + 6 p = (1 - p) + 7 p

A la izquierda, lo que queda del (8,4); a la derecha, lo que queda del (7,4). Las dos tienen $P (E) = 1 - {(1 - p)}^{6} (1 + 6 p)$ , para todo $p$ : los siete dobles que el (8,4) corrige pagan exactamente lo que cuesta exponer un bit más al canal. Para que el octavo bit sirva hay que cambiar de decodificador.

06 · La decodificación incompleta

La decodificación incompleta corrige sólo en las filas cuyo líder pesa $\leq t$ . Para los demás síndromes declara falla y levanta una bandera, en vez de apostar. Renuncia justo a las apuestas más flojas, que es donde viven los empates, y en un sistema con retransmisión una bandera vale más que una corrección dudosa.

Lo que no trae es una promesa sobre los errores grandes. La bandera se levanta cuando $r$ está a distancia mayor que $t$ de todas las palabras, fuera de toda esfera de radio $t$ , y nada más. Un patrón pesado que deja a $r$ adentro de la esfera de otra palabra se corrige hacia esa otra palabra, en silencio, igual que con la decodificación completa. Medido sobre los 255 patrones no nulos del (8,4), mandando cualquier palabra:

peso del error	patrones	bandera	bien corregidos	mal, en silencio
1	8	0	8	0
2	28	28	0	0
3	56	0	0	56
4	70	56	0	14
5	56	0	0	56
6	28	28	0	0
7	8	0	0	8
8	1	0	0	1
todos	255	112	8	135

Los patrones de peso impar desde 3 dejan a $r$ a distancia 1 de alguna palabra y salen mal sin aviso. Los 14 de peso 4 que no avisan y el de peso 8 son palabras de código, que ningún síndrome ve. Con $p = 10^{- 2}$ , la incompleta entrega en silencio una palabra equivocada con probabilidad $5,34 \cdot 10^{- 5}$ y levanta la bandera con $2,64 \cdot 10^{- 3}$ . La completa se equivoca, siempre en silencio, con $2,03 \cdot 10^{- 3}$ .

En el (7,4) la incompleta no se distingue de la completa. Es perfecto: sus esferas de radio 1 cubren $V_{7}$ entero, ningún $r$ queda afuera y la bandera no se levanta nunca. Los 120 patrones de peso 2 o más salen mal, todos en silencio.

07 · La tabla de síndromes

Del arreglo se puede tirar todo menos la primera columna. Como el síndrome identifica la fila, decodificar son tres pasos:

Paso 1: calcular el síndrome, $s = r H^{T}$ .

Paso 2: buscar el líder $\hat{e}$ que la tabla tiene para ese $s$ .

Paso 3: entregar $\hat{v} = r + \hat{e}$ . Con el código en forma sistemática, el mensaje son sus primeras $k$ posiciones.

La tabla tiene $2^{n - k}$ entradas en lugar de $2^{n}$ . La del (7,4), con la $H$ del apunte y los vectores escritos con la posición 0 a la izquierda:

síndrome s	líder ê	qué supone
000	0000 000	sin errores
110	1000 000	error en la posición 0
011	0100 000	error en la posición 1
111	0010 000	error en la posición 2
101	0001 000	error en la posición 3
100	0000 100	error en la posición 4
010	0000 010	error en la posición 5
001	0000 001	error en la posición 6

Salvo el nulo, cada síndrome es una columna de $H$ . Que un error simple en la posición $i$ dé $s = h_{i}$ vale en cualquier código: el síndrome es la suma de las columnas de $H$ donde hubo error. Lo particular del (7,4) es lo otro, que los siete síndromes no nulos sean todos errores simples y no sobre ninguno para un patrón más pesado. Pasa porque sus siete columnas son los siete vectores no nulos de 3 bits: es el $8 = 1 + 7$ otra vez.

El costo sigue siendo exponencial, ahora en la redundancia. Un (255,239) necesita una tabla de $2^{16} = 65 536$ líderes, y su arreglo tendría $2^{255}$ celdas: nadie lo construye, se lo estudia porque dice qué hace un decodificador óptimo. Por eso los códigos que vienen imponen estructura. Los cíclicos de la Unidad 5 y los BCH de la Unidad 6 calculan el patrón de error a partir del síndrome, en vez de buscarlo.

08 · El corrector del RTL

El decodificador del (7,4) del curso es la tabla de síndromes en hardware. Un bloque calcula los tres bits del síndrome con compuertas XOR, y el corrector traduce el síndrome a una posición, arma un patrón de un solo bit y lo suma a lo recibido:

always_comb begin
    case (i_syndrome)
        3'b011:  error_position = 3'd0; //h0
        3'b110:  error_position = 3'd1; //h1
        3'b111:  error_position = 3'd2; //h2
        3'b101:  error_position = 3'd3; //h3
        3'b001:  error_position = 3'd4; //h4
        3'b010:  error_position = 3'd5; //h5
        3'b100:  error_position = 3'd6; //h6
        default: error_position = 3'd0;
    endcase
end

always_comb begin
    estimated_error                 = 7'd0;
    estimated_error[error_position] = 1'b1;
end

assign corrected_message = (i_zero_syndrome) ? i_message : (i_message ^ estimated_error);

El detalle que confunde está en los literales. El bus del síndrome se empaqueta como {s2, s1, s0}, con $s_{0}$ en el bit 0, y un literal de Verilog escribe el bit más alto a la izquierda. La tabla de arriba escribe al revés, con la posición 0 a la izquierda. Así la columna $h_{0} = 110$ — $s_{0} = 1$ , $s_{1} = 1$ , $s_{2} = 0$ — aparece en el case como 3'b011. Son los mismos tres bits leídos desde la otra punta, y los siete casos son las siete columnas de $H$ dadas vuelta. Los dos que no cambian, $h_{2}$ y $h_{3}$ , son palíndromos.

El síndrome nulo cae en el default, que apunta a la posición 0. No la invierte porque la última línea entrega i_message tal cual cuando i_zero_syndrome está en alto. Y es un decodificador completo: la salida o_is_corrected sólo dice que el síndrome no fue nulo, no que la corrección haya salido bien. Con dos errores también se levanta, y lo entregado está mal. Simulado sobre los 2048 casos —los 16 mensajes por los 128 patrones de error—, el mensaje que entrega coincide en todos con el de la tabla de síndromes.

Para tener a mano

Sobre el BSC con $p < 1 / 2$ , máxima verosimilitud es suponer el patrón más liviano, que es entregar la palabra más cercana. Óptima, no infalible.
El standard array: $2^{n - k}$ cosets por $2^{k}$ palabras. Cada fila la encabeza un vector de peso mínimo, el líder. Cada vector aparece una vez, y cada fila tiene su propio síndrome.
Se entrega el encabezado de la columna, $\hat{v} = r + \hat{e}$ . Un patrón se corrige si y sólo si es líder: (7,4), 8 de 128; (8,4), 16 de 256, con 7 dobles adentro aunque $t = 1$ .
$P (E) = 1 - \sum α_{i} p^{i} {(1 - p)}^{n - i}$ . El (7,4) en $p = 10^{- 2}$ : 2,03·10⁻³. El (8,4) completo da lo mismo para todo $p$ .
Los empates sólo pasan con el líder por encima de $t$ , pero no siempre que pasa eso: el (8,4) tiene siete filas con cuatro candidatos, y el (7,1) de 1100001 ninguna. Cambiar de candidato cambia lo entregado en toda la fila.
La tabla de síndromes: $s = r H^{T}$ , el líder de $s$ , $\hat{v} = r + \hat{e}$ . Son $2^{n - k}$ entradas. En el RTL, con el bus {s2, s1, s0}, la columna $h_{0} = 110$ se escribe 3'b011.
La incompleta avisa sólo cuando $r$ cae fuera de toda esfera de radio $t$ . En el (7,4), nunca. En el (8,4), 112 de 255 patrones, y los 56 de peso 3 salen mal sin aviso.