En un código perfecto, la bandera no se levanta

Un código de bloque $(n,k)$ manda $n$ bits por cada $k$ de mensaje. De los $2^n$ vectores posibles, sólo $2^k$ son palabras de código, las que el código declara válidas. El canal le suma a la palabra $v$ un patrón de error $e$, un vector con un 1 en cada posición que se dio vuelta, y llega $r=v+e$. El receptor calcula el síndrome $s=r{H}^T$, que es nulo cuando $r$ es palabra y que depende sólo de $e$, no de lo que se mandó. Con el síndrome busca en una tabla el líder: el patrón de menor peso, o sea con menos unos, entre los que dan ese síndrome. Lo supone como el error, se lo suma a $r$ y entrega.

Cuánto aguanta eso lo fija la distancia mínima $d_{\text{min}}$, la menor cantidad de posiciones en que difieren dos palabras. El decodificador corrige seguro hasta $t=\lfloor (d_{\text{min}}-1)/2\rfloor$ errores, la capacidad de corrección. En el Hamming $(7,4)$ del curso, $d_{\text{min}}=3$ y $t=1$. Con más errores que $t$ el decodificador no se entera: elige un líder liviano, corrige un bit que estaba bien y entrega una palabra equivocada sin avisar a nadie.

01 · La promesa de la bandera

La decodificación incompleta es la respuesta obvia. En vez de tener un líder para cada síndrome y usarlo siempre, corrige sólo cuando el líder pesa $t$ o menos. Para los demás síndromes declara una falla de decodificación: levanta una bandera, y el receptor pide que se retransmita el bloque o lo descarta. Con $\hat{e}$ el líder del síndrome recibido:

$$\hat{v}=\{\begin{array}{ll}r+\hat{e}& \text{si }w(\hat{e})\le t\\ \text{falla}& \text{si }w(\hat{e})>t\end{array}$$

El apunte la presenta con una promesa: así el decodificador nunca entrega en silencio una palabra equivocada por un error de peso alto, sino que avisa. En el $(7,4)$ la bandera no se levanta nunca, con ningún patrón de error. Y en un código que sí le deja lugar, se levanta, pero la promesa tampoco se cumple entera.

02 · Dieciséis esferas que no dejan hueco

Para ver por qué, hay que dibujar alrededor de cada palabra una esfera de radio $t$: el conjunto de los vectores que están a distancia $t$ o menos de ella, o sea que difieren de ella en $t$ posiciones o menos. Lo que cae en la esfera de una palabra se decodifica a esa palabra. En el $(7,4)$, con $t=1$, cada esfera tiene la palabra y sus siete vecinos a un bit: ocho vectores. Las dieciséis esferas juntan $16·8=128$ vectores, y $2^7=128$. No sobra ninguno.

Un código cuyas esferas de radio $t$ cubren todos los vectores sin solaparse es un código perfecto. La misma cuenta, vista desde el receptor: los patrones de peso $t$ o menos tienen todos síndromes distintos —si dos coincidieran, dos esferas se tocarían—, y hay $2^{n-k}$ síndromes. Perfecto es que se los repartan todos:

$$2^{n-k}=\sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right),2^3=1+7$$

En el $(7,4)$, el síndrome nulo y uno por cada error simple. Es la tabla de síndromes del apunte: ocho filas, y ningún líder de peso 2.

Ahí se termina la bandera. La incompleta la levanta cuando el síndrome no tiene ningún líder de peso $t$ o menos, y en un código perfecto ese síndrome no existe. Recorriendo los 127 patrones de error no nulos del $(7,4)$: 7 se corrigen, 0 levantan la bandera y 120 salen con una palabra equivocada, en silencio. Son los mismos 120 en que se equivoca la decodificación completa. En un código perfecto, la incompleta es la completa con otro nombre.

En el $(7,4)$ no hay forma de que aparezca un cuadro con borde de tinta. Probá con dos bits, con tres, con los siete: siempre hay un error simple que explica el síndrome, y el decodificador lo corrige con toda confianza. En el $(8,4)$ la fila de los dobles se marca entera de bandera, y la de los triples entera de rojo.

03 · El (8,4) deja lugar entre las esferas

El Hamming extendido $(8,4)$ es el $(7,4)$ con un octavo bit, la paridad de los otros siete. Toda palabra queda con peso par: catorce de peso 4 y la 1111 1111. La distancia mínima sube a $d_{\text{min}}=4$, pero $t$ no cambia: $\lfloor 3/2\rfloor =1$. Lo que cambia es el espacio. Cada esfera tiene ahora nueve vectores, las dieciséis juntan $16·9=144$, y hay $2^8=256$. Quedan 112 vectores fuera de toda esfera, a distancia 2 o más de todas las palabras. El código dejó de ser perfecto.

