Χάμινγκ Code: Εντοπισμός και Διόρθωση Σφαλμάτων με Παραδείγματα

⚡ Έξυπνη Σύνοψη

Ο κώδικας Hamming είναι ένας γραμμικός κώδικας διόρθωσης σφαλμάτων που προσθέτει πλεονάζοντα bit ισοτιμίας σε θέσεις δύναμης του δύο, επιτρέποντας σε έναν δέκτη να ανιχνεύει σφάλματα έως και δύο bit και να διορθώνει αυτόματα οποιοδήποτε σφάλμα ενός bit κατά τη μετάδοση δεδομένων.

🧭 Σκοπός: Ο κώδικας Hamming ανιχνεύει και διορθώνει σφάλματα μετάδοσης ενσωματώνοντας bits ισοτιμίας που εντοπίζουν την ακριβή θέση ενός κατεστραμμένου bit.
🔢 Περιττά bits: Ο αριθμός των bit ισοτιμίας (p) ικανοποιεί τον κανόνα 2^p ≥ n + p + 1, όπου n είναι ο αριθμός των bit δεδομένων.
📍 Τοποθέτηση: Τα bits ισοτιμίας καταλαμβάνουν θέσεις δύναμης του δύο — 1, 2, 4 και 8 — ενώ τα bits δεδομένων γεμίζουν τις υπόλοιπες θέσεις.
🧮 Χάμινγκ(7,4): Μια συνηθισμένη μορφή κωδικοποιεί τέσσερα bit δεδομένων σε επτά συνολικά bit χρησιμοποιώντας τρία bit ισοτιμίας.
🧯 Περιορισμός: Ο τυπικός κώδικας Hamming διορθώνει μόνο σφάλματα ενός bit. Ένα επιπλέον bit συνολικής ισοτιμίας προσθέτει ανίχνευση διπλού σφάλματος (SECDED).
🤖 Βοήθεια AI: Οι αποκωδικοποιητές μηχανικής μάθησης βοηθούν στην επισήμανση θορυβωδών καναλιών και μοτίβων σφαλμάτων που ενδέχεται να μην εντοπίζονται από μόνοι τους με τη χρήση διορθωμένων κωδικών.

Περισσότερα

Τι είναι το Σφάλμα;

TransmitΤα δεδομένα που έχουν υποστεί επεξεργασία ενδέχεται να καταστραφούν κατά την επικοινωνία. Είναι πιθανό να επηρεαστούν από εξωτερικό θόρυβο ή άλλες φυσικές βλάβες. Σε μια τέτοια περίπτωση, τα δεδομένα εισόδου δεν μπορούν να είναι τα ίδια με τα δεδομένα εξόδου. Αυτή η αναντιστοιχία είναι γνωστή ως «Σφάλμα».

Τα σφάλματα δεδομένων μπορεί να προκαλέσουν απώλεια σημαντικών ή ασφαλών δεδομένων. Το μεγαλύτερο μέρος της μεταφοράς δεδομένων σε ψηφιακά συστήματα λαμβάνει τη μορφή «μεταφοράς bit» και ακόμη και μια μικρή αλλαγή σε ένα μόνο bit μπορεί να επηρεάσει την απόδοση ολόκληρου του συστήματος. Σε μια ακολουθία δεδομένων, εάν ένα 1 αλλάξει σε 0 ή ένα 0 αλλάξει σε 1, αυτό ονομάζεται «σφάλμα bit».

Τύποι σφαλμάτων

Υπάρχουν κυρίως τρεις τύποι σφαλμάτων bit που εμφανίζονται όταν τα δεδομένα transmitαπό τον αποστολέα στον παραλήπτη. Το παρακάτω διάγραμμα δείχνει πώς κάθε τύπος επηρεάζει μια ακολουθία δεδομένων:

Σφάλματα ενός bit
Πολλά σφάλματα bit
Σφάλματα ριπής

Σφάλματα ενός bit

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

