Αλγεβρικοί Κώδικες

Η ψηφιακά κωδικοποιημένη πληροφορία κατά την διέλευσή της διά μέσου διαύλων επικοινωνίας με διαταραχές υφίσταται συχνά αλλοιώσεις. Το αντικείμενο της Θεωρίας των Κωδίκων Διορθωτών Λαθών είναι η κωδικοποίηση της πληροφορίας με τέτοιον τρόπο, ώστε αν μικρό πλήθος αλλοιώσεων έχει υπεισέλθει σ’ ένα μήνυμα, η αποκωδικοποίησή του να τις διορθώνει. Σήμερα οι Κώδικες Διορθωτές Λαθών έχουν ευρεία εφαρμογή σε ηλεκτρονικούς υπολογιστές, σε σύμπακτους δίσκους, δορυφορικές επικοινωνίες, αποστολή φωτογραφιών από το διάστημα κλπ.
Η γέννηση της Θεωρίας των Κωδίκων Διορθωτών Λαθών ανάγεται στο περίφημο άρθρο του C. Shannon «A mathematical theory of communication» το οποίο δημοσιεύτηκε στα 1948 και στο οποίο αποδεικνύεται η ύπαρξη αποτελεσματικών κωδίκων. Από τότε μέχρι σήμερα πολύ ερευνητική εργασία έχει γίνει με την χρήση τεχνικών από την Aλγεβρα, την Συνδυαστική και την Γεωμετρία για την κατασκευή κωδίκων που να διασφαλίζουν την αξιόπιστη διακίνηση της ψηφιακής πληροφορίας.
Το παρόν σύγγραμμα διαπραγματεύεται κυρίως τους αλγεβρικούς κώδικες, δηλαδή κώδικες που έχουν αλγεβρική δομή. Απευθύνεται σε φοιτητές τμημάτων Μαθηματικών, Πληροφορικής, Πολυτεχνικών Σχολών αλλά και σ’ οποιονδήποτε ενδιαφέρεται για την κωδικοποίηση της πληροφορίας με σκοπό την προστασία της από διαταραχές που εμφανίζονται σε διαύλους επικοινωνίας. Απαραίτητες γνώσεις για την κατανόησή του είναι η βασική Αλγεβρα και Θεωρία Αριθμών.
Στην αρχή του συγγράμματος παραθέτουμε μία ενότητα όπου υπενθυμίζουμε όλες τις έννοιες από την Αλγεβρα και Θεωρία Αριθμών που θα χρησιμοποιήσουμε.
Στο πρώτο κεφάλαιο δίνουμε μία εισαγωγή στη κωδικοποίηση της πληροφορίας και στην αρχή που βασίζονται οι μέθοδοι διόρθωσή της.
Στο δεύτερο κεφάλαιο περιγράφουμε την δομή των πεπερασμένων σωμάτων και μελετάμε τις βασικές ιδιότητες των γραμμικών κωδίκων.
Το τρίτο κεφάλαιο είναι αφιερωμένο σε μερικές βασικές ανισοτικές σχέσεις που συνδέουν τις παραμέτρους ενός κώδικα.
Τρεις πολύ γνωστές οικογένειες γραμμικών κωδίκων με σημαντικές εφαρμογές, οι κώδικες του Hamming, οι κώδικες του Golay και οι κώδικες των Reed – Muller αποτελούν το αντικείμενο του τέταρτου κεφαλαίου.
Στο πέμπτο κεφάλαιο μελετάμε μία από τις πλέον σημαντικές κατηγορίες γραμμικών κωδίκων, τους κυκλικούς κώδικες.
Στο έκτο κεφάλαιο δίνουμε μερικές ακόμη ιδιότητες των πεπερασμένων σωμάτων τις οποίες χρησιμοποιούμε για την περιγραφή μίας πολύ ενδιαφέρουσας οικογένειας κυκλικών κωδίκων, τους κώδικες BCH, οι οποίοι έχουν ευρεία χρήση.
Τέλος, θα ήθελα να ευχαριστήσω τον μαθηματικό και υποψήφιο διδάκτορα του τμήματός μας Παρασκευά Αλβανό για την προσεκτική ανάγνωση των χειρογράφων και τις εποικοδομητικές παρατηρήσεις του.

Περιεχόμενα

Συμβολισμοί – Ορολογία

1 Κωδικοποίηση

1.1 Εισαγωγή

1.2 Απόσταση του Hamming

1.3 Τέλειοι Κώδικες

1.4 Ισοδυναμία Κωδίκων

1.5 Ασκήσεις

2 Γραμμικοί Κώδικες

2.1 Πεπερασμένα Σωμάτα

2.2 Ορισμός Γραμμικού Κώδικα

2.3 Γεννήτορες Πίνακες

2.4 Ισοδυναμία Γραμμικών Κωδίκων

2.5 Κωδικοποίηση Μηνυμάτων

2.6 Πίνακες Ελέγχου

2.7 Αποκωδικοποίηση με Πίνακα

2.8 Αποκωδικοποίηση με Πλειοψηφία

2.9 Απαριθμητής Βάρους

2.10 Το Θεώρημα του Shannon

2.11 Ασκήσεις

3 Φράγματα Κωδίκων

3.1 Κάτω Φράγματα

3.2 Παραγωγή Κωδίκων

3.3 Το Φράγμα του Singleton

3.4 Το Φράγμα του Plotkin

3.5 Το Φράγμα του Griesmer

3.6 Ασκήσεις

4 Μερικοί Αποτελεσματικοί Κώδικες

4.1 Κώδικες του Hamming

4.2 Κώδικες του Golay

4.3 Κώδικες των Reed – Muller

4.4 Ασκήσεις

5 Κυκλικοί Κώδικες

5.1 Ορισμός – Βασικές Ιδιότητες

5.2 Διάσταση Κυκλικού Κώδικα

5.3 Δυϊκός Κυκλικού Κώδικα

5.4 Κωδικοποίηση με Κυκλικό Κώδικα

5.5 Αποκωδικοποίηση Κυκλικού Κώδικα

5.6 Διόρθωση Ριπών Λαθών

5.7 Ασκήσεις

6 Κώδικες BCH

6.1 Αυτομορφισμοί του F_q

6.2 Ρίζες της Μονάδας

6.3 Κατασκευή Κωδίκων BCH

6.4 Κώδικες των Reed – Solomon

6.5 Αποκωδικοποίηση των Κωδίκων BCH

6.6 Ασκήσεις

Βιβλιογραφία
Ευρετήριο Όρων