Δημιουργία πινάκων κωδικών μπλοκ. Κατασκευή του πίνακα επαλήθευσης

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

,

και η έξοδος του κωδικοποιητή είναι ένα διάνυσμα χαρακτήρων

.

Η λειτουργία κωδικοποίησης που εκτελείται σε έναν γραμμικό δυαδικό κώδικα μπλοκ μπορεί να αναπαρασταθεί από ένα σύνολο εξισώσεων της μορφής

(8.1.2)

όπου ή , και αντιπροσωπεύουν το γινόμενο του και . Γραμμικές εξισώσεις (8.1.2)

μπορεί επίσης να αναπαρασταθεί σε μορφή μήτρας

όπου είναι η μήτρα δημιουργίας του κώδικα, ίση με

(8.1.4)

Σημειώστε ότι μια αυθαίρετη κωδική λέξη είναι απλώς ένας γραμμικός συνδυασμός διανυσμάτων από ,

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

Οποιοσδήποτε πίνακας δημιουργίας κώδικα μπορεί να αναχθεί σε "συστηματική μορφή" εκτελώντας λειτουργίες σε σειρές (και αναδιάταξη στηλών):

, (8.1.6)

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

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

Παράδειγμα 8.1.1.Εξετάστε τον κωδικό (7, 4) με τον πίνακα δημιουργίας

. (8.1.7)

Μια τυπική κωδική λέξη μπορεί να εκφραστεί ως εξής:

όπου αντιπροσωπεύουν τέσσερα bit πληροφοριών, ένα αντιπροσωπεύει τρία bit ισοτιμίας, που ορίζονται ως εξής:

Ένας γραμμικός συστηματικός δυαδικός κωδικοποιητής μπλοκ μπορεί να υλοποιηθεί χρησιμοποιώντας έναν καταχωρητή μετατόπισης -bit, αθροιστές που σχετίζονται με τα αντίστοιχα κελιά καταχωρητή μετατόπισης και δημιουργώντας σύμβολα ισοτιμίας, τα οποία στη συνέχεια βρίσκονται προσωρινά σε έναν δεύτερο καταχωρητή μετατόπισης μήκους. Στη συνέχεια, τα bit πληροφοριών, ακολουθούμενα από τα bit ελέγχου, φεύγουν διαδοχικά από τους δύο καταχωρητές και τροφοδοτούνται στον διαμορφωτή. Αυτή η κωδικοποίηση απεικονίζεται στο Σχ. 8.1.1 για τον κωδικό (7, 4) από το παράδειγμα (8.1.1).

Ρύζι. 8.1.1. Καταχωρητής γραμμικής μετατόπισης για δυαδικό κώδικα (7,4)

Οποιοσδήποτε γραμμικός κώδικας σχετίζεται με έναν διπλό κωδικό διάστασης.

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

όπου σημαίνει ένα διάνυσμα στήλης που αποτελείται από μηδενικά και είναι η κωδική λέξη του κώδικα. Εφόσον η (8.1.9) ισχύει για οποιαδήποτε κωδική λέξη του κώδικα, ακολουθεί

όπου είναι τώρα ένας πίνακας με όλα τα μηδενικά στοιχεία.

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

(8.1.11)

Το αρνητικό πρόσημο (8.1.11) μπορεί να παραλειφθεί κατά την εργασία με δυαδικούς κωδικούς, αφού η αφαίρεση κατά είναι ταυτόσημη με την πρόσθεση κατά .

Παράδειγμα (8.1.2).Για τον συστηματικό κώδικα (7, 4), που δημιουργείται από τον πίνακα που ορίζεται από το (8.1.7), έχουμε, σύμφωνα με το (8.1.11), έναν πίνακα με τη μορφή

(8.1.12)

Τώρα η εξίσωση χωρίζεται σε τρεις εξισώσεις

(8.1.13)

Έτσι, βλέπουμε ότι το γινόμενο είναι ισοδύναμο με το άθροισμα των δοκιμαστικών συμβόλων με τους αντίστοιχους γραμμικούς συνδυασμούς των συμβόλων πληροφοριών που χρησιμοποιούνται για τον υπολογισμό. Αυτό σημαίνει ότι το (8.1.13) είναι ισοδύναμο με το (8.1.8).

