Los códigos de Hsiao

Un SEC-DED corrige un error y avisa cuando hay dos. La manera de libro de conseguirlo es el código extendido: al Hamming se le agrega un bit de paridad global, y a su $H$ una fila de unos. Hsiao observó en 1970 que esa fila sobra: la misma garantía sale de elegir bien las columnas. Y como sobran columnas para elegir, la elección se puede hacer pensando en el circuito. Por eso el SEC-DED de las memorias de servidor es un Hsiao y no un Hamming extendido.

01 · La definición

Un código de Hsiao es un código lineal $(n,k)$ cuya matriz de paridad $H$, de $m\times n$ con $m=n-k$, tiene columnas

$$h_0,h_1,\dots ,h_{n-1}\text{no nulas, distintas y con }w(h_i)\text{ impar}$$

donde $w(h_i)$ es el peso de la columna: cuántos unos tiene. Nada más. No hay fila agregada ni bit de paridad global: es una $H$ común de $m$ filas a la que se le pide algo a cada columna. Las $m$ columnas de peso 1 son la identidad, y con ellas en las posiciones de paridad la $H$ queda en forma sistemática; las $k$ de dato se eligen entre las de peso 3, 5, 7…

Las dos condiciones de siempre —no nulas, distintas— son las de un Hamming al que le faltan columnas, o sea un código acortado. Lo nuevo es la tercera, y se paga: de los $2^m$ vectores de $m$ bits, exactamente la mitad tiene peso impar —y ninguno de ellos es nulo—, así que

$$n\le 2^{m-1}$$

Con $m=8$ hay 128 columnas de peso impar, y el (72,64) usa 72.

02 · Por qué la distancia es al menos 4

La distancia mínima de un código lineal es la menor cantidad de columnas de $H$ que suman cero. Para $d_{\text{min}}\ge 4$ hay que descartar conjuntos de una, dos y tres.

Paso 1: una columna sola. No es nula, por hipótesis.

Paso 2: dos columnas. $h_i+h_j=0$ sólo si son iguales, y son distintas.

Paso 3: tres columnas, contando unos. Al sumar dos vectores en $\mathrm{GF}(2)$ se cancelan los unos que coinciden, de a pares, así que la paridad del peso se suma:

$$\begin{array}{rl}w(a+b)& =w(a)+w(b)-2w(a\wedge b)\\ & \equiv w(a)+w(b)(\mathrm{mod}2)\end{array}$$

Tres columnas de peso impar suman un vector de peso $1+1+1\equiv 1$: impar, y por lo tanto no nulo. Ninguna terna suma cero, y $d_{\text{min}}\ge 4$.

La misma cuenta dice qué hace la fila de unos del extendido: le da a cada columna un 1 más abajo, y lo que verifica es la paridad del patrón. En un Hsiao esa información ya está adentro: un número impar de columnas impares suma un vector impar, y un número par, uno par. La paridad del peso del síndrome es la paridad del patrón de error. El (8,4) del curso, con $H=[P^{\mathrm{T}}I]$, ya es así: cuatro columnas de peso 3 y la identidad. Es el Hsiao más largo con $m=4$.

03 · Cómo decide el decodificador

Sin $s_0$ aparte, los cuatro casos del SEC-DED se leen del síndrome entero $s=r{H}^{\mathrm{T}}$:

• $s=0$: se acepta lo recibido.
• $s$ de peso impar e igual a una columna $h_i$: error simple en la posición $i$, se corrige.
• $s$ de peso impar que no es ninguna columna: al menos tres errores; se avisa.
• $s$ de peso par y no nulo: un número par de errores, al menos dos; se avisa.

El último caso es el que importa, y no falla nunca: dos columnas impares distintas suman un vector par no nulo. En el (72,64), los 2556 patrones dobles caen los 2556 ahí, y lo mismo en el extendido del mismo tamaño: la garantía de peor caso es la misma. Lo que se agrega al circuito es un XOR de los $m$ bits del síndrome, que da la paridad de su peso. El caso «error en el bit de paridad global» del extendido no existe: acá no hay bit de paridad global.

04 · No cuesta largo

Parecería que pedir peso impar tira la mitad de las columnas. Pero el extendido usa una fila más para lo mismo. Con $r$ bits de paridad, el extendido es un Hamming de $r-1$ filas más la de unos, y llega a $n=2^{r-1}$; el Hsiao de $r$ filas, a $n\le 2^{r-1}$. El mismo techo, con los mismos bits de paridad: el (8,4) con 4, el (16,11) con 5, el (64,57) con 7.

El techo es duro. Con cuatro bits de paridad hay ocho columnas de peso impar y no se puede pasar del (8,4): por eso un Hsiao (12,8) con $n-k=4$, como el que lista en su primera fila la Tabla 4.1 de Lin y Costello, no puede existir. Con 64 bits de dato, siete bits de paridad dan a lo sumo 64 columnas y hacen falta 71: el (72,64) necesita ocho, igual que el extendido.

