Errores y borrados

Un demodulador que decide bit por bit fuerza un valor aun cuando la muestra cayó pegada al umbral. Si en esos casos dice «no sé», el decodificador recibe tres símbolos: cero, uno y borrado. Un error obliga a averiguar dos cosas, dónde está y cuánto vale. Un borrado sólo una: dónde está ya se sabe. Por eso un borrado cuesta la mitad que un error, y en un código BCH binario se puede aprovechar sin cambiar una sola línea del decodificador.

01 · La cota

Llega una palabra con $\nu$ errores, de posición desconocida, y $ϵ$ borrados, de posición conocida. Un código de distancia mínima $d_{\text{min}}$ recupera la palabra transmitida siempre que

$$2\nu +ϵ+1\le d_{\text{min}}$$

Con $d_{\text{min}}\ge 2t+1$, alcanza con la forma que usa la capacidad de corrección:

$$\nu +\frac{ϵ}{2}\le t$$

Cada borrado gasta media unidad del presupuesto $t$, y cada error una entera. Los casos extremos son los conocidos: sin borrados queda $\nu \le t$, y sin errores se rellenan hasta $d_{\text{min}}-1$ borrados. En el (15,5), con $d_{\text{min}}=7$ y $t=3$, los pares que entran justo son estos:

02 · Por qué un borrado cuesta medio error

La cuenta vale para cualquier código, binario o no. Sean $v$ la palabra transmitida y $E$ el conjunto de las $ϵ$ posiciones borradas.

Paso 1: tachar los borrados. Se borran las posiciones de $E$ en todas las palabras del código. Queda un código de largo $n-ϵ$ y lo recibido, tachado igual, tiene sólo los $\nu$ errores.

Paso 2: tachar cuesta a lo sumo ϵ de distancia. Dos palabras distintas difieren en al menos $d_{\text{min}}$ posiciones, y tachar $ϵ$ les saca a lo sumo $ϵ$ de ellas. El código tachado tiene distancia $\ge d_{\text{min}}-ϵ$.

Paso 3: los ν errores se corrigen ahí. Un código de distancia $d_{\text{min}}-ϵ$ corrige $\nu$ errores si $2\nu +1\le d_{\text{min}}-ϵ$, que es la cota con $ϵ$ pasado al otro lado.

Paso 4: completar es único. Como $ϵ<d_{\text{min}}$, dos palabras del código no pueden coincidir fuera de $E$: la palabra tachada determina la palabra entera.

Un error se paga dos veces porque hay que alejarse de él por los dos lados: la palabra recibida queda a $\nu$ de la transmitida y tiene que quedar a más de $\nu$ de cualquier otra. Un borrado no aleja a lo recibido de nada, porque en esa posición no hay valor que comparar: sólo achica el espacio donde las palabras se distinguen.

03 · El procedimiento de dos pasadas

La prueba de la sección 02 pide decodificar un código tachado, que es otro código para cada $E$. En un código binario no hace falta: el valor de un borrado sólo puede ser 0 o 1, y se prueban los dos rellenos con el decodificador ordinario de errores, el de los síndromes, Berlekamp-Massey y la búsqueda de Chien, sin modificarlo.

Paso 1: rellenar con ceros. Las $ϵ$ posiciones borradas se ponen en 0 y se decodifica. Sale una palabra $v_0$, o el decodificador declara falla.

Paso 2: rellenar con unos. Las mismas posiciones se ponen en 1 y se decodifica de nuevo. Sale $v_1$, o una falla.

Paso 3: elegir. Entre las pasadas que entregaron una palabra, gana la que corrigió menos posiciones fuera de $E$. Una pasada que declaró falla no compite. Si las dos fallan, se declara falla.

Lo que se corrigió adentro de $E$ no cuenta: ahí el relleno fue una apuesta, y que el decodificador la dé vuelta no dice nada sobre el canal. Lo de afuera sí: cada corrección fuera de $E$ es un error que el canal tuvo que cometer para que esa palabra fuera la transmitida.

04 · Por qué una de las dos acierta

Sea ${ϵ}^{\ast }$ la cantidad de posiciones borradas en las que $v$ vale 1.