Πολλαπλά λάθη bit

Όταν δύο ή περισσότερα bit μιας ακολουθίας δεδομένων αλλάζουν μεταξύ transmitter και τον δέκτη, είναι γνωστό ως «σφάλμα πολλαπλών bit».

Αυτός ο τύπος σφάλματος εμφανίζεται τόσο σε σειριακά όσο και σε παράλληλα δίκτυα επικοινωνίας δεδομένων.

Σφάλματα ριπής

Μια αλλαγή σε ένα σύνολο διαδοχικών bit σε μια ακολουθία δεδομένων είναι γνωστή ως «σφάλμα burst». Το μήκος ενός σφάλματος burst μετριέται από το πρώτο bit που άλλαξε έως το τελευταίο bit που άλλαξε.

Τι είναι η Ανίχνευση και η Διόρθωση Σφάλματος;

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

Ανίχνευση σφαλμάτων είναι μια μέθοδος εύρεσης σφαλμάτων που υπάρχουν στα δεδομένα transmitαπό ένα transmitter σε έναν δέκτη σε ένα επικοινωνία δεδομένων σύστημα.

Οι κώδικες πλεονασμού χρησιμοποιούνται για την εύρεση αυτών των σφαλμάτων προσθέτοντας επιπλέον bit στα δεδομένα όταν αυτά είναι transmitαπό την πηγή. Αυτά τα επιπλέον bit ονομάζονται «κώδικες ανίχνευσης σφαλμάτων». Οι τρεις πιο συνηθισμένοι τύποι κώδικα ανίχνευσης σφαλμάτων είναι:

Έλεγχος ισοτιμίας
Κυκλικός έλεγχος πλεονασμού (CRC)
Διαχρονικός έλεγχος πλεονασμού (LRC)

Έλεγχος ισοτιμίας

Είναι επίσης γνωστός ως έλεγχος ισοτιμίας.
Παρέχει έναν οικονομικά αποδοτικό μηχανισμό για την ανίχνευση σφαλμάτων.
Σε αυτήν την τεχνική, το πλεονάζον bit που προστίθεται σε κάθε μονάδα δεδομένων είναι γνωστό ως bit ισοτιμίας. Ορίζεται έτσι ώστε ο συνολικός αριθμός των 1 στη μονάδα να γίνεται άρτιος (ζυγή ισοτιμία) ή περιττός (περιττή ισοτιμία).

Διαχρονικός Έλεγχος Πλεονασμού

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

Κυκλικός έλεγχος απόρριψης

Ο κυκλικός έλεγχος πλεονασμού προσθέτει μια ακολουθία πλεοναζόντων bit στο τέλος της μονάδας δεδομένων, έτσι ώστε η προκύπτουσα μονάδα δεδομένων να διαιρείται ακριβώς με έναν δεύτερο, προκαθορισμένο δυαδικό αριθμό.

Στον προορισμό, τα εισερχόμενα δεδομένα διαιρούνται με τον ίδιο αριθμό. Εάν δεν υπάρχει υπόλοιπο, η μονάδα δεδομένων θεωρείται σωστή και γίνεται δεκτή. Διαφορετικά, υποδηλώνει ότι η μονάδα δεδομένων υπέστη ζημιά κατά τη μετάδοση και πρέπει να απορριφθεί.

Τι είναι το Χάμινγκ Code?

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

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

Ιστορία του Χάμινγκ Code

Ο κώδικας Hamming είναι μια τεχνική που αναπτύχθηκε από τον RW Hamming για την ανίχνευση και διόρθωση σφαλμάτων.
Μπορεί να εφαρμοστεί σε μονάδες δεδομένων οποιουδήποτε μήκους και χρησιμοποιεί τη σχέση μεταξύ bit δεδομένων και bit πλεονασμού.
Ο Χάμινγκ εργάστηκε πάνω στο πρόβλημα της διόρθωσης σφαλμάτων και ανέπτυξε μια ολοένα και πιο ισχυρή σειρά αλγορίθμων.
Το 1950, δημοσίευσε τον κώδικα Hamming, ο οποίος χρησιμοποιείται ευρέως μέχρι σήμερα σε εφαρμογές όπως η μνήμη ECC.