05 · El criterio de Hsiao

La distancia sale del peso impar, elija uno las columnas que elija. Lo que la elección decide es el circuito. Cada fila de $H$ es una ecuación de paridad, y en un calculador de síndrome paralelo cada ecuación es un árbol de compuertas XOR con tantas entradas como unos tiene la fila. Hsiao pide dos cosas:

1. Minimizar la cantidad total de unos de $H$: es el área, la cantidad de entradas de XOR. Se logra tomando las columnas de dato por peso creciente: todas las de peso 3 que hagan falta, y recién después las de peso 5.
2. Repartir los unos lo más parejo posible entre las filas: el síndrome está listo cuando termina su árbol más profundo, así que el retardo lo fija la fila más cargada. Con $w$ entradas y compuertas de $b$ entradas, el árbol tiene $\lceil {\log }_{b}w\rceil$ niveles.

En el (22,16), con $m=6$, hay $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ columnas de peso 3 y hacen falta 16. El primer criterio ya está: con las seis de la identidad son $6+16·3=54$ unos, el mínimo. Si las 54 se reparten parejo, 9 por fila. Cada fila aparece en 10 de las 20 columnas de peso 3, así que con la identidad pesaría 11 si se usaran todas; dejar afuera cuatro columnas le saca a cada fila tantos unos como columnas descartadas la tocan. Las filas quedan en 9 cuando las cuatro descartadas tocan dos veces cada fila. Recorridas las 4845 maneras de descartar cuatro, 75 dejan las seis filas en 9; las demás dejan alguna entre 10 y 11.

El arranque tiene dos filas de 11 y cuatro de 8. Sacá una de las columnas que tocan las dos filas cargadas y meté una de las que quedaron afuera: el total no se mueve, el perfil sí. Ahora probá una columna de peso 5 en lugar de una de peso 3: el total sube a 56 y ya no hay reparto que deje las seis filas en 9. Fijate en las dos últimas lecturas. Con compuertas de dos entradas, 9, 10 y 11 entradas dan los mismos cuatro niveles; con compuertas de tres, 9 entra en dos niveles y 10 ya pide tres. El balance se cobra en escalones, y si el escalón cae o no depende de la compuerta.

06 · El (72,64) contra el extendido

Con 64 bits de dato y $m=8$ hay 8 columnas de peso 1, $\left(\genfrac{}{}{0ex}{}{8}{3}\right)=56$ de peso 3 —se usan todas— y faltan 8, que salen de las de peso 5. Las 56 de peso 3 tocan cada fila $56·3/8=21$ veces; las 8 de peso 5 aportan 40 unos, y elegidas para que cada fila reciba 5, cada fila pesa $1+21+5=27$. Son 216 unos, 27 por fila, que es lo que da la Tabla 4.1 de Lin y Costello.

El extendido del mismo tamaño es el de la ec. (7) del apunte, $H_{\text{ext}}=\left[\begin{array}{cc}H& 0\\ 1\cdots 1& 1\end{array}\right]$, con $H$ la de un Hamming de $m=7$ acortado a 71 columnas. Para compararlo en su mejor versión, las 71 son las más livianas: las 7 de peso 1, las 21 de peso 2, las 35 de peso 3 y 8 de peso 4 (las de menor valor). Contando los unos de cada fila de las dos matrices:

El extendido pierde por los dos criterios, y la fila de unos es la razón de ambos: le suma 72 unos a la cuenta y es, ella sola, un árbol de 72 entradas. Con compuertas de dos entradas, las siete filas de arriba piden 5 niveles, como las del Hsiao, y la de 72 pide 7: el problema es la fila que verifica la paridad global, que Hsiao reparte entre todas. Con compuertas de tres entradas el árbol de 27 tiene los tres niveles que menciona el libro para este código, y ahí el escalón cae antes: 29 ya pasa de 27, así que las filas de arriba del extendido piden 4 niveles, los mismos que la de 72. Lo que decide es el balance, no sólo la fila de unos.

07 · La construcción en Python

El voraz que arma las dos matrices: la identidad, después las columnas por peso impar creciente, y entre las de un mismo peso, de a una, la que deja el perfil de filas más parejo —compara primero la fila más cargada—. Lo de los comentarios es la salida de correrlo.

import itertools
import numpy as np


