Ενότητα 4 - Θεωρία Πληροφορίας και Χωρητικότητα Καναλιού
Περιγραφή εννοιών Θεωρίας Πληροφορίας όπως από κοινού εντροπία, υπο συνθήκη εντροπία και αμοιβαία πληροφορία. Περιγραφή των εννοιών κωδικοποίησης και χωρητικότητας καναλιού και που αποσκοπούν.
Ενότητα 4 - Θεωρία Πληροφορίας και Χωρητικότητα Καναλιού.pptx
Θεωρία πληροφορίας - Κωδικοποίηση καναλιού

Η διάλεξη ξεκινάει με μια αναφορά σε ένα μειονέκτημα του αλγορίθμου Huffman. Στην συνέχεια, παρουσιάζεται το πρόβλημα της κωδικοποίησης καναλιού και τα ερωτήματα που μπορεί να απαντήσει. Παρουσιάζεται ένα βασικό σύστημα επικοινωνίας και περιγράφονται τρόποι διάκρισης των καναλιών μετάδοσης. Ορίζονται τα διακριτά κανάλια χωρίς μνήμη και δίνεται ένα παράδειγμα. Περιγράφονται οι πιθανότητες μετάβασης, οι από κοινού πιθανότητες εισόδου/εξόδου, οι πιθανότητες σφάλματος και παρουσιάζεται ένα παράδειγμα κατανόησης των παραπάνω.

Χωρητικότητα καναλιού μέσω της θεωρίας πληροφορίας (Μέρος Α)

Προκειμένου να απαντηθεί το ερώτημα αν είναι δυνατόν να έχουμε μετάδοση χωρίς σφάλματα μέσα από ένα κανάλι που εισάγει θόρυβο, εξετάζουμε τη μετάδοση μιας δυαδικής πηγής μέσα από ένα δυαδικό συμμετρικό και χωρίς μνήμη κανάλι. Για τη μελέτη μας αυτή, υπενθυμίζουμε τον ορισμό της εντροπίας και εισάγουμε τις έννοιες της από κοινού (συνδυασμένης) και της υπό συνθήκη εντροπίας. Στη συνέχεια, δίνεται η έννοια της αμοιβαίας πληροφορίας και γίνεται μια σύνδεσή της με τη μελέτη του καναλιού που μας ενδιαφέρει. Τέλος, ορίζεται η χωρητικότητα ενός καναλιού ως η μέγιστη τιμή της αμοιβαίας πληροφορίας για όλες τις δυνατές κατανομές εισόδου.

Χωρητικότητα καναλιού μέσω της θεωρίας πληροφορίας (Μέρος Β)

Ο υπολογισμός της χωρητικότητας ενός διακριτού καναλιού χωρίς μνήμη απαιτεί την μεγιστοποίηση μιας συνάρτησης (συνήθως) πολλών μεταβλητών, και μάλιστα υπό περιορισμούς. Για το λόγο αυτό, σπάνια μπορούμε να καταλήξουμε σε κλειστές εκφράσεις που δίνουν τη χωρητικότητα διακριτών καναλιών. Ως ένα παράδειγμα, κλειστή μορφή μπορούμε να βρούμε για τη χωρητικότητα του δυαδικού συμμετρικού καναλιού χωρίς μνήμη. Σε κάθε περίπτωση, το δεύτερο θεώρημα του Shannon μας δίνει τη συνθήκη για μετάδοση χωρίς σφάλματα από ένα κανάλι. Για την περίπτωση ενός συνεχούς ζωνοπεριορισμένου καναλιού που εισάγει λευκό προσθετικό θόρυβο κανονικής κατανομής (Gauss), το θεώρημα Shannon Hartley μας δίνει με κλειστό τύπο τη χωρητικότητά του. Τον τύπο αυτό μπορούμε να τον εκφράσουμε και συναρτήσει της πυκνότητας φάσματος ισχύος του θορύβου. Η χωρητικότητα αυτή αποτελεί και ένα άνω φράγμα της χωρητικότητας για το διακριτό κανάλι που περιλαμβάνει το εξεταζόμενο συνεχές κανάλι ως μέρος του. Ακολουθεί ένα παράδειγμα το οποίο παρουσιάζει την ανταλλαγή (trade off) ανάμεσα στην ισχύ μετάδοσης και το εύρος ζώνης, με μια ενδιαφέρουσα σύγκριση ανάμεσα στις αναλογικές και τις ψηφιακές επικοινωνίες.

Χωρητικότητα καναλιού (Φροντιστήριο - Μέρος Α)