Η μήτρα μπορεί να χρησιμοποιηθεί σε έναν αποκωδικοποιητή για να ελεγχθεί εάν η λαμβανόμενη κωδική λέξη ικανοποιεί τη συνθήκη (8.1.13), π.χ. . Έτσι, ο αποκωδικοποιητής ελέγχει τα λαμβανόμενα σύμβολα ισοτιμίας με τον αντίστοιχο γραμμικό συνδυασμό συμβόλων και , που σχηματίζουν τα σύμβολα ισοτιμίας κατά τη μετάδοση. Επομένως, είναι σύνηθες να το ονομάζουμε πίνακα ελέγχου που σχετίζεται με τον κώδικα.

Ας εκφράσουμε μια ιδέα σχετικά με τη σύνδεση μεταξύ της ελάχιστης απόστασης κωδικού και του πίνακα ελέγχου της. Το γινόμενο με αντιπροσωπεύει έναν γραμμικό συνδυασμό στηλών. Επειδή , τα διανύσματα στηλών εξαρτώνται γραμμικά. Ας πούμε τι σημαίνει η κωδική λέξη με το ελάχιστο βάρος ενός γραμμικού κώδικα. Πρέπει να ικανοποιεί την προϋπόθεση. Εφόσον το ελάχιστο βάρος είναι ίσο με την ελάχιστη απόσταση, προκύπτει ότι οι στήλες εξαρτώνται γραμμικά. Εναλλακτικά, μπορούμε να πούμε ότι το πολύ οι στήλες είναι γραμμικά ανεξάρτητες. Δεδομένου ότι η κατάταξη του πίνακα δεν είναι μεγαλύτερη από , έχουμε . Επομένως, έχει ένα άνω όριο. Ονομάζουμε τον κωδικό των συμβόλων πληροφοριών (σε όλους τους συνδυασμούς κωδικών) μηδενικά. Αυτά τα. Ο συντομευμένος κώδικας αποτελείται από κωδικές λέξεις. Η ελάχιστη απόσταση αυτών των κωδικών λέξεων κατά μήκος τουλάχιστονόχι μικρότερη από την ελάχιστη απόσταση πηγαίου κώδικα.

Ας εξετάσουμε έναν συστηματικό γραμμικό κώδικα που καθορίζεται από τον πίνακα δημιουργίας και ας κατασκευάσουμε έναν πίνακα της μορφής

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

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

Με βάση τις σχέσεις (6.4) και (6.6) έχουμε

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

Έτσι, ένας γραμμικός κώδικας μπορεί να καθοριστεί τόσο από τους πίνακες δημιουργίας (6.3) και ελέγχου (6.5) όσο και από τις σχέσεις (6.7) που καθορίζουν τη σύνδεση μεταξύ των συμβόλων ελέγχου και πληροφοριών των κωδικών λέξεων.

Θεώρημα 6.4.1.Ένας γραμμικός κώδικας έχει ελάχιστη απόσταση ίση με , εάν και μόνο εάν ο πίνακας ελέγχου περιέχει ένα σύνολο γραμμικά εξαρτώμενων στηλών και οποιοδήποτε σύνολο στηλών πίνακα είναι γραμμικά ανεξάρτητο.

Απόδειξη:Ας εξετάσουμε έναν γραμμικό κώδικα που καθορίζεται από έναν πίνακα ελέγχου διάστασης στη φόρμα

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

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

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

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

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

Λαμβάνοντας υπόψη τη δομή των πινάκων, μπορεί να γίνει το ακόλουθο συμπέρασμα. Και οι δύο πίνακες αποτελούνται από πολλά γραμμικά ανεξάρτητα διανύσματα, καθώς η παρουσία ενός πίνακα ταυτότητας στη δομή τους καθιστά αδύνατη την ύπαρξη ενός γραμμικού συνδυασμού σειρών μηδενικού αθροίσματος. Κατά συνέπεια, κάθε ένας από τους πίνακες μπορεί να θεωρηθεί ως η βάση κάποιου γραμμικού χώρου. Επιπλέον, καθένας από αυτούς τους χώρους είναι ένας υποχώρος ενός διανυσματικού χώρου που αποτελείται από όλα τα διανύσματα μήκους . Λαμβάνοντας υπόψη τα παραπάνω, μπορείτε να «ανταλλάξετε τους ρόλους τους» και να τους χρησιμοποιήσετε ως μήτρα παραγωγής και ως πίνακα ελέγχου κάποιου άλλου κώδικα. Οι κωδικοί που σχετίζονται με αυτήν τη μετατροπή καλούνται διπλόςο ένας τον άλλον. Έτσι, εάν η πηγή ήταν ένας κώδικας, τότε ο κώδικας θα είναι ο διπλός του.

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

