Τα καταφέραμε!
"Ο σκοπός αυτού του μαθήματος είναι να σας προετοιμάσει για το τεχνικό σας μέλλον."
Γεια σου, Χαμπρ. Θυμηθείτε το φοβερό άρθρο (+219, 2588 σελιδοδείκτες, 429 χιλιάδες αναγνώσεις);
Οπότε Hamming (ναι, ναι, αυτοέλεγχος και αυτοδιόρθωση ) υπάρχει ένα σύνολο , που γράφτηκε με βάση τις διαλέξεις του. Το μεταφράζουμε, γιατί ο άνθρωπος λέει τη γνώμη του.
Αυτό είναι ένα βιβλίο όχι μόνο για την πληροφορική, είναι ένα βιβλίο για το στυλ σκέψης των απίστευτα κουλ ανθρώπων. «Δεν είναι απλώς μια ώθηση θετικής σκέψης. περιγράφει τις συνθήκες που αυξάνουν τις πιθανότητες να κάνεις σπουδαία δουλειά».
Ευχαριστώ τον Andrey Pakhomov για τη μετάφραση.
Η Θεωρία της Πληροφορίας αναπτύχθηκε από τον C. E. Shannon στα τέλη της δεκαετίας του 1940. Η διοίκηση της Bell Labs επέμεινε να την ονομάσει «Θεωρία της Επικοινωνίας» επειδή... αυτό είναι ένα πολύ πιο ακριβές όνομα. Για προφανείς λόγους, το όνομα «Information Theory» έχει πολύ μεγαλύτερη απήχηση στο κοινό, γι' αυτό και το επέλεξε η Shannon, και είναι το όνομα που γνωρίζουμε μέχρι σήμερα. Το ίδιο το όνομα υποδηλώνει ότι η θεωρία ασχολείται με τις πληροφορίες, γεγονός που την καθιστά σημαντική καθώς προχωράμε βαθύτερα στην εποχή της πληροφορίας. Σε αυτό το κεφάλαιο, θα θίξω πολλά κύρια συμπεράσματα από αυτή τη θεωρία, θα παράσχω όχι αυστηρές, αλλά μάλλον διαισθητικές αποδείξεις ορισμένων μεμονωμένων διατάξεων αυτής της θεωρίας, ώστε να καταλάβετε τι είναι στην πραγματικότητα η «Θεωρία της Πληροφορίας», όπου μπορείτε να την εφαρμόσετε και πού όχι.
Πρώτα απ 'όλα, τι είναι η «πληροφορία»; Ο Shannon εξισώνει τις πληροφορίες με την αβεβαιότητα. Επέλεξε τον αρνητικό λογάριθμο της πιθανότητας ενός συμβάντος ως ποσοτικό μέτρο των πληροφοριών που λαμβάνετε όταν συμβαίνει ένα συμβάν με πιθανότητα p. Για παράδειγμα, αν σας πω ότι ο καιρός στο Λος Άντζελες είναι ομιχλώδης, τότε το p είναι κοντά στο 1, κάτι που πραγματικά δεν μας δίνει πολλές πληροφορίες. Αλλά αν πω ότι βρέχει στο Μοντερέι τον Ιούνιο, θα υπάρχει αβεβαιότητα στο μήνυμα και θα περιέχει περισσότερες πληροφορίες. Ένα αξιόπιστο συμβάν δεν περιέχει καμία πληροφορία, αφού το αρχείο καταγραφής 1 = 0.
Ας το δούμε αυτό με περισσότερες λεπτομέρειες. Ο Shannon πίστευε ότι το ποσοτικό μέτρο της πληροφορίας θα πρέπει να είναι μια συνεχής συνάρτηση της πιθανότητας ενός γεγονότος p, και για ανεξάρτητα γεγονότα θα πρέπει να είναι αθροιστικό - η ποσότητα των πληροφοριών που λαμβάνεται ως αποτέλεσμα της εμφάνισης δύο ανεξάρτητων γεγονότων πρέπει να είναι ίση με το ο όγκος των πληροφοριών που ελήφθησαν ως αποτέλεσμα της εμφάνισης ενός κοινού γεγονότος. Για παράδειγμα, το αποτέλεσμα μιας ρίψης ζαριών και ενός νομίσματος αντιμετωπίζονται συνήθως ως ανεξάρτητα γεγονότα. Ας μεταφράσουμε τα παραπάνω στη γλώσσα των μαθηματικών. Αν I (p) είναι η ποσότητα των πληροφοριών που περιέχονται σε ένα γεγονός με πιθανότητα p, τότε για ένα κοινό γεγονός που αποτελείται από δύο ανεξάρτητα γεγονότα x με πιθανότητα p1 και y με πιθανότητα p2 λαμβάνουμε
(το x και το y είναι ανεξάρτητα γεγονότα)
Αυτή είναι η συναρτησιακή εξίσωση Cauchy, η οποία ισχύει για όλα τα p1 και p2. Για να λύσετε αυτή τη συναρτησιακή εξίσωση, υποθέστε ότι
p1 = p2 = p,
αυτό δίνει
Αν p1 = p2 και p2 = p τότε
και τα λοιπά. Επέκταση αυτής της διαδικασίας χρησιμοποιώντας την τυπική μέθοδο για εκθετικά, για όλους τους ρητούς αριθμούς m/n ισχύει το ακόλουθο
Από την υποτιθέμενη συνέχεια του μέτρου πληροφοριών, προκύπτει ότι η λογαριθμική συνάρτηση είναι η μόνη συνεχής λύση στη συναρτησιακή εξίσωση Cauchy.
Στη θεωρία πληροφοριών, είναι σύνηθες να παίρνουμε τη βάση του λογαρίθμου ως 2, επομένως μια δυαδική επιλογή περιέχει ακριβώς 1 bit πληροφοριών. Επομένως, οι πληροφορίες μετρώνται με τον τύπο
Ας κάνουμε μια παύση και ας καταλάβουμε τι έγινε παραπάνω. Πρώτα απ 'όλα, δεν ορίσαμε την έννοια της «πληροφορίας», απλώς ορίσαμε τον τύπο για το ποσοτικό της μέτρο.
Δεύτερον, αυτό το μέτρο υπόκειται σε αβεβαιότητα και, παρόλο που είναι εύλογα κατάλληλο για μηχανές —για παράδειγμα, τηλεφωνικά συστήματα, ραδιόφωνο, τηλεόραση, υπολογιστές κ.λπ.—δεν αντικατοπτρίζει την κανονική ανθρώπινη στάση απέναντι στις πληροφορίες.
Τρίτον, αυτό είναι ένα σχετικό μέτρο, εξαρτάται από την τρέχουσα κατάσταση των γνώσεών σας. Εάν κοιτάξετε μια ροή "τυχαίων αριθμών" από μια γεννήτρια τυχαίων αριθμών, υποθέτετε ότι κάθε επόμενος αριθμός είναι αβέβαιος, αλλά εάν γνωρίζετε τον τύπο για τον υπολογισμό των "τυχαίων αριθμών", ο επόμενος αριθμός θα είναι γνωστός και επομένως δεν θα περιέχουν πληροφορίες.
Έτσι, ο ορισμός της πληροφορίας από τον Shannon είναι κατάλληλος για μηχανές σε πολλές περιπτώσεις, αλλά δεν φαίνεται να ταιριάζει στην ανθρώπινη κατανόηση της λέξης. Αυτός είναι ο λόγος που η «Θεωρία της Πληροφορίας» θα έπρεπε να είχε ονομαστεί «Θεωρία της Επικοινωνίας». Ωστόσο, είναι πολύ αργά για να αλλάξουμε τους ορισμούς (που έδωσαν στη θεωρία την αρχική της δημοτικότητα και που εξακολουθούν να κάνουν τους ανθρώπους να πιστεύουν ότι αυτή η θεωρία ασχολείται με «πληροφορίες»), επομένως πρέπει να ζήσουμε με αυτούς, αλλά ταυτόχρονα πρέπει να κατανοήστε ξεκάθαρα πόσο απέχει ο ορισμός της πληροφορίας του Shannon από τη συνηθισμένη σημασία τους. Οι πληροφορίες του Shannon ασχολούνται με κάτι εντελώς διαφορετικό, δηλαδή την αβεβαιότητα.
Εδώ είναι κάτι που πρέπει να σκεφτείτε όταν προτείνετε οποιαδήποτε ορολογία. Πώς ένας προτεινόμενος ορισμός, όπως ο ορισμός της πληροφορίας του Shannon, συμφωνεί με την αρχική σας ιδέα και πόσο διαφορετικός είναι; Δεν υπάρχει σχεδόν κανένας όρος που να αντικατοπτρίζει ακριβώς το προηγούμενο όραμά σας για μια έννοια, αλλά τελικά, είναι η χρησιμοποιούμενη ορολογία που αντικατοπτρίζει το νόημα της έννοιας, επομένως η επισημοποίηση κάτι μέσω σαφών ορισμών εισάγει πάντα κάποιο θόρυβο.
Θεωρήστε ένα σύστημα του οποίου το αλφάβητο αποτελείται από σύμβολα q με πιθανότητες pi. Σε αυτήν την περίπτωση μέση ποσότητα πληροφοριών στο σύστημα (η αναμενόμενη τιμή του) ισούται με:
Αυτό ονομάζεται εντροπία του συστήματος με κατανομή πιθανότητας {pi}. Χρησιμοποιούμε τον όρο «εντροπία» επειδή η ίδια μαθηματική μορφή εμφανίζεται στη θερμοδυναμική και τη στατιστική μηχανική. Αυτός είναι ο λόγος για τον οποίο ο όρος «εντροπία» δημιουργεί μια ορισμένη αύρα σημασίας γύρω του, η οποία τελικά δεν δικαιολογείται. Η ίδια μαθηματική μορφή σημειογραφίας δεν συνεπάγεται την ίδια ερμηνεία των συμβόλων!
Η εντροπία της κατανομής πιθανοτήτων παίζει σημαντικό ρόλο στη θεωρία κωδικοποίησης. Η ανισότητα Gibbs για δύο διαφορετικές κατανομές πιθανοτήτων pi και qi είναι μία από τις σημαντικές συνέπειες αυτής της θεωρίας. Πρέπει λοιπόν να το αποδείξουμε
Η απόδειξη βασίζεται σε ένα προφανές γράφημα, Εικ. 13.Ι, που δείχνει ότι
και η ισότητα επιτυγχάνεται μόνο όταν x = 1. Ας εφαρμόσουμε την ανισότητα σε κάθε όρο του αθροίσματος από την αριστερή πλευρά:
Εάν το αλφάβητο ενός συστήματος επικοινωνίας αποτελείται από σύμβολα q, τότε λαμβάνοντας την πιθανότητα μετάδοσης κάθε συμβόλου qi = 1/q και αντικαθιστώντας το q, λαμβάνουμε από την ανισότητα Gibbs
Εικόνα 13.Ι
Αυτό σημαίνει ότι εάν η πιθανότητα μετάδοσης όλων των συμβόλων q είναι η ίδια και ίση με - 1 / q, τότε η μέγιστη εντροπία είναι ίση με ln q, διαφορετικά ισχύει η ανισότητα.
Στην περίπτωση ενός μοναδικά αποκωδικοποιήσιμου κωδικού, έχουμε την ανισότητα του Kraft
Τώρα αν ορίσουμε ψευδοπιθανότητες
όπου φυσικά = 1, που προκύπτει από την ανισότητα του Gibbs,
και εφαρμόστε λίγη άλγεβρα (θυμηθείτε ότι K ≤ 1, ώστε να ρίξουμε τον λογαριθμικό όρο και ίσως να ενισχύσουμε την ανισότητα αργότερα), παίρνουμε
όπου L είναι το μέσο μήκος του κωδικού.
Έτσι, η εντροπία είναι το ελάχιστο όριο για οποιονδήποτε κωδικό χαρακτήρα προς σύμβολο με μέσο μήκος κωδικής λέξης L. Αυτό είναι το θεώρημα του Shannon για ένα κανάλι χωρίς παρεμβολές.
Τώρα εξετάστε το κύριο θεώρημα σχετικά με τους περιορισμούς των συστημάτων επικοινωνίας στα οποία οι πληροφορίες μεταδίδονται ως ρεύμα ανεξάρτητων δυαδικών ψηφίων και υπάρχει θόρυβος. Εννοείται ότι η πιθανότητα σωστής μετάδοσης ενός bit είναι P > 1/2 και η πιθανότητα να αντιστραφεί η τιμή του bit κατά τη μετάδοση (θα προκύψει σφάλμα) είναι ίση με Q = 1 - P. Για λόγους ευκολίας, Ας υποθέσουμε ότι τα σφάλματα είναι ανεξάρτητα και η πιθανότητα σφάλματος είναι η ίδια για κάθε απεσταλμένο bit - δηλαδή υπάρχει "λευκός θόρυβος" στο κανάλι επικοινωνίας.
Ο τρόπος με τον οποίο έχουμε μια μεγάλη ροή από n bit κωδικοποιημένα σε ένα μήνυμα είναι η n-διάστατη επέκταση του κώδικα ενός bit. Θα προσδιορίσουμε την τιμή του n αργότερα. Θεωρήστε ένα μήνυμα που αποτελείται από n-bits ως ένα σημείο στον n-διάστατο χώρο. Δεδομένου ότι έχουμε ένα χώρο n-διαστάσεων - και για απλότητα θα υποθέσουμε ότι κάθε μήνυμα έχει την ίδια πιθανότητα εμφάνισης - υπάρχουν M πιθανά μηνύματα (το M θα οριστεί επίσης αργότερα), επομένως η πιθανότητα οποιουδήποτε μηνύματος αποστέλλεται είναι
(αποστολέας)
Πρόγραμμα 13.II
Στη συνέχεια, εξετάστε την ιδέα της χωρητικότητας του καναλιού. Χωρίς να υπεισέλθω σε λεπτομέρειες, η χωρητικότητα καναλιού ορίζεται ως η μέγιστη ποσότητα πληροφοριών που μπορεί να μεταδοθεί αξιόπιστα μέσω ενός καναλιού επικοινωνίας, λαμβάνοντας υπόψη τη χρήση της πιο αποτελεσματικής κωδικοποίησης. Δεν υπάρχει κανένα επιχείρημα ότι περισσότερες πληροφορίες μπορούν να μεταδοθούν μέσω ενός καναλιού επικοινωνίας από την ικανότητά του. Αυτό μπορεί να αποδειχθεί για ένα δυαδικό συμμετρικό κανάλι (το οποίο χρησιμοποιούμε στην περίπτωσή μας). Η χωρητικότητα καναλιού, κατά την αποστολή bits, καθορίζεται ως
όπου, όπως και πριν, P είναι η πιθανότητα να μην υπάρχει σφάλμα σε κανένα απεσταλμένο bit. Κατά την αποστολή n ανεξάρτητα bit, η χωρητικότητα του καναλιού δίνεται από
Εάν βρισκόμαστε κοντά στη χωρητικότητα του καναλιού, τότε πρέπει να στείλουμε σχεδόν αυτόν τον όγκο πληροφοριών για καθένα από τα σύμβολα ai, i = 1, ..., M. Λαμβάνοντας υπόψη ότι η πιθανότητα εμφάνισης κάθε συμβόλου ai είναι 1 / M, παίρνουμε
όταν στέλνουμε οποιοδήποτε από τα M εξίσου πιθανά μηνύματα ai, έχουμε
Όταν αποστέλλονται n bit, αναμένουμε να προκύψουν σφάλματα nQ. Στην πράξη, για ένα μήνυμα που αποτελείται από n-bit, θα έχουμε περίπου nQ σφάλματα στο ληφθέν μήνυμα. Για μεγάλο n, σχετική παραλλαγή (παραλλαγή = πλάτος κατανομής, )
η κατανομή του αριθμού των σφαλμάτων θα γίνεται όλο και πιο περιορισμένη όσο αυξάνεται το n.
Έτσι, από την πλευρά του πομπού, παίρνω το μήνυμα ai για να στείλω και σχεδιάζω μια σφαίρα γύρω του με ακτίνα
που είναι ελαφρώς μεγαλύτερο κατά ποσό ίσο με e2 από τον αναμενόμενο αριθμό σφαλμάτων Q, (Εικόνα 13.II). Εάν το n είναι αρκετά μεγάλο, τότε υπάρχει μια αυθαίρετα μικρή πιθανότητα να εμφανιστεί ένα σημείο μηνύματος bj στην πλευρά του δέκτη που εκτείνεται πέρα από αυτή τη σφαίρα. Ας σκιαγραφήσουμε την κατάσταση όπως τη βλέπω από τη σκοπιά του πομπού: έχουμε οποιεσδήποτε ακτίνες από το μεταδιδόμενο μήνυμα ai στο ληφθέν μήνυμα bj με πιθανότητα σφάλματος ίση (ή σχεδόν ίση) με την κανονική κατανομή, φτάνοντας στο μέγιστο στο nQ. Για κάθε δεδομένο e2, υπάρχει ένα n τόσο μεγάλο που η πιθανότητα το προκύπτον σημείο bj να είναι έξω από τη σφαίρα μου είναι τόσο μικρή όσο θέλετε.
Ας δούμε τώρα την ίδια κατάσταση από την πλευρά σας (Εικ. 13.III). Στην πλευρά του δέκτη υπάρχει μια σφαίρα S(r) ίδιας ακτίνας r γύρω από το λαμβανόμενο σημείο bj σε n-διάστατο χώρο, έτσι ώστε αν το ληφθέν μήνυμα bj βρίσκεται μέσα στη σφαίρα μου, τότε το μήνυμα ai που στάλθηκε από εμένα είναι μέσα στο δικό σας σφαίρα.
Πώς μπορεί να συμβεί ένα σφάλμα; Το σφάλμα μπορεί να προκύψει στις περιπτώσεις που περιγράφονται στον παρακάτω πίνακα:
Εικόνα 13.III
Εδώ βλέπουμε ότι εάν στη σφαίρα που είναι χτισμένη γύρω από το ληφθέν σημείο υπάρχει τουλάχιστον ένα ακόμη σημείο που αντιστοιχεί σε ένα πιθανό απεσταλμένο μη κωδικοποιημένο μήνυμα, τότε παρουσιάστηκε σφάλμα κατά τη μετάδοση, καθώς δεν μπορείτε να προσδιορίσετε ποιο από αυτά τα μηνύματα μεταδόθηκε. Το απεσταλμένο μήνυμα είναι χωρίς σφάλματα μόνο εάν το σημείο που αντιστοιχεί σε αυτό βρίσκεται στη σφαίρα και δεν υπάρχουν άλλα σημεία δυνατά στον δεδομένο κώδικα που βρίσκονται στην ίδια σφαίρα.
Έχουμε μια μαθηματική εξίσωση για την πιθανότητα σφάλματος Pe αν σταλεί μήνυμα ai
Μπορούμε να πετάξουμε τον πρώτο παράγοντα στον δεύτερο όρο, λαμβάνοντας τον ως 1. Έτσι παίρνουμε την ανισότητα
Προφανώς,
ως εκ τούτου
υποβάλετε ξανά αίτηση στον τελευταίο όρο στα δεξιά
Λαμβάνοντας το n αρκετά μεγάλο, ο πρώτος όρος μπορεί να ληφθεί όσο μικρότερος επιθυμείτε, ας πούμε μικρότερος από κάποιον αριθμό d. Επομένως έχουμε
Τώρα ας δούμε πώς μπορούμε να κατασκευάσουμε έναν απλό κώδικα αντικατάστασης για να κωδικοποιήσουμε μηνύματα M που αποτελούνται από n bit. Μη έχοντας ιδέα πώς ακριβώς να κατασκευάσει έναν κώδικα (οι κωδικοί διόρθωσης σφαλμάτων δεν είχαν εφευρεθεί ακόμη), ο Shannon επέλεξε την τυχαία κωδικοποίηση. Γυρίστε ένα νόμισμα για κάθε ένα από τα n bit του μηνύματος και επαναλάβετε τη διαδικασία για τα M μηνύματα. Συνολικά, πρέπει να γίνουν ανατροπές νομισμάτων nM, οπότε είναι δυνατό
λεξικά κωδικών με την ίδια πιθανότητα ½nM. Φυσικά, η τυχαία διαδικασία δημιουργίας ενός βιβλίου κωδικών σημαίνει ότι υπάρχει πιθανότητα διπλότυπων, καθώς και σημείων κώδικα που θα είναι κοντά το ένα στο άλλο και επομένως αποτελούν πηγή πιθανών σφαλμάτων. Κάποιος πρέπει να αποδείξει ότι εάν αυτό δεν συμβαίνει με πιθανότητα μεγαλύτερη από οποιοδήποτε μικρό επιλεγμένο επίπεδο σφάλματος, τότε το δεδομένο n είναι αρκετά μεγάλο.
Το κρίσιμο σημείο είναι ότι η Shannon μέτρησε κατά μέσο όρο όλα τα πιθανά βιβλία κωδικών για να βρει το μέσο σφάλμα! Θα χρησιμοποιήσουμε το σύμβολο Av[.] για να δηλώσουμε τη μέση τιμή στο σύνολο όλων των πιθανών τυχαίων βιβλίων κωδικών. Ο μέσος όρος σε μια σταθερά d, φυσικά, δίνει μια σταθερά, αφού για τον μέσο όρο κάθε όρος είναι ίδιος με κάθε άλλο όρο στο άθροισμα,
που μπορεί να αυξηθεί (το M–1 πηγαίνει στο M)
Για κάθε δεδομένο μήνυμα, όταν υπολογίζεται ο μέσος όρος σε όλα τα βιβλία κωδίκων, η κωδικοποίηση διέρχεται από όλες τις πιθανές τιμές, επομένως η μέση πιθανότητα ένα σημείο να βρίσκεται σε μια σφαίρα είναι ο λόγος του όγκου της σφαίρας προς τον συνολικό όγκο του χώρου. Ο όγκος της σφαίρας είναι
όπου s=Q+e2 <1/2 και ns πρέπει να είναι ακέραιος.
Ο τελευταίος όρος στα δεξιά είναι ο μεγαλύτερος σε αυτό το άθροισμα. Αρχικά, ας υπολογίσουμε την αξία του χρησιμοποιώντας τον τύπο Stirling για παραγοντικά. Στη συνέχεια θα δούμε τον φθίνοντα συντελεστή του όρου μπροστά του, θα σημειώσουμε ότι αυτός ο συντελεστής αυξάνεται καθώς κινούμαστε προς τα αριστερά και έτσι μπορούμε: (1) να περιορίσουμε την τιμή του αθροίσματος στο άθροισμα της γεωμετρικής προόδου με αυτός ο αρχικός συντελεστής, (2) επεκτείνει τη γεωμετρική πρόοδο από ns όρους σε έναν άπειρο αριθμό όρων, (3) υπολογίζει το άθροισμα μιας άπειρης γεωμετρικής προόδου (τυπική άλγεβρα, τίποτα σημαντικό) και τελικά λαμβάνει την οριακή τιμή (για αρκετά μεγάλο n):
Παρατηρήστε πώς εμφανίστηκε η εντροπία H(s) στη διωνυμική ταυτότητα. Σημειώστε ότι η επέκταση της σειράς Taylor H(s)=H(Q+e2) δίνει μια εκτίμηση που λαμβάνεται λαμβάνοντας υπόψη μόνο την πρώτη παράγωγο και αγνοώντας όλες τις άλλες. Τώρα ας συγκεντρώσουμε την τελική έκφραση:
όπου
Το μόνο που έχουμε να κάνουμε είναι να επιλέξουμε e2 έτσι ώστε e3 < e1, και τότε ο τελευταίος όρος θα είναι αυθαίρετα μικρός, αρκεί το n να είναι αρκετά μεγάλο. Κατά συνέπεια, το μέσο σφάλμα PE μπορεί να ληφθεί όσο μικρό επιθυμείτε με τη χωρητικότητα του καναλιού αυθαίρετα κοντά στο C.
Εάν ο μέσος όρος όλων των κωδικών έχει ένα αρκετά μικρό σφάλμα, τότε τουλάχιστον ένας κωδικός πρέπει να είναι κατάλληλος, επομένως υπάρχει τουλάχιστον ένα κατάλληλο σύστημα κωδικοποίησης. Αυτό είναι ένα σημαντικό αποτέλεσμα που προέκυψε από τον Shannon - "Το θεώρημα του Shannon για ένα θορυβώδες κανάλι", αν και πρέπει να σημειωθεί ότι το απέδειξε για μια πολύ πιο γενική περίπτωση από ό,τι για το απλό δυαδικό συμμετρικό κανάλι που χρησιμοποίησα. Για τη γενική περίπτωση, οι μαθηματικοί υπολογισμοί είναι πολύ πιο περίπλοκοι, αλλά οι ιδέες δεν είναι τόσο διαφορετικές, επομένως πολύ συχνά, χρησιμοποιώντας το παράδειγμα μιας συγκεκριμένης περίπτωσης, μπορείτε να αποκαλύψετε το πραγματικό νόημα του θεωρήματος.
Ας κατακρίνουμε το αποτέλεσμα. Έχουμε επαναλάβει επανειλημμένα: "Για αρκετά μεγάλο n." Αλλά πόσο μεγάλο είναι το n; Πολύ, πολύ μεγάλο, αν θέλετε πραγματικά να είστε κοντά στη χωρητικότητα του καναλιού και να είστε σίγουροι για τη σωστή μεταφορά δεδομένων! Τόσο μεγάλο, στην πραγματικότητα, που θα πρέπει να περιμένετε πολύ καιρό για να συγκεντρώσετε ένα μήνυμα με αρκετά bits για να το κωδικοποιήσετε αργότερα. Σε αυτήν την περίπτωση, το μέγεθος του λεξικού τυχαίου κώδικα θα είναι απλά τεράστιο (εξάλλου, ένα τέτοιο λεξικό δεν μπορεί να αναπαρασταθεί σε συντομότερη μορφή από μια πλήρη λίστα όλων των bit Mn, παρά το γεγονός ότι τα n και M είναι πολύ μεγάλα)!
Οι κωδικοί διόρθωσης σφαλμάτων αποφεύγουν να περιμένουν ένα πολύ μεγάλο μήνυμα και στη συνέχεια να το κωδικοποιούν και να το αποκωδικοποιούν μέσω πολύ μεγάλων βιβλίων κωδίκων επειδή αποφεύγουν τα βιβλία κωδίκων και χρησιμοποιούν συνηθισμένους υπολογισμούς. Στην απλή θεωρία, τέτοιοι κώδικες τείνουν να χάνουν την ικανότητα να προσεγγίζουν τη χωρητικότητα του καναλιού και να διατηρούν χαμηλό ποσοστό σφάλματος, αλλά όταν ο κώδικας διορθώνει μεγάλο αριθμό σφαλμάτων, αποδίδουν καλά. Με άλλα λόγια, εάν εκχωρήσετε κάποια χωρητικότητα καναλιού στη διόρθωση σφαλμάτων, τότε πρέπει να χρησιμοποιείτε τη δυνατότητα διόρθωσης σφαλμάτων τις περισσότερες φορές, δηλαδή, πρέπει να διορθώνεται μεγάλος αριθμός σφαλμάτων σε κάθε μήνυμα που αποστέλλεται, διαφορετικά χάνετε αυτήν τη χωρητικότητα.
Ταυτόχρονα, το θεώρημα που αποδείχθηκε παραπάνω δεν είναι ακόμα χωρίς νόημα! Δείχνει ότι τα αποτελεσματικά συστήματα μετάδοσης πρέπει να χρησιμοποιούν έξυπνα σχήματα κωδικοποίησης για πολύ μεγάλες συμβολοσειρές bit. Ένα παράδειγμα είναι οι δορυφόροι που έχουν πετάξει πέρα από τους εξωτερικούς πλανήτες. Καθώς απομακρύνονται από τη Γη και τον Ήλιο, αναγκάζονται να διορθώνουν όλο και περισσότερα λάθη στο μπλοκ δεδομένων: ορισμένοι δορυφόροι χρησιμοποιούν ηλιακούς συλλέκτες, που παρέχουν περίπου 5 W, άλλοι χρησιμοποιούν πηγές πυρηνικής ενέργειας, που παρέχουν περίπου την ίδια ισχύ. Η χαμηλή ισχύς του τροφοδοτικού, το μικρό μέγεθος των πιάτων πομπού και το περιορισμένο μέγεθος των πιάτων δέκτη στη Γη, η τεράστια απόσταση που πρέπει να διανύσει το σήμα - όλα αυτά απαιτούν τη χρήση κωδικών με υψηλό επίπεδο διόρθωσης σφαλμάτων για τη δημιουργία αποτελεσματικό σύστημα επικοινωνίας.
Ας επιστρέψουμε στον n-διάστατο χώρο που χρησιμοποιήσαμε στην παραπάνω απόδειξη. Συζητώντας το, δείξαμε ότι σχεδόν ολόκληρος ο όγκος της σφαίρας συγκεντρώνεται κοντά στην εξωτερική επιφάνεια - επομένως, είναι σχεδόν βέβαιο ότι το απεσταλμένο σήμα θα βρίσκεται κοντά στην επιφάνεια της σφαίρας που είναι χτισμένη γύρω από το λαμβανόμενο σήμα, ακόμη και με σχετικά μικρή ακτίνα μιας τέτοιας σφαίρας. Επομένως, δεν προκαλεί έκπληξη το γεγονός ότι το λαμβανόμενο σήμα, μετά τη διόρθωση ενός αυθαίρετα μεγάλου αριθμού σφαλμάτων, nQ, αποδεικνύεται ότι είναι αυθαίρετα κοντά σε ένα σήμα χωρίς σφάλματα. Η χωρητικότητα ζεύξης που συζητήσαμε νωρίτερα είναι το κλειδί για την κατανόηση αυτού του φαινομένου. Σημειώστε ότι παρόμοιες σφαίρες που έχουν κατασκευαστεί για τη διόρθωση σφαλμάτων κωδικών Hamming δεν επικαλύπτονται μεταξύ τους. Ο μεγάλος αριθμός σχεδόν ορθογώνιων διαστάσεων στον n-διάστατο χώρο δείχνει γιατί μπορούμε να χωρέσουμε M σφαίρες στο χώρο με μικρή επικάλυψη. Εάν επιτρέψουμε μια μικρή, αυθαίρετα μικρή επικάλυψη, η οποία μπορεί να οδηγήσει σε μικρό μόνο αριθμό σφαλμάτων κατά την αποκωδικοποίηση, μπορούμε να επιτύχουμε μια πυκνή τοποθέτηση σφαιρών στο χώρο. Ο Hamming εγγυήθηκε ένα ορισμένο επίπεδο διόρθωσης σφάλματος, Shannon - μια χαμηλή πιθανότητα σφάλματος, αλλά ταυτόχρονα διατηρώντας την πραγματική απόδοση αυθαίρετα κοντά στη χωρητικότητα του καναλιού επικοινωνίας, κάτι που δεν μπορούν να κάνουν οι κωδικοί Hamming.
Η θεωρία της πληροφορίας δεν μας λέει πώς να σχεδιάσουμε ένα αποτελεσματικό σύστημα, αλλά δείχνει τον δρόμο προς αποτελεσματικά συστήματα επικοινωνίας. Είναι ένα πολύτιμο εργαλείο για την κατασκευή συστημάτων επικοινωνίας από μηχανή με μηχανή, αλλά, όπως αναφέρθηκε προηγουμένως, έχει μικρή σχέση με τον τρόπο με τον οποίο οι άνθρωποι επικοινωνούν μεταξύ τους. Ο βαθμός στον οποίο η βιολογική κληρονομικότητα μοιάζει με τα τεχνικά συστήματα επικοινωνίας είναι απλώς άγνωστος, επομένως δεν είναι επί του παρόντος σαφές πώς η θεωρία της πληροφορίας εφαρμόζεται στα γονίδια. Δεν έχουμε άλλη επιλογή από το να προσπαθήσουμε και αν η επιτυχία μας δείξει τη μηχανική φύση αυτού του φαινομένου, τότε η αποτυχία θα δείξει άλλες σημαντικές πτυχές της φύσης της πληροφορίας.
Ας μην παρεκκλίνουμε πολύ. Είδαμε ότι όλοι οι αρχικοί ορισμοί, σε μεγαλύτερο ή μικρότερο βαθμό, πρέπει να εκφράζουν την ουσία των αρχικών μας πεποιθήσεων, αλλά χαρακτηρίζονται από κάποιο βαθμό παραμόρφωσης και επομένως δεν είναι εφαρμόσιμοι. Είναι παραδοσιακά αποδεκτό ότι, τελικά, ο ορισμός που χρησιμοποιούμε καθορίζει στην πραγματικότητα την ουσία. αλλά, αυτό μας λέει μόνο πώς να επεξεργαζόμαστε τα πράγματα και σε καμία περίπτωση δεν μας μεταφέρει κανένα νόημα. Η θετική προσέγγιση, που τόσο ευνοείται στους μαθηματικούς κύκλους, αφήνει πολλά να είναι επιθυμητά στην πράξη.
Τώρα θα δούμε ένα παράδειγμα τεστ IQ όπου ο ορισμός είναι όσο κυκλικός θέλετε και, ως εκ τούτου, παραπλανητικός. Δημιουργείται ένα τεστ που υποτίθεται ότι μετράει τη νοημοσύνη. Στη συνέχεια αναθεωρείται για να γίνει όσο το δυνατόν πιο συνεπής και, στη συνέχεια, δημοσιεύεται και, με μια απλή μέθοδο, βαθμονομείται έτσι ώστε η μετρηθείσα «νοημοσύνη» να αποδειχθεί ότι είναι κανονικά κατανεμημένη (σε μια καμπύλη βαθμονόμησης, φυσικά). Όλοι οι ορισμοί πρέπει να επανελεγχθούν, όχι μόνο όταν προταθούν για πρώτη φορά, αλλά και πολύ αργότερα, όταν χρησιμοποιούνται στα συμπεράσματα που εξάγονται. Σε ποιο βαθμό τα οριστικά όρια είναι κατάλληλα για το πρόβλημα που επιλύεται; Πόσο συχνά οι ορισμοί που δίνονται σε μία ρύθμιση εφαρμόζονται σε αρκετά διαφορετικές ρυθμίσεις; Αυτό συμβαίνει αρκετά συχνά! Στις ανθρωπιστικές επιστήμες, που αναπόφευκτα θα συναντήσεις στη ζωή σου, αυτό συμβαίνει πιο συχνά.
Έτσι, ένας από τους σκοπούς αυτής της παρουσίασης της θεωρίας της πληροφορίας, εκτός από την απόδειξη της χρησιμότητάς της, ήταν να σας προειδοποιήσει για αυτόν τον κίνδυνο ή να σας δείξει πώς ακριβώς να τη χρησιμοποιήσετε για να επιτύχετε το επιθυμητό αποτέλεσμα. Έχει σημειωθεί εδώ και καιρό ότι οι αρχικοί ορισμοί καθορίζουν αυτό που θα βρείτε στο τέλος, σε πολύ μεγαλύτερο βαθμό από ό,τι φαίνεται. Οι αρχικοί ορισμοί απαιτούν μεγάλη προσοχή από εσάς, όχι μόνο σε οποιαδήποτε νέα κατάσταση, αλλά και σε τομείς με τους οποίους εργάζεστε εδώ και πολύ καιρό. Αυτό θα σας επιτρέψει να κατανοήσετε σε ποιο βαθμό τα αποτελέσματα που λαμβάνονται είναι ταυτολογία και όχι κάτι χρήσιμο.
Η διάσημη ιστορία του Έντινγκτον λέει για ανθρώπους που ψάρευαν στη θάλασσα με ένα δίχτυ. Αφού μελέτησαν το μέγεθος των ψαριών που έπιασαν, προσδιόρισαν το ελάχιστο μέγεθος ψαριού που βρίσκεται στη θάλασσα! Το συμπέρασμά τους οδηγήθηκε από το όργανο που χρησιμοποιήθηκε, όχι από την πραγματικότητα.
Για να συνεχιστεί ...
Όποιος θέλει να βοηθήσει με τη μετάφραση, τη διάταξη και την έκδοση του βιβλίου - γράψτε σε προσωπικό μήνυμα ή email [προστασία μέσω email]
Παρεμπιπτόντως, έχουμε ξεκινήσει επίσης τη μετάφραση ενός άλλου υπέροχου βιβλίου - )
Ψάχνουμε ιδιαίτερα αυτοί που θα βοηθήσουν στη μετάφραση . (μεταφορά για 10 λεπτά, τα πρώτα 20 έχουν ήδη ληφθεί)
Περιεχόμενα του βιβλίου και μεταφρασμένα κεφάλαια
- Εισαγωγή στο The Art of Doing Science and Engineering: Learning to Learn (28 Μαρτίου 1995)
- «Θεμέλια της Ψηφιακής (Διακριτικής) Επανάστασης» (30 Μαρτίου 1995)
- "History of Computers - Hardware" (31 Μαρτίου 1995)
- "History of Computers - Software" (4 Απριλίου 1995)
- "Ιστορία των Υπολογιστών - Εφαρμογές" (6 Απριλίου 1995)
- "Τεχνητή Νοημοσύνη - Μέρος Ι" (7 Απριλίου 1995)
- "Τεχνητή Νοημοσύνη - Μέρος II" (11 Απριλίου 1995)
- "Artificial Intelligence III" (13 Απριλίου 1995)
- "n-Dimensional Space" (14 Απριλίου 1995)
- «Θεωρία κωδικοποίησης - Η αναπαράσταση της πληροφορίας, Μέρος Ι» (18 Απριλίου 1995)
- «Θεωρία κωδικοποίησης - Η αναπαράσταση της πληροφορίας, Μέρος ΙΙ» (20 Απριλίου 1995)
- "Error-Corecting Codes" (21 Απριλίου 1995)
- «Θεωρία της Πληροφορίας» (25 Απριλίου 1995)
- "Ψηφιακά φίλτρα, Μέρος Ι" (27 Απριλίου 1995)
- "Ψηφιακά φίλτρα, Μέρος II" (28 Απριλίου 1995)
- "Digital Filters, Part III" (2 Μαΐου 1995)
- "Ψηφιακά φίλτρα, Μέρος IV" (4 Μαΐου 1995)
- "Simulation, Part I" (5 Μαΐου 1995)
- "Simulation, Part II" (9 Μαΐου 1995)
- "Simulation, Part III" (11 Μαΐου 1995)
- "Οπτικές ίνες" (12 Μαΐου 1995)
- "Computer Aided Instruction" (16 Μαΐου 1995)
- «Μαθηματικά» (18 Μαΐου 1995)
- "Quantum Mechanics" (19 Μαΐου 1995)
- «Δημιουργικότητα» (23 Μαΐου 1995). Μετάφραση:
- "Ειδικοί" (25 Μαΐου 1995)
- "Μη αξιόπιστα δεδομένα" (26 Μαΐου 1995)
- "Systems Engineering" (30 Μαΐου 1995)
- "You Get What You Measure" (1 Ιουνίου 1995)
- (Ιούνιος 2, 1995) μεταφράστε σε κομμάτια 10 λεπτών
- Hamming, «You and Your Research» (6 Ιουνίου 1995).
Όποιος θέλει να βοηθήσει με τη μετάφραση, τη διάταξη και την έκδοση του βιβλίου - γράψτε σε προσωπικό μήνυμα ή email [προστασία μέσω email]
Πηγή: www.habr.com