Η Βασική Άλγεβρα Πίσω από Μυστικούς Κώδικες και Διαστημική Επικοινωνία

Η εξερεύνηση του διαστήματος απαιτεί τεράστια ακρίβεια. Όταν προσγειώνετε ένα rover στον Άρη 70 εκατομμύρια μίλια μακριά από το πλησιέστερο πρατήριο καυσίμων, πρέπει να μεγιστοποιήσετε την απόδοση και να προετοιμαστείτε για το απροσδόκητο. Αυτό ισχύει για τα πάντα, από τη σχεδίαση του διαστημικού σκάφους έως τη μετάδοση δεδομένων: Αυτά τα μηνύματα που επιστρέφουν στη Γη ως σταθερή ροή 0 και 1 θα περιέχουν σίγουρα κάποια σφάλματα, επομένως πρέπει να μπορείτε να τα εντοπίσετε και να τα διορθώσετε χωρίς να χάνετε πολύτιμο χρόνο και ενέργεια.

Εκεί μπαίνουν τα μαθηματικά. Οι μαθηματικοί έχουν εφεύρει ευφυείς τρόπους μετάδοσης και αποθήκευσης πληροφοριών. Μια εκπληκτικά αποτελεσματική μέθοδος που χρησιμοποιεί Κώδικες Reed-Solomon, τα οποία είναι χτισμένα στην ίδια βασική άλγεβρα που μαθαίνουν οι μαθητές στο σχολείο. Ας πάμε σε ένα μάθημα μαθηματικών για να δούμε πώς οι κώδικες Reed-Solomon βοηθούν στη μετάδοση και την ασφάλεια των πληροφοριών, ενώ διορθώνουν τυχόν δαπανηρά σφάλματα που εμφανίζονται.

Δύο μαθητές, η Art και ο Zeke, ανταλλάσσουν μυστικά μηνύματα στο μάθημα των μαθηματικών της κυρίας Al-Jabr. Η τέχνη ξεδιπλώνει το τελευταίο σημείωμα του Zeke για να αποκαλύψει τους αριθμούς 57 και 99. Ξέρει ότι πρέπει να παράσχει το x-Οι συντεταγμένες 3 και 6 για τη δημιουργία των σημείων (3, 57) και (6, 99). Η τέχνη συνδέει κάθε σημείο στη γραμμική εξίσωση y = Ax + B και παράγει το ακόλουθο σύστημα εξισώσεων:

57 = 3A + B

99 = 6A + B

Για να αποκωδικοποιήσει το μήνυμα, η Τέχνη πρέπει να λύσει A και B. Ξεκινά αφαιρώντας την πρώτη εξίσωση από τη δεύτερη:

Αυτό εξαλείφει B. Η διαίρεση και των δύο πλευρών αυτής της νέας εξίσωσης με 3 λέει στην Τέχνη ότι A = 14, και μετά αντικαθιστώντας αυτό ξανά στην πρώτη εξίσωση, 57 = 3 × 14 + B, δίνει B = 15.

Η τέχνη γνωρίζει τώρα ότι η γραμμή που διέρχεται από (3, 57) και (6, 99) περιγράφεται από την εξίσωση y = 14x + 15. Αλλά ξέρει επίσης ότι σε έναν κώδικα Reed-Solomon, το μυστικό μήνυμα κρύβεται στους συντελεστές. Αποκωδικοποιεί το μήνυμα του Zeke χρησιμοποιώντας τον απλό συμφωνημένο αλφάβητο τους: το 14 είναι "N" και το 15 είναι "O", το οποίο λέει στον Art ότι, όχι, ο Zeke δεν μπορεί να παίξει βιντεοπαιχνίδια μετά το σχολείο σήμερα.

Το μυστικό αυτού του απλού κώδικα Reed-Solomon ξεκινά με δύο βασικά στοιχεία της γεωμετρίας. Πρώτον, μέσα από οποιαδήποτε δύο σημεία υπάρχει μια μοναδική γραμμή. Δεύτερον, για τους συντελεστές A και B, κάθε (μη κάθετη) γραμμή μπορεί να γραφτεί με τη μορφή y = Ax + B. Μαζί, αυτά τα δύο γεγονότα εγγυώνται ότι αν γνωρίζετε δύο σημεία σε μια γραμμή μπορείτε να βρείτε A και B, και αν ξέρεις A και B, γνωρίζετε όλα τα σημεία της γραμμής. Εν ολίγοις, η κατοχή οποιουδήποτε συνόλου πληροφοριών ισοδυναμεί με τη γνώση της γραμμής.