def hsiao(n, k):
    """H = [I_m | D] de un Hsiao (n, k): columnas distintas de peso impar."""
    m = n - k
    cols = [np.eye(m, dtype=int)[i] for i in range(m)]  # paridad: peso 1
    carga = np.ones(m, dtype=int)                         # unos por fila
    for w in range(3, m + 1, 2):                          # pesos impares
        faltan = n - len(cols)
        if faltan == 0:
            break
        cand = [np.isin(np.arange(m), s).astype(int)
                for s in itertools.combinations(range(m), w)]
        for _ in range(min(faltan, len(cand))):
            # la que deja el perfil más parejo: compara primero la fila más cargada
            perfil = lambda i: sorted(carga + cand[i], reverse=True)
            i = min(range(len(cand)), key=perfil)
            carga = carga + cand[i]
            cols.append(cand.pop(i))
    return np.array(cols, dtype=np.uint8).T


def ninguna_terna_suma_cero(H):
    cols = [int("".join(map(str, c)), 2) for c in H.T]
    conj = set(cols)
    return 0 not in conj and len(conj) == len(cols) and \
        all(a ^ b not in conj for a, b in itertools.combinations(cols, 2))


for n, k in [(22, 16), (72, 64)]:
    H = hsiao(n, k)
    print((n, k), "unos:", int(H.sum()), "por fila:", H.sum(axis=1).tolist(),
          "d_min >= 4:", ninguna_terna_suma_cero(H))

# (22, 16) unos: 54 por fila: [9, 9, 9, 9, 9, 9] d_min >= 4: True
# (72, 64) unos: 216 por fila: [27, 27, 27, 27, 27, 27, 27, 27] d_min >= 4: True

La prueba de la distancia usa las columnas como enteros: una terna suma cero si y sólo si el XOR de dos es la tercera, así que alcanza con mirar los pares. Para estos dos códigos el voraz llega al óptimo de los dos criterios: el mínimo de unos y todas las filas iguales. Es un voraz, y para otros $(n,k)$ no hay garantía de que reparta igual de bien. La $H$ del (22,16) que sale de acá tampoco es la de la Figura 4.1 de Lin y Costello: tiene el mismo perfil, otras columnas.

08 · Lo que el peso impar no arregla

Una sola columna par lo rompe. La garantía es de todas las columnas o de ninguna. En el Hsiao (22,16), cambiar la última columna por $110000$, de peso 2, deja $d_{\text{min}}=3$: esa columna es la suma de las dos primeras de la identidad, y aparecen seis palabras de peso 3. Un doble error en dos de esas tres posiciones da el síndrome de un simple en la tercera, y se corrige mal en silencio.

Con tres errores, corrige mal más de la mitad de las veces. Un triple da siempre un síndrome de peso impar. Si coincide con una columna, el decodificador corrige esa posición y entrega cuatro bits mal; si no, avisa. Enumerados los 59 640 patrones triples del (72,64):

En el extendido un triple da $s_0=1$; si $s^{\prime }$ es una de las 71 columnas se corrige mal, si es nulo la lógica lo toma por un error en el bit de paridad global y acepta, y si es uno de los 56 síndromes que el acortamiento dejó libres, avisa. Entre Hsiao y el extendido de la tabla de arriba hay menos de un punto: el peso impar no compra triples. Lo que sí los mueve es qué columnas sobreviven al acortar. El mismo extendido con las 64 de dato tomadas en orden numérico entre las de peso 2 o más —un (72,64) tan válido como el otro, con 284 unos y filas de 36, 36, 36, 32, 32, 32, 8 y 72— avisa sólo el 24,0 %. Contra los dobles, los tres avisan los 2556.

Para tener a mano

1. Código de Hsiao: $H$ de $m$ filas con columnas no nulas, distintas y de peso impar. Es un Hamming acortado en el que sobreviven sólo columnas impares; $n\le 2^{m-1}$, el mismo techo que el extendido con los mismos bits de paridad.
2. $d_{\text{min}}\ge 4$ porque tres columnas impares suman un vector impar, que no es nulo. Sin fila de paridad global: la paridad del peso del síndrome es la del patrón.
3. Decide así: $s=0$ acepta; impar y columna, corrige; impar y no columna, avisa; par no nulo, avisa. Los dobles se avisan todos.
4. Criterio de Hsiao: mínimo total de unos (columnas por peso impar creciente) y filas parejas. Cada fila es un árbol de XOR de $\lceil {\log }_{b}w\rceil$ niveles, y la más cargada fija el retardo.
5. (22,16): 54 unos, 9 por fila; 75 de las 4845 maneras de descartar cuatro columnas de peso 3 lo logran. (72,64): 8 de peso 1, las 56 de peso 3 y 8 de peso 5; 216 unos, 27 por fila. El extendido en la forma $[H0;1\cdots 1]$, con las columnas más livianas: 258 unos y una fila de 72.
6. Contra triples, Hsiao no es mejor que un buen extendido: 43,7 % contra 42,8 % avisados en el (72,64). Una sola columna de peso par y vuelve $d_{\text{min}}=3$.