Εισαγωγή
Τρισεκατομμύρια επί τρισεκατομμυρίων μηνύματα διασχίζουν κάθε χιλιοστό του δευτερολέπτου την απόσταση ανάμεσα στη Γη και σε γειτονικούς γαλαξίες.
Όμως η μετάδοση σε τόσο μεγάλες αποστάσεις είναι δύσκολη.
Ενοχλητικές ηλιακές εκλάμψεις, χρονικές παραμορφώσεις, αδέσποτες δυνάμεις, ακόμα και το φτερούγισμα μιας πεταλούδας του διαστήματος μπορούν να προκαλέσουν την αλλαγή ενός τυχαίου bit κατά τη μετάδοση.
Τώρα φαντάσου τις συνέπειες:
- Να καταρρεύσει το Διαγαλαξιακό Χρηματιστήριο όταν το "buy low" γίνεται "sell now".
- Να χαθεί η επαφή με το σύστημα Kepler Whirl όταν το "save new worm hole" γίνεται "cave new worm hole".
- Ή να βυθιστεί το σύμπαν σε υπαρξιακή φρίκη, αντικαθιστώντας ένα emoji καουμπόη 🤠 με ένα emoji κλόουν 🤡.
Ο εντοπισμός των αλλοιωμένων μηνυμάτων δεν είναι απλώς σημαντικός, είναι κρίσιμος.
Ο δέκτης πρέπει να ξέρει πότε κάτι πήγε στραβά, πριν χτυπήσει η καταστροφή.
Μα πώς;
Επιστήμονες και μηχανικοί από όλο το σύμπαν παλεύουν με αυτό το πρόβλημα εδώ και αμέτρητους αιώνες.
Ολόκληρα κοσμικά υπερσυμπλέγματα τεχνητής νοημοσύνης επεξεργάζονται τα δεδομένα χωρίς σταματημό.
Και τότε, μια μέρα, μια παλιά ιστορία επιστρέφει από τα βάθη του χρόνου: μια αρχαία, πανίσχυρη μέθοδος, που ψιθυρίζεται σε φόρουμ debugging, μουρμουρίζεται από μηχανικούς που έχουν δει πολλά...
Το Bit Ισοτιμίας!
Μια μέθοδος τόσο απλή, τόσο ισχυρή, που μπορεί και να σώσει τη διαστρική επικοινωνία.
Οδηγίες
Η δουλειά σου είναι να βοηθήσεις στην υλοποίηση
- του πομπού, που υπολογίζει την ακολουθία μετάδοσης, και
- του δέκτη, που την αποκωδικοποιεί.
Το bit ισοτιμίας είναι ένας απλός τρόπος να εντοπίζονται σφάλματα μετάδοσης.
Οι πομποί και οι δέκτες μπορούν να μεταδώσουν και να λάβουν ακριβώς οκτώ bit τη φορά (μαζί με το bit ισοτιμίας).
Το bit ισοτιμίας ορίζεται έτσι ώστε κάθε μετάδοση να έχει άρτιο αριθμό άσσων, και το bit ισοτιμίας είναι πάντα το πρώτο bit από τα δεξιά.
Έτσι, αν ο δέκτης λάβει 11000001, 01110101 ή 01000000 (δηλαδή μια μετάδοση με περιττό αριθμό άσσων), ξέρει ότι υπάρχει σφάλμα.
Ωστόσο, τα μηνύματα σπάνια είναι τόσο σύντομα, και όταν είναι μεγαλύτερα πρέπει να μεταδίδονται σε ακολουθία.
Για παράδειγμα, σκέψου το μήνυμα 11000000 00000001 11000000 11011110 (ή C0 01 C0 DE σε δεκαεξαδικό).
Επειδή κάθε μετάδοση περιέχει ακριβώς οκτώ bit, μπορεί να περιέχει μόνο επτά bit δεδομένων και το bit ισοτιμίας.
Ένα bit ισοτιμίας πρέπει λοιπόν να εισάγεται μετά από κάθε επτά bit δεδομένων:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
Η ακολουθία μετάδοσης για αυτό το μήνυμα μοιάζει κάπως έτσι:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
Τα δεδομένα στην πρώτη μετάδοση της ακολουθίας (1100000) έχουν δύο άσσους (άρτιος αριθμός), οπότε το bit ισοτιμίας είναι 0.
Η πρώτη μετάδοση γίνεται 11000000 (ή C0 σε δεκαεξαδικό).
Τα δεδομένα στην επόμενη μετάδοση (0000000) έχουν μηδέν άσσους (πάλι άρτιος αριθμός), οπότε το bit ισοτιμίας είναι και πάλι 0.
Έτσι, η δεύτερη μετάδοση γίνεται 00000000 (ή 00 σε δεκαεξαδικό).
Τα δεδομένα για τις επόμενες δύο μεταδόσεις (0111000 και 0001101) έχουν τρεις άσσους.
Τα bit ισοτιμίας τους ορίζονται σε 1, ώστε να έχουν άρτιο αριθμό άσσων στη μετάδοση.
Μεταδίδονται ως 01110001 και 00011011 (ή 71 και 1B σε δεκαεξαδικό).
Η τελευταία μετάδοση (1110) έχει μόνο τέσσερα bit δεδομένων.
Επειδή μεταδίδονται ακριβώς οκτώ bit τη φορά και το bit ισοτιμίας είναι το πιο δεξί bit, προστίθενται τρία μηδενικά bit και μετά το bit ισοτιμίας, ώστε να συμπληρωθούν τα οκτώ bit.
Τώρα μοιάζει κάπως έτσι (όπου _ είναι το bit ισοτιμίας):
1110 000_
↑↑↑ (added 0 bits)
Υπάρχει πάλι περιττός αριθμός άσσων, οπότε το bit ισοτιμίας είναι 1.
Η τελευταία μετάδοση της ακολουθίας γίνεται 11100001 (ή E1 σε δεκαεξαδικό).
Ολόκληρη η ακολουθία μετάδοσης για αυτό το μήνυμα είναι 11000000 00000000 01110001 00011011 11100001 (ή C0 00 71 1B E1 σε δεκαεξαδικό).