Οι κώδικες Reed-Solomon αξιοποιούν αυτά τα ισοδύναμα σύνολα πληροφοριών. Το μυστικό μήνυμα κωδικοποιείται ως συντελεστές A και B, και τα σημεία της γραμμής χωρίζονται σε κομμάτια, μερικά από τα οποία μεταδίδονται δημόσια και μερικά από τα οποία διατηρούνται ιδιωτικά. Για να αποκωδικοποιήσετε το μήνυμα, απλώς συλλέγετε τα κομμάτια και τα συναρμολογείτε ξανά. Και το μόνο που απαιτεί αυτό είναι μια απλή άλγεβρα.

Τα κομμάτια του Zeke ήταν οι αριθμοί 57 και 99, που έστειλε στο Art. Αυτοί οι αριθμοί είναι το δημόσιο μέρος του μηνύματος. Ο Art τα έβαλε μαζί με τα δικά του κομμάτια, 3 και 6, για να ανακατασκευάσει τα σημεία (3, 57) και (6, 99). Εδώ, το 3 και το 6 αποτελούν το ιδιωτικό μέρος του μηνύματος, το οποίο συμφώνησαν εκ των προτέρων ο Art και ο Zeke.

Τα δύο σημεία βρίσκονται σε μια γραμμή και για να αποκωδικοποιήσετε το μήνυμα, πρέπει απλώς να βρείτε την εξίσωση αυτής της γραμμής. Συνδέστε κάθε σημείο σε y = Ax + B σας δίνει ένα σύστημα δύο εξισώσεων για την ευθεία που πρέπει και οι δύο να είναι αληθείς. Τώρα η στρατηγική είναι απλή: Λύστε το σύστημα, καθορίστε τη γραμμή και αποκωδικοποιήστε το μήνυμα.

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

Όπως και με άλλα σχήματα κρυπτογράφησης, είναι ο έξυπνος συνδυασμός δημόσιων και ιδιωτικών πληροφοριών που διατηρεί τα μηνύματα ασφαλή. Ο Zeke μπορούσε να φωνάξει τους αριθμούς του 57 και 99 σε όλη την τάξη και αυτό δεν θα έθετε σε κίνδυνο την ασφάλεια του μηνύματός του προς την Art (αν και θα μπορούσε να τον φέρει σε μπελάδες με την κα Al-Jabr). Αυτό συμβαίνει γιατί χωρίς τις αντίστοιχες ιδιωτικές πληροφορίες — το x-συντεταγμένες 3 και 6 — είναι αδύνατο να προσδιοριστεί η εξίσωση της ευθείας. Εφόσον κρατούν αυτές τις αξίες για τον εαυτό τους, μπορούν να περάσουν με ασφάλεια τα μυστικά τους μηνύματα δημόσια.

Η γραμμή y = 14x Το + 15 είναι καλό για τη μετάδοση της λέξης «όχι» με δύο γράμματα, αλλά τι γίνεται αν οι μαθητές θέλουν να μοιραστούν ένα μεγαλύτερο μυστικό; Εδώ μπαίνει στο παιχνίδι η πλήρης δύναμη της άλγεβρας, της γεωμετρίας και των συστημάτων γραμμικών εξισώσεων.

Ας υποθέσουμε ότι ο Zeke θέλει να μάθει πώς πιστεύει ο Art ότι θα τα πάει στο αυριανό τεστ αγγλικών. Ο Αρτ μετατρέπει την απάντησή του με τρία γράμματα στους αριθμούς 14, 59 και 82 και τους μεταβιβάζει στον Zeke. Οι μαθητές συμφώνησαν εκ των προτέρων ότι όταν χρησιμοποιούν τους κωδικούς Reed-Solomon μήκους 3, οι ιδιωτικοί τους αριθμοί είναι 2, 5 και 6, έτσι ο Zeke ενώνει τα κομμάτια για να ανακατασκευάσει τα σημεία (2, 14), (5, 59) και (6, 82).

