El Hamming extendido y el SEC-DED

Un código de Hamming corrige un error y es perfecto: cada síndrome no nulo es la columna de una posición. Por eso, con dos errores, el síndrome es la columna de una tercera posición, el decodificador la invierte y entrega una palabra con tres bits mal sin avisar a nadie. Un bit más de redundancia alcanza para que eso no pase: el decodificador sigue corrigiendo un error, y con dos levanta una bandera.

01 · La definición

El código extendido de un código $(n,k)$ agrega a cada palabra de código un bit de paridad global en la posición $n$, la suma módulo 2 de las $n$ anteriores:

$$v_n=\sum _{i=0}^{n-1}{v}_i$$

Con eso la suma de los $n+1$ bits es cero, y esa es una ecuación de paridad más. La matriz de paridad crece en una columna de ceros, la del bit nuevo, que no entra en ninguna de las ecuaciones viejas, y en una fila de unos, la ecuación nueva. Es la ec. (7) del apunte:

$$H_{\text{ext}}=\left(\begin{array}{cc}H& 0\\ 11\cdots 1& 1\end{array}\right)$$

Un código $(n,k)$ pasa a $(n+1,k)$: la misma información, un bit más de paridad. Aplicado al Hamming de orden $m$ da el Hamming extendido, de parámetros

$$(2^m,2^m-1-m,4)$$

La familia es $(8,4)$, $(16,11)$, $(32,26)$, $(64,57)$, $(128,120)$ y $(256,247)$. La tasa baja un poco: de $4/7\approx \mathrm{0,571}$ a $1/2$ en el primero, de 0,969 a 0,965 en el último.

El $(8,4)$ del curso sale del $(7,4)$ del apunte. Cada fila de $G$ recibe su paridad, y $H$ recibe la columna y la fila nuevas:

$$G_{\text{ext}}=\left(\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 0& 1\\ 0& 1& 0& 0& 0& 1& 1& 1\\ 0& 0& 1& 0& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 0& 1& 1\end{array}\right)$$ $$H_{\text{ext}}=\left(\begin{array}{cccccccc}1& 0& 1& 1& 1& 0& 0& 0\\ 1& 1& 1& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 0& 0& 1& 0\\ 1& 1& 1& 1& 1& 1& 1& 1\end{array}\right)$$

El mensaje $u=1001$ se codifica en el $(7,4)$ como $\mathrm{1001\; 011}$, de peso 4, y se extiende con un 0: $v=\mathrm{1001\; 0110}$. Las cuatro filas de $H_{\text{ext}}$ son, además, palabras del código: el $(8,4)$ es su propio dual, el código auto-dual del cierre de la Unidad 3.

Un código SEC-DED —single error correction, double error detection— corrige todo error simple y detecta, sin corregirlo, todo error doble, y distingue un caso del otro. Es el modo mixto de la Unidad 3: corregir hasta $\lambda$ errores y detectar hasta $\ell$ pide $\lambda +\ell +1\le d_{\text{min}}$, y con $\lambda =1$ y $\ell =2$ hace falta $d_{\text{min}}=4$. El Hamming tiene 3; el extendido, 4.

02 · Por qué la distancia sube a 4

El teorema es general: si un código lineal tiene distancia mínima $d$ impar, su extendido tiene distancia mínima $d+1$. En un código lineal la distancia mínima es el menor peso de una palabra no nula, así que alcanza con seguir los pesos.

Paso 1: toda palabra extendida tiene peso par. El bit agregado es la suma de los demás, así que completa una cantidad par de unos.

Paso 2: ningún peso baja. Una palabra de peso par recibe un 0 y conserva su peso; una de peso impar recibe un 1 y gana uno.

Paso 3: las de peso $d$ pasan a $d+1$. Como $d$ es impar, todas las palabras de peso mínimo reciben un 1. Las de peso menor que $d$ no existían, y las de peso $d$ dejaron de pesar $d$. El menor peso no nulo es ahora $d+1$, que existe porque las de peso $d$ llegan ahí.

