Για τον θεμελιωτή της Θεωρίας Πληροφορίας

Λίγοι άνθρωποι έχουν αφήσει τόσο βαθύ αποτύπωμα στο πέρασμά τους από τη γη όσο ο Κλωντ Έλγουντ Σάννον. Λίγοι άνθρωποι έχουν αφήσει τόσο βαθύ αποτύπωμα στο πέρασμά τους από τη γη όσο ο Κλωντ Έλγουντ Σάννον. Ξεχωρίζω τους αρχαίους Έλληνες κλασικούς, τον Γαλιλαίο, τον Νεύτωνα, τον Αϊνστάιν, τον Τούρινγκ. Ο Σάννον, ο οποίος δεν είναι ευρέως γνωστός στην Ελλάδα, είναι ο θεμελιωτής της Θεωρίας Πληροφορίας (Information Theory). Το έργο του Σάννον είναι πολυσχιδές και δύσκολα θα μπορούσε να αναλυθεί πλήρως σε ένα άρθρο. Είναι από τους ελάχιστους επιστήμονες οι οποίοι σε μία εργασία, σχεδόν από το μηδέν, (1) ποσοτικοποίησαν αφηρημένες έννοιες, (2) έθεσαν σημαντικά επιστημονικά προβλήματα και, το σημαντικότερο, (3) έλυσαν τα πιο βασικά από αυτά τα προβλήματα, θεμελιώνοντας μία νέα επιστημονική περιοχή, στην οποία, ταυτόχρονα, εμβάθυναν. Πιο συγκεκριμένα, σε ένα επιστημονικό άρθρο, το οποίο δημοσιεύτηκε το 1948,[2] ο Σάννον όρισε ποσοτικά την έννοια της πληροφορίας και έθεσε σε στέρεη μαθηματική βάση το πρόβλημα της αξιόπιστης επικοινωνίας (ως μετάδοσης πληροφορίας), το οποίο και έλυσε. Είναι εντυπωσιακό το ότι αυτά αποτελούν μόνο ένα μέρος της επιστημονικής συνεισφοράς του Σάννον (στην πραγματικότητα, ένα μέρος του άρθρου που δημοσιεύθηκε το 1948). Θα επικεντρωθώ στα τεχνικά χαρακτηριστικά του έργου του Σάννον[3] στην περιοχή της επικοινωνίας και στις εξαιρετικά σημαντικές συνέπειές του στην καθημερινή ζωή όλων μας. Αναγκαστικά, η προσέγγιση θα είναι απλουστευτική. Εξαιρετικές επιστημονικές προσεγγίσεις περιέχονται στα κλασικά βιβλία των T. Κόβερ, Τζ. Τόμας και Ρ. Τζ. Μακέλις.[4] Η πρώτη θεμελιώδης ποσότητα την οποία όρισε ο Σάννον είναι η εντροπία (entropy) ή αβεβαιότητα (uncertainty) ή πληροφορία (information) μίας τυχαίας ποσότητας. Ένα τυχαίο ενδεχόμενο εμπεριέχει μεγάλο ποσό πληροφορίας αν η πιθανότητα να συμβεί είναι πολύ μικρή. Για παράδειγμα, η πρόταση «μία ημέρα του Μαΐου ο ουρανός στα Χανιά είναι γαλάζιος» δεν εμπεριέχει μεγάλο ποσό πληροφορίας διότι δηλώνει κάτι το συνηθισμένο, ενώ η πρόταση «μία ημέρα του Μαΐου χιόνισε στα Χανιά» εμπεριέχει μεγάλο ποσό πληροφορίας διότι δηλώνει κάτι σπάνιο (και, σίγουρα, είναι πιο ενδιαφέρουσα). Η εντροπία μίας τυχαίας ποσότητας χαρακτηρίζει τη δυνατότητα συμπίεσης (compression) της τυχαίας ποσότητας, μετριέται σε bits (συντομογραφία του όρου binary digits), και ισούται με τον ελάχιστο αριθμό δυαδικών ψηφίων με τα οποία μπορούμε να αναπαραστήσουμε την τυχαία ποσότητα χωρίς “απώλεια πληροφορίας” (αυτό σημαίνει ότι η γνώση των δυαδικών ψηφίων επιτρέπει τον ακριβή προσδιορισμό της τιμής της τυχαίας ποσότητας). Τυχαίες ποσότητες με μεγάλη εντροπία εμπεριέχουν μεγάλο ποσό πληροφορίας και δεν είναι δυνατόν να συμπιεστούν σημαντικά, σε αντίθεση με τυχαίες ποσότητες με μικρή εντροπία. Η δεύτερη θεμελιώδης ποσότητα την οποία όρισε ο Σάννον είναι η αμοιβαία πληροφορία (mutual information) μεταξύ δύο (συσχετισμένων) τυχαίων ποσοτήτων, η οποία μετρά κατά πόσο η γνώση της μίας μειώνει την αβεβαιότητα σχετικά με την άλλη. Για παράδειγμα, η γνώση του ύψους ενός ανθρώπου μειώνει την αβεβαιότητα σχετικά με το βάρος του, με την έννοια ότι, αν γνωρίζω ότι ένας άνθρωπος είναι ψηλός, μπορώ να εκτιμήσω ότι το βάρος του θα είναι μεγαλύτερο από τον μέσο όρο βάρους. Όπως και η εντροπία, η αμοιβαία πληροφορία μετριέται σε bits. Η σημαντικότερη χρήση της αφορά τον χαρακτηρισμό της αξιόπιστης επικοινωνίας μέσω τηλεπικοινωνιακών συστημάτων. Για να κατανοήσουμε καλύτερα την έννοια της αμοιβαίας πληροφορίας και τη χρησιμότητά της στις τηλεπικοινωνίες, εισάγουμε την έννοια του τηλεπικοινωνιακού συστήματος. Ένα τηλεπικοινωνιακό σύστημα αποτελείται από ένα πομπό (transmitter), ένα δίαυλο ή κανάλι (channel), και ένα δέκτη (receiver). Στον πομπό παράγεται ένα μήνυμα το οποίο μεταδίδεται μέσω του καναλιού και φθάνει στον δέκτη. Ως τηλεπικοινωνιακά κανάλια μπορούν να δράσουν τα ενσύρματα μέσα (ενσύρματες επικοινωνίες), οι οπτικές ίνες (οπτικές επικοινωνίες), η ατμόσφαιρα (ασύρματες επικοινωνίες), το νερό (υποθαλάσσιες επικοινωνίες), κ.ά. Σε μία πιο θεωρητική προσέγγιση, ως τηλεπικοινωνιακό σύστημα ορίζουμε ένα σύστημα με μία τυχαία είσοδο (στον πομπό) και μία τυχαία έξοδο (στον δέκτη). Η τυχαιότητα στην είσοδο οφείλεται στο ότι το μήνυμα το οποίο μεταδίδει ο πομπός προέρχεται από μία πηγή πληροφορίας, η οποία το επιλέγει τυχαία από ένα σύνολο μηνυμάτων. Αυτό το σύνολο μηνυμάτων καλείται κωδικό βιβλίο (codebook) ή, απλά, κώδικας (code). Η τυχαιότητα στην έξοδο οφείλεται στην παρουσία θορύβου (noise) στον δέκτη. Αν δεν υπάρχει θόρυβος στον δέκτη, τότε, υπό κάποιες συνθήκες, μπορούμε να υποθέσουμε ότι η έξοδος του συστήματος ισούται με την είσοδό του. Ας υποθέσουμε ότι η πηγή πληροφορίας στον πομπό έχει επιλέξει ένα μήνυμα προς μετάδοση και ότι το μήνυμα έχει φθάσει στον δέκτη μέσω του τηλεπικοινωνιακού καναλιού. Το έργο του δέκτη είναι να ανακτήσει το μήνυμα που απέστειλε ο πομπός. Η είσοδος του συστήματος, η οποία είναι το μήνυμα που απέστειλε ο πομπός, είναι άγνωστη στον δέκτη, αλλά, γενικά, είναι συσχετισμένη με την έξοδο του συστήματος στον δέκτη – όπως είπαμε, η αβεβαιότητα οφείλεται στην ύπαρξη θορύβου στον δέκτη. Η επικοινωνία είναι επιτυχής όταν ο δέκτης, γνωρίζοντας μόνο την έξοδο του συστήματος και τον κώδικα, μπορεί να εκτιμήσει με μεγάλη αξιοπιστία το μήνυμα που απέστειλε ο πομπός, δηλαδή πρακτικά να μηδενίσει την αβεβαιότητά του σχετικά με την είσοδο του συστήματος. Σε ένα από τα θεμελιώδη αποτελέσματά του, το Θεώρημα Κωδικοποίησης Καναλιού (Channel Coding Theorem), o Σάννον απέδειξε ότι αυτό είναι δυνατό να συμβεί μόνο όταν η εντροπία της πηγής πληροφορίας στον πομπό είναι μικρότερη από την αμοιβαία πληροφορία ανάμεσα στην είσοδο και την έξοδο του τηλεπικοινωνικού συστήματος. Αυτή η ποσότητα καλείται χωρητικότητα (capacity) του συστήματος και αποτελεί τον μαγικό αριθμό κάθε τηλεπικοινωνιακού συστήματος. Αν ο θόρυβος στον δέκτη είναι “ασθενής,” τότε η είσοδος και η έξοδος του συστήματος είναι πολύ συσχετισμένες και η αμοιβαία πληροφορία τους, δηλαδή η χωρητικότητα του συστήματος, είναι μεγάλη. Στην αντίθετη περίπτωση, η χωρητικότητα του συστήματος είναι μικρή. Το Θεώρημα Κωδικοποίησης Καναλιού συνέδεσε τις δύο βασικές ποσότητες τις οποίες όρισε ο Σάννον και τους προσέδωσε τεράστια πρακτική σημασία. Πιο συγκεκριμένα, ο Σάννον μελέτησε τα βασικότερα μοντέλα τηλεπικοινωνιακών συστημάτων, υπολόγισε τη χωρητικότητά τους, και απέδειξε ότι, αν ο ρυθμός μετάδοσης πληροφορίας, ο οποίος ισούται με την εντροπία της πηγής πληροφορίας, είναι μικρότερος από τη χωρητικότητα του τηλεπικοινωνιακού συστήματος, τότε υπάρχει κώδικας η χρήση του οποίου μπορεί να εξασφαλίσει αυθαίρετα αξιόπιστη επικοινωνία. Αντίθετα, αν ο ρυθμός μετάδοσης πληροφορίας είναι μεγαλύτερος από την χωρητικότητα του συστήματος, τότε δεν είναι δυνατόν να καταστεί αξιόπιστη η επικοινωνία (δηλαδή, δεν υπάρχει κατάλληλος κώδικας). Η βαθύτερη μελέτη της απόδειξης του Σάννον οδηγεί στην διαπίστωση ότι η συντριπτική πλειονότητα κατάλληλα κατασκευασμένων κωδίκων μπορεί να εξασφαλίσει αξιόπιστη επικοινωνία με ρυθμούς μετάδοσης πληροφορίας πολύ κοντά στην χωρητικότητα του συστήματος. Μία επιφανειακή μετάφραση αυτής της διαπίστωσης είναι το ότι «ο Σάννον έλυσε το πρόβλημα της αξιόπιστης επικοινωνίας με ρυθμούς μετάδοσης πληροφορίας πολύ κοντά στην χωρητικότητα.» Αυτό δεν είναι αληθές, διότι η αποκωδικοποίηση των κωδίκων που χρησιμοποίησε ο Σάννον είναι εξαιρετικά πολύπλοκη, πέραν των υπολογιστικών δυνατοτήτων ακόμη και των πιο εξελιγμένων υπερυπολογιστών. Συνεπώς, τι συνέβη στην πράξη; Στην πράξη, ο Σάννον έθεσε τα άνω όρια στους επιστήμονες που ασχολούνται με τη Θεωρία Κωδικοποίησης (Coding Theory), ορίζοντας και υπολογίζοντας τις χωρητικότητες των διαφόρων τηλεπικοινωνιακών συστημάτων. Από το 1948 μέχρι σήμερα, μία μεγάλη ομάδα εξαιρετικών επιστημόνων, μετά από τεράστιες προσπάθειες και χρησιμοποιώντας ιδιοφυώς μία πληθώρα μαθηματικών εργαλείων, κατόρθωσε να αναπτύξει κώδικες, για διάφορα είδη τηλεπικοινωνιακών συστημάτων, με αποδεκτή πολυπλοκότητα αποκωδικοποίησης, και ρυθμούς μετάδοσης πληροφορίας πολύ κοντά στις χωρητικότητες των τηλεπικοινωνιακών συστημάτων (ως χαρακτηριστικά παραδείγματα αναφέρω τους τούρμπο κώδικες (turbo codes) και τους LDPC κώδικες[5]). Οι επιστήμονες αυτοί συμπλήρωσαν το έργο του Σάννον και συνέβαλαν καθοριστικά στην γένεση της λεγόμενης 4ης Βιομηχανικής Επανάστασης, δηλαδή της Επανάστασης της Πληροφορίας. Ο Σάννον ασχολήθηκε, κυρίως, με τηλεπικοινωνιακά συστήματα με ένα πομπό και ένα δέκτη. Οι ιδέες του γενικεύτηκαν και εφαρμόστηκαν σε συστήματα με πολλούς πομπούς ή/και πολλούς δέκτες. Η αντίστοιχη ερευνητική περιοχή καλείται Θεωρία Πληροφορίας Δικτύων (Network Information Theory). Επιστημονικές περιοχές στις οποίες οι ιδέες του Σάννον είχαν σημαντική επίδραση είναι, μεταξύ άλλων, η Θεωρία Πολυπλοκότητας, η Στατιστική, η Βιολογία, η Ανάλυση και Διαχείριση Δεδομένων, και η Διαχείριση Κεφαλαίων.[6] Όπως ίσως συμβαίνει σε κάθε επιστημονική περιοχή, υπήρξαν στιγμές στο παρελθόν κατά τις οποίες σημαντική μερίδα των επιστημόνων της περιοχής πίστεψε ότι «η Θεωρία Πληροφορίας είναι νεκρή!». Αυτό συνέβη διότι υπήρξε η λανθασμένη αντίληψη ότι τα βασικά προβλήματα της περιοχής είχαν τεθεί και λυθεί, με ελάχιστα πολύ δύσκολα άλυτα προβλήματα να ταλαιπωρούν γενιές νέων επιστημόνων. Όμως, η πραγματική ζωή και κάποια φωτισμένα μυαλά πάντα, τελικά, κατάφερναν να θέτουν και να λύνουν νέα σημαντικά προβλήματα, επιδρώντας αποφασιστικά στη ζωή όλων μας. Ένα σχετικά πρόσφατο τέτοιο παράδειγμα, το οποίο αναδεικνύει την εξαιρετικά σημαντική επίδραση της Θεωρίας Πληροφορίας στις σύγχρονες ασύρματες τηλεπικοινωνίες και, εντέλει, στην καθημερινή ζωή μας, αποτελεί ο υπολογισμός της χωρητικότητας ενός ασύρματου τηλεπικοινωνιακού συστήματος με πολλές κεραίες στον πομπό ή/και στον δέκτη – ένα τέτοιο σύστημα καλείται πολυκεραιακό σύστημα (multi-antenna system). Το πρόβλημα αυτό ήταν εξαιρετικά σημαντικό στα μέσα της δεκαετίας του 1990 διότι τα τότε συστήματα, τα οποία συνήθως είχαν μία κεραία στον πομπό και μία κεραία στον δέκτη, δεν ήταν σε θέση να ικανοποιήσουν τις αυξανόμενες απαιτήσεις για γρήγορη και αξιόπιστη μετάδοση πληροφορίας που απέρρεαν από την τεράστια επιτυχία της κινητής τηλεφωνίας δεύτερης γενιάς. Υπήρχαν σημαντικές ενδείξεις ότι τα πολυκεραιακά συστήματα μπορούσαν να επιτύχουν αυξημένους ρυθμούς μετάδοσης πληροφορίας, δεν ήταν όμως γνωστά τα θεωρητικά όριά τους. Το 1998, ερευνητές από τα Bell Labs, ακολουθώντας τον δρόμο που χάραξε Σάννον ‒κάτι που είχε γίνει πολλές φορές το παρελθόν, από άλλους ερευνητές, σε άλλα προβλήματα‒ υπολόγισαν την χωρητικότητα αυτών των συστημάτων, αναδεικνύοντας τη σημαντικότατη αύξηση των ρυθμών αξιόπιστης μετάδοσης πληροφορίας που συνεπάγεται η χρήση τους.[7] Έτσι ξεκίνησε μία επανάσταση στον τομέα των ασύρματων επικοινωνιών, με στόχο την ανάπτυξη κωδίκων για την επίτευξη αυτών των αυξημένων ρυθμών επικοινωνίας, η οποία, μετά από περίπου μία δεκαετία εντατικής δουλειάς από χιλιάδες επιστήμονες, οδήγησε στα σύγχρονα έξυπνα ασύρματα τηλέφωνα και δίκτυα. Αξίζει να αναφέρω ότι νέοι τρόποι ασύρματης επικοινωνίας, οι οποίοι δεν έχουν, προς το παρόν, χρησιμοποιηθεί ευρέως στην πράξη, αλλά αναμένεται να κυριαρχήσουν στο άμεσο μέλλον, όπως η ευκαιριακή επικοινωνία (opportunistic communication),[8] που ένας χρήστης του δικτύου μεταδίδει όταν η χωρητικότητα του καναλιού του είναι μεγαλύτερη από αυτή των άλλων χρηστών, και η συνεργατική επικοινωνία (cooperative communication)[9], όπου διάφοροι χρήστες του δικτύου συνεργάζονται για να μεταδώσουν ένα μήνυμα, με στόχο να βελτιώσουν την απόδοση του καθενός αλλά και τη συνολική απόδοση του δικτύου, έχουν τις ρίζες τους στη Θεωρία Πληροφορίας. Η Θεωρία Πληροφορίας, γενικά, αγνοεί το περιεχόμενο του μηνύματος. Πολύ πρόσφατα, έχουν ξεκινήσει συντονισμένες προσπάθειες επέκτασής της ούτως ώστε να λαμβάνονται υπ’ όψιν η δομή (structure), ο χρόνος, ο χώρος, και η σημασιολογία (semantics) του μηνύματος.[10] Αν οι προσπάθειες αυτές ευδοκιμήσουν, αναμένεται να υπάρξουν σημαντικές συνέπειες σε επιστημονικές περιοχές που είτε δεν υπήρχαν είτε βρίσκονταν σε αρχικά στάδια όταν ο Σάννον εισήγαγε τη Θεωρία Πληροφορίας, όπως τα δίκτυα κινητών τηλεπικοινωνιών, η βιοτεχνολογία και η νευροεπιστήμη (neuroscience), η θεωρία κβαντικών υπολογισμών (quantum computing), τα κοινωνικά δίκτυα κ.ά. Είμαι βαθιά πεπεισμένος ότι με το πέρασμα του χρόνου το αποτύπωμα του Κλωντ Σάννον πάνω στη γη θα βαθαίνει και ότι οι ιδέες του θα επηρεάζουν όλο και πιο πολύ, ίσως με αναπάντεχους τρόπους, την ανθρώπινη ζωή και σκέψη μέχρι το απώτατο μέλλον. Ευτυχώς, η Θεωρία Πληροφορίας είναι ζωντανή και είναι γύρω μας! [1] Ευχαριστώ τον Αντώνη Ευφραιμίδη για την προτροπή να γράψω αυτό το άρθρο και τους Γιάννη Κοντογιάννη, Σταύρο Τουμπή και Δημήτρη Τουμπακάρη για τα πολύ χρήσιμα σχόλιά τους. [2] C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, July and October 1948, pp. 379-423 and 623-656. [3] Τα άπαντα του Σάννον περιέχονται στον τόμο A. Wyner, N. Sloane, Claude Elwood Shannon: Collected papers, Wiley-IEEE Press, 1993. [4] T. Cover, J. Thomas, Elements of Information Theory, Wiley-Interscience, 22006 (κλασικό βιβλίο Θεωρίας Πληροφορίας με αρκετές προεκτάσεις) και R. J. McEliece, The Theory of Information and Coding, Cambridge University Press, 2004 (εξαιρετικό βιβλίο Θεωρίας Πληροφορίας και Κωδίκων). [5] T. Richardson, R. Urbanke, Modern Coding Theory, Cambridge University Press, 2008. [6] T. Cover, J. Thomas, ό.π.. [7] G. J. Foschini, M. J. Gans, “On limits of Wireless Communications in a Fading Environment when Using Multiple Antennas,” Wireless Personal Communications, 1998 και E. Telatar, “Capacity of Multi-antenna Gaussian Channels,” Transactions of Emerging Telecommunications Technology, 1999. [8] D. Tse, “Opportunistic Communication: From Theory to Practice,” Viterbi Conference, March 2005, https://web.stanford.edu/~dntse/papers/viterbi05.pdf [9] G. Kramer, I. Maric, and R. D. Yates, “Cooperative Communication,” Foundations and Trends in Networking, NOW Publishers, 2007. [10] Neil Savage, “Information Theory after Shannon,” Science DOI:10.1145/1897816.1897822, https://www.cs.purdue.edu/homes/spa/cacm-soi.pdf

Για τον θεμελιωτή της Θεωρίας Πληροφορίας

Σύνδεση