Εφαρμογές του Χάμινγκ Code

Ακολουθούν μερικές συνηθισμένες εφαρμογές του κώδικα Hamming:

Δορυφόροι
Μνήμη υπολογιστή (ECC RAM)
μόντεμ
PlasmaCAM
Ανοίξτε τους συνδέσμους
Θωρακισμένο σύρμα
Ενσωματωμένοι επεξεργαστές

Πλεονεκτήματα του Χάμινγκ Code

Ο κώδικας Hamming είναι αποτελεσματικός σε δίκτυα όπου οι ροές δεδομένων εκτίθενται σε σφάλματα ενός bit.
Δεν ανιχνεύει μόνο ένα σφάλμα bit, αλλά σας βοηθά επίσης να εντοπίσετε το bit που περιέχει το σφάλμα, ώστε να μπορεί να διορθωθεί.
Η ευκολία χρήσης των κωδίκων Hamming τους καθιστά κατάλληλους για τη μνήμη του υπολογιστή και τη διόρθωση μεμονωμένων σφαλμάτων.

Μειονεκτήματα του Χάμινγκ Code

Πρόκειται για έναν κώδικα ανίχνευσης και διόρθωσης σφαλμάτων ενός bit. Εάν διαπιστωθεί ότι πολλά bit είναι εσφαλμένα, το αποτέλεσμα μπορεί να ανατρέψει ένα άλλο bit που ήταν στην πραγματικότητα σωστό, αλλοιώνοντας περαιτέρω τα δεδομένα.
Ο αλγόριθμος κώδικα Hamming μπορεί να επιλύσει μόνο προβλήματα ενός bit.

Πώς να κωδικοποιήσετε ένα μήνυμα σε Hamming Code

Η διαδικασία που χρησιμοποιεί ο αποστολέας για να κωδικοποιήσει το μήνυμα περιλαμβάνει τα ακόλουθα τρία βήματα:

Υπολογίστε τον συνολικό αριθμό των πλεοναζόντων bit.
Προσδιορίστε τη θέση των πλεοναζόντων bit.
Υπολογίστε την τιμή κάθε πλεονάζοντος bit.

Όταν τα πλεονάζοντα bit ενσωματωθούν στο μήνυμα, η πλήρης κωδική λέξη αποστέλλεται στον παραλήπτη.

Βήμα 1) Υπολογίστε τον συνολικό αριθμό των πλεοναζόντων bit.

Υποθέστε ότι το μήνυμα περιέχει n bits δεδομένων και p περιττά bits, προστιθέμενα έτσι ώστε 2^p μπορεί να υποδείξει τουλάχιστον (n + p + 1) διαφορετικές καταστάσεις.

Εδώ, το (n + p) λαμβάνει υπόψη τη θέση ενός σφάλματος σε κάθε μία από τις θέσεις των bit (n + p), και μία επιπλέον κατάσταση υποδεικνύει ότι δεν υπάρχει σφάλμα. Επειδή τα bit ισοτιμίας p μπορούν να υποδείξουν 2^p πολιτείες, 2^p πρέπει να είναι τουλάχιστον ίσο με (n + p + 1).

Βήμα 2) Τοποθετήστε τα περιττά κομμάτια στις σωστές τους θέσεις.

Τα p πλεονάζοντα bit τοποθετούνται σε θέσεις bit που είναι δυνάμεις του 2 — για παράδειγμα, 1, 2, 4, 8 και 16. Αναφέρονται ως p.₁ (στη θέση 1), σελ₂ (στη θέση 2), σελ₃ (στη θέση 4) και ούτω καθεξής.

