Bitácora · FEC

Códigos detectores y correctores de errores

Curso extracurricular de la Fundación Fulgor. Del canal ruidoso a los cuerpos de Galois.

El curso arranca con una pregunta de ingeniería —cómo transmitir confiablemente por un canal que corrompe— y a la segunda unidad ya está construyendo cuerpos de Galois. Ese salto no es un desvío: es el argumento. Las notas lo siguen en ese orden.

Unidad 1 · El canal y el problema

Ensayo 1 Un canal que siempre miente es un canal perfecto — La capacidad del canal binario simétrico cae a cero en p = 0,5 y vuelve a uno en p = 1. Lo que arruina un canal no es el error: es la incertidumbre.

Ensayo 2 El código que todos inventan primero no paga nunca — Repetir tres veces cada bit es peor que no codificar en todo el rango, y ni en el límite empata: con decisión dura tiende a −1,76 dB.

Unidad 2 · Por qué hace falta el álgebra

Ensayo 3 Cuatro operaciones y finito — El alfabeto necesita suma, resta, producto y división, y tiene que ser finito. Eso solo fuerza que los cuerpos existan únicamente en potencias de primos.

Ensayo 4 Las potencias de α recorren todo, o no — Con un polinomio primitivo las potencias de α dan la vuelta entera; con uno que no lo es, el ciclo se cierra antes y el cuerpo no aparece.

Unidad 3 · Códigos de bloque lineales

Ensayo 5 Un síndrome cero no prueba nada — El (7,4) promete ver hasta dos errores y además ve 84 de los 99 patrones de tres o más. Los quince que se le escapan no son los de mucho error: son exactamente las palabras de código.

Ensayo 6 Con dos errores, el decodificador empeora — Con dos errores el decodificador del (7,4) no falla: agrega un tercero, porque dos columnas de H siempre suman una tercera. Los 21 pares salen con tres bits mal.

Ensayo 7 Corregir uno en vez de detectar dos cuesta 3/p — Con la misma distancia mínima, corregir entrega en silencio unas 3/p veces más palabras malas que sólo detectar, a cambio de no pedir retransmisión.

Ensayo 8 En un código perfecto, la bandera no se levanta — La decodificación incompleta promete avisar en vez de equivocarse. En el (7,4) no avisa nunca, porque sus esferas no dejan hueco; el (8,4) sí deja.

Unidad 4 · Las familias

Ensayo 9 El producto corrige más de lo que promete — Al (49,16,9) decodificado por etapas se le suele garantizar un error. Corrige todos los de dos y de tres, y de los de cuatro sólo falla cuando dos filas traen dos errores cada una.

Ensayo 10 La ráfaga la corrige el orden — El mismo código producto corrige toda ráfaga de hasta 15 símbolos si se transmite fila por fila, y de hasta 7 si se transmite columna por columna. La protección sale del orden, no del código.

Ensayo 11 Votar no es buscar la más cercana — Hasta t errores, la votación de Reed y la palabra más cercana coinciden. Con ocho en el RM(1,5) de la Mariner 9, la más cercana es única en el 92,4 % de los patrones; la votación decide sin empatar en el 14,5 %.

Unidad 5 · Los códigos cíclicos

Ensayo 12 Un bit más de redundancia puede costar distancia — Con largo 15, pasar de 11 a 12 bits de paridad baja la mejor distancia de los cíclicos de 8 a 5: con 12 hay un solo código, un patrón de 3 bits repetido 5 veces. Con 8 bits, elegir mal los factores da 3 en vez de 5.

Ensayo 13 La ráfaga que más se escapa — Un CRC de n − k bits ve toda ráfaga de hasta n − k. La que más se le escapa no es la más larga sino la que se pasa por uno, con el doble de fracción: con 32 bits, una de cada 2 147 483 648.

Unidad 5 · Clase práctica resuelta

Ejercicios 1, 6 y 7 Desplazar, factorizar, elegir — Girar es multiplicar por X y tomar un resto; el generador más redundante que contiene a una palabra es su mcd con X¹⁵ + 1; y con n − k = 8 la distancia es 5, 5 o 3 según los factores.

