Teoría de codificación esencial [pdf]

• Este libro organiza de forma integral los conceptos clave de la teoría de codificación y sus desarrollos modernos
• Aborda los principios básicos de los códigos de corrección de errores, la estructura y los límites de distintos códigos, así como sus áreas de aplicación práctica
• Explica con especial atención códigos ampliamente usados en la práctica, incluyendo la teoría de Shannon y los códigos de Hamming, además de Reed-Solomon
• También ofrece de forma sistemática casos de uso en sistemas de TI modernos, como hashing, pruebas grupales y protección de información biométrica
• Incluye apéndices, ejercicios y bibliografía, por lo que está compuesto como una referencia eficaz tanto para estudiantes como para profesionales

---

Prólogo

• Este libro se basa en las notas de clase de teoría de codificación de Venkatesan Guruswami, Atri Rudra y Madhu Sudan
• Se basa en contenidos impartidos en cursos de University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT y otras instituciones
• Recibió apoyo de la subvención NSF CAREER grant CCF-0844796
• Las opiniones y resultados de los autores no representan la postura oficial de la NSF
• Está disponible bajo la licencia Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License

Resumen del índice

Capítulo 1: Preguntas fundamentales

• El propósito de la teoría de codificación, definiciones básicas y códigos
• Corrección de errores, concepto de distancia de los códigos, códigos de Hamming y cotas
• Clasificación de familias de códigos, con ejercicios y bibliografía

Parte I: Fundamentos

• Introducción de estructuras matemáticas como códigos lineales, cuerpos finitos y espacios vectoriales
• Explicación de la decodificación eficiente de códigos de Hamming y de los códigos duales
• Incluye ejercicios y bibliografía

Capítulo 3: Probabilidad y función de entropía q-aria

• Fundamentos de probabilidad, método probabilístico y comprensión de la función de entropía q-aria
• Incluye ejercicios y bibliografía relacionados

Parte II: Combinatoria

• Explica cotas y límites de los códigos como Hamming, Gilbert-Varshamov, Singleton y Plotkin
• Códigos Reed-Solomon, polinomios y aplicaciones de cuerpos finitos
• Modelo de ruido de Shannon y límites de la transmisión de información, con comparación frente a Hamming
• Ampliaciones como list decoding, Johnson Bound y capacidad de list decoding
• Nuevas teorías de límites como Elias-Bassalygo y cotas de programación lineal

Parte III: Estructuras diversas de códigos

• Códigos basados en polinomios, aplicación sobre campos binarios y estructuras generales de códigos
• Concatenación de códigos, Zyablov Bound, técnicas avanzadas de concatenación y resumen
• Grafos expander y códigos expander, amplificación de distancia y casos de aplicación

Parte IV: Algoritmos

• Métodos eficientes de decodificación para Reed-Solomon, Reed-Muller y códigos concatenados
• Métodos para alcanzar la capacidad del canal BSCp y estructura de códigos internos/externos
• Códigos polar, principio de polarización e implementación de codificadores/decodificadores, además de capacidad de list decoding
• Explicación de códigos con codificación en tiempo lineal y recuperación local

Parte V: Aplicaciones

• Teoría del hashing y prevención de colisiones, funciones hash casi universales y prueba de posesión de datos
• Concepto de Fuzzy Vault para proteger autenticación biométrica (huellas dactilares)
• Formalización de Group Testing, cotas y aplicaciones a algoritmos de data stream
• Complejidad de los problemas de codificación: problema del codeword más cercano, decodificación basada en preprocesamiento, aproximación, problema de distancia mínima, etc.
• Como temas de apoyo en complejidad computacional, trata complejidad de comunicación, aleatorización, Pseudorandomness, Hardcore Predicates y problemas de dificultad promedio, entre otros

Apéndice

• Tabla de símbolos, desigualdades y ecuaciones útiles, notación asintótica, y fundamentos básicos de algoritmos y complejidad
• Introducción a algoritmos algebraicos, cuerpos finitos y operaciones con polinomios
• Principales conceptos de teoría de la información: entropía, entropía condicional, información mutua, etc.

Características y valor de uso

• Ofrece de forma integral el trasfondo teórico y la aplicación práctica de algoritmos de corrección de errores, esenciales en comunicaciones modernas, almacenamiento de datos y sistemas criptográficos
• Organiza desde conceptos básicos hasta tendencias recientes y aplicaciones reales, transmitiendo conocimientos amplios a desarrolladores junior, investigadores y profesionales de TI
• Cada capítulo incluye ejercicios y bibliografía, lo que favorece el aprendizaje y el estudio autodirigido
• Puede usarse libremente con fines académicos y no comerciales bajo la licencia Creative Commons

[GN⁺]

Comentarios de Hacker News

