Códigos de paridad de baja densidad, LDPC

J. CASTIÑEIRA MOREIRA

Facultad de Ciencias Exactas y Naturales, Mar del Plata

Conferencia; Jornadas sobre Criptografía desarrolladas en la Facultad de Ciencias Exactas y Naturales de la UNMDP; 2006

Los limites de la técnica de corrección de errores fueron establecidos por Shannon en su trabajo sobre el modelo matemático para las comunicaciones, y luego de este planteo surgieron una serie de técnicas de codificación que no encontraron un acercamiento notorio a los limites predichos hasta la aparición en 1993 de los códigos turbo. Posteriormente David J. C. Mackay y R. M. Neal (1996) redescubrieron los llamados códigos Gallager, que por años permanecieron ocultos, a pesar de su excelente funcionamiento. Los códigos Gallager, también conocidos como códigos de paridad de baja densidad, que en ingles son descriptos como “low-density parity-check codes” (LDPC) son códigos de bloques lineales, que se construyen sobre la base de una matriz de paridad  que tiene como característica ser de baja densidad (en Ingles, “Sparse Matrix”), es decir, en el caso binario contiene pocos elementos  dispersos entre un gran numero de elementos ‘0‘. El diseño propuesto por Gallager (R. G. Gallager, 1962) presenta el método constructivo, el algoritmo probabilistico iterativo, y los elementos principales de su desarrollo, pero la carencia de procesamiento de cálculo poderoso para esa época (año 1962) no permitió mostrar la eficacia de estos códigos.