El intercalado

Todos los códigos de la unidad se diseñan contra errores sueltos: cada símbolo se equivoca por su cuenta. Los canales reales se equivocan de a muchos seguidos. El intercalado no cambia el código ni le agrega redundancia: cambia el orden en que sus símbolos pasan por el canal, para que una ráfaga llegue a cada palabra como unos pocos errores sueltos.

01 · Las ráfagas

El canal binario simétrico invierte cada bit con probabilidad $p$, independiente de lo que pasó con el anterior. Describe bien un canal dominado por ruido térmico. No describe un desvanecimiento en un enlace de radio, una rayadura en un disco, un transitorio de conmutación o una no linealidad en la fibra: ahí, si un símbolo salió mal, es probable que el siguiente también. El canal tiene memoria, y los errores llegan agrupados.

Una ráfaga de longitud $b$ es un tramo de $b$ símbolos consecutivos del canal donde caen los errores. Contra un código $(n,k)$ con capacidad de corrección $t$, lo que importa no es cuántos errores hay sino cómo se reparten. Con el Hamming (7,4), que corrige $t=1$, una ráfaga de 3 que cae entera en una palabra la arruina; los mismos 3 errores, uno en cada una de tres palabras, se corrigen los tres. El problema es la concentración.

Hay códigos diseñados para corregir ráfagas. La solución que domina en la práctica es otra: no tocar el código y transformar el canal.

02 · El intercalador de bloque

Un intercalador de bloque de profundidad $\lambda$ junta $\lambda$ palabras de código de largo $n$ en un arreglo de $\lambda$ filas por $n$ columnas, una palabra por fila, y lo transmite leyéndolo por columnas: primero el símbolo 0 de las $\lambda$ palabras, después el símbolo 1 de todas, y así. Con $v_i$ la palabra de la fila $i$, su símbolo $j$ viaja en la ranura

$$\tau =j\lambda +i,0\le i<\lambda ,0\le j<n$$

El desintercalador hace la inversa: escribe por columnas los $\lambda n$ símbolos que llegan y entrega las filas al decodificador, en el orden original. Entre los dos, el decodificador ve las mismas palabras de siempre; sólo el canal vio otro orden.

El ejemplo del apunte es el (7,4) con $\lambda =4$: un arreglo de 4 × 7 que sale al canal como 28 símbolos. Una ráfaga de 7 que arranca en la ranura 2 toca las ranuras 2 a 8, que son de las palabras 2, 3, 0, 1, 2, 3, 0. Desintercalado, deja 2, 1, 2 y 2 errores en $v_0$ a $v_3$. Sin intercalar, la misma ráfaga sobre las mismas 28 posiciones deja 5 en una palabra y 2 en la siguiente.

03 · Por qué cada palabra recibe ⌈b/λ⌉

Paso 1: las ranuras recorren las filas en ciclo. La ranura $\tau$ es de la palabra $i=\tau mod\lambda$. Dos ranuras consecutivas son de filas consecutivas, y la sucesión de filas se repite con período $\lambda$.

Paso 2: en $\lambda$ ranuras seguidas hay una de cada palabra. Cualquier tramo de $\lambda$ ranuras consecutivas recorre los $\lambda$ restos módulo $\lambda$ una vez cada uno, empiece donde empiece. Dentro del mismo arreglo eso es una ranura por palabra; si el tramo cruza al arreglo siguiente, las ranuras del final y las del principio son de palabras distintas, y la cuenta por palabra sólo puede bajar.

Paso 3: se cortan las $b$ ranuras en tramos de $\lambda$. Una ráfaga de $b$ ranuras se parte en $\lceil b/\lambda \rceil$ tramos de a lo sumo $\lambda$. Cada tramo le aporta a una palabra a lo sumo un error:

$$\text{errores en cada palabra}\le \lceil \frac{b}{\lambda }\rceil$$

Y de ahí el corolario: si $b\le \lambda t$, cada palabra recibe a lo sumo $t$ errores y el decodificador de siempre corrige la ráfaga entera. La cota es justa: una ráfaga de $\lambda t+1$ que arranca en la ranura 0 toca $v_0$ en las ranuras $0,\lambda ,\dots ,\lambda t$, que son $t+1$. La profundidad se elige entonces por la ráfaga más larga que se espera del canal: $\lambda \ge b_{\text{máx}}/t$.

El conjunto de los arreglos transmitidos es otro código lineal, de parámetros $(\lambda n,\lambda k)$: la misma tasa y la misma distancia mínima $d_{\text{min}}$ que el original, porque cada arreglo son $\lambda$ palabras del original, y el de menor peso no nulo es una sola de ellas con las demás en cero. El intercalado no agrega redundancia: reordena.

04 · En Python, y la trampa del reshape

