Kodowanie, Kompresja, Kryptografia (KKK)

Konspekt wykładu

1. Wstęp: prawdopodobieństwo, entropia, nierówność Krafta (pdf)
2. Tw. Shannona-Fano o kodowaniu bez szumu, kompresja Huffmana, kody blokowe (pdf)
3. Kompresja LZW, kod arytmetyczny (pdf)
4. Kodowanie w obecności szumu: bity parzystości, kod Hamminga, cykliczne kody liniowe, kody wielomianowe, technmika CRC, kody BCH (pdf)
5. Przykład kodu liniowego (pdf)
6. Wzajemna informacja, nierówność Fano, tw. Shannona o kodowaniu w obecności szumu (pdf)
7. Kryptografia: typy kodów, publiczny klucz i protokoły podpisu elektronicznego, algorytm RSA (pdf)
8. Elementy kwantowekj teorii informacji: podstawy teoretyczne, qubity i bramki kwantowe, przykłady zastosowań - kwantowy protokół dystrybucji klucza, algorytm faktoryzacji Shora, gęste kodowanie (pdf)

Materiały pomocnicze

1. Entropia języka naturalnego

   • Estimating the entropy of English

   • Entropy and redundancy in English

   • C.E. Shannon: Prediction and Entropy of Printed English

2. Frekwencja liter, bigramów,  trigramów ...

   • Wikipedia

   • Singlety: tabela i histogram

   • Bigramy:  tabela i histogram,  "The frequency of bigrams..."

   • Trigramy

3. Entropie blokowe

   • Block entropy analysis of the Indus script and natural languages
     

4. Kody Reeda-Solomona (artykuł)

Zagadnienia do egzaminu - plik pdf