La distancia mínima

Un código sirve si sus palabras están lejos unas de otras: para que el canal convierta una en otra tiene que dar vuelta muchos bits a la vez. La distancia mínima mide cuán lejos están las dos más cercanas, y de ese solo número salen cuántos errores se detectan y cuántos se corrigen con garantía.

01 · Peso y distancia

El peso de Hamming de un vector $v$ de $V_n$, $w(v)$, es la cantidad de componentes no nulas. La distancia de Hamming entre dos vectores, $d(u,v)$, es la cantidad de posiciones en que difieren. Las dos se tocan en una identidad:

$$d(u,v)=w(u+v)$$

La suma módulo 2 pone un 1 exactamente donde los dos vectores difieren. Con dos palabras del $(7,4)$: 1000 110 y 0100 011 suman 1100 101, de peso 4, y difieren en cuatro posiciones.

La distancia es una métrica de verdad: no es negativa, es simétrica, vale cero sólo entre un vector y sí mismo, y cumple la desigualdad triangular, $d(u,v)+d(v,x)\ge d(u,x)$. Por eso vale la imagen que se usa todo el tiempo: los $2^n$ vectores son los vértices de un hipercubo de $n$ dimensiones, la distancia es la cantidad de aristas para ir de uno a otro, y las palabras de código son un subconjunto de vértices que conviene tener separados.

02 · La distancia mínima es el peso mínimo

La distancia mínima de un código $C$ es la menor distancia entre dos palabras distintas:

$$d_{\text{min}}=min\{d(v,x):v,x\in C,v\ne x\}$$

Es tan central que un código se nombra por la terna $(n,k,d_{\text{min}})$. Por la definición hay que comparar todos los pares: en el $(7,4)$ son $\left(\genfrac{}{}{0ex}{}{16}{2}\right)=120$. Contados uno por uno, 56 pares están a distancia 3, 56 a distancia 4 y 8 a distancia 7. En un código lineal alcanza con mucho menos: si $w_{\text{min}}$ es el menor peso de las palabras no nulas,

$$d_{\text{min}}=w_{\text{min}}$$

Paso 1: cada distancia es un peso. Por la identidad de arriba, $d(v,x)=w(v+x)$, y como el código es lineal, $v+x$ es otra palabra, no nula porque $v\ne x$.

Paso 2: cada peso es una distancia. El peso de una palabra no nula $v$ es su distancia a la palabra nula, $w(v)=d(v,0)$, y la nula está en todo código lineal.

Paso 3: mismos conjuntos, mismo mínimo. Los números sobre los que se toman los dos mínimos coinciden, así que los mínimos coinciden.

El costo pasa de los pares a las palabras: 15 pesos en vez de 120 comparaciones. Sigue siendo exponencial en $k$, y hay un camino mejor, que mira la matriz de paridad en vez de las palabras. La misma cuenta dice algo más: vistas desde cualquier palabra, las demás están a las mismas distancias que vistas desde la nula. Por eso las 120 distancias son los 15 pesos vistos desde cada una de las 16 palabras, con cada par contado dos veces: los 56 pares a distancia 3 son $16·7/2$. En un código lineal ninguna palabra está peor rodeada que otra.

03 · La distribución de pesos

$d_{\text{min}}$ es el primer peso no nulo, pero para calcular probabilidades hace falta saber cuántas palabras hay de cada peso. La distribución de pesos es la lista $A_0,A_1,\dots ,A_n$, con $A_i$ la cantidad de palabras de peso $i$. Siempre $A_0=1$ y ${\sum }_i{A}_i=2^k$, y se la junta en el polinomio enumerador $A(z)={\sum }_i{A}_i{z}^i$.

El $(7,4)$ es el de la Tabla 1 del apunte, con $A(z)=1+7z^3+7z^4+z^7$. El $(8,4)$ es el mismo con un bit más de paridad global, que vuelve par toda palabra: las de peso 3 pasan a 4, las de peso 4 se quedan, y la distancia mínima sube a 4.