Con numpy, intercalar es transponer y aplanar. Desintercalar es la inversa, y ahí está la trampa: reshape llena por filas, así que el flujo hay que cortarlo en $n$ tramos de $\lambda$ —uno por columna del arreglo— y recién después transponer:

import math
import numpy as np

def intercalar(palabras):
    """λ palabras, una por fila (λ × n) → el flujo leído por columnas."""
    return palabras.T.flatten()

def desintercalar(flujo, lam, n):
    """La inversa: se escribe por columnas y se lee por filas."""
    return flujo.reshape(n, lam).T

def errores_por_palabra(lam, n, b, inicio):
    e = np.zeros(lam * n, dtype=np.uint8)
    e[inicio:inicio + b] = 1          # la ráfaga, en el canal
    return desintercalar(e, lam, n).sum(axis=1)

lam, n, b = 4, 7, 7
print(errores_por_palabra(lam, n, b, 2).tolist())
# [2, 1, 2, 2]
peor = max(errores_por_palabra(lam, n, b, i).max() for i in range(lam * n - b + 1))
print(int(peor), math.ceil(b / lam))
# 2 2

e = np.zeros(lam * n, dtype=np.uint8)
e[2:2 + b] = 1
print(e.reshape(lam, n).sum(axis=1).tolist())     # sin la transpuesta
# [5, 2, 0, 0]

La última línea es el error que da reshape(lam, n) sin transponer: vuelve a cortar el flujo en tramos consecutivos de $n$, que es exactamente no haber intercalado, y la ráfaga queda amontonada en una palabra. El peor caso sobre las 22 posiciones de arranque posibles es 2, que es $\lceil 7/4\rceil$.

05 · Lo que cuesta el de bloque

Las ventajas se pagan en memoria y en retardo. El apunte cuenta el arreglo entero, $\lambda n$ símbolos en cada extremo, y un retardo del orden de $2\lambda n$. El mínimo exacto sale de un modelo explícito: entra un símbolo por tiempo de símbolo, sale uno por tiempo de símbolo, y nada sale antes de haber llegado.

Paso 1: cuándo llega cada símbolo. Contando desde el principio del arreglo, el símbolo $j$ de $v_i$ llega en el instante $in+j$.

Paso 2: cuándo puede salir. Si el canal arranca en $D_{\text{tx}}$, ese símbolo sale en $D_{\text{tx}}+j\lambda +i$. Tiene que ser después de haber llegado para todo $i$ y todo $j$:

$$D_{\text{tx}}\ge \underset{i,j}{máx}[i(n-1)-j(\lambda -1)]=(\lambda -1)(n-1)$$

El peor es $i=\lambda -1$, $j=0$: la primera columna necesita el primer símbolo de la última palabra.

Paso 3: el receptor, al revés. El desintercalador tiene que entregar en orden, y el que más se hace esperar es el último símbolo de la primera palabra, que viaja en la última columna. Por la misma cuenta agrega otros $(\lambda -1)(n-1)$, y el retardo mínimo de punta a punta es

$$D_{\text{bloque}}=2(\lambda -1)(n-1)$$

Paso 4: la memoria. En cada extremo entra un símbolo y sale uno por tiempo de símbolo, corridos $(\lambda -1)(n-1)$: adentro hay siempre esa cantidad. Contado con un modelo de eventos —cada símbolo ocupa una celda desde que llega hasta que sale, arreglo tras arreglo— da eso mismo, en régimen y en los dos extremos. En el (7,4) con $\lambda =4$ son 18 símbolos por extremo y 36 de retardo, contra los 28 y 56 de contar el arreglo entero. Implementado como un arreglo que se llena y se vacía, se reservan los $\lambda n$; los 18 son el piso.

06 · El intercalador convolucional

El intercalador convolucional evita el arreglo y trabaja sobre un flujo continuo. Tiene $\lambda$ ramas, que son líneas de retardo de $0,J,2J,\dots ,(\lambda -1)J$ celdas, y dos conmutadores sincronizados que las recorren en ciclo, una rama por símbolo. El símbolo $t$ de la entrada entra por la rama $tmod\lambda$. Esa rama avanza una celda cada vez que el conmutador vuelve a ella, o sea cada $\lambda$ símbolos, así que el símbolo sale al canal en

$$\tau (t)=t+(tmod\lambda )J\lambda$$

Con λ = 4 y J = 2: las dos mitades tienen las ramas en orden inverso, y cada símbolo pasa por (λ − 1)J = 6 celdas de su rama.

El retardo es el mismo para todos. El desintercalador tiene las mismas ramas en orden inverso: la rama $i$ retarda $(\lambda -1-i)J$ celdas. Un símbolo de la rama $i$ espera $iJ\lambda$ instantes de un lado y $(\lambda -1-i)J\lambda$ del otro, y en total