• Quiero destacar que "The Mathematical Theory of Communication" de Claude Shannon es un texto fundamental de teoría de la información explicado de forma lo bastante accesible como para que cualquiera pueda leerlo, incluso sin una base matemática profunda enlace

  • También quiero decir que Shannon es una figura excelente para empezar a adoptar una forma de pensar matemática. Al principio, derivó el concepto de entropía de la información sin asignarle ningún significado en particular, basándose solo en las propiedades que necesitaba. Sorprendentemente, esa definición creada casi por accidente resultó coincidir casi por completo con la entropía termodinámica de la física, y fue Von Neumann quien lo señaló y le dio el nombre. Muchas veces las matemáticas avanzan mediante desarrollos lógicos del tipo "si esto debe satisfacer estas reglas", y esa es una de las razones por las que a mucha gente le parecen difíciles. El artículo de Shannon solo construyó el esqueleto de la teoría de códigos, y la implementación real no está en el artículo. En una startup donde trabajé antes, organicé un club de lectura en el que leímos la versión en libro de ese artículo, y quiero recomendarlo como una experiencia muy valiosa para entender la teoría de la información y las matemáticas en general

• Como la compresión sin pérdida está muy relacionada con la IA generativa, sería interesante agregar más contenido sobre eso. Quiero recomendar una tesis doctoral que presenta muy bien la conexión entre compresión sin pérdida y machine learning enlace

  • Tampoco hace falta limitar esto estrictamente a la compresión sin pérdida. De hecho, casi todo el machine learning puede entenderse como una forma de compresión, en su mayoría compresión con pérdida. Por ejemplo, si solo envías embeddings semánticos por un canal, muchas tareas siguen siendo posibles aunque no tengas el texto original completo, porque esos valores contienen suficiente información. La clasificación de datos también es, al final, un proceso de conservar solo una representación latente de categorías generales y descartar el resto. En el caso de la IA generativa, justamente funciona bien porque hacemos "compresión con pérdida". Al descartar información de forma deliberada y tener que inferir los huecos, se abre la vía para la generalización. Un LLM sin pérdida en realidad no sería algo especialmente interesante en el uso práctico. Aun así, el artículo que recomendé es muy especial porque trata la compresión sin pérdida, algo poco común incluso dentro del machine learning

• Como material reciente y bueno, está el libro de texto <i>Information Theory: From Coding to Learning</i>. También hay una versión PDF en línea, así que puede valer la pena revisarlo enlace

  • También quiero recomendar <i>Information Theory, Inference, and Learning Algorithms</i> de David MacKay enlace

• Para responder a la pregunta de qué significa "coding" aquí: en este contexto, se refiere al acto de codificar/decodificar información, transformándola de una representación a otra. A estos sistemas se les llama códigos, y están diseñados para resistir interferencias, alteraciones o escuchas durante la transmisión de información. Es decir, el coding se usa en muchas áreas como compresión de datos, cifrado, detección y corrección de errores, transmisión y almacenamiento de datos enlace

  • En particular, el libro mencionado se enfoca en los códigos de corrección de errores (error correcting code). Se añaden datos extra para poder recuperar las partes perdidas al transmitir un mensaje. La dificultad a resolver está en diseñar esos datos adicionales para corregir suficientes errores con el menor overhead posible y en un tiempo de cómputo razonable. Esta tecnología se usa en la práctica en una gran variedad de lugares, como WiFi, discos duros, códigos QR y RAM. Por ejemplo, el ECC de la memoria ECC RAM es precisamente un código de corrección de errores. En DDR5, esta tecnología pasó a ser parcialmente obligatoria recientemente

• Ya que estamos compartiendo ebooks gratuitos de CS, también quiero recomendar fuertemente el libro de Algorithms de Jeff E.. Es lectura obligada para cualquiera que quiera aprender algoritmos o repasar su nivel enlace

• He leído algunos capítulos de este libro y estoy realmente satisfecho. Pienso seguir leyéndolo poco a poco durante las próximas semanas, o incluso meses

• Si quieres estudiar más a fondo teoría de la información y teoría de códigos, también me gustaría recomendar estos materiales. Para códigos de corrección de errores, "Error-Correcting Codes" de W. Wesley Peterson y E. J. Weldon, Jr.; y para álgebra abstracta, especialmente teoría de cuerpos, "Commutative Algebra" de Oscar Zariski y Pierre Samuel

  • Los comandos de LaTeX no funcionan aquí

• Si tuviera que recomendar algunos libros para principiantes:

  1. <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> de John R. Pierce - un clásico excelente para entender los conceptos y desarrollar intuición. Otros libros del mismo autor también son muy buenos
  2. <i>Information Theory: A Tutorial Introduction</i> de James V. Stone - una introducción fácil y buena. Otros tutoriales escritos por el autor también son útiles
  3. <i>A Student's Guide to Coding and Information Theory</i> de Stefan Moser y Po-ning chen - una guía breve y clara, y también vale la pena recomendar otros libros de la misma serie

• Cada vez que alguien dice que "esto es esencial", para mí siempre es un momento un poco intimidante, porque en la carrera apenas llegué a tener un leve contacto con ese tema

  • En esta materia, "esencial" no significa tanto que sea algo que todo estudiante de ciencias de la computación deba saber obligatoriamente, sino que contiene la esencia de la teoría de códigos. Uno de los coautores del libro da clases directamente en nuestra universidad, y este curso es una materia optativa de años superiores con una carga matemática abrumadora. En una carrera de cuatro años de ciencias de la computación, normalmente solo la toma una fracción muy pequeña de estudiantes del último año, y entre mis conocidos, todos los que la llevaron eran personas a las que les gustaban las demostraciones matemáticas. La disfrutaron

  • Cuando dice "esencial" o "introductorio", es señal de que te espera un libro de texto muy denso