Οποιοσδήποτε κωδικός με σχέση ικανοποιητικής απόστασης κώδικα (6.8) καλείται κωδικός με μέγιστη απόσταση.

Σχόλιο.Το όριο Singleton (6.8) είναι άχρηστο για δυαδικούς κώδικες, καθώς είναι σημαντικά κατώτερο σε ακρίβεια από τα όρια Plotkin και Hamming. Ωστόσο, παίζει σημαντικό ρόλο στην περίπτωση των -αρικών κωδίκων.

1.2.2. Πίνακας ελέγχου γραμμικού κώδικα

Από γραμμικό κώδικα Vείναι ένας υποχώρος, τότε για αυτόν υπάρχει ορθογώνιο συμπλήρωμα(ή μηδενικός υποχώρος). Ορθογώνιο συμπλήρωμα V" (n, κ) - κωδικός Vαποτελείται από όλα τα διανύσματα μήκους n, ορθογώνια σε κάθε διάνυσμα vÎ V. Τα διανύσματα ονομάζονται ορθογώνιο, αν το γινόμενο κουκίδων τους είναι 0. Για τα δυαδικά διανύσματα, το γινόμενο με τελείες είναι ίσο με το άθροισμα των γινομένων των αντίστοιχων συστατικών. Για παράδειγμα, κλιμακωτό προϊόν(00101, 10110) των διανυσμάτων 00101 και 10110 είναι το διάνυσμα 00100 = 0×1 + + 0×0 + 1×1 + 0×1 + 1×0. Το ορθογώνιο συμπλήρωμα είναι επίσης ένας υποχώρος και επομένως μπορεί να θεωρηθεί γραμμικός κώδικας. Ενα μάτσο V" - ονομάζεται κωδικός διπλόςή διπλόςΠρος την V.

Ορθογώνιο συμπλήρωμα V" (n, κ) - κωδικός Vέχει διάσταση ( n-κ); κατά συνέπεια, οποιαδήποτε βάση του αποτελείται από ( n-κ)φορείς. Πίνακας γεννήτριας Νορθογώνιο συμπλήρωμα ονομάζεται μήτρα ελέγχουκώδικας V.

Εφόσον ο πίνακας ελέγχου αποτελείται από διανύσματα βάσης του ορθογώνιου συμπληρώματος, τότε το δυαδικό διάνυσμα Μεείναι μια κωδική λέξη εάν και μόνο εάν cNΤ = 0. Έτσι, ο έλεγχος για σφάλματα κατά τη μετάδοση μιας κωδικής λέξης περιορίζεται στον πολλαπλασιασμό δύο πινάκων αντί της απαρίθμησης όλων των κωδικών λέξεων. Πολλαπλασιασμός πινάκων, των οποίων η διάσταση είναι αρκετές χιλιάδες, με σύγχρονους τεχνολογία υπολογιστώντρέχει πολύ γρήγορα.

Ο πίνακας επαλήθευσης μπορεί να κατασκευαστεί με την εύρεση του θεμελιώδους συστήματος λύσεων για το αντίστοιχο σύστημα εξισώσεων. Μήτρα

από την προηγούμενη ενότητα δημιουργεί το παρακάτω σύστημαεξισώσεις:

Ο κύριος πίνακας του συστήματος συμπίπτει με τον πίνακα σολ. Αγνωστος Χ 1 , Χ 2 και ΧΤο 3 για το οποίο υπάρχει δευτερεύον μη ίσο με 0 μπορούν να δηλωθούν ως κύριοι άγνωστοι. Μετά το άγνωστο Χ 4 και Χ 5 είναι δωρεάν. Επιλέγουμε γραμμικά ανεξάρτητες τιμές 01 και 10 για αυτές και λαμβάνουμε συστήματα εξισώσεων:

Και

Από το πρώτο σύστημα που παίρνουμε Χ 1 = 1, Χ 2 = 0, Χ 3 = 1, δηλαδή η λύση αρχικό σύστημαείναι το διάνυσμα 10101. Από το δεύτερο σύστημα παίρνουμε Χ 1 = 1, Χ 2 = 1, Χ 3 = 0, δηλαδή η δεύτερη λύση στο θεμελιώδες σύστημα λύσεων είναι το διάνυσμα 11010. Έτσι, λαμβάνουμε τον πίνακα ελέγχου:

.

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