$$D_{\text{conv}}=(\lambda -1)J\lambda$$

sea cual sea su rama. Por eso a la salida el flujo vuelve al orden original, entero, con un corrimiento fijo.

La memoria es la suma de las ramas. En cada extremo,

$$M_{\text{conv}}=J(0+1+\cdots +\lambda -1)=\frac{J\lambda (\lambda -1)}{2}$$

celdas, que están siempre llenas. Y emite un símbolo por cada símbolo que recibe desde el primer instante: no hay arreglo que llenar. Lo que sí hay que decidir es $J$, y de eso depende todo lo que sigue. Probalo abajo: con el (7,4) y $\lambda =4$, mirá qué ráfaga aguanta con $J=1$ y con $J=2$.

Con $\lambda =1$ el canal lleva las palabras enteras, una detrás de otra, y la ráfaga de 3 cae en una sola. Subí $\lambda$ a 4: cada renglón del canal pasa a alternar las cuatro palabras, y para dejar dos errores en una hace falta una ráfaga de 5. Arrastrala —o movela con las flechas— y buscá dónde duele. En el convolucional, con el mismo $\lambda$, el número de abajo es la ráfaga más larga que se corrige en cualquier lugar del flujo; con $J$ chico se derrumba. Con el (8,4) y $\lambda =4$, poné $J=2$ y prendé «palabras corridas».

07 · Cuándo cuesta la mitad

El apunte y la filmina dicen que, a igual capacidad de dispersar ráfagas, el convolucional usa aproximadamente la mitad de memoria y la mitad de retardo que el de bloque equivalente. Para medirlo hay que fijar qué es «equivalente». Acá: la misma profundidad $\lambda$, y el $J$ más chico con el que el convolucional corrige, como el de bloque, toda ráfaga de hasta $\lambda t$ en cualquier lugar del flujo. El modelo: palabras de $n$ símbolos consecutivos de la entrada, el símbolo $t$ sale en $\tau (t)$, y se cuenta cuántos errores le deja a cada palabra una ráfaga en cada posición del canal, ya en régimen.

El J mínimo. Barriendo $n\in \{5,7,8,12,15,16,24\}$, $t\le 3$ y $\lambda$ de 2 a 8, el $J$ mínimo es, en todos los casos,

$$J=\lceil \frac{n}{\lambda }\rceil$$

si la primera palabra entra por la rama 0, y si no,

$$J=\lceil \frac{n+1}{\lambda }\rceil$$

Con ese $J$, los símbolos de una misma palabra quedan en el canal a $\lambda$ ranuras o más unos de otros, como en el de bloque. Un $J$ menos y la garantía se derrumba: el (15,11) con $\lambda =5$ y $J=2$ ya no aguanta ni una ráfaga de 2, y el Golay (24,12), con $t=3$, $\lambda =7$ y $J=3$, corrige hasta 15, no hasta 21. Si $\lambda$ no divide a $n$, las palabras arrancan en todas las ramas por turno y las dos fórmulas dan lo mismo. Si lo divide, todas arrancan en la misma rama, y que sea la 0 vale una celda por rama: corrido un símbolo, el (15,11) con $\lambda =5$ y $J=3$ vuelve a no aguantar una ráfaga de 2, y necesita $J=4$.

La razón. Con el de bloque en su mínimo, memoria y retardo dan la misma razón, porque los dos lados escalan igual:

$$\frac{M_{\text{conv}}}{M_{\text{bloque}}}=\frac{D_{\text{conv}}}{D_{\text{bloque}}}=\frac{J\lambda (\lambda -1)/2}{(\lambda -1)(n-1)}=\frac{J\lambda }{2(n-1)}$$

Como $J\lambda \ge n$, la razón es por lo menos $n/2(n-1)$: siempre un poco más que la mitad, y tiende a la mitad cuando $\lambda$ divide a $n$, las palabras entran alineadas con la rama 0 y $n$ es largo. Medidas con el modelo de eventos —las ocupaciones y los retardos, no las fórmulas—:

La última columna compara contra la cuenta del apunte, el arreglo entero: $\lambda n$ por extremo y $2\lambda n$ de retardo. Contra eso la razón es $(\lambda -1)J/2n$, y queda por debajo de la mitad cuando $J\lambda =n$. La fila del Golay con $\lambda =8$ corrige 25, uno más que los $\lambda t=24$ del de bloque: cada palabra tiene sólo 3 símbolos por rama.

Así que la afirmación vale en su versión aproximada, y con condiciones: que $\lambda$ divida a $n$, que las palabras entren alineadas con la rama 0, y palabras largas. El (128,119) con $\lambda =16$ está en 0,504. Cuando $\lambda$ no divide a $n$, $J$ se redondea para arriba y la razón sube: el (7,4) con $\lambda =4$ cuesta dos tercios. Y con las palabras corridas, el (15,11) con $\lambda =5$ necesita $J=4$ y cuesta 20/28 = 0,714.

