Teoria Essencial da Codificação [pdf]

• Este livro organiza de forma abrangente os conceitos centrais da teoria da codificação e seus desenvolvimentos modernos
• Aborda os princípios básicos dos códigos de correção de erros, a estrutura e os limites de vários códigos, além de áreas de aplicação prática
• Explica com foco especial códigos amplamente usados no mundo real, como a teoria de Shannon e os códigos de Hamming, além de Reed-Solomon
• Também apresenta de forma sistemática casos de aplicação em sistemas de TI modernos, como hashing, testes em grupo e proteção de dados biométricos
• Inclui apêndices, exercícios e referências, sendo composto como uma obra de referência eficaz tanto para estudantes quanto para profissionais

---

Prefácio

• Este livro se baseia nas notas de aula de teoria da codificação de Venkatesan Guruswami, Atri Rudra e Madhu Sudan
• Tem como base conteúdos ministrados na University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT e outras instituições
• Recebeu apoio da bolsa NSF CAREER grant CCF-0844796
• As opiniões e resultados dos autores não representam a posição oficial da NSF
• Está disponível sob a licença Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Resumo do sumário

Capítulo 1: Perguntas fundamentais

• Objetivo da teoria da codificação, definições básicas e códigos
• Correção de erros, conceito de distância entre códigos, códigos de Hamming e limites
• Inclui classificação de famílias de códigos, exercícios e referências

Parte I: Fundamentos

• Introdução de estruturas matemáticas como códigos lineares, corpos finitos e espaços vetoriais
• Explicação da decodificação eficiente dos códigos de Hamming e dos códigos duais
• Inclui exercícios e referências bibliográficas

Capítulo 3: Probabilidade e função de entropia q-ária

• Fundamentos de probabilidade, método probabilístico e compreensão da função de entropia q-ária
• Oferece exercícios e referências relacionados

Parte II: Combinatória

• Explica limites de códigos e restrições como Hamming, Gilbert-Varshamov, Singleton e Plotkin
• Códigos Reed-Solomon, polinômios e aplicações de corpos finitos
• Modelo de ruído de Shannon e limites da transmissão de informação, com comparação a Hamming
• Extensões como list decoding, Johnson Bound e capacidade de list decoding
• Novas teorias de limites, como Elias-Bassalygo e limites por programação linear

Parte III: Diversas estruturas de códigos

• Códigos baseados em polinômios, aplicação em campos binários e estruturas gerais de códigos
• Concatenação de códigos (concatenation), Zyablov Bound, técnicas avançadas de concatenação e resumo
• Grafos expander e códigos expander, amplificação de distância e casos de aplicação

Parte IV: Algoritmos

• Métodos eficientes de decodificação para Reed-Solomon, Reed-Muller e códigos concatenados
• Métodos para atingir a capacidade do canal BSCp e estruturas de códigos internos/externos
• Códigos polares, princípio de polarização, implementação de codificador/decodificador e capacidade de list decoding
• Explicação de códigos com codificação em tempo linear e recuperação local

Parte V: Aplicações

• Teoria do hashing e prevenção de colisões, funções hash quase universais, prova de posse de dados
• Conceito de Fuzzy Vault para proteção de autenticação biométrica (impressões digitais)
• Formalização de testes em grupo (Group Testing), limites e aplicações em algoritmos de fluxo de dados
• Complexidade de problemas de codificação: problema do codeword mais próximo, decodificação com pré-processamento, aproximação, problema da distância mínima etc.
• Como temas de apoio em complexidade computacional, aborda complexidade de comunicação, aleatorização, pseudorrandomness, hardcore predicates e problemas de dificuldade média

Apêndice

• Tabela de símbolos, desigualdades e igualdades úteis, notação assintótica, fundamentos de algoritmos e complexidade
• Introdução a algoritmos algébricos, corpos finitos e operações com polinômios
• Organização dos principais conceitos da teoria da informação: entropia, entropia condicional, informação mútua etc.

Características e valor prático

• Oferece de forma abrangente a base teórica e a aplicação prática de algoritmos de correção de erros essenciais em telecomunicações modernas, armazenamento de dados e sistemas criptográficos
• Organiza desde conceitos básicos até tendências recentes e aplicações reais, transmitindo conhecimento amplo a desenvolvedores iniciantes, pesquisadores e profissionais de TI
• Cada capítulo inclui exercícios e referências, favorecendo o estudo e a aprendizagem autodirigida
• Pode ser usado livremente para fins acadêmicos e não comerciais, de acordo com a licença Creative Commons

[GN⁺]

Comentários do Hacker News

• Quero destacar que "The Mathematical Theory of Communication", de Claude Shannon, é um documento fundamental da teoria da informação explicado de forma tão acessível que qualquer pessoa consegue ler, mesmo sem uma base matemática profunda link

  • Quero dizer que Shannon é realmente uma ótima figura para começar a pensar matematicamente. Ele chegou ao conceito de entropia da informação inicialmente sem atribuir nenhum significado a ele, derivando-o apenas a partir das propriedades necessárias. Surpreendentemente, essa definição criada quase por acaso coincide muito de perto com a entropia termodinâmica da física, e foi Von Neumann quem apontou isso e deu o nome. A matemática frequentemente avança por desenvolvimentos lógicos do tipo "se isso precisa satisfazer estas regras", e esse é um dos motivos pelos quais muita gente a acha difícil. O artigo de Shannon apenas estabeleceu a estrutura da teoria da codificação; a implementação real não está no artigo. Eu já cheguei a organizar um clube de leitura numa startup antiga para ler a versão em livro desse trabalho junto com outras pessoas, e quero recomendar isso como uma experiência realmente excelente para entender teoria da informação e matemática de forma mais ampla

