Ψηφιακές Τηλεπικοινωνίες — Νοέμβριος 2011¶
Μεταγραφή από το αρχείο 26.png.
26.png¶
2.1 ΘΕΜΑ 2 ΝΟΕΜΒΡΙΟΣ 2011
Έστω ότι το αλφάβητο μιας διακριτής πηγής πληροφορίας (χωρίς μνήμη) αποτελείται από 7 σύμβολα με τις πιθανότητες εμφάνισης που δίνονται στον παρακάτω πίνακα:
| Σύμβολο | s0 | s1 | s2 | s3 | s4 | s5 | s6 |
|---|---|---|---|---|---|---|---|
| Πιθανότητα Εμφάνισης | 0,0625 | 0,125 | 0,25 | 0,25 | 0,125 | 0,0625 | 0,125 |
α)Να κωδικοποιηθεί η συγκεκριμένη πηγή με χρήση του αλγορίθμου Huffman και να υπολογισθεί η αποδοτικότητα της κωδικοποίησης
β)Αν κωδικοποιήσετε την παραπάνω πηγή με ένα απλό κώδικα σταθερού μήκους τότε πως συγκρίνεται η αποδοτικότητα της κωδικοποίησης με αυτή που επιτεύχθηκε στο ερώτημα α;
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία με λύση στο ίδιο στιγμιότυπο της εκφώνησης (προέλευση δεν αναγράφεται)
Προσοχή
Η προέλευση της φωτογραφίας λύσης δεν είναι γνωστή (δεν φαίνεται αν είναι του διδάσκοντα ή φοιτητή)· κρατείται ως κοινοτική μέχρι επαλήθευσης. Ο πίνακας κωδικών της φωτογραφίας δίνει s2=00 και s3=01, ενώ οι ετικέτες ακμών του σχήματος δίνουν s3=00 και s2=01 (άνω κλάδος με πρόθεμα 0). Η αντιστοιχία δεν επαληθεύτηκε· μεταγράφεται όπως είναι.
Λύσεις — 2011-11¶
26.png¶
2.1 ΘΕΜΑ 2 ΝΟΕΜΒΡΙΟΣ 2011
Έστω ότι το αλφάβητο μιας διακριτής πηγής πληροφορίας (χωρίς μνήμη) αποτελείται από 7 σύμβολα με τις πιθανότητες εμφάνισης που δίνονται στον παρακάτω πίνακα:
| Σύμβολο | s0 | s1 | s2 | s3 | s4 | s5 | s6 |
|---|---|---|---|---|---|---|---|
| Πιθανότητα Εμφάνισης | 0,0625 | 0,125 | 0,25 | 0,25 | 0,125 | 0,0625 | 0,125 |
α)Να κωδικοποιηθεί η συγκεκριμένη πηγή με χρήση του αλγορίθμου Huffman και να υπολογισθεί η αποδοτικότητα της κωδικοποίησης
β)Αν κωδικοποιήσετε την παραπάνω πηγή με ένα απλό κώδικα σταθερού μήκους τότε πως συγκρίνεται η αποδοτικότητα της κωδικοποίησης με αυτή που επιτεύχθηκε στο ερώτημα α;
Λύση
α)
[Σχήμα: δένδρο Huffman. Άνω μέρος: s2 (0,25) → 0,500 με ετικέτα 1· s3 (0,25) → 0,500 με ετικέτα 0· 0,500 → ρίζα με ετικέτα 0. Μέσο μέρος: s1 (0,125) → 0,250 με ετικέτα 0· s4 (0,125) → 0,250 με ετικέτα 1· 0,250 → 0,500 (μέσο) με ετικέτα 0· 0,500 (μέσο) → ρίζα με ετικέτα 1. Κάτω μέρος: s6 (0,125) → 0,250 (κάτω) με ετικέτα 0· s0 (0,0625) → 0,125 με ετικέτα 0· ετικέτα 1 κάτω αριστερά, κοντά στην s0· s5 (0,0625) → 0,125 με ετικέτα 1· 0,125 → 0,250 (κάτω) με ετικέτα 1· 0,250 (κάτω) → 0,500 (μέσο) με ετικέτα 1. Μεμονωμένη ετικέτα 1 κάτω δεξιά, χωρίς ακμή.]
| Σύμβολο | Κωδική Λέξη |
|---|---|
| s0 | 1110 |
| s1 | 100 |
| s2 | 00 |
| s3 | 01 |
| s4 | 101 |
| s5 | 1111 |
| s6 | 110 |