Η σχέση μεταξύ της απόστασης κώδικα ενός γραμμικού κώδικα και του πίνακα ελέγχου ισοτιμίας καθορίζεται από το ακόλουθο θεώρημα:

Θεώρημα 1.3.Κάθε μη μηδενική κωδική λέξη έχει βάρος τουλάχιστον w, αν και μόνο ανοποιαδήποτε συλλογή από wστήλες μήτρες Ν

Απόδειξη.Για οποιαδήποτε κωδική λέξη Μεισχύει η ισότητα cNΤ = 0. Αφήστε την κωδική λέξη Μεέχει βάρος u. Ας εξαιρέσουμε τα μηδενικά συστατικά του διανύσματος από την εξέταση. Η προκύπτουσα ισότητα θα είναι η σχέση γραμμική εξάρτηση uστήλες από Ν. Ως εκ τούτου, Νπεριέχει πολλά από uγραμμικά εξαρτώμενες στήλες. Υπάρχει λοιπόν μια λέξη βάρους στον κώδικα u, εάν και μόνο εάν στον πίνακα Νυπάρχει μια συλλογή από uγραμμικά εξαρτώμενες στήλες. Έτσι, όλες οι μη μηδενικές λέξεις κώδικα έχουν βάρος τουλάχιστον w w-1 στήλες μήτρας Νείναι γραμμικά ανεξάρτητη.

Ως συνέπεια των Θεωρημάτων 1.1 και 1.3, ισχύει η ακόλουθη δήλωση:

Συνέπεια.Απόσταση γραμμικού κώδικα όχι μικρότερη από w, εάν και μόνο εάν υπάρχει κάποια συλλογή από w-1 στήλες μήτρες Νείναι γραμμικά ανεξάρτητη .

Σύμφωνα με τις δηλώσεις που διατυπώθηκαν παραπάνω, προκειμένου να βρεθεί (Π,κ) - κωδικός που διορθώνει tλάθη, αρκεί να δημιουργήσετε μια μήτρα Νδιαστάσεις ( p - k) × n, στην οποία οποιαδήποτε 2 tοι στήλες είναι γραμμικά ανεξάρτητες.

Πίνακας γεννήτριαςΟ γραμμικός κώδικας ονομάζεται πίνακας μεγέθους, οι σειρές του οποίου είναι τα βασικά του διανύσματα.

Για παράδειγμα,

είναι η μήτρα δημιουργίας του κωδικού δύο λέξεων (000, 011).

δημιουργεί για τον κωδικό Β από το Παράδειγμα 6.3.

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

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

Ας στραφούμε στο πρόβλημα της αποκωδικοποίησης.

Ας υποθέσουμε ότι για κάποιο δυαδικό διάνυσμα όλες οι κωδικές λέξεις του -code , ικανοποιούν την ταυτότητα

στο οποίο δηλώνει το βαθμωτό γινόμενο των διανυσμάτων και .

Για ένα τέτοιο διάνυσμα θα πούμε ότι είναι ορθογώνιο. Έχοντας βρει ένα τέτοιο διάνυσμα, θα μπορούσαμε να ελέγξουμε χρησιμοποιώντας την ταυτότητα (6.2) εάν η ακολουθία που λαμβάνεται από το κανάλι είναι κωδική λέξη.

Σημειώστε ότι το (6.2) ισχύει για όλες τις κωδικές λέξεις εάν ισχύει για διανύσματα βάσης, π.χ. Αν

όπου ο εκθέτης Τ υποδηλώνει μετάθεση.

Όσο περισσότερους τέτοιους «έλεγχους» βρούμε, τόσο περισσότερα σφάλματα, προφανώς, θα μπορούμε να εντοπίσουμε και να διορθώσουμε.

Άσκηση 6.4. Να αποδείξετε ότι οι έλεγχοι σχηματίζουν γραμμικό διάστημα.

Ονομάζουμε αυτόν τον χώρο χώρο ορθογώνιο γραμμικός κώδικαςή χώρο δοκιμής.

Άσκηση 6.5. Βρείτε τη διάσταση του γραμμικού χώρου των επιταγών.

