Hamming Code: Ανίχνευση σφαλμάτων και διόρθωση με παραδείγματα

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

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

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

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

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

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

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

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

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

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

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

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

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

Τι είναι η ανίχνευση και η διόρθωση σφαλμάτων;

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

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

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

Τρεις τύποι κωδικών ανίχνευσης σφαλμάτων είναι:

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

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

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

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

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

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

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

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

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

Η ιστορία του κώδικα Hamming

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

Εφαρμογή του κώδικα Hamming

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

• Δορυφόροι
• Μνήμη υπολογιστή
• μόντεμ
• PlasmaCAM
• Ανοίξτε τους συνδέσμους
• Σύρμα θωράκισης
• Ενσωματωμένος επεξεργαστής

Πλεονεκτήματα του κώδικα Hamming

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

Μειονεκτήματα του κώδικα Hamming

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

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

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

• Υπολογισμός συνολικού αριθμού περιττών bit.
• Έλεγχος της θέσης των περιττών bits.
• Τέλος, ο υπολογισμός των τιμών αυτών των περιττών bits.

Όταν τα παραπάνω περιττά bits ενσωματωθούν στο μήνυμα, αποστέλλεται στον χρήστη.

Βήμα 1) Υπολογισμός του συνολικού αριθμού περιττών bit.

Ας υποθέσουμε ότι το μήνυμα περιέχει:

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

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

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

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

Βήμα 3) Υπολογισμός των τιμών του πλεονάζοντος bit.

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

Οι δύο τύποι ισοτιμίας είναι ;

• Ο συνολικός αριθμός των bit στο μήνυμα που γίνεται ζυγός ονομάζεται ζυγή ισοτιμία.
• Ο συνολικός αριθμός των bit στο μήνυμα που γίνεται περιττός ονομάζεται περιττή ισοτιμία.

Εδώ, όλο το περιττό bit, p1, πρέπει να υπολογιστεί ως ισοτιμία. Θα πρέπει να καλύπτει όλες τις θέσεις bit των οποίων η δυαδική αναπαράσταση θα πρέπει να περιλαμβάνει ένα 1 στην 1η θέση εξαιρουμένης της θέσης του p1.

Το P1 είναι το bit ισοτιμίας για κάθε bit δεδομένων σε θέσεις των οποίων η δυαδική αναπαράσταση περιλαμβάνει ένα 1 στη λιγότερο σημαντική θέση χωρίς να περιλαμβάνει 1 Like (3, 5, 7, 9, …. )

Το P2 είναι το bit ισοτιμίας για κάθε bit δεδομένων σε θέσεις των οποίων η δυαδική αναπαράσταση περιλαμβάνει 1 στη θέση 2 από δεξιά, χωρίς να περιλαμβάνει 2 Like (3, 6, 7, 10, 11,…)

Το P3 είναι το bit ισοτιμίας για κάθε bit σε θέσεις των οποίων η δυαδική αναπαράσταση περιλαμβάνει 1 στη θέση 3 από δεξιά και όχι 4 Like (5-7, 12-15,… )

Αποκρυπτογράφηση μηνύματος σε κώδικα Hamming

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

Η διαδικασία επανυπολογισμού γίνεται στα ακόλουθα βήματα:

• Μετρώντας τον αριθμό των περιττών bits.
• Σωστή τοποθέτηση όλων των περιττών bits.
• Έλεγχος ισοτιμίας

Βήμα 1) Μετρώντας τον αριθμό των περιττών bits

Μπορείτε να χρησιμοποιήσετε τον ίδιο τύπο για την κωδικοποίηση, τον αριθμό των περιττών bit

2^p ? n + p + 1

Εδώ, ο αριθμός των bit δεδομένων και το p είναι ο αριθμός των περιττών bit.

Βήμα 2) Τοποθετώντας σωστά όλα τα περιττά bits

Εδώ, το p είναι ένα περιττό bit το οποίο βρίσκεται σε θέσεις bit ισχύος 2, για παράδειγμα, 1, 2, 4, 8, κ.λπ.

Βήμα 3) Έλεγχος ισοτιμίας

Τα bit ισοτιμίας πρέπει να υπολογίζονται με βάση τα bit δεδομένων και τα πλεονάζοντα bit.

p1 = ισοτιμία(1, 3, 5, 7, 9, 11…)

p2 = ισοτιμία(2, 3, 6, 7, 10, 11… )

p3 = ισοτιμία(4-7, 12-15, 20-23… )

Σύνοψη

• Τα μεταδιδόμενα δεδομένα μπορεί να καταστραφούν κατά την επικοινωνία
• Τρεις τύποι σφαλμάτων bit είναι 1) Σφάλματα ενός bit 2) Σφάλμα πολλαπλών bit 3) σφάλματα Burst Bit
• Η αλλαγή που έγινε σε ένα bit σε ολόκληρη την ακολουθία δεδομένων είναι γνωστή ως "Σφάλμα ενός bit".
• Στην ακολουθία δεδομένων, εάν υπάρχει αλλαγή σε δύο ή περισσότερα bit μιας ακολουθίας δεδομένων από έναν πομπό προς τον δέκτη, είναι γνωστή ως "Σφάλματα πολλαπλών bit".
• Η αλλαγή του συνόλου των bit στην ακολουθία δεδομένων είναι γνωστή ως "Σφάλμα ριπής".
• Η ανίχνευση σφαλμάτων είναι μια μέθοδος ανίχνευσης των σφαλμάτων που υπάρχουν στα δεδομένα που μεταδίδονται από έναν πομπό σε δέκτη σε ένα σύστημα επικοινωνίας δεδομένων
• Τρεις τύποι κωδικών ανίχνευσης σφαλμάτων είναι 1) Έλεγχος ισοτιμίας 2) Έλεγχος κυκλικού πλεονασμού (CRC) 3) Διαχρονικός έλεγχος πλεονασμού (LRC)
• Ο κώδικας Hamming είναι ένας κωδικός γραμμής που είναι χρήσιμος για ανίχνευση σφαλμάτων έως και δύο σφαλμάτων άμεσα bit. Είναι ικανό για σφάλματα ενός bit.
• Ο κώδικας Hamming είναι μια τεχνική που δημιουργήθηκε από την RWHamming για τον εντοπισμό σφαλμάτων.
• Συνήθεις εφαρμογές χρήσης του κώδικα Hamming είναι η Μνήμη Υπολογιστών Δορυφόρων, τα Μόντεμ, ο Ενσωματωμένος Επεξεργαστής κ.λπ.
• Το μεγαλύτερο πλεονέκτημα της μεθόδου κώδικα hamming είναι αποτελεσματικό σε δίκτυα όπου οι ροές δεδομένων δίνονται για τα σφάλματα ενός bit.
• Το μεγαλύτερο μειονέκτημα της μεθόδου κώδικα hamming είναι ότι μπορεί να λύσει μόνο ζητήματα μεμονωμένων bits.
• Μπορούμε να εκτελέσουμε τη διαδικασία κρυπτογράφησης και αποκωδικοποίησης του μηνύματος με τη βοήθεια του κώδικα hamming.