| Περίληψη |
Η μετάδοση και η μεταφορά μηνυμάτων μέσω καναλιών είναι ένα σημαντικό πρακτικό πρόβλημα. Η θεωρία κωδικοποίησης ασχολείται με την εύρεση μεθόδων που ελαχιστοποιούν την πιθανότητα λάθους στην μετάδοση ενός μηνύματος. Η εξάπλωση της χρήσης ηλεκτρονικών υπολογιστών μετά την δεκαετία του 1950 έπαιξε τον καθοριστικότερο ρόλο στην ανάπτυξη των λεγόμενων κωδίκων διόρθωσης λαθών (error-correcting codes), κωδίκων, δηλαδή, που θα ανιχνεύουν και θα διορθώνουν λάθη που έχουν προκύψει κατά την μεταφορά μηνυμάτων. Η ανάπτυξη της αντίστοιχης θεωρίας οφείλεται κυρίως στους Shannon και Hamming. Ένας κώδικας αποτελείται από 3 βασικές παραμέτρους. Το πλήθος Μ των κωδικών του λέξεων, το μήκος n των κωδικών λέξεων και την ελάχιστη απόσταση d μεταξύ τους. Είναι σημαντικό να κατασκευάζουμε κώδικες οι οποίοι θα έχουν μεγάλο Μ και μικρό n για οικονομία στην μετάδοση του μηνύματος αλλά και μεγάλο d ώστε να μπορούμε να διορθώνουμε όσο το δυνατόν περισσότερα λάθη. Βασικός σκοπός της εργασίας είναι η εύρεση γραμμικών κωδίκων που μια από τις τρεις παραμέτρους, δοσμένων των άλλων δύο, είναι βέλτιστη. Αυτά τα προβλήματα ονομάζονται κεντρικά προβλήματα της Θεωρίας Κωδικοποίησης. Συνδέουμε το πρόβλημα της εύρεσης του μέγιστου n, δοσμένων των n k, d και q, για το οποίο υπάρχει ένας [n, k, d]q-κώδικας με ένα άλλο γνωστό πρόβλημα: το πεπερασμένο packing πρόβλημα, αυτό της εύρεσης του μεγαλύτερου n για το οποίο υπάρχει σύνολο που αποτελείται από n στοιχεία τα οποία είναι ανά d 1 γραμμικά ανεξάρτητα. Το πρόβλημα αυτό αν και λύθηκε γρήγορα για τις περιπτώσεις όπου d ≤ 3 παραμένει ανοικτό μέχρι σήμερα. Χρησιμοποιούμε Πεπερασμένη Γεωμετρία για να αντιμετωπίσουμε το πρόβλημα και παρουσιάζουμε όλα τα γνωστά αποτελέσματα μέχρι σήμερα. Επίσης, παρουσιάζουμε συνοπτικά την εξέλιξη των αποτελεσμάτων στην περίπτωση των MDS κωδίκων (κώδικες για τους οποίους ισχύει d = k + 1), την περίφημη βασική εικασία για τους MDS κώδικες. Στη συνέχεια επιχειρούμε μια άλλη προσέγγιση του προβλήματος αυτό της εύρεσης του ελάχιστου n δοσμένων των k, d και q, για το οποίο υπάρχει ένας [n, k, d]q-κώδικας. Το φράγμα του Griesmer μαζί με ένα θεώρημα του Belov μετατρέπουν το πρόβλημα μας σε ένα πεπερασμένο πρόβλημα. Παρουσιάζουμε όλα τα γνωστά αποτελέσματα στην περίπτωση των τετραδικών κωδίκων και τα πρόσφατα αποτελέσματα στην περίπτωση των δυαδικών κωδίκων. Τέλος, χρησιμοποιούμε την Θεωρία των Βάσεων Gröbner για να παρουσιάσουμε ένα αλγόριθμο αποκωδικοποίησης κυκλικών κωδίκων ο οποίος γενικεύεται για όλους τους γραμμικούς κώδικες.
|
Εύρεση και αποκωδικοποίηση βέλτιστων κωδίκων με χρήση Πεπερασμένης Γεωμετρίας και Βάσεων Groebner
