Προέλευση και ευρύτερη χρήση
Οι κώδικες Reed–Solomon περιγράφηκαν από τους Irving S. Reed και Gustave Solomon το 1960. Δουλεύουν σε ολόκληρα σύμβολα, συνήθως byte, και όχι σε μεμονωμένα bit, κάτι που τους κάνει καλούς στη διαχείριση ριπών φθοράς, όπως μια γρατζουνιά ή μια μουτζούρα.
Η ίδια οικογένεια κωδίκων προστατεύει δεδομένα σε CD, DVD και δίσκους Blu-ray, σε κάποιες ψηφιακές τηλεοπτικές και δορυφορικές ζεύξεις και σε άλλους δισδιάστατους γραμμωτούς κωδικούς, όπως τα Data Matrix ECC 200, Aztec code και PDF417.
Πώς τον χρησιμοποιούν οι κωδικοί QR
Ο κωδικός QR αντιμετωπίζει κάθε κωδική λέξη των 8 bit ως στοιχείο του πεπερασμένου σώματος GF(256), που χτίζεται με το πρωταρχικό πολυώνυμο x^8 + x^4 + x^3 + x^2 + 1 (hex 0x11D). Οι κωδικές λέξεις δεδομένων διαιρούνται με ένα πολυώνυμο γεννήτορα και το υπόλοιπο γίνεται οι κωδικές λέξεις διόρθωσης σφαλμάτων που προστίθενται σε αυτές.
Οι μεγαλύτεροι κωδικοί χωρίζουν τα δεδομένα τους σε αρκετά μπλοκ, καθένα με δικές του κωδικές λέξεις διόρθωσης σφαλμάτων. Τα μπλοκ διαπλέκονται έπειτα όταν οι κωδικές λέξεις τοποθετούνται στο πλέγμα, ώστε ένα σημείο φθοράς να απλώνεται σε πολλά μπλοκ αντί να καταβάλλει ένα.
Πόσα μπορεί να διορθώσει
Με n κωδικές λέξεις διόρθωσης σφαλμάτων σε ένα μπλοκ, ο αποκωδικοποιητής μπορεί να διορθώσει έως n/2 κωδικές λέξεις άγνωστης θέσης ή έως n κωδικές λέξεις γνωστής θέσης, που λέγονται διαγραφές (erasures). Οι μικτές περιπτώσεις ακολουθούν τον κανόνα ότι κάθε σφάλμα μετράει διπλά και κάθε διαγραφή μία φορά.
Γι' αυτό ένας κωδικός με καθαρή, επίπεδη περιοχή καλυμμένη από λογότυπο μπορεί να σαρώνεται ακόμη: ένας έξυπνος αναγνώστης μπορεί να αντιμετωπίσει την καλυμμένη περιοχή ως διαγραφές, ενώ η τυχαία φθορά διορθώνεται δυσκολότερα, γιατί ο αποκωδικοποιητής πρέπει πρώτα να τη βρει.
- Άγνωστα σφάλματα: έως το μισό του αριθμού των κωδικών λέξεων EC
- Διαγραφές (γνωστές θέσεις): έως τον αριθμό των κωδικών λέξεων EC
- Σώμα: GF(256), πολυώνυμο 0x11D
- Τα μπλοκ διαπλέκονται για να απλώνεται η φθορά ριπής