En el $(7,4)$ hay una palabra nula, siete de peso 3, siete de peso 4 y una de peso 7. Extendidas, las siete de peso 3 suben a 4 y se juntan con las otras siete, y la de peso 7 sube a 8:

$$1+7z^3+7z^4+z^7⟶1+14z^4+z^8$$

El $(16,11)$, enumerando sus 2048 palabras, tiene 140 de peso 4, 448 de peso 6, 870 de peso 8, 448 de peso 10, 140 de peso 12 y la de todos unos: ningún peso impar.

La misma cuenta se lee en las columnas de $H_{\text{ext}}$, donde la distancia mínima es la menor cantidad de columnas que suman cero. Todas las columnas tienen un 1 en la última fila, así que una suma de una cantidad impar de columnas tiene un 1 abajo y no puede ser nula. Tres columnas no suman cero nunca: hacen falta por lo menos cuatro. Es la idea que el código de Hsiao lleva más lejos, con todas las columnas de peso impar y sin la fila de unos.

El teorema funciona igual con cualquier $d$ impar: el Golay $(23,12,7)$ se extiende al $(24,12,8)$ con el mismo bit.

03 · El síndrome en dos piezas

Con $H_{\text{ext}}$, el síndrome de lo recibido tiene $m+1$ bits, y se parte en dos que dicen cosas distintas:

$$s=r{H}_{\text{ext}}^{\mathrm{T}}=(s^{\prime },s_0)$$

$s^{\prime }$ son los $m$ primeros: el síndrome del Hamming de adentro. Como todo síndrome, vale la suma de las columnas de $H$ en las posiciones donde el patrón de error $e$ tiene un 1, y por eso habla de la posición. La columna del bit de paridad global es nula en esas filas: un error en la posición $n$ no mueve $s^{\prime }$.

$s_0$ es el último: la ecuación de la fila de unos, o sea la suma de todos los bits recibidos. Como $r=v+e$ y las palabras suman cero,

$$s_0=\sum _{i=0}^n{r}_i=\sum _{i=0}^n{v}_i+\sum _{i=0}^n{e}_i=w(e)mod2$$

vale 1 si el patrón tiene una cantidad impar de errores y 0 si tiene una cantidad par. Habla de la paridad del error, y no sabe nada de dónde cayó.

La partición depende de escribir $H$ como en la ec. (7). La $H$ sistemática del $(8,4)$, la de la forma $[P^{\mathrm{T}}I]$, define el mismo código, pero su última fila es $\mathrm{1101\; 0001}$: la suma de las cuatro filas de $H_{\text{ext}}$. Con esa matriz ningún bit del síndrome es la paridad global; la paridad global es la suma de los cuatro, o sea la paridad del peso del síndrome.

04 · Los cuatro casos

Cada pieza vale cero o no, y las cuatro combinaciones cubren todo. Es la Figura 3 del apunte:

$s_0=0$ y $s^{\prime }=0$. El síndrome entero es nulo: lo recibido es palabra de código. Lo más probable es que no haya habido error, y se acepta.

$s_0=1$ y $s^{\prime }\ne 0$. Una cantidad impar de errores, y el más probable es uno solo. $s^{\prime }$ es la columna de su posición, y se invierte ese bit. Con $v=\mathrm{1001\; 0110}$ y un error en la posición 2 llega $\mathrm{1011\; 0110}$, con $s^{\prime }=111=h_2$ y $s_0=1$.

$s_0=1$ y $s^{\prime }=0$. Una cantidad impar de errores que no toca ninguna ecuación del Hamming. El único patrón de peso 1 que hace eso es el error en el propio bit de paridad global, cuya columna es nula arriba: los bits de información están limpios, y alcanza con descartar el bit de paridad.

