Κωδικός Hamming: Παραδείγματα διόρθωσης σφαλμάτων

Πίνακας περιεχομένων:

Anonim

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

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

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

Σε αυτό το σεμινάριο κώδικα Hamming, θα μάθετε:

  • Τι είναι το σφάλμα;
  • Τύποι σφαλμάτων
  • Τι είναι η ανίχνευση σφαλμάτων και η διόρθωση;
  • Τι είναι ο κωδικός Hamming;
  • Ιστορικό κώδικα Hamming
  • Εφαρμογή κώδικα Hemming:
  • Πλεονεκτήματα του κώδικα Hamming
  • Μειονεκτήματα του κώδικα Hamming
  • Διαδικασία κωδικοποίησης ενός μηνύματος χρησιμοποιώντας Hamming Code
  • Διαδικασία αποκρυπτογράφησης μηνύματος σε κώδικα Hamming

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

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

  • Σφάλματα ενός bit
  • Πολλαπλά σφάλματα bit
  • Σφάλματα έκρηξης

Σφάλματα ενός μπιτ

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

Πολλαπλά σφάλματα Bit

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

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

Σφάλματα έκρηξης

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

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

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

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

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

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

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

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

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

Έλεγχος διαμήκους πλεονασμού

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

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

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

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

Τι είναι ο κωδικός Hamming;

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

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

Ιστορικό κώδικα Hamming

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

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

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

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

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

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

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

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

Διαδικασία κωδικοποίησης ενός μηνύματος χρησιμοποιώντας Hamming Code

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

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

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

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

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

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

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

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

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

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

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

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

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

Εδώ, όλο το περιττό 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) Θέτοντας σωστά όλα τα περιττά κομμάτια

Εδώ, το 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) Σφάλματα μπιτ μπιτ 2) Σφάλμα πολλαπλών μπιτ 3) Σφάλματα ριπής
  • Η αλλαγή που έγινε σε ένα bit σε ολόκληρη την ακολουθία δεδομένων είναι γνωστή ως "Single bit error".
  • Στην ακολουθία δεδομένων, εάν υπάρχει αλλαγή σε δύο ή περισσότερα bit μιας ακολουθίας δεδομένων ενός πομπού σε δέκτη, είναι γνωστό ως "Πολλαπλά σφάλματα bit".
  • Η αλλαγή του συνόλου των bit στην ακολουθία δεδομένων είναι γνωστή ως "Burst error".
  • Η ανίχνευση σφαλμάτων είναι μια μέθοδος ανίχνευσης των σφαλμάτων που υπάρχουν στα δεδομένα που μεταδίδονται από έναν πομπό σε έναν δέκτη σε ένα σύστημα επικοινωνίας δεδομένων
  • Τρεις τύποι κωδικών ανίχνευσης σφαλμάτων είναι 1) Έλεγχος ισοτιμίας 2) Έλεγχος κυκλικού πλεονασμού (CRC) 3) Έλεγχος διαμήκους πλεονασμού (LRC)
  • Ο κωδικός Hamming είναι ένας κώδικας γραμμής που είναι χρήσιμος για την ανίχνευση σφαλμάτων έως και δύο άμεσων σφαλμάτων bit. Είναι ικανό για σφάλματα ενός bit.
  • Ο κωδικός Hamming είναι μια τεχνική που δημιουργείται από το RWHamming για τον εντοπισμό σφαλμάτων
  • Συνήθεις εφαρμογές της χρήσης κώδικα Hemming είναι η δορυφορική μνήμη υπολογιστή, τα μόντεμ, ο ενσωματωμένος επεξεργαστής κ.λπ.
  • Το μεγαλύτερο πλεονέκτημα της μεθόδου κωδικού σφυρηλάτησης είναι αποτελεσματικό σε δίκτυα όπου παρέχονται ροές δεδομένων για σφάλματα ενός bit.
  • Το μεγαλύτερο μειονέκτημα της μεθόδου κωδικού σφυρηλάτησης είναι ότι μπορεί να επιλύσει ζητήματα μόνο μπιτ.
  • Μπορούμε να εκτελέσουμε τη διαδικασία κρυπτογράφησης και αποκωδικοποίησης του μηνύματος με τη βοήθεια κώδικα hamming.