• Como a área de compressão sem perda tem uma relação próxima com a IA generativa, seria interessante adicionar mais conteúdo sobre isso. Quero recomendar uma tese de doutorado que apresenta muito bem a conexão entre compressão sem perda e machine learning link

  • Também não é necessário limitar isso apenas à compressão sem perda. Na verdade, quase todo machine learning pode ser entendido como uma forma de compressão, principalmente compressão com perda. Por exemplo, se você enviar apenas embeddings semânticos por um canal, ainda é possível realizar tarefas porque há informação suficiente embutida nesses valores, mesmo sem o texto original completo. A classificação de dados também acaba sendo um processo de manter apenas representações latentes de categorias gerais e descartar o resto. No caso da IA generativa, ela funciona bem justamente porque fazemos uma espécie de "compressão com perda". Ao descartar informação de propósito e exigir inferência para preencher as lacunas, abre-se um caminho para a generalização. Um LLM sem perda, na prática, não seria algo particularmente interessante em termos de uso real. Ainda assim, o artigo recomendado é muito especial por tratar de compressão sem perda, algo raro até mesmo dentro de machine learning

• Como material bom e mais recente, existe o livro-texto <i>Information Theory: From Coding to Learning</i>. Também há uma versão online em PDF, então vale a pena dar uma olhada link

  • Também quero recomendar <i>Information Theory, Inference, and Learning Algorithms</i>, de David MacKay link

• Para responder à pergunta sobre o que significa "coding" aqui: neste contexto, coding se refere ao ato de codificar/decodificar informação, convertendo-a de uma representação para outra. Esses sistemas são chamados de código e são projetados para resistir a interferência, modificação ou escuta durante a transmissão de informação. Ou seja, coding é usado em muitas áreas, como compressão de dados, criptografia, detecção e correção de erros, transmissão e armazenamento de dados link

  • Em especial, o livro mencionado foca em códigos de correção de erros (error correcting code). Ao transmitir uma mensagem, acrescentam-se dados extras para que seja possível recuperar partes perdidas. A dificuldade a ser resolvida é projetar esses dados adicionais de modo que consigam recuperar erros suficientes com o mínimo de overhead e em um tempo de computação razoável. Essa tecnologia é usada na prática em lugares muito diversos, como WiFi, discos rígidos, QR codes e RAM. Por exemplo, o ECC de ECC RAM é justamente um código de correção de erros. Recentemente, isso se tornou parcialmente obrigatório no DDR5

• Já que o clima é de compartilhar ebooks gratuitos de CS, também quero recomendar fortemente o livro de Algorithms do Jeff E. É leitura obrigatória para quem quer aprender algoritmos ou revisar seus conhecimentos link

• Li alguns capítulos desse livro e estou muito satisfeito. Pretendo continuar lendo devagar ao longo das próximas semanas, ou talvez meses

• Se você quiser estudar teoria da informação e teoria da codificação mais a fundo, também quero recomendar os seguintes materiais. Para códigos de correção de erros, "Error-Correcting Codes", de W. Wesley Peterson e E. J. Weldon, Jr.; e para álgebra abstrata, especialmente teoria dos corpos, "Commutative Algebra", de Oscar Zariski e Pierre Samuel

  • Comandos LaTeX não funcionam aqui

• Se eu tivesse que indicar alguns livros para iniciantes, seriam:

  1. <i>An Introduction to Information Theory, Symbols, Signals and Noise</i>, de John R. Pierce — um clássico excelente para entender os conceitos e desenvolver intuição. Outros livros do mesmo autor também são ótimos
  2. <i>Information Theory: A Tutorial Introduction</i>, de James V. Stone — uma introdução fácil e boa. Outros tutoriais escritos pelo autor também são úteis
  3. <i>A Student's Guide to Coding and Information Theory</i>, de Stefan Moser e Po-ning chen — um guia conciso e claro, e outros livros da mesma série também valem a recomendação

• Sempre que alguém diz que "isso é essencial", para mim, que no máximo tive um contato superficial com o tema durante o curso, esse sempre é um momento um pouco assustador

  • Nesse curso, "essencial" não significa exatamente que todo estudante de ciência da computação precisa saber isso, mas sim que o livro contém a essência da teoria da codificação. Um dos coautores do livro dá aula diretamente na nossa universidade, e essa disciplina é uma optativa de anos mais avançados com uma carga matemática esmagadora. Em um curso de quatro anos em ciência da computação, normalmente só uma minoria bem pequena dos alunos do último ano faz essa disciplina, e todos os amigos meus que a cursaram eram pessoas que gostavam de provas matemáticas. Eles gostaram da matéria

  • Quando está escrito "essencial" ou "introdução", isso costuma ser um aviso de que vem aí um livro-texto extremamente denso