Contado en síndromes: de los 16, uno es el nulo, ocho son los de los errores simples y siete no tienen ningún patrón de peso 1. El patrón más liviano de cada uno de esos siete pesa 2, y en cada uno hay cuatro empatados: $7·4=28$, que son todos los dobles. Un decodificador completo tendría que elegir uno de los cuatro y acertaría a uno de cada cuatro dobles. El incompleto no elige: levanta la bandera. Recorriendo los 255 patrones no nulos:

Los 21 dobles del $(7,4)$ salían con tres bits mal; los 28 del $(8,4)$ avisan, los 28. Y avisan también los cuádruples que no son palabra y los séxtuples: 112 banderas, una por cada vector del hueco.

La bandera sale de una cuenta de paridad. Las cuatro filas de la $H$ del $(8,4)$ suman 1111 1111, así que la paridad del síndrome es la paridad de todo lo recibido. Un error simple da un síndrome con una cantidad impar de unos, y se corrige; uno doble da un síndrome no nulo con una cantidad par, y se avisa. En los 256 vectores, la bandera se levanta exactamente cuando $s$ no es nulo y tiene peso par. Es la lógica entera del SEC-DED —corregir uno, detectar dos—, que la Unidad 4 trata como familia.

04 · Lo que compra el bit de más

En probabilidad, sobre el canal binario simétrico que da vuelta cada bit con probabilidad $p$, sumando $p^w{(1-p)}^{n-w}$ sobre cada patrón según lo que hace el decodificador:

En $p={10}^{-2}$, el $(7,4)$ entrega una palabra equivocada sin avisar en 2,03·10⁻³ de los bloques: en todo bloque con dos errores o más. El $(8,4)$, en 5,34·10⁻⁵, unas $3/(8p)$ veces menos, y a cambio pide retransmitir 2,64·10⁻³ de los bloques. Casi todo lo que el $(7,4)$ arruinaba callado, el $(8,4)$ lo avisa. La tasa baja de $4/7$ a $1/2$.

Lo que no compra es corrección. Con decodificación completa, el $(8,4)$ se equivoca exactamente tanto como el $(7,4)$. Un decodificador completo acierta cuando el patrón es líder: en el $(8,4)$, el nulo, los ocho simples y un doble por cada uno de los siete síndromes empatados. Sacando factor común ${(1-p)}^6$:

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

Arriba, la probabilidad de acertar del $(8,4)$; abajo, la del $(7,4)$. Es el mismo polinomio en $p$, para todo $p$. El octavo bit no le agrega al decodificador completo ni un acierto; todo lo que compra es la bandera, y la bandera existe sólo porque el código dejó de ser perfecto.

05 · Lo que la bandera no ve

Que el $(8,4)$ avise tampoco cumple la promesa. La bandera se levanta cuando lo recibido cae fuera de toda esfera, y nada más. Un error triple deja lo recibido a un bit de otra palabra: adentro de una esfera ajena. El decodificador ve un error simple, lo corrige y entrega la palabra equivocada sin avisar. Son 56 patrones; por la misma razón se van los de peso 5 y 7, y las 15 palabras no nulas ni siquiera dan síndrome. En total, 135 de 255 salen mal en silencio, y con $p$ chico los que mandan son los triples, que son los más probables de esos 135.

El apunte lo dice bien cuando describe el modo mixto: un código de distancia $d_{\text{min}}$ puede corregir hasta $\lambda$ errores y detectar hasta $\ell$, con $\lambda <\ell$, si $\lambda +\ell +1\le d_{\text{min}}$. El $(8,4)$ corrige 1 y detecta 2, porque $1+2+1=4$. Detectar 2 no es detectar cualquier error de peso alto: el tercero ya lleva lo recibido al territorio de otra palabra. En el $(7,4)$, con $d_{\text{min}}=3$, corregir uno ya agota la cuenta: no queda ningún $\ell$ mayor que $\lambda =1$.

Y lo del $(7,4)$ vale para todos los perfectos: la repetición de largo impar, todos los Hamming, el Golay $(23,12)$ con sus esferas de radio 3. En cualquiera de ellos, pedir decodificación incompleta no cambia nada. Para que un decodificador pueda avisar, el código tiene que dejar vectores que no sean de ninguna palabra, y eso se paga con redundancia que no corrige nada.