Άσκηση 1: Σε ένα δυαδικό συμμετρικό κανάλι εισέρχονται σύμβολα με ρυθμό 1000 σύμβολα ανά δευτερόλεπτο. Τα σύμβολα είναι ισοπίθανα. Για τις περιπτώσεις όπου η πιθανότητα σωστής μετάδοσης p ενός συμβόλου μέσα από το κανάλι, p=0.9, p=0.8 και p=0.6, υπολογίζουμε το ρυθμό μετάδοσης πληροφορίας μέσα από το κανάλι. Ο ζητούμενος ρυθμός δίνεται ως το γινόμενο της αμοιβαίας πληροφορίας με το ρυθμό της εισόδου σε σύμβολα ανά δευτερόλεπτο. Υπολογίζουμε την αμοιβαία πληροφορία μέσω της εντροπίας της πηγής και της υπό συνθήκη εντροπίας της εισόδου για δεδομένη έξοδο. Υπολογίζουμε τις από κοινού πιθανότητες εισόδου εξόδου μέσω του κανόνα του Bayes. Υπολογίζουμε τις υπό συνθήκη πιθανότητες χρησιμοποιώντας τον κανόνα της αλυσίδας. Άσκηση 2: Υπολογίζουμε τη χωρητικότητα ενός δυαδικού συμμετρικού καναλιού χωρίς μνήμη. Η χωρητικότητα δίνεται ως η μέγιστη τιμή της αμοιβαίας πληροφορίας ως προς όλες τις πιθανές κατανομές πιθανοτήτων των συμβόλων εισόδου. Η μεγιστοποίηση γίνεται θέτωντας την πρώτη παράγωγο της συνάρτησης την οποία μελετάμε ίση με το μηδέν.

Χωρητικότητα καναλιού (Φροντιστήριο - Μέρος Β)

Άσκηση 1: Μια πηγή μπορεί να παράγει δύο σύμβολα, x1 και x2. Τα σύμβολα αυτά μεταδίδονται μέσα από ένα κανάλι το οποίο αντιστοιχίζει το x1 με πιθανότητα 1/2 στο y1, το x1 με πιθανότητα 1/2 στο y2 και τέλος το x2 στο σύμβολο εξόδου y3 με πιθανότητα 1. Υπολογίζουμε τη χωρητικότητα του καναλιού αυτού μέσω της μεγιστοποίησης της αμοιβαίας πληροφορίας ως προς όλες τις κατανομές πιθανοτήτων για τα σύμβολα εισόδου. Η αμοιβαία πληροφορία υπολογίζεται χρησιμοποιώντας την εντροπία της πηγής και την υπό συνθήκη εντροπία της εισόδου για δοσμένη έξοδο. Άσκηση 2: Μας δίνεται μια από κοινού συνάρτηση πυκνότητας πιθανότητας δύο τυχαίων μεταβλητών X και Y, η οποία εξαρτάται από μια άγνωστη παράμετρο K. Χρησιμοποιώντας την ιδιότητα πως το ορισμένο ολοκλήρωμα μιας συνάρτησης πυκνότητας πιθανότητας σε όλο το πεδίο ορισμού της θα πρέπει να είναι μονάδα, υπολογίζουμε την τιμή της παραμέτρου K. Άσκηση 3: Πρέπει να δείξουμε πως η τυχαία μεταβλητή X είναι κανονική. Για να υπολογίσουμε την συνάρτηση πυκνότητας πιθανότητας της τυχαίας μεταβλητής X γνωρίζοντας την από κοινού συνάρτηση πυκνότητας πιθανότητας των X και Y, υπολογίζουμε το ορισμένο ολοκλήρωμα της από κοινού pdf πάνω στο πεδίο ορισμού της Y. Υπολογίζοντας την έκφραση που προκύπτει, αναγνωρίζουμε πως έχει τη μορφή μιας κανονικής pdf με μέση τιμή 0 και διασπορά 1. Άσκηση 4: Πρέπει να εξετάσουμε αν οι X και Y είναι ανεξάρτητες. Θα εξετάσουμε αν η από κοινού pdf είναι ίση με το γινόμενο των επιμέρους pdf. Εύκολα παρατηρούμε πως όταν οι τυχαίες μεταβλητές X και Y έχουν αντίθετα πρόσημα, τότε η απο κοινού pdf είναι μηδέν. Όμως, το γινόμενο των επιμέρους pdf δεν είναι μηδέν στις περιοχές αυτές. Επομένως οι τυχαίες μεταβλητές δεν είναι ανεξάρτητες.