08 · Sin fronteras de bloque

El de bloque tiene fronteras: el desintercalador tiene que saber dónde empieza cada arreglo, y desalineado un solo símbolo mezcla palabras y su salida no sirve. Hay $\lambda n$ alineaciones posibles y una sola es la buena. El convolucional no tiene arreglos: el desintercalador sólo necesita saber en qué rama está el conmutador, una referencia de fase entre $\lambda$ posibles. Del lado del transmisor, la sección anterior agrega una condición barata, porque codificador e intercalador están en el mismo lugar: hacer que cada palabra arranque en la rama 0.

09 · Lo que el intercalado no hace

No corrige más errores sueltos. El código intercalado tiene la misma $d_{\text{min}}$ y la misma tasa que el original. Sobre un canal sin memoria, reordenar no cambia nada: un canal que se equivoca en cada símbolo por su cuenta lo sigue haciendo en cualquier orden.

La garantía es para una ráfaga. Dos ráfagas cortas en el mismo arreglo suman. En el (7,4) con $\lambda =4$, una ráfaga en las ranuras 0 y 1 y otra en la 4 y la 5 dejan dos errores en $v_0$ y dos en $v_1$, aunque cada una por separado medía 2, la mitad de lo que el arreglo aguanta.

Y se paga en retardo. La profundidad sale de la ráfaga más larga del canal, $\lambda \ge b_{\text{máx}}/t$, y el retardo crece con $\lambda n$. En muchos sistemas es esa latencia, y no la capacidad de corrección, lo que fija el diseño. El convolucional la recorta, pero no la saca.

El código producto es el mismo mecanismo visto desde adentro: transmitido fila por fila, cada columna es una palabra intercalada con profundidad igual al largo de las filas, y la ráfaga que aguanta depende del orden en que salen los símbolos, no del código. Eso es la ráfaga la corrige el orden.

10 · La cadena del OIF-400ZR

El esquema C-FEC del OIF-400ZR, el del trabajo práctico final, concatena tres piezas de esta unidad. En el transmisor: un código exterior tipo producto, el staircase sobre BCH (255,239); un intercalador convolucional; y un código interior, el Hamming extendido y acortado (128,119). Después, el mapeo a DP-16QAM y la fibra. En el receptor, el camino inverso: el Hamming decodifica con decisión blanda, el desintercalador reordena, y el código exterior decodifica con decisión dura.

La ráfaga que este intercalador desarma no es sólo la del canal: la produce también el decodificador interior. Cuando elige mal, la palabra que entrega difiere de la transmitida en una palabra no nula del (128,119), con $d_{\text{min}}\ge 4$ porque acortar no la baja: por lo menos 4 bits mal, todos dentro de los mismos 128. Para el código exterior eso es una ráfaga, y el desintercalador la reparte entre muchas de sus palabras antes de que las vea. La tarea del Hamming no es entregar datos limpios: es bajar la tasa de error hasta donde el exterior, con su capacidad de corrección, la puede terminar.

Para tener a mano

1. El intercalado reordena; no agrega redundancia. El intercalado de un $(n,k)$ con profundidad $\lambda$ es un $(\lambda n,\lambda k)$ con la misma $R$ y la misma $d_{\text{min}}$.
2. De bloque: $\lambda$ palabras por filas, transmitidas por columnas. La ranura $\tau$ es de la palabra $\tau mod\lambda$.
3. Una ráfaga de $b$ deja a lo sumo $\lceil b/\lambda \rceil$ errores por palabra. Se corrige toda ráfaga de $b\le \lambda t$, y la cota es justa. Se elige $\lambda \ge b_{\text{máx}}/t$.
4. Costo del de bloque: el arreglo, $\lambda n$ por extremo; el mínimo, $(\lambda -1)(n-1)$ por extremo y $2(\lambda -1)(n-1)$ de retardo.
5. Convolucional: ramas de $0,J,\dots ,(\lambda -1)J$; $J\lambda (\lambda -1)/2$ celdas por extremo y $(\lambda -1)J\lambda$ de retardo, igual para todos los símbolos.
6. Dispersa como el de bloque si $J\lambda \ge n$ y la primera palabra entra por la rama 0; si no, hace falta $J\lambda \ge n+1$.
7. Contra el de bloque en su mínimo, cuesta $J\lambda /2(n-1)$ en memoria y en retardo: algo más de la mitad, que se acerca a la mitad con $\lambda$ que divide a $n$, palabras alineadas y largas. El (7,4) con $\lambda =4$ cuesta dos tercios.
8. Sin fronteras: el desintercalador convolucional se sincroniza con una fase entre $\lambda$; el de bloque, con una alineación entre $\lambda n$.