Ejercicios 2, 3 y 11 El Golay por dentro — Los dos generadores recíprocos y h(X) sin dividir, la palabra sistemática de 1 + X³ dividida a la vista, y el (20,9) acortado con su ρ(X).

Ejercicios 4 y 5 El registro ciclo a ciclo — La traza del codificador del (15,5) bit por bit, el síndrome de un error en X¹² como resto, y el ciclo de más que gira la palabra.

Ejercicios 8, 9 y 10 Atrapar errores y ráfagas — Con la misma t, el (15,5) captura 450 de 455 triples y el Golay 1035 de 1771: la captura pide posiciones limpias seguidas en el anillo. Y las ráfagas que un cíclico no ve.

Unidad 6 · Los códigos BCH

Ensayo 14 Pedir t puede darte más — Un BCH garantiza la tira más larga de raíces consecutivas, no la t pedida. En largo 255, 31 de los 64 valores dan más: pedís 32 y el (255,47) corrige 42.

Ensayo 15 Pasado t, la cuenta la hacen las palabras livianas — Con t + 1 errores, la fracción que sale equivocada en silencio es A₂ₜ₊₁·C(2t+1, t+1)/C(n, t+1): 38,5 % en el (15,5) y 17,2 % en el (31,16), con la misma t.

Unidad 6 · Ejercicio resuelto

Ejemplo integral El (15,5) de punta a punta — El mensaje 11001, tres errores en 2, 7 y 13, y el decodificador entero: los seis síndromes, el algoritmo iterativo binario, Chien y la corrección.

Conceptos

Unidad 3 El código lineal y la matriz G — Un subespacio de Vₙ: la palabra nula, la suma cerrada, la tasa, la matriz G, la forma sistemática [I P] y las 16 palabras del (7,4), con su codificador en SystemVerilog.

Unidad 3 La matriz de paridad y el código dual — H describe el código desde afuera: G·Hᵀ = 0, sus columnas, el dual (7,3), la paridad simple y la repetición como par dual, y el (8,4), que es su propio dual.

Unidad 3 El síndrome — s = rHᵀ depende sólo del patrón de error: es la suma de las columnas de H donde hubo error, y cada síndrome lo comparten 2ᵏ patrones. Con el calculador del RTL.

Unidad 3 La distancia mínima — Peso y distancia, d_min como el menor peso y como la menor cantidad de columnas de H que suman cero, la distribución de pesos, t, las esferas y los modos de operación.

Unidad 3 El standard array y la decodificación por síndrome — Máxima verosimilitud sobre el BSC, el arreglo con sus líderes, la tabla de síndromes y su case en RTL, los empates del (8,4), y lo que la decodificación incompleta avisa y lo que no.

Unidad 3 Las cotas de Singleton y de Hamming — Cuánta distancia compran n − k bits de paridad: Singleton y los MDS, Hamming y el empaquetamiento de esferas, los códigos perfectos, y el (90,78), que cumple la igualdad y no existe.

Unidad 4 Los códigos de Hamming — Todas las columnas no nulas: d_min = 3, perfectos, el síndrome como dirección del bit erróneo, el símplex dual, y una ganancia que deja de crecer con el largo.

Unidad 4 Los códigos acortados — Acortar es sacar columnas de H: (n − ℓ, k − ℓ), una d_min que no baja, síndromes que quedan libres, y el (128,119) del OIF-400ZR.

Unidad 4 El Hamming extendido y el SEC-DED — Un bit de paridad global lleva d_min de 3 a 4 y parte el síndrome en paridad y posición: cuatro casos, y qué pasa con cada peso de error.

Unidad 4 Los códigos de Hsiao — Columnas de peso impar: distancia 4 sin fila de paridad global, y el (72,64) de las memorias con 216 unos y 27 por fila, contra 258 y una fila de 72.

Unidad 4 Los códigos de Reed-Muller — RM(r, m) como tablas de verdad de grado ≤ r, la construcción (u, u + v), la dualidad, la equivalencia con el (8,4) extendido y el algoritmo de Reed por votos disjuntos.

Unidad 4 El código de Golay — El (23,12,7) perfecto, su extendido auto-dual (24,12,8), las 759 octadas del S(5,8,24), y por qué cuatro errores se detectan pero no se corrigen.