$s_0=0$ y $s^{\prime }\ne 0$. Una cantidad par de errores, y no es cero porque el síndrome no es nulo: hay por lo menos dos. El código no puede corregirlos, así que declara una falla de decodificación y lo avisa. Con errores en las posiciones 1 y 4 llega $\mathrm{1101\; 1110}$, con $s^{\prime }=111$ y $s_0=0$. El $(7,4)$ solo habría visto $s^{\prime }=h_2$ y habría invertido la posición 2.

El cuarto caso es la razón de toda la construcción, y su lugar se cuenta en síndromes. El $(8,4)$ tiene 16: el nulo, siete de error simple en las posiciones 0 a 6, uno para el bit de paridad global, y siete que no son de ningún error simple. Esos siete, con $s_0=0$ y $s^{\prime }\ne 0$, son la bandera. En general quedan $2^m-1$ libres, y el extendido deja de ser perfecto justamente por eso.

Prendé un bit cualquiera: cae abajo a la derecha, o abajo a la izquierda si es el 7, y lo entregado es $v$. Prendé un segundo: pasa arriba a la derecha, sea cual sea el par. Un tercero lo vuelve a bajar, y ahí el decodificador corrige con la misma confianza que con uno solo. Después de un rato, la fila de arriba junta sólo pesos pares y la de abajo sólo impares: $s_0$ elige la fila y no mira nada más.

05 · Lo que pasa con cada peso de error

Como el código es lineal, lo que el decodificador hace con un patrón no depende de la palabra enviada. Recorriendo los 256 patrones del $(8,4)$ con la decisión de cuatro casos, y contando como entrega mal toda palabra aceptada o corregida que no es la enviada:

Los 8 simples se corrigen: siete en el cuadro de corregir y uno, el del bit 7, en el del bit global. Los 28 dobles levantan la bandera, todos: tienen $s_0=0$, y $s^{\prime }$ no puede ser nulo: dos columnas distintas de $H$ no suman cero, y si uno de los dos errores cae en el bit 7, $s^{\prime }$ es la columna del otro. Hasta ahí, lo que el teorema garantiza.

Después se termina. Los 56 triples se corrigen mal, todos, y salen con cuatro bits mal: un triple deja lo recibido a distancia 1 de otra palabra, el decodificador lo lleva ahí y le suma un error a los tres del canal. 49 caen en el cuadro de corregir. Los otros 7 son las siete palabras de peso 3 del $(7,4)$, con $s^{\prime }=0$: caen en el del bit global, que declara limpios unos bits de información que llegaron con tres errores. De los 70 cuádruples, 56 avisan y 14 pasan: los 14 son las palabras de peso 4, y un error que es palabra de código da síndrome nulo.

El dibujo de la tabla es el de $s_0$. Los pesos pares van a la fila de arriba, y ahí sólo hay dos respuestas: aceptar si el patrón es una palabra, avisar si no. Los impares van a la fila de abajo, y ahí la respuesta es siempre corregir un bit, tenga el patrón uno o siete. Cuánto pesa cada fila en probabilidad, y cuánto le saca el $(8,4)$ al $(7,4)$ con decodificación incompleta, está en en un código perfecto, la bandera no se levanta.

06 · Dónde se termina

La garantía es de peor caso, hasta peso 2. El decodificador no sabe cuántos errores hubo: sabe la paridad. Con $s_0=1$ apuesta a uno, y con tres pierde siempre, en silencio. La apuesta es buena porque con $p$ chico tres errores son mucho menos probables que uno, no porque el código los distinga.

Extender dos veces no da nada. El teorema pide $d$ impar. En un código de distancia par las palabras de peso mínimo ya tienen peso par, reciben un 0 y no cambian. Extendiendo el $(8,4)$ sale un $(9,4)$ con la misma distribución de pesos, $1+14z^4+z^8$, y $d_{\text{min}}=4$: el bit nuevo vale 0 en todas las palabras.

