Information theory (2021, now in English)

Link for zoom classes: https://videoconf-colibri.zoom.us/j/343521115

Description of the first programming assignment:
Description of the second programming assignment:
Turn in date is February 2

The book of the course

  • David MacKay, Information theory, inference, and learning algorithms
    You can download the book from the author’s webpage.
    Utilizaremos para quase tudo e seguiremos o livro de perto.

Lesson Summaries

  • Aula 01 — Introdução à Teoria da Informação. Modelos e códigos para compressão e correcção de erros. O código de repetição. Probabilidades: Ensemble, eventos, ensemble de tuplos, probabilidade marginal, probabilidade condicional, independência, valor esperado.

    Para os alunos que faltaram:

    – Ver a introdução dada no ano passado, até ao código de repetição (podem ignorar a aproximação de Stirling, não vamos usar): https://youtu.be/4B3n9bd5yqQ

    – Ler notas sobre teoria das probabilidades:

    – Ler capítulo 2 do livro
  • Aula 02. Mais probabilidades.
  • Aula 03. Mais probabilidades e entropia.
  • Lesson 04. Exercises in probability and entropy
  • Lesson 05. Compression, Introduction to Shannon’s 1st theorem.
  • Lesson 06. Full proof of Shannon’s first theroem.
  • Lesson 07. Symbol codes, Kraft inequality, Huffman coding
  • Lesson 08. Optimality of Huffman codin
  • Lesson 09. (baby version of) Lempel-Ziv compression
  • Lesson 10. Channels and their capacity
  • Lesson 11. Computing channel capacity. A few examples.
  • Lesson 12. Informal intro to Shannon’s 2nd theorem.
  • Lesson 13. Test 1
  • Lesson 14. The typical pair lemma.
  • Lesson 15. First part of Shannon’s 2nd theorem.
  • Lesson 16. Programming with bits.
  • Lesson 17. The data processing inequality and the second part of Shannon’s 2nd theorem.
  • Lesson 18. Low Density Parity Check codes for the binary erasure channel.
  • Lesson 19 & 20. Project support and working on a conjecture about coding.
  • Lesson 21. Test 2

Syllabus

  1. Introduction (1 lesson).
    MacKay Chapter 1.
  2. Probability theory, entropy, and mutual information (3-4 lessons).
    MacKay Chapter 2.
  3. Shannon’s first theorem, source coding, Huffman coding (6 lessons).
    MacKay Chapters 4, 5 e 6.
  4. Shannon’s second theorem, and LDPC codes (8 lessons).
    MacKay Capítulos 8, 9, 10 e 47.

Grading

The grading will be based on 2 tests and 2 programming assignments.

The first test is for parts 2 and 3 of the syllabus (see above), and the second test is for part 4.

The test will consist of exercises from the book, and will include proving the course’s fundamental theorems.

The first programming assignment will be implementing a Lempel-Ziv compressor, and the second will be writing a coder and decoder for a simple variant of an LDPC code.

The grading of the programming assignments is all-or-nothing: if the program is correct, and the student can show they have written it, then they get the full grade. Otherwise they get 0.

Both tests and programming assignments can be improved/corrected during the 2nd exam season.

Sumários planeados

  • Aula 18 — Introdução ao 2º Teorema de Shannon, lema da típicalidade.
  • Aula 19 — 1ª parte do 2º Teorema de Shannon.
  • Aula 20 — 1ª parte do 2ºTS, Lema da tipicalidade.
  • Aula 21 — 1ª parte do 2º Teorema de Shannon.
  • Plano de estudo sobre o 2º teorema de Shannon. Solução do exercício sobre capacidades pelo Ruben Dhanaraju
  • Correspondência entre matéria dada nas aulas e capítulos do livro:
  • Aula 22 — Códigos LDPC (versão bébé para o canal de rasura).
  • Aula 23 —
  • Aula 24 —
Advertisement