Lo que importa del primer coeficiente no nulo es su tamaño. Sobre el BSC con probabilidad de bit $p$ chica, un patrón de error pasa inadvertido sólo si es una palabra, y la cuenta la dominan las más livianas: $P_u\approx A_{d_{\text{min}}}{p}^{d_{\text{min}}}$. En el $(7,4)$, $7p^3$; con $p={10}^{-2}$ la cuenta exacta da $\mathrm{6,79}·{10}^{-6}$. Dos códigos con la misma $d_{\text{min}}$ pueden diferir en ese coeficiente, y la distancia mínima sola no lo ve.

Calcular la distribución de un código grande es difícil en general. La identidad de MacWilliams la saca de la del código dual, que conviene cuando el dual tiene pocas palabras.

04 · La distancia mínima, leída en las columnas de H

Con $H=[h_0{h}_1\cdots h_{n-1}]$ escrita por columnas, el producto $v{H}^T$ es la suma de las columnas donde $v$ tiene un 1, y $v$ es palabra si y sólo si esa suma da cero. Juntando las dos cosas:

Hay una palabra de peso $w$ con unos en las posiciones $i_1,\dots ,i_w$ si y sólo si $h_{i_1}+\cdots +h_{i_w}=0$. Entonces $d_{\text{min}}$ es la menor cantidad de columnas de $H$ que suman cero, o sea, que son linealmente dependientes: sobre $\mathrm{GF}(2)$ los únicos coeficientes no nulos son unos, y «dependientes» es «alguna suma da cero». Y hay más: la cantidad de conjuntos de $w$ columnas que suman cero es exactamente $A_w$, porque cada conjunto es una palabra.

De ahí salen dos criterios que se aplican mirando:

• $d_{\text{min}}\ge 2$ si y sólo si ninguna columna es nula. Una columna nula $h_i$ es, sola, una palabra de peso 1.
• $d_{\text{min}}\ge 3$ si y sólo si, además, las columnas son distintas dos a dos. Dos iguales suman cero y dan una palabra de peso 2.

Las siete columnas de la $H$ del $(7,4)$ son 110 011 111 101 100 010 001: los siete vectores no nulos de $V_3$, todos distintos. Entonces $d_{\text{min}}\ge 3$. Y no puede ser más, porque con todos los no nulos de $V_3$ presentes, la suma de dos columnas cualesquiera es otra columna: $h_0+h_1=101=h_3$, y la palabra con unos en 0, 1 y 3 es 1101 000.

El criterio también sirve para diseñar. Un código con $d_{\text{min}}\ge 3$ y $n-k$ bits de paridad es una elección de $n$ columnas distintas y no nulas de $V_{n-k}$, y como hay $2^{n-k}-1$, el largo queda acotado: $n\le 2^{n-k}-1$. Usarlas todas es la familia de Hamming. Para llegar a 4 hace falta que tampoco sume cero ninguna terna. Las ocho columnas del $(8,4)$ son 1101 0111 1110 1011 1000 0100 0010 0001, todas de peso impar, y tres vectores de peso impar suman uno de peso impar, que nunca es cero.

Una columna sola no da cero, y dos tampoco: el widget lo dice en cuanto lo probás, y son los dos criterios de recién. En el $(7,4)$ la primera terna que suma cero aparece enseguida; hay siete, una por cada palabra de peso 3. Elegir las siete columnas también da cero: es 1111 111. En el $(8,4)$ ninguna terna sirve, por la paridad de los pesos, y el conjunto más chico tiene cuatro columnas: hay catorce, una por cada palabra de peso 4.

05 · Detectar: hasta d_min − 1

El receptor detecta un error cuando lo recibido no es palabra, o sea cuando el síndrome no es nulo. El error pasa inadvertido sólo si el patrón $e$ es él mismo una palabra no nula, y ninguna pesa menos que $d_{\text{min}}$:

$$\text{se detectan todos los patrones de hasta }{d}_{\text{min}}-1\text{ errores}$$

Es una garantía de peor caso. Por encima de $d_{\text{min}}-1$ no se promete nada, pero casi todo se detecta igual: de los $2^n-1$ patrones no nulos se escapan sólo los $2^k-1$ que son palabras. En el $(7,4)$, 15 de 127, y cuáles son lo cuenta un síndrome cero no prueba nada.

06 · Corregir: t y las esferas