Paso 1: cuántos errores mete cada relleno. Rellenar con ceros se equivoca justo en esas ${ϵ}^{\ast }$ posiciones, y rellenar con unos en las otras $ϵ-{ϵ}^{\ast }$. Los dos vectores llevan además los $\nu$ errores de afuera: $\nu +{ϵ}^{\ast }$ errores en total con ceros, $\nu +ϵ-{ϵ}^{\ast }$ con unos.

Paso 2: si ϵ* ≤ ϵ/2, acierta la de ceros. Tiene $\nu +{ϵ}^{\ast }\le \nu +ϵ/2\le t$ errores, y el decodificador corrige cualquier patrón de hasta $t$.

Paso 3: si ϵ* > ϵ/2, acierta la de unos. Tiene $\nu +ϵ-{ϵ}^{\ast }<\nu +ϵ/2\le t$.

Las dos pueden acertar a la vez: si ${ϵ}^{\ast }$ queda cerca de la mitad, los dos rellenos tienen a lo sumo $t$ errores. Lo que la prueba garantiza es que nunca fallan las dos.

05 · Por qué el criterio la encuentra

Que una pasada acierte no sirve si no se sabe cuál. Sea la buena la que entrega $v$. Lo que haga la otra tiene tres formas, y el paso 3 tiene que funcionar en las tres.

Paso 1: la buena corrige exactamente ν afuera. Fuera de $E$ lo recibido difiere de $v$ justo en los $\nu$ errores del canal.

Paso 2: si la otra también entrega v, da igual cuál se elija.

Paso 3: si la otra declara falla, no compite. Una falla no corrigió nada, ni adentro ni afuera. Si se la contara como cero correcciones, le ganaría a la buena cada vez que $\nu \ge 1$, y el procedimiento declararía falla con la palabra correcta en la mano. Por eso el paso 3 elige entre las pasadas que entregaron una palabra, y no pasa poco: en el (15,5) la otra pasada falla en uno de cada cuatro casos, como se mide en la sección 06.

Paso 4: si la otra entrega otra palabra w, corrige más afuera. Sea $a$ la cantidad de posiciones que corrigió fuera de $E$. Fuera de $E$, $v$ difiere de lo recibido en $\nu$ posiciones y $w$ en $a$, así que $v$ y $w$ difieren ahí en a lo sumo $\nu +a$. Adentro de $E$ difieren en a lo sumo $ϵ$. Como son dos palabras distintas,

$$d_{\text{min}}\le d(v,w)\le \nu +a+ϵ$$ $$a\ge d_{\text{min}}-ϵ-\nu \ge \nu +1$$

La última desigualdad es la cota. La palabra equivocada corrige afuera por lo menos $\nu +1$ posiciones, una más que la buena, y nunca empata con ella. El margen es $a-\nu \ge d_{\text{min}}-(2\nu +ϵ)$: se achica a medida que la cota se aprieta, y en el borde es uno.

Arranca con un error y dos borrados, lejos del borde. Apostá y decodificá. Después borrá también las posiciones 6 y 8, que en $v$ valen uno, y volvé a apostar; con esa misma palabra, pasá el criterio a «cuenta cero correcciones». Cargá «otra palabra» y mirá cuántas corrige afuera cada pasada. Y al final cargá el borde: los siete borrados caen justo sobre los siete unos de $v$.

06 · Medido en el (15,5)

Con $d_{\text{min}}=7$, la cota pide $2\nu +ϵ\le 6$. Se recorrieron todos los casos: las 32 palabras del código como transmitidas, todos los conjuntos de $ϵ$ borrados y todos los patrones de $\nu$ errores fuera de ellos, con el decodificador de síndromes, Berlekamp-Massey binario y Chien. Son 42 129 pares de patrones por palabra. Agrupados por $2\nu +ϵ$, lo que hace la pasada que no es la buena:

El procedimiento acierta en los 1 348 128. Debajo de $2\nu +ϵ=4$ las dos pasadas tienen a lo sumo tres errores y aciertan siempre las dos. Desde ahí, la otra pasada se equivoca cada vez más: en el total, en 336 896 casos declara falla —uno de cada cuatro— y en 262 920 entrega otra palabra.