Τώρα, δεν υπάρχει γραμμική συνάρτηση που να διέρχεται από αυτά τα τρία σημεία. Αλλά υπάρχει μια μοναδική τετραγωνική συνάρτηση που το κάνει. Και αφού κάθε τετραγωνική συνάρτηση μπορεί να γραφτεί με τη μορφή y = Ax² + Bx + C, μπορεί να εφαρμοστεί η ίδια γενική μέθοδος. Η μόνη διαφορά είναι το μέγεθος του συστήματος.

Συνδέστε κάθε σημείο σε y = Ax² + Bx + C δίνει μία εξίσωση, οπότε τα τρία σημεία παράγουν το ακόλουθο σύστημα τριών εξισώσεων:

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

Ένα σύστημα τριών εξισώσεων με τρεις αγνώστους απαιτεί λίγη περισσότερη δουλειά για να λυθεί από ένα σύστημα δύο εξισώσεων με δύο αγνώστους, αλλά ο στόχος είναι ο ίδιος: Συνδυάστε έξυπνα ζεύγη εξισώσεων για να εξαλείψετε μεταβλητές.

Για παράδειγμα, αν αφαιρέσετε την πρώτη εξίσωση από τη δεύτερη, θα έχετε τη νέα εξίσωση 45 = 21A + 3B. Ομοίως, αν αφαιρέσετε τη δεύτερη εξίσωση από την τρίτη, παίρνετε 23 = 11A + B. Αυτοί οι αλγεβρικοί χειρισμοί παράγουν ένα νέο σύστημα:

45 = 21A + 3B

23 = 11A + B

Τώρα έχετε ένα σύστημα "δύο προς δύο": δύο εξισώσεις με δύο αγνώστους. Για να το λύσετε, μπορείτε να πολλαπλασιάσετε τη δεύτερη εξίσωση με −3 και να την προσθέσετε στην πρώτη εξίσωση:

Παρατηρήστε πώς η επαναλαμβανόμενη εξάλειψη έχει μετατρέψει το αρχικό σύστημα τριών εξισώσεων σε μια ενιαία εξίσωση που μπορεί εύκολα να λυθεί: A = 2. Λειτουργώντας προς τα πίσω, μπορείτε να συνδέσετε A = 2 σε μία από τις εξισώσεις στο σύστημα δύο προς δύο για να βρείτε B = 1 και, στη συνέχεια, συνδέστε και τις δύο τιμές σε μία από τις αρχικές εξισώσεις για να λάβετε C = 4. Αφού χρησιμοποιήσει την απλή αλφαβητική κρυπτογράφηση στα 2, 1 και 4, ο Zeke ξέρει ότι η Art θα κάνει "BAD" στο αυριανό τεστ στα αγγλικά. Τουλάχιστον κάνει πολλή εξάσκηση στην άλγεβρα.

Χάρη σε ένα ειδικό γεγονός σχετικά με τις πολυωνυμικές συναρτήσεις, μπορείτε να μεταδώσετε ένα μήνυμα οποιουδήποτε μήκους χρησιμοποιώντας κωδικούς Reed-Solomon. Το κλειδί είναι το εξής: Δεδομένου οποιουδήποτε n σημεία στο επίπεδο με διαφορετικά x-συντεταγμένες, υπάρχει ένα μοναδικό πολυώνυμο "βαθμού" n − 1 που διέρχεται από αυτά. Ο βαθμός ενός πολυωνύμου είναι η υψηλότερη ισχύς μιας μεταβλητής στην έκφραση, άρα μια τετραγωνική συνάρτηση όπως Ax² + Bx + C έχει βαθμό 2, αφού η υψηλότερη ισχύς του x είναι 2. Και μια γραμμική συνάρτηση έχει βαθμό 1, αφού στην εξίσωση y = Ax + B, η υψηλότερη δύναμη του x είναι 1.

