Unidad 4 · Las familias · sacar columnas de H para llegar al largo que pide el sistema, lo que se conserva, los síndromes que quedan libres, el (192,184) y el (128,119) del OIF-400ZR
Los códigos de Hamming vienen en largos 7, 15, 31, 63, 127, 255: cada uno casi el doble del anterior. Un sistema que arma bloques de 192 bits, o de 128, no encuentra ninguno que le sirva. Acortar es la manera de llegar a cualquier largo intermedio, y cuesta poco: la tasa baja un poco, la distancia mínima no baja nada y el código deja de ser perfecto. Lo último suena a pérdida, y es justo lo que después se aprovecha.
Dado un código y un entero , el código acortado en posiciones son las palabras de código cuyas primeras posiciones de información valen cero, con esas posiciones suprimidas. Como valen cero siempre, no hace falta transmitirlas: el receptor ya las conoce. Queda un código
con la misma cantidad de bits de paridad, . Lo que se pierde son bits de información, nada más.
En la forma sistemática la cuenta se ve entera. Fijar es no usar las primeras filas de ; las filas que quedan tienen ceros en las primeras posiciones, y al suprimirlas sale una de que sigue siendo , con las últimas filas de . Del Hamming (15,11) acortado en 3 sale un (12,8), y su matriz de paridad es la del (15,11) sistemático —las columnas de peso ≥ 2 en orden creciente, después la identidad— sin sus tres primeras columnas:
Cuatro filas, como antes, y doce columnas: ocho de información y la identidad de la paridad al final.
Que la del acortado sea la del original sin unas columnas no es casualidad del ejemplo. Sea el conjunto de las posiciones que se suprimen y la columna de .
Paso 1: el criterio de pertenencia, por columnas. Como en el síndrome, es la suma de las columnas donde tiene un 1:
Paso 2: las columnas de no entran nunca. Una palabra del acortado tiene ceros en , así que ninguna con aparece en su suma. La ecuación sigue valiendo con , que es sin esas columnas, aplicada a la palabra sin esas posiciones.
Paso 3: y al revés. Un vector de bits que cumple la ecuación con , completado con ceros en , la cumple con : es una palabra del original con ceros en . Los dos conjuntos son el mismo, y el acortado es exactamente el código cuya matriz de paridad es .
Paso 4: la cuenta de dimensiones. son posiciones de información, así que las columnas de la identidad siguen en y sus filas siguen siendo independientes. El código tiene dimensión , la que daba la definición.
Leído así, acortar es elegir qué columnas de se usan. La definición dice «las primeras de información», pero cualquier conjunto de posiciones de información sirve, y la elección no es indiferente: es el tema de la sección 04.
La distancia mínima no baja. Hay dos razones, y son la misma vista de dos lados. Por las palabras: salvo los ceros suprimidos, el acortado es un subconjunto del original, y el menor peso no nulo de un subconjunto no puede ser menor que el del conjunto entero. Por las columnas: es la menor cantidad de columnas de que suman cero, y sacar columnas no crea dependencias nuevas.
La tasa baja. La paridad queda igual y la información se achica:
que vale siempre, porque . Del (15,11) al (12,8), pasa de 0,733 a 0,667.
La perfección se pierde. Con bits de síndrome hay síndromes. En el Hamming se reparten justo: el cero para «sin error» y los restantes, uno por posición. Por eso es un código perfecto. El acortado tiene los mismos síndromes y sólo posiciones: quedan síndromes libres, uno por cada columna sacada. El (12,8) usa 13 de sus 16.
Un síndrome libre es el síndrome de un error en una posición que no se transmite. Si aparece, el receptor sabe que no hubo un error simple. Es lo que pide la decodificación incompleta, que en el Hamming entero no tiene dónde avisar: en un código perfecto, la bandera no se levanta. Un error doble da , que en el Hamming siempre era una tercera columna. Si esa tercera se sacó, el doble cae en un síndrome libre y queda avisado. Si no, se corrige mal, como antes. En el (12,8) de la definición, con la de arriba, 18 de los 66 dobles caen en síndromes libres y los otros 48 se corrigen mal.
El decodificador no cambia. Se reinsertan los ceros en , se calcula el síndrome con la original y se busca la columna: si apunta a una posición de , el error no es simple y se declara falla en vez de corregir.
Arranca con el (15,11) entero: cero síndromes libres y los 105 dobles corregidos mal, siete por cada columna. Sacá una cualquiera y su ficha queda libre con siete dobles avisados: cada columna del Hamming es la suma de exactamente siete pares. La línea de d_min muestra tres columnas que suman cero; mientras exista alguna, la distancia sigue en 3.
Sobre el (15,11), recorriendo todas las elecciones de columnas de información: con se avisan siempre 7 de los 91 dobles, saque la que saque; con , entre 15 y 18 de 66 según cuáles. Y la distancia queda en 3 en todas las elecciones de hasta seis columnas. Con siete, de las 330 maneras hay una sola que la sube a 4: sacar las seis columnas de peso 2 y la de peso 4. Quedan las ocho de peso impar —las cuatro de la identidad y las cuatro de peso 3— y sale un (8,4) con que avisa los 28 dobles.
La razón es de paridad. La suma de tres columnas de peso impar tiene peso impar, así que nunca es cero: ninguna terna suma cero y la distancia es por lo menos 4. Es la construcción SEC-DED por acortamiento, y el (8,4) que sale tiene los parámetros del extendido del (7,4). Elegir entre las columnas de peso impar las que dejan menos unos y filas parejas es el criterio de los códigos de Hsiao.
Hasta el final, con , queda una sola columna de información además de la identidad, y la distancia depende de cuál: 3 si es de peso 2, 4 si es de peso 3, y 5 si es la . Ese último es la repetición (5,1): la única palabra no nula es . Acortar puede subir bastante, pero a costa de casi toda la tasa: 0,2.
El ejemplo del apunte parte del Hamming (255,247), con , y lo acorta en 63 posiciones: . Los mismos 8 bits de paridad, la tasa baja de 0,969 a 0,958, y quedan 63 de los 255 síndromes no nulos libres.
El apunte dice . Es exactamente 3, y no hay elección de las 63 columnas que la suba. Un código con y bits de paridad no puede ser más largo que : si se borra una de sus posiciones en todas las palabras, queda un con bits de paridad y distancia por lo menos 3, y ése tiene a lo sumo columnas distintas y no nulas. Con el techo es 128, y 192 se pasa. Para un SEC-DED de 184 bits de información hace falta un noveno bit de paridad.
Los síndromes libres sí avisan algo. Sacando, como dice la definición, las 63 primeras columnas de información de la sistemática —las de peso ≥ 2 en orden creciente de valor—, 5562 de los 18 336 dobles caen en un síndrome libre: el 30,3 %. El resto se corrige mal.
El código interior del esquema C-FEC del OIF-400ZR es un Hamming extendido acortado (128,119). Tiene bits de paridad: los 8 de un Hamming con más el de paridad global de la extensión. El extendido de ese Hamming es el (256,247), y acortado en 128 posiciones da
Lo mismo sale en el otro orden: el (255,247) acortado en 128 es un (127,119), y extendido es el (128,119). La tasa es 0,930.
Su distancia es exactamente 4. No baja de 4 porque el extendido la tenía y acortar no la baja. No llega a 5 por la cota de Hamming: corregir dos errores en 128 posiciones pediría un síndrome distinto para cada patrón de peso ≤ 2, que son , y con 9 bits hay 512. Quedan síndromes libres, y con ningún par de columnas suma una tercera: los 8128 dobles caen todos en ellos. Contado sobre las últimas 128 columnas de la del (256,247), de los 8128 pares ninguno suma otra columna.
Se puede leer también como un Hamming de acortado, pero con cuidado con el largo. Nueve bits de paridad dan el (511,502), no un código de 512, y acortarlo en 383 posiciones también da un (128,119). Con columnas cualesquiera, ese acortado sólo garantiza . Llega a 4 porque las 128 se eligen de una mitad: las que tienen un 1 en la fila de la paridad global, que son las 256 columnas del extendido. Es el mismo principio de la sección 04, a escala.
En la cadena del 400ZR el (128,119) va adentro, decodificado con decisión blanda, después de un intercalador convolucional y debajo de un código exterior tipo producto. Su tarea no es entregar datos limpios: es bajar la tasa de error lo suficiente para que el exterior trabaje dentro de su capacidad.
No agrega redundancia. Acortar sólo saca columnas; los bits de paridad son los mismos. Lo que bits no alcanzan a hacer en un largo dado, ninguna elección de columnas lo hace: el (192,184) no puede ser SEC-DED con 8 bits, y el (128,119) no puede corregir dos errores con 9. Las cotas mandan sobre el acortado igual que sobre cualquier código.
Acortar mucho es caro. La paridad no se achica con el largo. Llevar el (15,11) a 8 posiciones deja la mitad de la palabra en paridad, y a 5, cuatro quintos. Si el bloque del sistema es mucho más corto que , conviene un más chico: el acortamiento rinde cuando el largo pedido queda entre y , como 192 entre 128 y 255.
Los síndromes libres no son una garantía. Sin elegir las columnas, avisan los dobles que caen en ellos por azar de la construcción: el 30,3 % en el (192,184), 18 de 66 en el (12,8). Para que avisen todos hay que elegir columnas sin ternas que sumen cero, y eso sólo cabe hasta columnas.