Las tres formas del paso 3, medidas una por una:

• Cuando la otra entrega otra palabra, corrige afuera al menos $\nu +1$. El margen más chico que aparece es 3 con $2\nu +ϵ=4$, 2 con 5 y 1 con 6: exactamente $d_{\text{min}}-(2\nu +ϵ)$, la cota del paso 4 alcanzada.
• Con la falla contada como cero correcciones, en los 278 880 casos en que $\nu \ge 1$ y una pasada falla, la falla le gana a la buena. Con $\nu =0$ empatan en cero, y el resultado depende de cómo se rompa el empate.
• Un empate entre dos palabras distintas no aparece ni una vez.

Y la segunda pasada no es un lujo: rellenando sólo con ceros se recupera $v$ en 1 048 220 de los 1 348 128 casos, el 77,8 %. Sólo con unos, en la misma cantidad, porque la palabra de todos unos está en el código y cambia un relleno por el otro.

07 · Un paso más allá

Con $2\nu +ϵ=7$ la cota deja de valer, pero $ϵ$ es impar, así que ${ϵ}^{\ast }$ no puede ser la mitad exacta: uno de los dos rellenos mete a lo sumo $(ϵ-1)/2$ errores y su pasada tiene $\nu +(ϵ-1)/2=3$. Una de las dos acierta siempre. Lo que se cae es el paso 4: el margen $d_{\text{min}}-(2\nu +ϵ)$ llega a cero, y la otra puede entregar una palabra $w$ con las mismas $\nu$ correcciones afuera que la buena.

Eso no es una falla del criterio. Si $v$ y $w$ explican lo recibido con $\nu$ errores cada una y los borrados no dicen nada, no hay dato que las distinga: es la ambigüedad que la cota excluye. Pasa justo cuando $v+w$ es una palabra de peso 7 que cubre los $ϵ$ borrados, los $\nu$ errores y otras $\nu$ posiciones. El (15,5) tiene 15 palabras de peso 7, y la cuenta es cerrada:

$$\text{empates}=32·15·\sum _{2\nu +ϵ=7}\left(\genfrac{}{}{0ex}{}{7}{ϵ}\right)\left(\genfrac{}{}{0ex}{}{7-ϵ}{\nu }\right)$$ $$=32·(15+630+3150+2100)=188640$$

El recorrido da el mismo número. Con $2\nu +ϵ=8$ aparece además lo que la sección 04 excluía: con $ϵ$ par y ${ϵ}^{\ast }=ϵ/2$, los dos rellenos tienen cuatro errores y ninguna pasada acierta. Con el paso 3 tal cual, y un empate entre palabras distintas declarado como falla:

En 7 nada sale mal en silencio: o se entrega $v$, o se sabe que hay dos candidatas igual de buenas. Si el empate se rompe eligiendo la pasada de ceros, como haría un circuito que compara con $\le$, la mitad de los 188 640 sale con la palabra equivocada: 94 320. En 8, un cuarto de los casos entrega otra palabra sin aviso, la misma decodificación errónea que con $t+1$ errores. La cota es exacta en los dos sentidos: adentro no se escapa nada, y en el primer paso afuera ya hay casos que ningún criterio resuelve.

08 · La cuenta en Python

El mismo recorrido, con otro decodificador: uno de tabla, que a cada vector a distancia $\le 3$ de una palabra le asigna esa palabra y declara falla con el resto. No comparte una línea con el decodificador algebraico, y da lo mismo que él en cada fila: la última columna de la sección 06 y las cuatro últimas de la 07. Lo de los comentarios es la salida de correrlo; tarda medio minuto.

from itertools import combinations

n, t = 15, 3
g = 0b10100110111                     # g(X) = 1 + X + X² + X⁴ + X⁵ + X⁸ + X¹⁰

def mul(a, b):                        # producto de polinomios binarios
    r = 0
    while b:
        if b & 1:
            r ^= a
        a, b = a << 1, b >> 1
    return r

C = [mul(m, g) for m in range(32)]    # las 32 palabras del (15,5)
bits = lambda ps: sum(1 << p for p in ps)

