Διόρθωση σφαλμάτων Reed-Solomon
Η διόρθωση σφαλμάτων Reed-Solomon είναι ένας κώδικας διόρθωσης σφαλμάτων προς τα εμπρός. Λειτουργεί με υπερδειγματοληψία ενός πολυωνύμου που κατασκευάζεται από τα δεδομένα. Το πολυώνυμο αξιολογείται σε διάφορα σημεία και οι τιμές αυτές αποστέλλονται ή καταγράφονται. Η δειγματοληψία του πολυωνύμου συχνότερα από ό,τι είναι απαραίτητο καθιστά το πολυώνυμο υπερπροσδιορισμένο. Εφόσον λαμβάνει σωστά "πολλά" από τα σημεία, ο δέκτης μπορεί να ανακτήσει το αρχικό πολυώνυμο ακόμη και με την παρουσία "λίγων" κακών σημείων.
Οι κώδικες Reed-Solomon χρησιμοποιούνται σε πολλά διαφορετικά είδη εμπορικών εφαρμογών, για παράδειγμα σε CD, DVD και Blu-ray Discs, σε τεχνολογίες μετάδοσης δεδομένων όπως το DSL και το WiMAX και σε συστήματα μετάδοσης όπως το DVB και το ATSC.
Επισκόπηση
Οι κώδικες Reed-Solomon είναι κώδικες μπλοκ. Αυτό σημαίνει ότι ένα σταθερό μπλοκ δεδομένων εισόδου επεξεργάζεται σε ένα σταθερό μπλοκ δεδομένων εξόδου. Στην περίπτωση του πιο συχνά χρησιμοποιούμενου κώδικα R-S (255, 223) - 223 σύμβολα εισόδου Reed-Solomon (το καθένα μήκους οκτώ bit) κωδικοποιούνται σε 255 σύμβολα εξόδου.
- Τα περισσότερα συστήματα ECC R-S είναι συστηματικά. Αυτό σημαίνει ότι κάποιο τμήμα της κωδικής λέξης εξόδου περιέχει τα δεδομένα εισόδου στην αρχική τους μορφή.
- Επιλέχθηκε ένα μέγεθος συμβόλου Reed-Solomon οκτώ bit, επειδή οι αποκωδικοποιητές για μεγαλύτερα μεγέθη συμβόλων θα ήταν δύσκολο να υλοποιηθούν με την τρέχουσα τεχνολογία. Αυτή η σχεδιαστική επιλογή αναγκάζει το μεγαλύτερο μήκος κωδικής λέξης να είναι 255 σύμβολα.
- Ο τυπικός κώδικας (255, 223) Reed-Solomon μπορεί να διορθώσει έως και 16 σφάλματα συμβόλων Reed-Solomon σε κάθε κωδική λέξη. Δεδομένου ότι κάθε σύμβολο είναι στην πραγματικότητα οκτώ bit, αυτό σημαίνει ότι ο κώδικας μπορεί να διορθώσει έως και 16 σύντομες εκρήξεις σφάλματος λόγω του εσωτερικού συνελικτικού αποκωδικοποιητή.
Ο κώδικας Reed-Solomon, όπως και ο συνελικτικός κώδικας, είναι ένας διαφανής κώδικας. Αυτό σημαίνει ότι αν τα σύμβολα του καναλιού έχουν αντιστραφεί κάπου στη γραμμή, οι αποκωδικοποιητές εξακολουθούν να λειτουργούν. Το αποτέλεσμα θα είναι το συμπλήρωμα των αρχικών δεδομένων. Ωστόσο, ο κώδικας Reed-Solomon χάνει τη διαφάνειά του εάν χρησιμοποιείται εικονικό γέμισμα μηδέν. Για το λόγο αυτό είναι υποχρεωτικό να επιλυθεί η έννοια των δεδομένων (δηλαδή, αληθές ή συμπληρωμένο) πριν από την αποκωδικοποίηση Reed-Solomon.
Στην περίπτωση του προγράμματος Voyager, οι κώδικες R-S επιτυγχάνουν σχεδόν βέλτιστη απόδοση όταν συνδέονται με τον (7, 1/2) συνελικτικό (Viterbi) εσωτερικό κώδικα. Δεδομένου ότι απαιτούνται δύο σύμβολα ελέγχου για κάθε σφάλμα που πρέπει να διορθωθεί, αυτό οδηγεί σε συνολικά 32 σύμβολα ελέγχου και 223 σύμβολα πληροφορίας ανά κωδική λέξη.
Επιπλέον, οι κωδικοποιημένες λέξεις Reed-Solomon μπορούν να παρεμβάλλονται σε συμβολική βάση προτού κωδικοποιηθούν με συνελικτική κωδικοποίηση. Εφόσον αυτό διαχωρίζει τα σύμβολα σε μια κωδική λέξη, είναι λιγότερο πιθανό μια έκρηξη από τον αποκωδικοποιητή Viterbi να διαταράξει περισσότερα από ένα σύμβολο Reed-Solomon σε οποιαδήποτε κωδική λέξη.
Βασική ιδέα
Η βασική ιδέα πίσω από έναν κώδικα Reed-Solomon είναι ότι τα δεδομένα που κωδικοποιούνται αρχικά απεικονίζονται ως πολυώνυμο. Ο κώδικας βασίζεται σε ένα θεώρημα από την άλγεβρα που δηλώνει ότι οποιαδήποτε k διαφορετικά σημεία προσδιορίζουν μοναδικά ένα πολυώνυμο βαθμού το πολύ k-1.
Ο αποστολέας καθορίζει ένα πολυώνυμο βαθμού k - 1 {\displaystyle k-1}
, πάνω σε ένα πεπερασμένο πεδίο, το οποίο αντιπροσωπεύει τα k {\displaystyle k}
σημεία δεδομένων. Το πολυώνυμο στη συνέχεια "κωδικοποιείται" από την αξιολόγησή του σε διάφορα σημεία, και αυτές οι τιμές είναι αυτό που πραγματικά αποστέλλεται. Κατά τη διάρκεια της μετάδοσης, ορισμένες από αυτές τις τιμές μπορεί να αλλοιωθούν. Επομένως, αποστέλλονται στην πραγματικότητα περισσότερα από k σημεία. Εφόσον αρκετές τιμές λαμβάνονται σωστά, ο δέκτης μπορεί να συμπεράνει ποιο ήταν το αρχικό πολυώνυμο και να αποκωδικοποιήσει τα αρχικά δεδομένα.
Με την ίδια έννοια που μπορεί κανείς να διορθώσει μια καμπύλη με παρεμβολή πέρα από ένα κενό, ένας κώδικας Reed-Solomon μπορεί να γεφυρώσει μια σειρά σφαλμάτων σε ένα μπλοκ δεδομένων για να ανακτήσει τους συντελεστές του πολυωνύμου που σχεδίασε την αρχική καμπύλη.
Ιστορία
Ο κώδικας εφευρέθηκε το 1960 από τους Irving S. Reed και Gustave Solomon, οι οποίοι ήταν τότε μέλη του Εργαστηρίου Λίνκολν του MIT. Το θεμελιώδες άρθρο τους είχε τίτλο "Πολυωνυμικοί κώδικες πάνω σε ορισμένα πεπερασμένα πεδία". Όταν γράφτηκε, η ψηφιακή τεχνολογία δεν ήταν αρκετά προηγμένη για την εφαρμογή της έννοιας. Η πρώτη εφαρμογή, το 1982, των κωδίκων RS σε προϊόντα μαζικής παραγωγής ήταν ο συμπαγής δίσκος, όπου χρησιμοποιούνται δύο διαπλεκόμενοι κώδικες RS. Ένας αποτελεσματικός αλγόριθμος αποκωδικοποίησης για κώδικες RS μεγάλων αποστάσεων αναπτύχθηκε από τους Elwyn Berlekamp και James Massey το 1969. Σήμερα οι κώδικες RS χρησιμοποιούνται σε σκληρούς δίσκους, DVD, τηλεπικοινωνίες και πρωτόκολλα ψηφιακής μετάδοσης.