Corregir pide más que detectar: hay que saber qué palabra se mandó. Alrededor de cada palabra se traza una esfera de radio $t$, los vectores a distancia $\le t$ de ella. Si las esferas no se tocan, todo vector recibido con $t$ errores o menos cae en la esfera de la palabra transmitida y en ninguna otra, y el decodificador la identifica sin ambigüedad.

Paso 1: si se tocan, las palabras están cerca. Si $r$ está en las esferas de $v_1$ y de $v_2$, la desigualdad triangular da $d(v_1,v_2)\le d(v_1,r)+d(r,v_2)\le 2t$.

Paso 2: y al revés. Si dos palabras están a $d_{\text{min}}\le 2t$, dando vuelta en la primera $t$ de las posiciones en que difieren se llega a un vector que está a $\le t$ de las dos.

Paso 3: la condición. Las esferas no se tocan si y sólo si $2t<d_{\text{min}}$, y el mayor $t$ que lo cumple es la capacidad de corrección:

$$t=\lfloor \frac{d_{\text{min}}-1}{2}\rfloor$$

El $(7,4)$ y el $(8,4)$ tienen los dos $t=1$: el bit que el $(8,4)$ agrega no corrige nada más. Lo que cambia es el espacio que dejan las esferas. En el $(7,4)$ cada una tiene $1+7=8$ vectores, y las 16 juntan 128: todo $V_7$, sin hueco. Es un código perfecto. En el $(8,4)$ cada esfera tiene 9 y las 16 juntan 144 de los 256. Los otros 112 no están en ninguna: cada uno está a distancia 2 de exactamente cuatro palabras. Con $d_{\text{min}}$ par sobra siempre esa capa de vectores equidistantes, y sirve para detectar.

07 · Los modos de operación

Detectar y corregir se reparten la misma $d_{\text{min}}$. El decodificador del modo mixto corrige si lo recibido cae a distancia $\le \lambda$ de alguna palabra y, si no, levanta una bandera. Así corrige hasta $\lambda$ errores y detecta, sin corregir mal, hasta $\ell$, con $\ell \ge \lambda$, siempre que

$$\lambda +\ell +1\le d_{\text{min}}$$

Paso 1: hasta λ errores, corrige. Como $\ell \ge \lambda$, la condición implica $2\lambda +1\le d_{\text{min}}$, o sea $\lambda \le t$: las esferas de radio $\lambda$ no se tocan, y lo recibido cae sólo en la de la palabra transmitida.

Paso 2: entre λ + 1 y ℓ errores, avisa. Lo recibido $r$ está a más de $\lambda$ de la palabra transmitida $v$. Y de cualquier otra palabra $x$, por la desigualdad triangular, $d(r,x)\ge d(v,x)-d(v,r)\ge d_{\text{min}}-\ell \ge \lambda +1$. No cae en ninguna esfera de radio $\lambda$, y el decodificador levanta la bandera en vez de corregir hacia otra palabra.

Los dos modos puros son los extremos. Con $\lambda =0$ no se corrige nada y se detecta hasta $\ell =d_{\text{min}}-1$: es la sección 05. Con $\lambda =\ell =t$ se corrige todo lo que se puede y no se detecta nada más allá: es la sección 06. En el medio, cada error más que se corrige es uno menos que se detecta con garantía. Los pares $(\lambda ,\ell )$ que no se pueden mejorar en ninguna de las dos coordenadas:

Con $d_{\text{min}}$ par el modo de corrección ya trae detección gratis: el $(8,4)$ corrige 1 y detecta 2, y eso es la capa de 112 vectores de la sección anterior. El modo mixto es el que se usa cuando hay canal de retorno: los errores leves se corrigen en el momento y los graves se mandan a retransmitir. El decodificador que lo implementa con $\lambda =t$ es la decodificación incompleta.

08 · Dónde se termina la garantía

La condición dice qué pasa hasta $\ell$ errores y nada más. Un error de más y el decodificador puede corregir mal sin avisar. Transmitiendo la palabra nula por el $(8,4)$ en el modo $(\lambda ,\ell )=(1,2)$ y barriendo los 256 patrones de error, por peso: cuántos corrige bien, en cuántos avisa, cuántos corrige hacia otra palabra y cuántos no ve.