# Decodificador de distancia acotada: a cada vector a distancia ≤ t de una
# palabra, esa palabra. Lo que no está en la tabla es una falla declarada.
tabla = {}
for c in C:
    for w in range(t + 1):
        for ps in combinations(range(n), w):
            tabla[c ^ bits(ps)] = c

def dos_pasadas(r, E):
    m = bits(E)
    candidatas = []
    for relleno in (r & ~m, r | m):   # los borrados en cero, después en uno
        w = tabla.get(relleno)
        if w is not None:             # una falla no compite
            candidatas.append((bin((w ^ r) & ~m).count('1'), w))
    if not candidatas:
        return 'falla'
    candidatas.sort()
    if len(candidatas) == 2 and candidatas[0][0] == candidatas[1][0] \
            and candidatas[0][1] != candidatas[1][1]:
        return 'empate'
    return candidatas[0][1]

for s in range(9):                    # s = 2ν + ϵ
    cuenta = {'v': 0, 'otra': 0, 'empate': 0, 'falla': 0}
    for nu in range(s // 2 + 1):
        for E in combinations(range(n), s - 2 * nu):
            afuera = [i for i in range(n) if i not in E]
            for errores in combinations(afuera, nu):
                e = bits(errores)
                for v in C:
                    x = dos_pasadas(v ^ e, E)
                    clase = 'v' if x == v else x if isinstance(x, str) else 'otra'
                    cuenta[clase] += 1
    print(s, sum(cuenta.values()), cuenta)
# 0 32 {'v': 32, 'otra': 0, 'empate': 0, 'falla': 0}
# 1 480 {'v': 480, 'otra': 0, 'empate': 0, 'falla': 0}
# 2 3840 {'v': 3840, 'otra': 0, 'empate': 0, 'falla': 0}
# 3 21280 {'v': 21280, 'otra': 0, 'empate': 0, 'falla': 0}
# 4 90720 {'v': 90720, 'otra': 0, 'empate': 0, 'falla': 0}
# 5 314496 {'v': 314496, 'otra': 0, 'empate': 0, 'falla': 0}
# 6 917280 {'v': 917280, 'otra': 0, 'empate': 0, 'falla': 0}
# 7 2302560 {'v': 2113920, 'otra': 0, 'empate': 188640, 'falla': 0}
# 8 5054400 {'v': 2376360, 'otra': 1292760, 'empate': 619200, 'falla': 766080}

Las dos líneas que hacen al paso 3 son if w is not None, que deja afuera a la pasada que falla, y la que declara empate cuando las dos candidatas son palabras distintas con el mismo número de correcciones afuera. La máscara ~m es lo que cuenta sólo fuera de los borrados.

Para tener a mano

1. $2\nu +ϵ+1\le d_{\text{min}}$, o $\nu +ϵ/2\le t$: un borrado cuesta medio error. En el (15,5): (0,6), (1,4), (2,2), (3,0).
2. Por qué: tachar los $ϵ$ borrados baja la distancia a lo sumo $ϵ$, y el código tachado corrige $\nu$ si $2\nu +1\le d_{\text{min}}-ϵ$.
3. Dos pasadas: borrados en ceros, borrados en unos, el decodificador ordinario en cada una. Gana la que corrigió menos posiciones fuera de los borrados; una pasada que falla no compite.
4. Una acierta: con ${ϵ}^{\ast }$ unos entre los borrados, los rellenos meten ${ϵ}^{\ast }$ y $ϵ-{ϵ}^{\ast }$ errores, y uno de los dos es $\le ϵ/2$.
5. El criterio la encuentra: la buena corrige $\nu$ afuera; otra palabra corrige $\ge d_{\text{min}}-ϵ-\nu \ge \nu +1$; una falla no tiene palabra.
6. En el (15,5), todos los casos con $2\nu +ϵ\le 6$: 1 348 128 de 1 348 128. La otra pasada falla en 336 896 y da otra palabra en 262 920. Sólo ceros: 77,8 %.
7. En $2\nu +ϵ=d_{\text{min}}$ una pasada acierta siempre, pero hay empates genuinos: 188 640, el 8,2 %, contados por las 15 palabras de peso 7. En 8, el 25,6 % sale como otra palabra.