Unidad 4 Los códigos producto — El arreglo con filas en C1 y columnas en C2: d_min = d1·d2, la decodificación por etapas y su garantía (t1+1)(t2+1) − 1, y los patrones que ninguna pasada arregla.

Unidad 4 El intercalado — El intercalador de bloque y su ⌈b/λ⌉, lo que cuesta en memoria y latencia, el convolucional y cuándo cuesta la mitad, y la cadena del OIF-400ZR.

Unidad 5 Los códigos cíclicos — El giro como X·v(X) módulo Xⁿ + 1, las órbitas, y el (7,4) del curso, que ya era cíclico.

Unidad 5 El polinomio generador — Las palabras de un cíclico son los múltiplos de un solo polinomio, que divide a Xⁿ + 1. Construir es factorizar, y el dual lo genera el recíproco de h(X), no h(X).

Unidad 5 El codificador cíclico — Codificar en forma sistemática es una sola división. La hace un registro de n − k etapas, y el de k etapas por h(X) da la misma palabra.

Unidad 5 El síndrome cíclico — El síndrome como resto de dividir por g(X), el mismo registro que codifica, y el teorema 5: un ciclo más del registro es el síndrome de la palabra girada.

Unidad 5 El decodificador de Meggitt — Una sola pregunta sobre el síndrome, hecha n veces: en el (7,4) se reduce a una compuerta AND, y en el (15,5) a 106 síndromes en vez de 576, a cambio de n ciclos.

Unidad 5 La captura de errores — Si los errores caben en las n − k posiciones de paridad, el síndrome es el error. El (15,5) captura todo menos 5 triples; el Golay necesita Kasami o la búsqueda sistemática.

Unidad 5 Los CRC y los códigos cíclicos acortados — Toda ráfaga de hasta n − k, las que se escapan después, acortar sin cambiar el circuito, y lo que garantiza cada CRC normalizado.

Unidad 5 El LFSR y las m-secuencias — El LFSR multiplica su estado por X módulo g(X): las órbitas miden el orden de g, y sólo un primitivo da la m-secuencia.

Unidad 5 El producto cíclico y los quasi-cíclicos — Dos cíclicos de largos coprimos dan un producto cíclico si el arreglo se lee en diagonal; leído por filas, sólo es quasi-cíclico, como el (9,3).

Unidad 6 Las clases conjugadas y los polinomios mínimos — El orden y las longitudes que habilita, el cuadrado como operación lineal, las clases conjugadas, el polinomio mínimo como producto binario sobre la clase, y lo que cuesta cada operación.

Unidad 6 Los códigos BCH — Se piden 2t raíces consecutivas y sale el código: g(X) como MCM de los polinomios mínimos, los cuatro ejemplos, la tira más larga, el catálogo y n − k ≤ mt.

Unidad 6 La cota BCH — Por qué 2t raíces consecutivas garantizan distancia 2t + 1: la prueba por la Vandermonde, la igualdad, la desigualdad, y por qué la familia no aguanta bloques largos.

Unidad 6 La distribución de pesos de los códigos BCH — El dual del (31,21) y MacWilliams, la binomial como primer término, y P_u(E) con sus dos cotas.

Unidad 6 Los síndromes y el polinomio localizador — Sᵢ = r(βⁱ), los pares como cuadrados, σ(X), las identidades de Newton y el registro que genera los síndromes.

Unidad 6 El método de Peterson — Las identidades de Newton como sistema lineal: el primer determinante no nulo da cuántos errores hubo, y hasta t = 3 hay fórmula cerrada.

Unidad 6 El algoritmo de Berlekamp-Massey — El localizador como el registro más corto que genera los síndromes: la discrepancia, la elección de ρ, la versión binaria de t iteraciones y la versión sin inversiones.

Unidad 6 La búsqueda de Chien — Las raíces de σ(X) por prueba exhaustiva encadenada por constantes, el orden de las posiciones, el circuito, y qué atrapa cada comprobación de falla.

Unidad 6 Errores y borrados — Un borrado cuesta medio error: la cota, las dos pasadas y por qué el criterio elige bien.

Unidad 6 El decodificador BCH en hardware — La aritmética de GF(2ᵐ) hecha compuertas, el iterativo sin inversiones, Chien en paralelo y la cascada segmentada, con el (255,239) dimensionado.