Για να ολοκληρώσετε την τελευταία άσκηση, πρέπει να παρατηρήσετε ότι ο πίνακας είναι ακριβώς γραμμικός ανεξάρτητες στήλες. Όχι περισσότερο (γιατί;) και όχι λιγότερο (γιατί;). Ας φτιάξουμε μια λίστα με τους αριθμούς αυτών των στηλών και ας καλέσουμε αυτό το σύνολο αριθμών σύνολο πληροφοριών. Λίγο αργότερα η σημασία αυτού του ονόματος θα γίνει πιο ξεκάθαρη. Ας επιλέξουμε αυθαίρετα διανυσματικές τιμές σε θέσεις που δεν περιλαμβάνονται σύνολο πληροφοριών. Ποιες πρέπει να είναι οι τιμές στις θέσεις του συνόλου πληροφοριών προκειμένου να εκπληρωθεί το (6.3); Για να απαντήσουμε σε αυτή την ερώτηση, θα πρέπει να λύσουμε το σύστημα γραμμικές εξισώσεις, και το σύστημα έχει μόνη απόφαση.

Το απόρροια αυτών των επιχειρημάτων είναι το θεώρημα

Θεώρημα.Η διάσταση του χώρου ελέγχου ενός γραμμικού κώδικα είναι ίση με .

Γράφουμε τη βάση του χώρου δοκιμής ως μήτρα

που ονομάζεται μήτρα ελέγχουκώδικας.

Οι πίνακες ελέγχου και δημιουργίας σχετίζονται με τη σχέση

Από αυτή τη σχέση βλέπουμε ότι για οποιαδήποτε κωδική λέξη έχουμε

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

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

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

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

όπου είναι ο πίνακας ταυτότητας της τάξης και είναι κάποιος πίνακας μεγέθους.

Ένας πίνακας της μορφής (6.6) ονομάζεται πίνακας παραγωγής που ανάγεται σε συστηματική μορφή, και καλείται ο αντίστοιχος κωδικός συστηματικός. Η κωδικοποίηση για συστηματικό κώδικα είναι λίγο πιο εύκολη από ό, τι για κώδικα γενική εικόνα:

, (6.7)

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

Για έναν συστηματικό κώδικα με έναν πίνακα δημιουργίας στη μορφή (6.6), ο πίνακας ελέγχου ισοτιμίας μπορεί να υπολογιστεί χρησιμοποιώντας τον τύπο

Άσκηση 6.6. Έλεγχος (6.7). Υπόδειξη: για να γίνει αυτό πρέπει να αντικαταστήσετε τα (6.8) και (6.6) με τα (6.4).

Πώς να βρείτε τη μήτρα ελέγχου ισοτιμίας για μη συστηματικό κώδικα;

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

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

Ας ορίσουμε τους επίσημους (δημιουργικούς) κανόνες με τους οποίους πραγματοποιείται η κωδικοποίηση, δηλ. μετατροπή μιας αλληλουχίας πληροφοριών σε κωδική λέξη.

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

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

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

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

Γραμμικό μπλοκΟ (l, /c)-κωδικός καθορίζεται πλήρως από έναν πίνακα μεγέθους G Προς τηνΧ Πμε στοιχεία δυαδικού πίνακα. Σε αυτή την περίπτωση, κάθε κωδική λέξη είναι ένας γραμμικός συνδυασμός σειρών του πίνακα G και κάθε γραμμικός συνδυασμός σειρών G είναι μια κωδική λέξη.

Θα καλέσουμε γραμμικούς κώδικες μπλοκ που ορίζονται με τη δημιουργία πινάκων κωδικούς μήτρας.Η συνήθης (κανονική) αναπαράσταση του πίνακα παραγωγής μοιάζει με αυτό:

Για παράδειγμα, για τον απλούστερο (4, 3) κώδικα με έλεγχο ισοτιμίας, ο πίνακας δημιουργίας θα μοιάζει με:

Αφήνω T -(t 1; t 2, ..., tk)θα είναι το μπλοκ μηνυμάτων που πρέπει να κωδικοποιηθεί χρησιμοποιώντας αυτόν τον κωδικό.

Στη συνέχεια η αντίστοιχη κωδική λέξη Uθα

Λαμβάνοντας υπόψη τη δομή του πίνακα σολσύμβολα κωδικών λέξεων Καιθα είναι έτσι:

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

Για παράδειγμα, εάν η ακολουθία εισαγωγής κωδικοποιητή t == (10 1), στη συνέχεια χρησιμοποιώντας τον πίνακα δημιουργίας ο κώδικας θα κατασκευαστεί ως εξής:

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

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

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

Ο κωδικός που ορίζεται με αυτόν τον τρόπο καλείται γραμμικό μπλοκ συστηματικό(Π,Κωδικός /cj με γενικευμένους ελέγχους ισοτιμίας.