Στο πρώτο παράδειγμα χρησιμοποιήσαμε το γεγονός ότι δύο σημεία καθορίζουν ένα μοναδικό γραμμικό, ή βαθμό-1, πολυώνυμο. Στη δεύτερη, βασιστήκαμε στο γεγονός ότι τρία σημεία καθορίζουν ένα μοναδικό βαθμό-2, ή τετραγωνικό, πολυώνυμο. Και αν θέλετε να στείλετε ένα μήνυμα μήκους 10, απλώς κωδικοποιήστε το μήνυμα ως τους 10 συντελεστές μιας πολυωνυμικής συνάρτησης βαθμού-9. Μόλις έχετε τη συνάρτησή σας, υπολογίστε το 10 δημόσιο y-τιμές αξιολογώντας τη συνάρτηση στο προηγουμένως συμφωνημένο 10 ιδιωτικό x-αξίες. Μόλις το κάνετε αυτό, μπορείτε να τα περάσετε με ασφάλεια y-συντεταγμένες δημόσια για αποκωδικοποίηση του δέκτη σας. Στην πράξη, οι κώδικες Reed-Solomon είναι λίγο πιο περίπλοκοι από αυτό, χρησιμοποιώντας πιο εξελιγμένα είδη συντελεστών και σχημάτων μετάφρασης, αλλά η θεμελιώδης ιδέα είναι η ίδια.

Εκτός από το ότι διατηρούν το μήνυμά σας ασφαλές, οι κωδικοί Reed-Solomon προσφέρουν επίσης απλούς και αποτελεσματικούς τρόπους εντοπισμού και ακόμη και διόρθωσης σφαλμάτων. Αυτό είναι σημαντικό κάθε φορά που μεταδίδονται ή αποθηκεύονται δεδομένα, καθώς υπάρχει πάντα η πιθανότητα να χαθούν ή να καταστραφούν ορισμένες από τις πληροφορίες.

Μια λύση σε αυτό το πρόβλημα θα ήταν η απλή αποστολή επιπλέον αντιγράφων των δεδομένων. Για παράδειγμα, ο Zeke μπορεί να στείλει το μήνυμα [14, 14, 14, 15, 15, 15] αντί για [14, 15]. Εφόσον ο Art γνωρίζει ότι κάθε μέρος του μηνύματος αποστέλλεται εις τριπλούν, μπορεί να αποκωδικοποιήσει το μήνυμα και να ελέγξει για σφάλματα. Μάλιστα, αν βρει κάποια λάθη, έχει πολλές πιθανότητες να τα διορθώσει. Εάν ο Art λάβει [14, 14, 24, 15, 15, 15], το γεγονός ότι οι τρεις πρώτοι αριθμοί είναι διαφορετικοί τον ειδοποιεί για ένα σφάλμα και επειδή δύο από αυτούς είναι 14, μπορεί να μαντέψει ότι το 24 θα πρέπει πιθανώς να είναι 14 επίσης. Αντί να ζητήσει να σταλεί εκ νέου το μήνυμα, ο Art μπορεί να συνεχίσει την αποκωδικοποίησή του. Αυτή είναι μια αποτελεσματική αλλά δαπανηρή στρατηγική. Ό,τι χρόνο, ενέργεια και προσπάθεια απαιτείται για την αποστολή n πληροφορίες, αυτό απαιτεί τρεις φορές περισσότερο.

Αλλά τα μαθηματικά πίσω από τους κώδικες Reed-Solomon προσφέρουν μια αποτελεσματική εναλλακτική. Αντί να στέλνετε πολλά αντίγραφα κάθε τμήματος δεδομένων, μπορείτε απλώς να στείλετε έναν επιπλέον πόντο! Εάν αυτό το πρόσθετο σημείο ταιριάζει στο πολυώνυμο σας, τότε οι πληροφορίες είναι σωστές. Εάν δεν το κάνει, υπάρχει σφάλμα.

Για να δείτε πώς λειτουργεί αυτό, ας υποθέσουμε ότι θέλετε να ελέγξετε το μήνυμα "ΟΧΙ" στο πρώτο παράδειγμα. Ο Zeke μπορεί απλώς να στείλει το πρόσθετο y-συντεταγμένη 155. Υποθέτοντας ότι αυτός και ο Αρτ συμφώνησαν σε ένα τρίτο ιδιωτικό x-συντονίζω εκ των προτέρων, ας πούμε x = 10, ο Art μπορεί να ελέγξει αυτό το τρίτο σημείο σε σχέση με τη γραμμή που αποκωδικοποίησε. Όταν βουλώνει x = 10 σε y = 14x + 15 και βλέπει ότι το αποτέλεσμα είναι 155, ξέρει ότι δεν υπήρχαν σφάλματα στη μετάδοση.