Hasta dos errores la garantía se cumple entera. Con tres se rompe entera: los 56 patrones de peso 3 quedan a distancia 1 de una palabra de peso 4, el decodificador los «corrige» hacia ella y entrega una palabra equivocada sin bandera. Con cuatro vuelve a avisar en 56, y los 14 que son palabras pasan sin que el síndrome los vea.

El $(7,4)$ lo muestra con un error menos. Su único modo que corrige es $(1,1)$, sin margen para detectar, y los 21 patrones dobles se corrigen mal: con dos errores el decodificador empeora. Por eso en un código perfecto la bandera no tiene dónde levantarse: en un código perfecto la bandera no se levanta.

09 · La cuenta en Python

La búsqueda del widget, escrita entera: recorre los conjuntos de columnas por tamaño creciente y devuelve el primero que suma cero. Las $H$ son la del apunte para el $(7,4)$ y la del $(8,4)$ en la misma forma $[P^{T}I]$. Lo de los comentarios es la salida de correrlo.

from itertools import combinations

def dmin_por_columnas(H):
    """La menor cantidad de columnas de H que suman cero, y cuáles."""
    m, n = len(H), len(H[0])
    columnas = [tuple(fila[i] for fila in H) for i in range(n)]
    for w in range(1, n + 1):
        for elegidas in combinations(range(n), w):
            suma = [sum(columnas[i][j] for i in elegidas) % 2 for j in range(m)]
            if not any(suma):
                return w, elegidas

H74 = [[1, 0, 1, 1, 1, 0, 0],
       [1, 1, 1, 0, 0, 1, 0],
       [0, 1, 1, 1, 0, 0, 1]]
H84 = [[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, 0, 1, 0, 0, 0, 1]]

print(dmin_por_columnas(H74))   # (3, (0, 1, 3))
print(dmin_por_columnas(H84))   # (4, (0, 1, 2, 5))

Recorre ${\sum }_{w=1}^{d_{\text{min}}}\left(\genfrac{}{}{0ex}{}{n}{w}\right)$ conjuntos en el peor caso: depende de $n$ y de $d_{\text{min}}$, no de $k$. En el $(7,4)$ no gana nada: hasta 3 columnas son 63 conjuntos contra 16 palabras. Gana cuando $k$ es grande y $d_{\text{min}}$ chica: en el Hamming $(255,247)$, hasta 3 columnas son 2.763.775 conjuntos, y las palabras son $2^{247}\approx \mathrm{2,26}·{10}^{74}$. Con $d_{\text{min}}$ grande deja de servir: el problema general es difícil, y por eso las familias de las unidades que siguen se construyen para que $d_{\text{min}}$ se sepa de antemano.

Para tener a mano

1. $d(u,v)=w(u+v)$, y en un código lineal $d_{\text{min}}=w_{\text{min}}$: el menor peso de una palabra no nula.
2. $d_{\text{min}}$ es la menor cantidad de columnas de $H$ que suman cero. Ninguna nula da $\ge 2$; además distintas, $\ge 3$. Los conjuntos de $w$ columnas que suman cero son $A_w$.
3. $(7,4)$: $A(z)=1+7z^3+7z^4+z^7$, $d_{\text{min}}=3$. $(8,4)$: $1+14z^4+z^8$, $d_{\text{min}}=4$: sus columnas son todas de peso impar, y ninguna terna suma cero.
4. Detecta hasta $d_{\text{min}}-1$; corrige hasta $t=\lfloor (d_{\text{min}}-1)/2\rfloor$, que es la condición para que las esferas de radio $t$ no se toquen.
5. Modo mixto: corrige $\lambda$ y detecta $\ell \ge \lambda$ si $\lambda +\ell +1\le d_{\text{min}}$. Los modos puros son $\lambda =0$ y $\lambda =\ell =t$.
6. Las garantías son de peor caso, hacia los dos lados: casi todo lo que pasa de $d_{\text{min}}-1$ se detecta igual, y un error más que $\ell$ puede corregirse mal y en silencio.
7. La probabilidad de que un error pase la decide $A_{d_{\text{min}}}$ además de $d_{\text{min}}$: $P_u\approx A_{d_{\text{min}}}{p}^{d_{\text{min}}}$.