La fila de unos es la más larga del circuito. Cada fila de $H$ es un árbol de XOR con tantas entradas como unos tenga la fila. En el $(8,4)$ las filas de $H_{\text{ext}}$ tienen 4, 4, 4 y 8 unos; en el $(16,11)$, 8, 8, 8, 8 y 16. El árbol de $s_0$ suma todos los bits y fija el camino crítico. Por eso las memorias usan Hsiao, que consigue la misma distancia con filas parejas. Y cuando el largo de la familia no es el que hace falta, se acorta: el código interior del OIF-400ZR es un Hamming extendido acortado, el $(128,119)$.

07 · La decisión en Python

La Figura 3 escrita entera, sobre la $H$ del $(7,4)$ del apunte: $s^{\prime }$ con las tres filas sobre los siete primeros bits, y $s_0$ con los ocho. Como el código es lineal, alcanza con mandar la palabra nula y mirar si vuelve nula. Lo de los comentarios es la salida de correrlo.

from itertools import combinations

H = [[1, 0, 1, 1, 1, 0, 0],          # la H del (7,4) del apunte
     [1, 1, 1, 0, 0, 1, 0],
     [0, 1, 1, 1, 0, 0, 1]]
columnas = [tuple(fila[i] for fila in H) for i in range(7)]

def decidir(r):
    """Los cuatro casos de la Figura 3: r es una lista de 8 bits."""
    s_prima = tuple(sum(f[i] * r[i] for i in range(7)) % 2 for f in H)
    s0 = sum(r) % 2
    if s0 == 0 and not any(s_prima):
        return 'acepta', r
    if s0 == 0:
        return 'bandera', None
    if not any(s_prima):
        return 'paridad', r[:7] + [1 - r[7]]
    i = columnas.index(s_prima)
    return 'corrige', r[:i] + [1 - r[i]] + r[i + 1:]

for w in range(1, 5):
    cuenta = {}
    for pos in combinations(range(8), w):
        r = [1 if i in pos else 0 for i in range(8)]
        caso, v = decidir(r)
        bien = v is not None and not any(v)
        clave = caso + ('' if caso == 'bandera' else (' bien' if bien else ' mal'))
        cuenta[clave] = cuenta.get(clave, 0) + 1
    print(w, cuenta)

# 1 {'corrige bien': 7, 'paridad bien': 1}
# 2 {'bandera': 28}
# 3 {'corrige mal': 49, 'paridad mal': 7}
# 4 {'bandera': 56, 'acepta mal': 14}

columnas.index(s_prima) no falla nunca en el caso de corregir: las siete columnas del $(7,4)$ son todos los vectores no nulos de tres bits, así que todo $s^{\prime }$ no nulo es la columna de alguien. En un extendido acortado eso deja de valer, y un $s^{\prime }$ sin columna también tiene que ir a la bandera.

Para tener a mano

1. Extender es agregar $v_n={\sum }_i{v}_i$: $H_{\text{ext}}$ es $H$ con una columna de ceros y una fila de unos, ec. (7). De $(n,k)$ a $(n+1,k)$.
2. Con $d$ impar, el extendido tiene $d+1$: todas las palabras quedan de peso par. Con $d$ par no cambia nada.
3. Hamming extendido: $(2^m,2^m-1-m,4)$. El $(8,4)$ tiene catorce palabras de peso 4 y una de peso 8, y es auto-dual.
4. $s=(s^{\prime },s_0)$: $s^{\prime }$ es la suma de columnas del Hamming y da la posición; $s_0$ es la suma de todos los bits recibidos y da la paridad del peso del error.
5. Los cuatro casos: nulo, acepta; $s_0$ en 1 y $s^{\prime }$ no nulo, corrige en $s^{\prime }$; $s_0$ en 1 y $s^{\prime }$ nulo, error en el bit global; $s_0$ en 0 y $s^{\prime }$ no nulo, bandera.
6. En el $(8,4)$: corrige los 8 simples, avisa los 28 dobles, corrige mal los 56 triples, y de los 70 cuádruples avisa 56 y deja pasar 14. Correcto garantizado sólo hasta peso 2.