Βήμα 3) Υπολογίστε την τιμή κάθε πλεονάζοντος bit.

Κάθε πλεονάζον bit είναι ένα bit ισοτιμίας που κάνει τον αριθμό των 1 στην ομάδα του είτε άρτιο είτε περιττό. Οι δύο τύποι ισοτιμίας είναι:

Αρτια ισοτιμία: Ο συνολικός αριθμός των 1 στις καλυμμένες θέσεις γίνεται άρτιος.
Περιττή ισοτιμία: Ο συνολικός αριθμός των 1 στις καλυμμένες θέσεις γίνεται περιττός.

Κάθε bit ισοτιμίας καλύπτει ένα συγκεκριμένο σύνολο θέσεων, που καθορίζεται από τη δυαδική αναπαράσταση των αριθμών θέσης:

p₁ ελέγχει κάθε θέση της οποίας η δυαδική τιμή έχει 1 στο λιγότερο σημαντικό bit — θέσεις 1, 3, 5, 7, 9, 11, και ούτω καθεξής.
p₂ ελέγχει κάθε θέση της οποίας η δυαδική τιμή έχει 1 στο δεύτερο bit από τα δεξιά — θέσεις 2, 3, 6, 7, 10, 11, και ούτω καθεξής.
p₃ ελέγχει κάθε θέση της οποίας η δυαδική τιμή έχει 1 στο τρίτο bit από τα δεξιά — θέσεις 4 έως 7, 12 έως 15, και ούτω καθεξής.

Παράδειγμα εργασίας (7,4): Θεωρήστε τα τέσσερα bit δεδομένων 1011Απαιτούνται τρία bit ισοτιμίας (2³ = 8 ≥ 4 + 3 + 1), δίνοντας μια κωδική λέξη επτά bit που έχει ως p₁ p₂ d₁ p₃ d₂ d₃ d₄Η τοποθέτηση των δεδομένων τοποθετεί τις θέσεις 3, 5, 6, 7 = 1, 0, 1, 1. Χρησιμοποιώντας άρτια ισοτιμία: p₁ καλύπτει τις θέσεις 1, 3, 5, 7 (bits 1, 0, 1 → p₁ = 0); σ₂ καλύπτει 2, 3, 6, 7 (bits 1, 1, 1 → p₂ = 1); σ₃ καλύπτει 4, 5, 6, 7 (bits 0, 1, 1 → p₃ = 0). Το transmitΗ κωδική λέξη ted είναι επομένως 0110011.

Πώς να αποκωδικοποιήσετε ένα μήνυμα στο Hamming Code

Ο παραλήπτης λαμβάνει το εισερχόμενο μήνυμα και εκτελεί επανυπολογισμούς για να εντοπίσει και να διορθώσει σφάλματα. Η διαδικασία επανυπολογισμού χρησιμοποιεί τα ακόλουθα βήματα:

Μετρήστε τον αριθμό των πλεονάζοντων bit.
Τοποθετήστε σωστά όλα τα πλεονάζοντα κομμάτια.
Εκτελέστε τον έλεγχο ισοτιμίας.

Βήμα 1) Μετρήστε τον αριθμό των πλεοναζόντων bit. Χρησιμοποιήστε τον ίδιο τύπο όπως για την κωδικοποίηση: 2^p ≥ n + p + 1, όπου n είναι ο αριθμός των bit δεδομένων και p είναι ο αριθμός των πλεοναζόντων bit.

Βήμα 2) Τοποθετήστε σωστά όλα τα πλεονάζοντα κομμάτια. Κάθε πλεονάζον bit βρίσκεται σε μια θέση bit που είναι δύναμη του 2 — για παράδειγμα, 1, 2, 4 και 8.

Βήμα 3) Εκτελέστε τον έλεγχο ισοτιμίας. Τα bits ισοτιμίας υπολογίζονται εκ νέου από τα bits δεδομένων και τα ληφθέντα πλεονάζοντα bits:

p₁ = ισοτιμία (1, 3, 5, 7, 9, 11, …)
p₂ = ισοτιμία (2, 3, 6, 7, 10, 11, …)
p₃ = ισοτιμία (4–7, 12–15, 20–23, …)

Τα επανυπολογισμένα bit ισοτιμίας σχηματίζουν μαζί έναν δυαδικό αριθμό. Εάν αυτός ο αριθμός είναι μηδέν, δεν υπάρχει σφάλμα. Διαφορετικά, η τιμή του δίνει την ακριβή θέση του μοναδικού κατεστραμμένου bit, το οποίο στη συνέχεια αντιστρέφεται για να διορθωθεί το μήνυμα.

Συχνές Ερωτήσεις

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

Η μέθοδος Hamming(7,4) κωδικοποιεί τέσσερα bit δεδομένων σε μια κωδική λέξη επτά bit προσθέτοντας τρία bit ισοτιμίας. Διορθώνει οποιοδήποτε σφάλμα ενός bit και ανιχνεύει σφάλματα δύο bit. Η σημειογραφία (n, k) δηλώνει το συνολικό μήκος της κωδικής λέξης n και τον αριθμό των bit δεδομένων k.

Ένα bit ισοτιμίας ανιχνεύει μόνο έναν περιττό αριθμό σφαλμάτων bit και δεν μπορεί να τα εντοπίσει ή να τα διορθώσει. Ο κώδικας Hamming χρησιμοποιεί πολλαπλά bit ισοτιμίας σε θέσεις δύναμης του δύο, επομένως εντοπίζει ακριβώς το bit που έχει αποτύχει και το διορθώνει αυτόματα.

Ο βασικός κώδικας Hamming διορθώνει σφάλματα ενός bit, αλλά μπορεί να διορθώσει εσφαλμένα σφάλματα δύο bit. Η προσθήκη ενός bit συνολικής ισοτιμίας που καλύπτει ολόκληρη την κωδική λέξη δημιουργεί SECDED (διόρθωση ενός σφάλματος, ανίχνευση διπλού σφάλματος), αυξάνοντας την ελάχιστη απόσταση σε τέσσερα και ανιχνεύοντας αξιόπιστα σφάλματα διπλού bit.

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

Ο κώδικας Hamming είναι ένας γραμμικός κώδικας μπλοκ. Επεξεργάζεται ένα μπλοκ δεδομένων σταθερού μεγέθους ταυτόχρονα και προσθέτει bits ισοτιμίας, σε αντίθεση με τους συνελικτικούς κώδικες που κωδικοποιούν μια συνεχή ροή bit χρησιμοποιώντας τη μνήμη προηγούμενων bit. Αυτό καθιστά τον κώδικα Hamming απλό και γρήγορο.

Τα μοντέλα μηχανικής μάθησης μαθαίνουν τα μοτίβα θορύβου ενός καναλιού και προβλέπουν πιθανά σφάλματα bit, βελτιώνοντας την ακρίβεια αποκωδικοποίησης πέρα από τα καθορισμένα σχήματα. Οι αποκωδικοποιητές που βασίζονται στην τεχνητή νοημοσύνη για LDPC και πολικούς κώδικες βοηθούν πλέον τα σύγχρονα συστήματα 5G και αποθήκευσης όπου ο κλασικός κώδικας Hamming από μόνος του δεν επαρκεί.

GitHub Copilot μπορεί να υποστηρίξει συναρτήσεις κωδικοποιητή και αποκωδικοποιητή, να δημιουργήσει μάσκες ισοτιμίας bit και να σχεδιάσει δοκιμές μονάδων από ένα σύντομο σχόλιο. Επαληθεύστε τα μαθηματικά θέσης bit και την ομάδα ισοτιμίας.pingπροσεκτικά, επειδή η ανεξάρτητη ευρετηρίαση είναι μια συχνή πηγή σφαλμάτων στον παραγόμενο κώδικα.