Códigos de paridad de baja densidad (Low density parity check codes, LDPC)

Abstract

En 1948, C. E. Shannon propuso una teoría matemática para el problema general de la comunicación confiable de información a través de medios no confiables que, en particular, abarca problemas como el de transmitir información de un lugar a otro o el de almacenar información a ser recuperada más tarde. Además de dar las bases matemáticas para modelar el problema, Shannon demostró que, si la información es representada y procesada en forma adecuada, la confiabilidad puede ser arbitrariamente alta si y sólo si la eficiencia con la cual se utiliza el medio no supera un cierto límite que depende del mismo. Sin embargo, el teorema de Shannon no dice nada sobre la complejidad de los algoritmos que representan y procesan la información. La búsqueda de cómo representar y procesar la información para comunicar con eficiencia cercana al límite, en distintos tipos de medios, con alta confiabilidad y con algoritmos de baja complejidad ha resultado un verdadero desafío, desde ese entonces, para matemáticos e ingenieros en comunicaciones. Los Códigos de Paridad de Baja Densidad (Low-Density Parity-Check, LDPC) fueron descubiertos en 1963 por R. G. Gallager pero, debido a las limitaciones existentes en la capacidad de cómputo y de almacenamiento de los equipos disponibles en la época, fueron abandonados y, recién en la década de los 90', fue descubierto su verdadero potencial para acercarse al límite de Shannon, con confiabilidad arbitrariamente alta y con baja complejidad en los algoritmos. En este proyecto, presentamos un estudio de la teoría fundamental de los Códigos LDPC junto con los elementos básicos de la Teoría de la Información y de la Codificación. Además, presentamos los resultados de un trabajo de experimentación con el objetivo de verificar empíricamente algunos resultados importantes de la teoría. Finalmente, proponemos varios trabajos a realizar en el futuro, relacionados con el tema de los Códigos LDPC.