Αυτό δεν λειτουργεί μόνο για γραμμές. Για να μπορέσει ο Zeke να ελέγξει το "BAD" στο δεύτερο παράδειγμα, το Art μπορεί να στείλει y = 25. Εάν έχουν συμφωνήσει ότι το 3 είναι το επιπλέον ιδιωτικό x-συντεταγμένη, ο Zeke μπορεί να συνδέσει x = 3 στην τετραγωνική του συνάρτηση y = 2x² + x + 4 και επαληθεύστε ότι το σημείο (3, 25) ταιριάζει, επιβεβαιώνοντας ξανά μια μετάδοση χωρίς σφάλματα με ένα μόνο σημείο ακόμη.

Και αυτός ο επιπλέον βαθμός μπορεί ενδεχομένως να διορθώσει και σφάλματα. Εάν εντοπιστεί σφάλμα και ο παραλήπτης δεν μπορεί να κατασκευάσει την πολυωνυμική συνάρτηση που περιέχει το μήνυμα, μπορεί αντ 'αυτού να κατασκευάσει το πολυώνυμο "καλύτερης προσαρμογής" χρησιμοποιώντας τεχνικές παλινδρόμησης. Όπως μια γραμμή βέλτιστης προσαρμογής στην τάξη στατιστικών, αυτή είναι η πολυωνυμική συνάρτηση που μαθηματικά καθορίζεται ώστε να ταιριάζει περισσότερο στα δεδομένα σημεία, ακόμα κι αν δεν περνά από όλα. Ανάλογα με τη δομή του μηνύματος και πόσες επιπλέον πληροφορίες στέλνετε, αυτό το πολυώνυμο που ταιριάζει καλύτερα μπορεί να σας βοηθήσει να ανασυνθέσετε το σωστό πολυώνυμο — και επομένως το σωστό μήνυμα — ακόμη και από κατεστραμμένες πληροφορίες.

Αυτή η αποτελεσματικότητα στη μετάδοση και τη διόρθωση των επικοινωνιών εξηγεί γιατί η NASA χρησιμοποίησε τους κώδικες Reed-Solomon στις αποστολές της στο φεγγάρι και στον Άρη. Και σας δίνει κάτι να σκεφτείτε καθώς λύνετε το επόμενο σύστημα εξισώσεων. Καθώς μαντεύετε, ελέγξτε ή εξαλείψτε την πορεία σας προς τη λύση, σκεφτείτε τη δύναμη και την κομψότητα των κωδίκων Reed-Solomon και όλα τα μυστικά που μπορεί να αποκαλύψει το σύστημά σας.

Ασκήσεις

1. Χρησιμοποιώντας το ίδιο σχήμα που χρησιμοποιούσαν στην τάξη, το Art δημοσιεύει τους δημόσιους αριθμούς 33 και 57 για να αποκωδικοποιήσει ο Zeke. Ποιο είναι το μήνυμα;

2. Πώς μπορούν οι Art και Zeke να είναι σίγουροι ότι το σύστημα εξισώσεων που προκύπτει από τους ιδιωτικούς τους αριθμούς x = 3 και x = 6 θα έχει πάντα λύση;

3. Σε απάντηση στο μήνυμα του Art για το "BAD" σχετικά με το τεστ στα αγγλικά, ο Zeke στέλνει πίσω [90, 387, 534]. Αν υποθέσουμε ότι χρησιμοποιούν το ίδιο σχήμα που χρησιμοποιούσαν στην τάξη, ποιο είναι το μήνυμά του;

4. Η Lola σας στέλνει ένα μήνυμα δύο γραμμάτων συν έναν αριθμό ελέγχου σφαλμάτων χρησιμοποιώντας έναν κωδικό Reed-Solomon και τον ίδιο απλό αλφαβητικό κρυπτογράφηση που χρησιμοποιούν οι Art και Zeke. Έχετε συμφωνήσει κρυφά για το x-συντεταγμένες 1, 3 και 10 εκ των προτέρων και η Λόλα μεταδίδει τους δημόσιους αριθμούς [27, 43, 90]. Μήπως το μήνυμα περιέχει κάποιο σφάλμα;