2022¶

Παρακαλώ διαβάστε από το βιβλίο MacK = MacKay, Information Theory, Inference and Learning Algorithms.

Υπολογισμός εντροπίας με σταδιακή αποκάλυψη πληροφορίας: $$ H(p_1, \ldots, p_n) = H(p_1, 1-p_1) + (1-p_1) H(\frac{p_2}{1-p_1},\ldots,\frac{p_n}{1-p_1}). $$ Παράδειγμα [MacK 2.13, σελ. 34].
Gibbs inequality: Αν $p_i, q_i$, $i=1, 2, \ldots, n$ είναι δύο κατανομές πιθανότητας τότε $$ \sum_{i=1}^n p_i \log\frac{1}{p_i} \le \sum_{i=1}^n p_i \log\frac{1}{q_i}. $$ Απόδειξη στο [MacK, p.44] χρησιμοποιώντας την ανισότητα του Jensen.
Δυαδικοί κώδικες: σε κάθε γράμμα ενός αλφαβήτου $A = \{a_1, \ldots, a_n\}$ αντιστοιχίζουμε το αντίστοιχο σύμβολο ενός δυαδικού κώδικα $C$. Αυτό είναι ένα σύνολο με $n$ λέξεις, πάνω από το δυαδικό αλφάβητο η κάθε μία, όχι απαραίτητα με το ίδιο μήκος. Δείτε το παράδειγμα [MacK 5.6, σελ. 93] που αντιστοιχεί σε ένα αλφάβητο με 4 γράμματα.
Με $\ell_i$ συμβολίζουμε το μήκος της $i$-οστής λέξης ενός δυαδικού κώδικα (το μήκος μιας λέξης είναι το πόσα δυαδικά ψηφία έχει).
Οι κώδιικες που μας ενδιαφέρουν είναι οι αντιστρέψιμοι: μπορείς δηλ. να ανακτήσεις την αρχική λέξη από το αλφάβητο $A$ αν σου δώσουν τη λέξη πάνω από τον κώδικα $C$ (όπου το κάθε γράμμα του αλφαβήτου έχει αντικατασταθεί από την αντίστοιχη λέξη στο $C$).
Prefix codes: είναι οι κώδικες $C$ όπου καμία λέξη του $C$ δεν είναι πρόθεμα (prefix) μιας άλλης λέξης του $C$. Η αποκωδικοποίηση είναι ιδιαίτερα απλή για τέτοιους κώδικες (που είναι συνεπώς αντιστρέψιμοι) και για κάθε τέτοιο κώδικα φτιάχνουμε συνήθως ένα δυαδικό δέντρο του οποίου τα φύλλα είναι τα σύμβολα του αλφαβήτου $A$. Δείτε ένα τέτοιο δέντρο στο [MacK 5.6, στο σχήμα δεξιά για τον $C_3$]. Με το δέντρο αυτό η αποκωδικοποίηση είναι πολύ εύκολη.
Αν για κάθε γράμμα του αλφαβήτου $A$ έχουμε μια πιθανότητα εμφάνισης στο κείμενο που κωδικοποιύμε (ας την πούμε $p_i$) τότε το αναμενόμενο μήκος του κώδικα $C$ είναι η ποσότητα $L(C) = \sum_{i=1}^n p_i \ell_i$. Αυτό αντιπροσωπεύει το μέσο μήκος του κώδικα ανά γράμμα του αλφαβήτου $A$ όπου αυτό το γράμμα επιλέγεται σύμφωνα με την κατανομή $p_i$.